Функциональное программирование. Лекция 3. Определение функций и вычислимые формы

1. Функциональное программирование

Лекция 3.
Определение функций и
вычислимые формы.

2. Функциональные вычислимые формы

Вызов стандартной или пользовательской
функции;
Построение лямбда – выражения;
Вызов стандартной вычислимой формы языка

3. Использование префиксной нотации

cos(5)= (cos 5)
12,65+55,04*9,1=(+ 12,65 (* 55,04 9,1))
345/1281-(77+80)*(21+18)=
((/ 345 1281)
(*
(+ 77 80)
(+ 21 18)
)
)

4. Лямбда – форма в лямбда-исчислении

Операции теории лямбда
Аппликация – применение функции к аргументу
– исходная операция теории лямбда.
Применение
функции
f
к
аргументу
а
обозначается как fa.
а- фактический параметр.
Дополнительной
к
аппликации
операция абстракции.
является

5. Лямбда – форма в лямбда-исчислении

Функция одной переменной
Пусть t – выражение, возможно содержащее
переменную х. Тогда
λх.t(x) – функция, сопоставляющая
аргументу a значение t(a).
(λх.t(x))а= t(a)
(β конверсия) – аксиома теории
Функция нескольких переменных
fx=λy.f(x,y)
(ax)y=fxy=f(x,y).
a=λx.fx

6. Лямбда – форма в функциональном программировании

λх.t(x) (LAMBDA (x) (t x))
(λх.t(x))a ((LAMBDA (x) (t x)) a)
(λхy.t(x,y))a,b ((LAMBDA (x y) (t x y)) a b)
(λyx.t(x,y))a,b
((LAMBDA (y x) (t x y)) a b)
((LAMBDA (x y) (t x y)) b a)

7. Применение лямбда-выражения

cos(x)= (lambda (x) (cos x))
cos(5)= ((lambda (x) (cos x)) 5)
cos(-1)= ((lambda (x) (cos x)) -1)
x+y*z=(lambda (x y z) (+ x (* y z)))
12,65+55,04*9,1 =
((lambda (x y z) (+ x (* y z))) 12.65 55.04 9.1)

8. Конструирование функций

(LAMBDA (x) (t x)) - безымянная функция
(DEFUN f (LAMBDA (x) (t x)) ) - у функции
появилось имя f
(DEFUN f (x) (t x))
(lambda (x y z) (+ x (* y z)))
(defun f (x y z) (+ x (* y z))
(f 1243 998 234)

9. Ключевые слова лямбда-выражений

&OPTIONAL - необязательные параметры,
значения которых в вызове можно не указывать,
тогда они автоматически примут значение nil
&REST - переменное число параметров.
Количество указанных в вызове параметров
определит местность функции при вызове
&KEY
- ключевые параметры. В вызове
ключевые параметры начинаются с ":"
&AUX
- вспомогательные переменные
Действие ключевого слова распространяется до следующего ключевого слова.
Аргументы, расположенные до ключевых слов являются обязательными.

10. Примеры применения ключевых слов

(defun f (x &optional (y (+ x 2)) )
(* x y)
)
(f 6) 48
(f 6 4) 24

11. Примеры применения ключевых слов

(defun f (x &optional y &rest z)
(list x y z)
)
(f ‘a) (A NIL NIL)
(f ‘a ‘b) (A B NIL)
(f ‘a ‘b ‘c)
(A B C)
(f ‘a ‘b ‘c ‘d) (A B (C D))

12. Примеры применения ключевых слов

(defun f (&key x y z)
(* x y z)
)
(f :y 2 :x 1 :z 4) 8
(defun f (&key x y (z 4)
(* x y z)
)
(f :y 2 :x 1)
8

13. Функциональные вычислимые формы

Форма - символьное выражение, значение которого
может быть найдено интерпретатором.
Простые формы:
•константа,
•лямбда-вызов,
•вызов функций,
•вызов композиции функций.
Специальные формы:
eval,
quote,
set.
Лямбда-выражение без фактических параметров
вычислимой формой не является.

14. Категории вычислимых форм

- самоопределенные формы;
- символы, использующиеся в качестве
имен переменных;
- формы в виде списочной структуры
(управляющие формы).

15. Формы работы с контекстом

QUOTE, EVAL
Лямбда-вызовы или вызовы функций
Формы LET_

16. Последовательные связывания

(LET (списки связей)
вычисляемые формы)
(
(LAMBDA (формальные параметры)
вычисляемые формы)
фактические параметры)

17. Последовательные связывания

(Let ((a 4) (b 7) (c ‘r))
(list (+ a b) c))
(11 r)
(Let ((a 4) (b 7) (c ‘r))
(+ a b)
(list a b c))
(4 7 r)
(Let ((a 4) (b 7) (c ‘r))
(setq m (+ a b))
(list m c))
(11 r)

18. Последовательные связывания

(Let ((a 4) (b 7) (c ‘r))
(setq m (+ a b))
(list m c))
(Let ((a 4) (b 7) (c ‘r) (m (+ a b))
(list m c))
(Let* ((a 4) (b 7) (c ‘r) (m (+ a b))
(list m c))
(11 r)
error:
Unbound atom b
(11 r)

19. Последовательные вычисления

(PROG_
вычисляемые формы)
Progn
Prog1
Prog2

20. Последовательные вычисления

(Progn (setq a 4) (setq b 3) (+ a b) (* a b))
12
(Prog1 (setq a 4) (setq b 3) (+ a b) (* a b))
4
(Prog2 (setq a 4) (setq b 3) (+ a b) (* a b))
3

21. Ветвления: форма IF

(IF предикат
действие_да
действие_нет
)
(IF предикат
действие_да
)
(setq a 7)
(setq b 3)
(if (> a b) a b) 7
(if (> a b) ‘a ‘b) A
(setq a 3)
(setq b 7)
(if (> a b) a) NIL
(if (< a b) ‘a) A

22. Ветвления: CASE

(case key
(list-key1 f11 f12 …)
(list-key1 f11 f12 …)
…)
(case ball
(2 ‘неудовлетворительно)
(3 ‘удовлетворительно)
(4 ‘хорошо)
(5 ‘отлично))

23. Ветвления: COND

(cond
(p1 d1)
(p2 d2)
…
(pn dn)
)
(cond
((= ball 2) ‘неудовл.)
((= ball 3) ‘ удовл.)
((= ball 4) ‘ хор.)
((= ball 5) ‘ отл.)
)

24. Остальные формы ветвления

(when p f1 f2 …)
(unless (not p) f1 f2 …)
(cond (p f1 f2 …))
(if p (progn f1 f2 …) nil)

25. Циклические вычисления

DO - итерационное вычисление
PROG, LOOP - передача управления
THROW, CATCH -динамическое управление

26. Итерирование

(do
((var1 val1 step1) (var2 val2 step2)…)
(p_end f11 f12 …)
f21 f22 …)
(do ((f 1)) ((= n 1) f) (setq f (* f n)) (setq n (- n 1)))
(do ((f 1) (k 1 (+ 1 k))) ((= k n) f) (setq f (* f k)))
(do ((f 1 (* f n))) ((= 1 n) f) (setq n (- n 1)))

27. Передача управления

(PROG (var1 var2 …) oper1 oper2 …)
Среди операторов operi может быть символ
или число, тогда на него устанавливается
метка (LOOP)
переход к метке:
(GO метка)
(RETURN результат)

28. Передача управления

(Prog (f)
(setq f 1)
met (if (= n 1) ( return f))
(setq f (* f n))
(setq n (- n 1))
(go met))

29. Циклические вычисления

(LOOP f1 f2 …)
(setq i 7) 7
(loop (+ i 1) (setq b (* i 2)))
(loop (+ i 1) (setq b (* i 2)) (if (> b i) (return b))) 10