Математическое введение в декларативное программирование. Зюзысов В.М. - 52 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Большинство функциональных языков программирования используют λ–
исчисление в качестве промежуточного кода, в который можно транслировать исходную
программу. Функциональные языки «улучшают» нотацию λ–исчисления в прагматиче-
ском смысле, но при этом, в какой–то мере, теряется элегантность и простота последнего.
Изучение и понимание многих сложных ситуаций в программировании, например,
таких, как автоаппликативность (самоприменимость) или авторепликативность (самовос-
производство), сильно облегчается, если уже имеется опыт работы в λ–исчислении, где
выделены в чистом виде основные идеи и трудности.
Язык ламбда–исчисления является сейчас одним из важнейших выразительных
средств в логике, информатике, математической лингвистике, искусственном интеллекте
и когнитивной науке.
9.1.2 Синтаксис и семантика ламбда–исчисления
Ламбда–исчисление есть язык для определения функций. Выражения языка назы-
ваются λ–выражениями и каждое такое выражение обозначает функцию. Далее мы рас-
смотрим, как функции могут представлять различные структуры данных: числа, списки и
т. д. Для некоторых λ–выражений мы будем использовать имена (или сокращенные обо-
значения), они будут записываться полужирным шрифтом.
Определение λ–выражений (λ–термов)
Имеется три вида λ–выражений:
• Переменные: x, y и т. д.
• Функциональная аппликация: если M и N есть произвольные λ–термы, то можно по-
строить новый λ–терм (MN) (обозначающий применение, или аппликацию, оператора
M к аргументу N). Например, если (<m>, <n>) обозначает функцию, представляющую
пару чисел m и n и sum обозначает функцию сложения в λ–исчислении, то аппликация
(sum (<m>, <n>)) обозначает <m+n> (т. е. ламбда–терм, представляющий число m+n).
• Абстракция: По любой переменной x и любому λ–терму M можно построить новый λ–
терм (λx.M) (обозначающий функцию от x, определяемую λ–термом M). Такая конст-
рукция называется λ–абстракция. Например, λx. sum (x, <1>) обозначает функцию от
x, которая увеличивает аргумент на 1.
Тождественная функция представляется λ–термом (λx. x). Аппликация (λx. x) E да-
ет E.
Еще пример. Пусть λ–выражения <0>, <1>, <2>, … представляют числа 0, 1, 2, …,
соответственно; и add есть λ–выражение, обозначающее функцию, удовлетворяющее пра-
вилу:
((add <m>) <n>) = <m+n>.
Тогда (λx. ((add <1>) x)) есть λ–выражение, обозначающее функцию, что преобразует <n>
в <n+1>, и (λx. (λy. ((add x) y))) есть λ–выражение, обозначающее функцию, которая пре-
образует <m> в функцию (λy. ((add <m>) y)).
Символ x после λ называется связанной переменной абстракции и соответствует
понятию формального параметра в традиционной процедуре или функции. Выражение
справа от точки называется телом абстракции, и, подобно коду традиционной процедуры
или функции, оно описывает, что нужно сделать с параметром, поступившим на вход
функции. Мы читаем символ λ как «функция от» и точку (.) как «которая возвращает».
Чтобы уменьшить число применяемых скобок будем использовать следующие со-
глашения.
• Операция аппликации лево–ассоциативна, т. е. E
1
E
2
… E
n
означает
52

Страницы