Codito ergo sum View RSS

Блогът на Стефан Кънев
Hide details



Machine Learning курс във ФМИ 29 Sep 2017 8:33 AM (8 years ago)

Заедно с г-н инж. д-р Лъчо решихме да водим курс по Machine Learning във ФМИ този семестър. Искам да разкажа накратко.

Последните години machine learning-а стана много популярен. Навлизането в него е трудно по ред причини – има концептуални моменти за разбиране, иска количество математика и отвън изглежда като черна магия. Ще направим смел опит да представим материала по най-разбираемия начин, така че всеки да има шанс да се справи. Специфично:

Ще направим кратки въведения във всичко, което ни е нужно – само толкова, колкото да може да обясним основния материал. Въпреки това, курса ще е труден – трябва да разгледаме три библиотеки (scikit-learn, XGBoost и TensorFlow), една интерактивна среда (jupyter) и основите на един език за програмиране (Python).

Основната ни цел ще бъде да се разходим из алгоритмите и да помогнем на студентите да изградят интуиция как да ги прилагат. Едва ли ще станете machine learning експерт, но пък ще имате много добра стартова точка.

Официалното име на курса е Практическо въведение в машинното самообучение с Python. Ще бъде две вечери на седмица, в интервала 19:00-21:00. Все още не е ясно кои – ще разберем по някое време следващата седмица. Поради грешка, програмата в момента казва един път на седмица. Записването за студенти става по стандартната СУСИ схема, но едва ли ще ви спрат на вратата ако не сте от ФМИ 🙂

Add post to Blinklist Add post to Blogmarks Add post to del.icio.us Digg this! Add post to My Web 2.0 Add post to Newsvine Add post to Reddit Add post to Simpy Who's linking to this post?

Не подценявайте XSS атаките 6 Mar 2017 8:52 AM (8 years ago)

Cross-site scripting атаките са лесни за подценяване. Отгоре изглеждат като „някой хакер може да изпълнява alert в браузъра на потребителите“, но е по-дълбоко. Ще ви разкажа за определен тип уязвимост, която често виждам да се подценява, а е много лесна са сериозна експлоатация.

Именно „има XSS през URL параметър, но той не се записва в базата“.

Пример

Нека си представим, че говорим за online магазин. Някъде в него има следния код:

<h1><? echo $_GET['title'] ?></h1>

Ако това е достъпно http://example.com/hack, то на следното URL е проблематично:

http://example.com/hack?title=<script>alert(‘hi’)</script>

Ако потребителя го отвори, ще изпълни alert('hi').

Въпреки това, този текст не се записва в базата. Няма как злонамерен човек да го изпълни в браузърите на останалите потребители. Единственият начин е да им изпрати URL-то по друг канал. Това може да е много трудно (един клиент обикновено не знае за другите) и слабо ефективно (по-опитни потребители ще разпознаят URL-то, много други няма да го отворят въобще).

И все пак, как това може да се експлоатира сериозно? Един вариант е чрез търговските представители (a.k.a. customer support).

Атаката

Ето как един „хакер“ може да се възползва от уязвимостта.

  1. Харесва си един продукт.
  2. Създава URL с JS код, който бърка в cookie-тата, вади session_id-то и го праща на друга система (например чрез GET). След това прави redirect към продукта.
  3. Минава адреса през bit.ly за да го направи по-малко притеснителен.
  4. Пише на support-а с въпрос като „Този продукт имате ли го наличен?“ или „Харесал съм тези две неща, кое бихте ми препоръчали“ и bit.ly адреса. От гледна точка на търговския представител това е валиден въпрос, на който иска да отговори.
  5. Две неща са много вероятни за support-а – (1) да не са силни технически и (2) да имат повече права в системата (или дори да са админи). Вероятно е да отвори линка и атакуващия да получи session_id-то му. Също е вероятно да не отрази артефактите около редиректа след първоначалното отваряне. Съответно, линка бива отворен.
  6. Атакуващия получава session_id-то и вече може да се log-не като support. Ако има админ права, може да ползва това за каквото си поиска (например да си даде 100% отстъпка за продукт). Ако няма – може да се ползва като стъпка към някакъв social engineering (ако има вътрешна messaging система, може да се представи за служител).

Безопасно на пръв поглед, но ето как резултира до админски достъп.

Вариации, защита и уточнения

Реалния свят обикновено не е толкова прост. Ред неща биха могли да бъдат различни и за двете страни:

Като цяло, най-сигурния начин да се пазите от това е да нямате XSS уязвимости. Което обикновено се казва по-лесно, отколкото се прави.

TL;DR

XSS атаките са лесни за подценяване най-вече защото са сложни и завъртяни. В сравнение с тях SQL injection-а е тривиален за разбиране – всеки схваща защо е лошо да може да изпълни DROP TABLE users с GET заявка. При XSS трябва повече подготовка, строене на сложно URL и дори пускане на сървър някъде другаде, който може да приема „открадната информация“. Въпреки това, привидно незначителни уязвимости могат да се окажат сериозни.

Не подценявайте XSS.

Add post to Blinklist Add post to Blogmarks Add post to del.icio.us Digg this! Add post to My Web 2.0 Add post to Newsvine Add post to Reddit Add post to Simpy Who's linking to this post?

Любимият ми пример за четимост 20 Feb 2014 2:37 AM (11 years ago)

Освен на Python, в курса ни във ФМИ се опитваме да учим студентите на „добър код“ (каквото и да значи това). Всеки семестър правим поне една лекция на тема „добри практики“ (спорно с каква успеваемост, понеже такива неща се учат с реални проекти, а не лекции). Искам да споделя любимия си пример.

Иде реч за това как може да направим кода по-ясен (revealing intent). Последователно показвам три различни парчета код, като след всяко питам какво прави. Първото е следното:

    movl    $0, –4(%rbp)
loop:
    cmpl    $12, –4(%rbp)
    jge     done
    leaq    _array(%rip), %rax
    movslq  –4(%rbp), %rcx
    movq    (%rax,%rcx,8), %rdi
    callq   _puts
    movl    %eax, –8(%rbp)
    movl    –4(%rbp), %eax
    addl    $1, %eax
    movl    %eax, –4(%rbp)
    jmp     loop
done:

Обикновено отговорът е:

Ъ? Ами…

Ако човек няма идея от assembly, декриптирането на този код е загубена кауза. Иначе – изглежда като цикъл и имената _array и _puts са подсказващи. Вероятно човек може да се сети, че това е компилираната версия на втория пример:

for (int i = 0; i < 12; i++) {
    puts(array[i]);
}

Тук всички дават следния отговор:

Извежда масив с 12 елемента

Съвсем точно.

Интересното е, че няма голяма „концептуална“ разлика между двете. Макар, втория вариант да е по-кратък (и „структуриран“), той казва същото – „извеждаме 12 низа“. Въобще не загатва какви или защо.

Третият пример се получава със съвсем лека промяна:

for (int i = 0; i < 12; i++) {
    puts(monthNames[i]);
}

Новият отговор е:

Извежда имената на месеците

Забележете, че само едно нещо е променено (array → monthNames), но отговора вече е на по-високо ниво на абстракция. „Масив с 12 елемента“ звучи като имплементационен детайл, докато „имената на месеците“ е общо-разбираема, непрограмистска концепция.

Това е фин детайл, но разликата е съществена. Изводи колко искаш, но на мен любимият ми е следния: опитвайте да кръщавате нещата на domain-а, вместо на имплементацията.

Add post to Blinklist Add post to Blogmarks Add post to del.icio.us Digg this! Add post to My Web 2.0 Add post to Newsvine Add post to Reddit Add post to Simpy Who's linking to this post?

IDE-то е наклонена плоскост 5 Feb 2014 3:11 AM (11 years ago)

Това са малко размисли на тема IDE-та (като Eclipse, IntelliJ и RubyMine) и редактори (като Vim, Emacs и SublimeText). Ще разкажа за един проблем с IDE-тата. Disclaimer: не смятам едните за строго по-добри от други – избора, както обикновено, зависи от контекста.

IDE-тата обикновено са оптимизирани около определен начин на решаване на проблемите. Когато искате да ги решите по различен начин, има два варианта. В първия случай IDE-то ви позволява, но поради „специфичността“ на подхода, губите част от неговите благинки. Във втория IDE-то въобще не поддържа тази възможност и тогава заобикаляте проблема отдалеч. Всичко това афектира качеството на проекта.

Илюстрация

Следва прост пример от RubyMine, от времето в което си играх с него. Проблемът вече е решен, но целта ми е да илюстрирам концептуален принцип, а не конкретен проблем.

Във версията, в която си играх за последно, имаше поддръжка на RSpec, но тя бе леко осакатена. Спекове в RSpec се дефинират така:

describe Thing do
  it "is fancy" do
    Thing.new.should be_fancy
  end

  it "looks cool" do
    Thing.new.should be_looking_cool
  end
end

RubyMine се справяше добре с пускането на тестовете и показване на резултати. Например, имаше shortcut за пускане единствено на теста, в който се намира курсора. Също, създава списък от неуспешни тестове, към които може да се навигира лесно (или да се пуснат само те). Дотук добре.

Да видим какво става, ако класът е в именовано пространство (Widget::Thing). Тогава аз (и не само) предпочитам следния код:

module Widget
  describe Thing do
    it "is fancy" do
      Thing.new.should be_fancy
    end

    it "looks cool" do
      Thing.new.should be_looking_cool
    end
  end
end

Така spec-а е поставен в самия модул. Това е напълно нормално Ruby. Предимството е, че Thing няма нужда да се квалифицира навсякъде с пълен път. Всичко работи нормално.

Освен RubyMine.

RubyMine просто нямаше поддръжа за spec-ове, написани така. Нито работеха клавишите за пускане на определен тест, нито въобще откриваше теста. Едната алтернатива бе да се пускат от терминала, което е изключително неудобно. Другата е да си направите специална задача, която да пуска този (или текущия) файл. Последното работи частично – няма нужда да ходите в терминала, но нито клавиша за „тест под курсора“, нито интерфейса за неуспешни тестове, работят.

RubyMine не е с отворен код, съответно, не може да решите този проблем. Може, обаче, да го заобиколите:

describe Widget::Thing do
  it "is fancy" do
    Widget::Thing.new.should be_fancy
  end

  it "looks cool" do
    Widget::Thing.new.should be_looking_cool
  end
end

Това работи, но всеки път трябва да квалифицирате класа с пълния път.

Първия код е очевидно по-добър, но не работи в IDE-то ви. Какво правите? Може да пускате тестове през терминала, но тогава губите част от IDE-то си. А може да изнесете describe извън модула и да квалифицирате имената с пълен път, но тогава губи кода ви. И в двата случая – лошо.

Имахме колега, работещ с RubyMine и той бе избрал втория път. От това страдахме всички. По-интересно – дори не бе осъзнал, че първият вариант е валиден. Бе пробвал да го направи по първия начин, но не бе сработило – не защото е невалидно, а защото IDE-то не го поддържа.

Проблема бе решен в следваща версия на RubyMine, но това остана като интересен урок. Решенията на въпросния колега не бяха мотивирани от кода, а на възможностите на средата му. Както и възприятието му за това кое работи и кое не.

Ами ако искахме да ползваме друга тестова библиотека, която няма поддръжа в RubyMine? Може би тя щеше да се справя по-добре, но липсата на поддръжка определено щеше да му вързва ръцете. Съответно, щеше да е по-вероятно да не я предпочете. Щеше да я вижда като нещо, което го забавя (поради липсата на tooling), докато останалите щяхме да го виждаме като нещо, което ни забързва.

Наклонената плоскост

Като програмисти, имаме навика да вървим по пътя на най-лесното съпротивление. Ако трябва да изберем между нещо, което става лесно в средата ни и нещо, което става трудно, обикновено бихме предпочели лесното. Дори трудния вариант да е „по-чист“, лесният е по-прагматичен. В крайна сметка, това също е фактор в цената на поддръжката.

Виждаме проекта през лещите на инструментите си. IDE-та са специфични. Правят някои неща лесни, но други остават трудни или почти невъзможни. Това афектира как предпочитаме да пишем код, какви инструменти използваме и дори какво смятаме за добър дизайн. Благодарение на auto-complete и class browser, сложна йерархия е много по-разбираема в Eclipse, отколкото в UltraEdit. Eclipse потребителя може да сметне за добър код нещо, което за UltraEdit потребителя е твърде сложно.

Това е „проклятието и благословията“ на IDE-тата – налагат подход. Когато този подход е подходящ за проекта, всичко е супер. Когато не е – започваме да вземаме грешни решения.

Различното в редакторите

Представете си същия проблем, но в SublimeText. RSpec плъгина е просто набор от shell скриптове и ruby файлове, които единствено пускат rspec (или rake) и извежат резултати, подходящи за Sublime. Бързично отваряте кода, добавяте нужните параметри и сте готови.

Дори да бяхте подбрали библиотека без поддръжка, може просто да копирате rspec плъгина и да го промените. Няма да е сложно и няма да отнеме много време.

В IntelliJ/RubyMine това няма как да стане. В Eclipse може, но съществената разлика е в простотата – всеки SublimeText потребител може да извърши тази задача, но колко Eclipse потребители дори знаят откъде да започнат да модифицират плъгин?

Редактори vs. IDE-та

Това значи ли, че IDE-тата не струват? Не, разбира се. Въпрос на trade-off. Някои неща стават лесно в редактори, други – в IDE-та. Това е едно от първите. Има други, които са елементарни в интегрираните среди и почти невъзможни в текстовите редактори. Автоматизиран refactoring е само един от примерите, за които се сещам.

Важно е да използваме добри инструменти. Но също толкова важно е да разбираме по какъв начин влияят на процеса ни. Ако единственото, което имате, е чук, то всичко изглежда като пирон. Инструментите ни влияят по комплексен начин на решенията ни.

Важно е да знаем кога те са породени от ограничения на IDE-то.

Бележки под линия

Add post to Blinklist Add post to Blogmarks Add post to del.icio.us Digg this! Add post to My Web 2.0 Add post to Newsvine Add post to Reddit Add post to Simpy Who's linking to this post?

Загубени в превода: Design Patterns 15 Jan 2014 2:32 AM (11 years ago)

Този пост е съставен от две неща – кратък rant за някои особености на българския език и странен паралел с designs patterns (които упорито няма да наричам „шаблони за дизайн“). Първо ще се опитам да ви убедя в загубената кауза да използваме „чуждици“ като „патърн“ (или „патерн“) и след това (за пореден път) ще се опитам да илюстирирам, че „дизайн патърните“ въобще не са нещо лошо, дори в език като Ruby.

Първо, няколко думи за употребата на design patterns. Ако не четете книгата отгоре-отгоре, ще видите, че това са „примери за добър дизайн, чиито идеи могат да се преизползват“, а не „рецепти за решаване на сходни проблеми“. По-важното нещо за преизползване са идеите зад pattern-ите, а не структурата на кода им. Дори имената служат за да навяват асоциации, а не да именоват структурно еднакви парчета код.

Това е изключително важно уточнение, поради най-честата грешка при прилагането на тази книга – преизползват се структурите (интерфейс IObserver и клас AbstractObserver), а не идеите зад тях (индирекция между клас, който прави нещо, и друг, който иска да знае за това).

Из превода

Следват, дефиниции на думите „шаблон“ и „pattern“. Едно речниково значение на „шаблон“ e:

мн. шаблони, (два) шаблона, м.
1 Образец (форма, калъп и др.), по който се изработват множество еднакви изделия. Шаблон за буква.
2 Прен. Само ед. Общоизвестен, изтъркан модел за творческа дейност, който води до еднообразие; липса на оригиналност. Мисли по шаблон.
3 Прен. Шаблонен израз. Речевите шаблони.

Ето и релевантната част от значението на „pattern“ от New Oxford American Dictionary:

pattern |ˈpat(ə)n|
noun
2 a regular and intelligible form or sequence discernible in the way in which something happens or is done: a complicating factor is the change in working patterns.
4 an excellent example for others to follow: he set the pattern for subsequent study.

Забавлява ме как този превод има грешка още в заглавието.

Впрочем, ето някои други възможности за превод, взети от българско-английския речник:

образец, пример, мостра, шаблон, еталон, кройка, диаграма, схема, стил, характер, устройство, строеж, структура, насока, тенденция, особеност

Аз лично харесвам първата – образец. Носи ми най-подходящата асоциация. И въпреки това, не ми харесва, понеже в този контекст „pattern“ е по-скоро жаргонна дума със специфичен смисъл.

Design patterns in Ruby, vol. 3

В кода на сайтовете на курсовете, които водим, имаме клас TaskChecker, който проверява предадените решения. Той прави следните неща:

  1. Намира всички решения, които трябва да пусне.
  2. Пуска тестовете на задачата с всяко решение (прави shell out за целта).
  3. Записва резултатите в базата.

Един от начините да пуснем проверка е с бутона „Провери решенията“ в сайта. Използва се message queue (Sidekiq) за да се изпълни всичко в background-а. Когато той приключи, резултатите са в базата и могат да бъдат разгледани от администратор, преди да бъдат обявени публично. Кода в worker-а е следния:

checker = TaskChecker.new task
checker.run

Банален клас с банален интерфейс.

Втората употреба е от Rake задача. Преподавателите могат да изтеглят решенията при себе си и да ги пуснат в локална версия на системата. Това е удобен начин да се провери дали тестовете са адекватни – понякога се „сгъбват“ с работещи решения на студентите, а друг път откриваме, че липсват проверки за често срещани грешки.

Ще бъде хубаво, ако Rake задачата показва някакво състояние: например, след всяка проверка показва колко теста са минали и колко не са. Кодът е следния:

checker = TaskChecker.new task

checker.on_each_solution do |s|
  puts "##{s.user_id} Passed: #{s.passed_tests} Failed: #{s.failed_tests}"
end

checker.run

(В оригинала променливата се казва solution, но тук я прекръстих на s за да бъде по-кратко)

Разликата е в извикването на on_each_solution. За незнаещите Ruby, това е като извикване на метод с един аргумент, който е анонимна функция. Последната има един параметър и принтира низ. TaskChecker запазва блока и го извиква след всяка проверка.

Как наричам това? Observer.

Но защо? В крайна сметка, няма еквивалентите на IObservable и IObserver. Няма addObserver, removeObserver и прочее.

Есенцията на този „образец за дизайн“ е индирекцията между класа, който изпълнява задачите, и кода, който го ползва. Тук имаме два клиента – worker-а на Sidekiq и Rake задачата. Първият го ползва единствено заради страничните му ефекти, докато вторият има нужда да знае малко повече и да реагира по подходящ начин (извежда по един ред за всяка проверка). Това е стандартно приложение на observer.

Какви биха били алтернативите?

Ето, че с малко вдъхновение от книгата може да измислим просто и елегантно решение. Ключовият момент е използването на observer като „pattern“, а не като „шаблон“.

Null Object

Впрочем, има още един „дизайн образец“ в TaskChecker – видяхте ли го? Намира се в конструктора. Полето @on_each_solution се инициализира с lambda { |_| }, което е функция на един аргумент, която не прави абсолютно нищо. Така run няма нужда от if, с който да проверява дали @on_each_solution е nil.

Това напомня на друг популярен pattern – Null Object. Това е хубав начин да се справим със специални случаи, без да експлозия от if-ове.

Не мисля, че null object-а е наложителен в този код – би бил достатъчно прост и с един if в run. Но не пречи.

В заключение

Design Patterns не е книга с рецепти, а каталог с идеи. Те са широко приложими, особено ако се вземе предвид как се пренасят в различни езици.

А „шаблони за дизайн“ е лош превод.

Add post to Blinklist Add post to Blogmarks Add post to del.icio.us Digg this! Add post to My Web 2.0 Add post to Newsvine Add post to Reddit Add post to Simpy Who's linking to this post?

Отварящата скоба и новият ред 10 Jan 2014 3:07 AM (11 years ago)

Върл привърженик съм на идеята, че няма значение каква е конвенцията, стига да се спазва от всички в екипа с религиозен фанатизъм. Дори веднъж, когато приготвях pull request за един проект, се усъмних, че не съм съвсем в тон със стилистиката му. Прегледах кода още веднъж, и установих, че автора никъде не е ползвал unless – вместо това навсъкъде прави if !. Никак не бях съгласен с тази идея, но това не бе моя проект и послушно заместих моя unless с неговия if ! преди да отворя PR-а. Но има една конвенция, която не ми се е налагало да следвам, и ми е трудно да си представя как бих я понесъл.

Говоря за отваряща „къдрава“ скоба на нов ред. Така и не схванах защо някой би предпочел да го прави. Но след като препрочетох K&R, мисля че разбрах откъде идва.

За щастие, това в днешно време се прави предимно в продуктите на Microsoft и някак ми се разминава да работя с така подреден код. Нито ми се струва по-информативно визуално, нито ми е по-лесно да разпознавам блоковете, нито мога да си представя някаква естетическа причина, поради която бих намерил това за „по-красиво“. С каквито и очи да гледам кода, всеки път се чудя защо трябва да се похабява по цял отделен ред.

Препрочитайки K&R, останах с впечатлението, че причината тази конвенция да се появи, е причината за повечето странни неща в софтуера – legacy.

В книгата дефинират функции така:

void print_strings(char **names, int size)
{
    int i;

    for (i = 0; i < size; i++) {
        printf("%s\n", names[i]);
    }
}

Забележете как само отварящата скоба на print_strings е на нов ред. Тази на for – и на if, while и прочее – е на същия ред. Причината за това? Промени в C стандарта.

Достолепния ANSI C стандартизира определянето на типове при параметрите на функции, при това, във вида по-горе. В по-ранните години на езика е ставало по следния начин:

void print_strings(names, size)
char **names;
int size;
{
    int i;

    for (i = 0; i < size; i++) {
        printf("%s\n", names[i]);
    }
}

Докато в днешно време ще се озорите да намерите компилатор, който изисква втория стил, едно време далеч не е било така (под „едно време“ разбирайте „преди повечето от нас да се родят“). В тази нотация е съвсем естествено скобата да е на отделен ред. Колкото и субективни да са естетическите въпроси, навярно всички ще се съгласим, че това скобата да стои след int size; би било „грозно“.

Тази времена са отдавна отминали, обаче, и сега първия стил е далеч по-приет. Всъщност, не се съмнявам втория стил да изненада немалко съвременни C програмисти. Въпреки това, тази конвенция не просто е намерила начин да оцелее, но и да се разпространи до другите конструкции, където въобще не е нужна.

Не успях да намеря друг източник на тази толкова странна според мен практика. Докато това не доказва нищо, не мога да не си мисля, че е една от страните в една от старите безполезни „религиозни войни“ (подобно на vi vs. Emacs) защитава legacy позиция. И докато бих спазвал тази конвенция, макар и с огромно неудоволствие, едва ли ще мога да се оттърся от усещането, че не режа краищата на ястието без причина.

А вие знаете ли друга, по-правдовоподобна история, за отварящата скоба на нов ред?

Add post to Blinklist Add post to Blogmarks Add post to del.icio.us Digg this! Add post to My Web 2.0 Add post to Newsvine Add post to Reddit Add post to Simpy Who's linking to this post?

Езици за програмиране и нотация 3 Jan 2014 3:00 AM (11 years ago)

Неведнъж са ми се чудели защо се занимавам със всякакви екзотични езици за програмиране. Има ред причини, и учудващо, всички са практически. „Учудващо“, защото приложението не е очевидно – докато няма скоро да пиша production на Io, научаването му направи Ruby кода ми по-добър. Дори преди години имаше подобна серия от блог постове – Как език X ме направи по-добър програмист в Y. Друг е въпросът дали няма по-ефективен начин от постоянното учене на езици. Това настрана, искам да разкажа за един интересен аспект на „програмистската полиглотност“, за който ще направя паралел с математиката.

В дебрите на (математическата) история

Макар числата да са ни известни от много отдавна, изглежда древните гърци поставят началото на математиката като наука. Сектата на Питагор, Евклид, Архимед и други са прекарали голяма част от живота си в „измислянето“ на алгебрата и геометрията, които сега се изучават в основното училище. Интересно е, че за цялата математиката до края на Средновековието в момента се изучава в него. Деца се справят успешно с неща, с които възрастни хора от „едно време“ са се измъчвали. Около Нютон и Лайбниц нещата започват да се променят и вече развиваме по-сложна математика. През следващите 200-300 години „избухваме“ с теория, която озорва дори сегашните магистри.

Можете ли да познаете каква промяна превръща математиката от нещо трудно и философско, в нещо, което десет годишно дете може да научи?

Нотацията. Най-същественото нещо за развитието на математиката е създаването на удобна нотация. Например, древните гърци не са разполагали с удобен запис на прости отношения. Евклид би казал „токът е право-пропорционален на напрежението и обратно пропорционален на съпротивлението“ (сметките за електроенергия са били сред честите теми за разговор из пазарите на Елада). Може да си представите колко по-трудно им е било. Съвременният човек е далеч по-ефективен:

$$ I = \frac{U}{R} $$

Разликата е дори по-голяма. До края на Средновековието са се ползвали римски цифри (древните гърци са ползвали подобен запис). Само вижте как се прави аритметика с римски цифри. Събирането и изваждането са играчка, умножението е зор, а делението си е направо хвърляне на боб. Нищо чудно, че римляните са имали нужда от сметало.

И нищо чудно, че математиката започва да се развива чак когато започваме да използваме арабски числа и подходяща нотация.

Защо нотацията е важна?

Виждам две причини. Първата е психологическа (neuroscientific?) – мозъкът ни се справя добре с написани символи и не-толкова-добре с абстрактни идеи, изразени в думи. Добрата символна система е основната причина да се справяме добре с писмен език. Когато нямаме добра нотация, създаваме едно (или няколко) междинни нива.

Ще се опитам да дам пример. Да вземем низа „ди оу джи“. Тук има няколко слоя на траснлация. Имаме (1) транскрибиране на кирилица на (2) три звука, които представляват (3) букви от латинската азбука, (4) образуващи дума. Далеч по-лесно схващате смисъла, ако напиша „dog“. При кратки думи не е толкова голям проблем, но ако напиша цял параграф (или блог пост?) по този начин, ще видите голям зор да стигнете до смисъла. Вероятно бързо ще се откажете просто да четете. Вместо това сигурно ще преведете от кирилското изписване до латински букви и после да прочете текста на английски. А ако не знаете латинската азбука? В подобно положение са били древните гърци.

Втората причина е прагматичност. Докато арабски числа се събират лесно наум, то колко е CCCLXXIX плюс CDLXIII? Ако тръгнете да го смятате, вероятно първо ще обърнете до арабски цифри, ще направите събирането с тях и ще обърнете резултата обратно до римски. Това е доста по-прагматичен начин да стигнете до отговора, DCCCXLII. Уви, римляните са виждали повече зор.

Обратно към програмирането

Препрочитам K&R и една задача ми направи впечатление:

Напишете програма, която замества всички табулации в началото на реда с четири интервала

Понеже това е C книга, нека да видим как изглежда решението на C:

#include <stdio.h>

int main() {
    int bol, c;
    bol = 1;

    while ((c = getchar()) != EOF) {
        if (bol && c == ‘\t‘) {
            printf("    ");
        } else if (c == ‘\n‘) {
            bol = 1;
            putchar(c);
        } else {
            bol = 0;
            putchar(c);
        }
    }

    return 0;
}

Обърнете внимание на нивото на абстракция. Трябва ясно да моделираме самото изчисление, както и да поддържаме състояние (bol, което ми се стори подходящо C име за „beginning of line“). Има ред малки детайли, в които няма да задълбавам (като представянето на булева стойност като цяло число).

Това не е лош код. Определено ще е бързичък. Може да се подобри по няколко начина. Например set-ването на bol на всеки символ може да се избегне и (вероятно) кода да стане по-бърз (с точност до компилатор). От stdbool.h може да вземем булев тип, което ще го направи малко по-ясен.

Ето и версия на Perl:

while (<>) {
    s/^\t+/’    ‘ x length($&)/e;
    print;
}

Две сериозни подобрения. Първо, обхождането по редове е изразено по-конкретно (с по-добра нотация) като while (<>) { ...; print; }. Второ, регулярните изрази изразяват табулациите в началото на реда по-ясно.

От друга страна, ако не знаете Perl, неща като <> и x length($&) не са съвсем очевидно. Да не говирим, че сигурно ще се чудите защо print не взема аргумент.

Ами Ruby?

STDIN.each_line do |line|
  puts line.gsub(/^\t+/) { |ws| ‘    ‘ * ws.length }
end

Една идея по-експлицитно, дори да е проста „транслитерация“ към Perl кода.

Нищо не ни пречи да ползваме while/getc цикъл в Ruby, нито да ползваме библиотека за регулярни изрази в C. Въпреки това, кода по-горе е „идиоматичен“ – този, който опитен програмист на езика би написал. Съответно, можем да кажем (с известни уговорки), че това е начина, по който „се мисли“ на тези езици.

Разбирането на смисъла също е интересно. В Ruby (и Perl) от кода е относително очевидно какво прави програмата (ако знаете Ruby (и Perl)), докато в C трябва да я „интерпретираме наум“ за да стигнем до извод. С известна неточност, може да кажем, че последните две програми са „по-декларативни“, докато първата – „по-императивна“.

Всичко тук е следствие от по-удобна нотация.

Обратно към многото езици

Всеки език, с идиомите си, ни научава на нов начин за изразяване. Понякога това помага да разберем по-добре нещо в „родния“ език (например Smalltalk ми помогна да схвана ООП-то в Java и design pattern-ите). Понякога не показва как нещо не-толкова-централно може да се окаже безценнен инструмент (Scheme ме научи на map, select и reduce). Понякога показват как да решим проблеми, за които „родния ни език“ не е проектиран. При всички случаи, научаваме нов подход.

И една идея по-нагоре, развиваме по-качествен начин на мислене за такива проблеми. Само защото друг език е подбрал различна нотация.

Бележки под линия

Add post to Blinklist Add post to Blogmarks Add post to del.icio.us Digg this! Add post to My Web 2.0 Add post to Newsvine Add post to Reddit Add post to Simpy Who's linking to this post?

Поглед назад V: още по-кратка ретроспекция на 2013 31 Dec 2013 8:06 AM (11 years ago)

По всички критерии, тази година бе една от странните. Гледайки назад, ми се струва, че съм постигнал срамно по-малко, отколкото ми се искаше. От друга страна, не е толкова малко, колкото си мисля. Нещата включват:

  1. Научих Clojure. Предвид, че знаех Haskell, Scala и Scheme, мислех, че няма много за учене. Бях приятно изненадан. Езика много ме вдъхновява и ентусиазъма ми е подобен на този, с който учех Ruby. Не писах на него колкото ми се искаше тази година, но мисля следващата да се реванширам.
  2. Минах през първите десет глави от Introduction to Algorithms и упражненията им. Не мога да повярвам, че толкова късно проявих по-сериозен интерес към алгоритмите. На тази възраст изглежда съм развил търпение към математиката и ми беше изключително забавно, макар и доста времеемко, да стигна до там. Structure and Interpretation of Computer Programs ряпа да яде – доста повече работа има в решаването на тези задачи. И все пак, много ми допадна и мисля догодина да продължа, дори с по-добри темпове.
  3. Говорейки за математика, старата ми любов към нея нещо се разпламени. Порешавах малко задачи и дори направих презентация, в която си известно преувеличаване може да се каже, че имаше нотки на математика. Подобно на алгоритмите, задачите ми доставят голямо удоволствие. Убеден съм, че няма да излезе нищо хубаво от това.
  4. Миналата година започна силно откъм спорт и завърши слабо. Тази е наобратно. Занемарих планинското си колело, но за сметка на това си взех шосейно. Започвах да правя тренировки от по два часа тичане и сериозно да си оправям стила на плуване. Докато има още много работа за добро темпо, нещата изглеждат добре. Може дори да се пробвам да завърша някое състезание. Проходих и на фитнес, макар че „секта“ може би е по-точната дума.
  5. Навъртях немалко километри зад волана. Направих едно пътешествие до Букурещ и друго до Атина. Изненадан съм, че колата ми го понесе. Приятно изненадан.
  6. Присъствах на пет чуждоземни конференции – Railsberry, EuRuKo, BaRuCo, I.T.A.K.E. и разбира се, NordicRuby. Направих някакво глупаво число презентации – броя ги 11, една от които на английски. Вероятно изпускам нещо.
  7. В този дух, имаше го и цялото турне, което бе бая работа, колкото и да се изплъзвах от организаторски неща. Организирах и една друга, потайна конференция, която планирам да повторя в по-широк кръг.
  8. Прочетох срамно малко книги. За сметка на това, една от тях бе [Gödel, Escher, Bach: An Eternal Golden Braid][egb], на която се каня от 2007ма насам. Определено си струваше. Догодина сериозно се надявам на повече.
  9. Поднових си блога. Все още не съм писал достатъчно да имам съвсем пълно право да го казвам, но съм убеден, че този път ще се случи. Част от това включваше местенето на нов сървър, което може би не изглежда чак толкова сериозно нещо, но го усещам като голям milestone, предвид откога се каня.
  10. Не успях да реализирам един тон други амбиции като курс по TDD, преминаване на Emacs, прочитане и решаване на The Dragon Book и ред други. За сметка на това, не съм ги изоставил.

Догодина се надявам да завърша започнатите неща и да се хвърля на нови. Има доста пот за леене, код за писане, математика за схващане, книги за четене и какво ли още не.

Add post to Blinklist Add post to Blogmarks Add post to del.icio.us Digg this! Add post to My Web 2.0 Add post to Newsvine Add post to Reddit Add post to Simpy Who's linking to this post?

Защо не правим refactoring? 18 Dec 2013 4:31 AM (11 years ago)

От време на време ми се случва да чувам неубедителни причини защо във фирмата на познат да не се рефакторира. Неща като „клиентът не иска“ или „няма време“. Повечето се свеждат до няколко грешни схващания за refactoring-а, най-честата от които: трябва да се отдели специално време за него. Писах за нещо подобно преди време – рефакториране тип „чистене на гараж“ и тип „чистене на кухня“. С този пост ще се опитам да разкажа няколко неща, които биха помогнали за „убеждаването“ на колеги, мениджъри или клиенти, както и за имплементирането ѝ.

Следват няколко проблема с рефакторирането тип „гараж“ т.е. отделянето на по-дълъг интервал от време (ден-седмица) за преработка на част от системата.

Аргументацията е трудна

Представете си, че правите дълъг ремонт вкъщи. Един от майсторите ви казва:

Ще свалим всички керемиди от покрива и ще ги пренаредим. Няма да ги сменяме с нови или да променяме каквото и да е друго – просто ще ги разместим. Някои може да се счупят и ще трябва да се заменят. Ще отнеме седмица, през която няма да пипаме нищо друго. Ще ни платиш за тази работа.

Не звучи като нещо, което бихте приели. Вероятно клиентът/product owner-ът се чувства по същия начин, когато чуе „ще рефакторираме админ панела“. Седмица, която не носи бизнес стойност на проекта, изглежда като лоша инвестиция. Има сериозна разлика между възприятието на техничарите и на нетехничарите – за първите нуждата от refactoring е очевидна, докато вторите трудно могат да я проумеят. Или поне на пръв поглед.

В един момент човек си казва „Уф, този код трябва да се рефакторира“ и той идва по различно време при различните хора. Едни са склонни да тръгват да преработват рано, докато други – да отлагат дълго. Едни са ОК с по-сложен код, докато други държат на максимално простия. За едни е достатъчно да забележат неконсистентност или лош дизайн, докато други имат нужда емпирично да се убедят, че се работи трудно. Затова двама членове на един екип могат да са на коренно противоположни мнения, въпреки че работят с един код.

Цената е висока

От гледна точка на бизнеса, екипът трябва постоянно да доставя нова стойност. Ако следвате идеите на Lean Startup, искате редовно да ship-вате нова функционалност, които да валидират предположенията на бизнеса (например, че потребителите имат нужда от нея или как биха я използвали).

Дори да сте в по-инертна организация, времето прекарано в преработка на системата изглежда просто като загубено време. Основната аргументация е short-term vs. long-term gain – ако не оправим кода сега, в бъдеще ще сме много по-бавни (и бъгави) в произвеждането на нова функционалност. Колкото повече отлагаме, толкова по-лошо ще става. Това е прост и разбираем аргумент (технически дълг) – представен така, кара хората се вслушват. Но квантификацията е трудна – почти невъзможно е да се измери дали си е струвало.

Качеството е култура

Основната цел на рефакторирането е качество. Качеството е важно – прави кода разбираем, прави новата функционалност по-лесна за писане, позволява на нови хора да влязат по-лесно в екипа и дава повече гъвкавост на бизнеса. Все неща, които намаляват най-голямото перо в бюджета – поддръжката. Да не говорим, че прави работата по-приятна, което сигурно ще доведе до подобрения.

А качеството е подход. Ако веднъж сте го изтървали, няма да го възстановите и поддържате само с няколко дни на месец. Това ми напомня на следния цитат от „Зен и изкуството да поддържаш мотоциклет“:

You want to know how to paint a perfect painting? It’s easy. Make yourself perfect and then just paint naturally. […] The making of a painting or the fixing of a motorcycle isn’t separate from your existence. If you’re a sloppy thinker the six days of the week you aren’t working on your machine, what trap avoidances, what gimmicks, can make you all of a sudden sharp on the seventh? It all goes together.

Ако качеството е ниско, това е защото за екипа не е важно да го поддържа. Решението на проблема е промяна на възгледите и изграждане на навици, а не да се сещате за него само когато ножът опре до кокъла. Заменете „качество“ с „хигиена“ и ще получите по-убедителен аргумент – един ресторант се поддържа чист когато се чисти постянно, а не когато се чисти „само в неделя“.

Аргументите дотук

Какво излиза? Такава преработка е трудна за продаване, трудна за измерване и най-вероятно няма дългосрочен ефект. Нищо чудно, че немалко хора „не рефакторират“. Но както споменах в началото, това се дължи на схващането му като „чистене на гараж“. А далеч по-ценното е „чистенето на кухня“. И се прилага по-лесно.

Може да следвате следните простички правила:

Първите две правила държат scope-а на рефакторирането малък, а третото се опитва да насърчава постоянни малки подобрения (Kaizen). Така качеството бавно и постепенно се подобрява – без големи паузи в разработката, без осезаеми забавяния и без long-term trade-off.

Защо наистина?

И стигнахме до истинската причината защо някой не прави refactoring – качеството на кода не е сред ценностите на екипа. Ако сте заварили лош код, но искате да го подобрите, не е нужно да зарежете всичко за месеци в преработка. Достатъчно е да правите по нещо малко всеки ден. Нужно е само всички замесени да придобият тази нагласа.

Add post to Blinklist Add post to Blogmarks Add post to del.icio.us Digg this! Add post to My Web 2.0 Add post to Newsvine Add post to Reddit Add post to Simpy Who's linking to this post?

Understanding Computation 15 Dec 2013 12:00 AM (11 years ago)

Дискретната математика бе един от най-забавните за мен предмети в университета. Не ми се отдаваше и не бе безкрайно полезна в работата ми, но пък разказваше за мистични неща като „крайни автомати“, „стекови автомати“ и „машини на Тюринг“. Шантави работи, последните от които имали мощността на който и да е език за програмиране. Не запомних много, но у мен остана усещане, че това е много интересна материя. От тогава все ми се искаше да се върна към нея. Тази книга ми даде възможност.

Understanding Computation корица

Understanding Computation разказва за изчислимост. Това е дял от компютърните науки, който разглежда различни модели за изпълнение (машини) и на какво са способни. Занимава се с ред забавни въпроси, като например дали една програма може да определи дали друга забива (не, не може). Примерите са на Ruby и за почти всичко обяснено има написан код, който го симулира.

Книгата започва с прост език за програмиране и няколко начина, по които може да бъде имплементиран. След това скача на всевъзможните изчислителни модели – крайни автомати, стекови автомати, машини на Тюринг и недетерминистичните им версии. Показва как регулярни изрази се изпълняват с крайни автомати, как езици могат да се разпознават с недетерминирани стекови автомати и как машина на Тюринг може да симулира друга машина на Тюринг. Показва ред забавни неща, включително един алгоритъм за минимизация на краен автомат, който ми се стори толкова невероятен, че трябваше да го пробвам, за да се уверя, че наистина работи.

След това, книгата разказва за ламдба смятане. Обяснява основните положения, показва Y комбинатора и дори имплементира FizzBuzz (наред с числа, масиви и низове) само с анонимни функции (като в тази презентация). Последното е впечатляващо – беше ми изключително трудно да си представя как може да се направи аритметика само с ламбди.

Всъщност, ламбда смятането не е единствения универсален модел. Има ред други, кой от кой по-шантав, които е трудно човек да повярва, че са равномощни с машина на Тюринг (и съответно който и да е език за програмиране). Няколко такива са разгледани и още ми е трудно да ги приема (например Rule 110 или йота комбинатора).

Ако имате интерес към любопитните аспекти на компютрите, тази книга ще ви хареса. Написана е на достъпен език – нямате нужда от „академични“ познания по компютърни науки. Ако сте учили това в университета, може да ви опресни паметта. Ако не сте – ще откриете цял нов свят.

Add post to Blinklist Add post to Blogmarks Add post to del.icio.us Digg this! Add post to My Web 2.0 Add post to Newsvine Add post to Reddit Add post to Simpy Who's linking to this post?