- •Содержание
- •1. Введение в функции
- •1.1. Чистые функции
- •1.2. Функциональность
- •2. Введение в функциональное программирование
- •2.1. О языке Лисп
- •2.2. Примеры программ
- •2.3. Символьная обработка
- •2.4. Особенности Лиспа
- •3. Основы языка лисп
- •3.1. Символы и списки
- •3. 2. Понятие функции
- •3.3. Базовые функции
- •3.4. Имя и значение символа
- •4. Определение функций
- •5. Математические основы: -исчисление
- •5. 1. Введение в синтаксис
- •Определение -термов
- •5.2. Вычисление -выражений
- •5.3. Порядок редукций и нормальные формы
- •5.4. Рекурсивные выражения
- •5.5. Чистое -исчисление
- •5.6. Ламбда-абстракции в Лиспе
- •6. Внутреннее представление списков
- •7. Рекурсия
- •7.1. Простая рекурсия
- •7.2. Другие формы рекурсии
- •8. Функции более высокого порядка
- •8.1. Функционалы
- •8.2. Способы композиции функций
- •8.3. Замыкания
- •8.4. Абстрактный подход
3.3. Базовые функции
First, rest, cons. Базовые функции для построения, разбора и анализа списков.
Если список не пуст, то он имеет вид (голова списка - первый элемент, хвост списка).
(first <head tail>) --> <head>
(first список) —> символьное выражение (s- выражение)
(first nil) ---> nil
(first атом) ---> ошибка
(rest <head tail>) --> <tail>
(rest список) ---> список
(rest nil) --> nil
(rest атом) --> ошибка
Традиционно ( в связи с первоначальной реализацией Лиспа) для функций first и rest используются также обозначения car и cdr. (first ‘(1 2 3)) ==> 1 (rest ‘(1 2 3)) ==> (2 3)
Функция CONS (construct) строит новый список из переданных в качестве аргументов головы и хвоста:
(cons ‘a ‘(b c)) ==> (a b c) (cons ‘(a b) ‘(c d)) ==> ((a b) c d) (cons (+ 1 2) ‘(+ 4 6)) => (3 + 4 6) (cons nil nil) ==> (nil) (cons ‘(a b c) nil) ==> ((a b c)) (cons nil ‘(a b c)) ==> (nil a b c)
Связь между функциями first, rest , cons: (cons (first ‘(a b c)) (rest ‘(a b c))) ==> (a b c)
Комбинируя селекторы car=first и cdr=rest, можно выделить произвольный элемент списка. Например,
(cdr (cdr (car ‘((a b c) (d e) (f))))) ==> (c) Вложенные вызовы CAR и CDR можно записывать в сокращенном виде в виде одного вызова функции:
(C...R список). (cadr x) <==> (car (cdr x)) (cddar x) <==> (cdr (cdr (car x))) (не больше 4-х символов вместо точек)
Предикаты – функции, которые проверяют выполнение некоторого условия и возвращают в качестве результата логическое значение T (в более общем виде, произвольное выражение, отличное от NIL) или NIL.
(ATOM s-выражение) - проверяет, является ли выражение атомом. (atom ‘(a b c)) ==> nil (atom 7) ==> t (atom nil) ==> t (atom (atom (+ 3 4))) ==> t
(NULL s-выражение) - проверяет, является ли аргумент пустым списком. (null ‘(3 4 5)) ==> nil (null ()) ==> t (null ‘a) ==> nil
(EQ <символ1> <символ2>) - проверяет тождественность двух символов: (eq t (atom ‘atom)) ==> t (eq nil t) ==> nil
(= <число1> <число2>) - проверяет равенство двух чисел.
EQL - сравнивает символы и числа одинаковых типов. Предикат используется во многих встроенных функциях, осуществляющих более сложные операции сравнения. Его использование для сравнения списков - типичная ошибка.
EQUAL работает как eql, но, кроме того, проверяет одинаковость двух списков.
Функции second, third, fourt, fifth, sixth, seven, eighth, ninth, tenth выдают второй, третий,…, десятый элемент списка.
(nth n список) - выдает n-ый элемент списка.
(Last список) - список, состоящий из последнего элемента списка-аргумента
(last ‘(a b c)) ==> (c)
(list x1 x2 x3 ...) - возвращает в качестве своего значения список из значений аргументов:
(list 1 2) ==> (1 2)
(list ‘a ‘(b c) ‘ d) ==> (a (b c) d)
(list (list ‘a ) ‘b nil) ==> ( (a) b nil)
(list nil) ==> (nil)
3.4. Имя и значение символа
Символы можно использовать как переменные. В этом случае они могут обозначать некоторые выражения. У символов изначально нет какого-нибудь значения, как у констант.
При помощи функции SET символу можно присвоить (set) или связать (binding) с ним некоторое значение. SET вычисляет оба аргумента.
> a ==> ошибка (unbound variable)
(set ‘a ‘(1 2 3))
> a ==> (1 2 3)
Функция SETQ отличается от SET тем, что она вычисляет только свой второй аргумент. Об автоматическом блокировании вычисления первого аргумента напоминает буква Q.
(setq b a)
>b ==> (1 2 3)
Эти функции имеют побочный эффект. Эффект функции состоит в образовании связи между символом и его значением, а значением функции является связываемое значение.
В Лиспе все действия возвращает некоторое значение. Значение имеется даже у таких действий, основное предназначение которых заключается в осуществлении побочного эффекта, таких, например, как связывание символа или вывод результатов на печать. Функции, обладающие побочным эффектом, в Лиспе называются псевдофункциями. В практическом программировании псевдофункции полезны, хотя в теории, чистом функциональном программировании не нужны.
(list (+ (setq a 3) 4) a) ===> (7 3)
Интерпретатор Лиспа называется EVAL, и его можно так же, как и другие функции вызывать из программы. Лишний вызов интерпретатора может, например, снять эффект блокировки вычисления или позволяет найти значение значения выражения.
‘(+ 2 3) ==> (+ 2 3)
(eval ‘(+ 2 3)) ==> 5
(setq x ‘(a b c))
‘x ==> x
(eval ‘x) ==> (a b c)
(setq y ‘x)
> y ===> x
(eval y) ===> (a b c)
Основной цикл: READ-EVAL-PRINT
(print ‘>)
(setq a (read))
(setq b (eval a))
(print b)
(print ‘>)