Ламбда смятане. Неименовани функции

Функции от по-висок ред.
Функции първа класа

Здрасти. Аз съм зает човек. Знам, че и ти също. Затова днес ще го караме кратко, сбито и ясно. По темата.
Така.
Почти.

Кратка история на ламбда смятането.

Ламбда смятането (Lambda($\lambda$) Calculus) е формална система, създадена от Чърч и Клийни през тридесетте години на двадесети век. Това е сложна и интересна система, която се използва за доказателства за изчислимост, теория на рекурсията и други хубави неща. От тази система е взето, в общи линии, името. Нещо като отношението между математическия модел "Регулярен израз" и регулярните изрази в популярните днешни езици. Сериозно, можеше да ти кажа, че ламбдите в Lisp/Scheme идват от Half-Life и щеше да е същата работа. Даже може би малко по-интересно. Гордън Фриймън удря извънземни с гегата и си мисли "Земи тая ламбда, инопланетянска гад!". Както и да е.
Започваме вече по-интересните части от функционалното програмиране.

Функции първа класа

Това е термин от информатиката. Отнася се до езици - един език притежава функции от първа класа ако може да третира функциите като обект от езика. Тоест, да ги подава като аргументи на други функции, да може да се направи функция да връща друга функция… Да може да се складират функции в масиви, да се създават функции по време на изпълнение и(както се казваше в един филм)… още нещо.
Тук не се има предвид някакви дълбоки магии с компилатори, предпроцесори и така нататък. Ако се постараеш достатъчно и на Асемблер ще докараш такива неща, ама няма смисъл и ще ти отнеме едни десет години от живота. Впрочем, първа класа идва от това, че са VIP, не нещо друго. Както има първа класа в БДЖ, само дето тук реално е чисто и светло.

В голяма част от модерните езици присъстват функциите първа класа - просто защото са много, много удобни. Днес ще се убедим в това. Пример за това са Python1 и Ruby2 - там може да се правят какви ли не трикове точно заради ламбда смятането.
Във функционалните езици такъв математически модел е на практика неизбежен и задължителен, защото почти всичко се (основава на)/(свежда до) подаване на функции или връщане на генерирани нови функции. Впрочем, когато е изпълнено едно от тези две неща не казваме функция, а функционал. Функционалите са точно функциите от по-висок ред. Всички нови термини от този параграф са взаимнозаменями. Синоними. За обща кулутра, нали.

Ламбда в Scheme

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

(lambda (a b c) expression)

Тази ламбда функция приема три аргумента (a, b и c) и с тях оценява кода в expression.
Доста подобно на define. Нормално, нали пак си създава функция.
Има обаче една уловка. Ламбдите са като бананите през зимата. Страхотни са, ама ако не ги изядеш веднага, за нищо не стават. Така де, най-добре е такива функции да се викат още щом са направени. Виж следния пример:
(define (f a) (* a (+ a a)))
...
(f 4)
(f (f 5))

Супер! Хайде сега направи това с ламбди:
(lambda (a) (* a (+ a a)))
...
Ъъъ...

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

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

( (lambda x (* 2 x) ) 10 )

И резултатът ще е 20.

До момента, ако ни трябваше функция която, да речем, пресмята факториел от дадено число N, щяхме да си я кръстим

(define (factorial n) ...

По-несръчните от нас биха написали нещо такова
(define (f n) ...

или даже
(define (Gosho_e_velik Pesho_e_bastun) ...

Но най-големите майстори въобще няма да дадат име на функцията. Защо? Просто е. Ако, например, ти трябва някаква функция, която веднъж ще използваш и ще забравиш - кръщаваш я "A" и си я използваш. Да, ама ако ти трябва още една проста функция? "A" вече е заето, ще заемеш и "B". И така много пъти и накрая не остана място за функции. И ще почнеш да ги кръщаваш "GAIOMNQ", което не е добре.
Или ако ти трябва да си генерираш някаква функция в реално време. Не се знае какво ще има в нея, няма какво смислено име да се даде. Например, нещо което да работи с файлове. Вътре си отваряш файла и трябва да върнеш друга функция, която да позволява да се чете неговото съдържание. Ама за всеки файл това е различно. Примерно, ако е текстов файл да разчиташ текста във файла и ако се окаже, че това е валиден Scheme код, да връщаш функция, която изпълнява този код. В противен случай просто да връщаш функция, която казва колко реда е текстът и по дадено N да връща N-тия ред.
Е как ще стане, освен ако не си направиш функция по време на изпълнението на другата функция?

Така че, подостри си виртуалните моливи и се хващай да пишеш код.

Задачи

Както може би видя, в този урок нямаше нищо сложно. Естествено, възможно е съзнанието ти да е разбито, ако не си чувал преди за функции от по-висок ред(Оо, ама то можело ли?), но предполагам си поне втори курс и вече такива неща едвам-едвам ти вдигат едната вежда. Малко. Така че, време е за упражнения и това ще е за днес.

Да се направи функция (composition f g), която приема две функции като аргументи и връща тяхната композиция. Например, ако на composition се подадат функциите f(x) повдигане на квадрат и g(x)умножение по две, то композицията им ще е $c(x) = g( f(x) )$

Направи функция, която по зададено естествено число K да връща функция, която приема един параметър - число N и го повдига на степен K.

Дадена е функция f, която приема естествено число и връща естествено число. Да се напише процедура, която връща функция със следната характеристика: Приема две числа, a и b. Връща едно число x, за което се достига минимумът на F в интервала $[a,b]$. Тоест, ако е дадено:

(1)
\begin{align} \begin{array} f = (x - 2)^2 \\ a = 0 \\ \end{array} b = 5 \end{align}

То програмата трябва да върне 2, защото при $x = 2$, $f(x) = 0$ и това е най-малката стойност на $f(x)$ в инервала $[0,5]$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License