Введение в функциональное программирование
1920-30 гг. – заложены основы ФП
Теоретическая основа – комбинаторная логика (Шейфинкель, Хаскел Капс)
Чорч – λ-исчисление
Шаргей
ЛИСП – первый язык ФП (Джон Маккарти) – 1958 г.
LIST Processing = LISP
Развитие функциональных языков
Нет строгой типизации данных
На базе ЛИСПа создали ML, Miranda и многие другие (здесь есть строгая и т.д.)
Haskell – чистый функциональный язык
В 80-х годах Мартин Лёв создал теорию типов.
GNU Lisp
Турчин – РЕФАЛ
Теоретическая модель – нормальные алгоритмы Маркова
60-е годы
РЕФАЛ 2, РЕФАЛ 5.
1973 г. – аппарат ЛИСП-машины (Массачусетский университет)
1986 г. – Erlang (многопоточный)
Для РЕФАЛа также создан аппаратный процессор.
При разработке систем искусственного интеллекта ЛИСП занимает доминирующую позицию. (символьные обработки и т.д.)
Функционально-аппликативное программирование.
Свойства:
- программы значительно короче, более видна суть задачи, чем в императивных языках
- в программах отсутствуют побочные эффекты (результат строго зависит от вводимых данных)
- отсутствует понятие изменяемой переменной
- короткие, прозрачные программы
Некоторые считают, что функциональное программирование к декларативному программированию. Другие же относят его к императивному программированию.
(a+b)/(c-d)
x
=a+b
последовательность
y=c-d действий
z=x/y
В функциональном программировании последовательность не задается четко.
«Ленивое вычисление»
Функции высших порядков (функции, применяемые к функциям, результат - функция)
LISP
Состоит из S-выражений (атом и список).
Атом – с помощью алфавитно-цифрового обозначения (число тоже атом).
Список – некоторая крупная часть, заключенная в ( ) (внутри списка могут быть вложены списки). Пример: ((король ферзь)((ладья) (слон))пешка).
Есть набор предопределенных функций.
Некоторые атомы являются функциями.
ЛИСП – система поставляется с набором стандартных функций.
Квотирование (QUOTE L)
Задание выражений: (SETQ <атом> ‘<S-выр>)
Обработка списков:
(CAR ‘(A B C)) A (первый элемент списка)
(CAR ‘((A) B C)) (A)
F(x) – (F x)
F(x y) – (F x y)
NILL – пустой список
(CDR ‘(A B C)) (B C) (отбрасывает первый элемент)
(CDR ‘A) ( )
(CAR (CDR ‘(A B C))) B
(CADR ‘(A B C)) B
(CADDR )
(CADDAR S)
(CAR (CDR(CDR(CAR S))))
Соединение списков: (CONS ‘A ‘(BC)) (A B C)
(CONS ‘A NIL) (A)
(CONS (CAR S)(CDR S)) S
Предикаты – возвращенное значение либо NIL (ложь), либо T (истина):
(АТОМ ‘А) T
(ATOM ‘(A B)) NILL
(NULL ‘S) NILL
(EQUAL ‘(A B) ‘(A B)) – проверка на равенство
(NOT )
(AND )
(OR )
(COND (<t1> <d1>)
(<t2> <d2>)
……
(<tₓ> <dₓ>)
)
Сначала вычисляется t1, если оно не NILL, тогда значение COND=t1, если NLL, то переходим к следующей паре и т.д.
Страуструп – С++
Список – рекурсивные данные.
Рекурсивные программы в большинстве случаев пишутся на Лиспе.
Присваивание, вызов процедуры, оператор, циклическое выражение (итераторы).
DEFAULT – в качестве предеката в последней паре ставится Т.
Является ли аргумент числом (NUMBERP ‘A).
Является ли число нулём (ZEROP ‘N).
(+ 2 2) – результат 4
ЛИСП реализуется обычно как интерпретатор.
(В следующей строке немедленно получим ответ).
(- 5 3)
(* 3 3)
(/ 7 1)
(ADD1 6) 7
(SUB1 7) 6
(MAX 5 8 7 6) 8
(MIN 5 8 7 6) 5
(SQRT 81) 9
(ABS -3) 3
(LESSP 2 3) = (< 2 3)
(GREATERP 5 7) = (> 5 7)
Работа со списками:
Конструктор списков (2-й аргумент не может быть атомом):
(CONS ‘A ‘(B C)) (A B C)
(CONS ‘A NIL) (A)
(CONS (CAR S)(CDR S)) S
Объединение списков:
(APPEND ‘(A) NIL ‘((B)(C))) (A (B) (C)) – все аргументы должны быть списками.
(LIST ‘(A) NIL ‘((B)(C))) ((A) NIL ((B)(C))) – можно использовать атомы.
(LIST ‘A NIL) (A NIL)
(LENGTH ‘((A B) C (D))) 3 (длина списка)
(REVERSE ‘(A (B C) D)) (D (B C) A)
(MEMBER ) – входит ли первый элемент, являющийся атомом, во второй элемент, являющийся списком.
(SETQ M ‘(A B (C D) E))
(MEMBER ‘F M) NIL
(MEMBER ‘C M) NIL
(MEMBER ‘B M) (B (C D) E)
(SUBST ) – подстановка, 3 элемента.
(SUBST ‘A ‘B ‘(A B C)) (A A C)
(RPLACA ) – заменяет 1 элемент на указанное выражение.
(SETQ G ’(A B C)) (A B C)
(RPLACA (CDR G) ‘D) (D C)
(RPLACD ) - заменяет хвост первого аргумента на указанное выражение.