Приведем примеры определения наиболее часто используемых в прак-
тике программирования функций. Отметим, что для простоты ото-
браны функции, действующие на списки как на свои аргументы. Как
обычно, под списком понимается конечная последовательность.
Начиная работать со списками, можно оценить возможности си-
стемы программирования LISP1. Таким образом, в этой системенет
1
По своей основе LISP имеет, практически, все возможности бестипового
ламбда-исчисления. В зависимости от применяемого диалекта внешняя форма за-
писи объектов может варьироваться. Подчеркнем еще раз, что в этом языке нет
операторов. Единственный вид используемых в нем объектов -- это функции. Ре-
ализованные механизмы рекурсии с математической точки зрения иллюстрируют
эффект вычислений с неподвижной точкой. Обычно в языке дополнительно пред-
лагаются нерекурсивные средства организации циклических вычислений.
различия между “программами” и “данными”: и то, и другое -- впол-
не равноправные объекты. Большой интерес, проявляемый к системе
программирования LISP, вполне оправдан. Имея четкие и краткие
математические основания, эта система программирования преодо-
левает барьер между практическим программированием задачи и ее
математическим осмыслением.
Задача 9.1 Пользуясь функцией поиска неподвижной точки Y , вы-
разить определения приводимых ниже функций:
2) sum = λx.if null x
then 0
else (car x) +sum(cdr x),
3) product = λx.if null x
then 1
else (car x) × product(cdr x),
4) append = λx.λy.if null x
then y
else (list((car x)(append(cdr x)y)),
5) concat = λx.if null x
then ()
else append(car x)(concat(cdr x)),
6) map = λfλx.if null x
then ()
else list((f(car x))(map f(cdr x))).
length(a1, a2, a3) = 3;
sum(1,2,3,4) = 10;
product(1,2,3,4) = 24;
append(1,2)(3,4,5) = (1,2,3,4,5);
concat((1,2),(3,4),()) = (1,2,3,4);
map square (1,2,3,4) = (1,4,9,16).
Для примеров “обращения” к каждой из функций выполнить проверку.
Решение. В качестве примера приведем соответствующие выкладки
для функцийlength(вычисление длины списка) иmap(функционал,
“распределяющий” вдоль списка действие функции-аргумента). При
вычислении этих функций проявляются основные особенности ре-
курсивных вычислений над списками.
length--1. Для функции length исходное определение
length = λx.if null x
then 0
else 1 +length(cdr x),
перепишем в виде:
length = (λf.λx.if null x
then 0
else 1 +f(cdr x))length.
length--2. Отсюда следует, что
length = Y (λf.λx.if null x
then 0
else 1 +f(cdr x)).
Тем самым желаемая комбинаторная характеристика полу-
чена.
length--3. Произведем проверку определения для списка длины 2,
то есть возьмем x = (a1, a2):
length(a1, a2) = Y (λfλx.if null x
then 0
else 1 +f(cdr x))(a1, a2)
= (λfλx.if null x
then 0
else 1 +f(cdr x))(Y (. . .))(a1, a2)
= if null(a1, a2)then 0 else 1 + (Y (. . .))(cdr (a1, a2))
= 1 + (λfλx.if null x then 0 else 1 +f(cdr x))(Y (. . .))(a2)
= 1 +if null(a2)then 0 else 1 + (Y (. . .))nil
= 1 + 1(λfλx.if null x then 0 else 1 +f(cdr x))(Y (. . .))nil
= 1 + 1 + 0 = 2.
map--1. Для функции map исходное определение
map = λf.λx. if null x
then ()
else ((f(car x)) : (mapf(cdr x))
перепишем в виде:
map = (λm.λf.λx. if null x
then ()
else (f(car x)) : (mf(cdr x))) map.
Отсюда следует, что
map = Y (λm.λf.λx. if null x
then ()
else (f(car x)) : (mf(cdr x))).
Проверка для f = square, x = (2,3):
map square (2,3) =
= (λmλfλx.if null x
then ()
else (f(car x)) : (mf(cdr x)))(Y (. . .))square (2,3)
= (square 2) : ((Y (. . .))square (3))
= (square 2) : ((λm.λf.λx. . . .)(Y (. . .))square (3))
= (square 2) : ((square 3) : ((Y (. . .))square ())
= (square 2) : ((square 3) : ())
= (4,9).
В данном случае символ “:” принят для обозначения инфикс-
ной формы функции list, поэтому принимаем в качестве со-
глашения об обозначениях, что x : (y : (z : ())) = x, y, z =
(x, y, z).
|
Главная
Каталог файлов
