 |
Определения форм FLET, LABELS
|
|
|
|
(flet (<binding>...) <expr>)
(labels (<binding>...) <expr>)
где
<binding> - функциональные связи, каждая из которых имеет вид
(<sym> <farg> <body>)
<sym> - имя локальной функции
<farg> - список формальных параметров
<body> - тело локальной функции
<expr> - вычисляемое выражение формы, содержащее вызовы локальных функций.
Labels используется в рекурсивном случае.
Накапливающие параметры
Стандартное определение факториала (n! = 1*2*3*…*n):
(defun! (n)
(if (= n 0) 1.0
(* n (! (1- n))))
)
При больших n стек будет переполнен.
В следующем определении используется метод накапливающего параметра. Определена локальная функция fac, у которой второй аргумент служит для накопления результата.
(defun! (n)
(labels ((fac (x y)
(if (zerop x) y (fac (1- x) (* x y))))
)
(fac n 1.0))
)
Нахождение наибольшего общего делителя двух чисел
(defun gcd (n m)
(let ((r (rem n m)))
(if (zerop r) m (gcd m r))))
Вычисление суммы и произведения элементов списка
; 1 вариант
; программирование "в лоб"
(defun sumpr (x)
(if (null x) (list 0 1)
(list (+ (first x) (first (sumpr (rest x))))
(* (first x) (second (sumpr (rest x))))))
)
; 2 вариант
; использование let
(defun sumpr (x)
(if (null x) (list 0 1)
(let ((z (sumpr (rest x))))
(list (+ (first x) (first z))
(* (first x) (second z)))))
)
; 3 вариант
; еще одно использование let
(defun sumpr (x)
(if (null x) (list 0 1)
(let ((n (first x)) (z (sumpr (rest x))))
(list (+ n (first z))
(* n (second z)))))
)
; 4 вариант
; еще одно использование let
(defun sumpr (x)
(if (null x) (list 0 1)
(let ((n (first x)) (z (sumpr (rest x))))
(let ((a (first z)) (b (second z)))
(list (+ n a) (* n b)))))
)
; 5 вариант
; использование накапливающих параметров
(defun sumpr (x) (sp x 0 1))
(defun sp (x s p)
(if (null x) (list s p)
(sp (rest x) (+ (first x) s) (* (first x) p)))
)
; 6 вариант
; использование локальной функции
(defun sumpr (x)
(labels ((sp (y s p)
|
|
|
(if (null y) (list s p)
(sp (rest y) (+ s (first y)) (* p (first y))))))
(sp x 0 1))
)
МАТЕМАТИЧЕСКИЕ ОСНОВЫ: l-ИСЧИСЛЕНИЕ
l-исчисление было использовано как средство для описания (чисто синтаксического) свойств математических функций и эффективной обработки их в качестве правил. Функциональные программы построены из “чистых” функций, т. е. функций в математическом смысле, и поэтому нотация l-исчисления особенно удобна для формального описания манипулирования функциями и даже в качестве промежуточного кода, в который можно транслировать исходную программу. В действительности функциональные языки программирования часто представляют собой “улучшенные” версии нотации l-исчисления в том смысле, что все функциональные программы можно преобразовать в эквивалентные l-выражения. Хотя нотация l-исчисления проста, она является достаточно мощной, чтобы описать все черты исходного функционального языка.
Введение в синтаксис
l-исчисление можно рассматривать как язык программирования, хотя оно было создано (Чёрч) в 20-х годах нашего века в период философских исследований в области оснований математики. Главная особенность заключается в том, что оно является языком высшего порядка, т. е. в нём имеются средства описания функций, входные и выходные значения которых также могут быть функциями. Кроме того, оно основано не на концепции множества, как многие другие математические языки, а на понятии функции.
Работая в направлении автоматизации значительной части математического и логического интеллекта, программисты-теоретики сталкиваются с теми же проблемами над которыми логики ломают голову уже 80 лет (например, что такое математическое мышление и как его формализовать?). Поэтому их исследования могут служить полезным источником для программистов.
Два подхода к функциям
1. Дирихле: функция задается графиком - множеством пар < аргумент, значение>.
|
|
|
2. Функция – правило, вычислительное предписание.
С первой точки зрения x^2-4 и (x+2)*(x-2) - разные обозначения одной и той же функции; со второй точки зрения – это разные функции.
Обычная запись f(x) может обозначать как обозначение функции, так и вызов функции с аргументом x. Для более строгого подхода это необходимо различать. Для этого вводятся ламбда-обозначения.
Например, x^2+3 - некоторая функция, зависящая от x. Ламбда-обозначение для этой функции lx. x^2+3. Этой записи соответствует правило:
для любого a (lx. x^2 +3) (a) = a^2+3
Выражение x + 2y можно считать как функцию от x (записывается lx. x +2y) и как функцию от y (записывается ly. x +2y).
(lx. x +2y) a ® a+2y
(ly. x +2y) a ® x+2a
Запись ly.lx.E понимается как ly.(lx. E). Поэтому
((ly.lx. x+2y) a) b ® (lx. x+2a) b ® b+2a
((lx.ly. x+2y) a) b ® (ly. a+2y) b ® a+2b
Мы читаем символ l как “функция от” и точку (.) как “которая возвращает”.
Определение l-термов
· Каждая переменная есть l-терм.
· Каждая константа есть l-терм.
· По любым l-термам M и N можно построить новый l-терм (M N) (обозначающий применение, или аппликацию, оператора M к аргументу N).
· По любой переменной x и любому l-терму M можно построить новый l-терм (lx.M) (обозначающий функцию от x, определяемую l-термом M). Такая конструкция называется l-абстракция.
Попросту говоря, l-исчисление - это исчисление анонимных (безымянных) функций.
Символ x после l называется связанной переменной абстракции и соответствует понятию формального параметра в традиционной процедуре или функции. Выражение справа от точки называется телом абстракции, и, подобно коду традиционной процедуры или функции, оно описывает, что нужно сделать с параметром, поступившим на вход функции.
Тело абстракции может быть любым допустимым l-выражением, и поэтому оно также может содержать другую абстракцию, например:
lx. ly. (x+y)*2
Это выражение читается как “функция от x, которая возвращает функцию от y, которая возвращает (x+y)*2.
Используется соглашение:
запись (...(((lx1. lx2.... lxn. E) a1) a2)...an)
кратко пишется как (lx1. lx2.... lxn. E) a1 a2...an
Для полноты опишем ламбда-нотацию более формально в виде БНФ:
<выражение>::= l<идентификатор>. <выражение> |
<идентификатор> |
<выражение> <выражение> |
(<выражение>) |
<константа>
|
|
|
Набор констант произволен: целые числа, булевы константы, арифметические операции, булевы функции и т. п.
Вычисление l-выражений
Мы рассмотрели, как l-нотация может быть использована для представления функциональных выражений и сейчас готовы к тому, чтобы определить правила вывода l-исчисления, которые описывают, как вычислять выражение, т. е. как получать конечное значение выражения из его первоначального вида.
Константы являются самоопределенными, т. е. их невозможно преобразовать в более простые выражения.
Применение константной функции записывается в виде встроенных соответствующих d-правил, например
+ 1 3 ®d 4
Процесс упрощения выражений называется редукцией. Пример редукции (®d – обозначение δ-редукции):
* (+ 1 2) (- 4 1)
®d * (+ 1 2) 3
®d * 3 3
®d 9
Правило редукции как применять l-абстракцию: копируется тело абстракции с заменой всех вхождений связанной переменной на выражения аргумента - называется b-редукцией (обозначается ®b или просто ®).
(lx. * x x) 2 ®b * 2 2
((lx. ly. + x y) 7) 8
® (ly. + 7 y) 8
® + 7 8
® 15
Редуцируемое выражение называется редексом, и мы можем на данном этапе заключить, что процесс редукции ламбда-выражения состоит из множества редукций, применяемых к редексам данного выражения до тех пор, пока выражение включает в себя хотя бы один редекс. В зависимости от того, какое правило можно применить к редексу, используются понятия b-редекса и d-редекса.
При выполнении b-редукции следует быть внимательными и не выполнять подстановку в тело абстракции, если связанная переменная этой абстракции имеет такое же имя, как и заменяемая переменная:
lx. (lx. x) (+ 1 x)
(lx. (lx. x) (+ 1 x)) 1
® (lx. 1) (+ 1 1)
® (lx. 1) 2
® 1 Ошибка!
В этом случае нужно оставить такую (внутреннюю) абстракцию без изменений. Возможно также переименовать переменную - алфавитно-эквива-лентное преобразование.
Правильно:
(lx. (lx. x) (+ 1 x)) 1
® (lx. x) (+ 1 1)
® (lx. x) 2
® 2
Примеры редукции выражений (используемые редексы подчеркнуты):
1)
(lf. lx. f 4 x) (ly. lx. + x y) 3
® (lx. (ly.lx. + x y) 4 x) 3 - выбрали один из двух возможных редексов
|
|
|
® (ly. lx. + x y) 4 3
® (lx. + x 4) 3
® + 3 4
® 7
2)
(lf. lx. f 4 x) (ly. lx. + x y) 3
® (lx. (ly.lx. + x y) 4 x) 3 - выбрали один из двух возможных редексов
® (lx. (lx. + x 4) x) 3 - снова делаем произвольный выбор
® (lx. + x 4) 3
® + 3 4
® 7
|
|
|
