1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J

if (!(t -> left)) { p = t; t = t -> right; delete p; }

else if (!(t -> right)) { p = t; t = t -> left; delete p; }

else { p = t -> left;

while (p -> right) p = p -> right;

t -> inf = p -> inf;

Del (t -> left, p -> inf);

}

}

template

void BinOrdTree::Create ()

{ DeleteTree (root);

T x; char c;

do {

cin >> x;

AddNode (x);

cout << “Enter more (y/n)? “;

cin >> c;

} while (c == ‘y’ || c == ‘Y’);

}
14. Основни конструкции в езиците за функционално програмиране. Дефиниране и използване на функции. Списъци. Функции от

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

Тук ще разглеждаме езика Scheme, който е пример за нестрог функционален език и е диалект на езика Lisp.

Математически основи на езика Lisp се основава на -смятането на Чърч. Основната структура в този език са списъците и чрез тях се моделират обекти от реалния свят.
Езикът Scheme притежава три механизма за изразяване:

• 
  примитивни изрази;
  
• 
  средства за комбинация;
  
• 
  средства за абстракция.
  

• 
  чете израз (read);
  
• 
  оценява израз (evaluate);
  
• 
  извежда оценката (print).
  

• 
  числа – с фиксирана или плаваща точка – на практика с неограничен размер;
  
• 
  символни низове – поредица от знаци, заградени в кавички (“ “);
  
• 
  вградени функции – например +, -, *, / и др.;
  
• 
  символни атоми – в процедурните езици са известни като идентификатори – поредица от букви или цифри, която трябва да започва с буква.
  

• 
  оценката на число е самото число;
  
• 
  оценката на символен низ е самия низ;
  
• 
  оценката на вградена функция е така наречения функционален (процедурен) обект – двойка съдържаща указател към среда и поредица от машинни инструкции, които реализират съответната функция;
  
• 
  за да има оценка един символен атом, той трябва да означава име на променлива или функция, т.е. предварително трябва да е дефиниран, ако не е дефиниран оценката на символния атом е неопределена.
  

Семантично списъците биват няколко вида и оценката им зависи от техния вид, ако искаме независимо от вида на списъка оценката му да бъде самия списък, използваме цитат по следния начин: (quote <списък>) или ‘<списък>.

(<функция> <ФактП 1> <ФактП 2> ... <ФактП n>).

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

Оценяването на комбинация се извършва по следното общо правило:

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

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

(define <име_на_променлива> <израз>).

Тук <име_на_променлива> е произволен символен атом, <израз> е произволен израз. Оценката на израза е <име_на_променлива>, но като страничен ефект се получава свързване на символния атом <име_на_променлива> с оценката на <израз> в специална работна памет, наречена среда. След като този израз е оценен, оттам нататък оценката на <име_на_променлива> ще бъде оценката на <израз>.

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

(define (<име_на_процедура> <ФормП1> …<ФормПn>) <тяло>).

Тук <име_на_процедура> и <ФормПi>, i = 1, …, n са символни атоми, <тяло> е редица от изрази, разделени с един или повече интервали. Оценката на израза е <име_на_процедура>, но като страничен ефект в средата, в която се извършва свързването се създава нов процедурен обект – той съдържа указател към текущата среда и код. Кодът се състои от параметрите

(<ФормП1>, …, <ФормПn>) и тяло (изразите в редицата <тяло>).

В езика Scheme при оценяването се използва т.н. модел на средите. При него, паметта, която служи за съхраняване на двойките (име, обект) се нарича среда. В началото на оценяването имаме дефинирана само една среда – наричаме я глобална. В процеса на оценяване могат да възникнат и други среди. Когато се създава нова среда тя винаги се явява разширение на вече съществуваща среда. Когато се извършва оценяване, то винаги се прави в контекста на някоя среда. Например, нека имаме средите E₀, E₁, …, E_n, като E₀ е глобалната среда и средата E_i е разширение на средата E_i-1, i = 1, …, n.

Да предположим, че търсим оценката на името A в E_n. В модела на средите това търсене се извършва по следния начин: започвайки от E_n, последователно обхождаме средите в обратен ред на разширяването (от E_i към E_i-1), до първия момент в който достигнем до среда E_k, в която е дефинирана двойка (А, обект). Тогава процесът на търсене спира и оценката на A е съответният обект. При това е възможно да е дефинирана двойка (А, обект1) в среда E_j при j < k, но това не променя нищо (локалните имена скриват глобалните).
Както вече казахме, оценяването на един съставен израз (комбинация) представлява обръщения към процедура.

Нека имаме следната комбинация:

(<процедура> <ФактП1> …<ФактПn>).

Ще опишем как се извършва нейното оценяване в модела на средите. Нека оценяването на комбинацията се извършва в средата E. <процедура> е израз, който определя процедурата, към която се обръщаме, <ФактПi>, i = 1, …, n са фактическите параметри на обръщението. Първото което се прави е в средата E да се оценят <процедура> и <ФактПi>, i = 1, …, n. За да е коректно оценяването, оценката на <процедура> задължително трябва да е процедурен обект и фактическите параметри трябва да съответстват на формалните параметри по брой, тип и смисъл.

Нека указателят в процедурния обект, който е оценка на <процедура> сочи към средата E. Тогава се създава нова среда E, която е разширение на E и в E всички формалните параметри на процедурния обект се свързва с оценките на съответните им фактически параметри. След това в контекста на средата E се извършва последователно оценка на изразите от тялото на процедурния обект. Оценката на последния израз от тялото е оценка на първоначалната комбинация в средата E.

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

Може да се докаже, че ако процесът на оценяване по апликативния модел завършва, то процесът на оценяване по нормалния модел също завършва и в резултат се получава една и съща оценка. Съществуват, обаче, много програми, които завършват изпълнението си по нормалния модел на оценяване, но не завършват по апликативния. Затова казваме, че нормалният модел е по-общ от апликативния. Езикът Scheme използва моделът на средите, в основата на който стои апликативният модел.

В някои случаи, обаче, например при работа с отложени безкрайни обекти Scheme използва нормалният модел.

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

(define (fact n)

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

(define (fact n)

(define (iterfact result m)

(if (> m n) result (iterfact (* result m) (+ m 1))))

(iterfact 1 1)

)

Оценяването на (fact 3) поражда следните процеси:

 (* 3 (* 2 (* 1 1)))  (* 3 (* 2 1))  (* 3 2)  6,

(fact 3)  (iterfact 1 1)  (iterfact 1 2)  (iterfact 2 3)  6.

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

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

Когато в своята дефиниция една процедура извиква себе си повече от веднъж, то забелязваме че броят на отложените операции става експоненциален. Процесите, които пораждат такива процедури наричаме дървовидно рекурсивни. Добър пример е процедурата за намиране на n-тото число на Фибоначи:

(define (fib n)

(if (= n 0) 1

(if (= n 1) 1

(+ (fib (- n 1)) (fib (- n 2))))))

Оценяването на (fib 4) поражда следния процес:

Вижда се, че това е твърде неефективна реализация, тъй като се правят излишни изчисления – (fib 2) се оценява 2 пъти, (fib 1) се оценява 3 пъти, (fib 0) се оценява 2 пъти.

Много по-ефективно е следното решение:

(define (fib n)

(define (iterfib a b counter)

(if (= counter n) а

(iterfib b (+ a b) (+ counter 1))))

(iterfib 1 1 0))

Оценяването на комбинацията (fib 4) се извършва по следния начин: (fib 4)  (iterfib 1 1 0)  (iterfib 1 2 1)  (iterfib 2 3 2)  (iterfib 3 5 3)  (iterfib 5 8 4)  5. Процесът е линейно итеративен.
Всяка процедура, която манипулира с процедурни обекти се нарича процедура от по-висок ред. По-специално процедурите от по-висок ред получават процедурни обекти като параметри или връщат процедурни обекти като резултат.

Предаването на процедурите като параметри дава възможност за осъществяване на по-голямо ниво на абстракция в програмите на Scheme. Синтактично, то се осъществява по начина, по който се предават обикновени параметри. Като пример ще реализираме абстракцията f (a) + f (next (a)) … + f (b). Тук чрез next се получава следващата стъпка, сумирането започва от a и продължава до b.

(define (sum a b next f)

(if (> a b) 0

(+ (f a) (sum (next a) b next f))))

По-ефективен е следният линейно итеративен вариант:

(define (sum a b next f)

(define (itersum i result)

(if (> i b) result

(itersum (next i) (+ result (f i)))))

(itersum a 0)

)

Примерно използване: (sum 1 5 (lambda (x) (+ x 1)) (lambda (x) x)) се оценява до 1+2+3+4+5 = 15.

(define (exponent f n)

(if (= n 0) (lambda (x) x)

(lambda (x) (f ((exponent f (- n 1)) x)))))

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

Примерно използване:

((exponent (lambda (x) (* x x)) 2) 3) се оценява до (3²)² = 81.
Основното предназначение на езика за функционално програмиране Scheme е работа със списъци. Списъците се реализират чрез точкови двойки. Точковата двойка е съставен тип данни в Scheme и тя представлява указател към двойна клетка, състояща се от лява и дясна част. Тези части сами по себе си могат да са точкови двойки или атоми. За да можем да работим с точкови двойки са необходими операция за конструиране на точкова двойка, операция за извличане на лявата част на точкова двойка и операция за извличане на дясната част на точкова двойка. Въпреки, че програмистите могат сами да си дефинират такива операции, за по-голяма ефективност те обикновено са вградени. В Scheme имаме:

(cons a b) – конструира точкова двойка с лява част оценката на a и дясна част оценката на b;

(car x) – извлича лявата част на оценката на x, която трябва задължително да е точкова двойка;

(cdr x) – извлича дясната част на оценката на x, която трябва задължително да е точкова двойка.