Принципи на Функционалното програмиране. Увод в Scheme

Кратка история

През 1946 Фон Нойман измисля архитектура за изчислително устройство. То е сравително просто и се състои от входно/изходно устройство, оперативна памет и централно управление (Управляващо Устройство + Аритметично Логическо Устройство). Ще чуете връзката между оперативната памет (ОП) и процесора да бъде нарична 'гърло на бутилката' (на английски bottleneck) - по-надолу става ясно защо.
В зората на компютрите/програмирането на базата на тази архитектура са били измислени императивните езици за програмиране. При тях най-важното свойство е, че човекът (потребителят (user) / програмистът), ръчно задава точно определения начин, по който ще работи програмата (сега като четете това може да си кажете… а то има ли друг начин? Има.);

Така програмата става съвкупност от 2 неща:

• алгоритми
• структури от данни

Още информация

Може да се каже, че най основният оператор в императивните езици е операторът за присвояване (= в C/C++). Всички сметки, които правите на тях, трябва да се 'запишат' някъде в паметта, евентуално в структури от данни (опашка, свързан списък, стек, и т.н.) и евентуално да се ползват по-късно, като пак чрез присвояване се вземат от текущото им място и се сложат на ново и т.н.; Тези езици, макар и привидно задоволителни, имат следните много основни недостатъци:

• ниска мощност - през bottleneck-а (връзката между рамта и процесора) минават огромно количество 'ненужна информация'. Например адресите в паметта на променливите от които четем и в които пишем. Разбира се, информацията не е съвсем ненужна, но при така зле устроена архитектура просто няма как да се мине с по-малко. Името bottleneck идва от там, че това е най-бавната част от цялото нещо (няй-тясната част от бутилката). Т.е в днешно време паметта и процесора са ненормално бързи, но шината (system bus, това е bottleneck-а) по който пътува информацията е несравнимо по-бавен от тях. И тъй като постоянно се налага 2-те да си комуникират цялата система става страшно бавна (при евентуално друга архитектура и същите параметри биха се постигнали в пъти по-добри резултати)
• липсват полезни математически свойства - когато програмистът пише как става абсолютно всичко в програмата, възможно е да допусне някоя 'тъпа' грешка (всички сте дебъгвали досега, нали?). Програмите понякога изпадат в безкраен цикъл, понякога забиват, понякога просто не правят това, което трябва. Но когато програмистът трябва да мисли за всяка една отделна дребна частичка от кода това е съвсем разбираемо (затова никой не псува много програмистите за това, че пишат бъгави програми и трябва да се оправят известно време преди да ги пуснат наистина - ами просто нещото е достатъчно сложно и малките грешки са неизбежни). По-конкретно, в тази архитектура липсват свойства като
  • тотална коректност - алгоритъмът да работи за всички възможни входни данни
  • частична коректност - алгоритъмът да работи само за някакво подмножество на входните данни (примерно не позволява делителят да е 0, ако е нула на програмата е 'позволено' да забие)
  • да завършва винаги - т.е да не изпада в безкраен цикъл
• Горните 3 свойства може да ви се виждат много прости но на практика не е никак лесно да се гарантират във един императивен език като C (да не кажа невъзможно).

Хората oтдавна си задавали въпроса: а това ли е единствената алтернатива? Не може ли програмите да се пишат по-лесно, да решават практически задачи, да се допускат по-малко грешки при тяхното писане, да вървят по-бързо? Станало ясно, че в повечето области, в които се използват компютрите трябват сложни системи с изкуствен интелект, които биха били чудовищно сложни за писане на императивен език, освен това и много бавни. Тогава се появила идеята за декларативните/дескриптивните езици. Те се състоят от:

• списък от функции
• списък от равенства (различни от присвояването, за което говорихме по-горе). Още известни са като списък от факти.

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

Приложение

Къде са полезни декларативните езици? Когато ни интересува резултатът, а не начина, по който сме стигнали до него. Какво се прави, а не как се прави. Един пример за такъв език е HTML. Как щеше да изглежда една уеб-страница ако всеки път, когато нещо трябва да бъде, например, центрирано - пишехме целия нужен код за това? Всичко, къде на екрана трябва да се появи елементът, на колко пиксела от центъра трябва да се намира, къде да се поставя спрямо другите елементи в страницата… Цикли, If-else, случаи… Не. Просто в интернет щеше да има общо около 16 страници и толкова. А с декларативен език?

<center>Some Text</center>

Какво, а не как.

Видове езици

Следва кратка спецификация на езиците:

• Императивни
  • Процедурни
  • Обектно Ориентирани (може да са ви напълнили главата с много работи за ООП-то … и все пак това е императивен стил, за който важат същите недостатъци)
• Декларативни
  • Функционални
    • $\lambda$ смятане - LISP-по подобни
    • равенства
    • FP
  • Логически
  • Функционални + Логически
  • Генетични

LISP

Името идва от LISt Processing, или на български - "обработка на списъци". LISP¹-ът, като един много стар и използван език е мутирал в няколко варианта. Този, на който главно ще се учим в този курс се казва Scheme. За сега имайте едно на ум, че съществуват и други езици, които всъщност пак са LISP и че различията между различните 'мутации' понякога са значителни.

Елементи на LISP

Езикът предлага следното:

• примитивни изрази - това включва;
  • символи - в императивните езици още наричани идентификатори. Т.е това ще бъдат имена на фактически аргументи на функция, както и имената на самите функции. Тук имаме много повече свобода при избора на име. Следните знаци са позволени:
    • a-zA-Z0-9 - главни/малки букви и цифри
    • +-*/ - някои аритметични знаци (в императивните езици са забранени)
    • = < > - оператори за сравнение (пак забранени в императивните езици)
    • ?!@# - някои знаци, които съвсем са забранени в императивните
    • нямате право да ползвате "()[]{}, както и интервал
    • Примери:
      • ala_bala
      • 12tova+e-str@nen*no/pozvolen=identifikator
  • числа - цели и дробни, с произволно голяма точност - т.е няма да се притеснявате, че нещо може да се препълни. Записването е като на C/C++
    • Пример:
      • 12
      • -3
      • 12.432
      • 1е-9 (това е доста малко всъщност - 0.000000001)
  • низове - тук също нищо интересно - последователност от символи заградена с двойни кавички
    • Пример:
      • "ala bala"
      • "12fd{}32izvr@t#ni simvoli kakto i [kavi4ki] i wsi4ko drugo`"
      • "\"escape na dvoina kavi4ka s obratna pod4ka\": kaza nqkoj"
    • списъци - тук внимавайте, все пак целият език е създаден за обработка на списъци ;)
      • това са просто неща заградени в кръгли скоби (), и разделени с интервал (даже си спестявате запетайката ;))
      • Важното е, че може да са от какъвто си поискат тип, даже и в рамките на един списък.
      • Пример:
        • (1 2 3) - списък от целите числа 1, 2 и 3
        • ((1 2 3) (4 5 6)) - списък от 2 списъка с по 3 числа (може да го използвате (примерно) за матрица 2 x 3)
        • (1 (2 3 ()) (3.5 "h" (()) )) - това е списък от 3 елемента, първият е 1, вторият е списък от 3 елемента (2 после 3 после празен списък), последния елемент е списък от 3 елемента - 3.5, стринга "h", както и списък от празен списък.

Хайде стига суха теория - да видим малко код в действие (редовете започват с >, защото средата ви 'подканя' да въвеждате код. Редовете които не започват така са резултат от действието.

> ;всичко след този знак на реда е коментар (освен ако не е в низ)
> ;сумираме 2 числа
> (+ 1 2)
3
> ;сумираме 3 числа
> (+ 1 2 3)
6
> ;вадим 3 числа (от първото се махат останалите)
> (- 1 2 3)
-4
> ;намираме корен квадратен
> (sqrt 3)
1.7320508075688772
> ;проверяваме дали 2 е равно на 3 - резултатът естествено е false (#f)
> (= 2 3)
#f
> ;проверяваме дали 2 е равно на 2 - резултатът е true (#t)
> (= 2 2)
#t

Функции

Може би ви е направило впречатление, че всичко в този език е списък … няма случайни неща ;-). Както вече знаете, това е функционален език, и повечето неща, които ще се случват в него са създаване и извикване на функции. За да извикате функцията с име FUNC, и параметри ARG1, ARG2, …, ARGN трябва да напишете

(FUNC ARG1 ARG2 ... ARGN)
;; може да ви прилича на FUNC (ARG1, ARG2, ..., ARGN) 
;; което е най-близкото подобие на това в C/C++

което по своето същество е точно един списък, в който първият елемент е името на функцията, а останалите елементи са параметрите.

Когато езикът срещне тази конструкция, той започва да изчислява всеки един от параметрите, подадени на функцията. Всяко изчисление в езика се извършва в някакво обкръжение². Това е просто съвкупността от променливите(константите) и дефинираните функции на дадено място. Т.е обкръжението е просто списък от двойки - име, стойност. Разбира се, не трябва да ограничавате съзнанието си - зад 'стойност' може да стои цяла функция :-). Просто във функционалните езици функциите са нещо дотолкова нормално, че можете да си ги присвоявате насам натам, да им променяте кода след като сте го написали, да променяте обкръжението … но да не се отплесваме.

Създаване на нови имена/функции

Ето как се създават нови имена в текущото обкръжение:

> (define decimal-pi 3.14)
> (define fraction-pi (/ 22 7))
> decimal-pi
3.14
> fraction-pi

(1)

\begin{align} 3\frac{1}{7} \end{align}

Да! Наистина показва 3 и 1/7!

> ;избираме си пи да бъде десетичната дроб
> (define pi decimal-pi)
> (define r 10) ; радиус
> ;сега, естествено, ще намерим лицето на кръг с радиус 10 и приближение на пи 3.14
> (* pi r r)
314.0

Както може би сте отгатнали, дефинирането на нови двойки (име, стойност) в текущото обкръщение става чрез (привиден списък) започващ със ключовата дума define, последвано от името (или символ, както го дефинирахме по-горе), последвано от стойност, която, разбира се, може да се изчислява:

> (define <символ> <израз>)

Сигурен съм, че изгаряте от нетърпение да научите как се дефинират функции. Аз казвам да започнем с функцията за факториел:

(define (fact n)
  (if (= n 0)
    1
    (* n (fact (- n 1)))))

Нарочно съм подравнил така кода, за да е горе долу ясно кое след кое следва. Започваме с define, рaзбира се - тъй като дефинираме функция, се нуждаем не просто от име, ами и от списък с параметри, които функцията приема. За това първият параметър след define е списък от името на функцията, последвано от името на нейните формалните параметри (в случая n). Следва кодът на функцията - проверяваме дали n == 0, ако е 0 връщаме 1, иначе връщаме факториел от n-1 умножен по n. Няма return, няма типове данни … ако човек се вгледа внимателно обаче, ще види че има точно важните неща, без които съвсем не може.
if-ът е специална функция, която приема 3 параметъра, първият е условие, а резултатът от нея (функцията if) е вторият аргумент, ако условието е true, или третият аргумент, ако условието е false.

Ето как стоят теоретично нещата с дефинирането на функция:

(define (<име> <фп1> <фп2> .... <фпn>) ; фп e формален параметър
  <тяло>)

Например:

(define (Gosho a b c)
  (* a (+ b c))
)

(Gosho 3 5 8)
> 39

Е, това беше уводът в Lisp/Scheme, надявам се че ти е харесал.
Прегледай пак какво пише тук и започвай другите статии.

Footnotes

1. Lost In Stupid Parentheses

2. На английски се казва closure. Известно е още като "Всички променливи, които в момента са дефинирани"