1.2 Лямбда-исчисление и функциональное программирование

Определение функций и их вычислений в Лиспе основано на лямбда-исчислении (lambda calculus) Черча. Лямбда-выражение - это определение вычислений и параметров функции в чистом виде, то есть без фактических параметров или аргументов, которое имеет вид

(LAMBDA (x1 x2…xn) fn)

Символ LAMBDA обозначает, что мы имеем дело с определением функции. Символы xi язвляются формальными параметрами (formal parameter) определения, которые именуют аргументы в описывающем вычисления теле (body) функции fn. Входящий в состав формы список, образованный из параметров, называется лямбда-списком (lambda list).

Телом функции является произвольная форма, значение которой может вычислить интерпретатор Лиспа, например: константа, связанный со значением символ или композиция из вызовов функций.

В математике и обычных языках программирования вызов функции записывается, как правило, в так называемой префиксной записи (нотации), в которой имя функции стоит перед скобками, окружающими аргументы:

f(x), g(x,y), h(x, g(y,z))

Определение функции в языке Лисп позволяет задать произвольное вычислимое отображение. Например, функцию, вычисляющую сумму квадратов, можно определить с помощью сложения и умножения:

(defun сумма_квадратов (x y)

(+ (* x x) (* y y)))

имя –сумма_квадратов; аргументы - x, y; значение – x*x+y*y.

Используя лямбда-выражение, данную функцию можно записать

(lambda (x y) (+ (* x x) (* y y)))

Здесь x и y – формальные параметры, представляющие произвольные числа. Формальность параметров означает, что их можно заменить на любые другие символы, и это не отразится на вычислениях, определяемых функцией. Именно это и скрывается за лямбда-нотацией.

Вызов функции обозначает запуск, или применение определения функции к конкретным значениям аргументов. Например, применим функцию суммаквадратов к фактическим аргументам x =2 и y =3:

(cумма_квадратов 3 4)  25.

Используемое в Лиспе функциональное программирование основывается на том, что в результате каждого действия возникает значение. Значения становятся аргументами следующих действий и конечный результат всей задачи выдается пользователю. Программы строятся из логически расчлененных определений функций. Кроме функционального программирования в Лиспе можно использовать программирование, основанное на обычном последовательном исполнении операторов с присваиваниями, передачами управления и специальными операторами цикла.

В Лиспе существуют специальные функции, которые проверяют наличие у символьного выражения некоторого свойства, которые называются предикатом. Другими словами, предикат - это функция, которая определяет, обладает ли аргумент определенным свойством и возвращает в качестве значения "ложь" (или NIL) в случае, если аргумент не обладает этим свойством, и "истина" (или T) в противном случае.

1.3 Пример простейшей программы на языке Лисп

Определим функцию, которая вычисляет факториал целого числа n. Для этого необходимо перемножить все числа от 1 до n. Из математики известно, что n!=n(n-1)!, то есть факториал n равен произведению n и факториала от (n-1) Запишем определение функции, считая что 0!=1

(defun fact (n)

(cond (zerop n) 1)

(t (* n (fact (- n 1)))))

В данном примере функция fact рекурсивно вызывает сама себя с аргументом, который на 1 меньше значения предыдущего вызова. Рекурсивный вызов продолжается до тех пор, пока значение аргумента не станет равно 0.

(fact 3) (3*fact(2)) 3*2=6

(2*fact(1)) 2*1=2

(1*fact(0)) 1*1=1