Функционално програмиране
Функционални езици
Основи
математически функции и ג-смятането
метод за дефиниране на функции без име – lambda функции (Alonzo Church, 1941)
Особености
- не използват променливи и оператори за присвояване ⇒ итеративните конструкции не са възможни
- Повторенията се реализират чрез рекурсия
- Програмите представляват дефиниране на функции
- еднакво представяне на код (функции) и данни
- Изпълнението на функция винаги дава същия резултат при същите входни параметри
- Проста семантика
- Задават множества от примитивни функции и функционални форми за конструиране на съставни функции, операции, и някои структури за представяне на данните
- Използват се по-често интерпретатори
- Чист функционален език – LISP, Haskell
- Нечист функционален език– Scheme, Common Lisp, ML(1980), … (диалекти на LISP), APL
- LISP
- Особености
- най-старият и най-разпространеният
- много диалекти
- първият диалект е за IBM 704
- За символна обработка и приложения със списъци
- Безтипов език
- Притежава императивни черти – променливи, присвояване и итерация
- Префиксен запис
(funname arg1 arg2 …argn)
- Механизъм на работа:
Четене – оценка – отпечатване
- Scheme (1975) – диалект на LISP
- Фукциите могат да бъдат стойности на изрази и елементи на списъци, могат да бъдат присвоявани на променливи и предавани като параметри
- Примитивни изрази (обекти)
- Атоми:
- Числа – цели и реални (7, -2.3)
- Константи – #t (true), #f (false)
- Символи – последователност от малки и главни латински букви, цифри и специални знаци без интервали, кавички и скоби (а, ав)
Идентификатори – символи, започващи с буква и означават имена на обекти
Числата не са символи. Символите представляват данни, процедури и идентификатори.
- Низове – последователност от знаци, заградена с кавички (“а в”)
- Списъци – наредена последователност от обекти, разделени с интервал и заградена с ()
- Обикновен – (1 2 3), () (nil), (1 (2 3))
- Комбинация
- Специална форма – всички вградени и потребителски процедури (функции)
- Оценяване
- Числа – като самите себе си
> 7
7
- Символи – в зависимост дали със символа е свързана стойност или не
> а (ако а е несъвързанa)
error
> а (ако а=5)
5
- Низове – като самите себе си
> “abc”
abc
- Обикновени списъци – като грешка
> (1 2 3)
error
- Специални форми – различно за всяка функция
- Примитивни функции
- +, * – с 0 или повече параметъра
- -, / – с 2 или повече параметъра
- sqrt – вдигане на квадрат
- Предикатни функции
- Определение – функции, връщащи логическа стойност
- (eq? arg1 arg2) – резултата е #t, ако аргументите са еднакви атоми,иначе връща ()
>(eq? ‘a ‘a) >(eq? ‘a ‘b) >(eq? ‘a ‘(a b))
#t () ()
>(eq? ‘(a b) ‘(a b))
() или #t
- (list? arg) – резултата е #t, ако аргумента е списък
>(list? ‘(x y)) >(list? ‘x) >(list? ‘())
#t () #t
- (null? arg) – резултата е #t, ако аргумента е празен списък
>(null? ‘(x y)) >(null? ‘()) >(null? ‘x) >(null? ‘(()))
() #t () ()
- Предикатни функции
=, <>, >, <, >=, <=
even? – проверява дали аргумента е четно число
odd? – проверява дали аргумента е нечетно число
zero? – проверява дали аргумента е нула
Scheme:
eq? – еквивалентност при символни данни
= – еквивалентност при числови данни
eqv? – еквивалентност при символни и числови данни
Функции за изход:
(display <израз>) – отпечатва на екрана
(newline) – нов ред
- Комбинации
- Определение: комбинацията представлява списък, чийто първи елемент е процедура (първият елемент се нарича операция, а останалите операнди).
- Оценяване: Оценява се операцията (процедурата), като нейната оценка е процедурен обект, който представлява последователност от машинни инструкции, които реализират операцията. Оценяват се операндите. Накрая процедурния обект се прилага върху оценените операнди.
- Пример:
> (+ 1 2)3
> (+ 1 2 3) – предимство на префиксния запис: произволен брой аргументи
6
- Специални форми. Примери
- quote – връща неоценения обект
(quote exp)
>(quote (1 2 3)) >‘(1 2 3) >’1
(1 2 3) (1 2 3) 1
- eval – връща като резултат оценения израз
Универсална функция, която може да оцени всяка друга функция ⇒ може да се използва като интерпретатор (McCarthy, 1965)
(eval exp)
>(set ‘expr ‘(+ 3 4)) >(set ‘y 123)
(+ 3 4) >(set ‘x ‘y)
>(eval expr) >x
7 y
>(eval (list + 3 4)) >(eval x)
7 123
>(eval ”x)
x
- Специални форми. Примери
- cond – оценява условен_израз_1, ако е false се оценява условен_израз_2 и т. н. докато се получи оценка true. След това се оценява съответния списък от изрази и получената оценка се връща като оценка на cond-израза. Оценката на списък от изрази е оценката на последния израз. Ако никои условен израз не е true се връща оценката на списъка от изрази след else.
(cond (<условен_израз_1> <списък_от_изрази_1>) Пример: (cond ((> x 0) x)
(<условен_израз_2> <списък_от_изрази_2>) ((< x 0) (- 0 x))
… (else 0))
(else <списък_от_изрази>))
- If – оценява се условен_израз и ако е true се получава като оценка на if-израза оценката на израз_1, иначе се получава оценката на израз_2
(If <условен_израз> <израз_1> <израз_2>)
Пример: (if (> x 0) 1 -1)
- Точкова двойка (S-израз)
- Определение: всеки атом е S-израз; ако X и Y са S-изрази, то (X.Y) е S-израз (X – глава, Y – опашка)
- Конструиране
(cons <глава> <опашка>) Пример: >(cons 1 2)
(1.2)
- Достъп до частите на точковата двойка
(car <точкова двойка>) Пример: >(car ‘(1.2))
(first) 1
(cdr <точкова двойка>) Пример: >(cdr ‘(1.2))
(rest) 2
- Списъци
- Съставен обект, вграден в Лисп
>(cons a1 (cons a2 … (cons an nil) … ))
(a1.(a2. … .(an.nil) … )) означаваме с (a1 a2 … an)
- Празен списък [] ([]=nil=#f)
- Конструиране
(list <елемент_1> <елемент_2> …) Примери: >(list 1 2 3) >(list 1 ‘(2 3))
(1 2 3) (1 (2 3))
(cons <глава> <опашка>) Примери: >(cons 1 ‘(2)) >(cons ‘(1 2) ‘(3 4))
(append <списък1> <списък2>) (1 2) ((1 2) 3 4)
- Достъп до частите на точковата двойка
(car <списък>) Пример: >(car ‘(1 2)) >(car ‘((1 2) (3 4)))
(first) 1 (1 2)
(cdr < списък >) Пример: >(cdr ‘(1 2)) >(cdr ‘((1 2) (3 4)))
(rest) (2) ((3 4))
(last)
- Списъци. Примери
>(car ‘а) >(car ‘()) >(car ‘(a))
error error/nil a
>(cdr ‘а) >(cdr ‘()) >(cdr ‘(a))
error error/() ()
>(cons ‘a ‘())
(a)
>(cons’() ‘(a b))
(() a b)
- Списъци
- Празен списък []
[]=nil=#f
- Основни алгоритми
- …
- Прости функции
- Видове
- обикновени
cube(x)=x*x*x cube(2)=8
- lambda
ג(x) x*x*x ג((x) x*x*x) (2)=8
- Методи за абстракция
- Синтаксис:
(define <име> <израз>)
- Оценяване – като оценка връща името, като преди това името е свързвано с оценката на израза
- Пример:
>(define pi 3.14)
pi
>pi
3.14
- Методи за абстракция
- Синтаксис:
(define (<име> <списък от аргументи>)
тяло)
- Оценяване – като оценка връща името на процедурата, като преди това с това име се свързва кода от тялото и списъка от аргументи (свързване на име с lambda-израз)
- пример:
>(define (cube x)
(* x x x))
cube
>(cube 2)
8
- Рекурсия
- Сума на елементите на списък
(define (sumlist d) (define (sumlist d)
(if (null? ‘d) (if (null? ‘d)
0 0
(+ (car ‘d) (eval (cons ‘+ d))))
(sumlist (cdr ‘d)))))
>(sumlist ‘(1 2 3))
6
- Повдигане на квадрат на елементите на списък
(define (list2 d)
(if (null? ‘d)
‘()
(cons (sqrt (car ‘d)) (list2 (cdr ‘d)))))
>(list2 ‘(1 2 3))
(1 4 9)
- Функции от по-висок ред
- Определение: Функция, чийто параметър е функция или връща като стойност функция или и двете (functional form)
- Видове
- Композиция на функции – резултата е едната функцията, приложена върху резултата на другата функцията (в оригиналния Lisp)
f(x)=x+2 g(x)=3*x h(x)=f(g(x))=(3*x)+2
(cdr (cdr ‘(a b c)))
- Конструкция – приема като параметър списък от функции, тези функции се прилагат към аргумента и резултатите се връщат като списък
g(x)=x2 h(x)=2*x f(x)=x/2 [g, h, f] (4) -> (16, 8, 2)
- Прилагане – приема като параметър една функция и се прилага към списък с аргументи, като резултата от прилагането се връща в списък
h(x)=x2 α(h, (2, 3, 4)) -> (4, 9, 16)
Scheme: (define (mapcar fun lis)
(cond ((null? Lis) ‘())
(else (cons (fun (car lis)) (mapcar fun (cdr lis))))))
>(mapcar (lambda (x) (* x x x)) ‘(1 2 3))
(1 4 9)
- Функции от по-висок ред
- Пример:
1) а+(а+1)+…+b 2) a3+(a+2)3+…+b3
(define (sum1 a b) (define (sum2 a b)
(if (> a b) 0 (if (> a b) 0
(+ a (sum1 (+ a 1) b)))) (+ (cube a) (sum2 (+ a 2) b))))
(define (sum a item b next)
(if (> a b) 0
(+ (item a) (sum1 (next a) b))))
1) (define (sum1 a b) 2) (define (sum2 a b)
(sum a id b +1)) (sum a cube b +2))
- Ламбда изрази
- Дефиниране на процедура “анонимно”, т. е. без да се свързва с име
- Синтаксис:
(lambda (<формални параметри>) <тяло>)
- Оценка: същата е като на define-изразите, разликата е, че няма свързване с име
- Примери:
(lambda (e) (car (cdr e)))
((lambda (e) (car (cdr e))) ‘(a b c)) e – свързана променлива
>b
(define (sum1 a b) (define (sum1 a b)
(define (term x) (sum (lambda (x) (* x x))
(* x x)) a
(define (next x) (lambda (x) (+ x 1))
(+ x 1)) b))
(sum term a next b))
- Локални променливи
- let – временно свързване на променливи с оценките на изрази
(let ( (<име_1> <израз_1>)
…
(<име_n> <израз_n>) )
<тяло>)
- Пример:
>(let ((а 5) (let ((a 7)) (* 5 a)) ⇔
(b 3) ((lambda (a) (* 5 a)) 7)
(+ *))
(+ a b))
15
- Функции като връщани стойности
f(x)=x3 Df(x)=3*x2
Df(x)=(f(x+dx)-f(x))/dx, dx – произволно достатъчно малко число
(lambda (x) – не се знае коя функция се получава
(/ (- (f (+ x dx)) като резултат
(f x))
dx))
(define (derive f dx) – процедура намираща производната
(lambda (x)
(/ (- (f (+ x dx))
(f x))
dx)))
>((derive cube 0.001) 5)
75.015
- Scheme
- Императични черти – имената могат да се свързват със стойности, които след това да се променят
- set!
- set-car!
- set-cdr!
- Статично свързване
- Използване в университетите
- Малък обем
- COMMON LISP
- Steele, 1984
- С цел комбиниране на възможностите на съществуващите диалекти ⇒ обширен и сложен
- Особености:
- Динамични и статично (по подразбиране) свързване
- Голям брой типове данни и структури (записи, масиви, комплексни числа и низове)
- Операции за вход и изход
- Пакетиране на функции и данни
- Императивни възможности като Scheme
- Комерсиален език (за ИИ)
- COMMON LISP
- prog – възможност за правене на последователности (в Scheme липсва)
(prog (<локални променливи>
<израз_1> – израз, които е атом се интерпретира
… като етикет
<израз_n>)
- go – прехвърляне на контрола към етикет в prog-израз
- return – има параметър, които става стойност на prog-израза
- dotimes, dolist – за конструиране на итерации
- prog1, prog2, progn – за построяване на последователности
- setq (=set!)
- defun (=define)
- COMMON LISP
(defun iterative_member (atm lst)
(prog ()
loop_1
(cond
((null lst) (return nil))
((equal atm (car lst)) (return t)
)
(setq lst (cdr lst))
(go loop_1)
))
(defun recursive_member (atm lst)
(cond
((null lst) nil)
((equal atm (car lst)) t)
(t (recursive_member atm (cdr lst)))
))
- ML
- Milner, 1990
- Статично свързване
- Синтаксис по сходен с Паскал, отколкото с Лисп
- Не е чист функционален език
- Деклариране на типове, строго типизиран, не е необходимо променливите да се декларират (type inferencing)
- Има exception handling
- Модулност с абстрактни типове данни
- Свързване на променливи със стойност, която след това не може да бъде свързана отново. При повторен опит се прави др. копие на променливата:
val <име>=<израз> val distance=time*speed;
- let-израз
let val <име>=<израз1> in <израз2> end
let val pi=3.14159 in pi*radius*radius end;
- ML
- Списъци, изброими типове, масиви, записи
- Декларации на функции:
fun <име> (<формални параметри>) = <тяло-израз>;
fun square (x : int) = x*x;
- Функции използващи само операциии със списъци, =, <> и със записи могат да бъдат полиморфни (за разлика с аритметични и логически операции и релациии с изключение на = и <>)
- Условен израз
If <логически израз> then <израз_1> else <израз_2>
- HASKELL
- Thompson, 1996
- Подобен синтаксис на ML
- Произход на някои от чертите на езика от Miranda (Turner, 1986)
- Статично свързване
- Строго типизиран
- Същия метод за type inferencing
- Чист функционален език
- Няма променливи и оператор за присвояване
- Няма императивни черти
- Техника за оценяване (lazy evaluation) – не се оценяват подизразите, докато тяхната стойност не стане нужна; параметрите на функцията се оценяват, тогава когато трябва да се оцени функцията; и се оценяват само веднъж
- Метод за дефиниране на безкрайни списъци (list comprehensions)
- HASKELL
- Дефиниция на функция
fact 0 = 1
fact n = n * fact (n – 1)
fact n
| n == o = 1
| n > 0 = n * fact (n – 1)
- Otherwise в условен израз
fun n
| n < 10 = 0
| n >100 =2
| otherwise = 1
- Функции със списъци
product [] = 1
product (a : x) = a * product x
(a – глава; х – опашка)
fact n = product [1..n]
- HASKELL
- Безкрайни структури от данни
positives = [0..]
evens = [2, 4..]
squares = [ n* n | n <- [0..]]
Сходни статии:
- Програмиране в C и C++ Кодирането или съставянето на програмата е реализация на алгоритмите чрез език за програмиране. Езиците за програмиране от високо ниво, какъвто е и програмният език C, се характеризират със задължителни синтактични...
- Програмиране на Basic ФОРМАТ НА ПРОГРАМНИЯ РЕД Програмните редове в Basic имат следния формат: nnnnn Бейсик_оператор[ : Бейсик_оператор. . . ] [ ‘ коментар] и завършват със символа за край на ред (Enter)....
- Програмиране от по-висок ред в C++ Функция, някои формални параметри на която са функции, се нарича функция от по-висок ред. В езика C++ е възможно формален параметър на функция да е указател към функция, а също...
- Начини за описание и въвеждане на входни данни в системите за автоматизирано програмиране (САП) Входни данни: размерни геометрични данни за повърхнините който обработваме. технологични данни за режещи инструменти, режими на рязане, последователност на обработваните преходи и др. Геометричните данни се вземат от чертежа на...
- Програмиране и използване на компютри. Програмиране на С++ Условие на задачата: Дадени са четири таблици,в които са записани цели шест цифрени положителни числа. Таблиците имат M реда и N колони(3 ≤ M≤10 и 3≤ N≤5).Напишете програма, с която...