Потоци

Здрасти. Днес ще се занимаваме с може би най-хитрата идея на функционалното програмиране въобще. Потоците.
Обикновено тук бих казал как точно това е елементът в Lisp/Scheme, който прави тези езици многократно по-добри от всички останали и как това е новата топла вода. Но, потоците са нещо толкова полезно, че кажи-речи всички други езици са откраднали идеята, и сега го има навсякъде.

Първо едно уточнение

Програмирането не е създадено в България. Джон Атанасов не е създал първия компютър, не е бил дори близко. Езиците за програмиране не се пишат на български, а човекът, който ги е превеждал, е бил бавноразвиващ. Като следствие, повечето термини са безнадеждно объркани, а повечето програмисти дотолкова са свикнали с чуждиците, че изпитват затруднения да говорят на собствения си език. В момента се сещам за поне 3 неща, които се превеждат като "поток" на български. За да ги различаваш по-лесно вбъдеще - "поток" ще наричаме това, за което се говори в тази статия, а за другите неща ще се правим, че не съществуват.

Списък от числа

Искам да отпечатам всички числа от 1 до 1 000 000. Под "отпечатам" се има предвид процедурата display.
Как ще стане тази работа? Ами, много просто. Правя си списък с процедурата interval, която преди време си дефинирах и изглежда така:

(display (interval 1 1000000))

После го печатам. Окей, това е лесно. Къде е проблемът?
Основно, че заемам един милион клетки памет за списък, който всъщност не ми трябва особено много.
Толкова ли не мога да си направя едно цикълче от a до b и да си върша операцията в него?
(define (for a b)
    (display a)
    (if (< a b)
        (for (+ a 1) b)
    )
)

Това работи. И не заема никаква излишна памет. Естествено, работи само и единствено за този пример с display и ще трябва значително да се постараем, за да тръгне с каквото и да било друго. Нямаше ли да е хубаво ако имаше някакъв лесен начин, някакъв инструмент за работа с големи огромни списъци, без да се заема цялата рам всеки път?
Щеше. И има. Инструментът се нарича Поток.

Безкраен списък от числа

Задачата от предишния раздел се оказа твърде лесна за хора с велики умения като нашите. Ето сега една по-гадна

Отпечатай ми всички естествени числа

Успех да го направиш с горната функция.
Основно свойство на естествените числа е, че те са безкрайно много. С досегашните методи ще кажем нещо от този род:
"За всички числа от 1 до безкрайност изпълни процедурата display." След това ще почакаме известно време.

Нека да опростим задачата.
Започни да печаташ естествени числа, а аз ще ти кажа кога да спреш.
Дадена е някаква функция end?, която връща истина когато е време да приключваме с потока, защото майка му1 го вика за вечеря.

Точоо, ела мама да папаш супичка.

Иди сега и го напиши. Написа ли го? Браво.

Задачата за изхвърлянето на боклука

Помниш ли как беше в гимназията? Прекарваш дните си бивайки тъп, а светът е красив, лесен и те обича. За идилията, която са тийнейджърските години, имаше едно единствено условие, едно единствено задължение:

Спасее, иди да изхвърлиш боклукааа…
- Добреее…

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

Това е и цялата идея на потоците.

Формална дефиниция

Поток е наредена двойка от два елемента. Първият елемент, наричан често head е някаква произволна стойност, текущият елемент на недовършения(и евентуално безкраен) поток. Вторият елемент, tail е функция, която при нужда ще генерира следващия елемент. Тоест, tail е обещание, че потокът ще продължи напред.2
Да вземем за по-лесно пак примера с естествените числа. Как ще генерираме всички естествени числа? Просто, също както с изхвърлянето на боклука - ще върнем две неща. Първото е единица, за да видят, че сме сериозни, а второто е обещание, че ако им трябва още, ще им дадем и двойка.3 Самото обещание се състои от две неща - Двойка, за да видят, че все още сме сериозни и обещание, че ако им трябва още, ще им дадем и тройка. Окей, тук вече има проблем. С текущите средства това няма как да се направи:

(define (integers)
    (define (ints a)
        (cons a (ints (+ a 1)))
    (ints 1)
)

Това доста очевидно е безкраен цикъл. Върнахме се в откъдето тръгнахме. Май тая работа с потоците ще се окаже, че не е толкова лесна, а? Май преди да свършим тази глава, ще трябва поне малко термини да си дефинираме.

Мързеливо оценяване

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

delay

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

force

force приема един аргумент, който е обещание, и връща пазения в него обект. Забележи, че кодът в обекта не се изпълнява докато не се викне force.

Идеята на мързеливото оценяване е нещо да не се гледа колко е, преди да ти потрябва.
Ето пример:

(define (five) (delay 5))
five
> #<procedure:five>
(five)
> #<promise>
(force (five))
> 5

Нещо повече, кодът в обекта се изпълнява точно веднъж, без значение колко пъти викнеш force. Ето един по-дълъг пример. Ако например напишеш:
(define (sum a b)
  (if (> a b) 0
      (+ a (sum (+ a 1) b))
  )
)

(define (seven) (delay
                  (sum 1 100000)
                 )
)

seven
> #<procedure:seven>
(seven)
> #<promise>
(force (seven))
> 5000050000
(force (seven))
> ...
(force (seven))
(force (seven))
(force (seven))
(force (seven))
(force (seven))
...

Ще забележиш, че програмата мисли около секунда докато отпечата първото 5000050000, но всеки следващ път го отпечатва почти веднага. Това е защото то си стои запомнено някъде и чака да бъде извикано.
Това почти винаги е хубаво нещо. Ако не ти харесва, скоро ще можеш да си го предефинираш да прави каквото си искаш.

Използване на потоци вместо списъци

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

for x in range(1, 1000000):
    print x

и
for x in xrange(1,1000000):
    print x

е, че едното не ти чупи компютъра от препълване на рама.
Окей, ако до момента не съм успял да те убедя, че потоците са нещо полезно, едва ли ще успея и вбъдеще, затова оттук нататък преминавам само на важната част.

Как се работи с потоци, вместо със списъци? Ами, много просто - пренаписваме си map/filter/accumulate4
Ето например една процедура за създаване на поток:

(define (cons-stream head tail)
    (cons head (delay tail))
)

По-наблюдателните ще забележат, че това няма да работи, защото tail ще се оцени при викането на cons-stream. След това и да му слагаме delay, и да не му слагаме, голяма работа. Спокойно, в Scheme тази функция е специална. Дефинирана е по малко по-различен начин от горния - чрез предпроцесорен макрос и не оценява аргументите си предварително. Какво означава това, ще учим друг път, но за тези, които знаят C/C++ - там го има 100% същото.
#| Това работи за R5RS стандарта. На друго може, а може и да не тръгне. |#
(define-syntax cons-stream
    (syntax-rules ()
        (
            (cons-stream x y)
            (cons x (delay y))
        )
    )
)

(define (head stream)
    (car stream)
)
(define (tail stream)
    (force (cdr stream))
)

Забележи, че никъде не се казва, че потокът трябва да е безкраен. Ето поток с два елемента:
(cons-stream 1 (cons-stream 3 '()))

Малко помощни функции. Процедура Map, написана за потоци, както и процедура за печатане на N елемента от поток.
(define (map-stream stream operation)
  (if (null? stream)
      '()
      (cons-stream
       (operation (head stream))
       (map-stream (tail stream) operation)
      )
  )
)

(define (print-stream stream n)
  (if (or (= n 0) (null? stream))
      '()
      (begin
        (display (head stream))
        (newline)
        (print-stream (tail stream) (- n 1))
      )
  )
)

Ето как се прави краен поток:

(define (finite-stream n)
  (define (str a)
    (if (> a n)
        '()
        (cons-stream a (str (+ a 1)))
    )
  )
  (str 1)
)

Ето и безкраен:
(define (infinite-stream)
  (define (str a)
        (cons-stream a (str (+ a 1)))
  )
  (str 1)
)

Малко примерчета:

(print-stream (finite-stream 10) 20)
; Резултатът е на един ред за прегледност
> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
(print-stream (map-stream (finite-stream 100000000) (lambda (x) (* x 2))) 5)
; Забележи, че това изкарва резултата веднага, не след 3 години.
> 2, 4, 6, 8, 10
(print-stream (map-stream (infinite-stream) (lambda (x) (* x 2))) 5)
; А това далеч не чака до безкрайност.
> 2, 4, 6, 8, 10

Задачи за упражнение

След тази сравнително дълга и сложна лекция, време е за малко гадни гадни задачи.

1. Разбери как реално работят потоците. Сериозно, успя ли от първия път? На мен поне ми трябваше повече. Иди обратно горе и го прочети пак.
2. Направи Filter операция за потоци. Да връща нов поток, но само с тези елементи, които отговарят на даден предикат.


3. Направи и разни други операции за потоци. Например, да събира два потока. Връща нов поток, всеки елемент на който е сума от съответните два елемента на входните потоци.

4. Програма, която да обединява два потока. Всеки нечетен елемент е от първия, а всеки четен - от втория.

5. Направи някакъв там клиширан поток с някаква рекурентна зависимост. Ама ако много те домързи да го мислиш, и го направиш с числата на Фибоначи, ще ти се разсърдя.
6. Направи безкраен поток, който по два зададени списъка от фрази генерира оригинални псувни.
(print-stream (insults '( - списък от предложения - ) '( - списък от заплахи - )) 3)
> "А ти що не отидеш да пасеш боровинки преди да съм ти накокошинил зарзавата?"
> "А ти що не си купиш две карти за градски транспорт преди да е свършила специалната оферта?"
> "А ти що не станеш на 60 преди да е дошъл Пешо с туршията?"

(Няма нужда да ги правиш да имат смисъл)
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License