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

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

Лисп - язык функционального
программирования

2. Функциональная программа

Определение функции
Вызов функции
Указать имя и
Задать имя функции
Определить количество
входных параметров
Описать тело функции
(без указания возвращаемого
параметра)
фактические значения
входных параметров
Описать тело функции с
фактическими
параметрами
Использовать лямбдавыражение

3. Преимущества ФП

Кусочное тестирование
Константность представления данных
Отсутствие побочных эффектов
Возможность параллелизма
Замена кода без остановки процессов
Машинная оптимизация кода на основе анализа
функций
Использование функций высшего порядка
Упрощение функций (каррирование)
Ленивые (отложенные) вычисления

4. Недостатки ФП

Ленивые вычисления

5. Заблуждения относительно языка Лисп

Лисп – язык программирования
«искусственного интеллекта»
Лисп – язык списочных структур
Лисп – это интерпретатор
Лисп не экономит память
Лисп – бестиповый язык
Лисп – функциональный язык
программирования

6. Лисп как язык функционального программирования

Лисп
Алгебра
списочных
структур
лямбда-исчисления
Теория
рекурсивных
функций

7. Списочное представление данных

Список – это объект данных, содержащий конечное
число других объектов (элементов списка).
голова
Элемент списка
хвост
Список без головы
Атом (atom)
Список (listp)
Базис работы со списком
селекторы
CAR (отделение головы)
CDR(отделение хвоста)
конструктор
CONS(построение списочной ячейки, cons-ячейки)

8. Определение функции в лямбда-нотации

Лямбда-теория
Функциональная программа
x. f ( x )
(LAMBDA (x) (f x))
Вызов функции производится в ПРЕФИКСНОЙ нотации
(f x1 x2 x3 …)
f
Функтор
Блокировка от селекции:
(x1 x2 …)
Кортеж аргументов
QUOTE (f x1 x2 x3 …)

9. Область определения языка программирования Лисп

АТОМ
числовой (только
значение объекта)
символьный (имя или
значение объекта)
логический (T, NIL)
СПИСОК
Простой (состоит
только из атомов)
Составной (может
состоять из
подсписков и атомов)

10. Списочное представление лисп-объектов

Вызов функции производится
в ПРЕФИКСНОЙ нотации:
(f x1 x2 x3 … xn) = f(x1, x2, x3, …, xn)
(f x1 x2 x3 …xn)
f
(x1 x2 …xn)
Функтор
Кортеж
аргументов
Блокировка от вычисления: QUOTE = ‘
QUOTE (f x1 x2 x3 … xn) = (f x1 x2 x3 … xn)
(+ 2 3) = 5
‘ (+ 2 3) = (+ 2 3)
Блокировка символа представляет его как значение!

11. Атомы

Символ
Числовой атом
Используется в качестве
Не нуждается в
блокировке от вычислений имени для объекта
Применим в
арифметических
выражениях
Имя и значение
совпадают
Применяется как значение
объекта
При блокировке от
вычислений имя и значение
совпадают

12. Связывание объекта и символа

(set символ объект) – вычисляет символ и
связывает его значение с объектом
(set ‘one 1)
one
1
one 1
2
(set one 1)
(set ‘one 2)
Nonsymbolic Argument Break: (SET 1 1)
one 2

13. Связывание объекта и символа

(setq символ объект)
(set (quote символ) объект) связывает сам
символ (не вычисляя) с объектом
(setq one 1)
one 1
(setq ‘one 1)
Nonsymbolic Argument Break:
(SETQ (QUOTE ONE) 1)
(setq one 2)
one 2

14. Связывание объекта и символа

(setf символ объект) функция обновления
данных в связанной списочной ячейке
(setf two 2)
(setq one 1)
(setf one 2)
two 2
one 2
one
1
2

15. Применение форм семейства SET

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)
(setq x 12,65)
(setq y 55,04)
(setq z 9,1)
(+ x (* y z)))
(setq x -98)
(setq y 1255)
(setq z 432)
(+ x (* y z)))

16. СПИСКИ

Рекурсивный объект функциональной программы
без блокировки вычисляется функция,
связанная с символом – головой списка
при блокировке является значением
объекта

17. Базис Лиспа

Определение объекта
* Atom (базовый предикат)
(atom ‘d) => T
(atom ‘(+ 5 3)) => NIL
(atom (+ 5 3)) => T
(car ‘(d)) => d
(car ‘(+ 5 3)) => +
(car (+ 5 3)) => error
* cdr ( список без головы хвост)
* Listp ( определяется как
not(atom))
(listp ‘d) => NIL
(listp ‘(+ 5 3)) => T
(listp (+ 5 3)) => NIL
Конструкция «список»
* car (голова списка)
(cdr ‘(d)) => NIL
(cdr ‘(+ 5 3)) => (5 3)
(cdr (+ 5 3)) => NIL
*cons (построение
списочной ячейки)
(cons ‘(d) (g)) => ((d) g)
(cons 5 3) => (5.3)
(cons 5 (3)) => (5 3)

18. Базис Лиспа

Сравнение объектов
* Eq (сравнение
(eq ‘d ‘g) => NIL
(eq 5 5) => T
(eq 5.0 5) =>NIL
символьных атомов)
* Eql ( сравнение любых
атомов)
* Equal (сравнение
списков)
* Equalp ( сравнение всех
Лисп-объектов)
(eql ‘d ‘g) => NIL
(eql 5 5) => T
(eql 5.0 5) =>T
(equal ‘(d) ‘(g)) => NIL
(equal (5) (5)) => T
(equal (5.0) (5)) =>NIL

19. Базис Лиспа

Арифметические операции
* аддитивные (х+у, х-у)
* мультипликативные (х*у, х/у)
* математические функции
* логический базис
(- 2 3) => -1
(+ 4/5 7/12) => 1.3833333
(* 4 7) => 28
(/ 3/4 3/5) => 1.25
(mod 3 2) => 1
(abs -2) => 2
(evenp 3) => NIL
(oddp 3) => T
(and T NIL) => NIL
(or T NIL) => T
(not T) => NIL