Лямбда-исчисление

Поделись знанием:
Перейти к: навигация, поиск

Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия вычислимости.

λ-исчисление может рассматриваться как семейство прототипных языков программирования. Их основная особенность состоит в том, что они являются языками высших порядков. Тем самым обеспечивается систематический подход к исследованию операторов, аргументами которых могут быть другие операторы, а значением также может быть оператор. Языки в этом семействе являются функциональными, поскольку они основаны на представлении о функции или операторе, включая функциональную аппликацию и функциональную абстракцию. λ-исчисление реализовано Джоном Маккарти в языке Лисп. Вначале реализация идеи λ-исчисления была весьма громоздкой. Но по мере развития Лисп-технологии (прошедшей этап аппаратной реализации в виде Лисп-машины) идеи получили ясную и четкую реализацию.





Чистое λ-исчисление

Это простейший из семейства прототипных языков программирования, чистое λ-исчисление, термы которого, называемые также объектами («обами»), или λ-термами, построены исключительно из переменных применением аппликации и абстракции. Изначально наличие каких-либо констант не предполагается.

Аппликация и абстракция

В основу λ-исчисления положены две фундаментальные операции:

  • Аппликация (лат. applicatio — прикладывание, присоединение) означает применение или вызов функции по отношению к заданному значению. Её обычно обозначают <math>f\ a</math>, где <math>f</math> — функция, а <math>a</math> — аргумент. Это соответствует общепринятой в математике записи <math>f(a)</math>, которая тоже иногда используется, однако для λ-исчисления важно то, что <math>f</math> трактуется как алгоритм, вычисляющий результат по заданному входному значению. В этом смысле аппликация <math>f</math> к <math>a</math> может рассматриваться двояко: как результат применения <math>f</math> к <math>a</math>, или же как процесс вычисления <math>f\ a</math>. Последняя интерпретация аппликации связана с понятием β-редукции.
  • Абстракция или λ-абстракция (лат. abstractio — отвлечение, отделение) в свою очередь строит функции по заданным выражениям. Именно, если <math>t\equiv t[x]</math> — выражение, свободно содержащее <math>x</math>, тогда запись <math>\ \lambda x.t[x]</math> означает: <math>\lambda</math> функция от аргумента <math>x</math>, которая имеет вид <math>t[x]</math>, обозначает функцию <math>x\mapsto t[x]</math>. Таким образом, с помощью абстракции можно конструировать новые функции. Требование, чтобы <math>x</math> свободно входило в <math>t</math>, не очень существенно — достаточно предположить, что <math>\lambda x.t\equiv t</math>, если это не так.

α-эквивалентность

Основная форма эквивалентности, определяемая в лямбда-термах, это альфа-эквивалентность. Например, <math>\lambda x.x</math> и <math>\lambda y.y</math> альфа-эквивалентные лямбда-термы и оба представляют одну и ту же функцию (функцию тождества). Термы <math>x</math> и <math>y</math> не альфа-эквивалентны, так как они не находятся в лямбда абстракции.

β-редукция

Поскольку выражение <math>\lambda x. 2\cdot x + 1</math> обозначает функцию, ставящую в соответствие каждому <math>x</math> значение <math>2\cdot x + 1</math>, то для вычисления выражения
<math>(\lambda x. 2\cdot x + 1)\ 3</math>,
в которое входят и аппликация и абстракция, необходимо выполнить подстановку числа 3 в терм <math>2\cdot x + 1</math> вместо переменной <math>x</math>. В результате получается <math>2\cdot 3+1=7</math>. Это соображение в общем виде записывается как
<math>(\lambda x.t)\ a = t[x:=a],</math>
и носит название β-редукция. Выражение вида <math>(\lambda x.t)\ a</math>, то есть применение абстракции к некому терму, называется редексом (redex). Несмотря на то, что β-редукция по сути является единственной «существенной» аксиомой λ-исчисления, она приводит к весьма содержательной и сложной теории. Вместе с ней λ-исчисление обладает свойством полноты по Тьюрингу и, следовательно, представляет собой простейший язык программирования.

η-преобразование

η-преобразование выражает ту идею, что две функции являются идентичными тогда и только тогда, когда, будучи применёнными к любому аргументу, дают одинаковые результаты. η-преобразование переводит друг в друга формулы <math>\lambda x.f\ x</math> и <math>f</math> (только если <math>x</math> не имеет свободных вхождений в <math>f</math>: иначе, свободная переменная <math>x</math> после преобразования станет связанной внешней абстракцией или наоборот).

Каррирование (карринг)

Функция двух переменных <math>x</math> и <math>y</math> <math>f(x,y) = x + y</math> может быть рассмотрена как функция одной переменной <math>x</math>, возвращающая функцию одной переменной <math>y</math>, то есть как выражение <math>\ \lambda x.\lambda y.x+y</math>. Такой приём работает точно так же для функций любой арности. Это показывает, что функции многих переменных могут быть выражены в λ-исчислении и являются «синтаксическим сахаром». Описанный процесс превращения функций многих переменных в функцию одной переменной называется карринг (также: каррирование), в честь американского математика Хаскелла Карри, хотя первым его предложил М. Э. Шейнфинкель (1924).

Семантика бестипового λ-исчисления

Тот факт, что термы λ-исчисления действуют как функции, применяемые к термам λ-исчисления (то есть, возможно, к самим себе), приводит к сложностям построения адекватной семантики λ-исчисления. Чтобы придать λ-исчислению какой-либо смысл, необходимо получить множество D, в которое вкладывалось бы его пространство функций D → D. В общем случае такого D не существует по соображениям ограничений на мощности этих двух множеств, D и функций из D в D: второе имеет бо́льшую мощность, чем первое.

Эту трудность в начале 1970-х годов преодолел Дана Скотт, построив понятие области D (изначально на полных решётках[1], в дальнейшем обобщив до полного частично упорядоченного множества со специальной топологией) и урезав D → D до непрерывных в этой топологии функций[2]. На основе этих построений была создана денотационная семантика[en] языков программирования, в частности, благодаря тому, что с помощью них можно придать точный смысл таким двум важным конструкциям языков программирования, как рекурсия и типы данных.

Связь с рекурсивными функциями

Рекурсия — это определение функции через себя; на первый взгляд, лямбда-исчисление не позволяет этого, но это впечатление обманчиво. Например, рассмотрим рекурсивную функцию, вычисляющую факториал:

f(n) = 1, if n = 0; else n × f(n - 1).

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

g := λr. λn.(1, if n = 0; else n × (r r (n-1)))
f := g g

Это решает специфичную проблему вычисления факториала, но решение в общем виде также возможно. Получив лямбда-терм, представляющий тело рекурсивной функции или цикл, передав себя в качестве первого аргумента, комбинатор неподвижной точки возвратит необходимую рекурсивную функцию или цикл. Функции не нуждаются в явной передаче себя каждый раз. Существует несколько определений комбинаторов неподвижной точки. Самый простой из них:

Y = λg.(λx.g (x x)) (λx.g (x x))

В лямбда-исчислении, Y g — неподвижная точка g; продемонстрируем это:

Y g
(λh.(λx.h (x x)) (λx.h (x x))) g
(λx.g (x x)) (λx.g (x x))
g ((λx.g (x x)) (λx.g (x x)))
g (Y g).

Теперь, чтобы определить факториал, как рекурсивную функцию, мы можем просто написать g (Y g) n, где n — число, для которого вычисляется факториал. Пусть n = 4, получаем:

g (Y g) 4
   (λfn.(1, if n = 0; and n·(f(n-1)), if n>0)) (Y g) 4
   (λn.(1, if n = 0; and n·((Y g) (n-1)), if n>0)) 4
   1, if 4 = 0; and 4·(g(Y g) (4-1)), if 4>0
   4·(g(Y g) 3)
   4·(λn.(1, if n = 0; and n·((Y g) (n-1)), if n>0) 3)
   4·(1, if 3 = 0; and 3·(g(Y g) (3-1)), if 3>0)
   4·(3·(g(Y g) 2))
   4·(3·(λn.(1, if n = 0; and n·((Y g) (n-1)), if n>0) 2))
   4·(3·(1, if 2 = 0; and 2·(g(Y g) (2-1)), if 2>0))
   4·(3·(2·(g(Y g) 1)))
   4·(3·(2·(λn.(1, if n = 0; and n·((Y g) (n-1)), if n>0) 1)))
   4·(3·(2·(1, if 1 = 0; and 1·((Y g) (1-1)), if 1>0)))
   4·(3·(2·(1·((Y g) 0))))
   4·(3·(2·(1·((λn.(1, if n = 0; and n·((Y g) (n-1)), if n>0) 0))))
   4·(3·(2·(1·(1, if 0 = 0; and 0·((Y g) (0-1)), if 0>0))))
   4·(3·(2·(1·(1))))
   24

Каждое определение рекурсивной функции может быть представлено как неподвижная точка соответствующей функции, следовательно, используя Y, каждое рекурсивное определение может быть выражено как лямбда-выражение. В частности, мы можем определить вычитание, умножение, сравнение натуральных чисел рекурсивно.

В языках программирования

В языках программирования под «λ-исчислением» зачастую понимается механизм «анонимных функций» — callback-функций, которые можно определить прямо в том месте, где они используются, и которые имеют доступ к локальным переменным текущей функции.

См. также

Напишите отзыв о статье "Лямбда-исчисление"

Примечания

  1. Scott D.S. The lattice of flow diagrams.-- Lecture Notes in Mathematics, 188, Symposium on Semantics of Algorithmic Languages.-- Berlin, Heidelberg, New York: Springer-Verlag, 1971, pp. 311—372.
  2. Scott D.S. Lattice-theoretic models for various type-free calculi. — In: Proc. 4th Int. Congress for Logic, Methodology, and the Philosophy of Science, Bucharest, 1972.

Литература

  • Барендрегт X. Ламбда-исчисление. Его синтаксис и семантика: Пер. с англ. — М.: Мир, 1985. — 606 с.

Отрывок, характеризующий Лямбда-исчисление

– Приехали. Жюли Друбецкая говорила мне. Я поехал к ним и не застал. Они уехали в подмосковную.


Офицеры хотели откланяться, но князь Андрей, как будто не желая оставаться с глазу на глаз с своим другом, предложил им посидеть и напиться чаю. Подали скамейки и чай. Офицеры не без удивления смотрели на толстую, громадную фигуру Пьера и слушали его рассказы о Москве и о расположении наших войск, которые ему удалось объездить. Князь Андрей молчал, и лицо его так было неприятно, что Пьер обращался более к добродушному батальонному командиру Тимохину, чем к Болконскому.
– Так ты понял все расположение войск? – перебил его князь Андрей.
– Да, то есть как? – сказал Пьер. – Как невоенный человек, я не могу сказать, чтобы вполне, но все таки понял общее расположение.
– Eh bien, vous etes plus avance que qui cela soit, [Ну, так ты больше знаешь, чем кто бы то ни было.] – сказал князь Андрей.
– A! – сказал Пьер с недоуменьем, через очки глядя на князя Андрея. – Ну, как вы скажете насчет назначения Кутузова? – сказал он.
– Я очень рад был этому назначению, вот все, что я знаю, – сказал князь Андрей.
– Ну, а скажите, какое ваше мнение насчет Барклая де Толли? В Москве бог знает что говорили про него. Как вы судите о нем?
– Спроси вот у них, – сказал князь Андрей, указывая на офицеров.
Пьер с снисходительно вопросительной улыбкой, с которой невольно все обращались к Тимохину, посмотрел на него.
– Свет увидали, ваше сиятельство, как светлейший поступил, – робко и беспрестанно оглядываясь на своего полкового командира, сказал Тимохин.
– Отчего же так? – спросил Пьер.
– Да вот хоть бы насчет дров или кормов, доложу вам. Ведь мы от Свенцян отступали, не смей хворостины тронуть, или сенца там, или что. Ведь мы уходим, ему достается, не так ли, ваше сиятельство? – обратился он к своему князю, – а ты не смей. В нашем полку под суд двух офицеров отдали за этакие дела. Ну, как светлейший поступил, так насчет этого просто стало. Свет увидали…
– Так отчего же он запрещал?
Тимохин сконфуженно оглядывался, не понимая, как и что отвечать на такой вопрос. Пьер с тем же вопросом обратился к князю Андрею.
– А чтобы не разорять край, который мы оставляли неприятелю, – злобно насмешливо сказал князь Андрей. – Это очень основательно; нельзя позволять грабить край и приучаться войскам к мародерству. Ну и в Смоленске он тоже правильно рассудил, что французы могут обойти нас и что у них больше сил. Но он не мог понять того, – вдруг как бы вырвавшимся тонким голосом закричал князь Андрей, – но он не мог понять, что мы в первый раз дрались там за русскую землю, что в войсках был такой дух, какого никогда я не видал, что мы два дня сряду отбивали французов и что этот успех удесятерял наши силы. Он велел отступать, и все усилия и потери пропали даром. Он не думал об измене, он старался все сделать как можно лучше, он все обдумал; но от этого то он и не годится. Он не годится теперь именно потому, что он все обдумывает очень основательно и аккуратно, как и следует всякому немцу. Как бы тебе сказать… Ну, у отца твоего немец лакей, и он прекрасный лакей и удовлетворит всем его нуждам лучше тебя, и пускай он служит; но ежели отец при смерти болен, ты прогонишь лакея и своими непривычными, неловкими руками станешь ходить за отцом и лучше успокоишь его, чем искусный, но чужой человек. Так и сделали с Барклаем. Пока Россия была здорова, ей мог служить чужой, и был прекрасный министр, но как только она в опасности; нужен свой, родной человек. А у вас в клубе выдумали, что он изменник! Тем, что его оклеветали изменником, сделают только то, что потом, устыдившись своего ложного нарекания, из изменников сделают вдруг героем или гением, что еще будет несправедливее. Он честный и очень аккуратный немец…
– Однако, говорят, он искусный полководец, – сказал Пьер.
– Я не понимаю, что такое значит искусный полководец, – с насмешкой сказал князь Андрей.
– Искусный полководец, – сказал Пьер, – ну, тот, который предвидел все случайности… ну, угадал мысли противника.
– Да это невозможно, – сказал князь Андрей, как будто про давно решенное дело.
Пьер с удивлением посмотрел на него.
– Однако, – сказал он, – ведь говорят же, что война подобна шахматной игре.
– Да, – сказал князь Андрей, – только с тою маленькою разницей, что в шахматах над каждым шагом ты можешь думать сколько угодно, что ты там вне условий времени, и еще с той разницей, что конь всегда сильнее пешки и две пешки всегда сильнее одной, a на войне один батальон иногда сильнее дивизии, а иногда слабее роты. Относительная сила войск никому не может быть известна. Поверь мне, – сказал он, – что ежели бы что зависело от распоряжений штабов, то я бы был там и делал бы распоряжения, а вместо того я имею честь служить здесь, в полку вот с этими господами, и считаю, что от нас действительно будет зависеть завтрашний день, а не от них… Успех никогда не зависел и не будет зависеть ни от позиции, ни от вооружения, ни даже от числа; а уж меньше всего от позиции.
– А от чего же?
– От того чувства, которое есть во мне, в нем, – он указал на Тимохина, – в каждом солдате.
Князь Андрей взглянул на Тимохина, который испуганно и недоумевая смотрел на своего командира. В противность своей прежней сдержанной молчаливости князь Андрей казался теперь взволнованным. Он, видимо, не мог удержаться от высказывания тех мыслей, которые неожиданно приходили ему.
– Сражение выиграет тот, кто твердо решил его выиграть. Отчего мы под Аустерлицем проиграли сражение? У нас потеря была почти равная с французами, но мы сказали себе очень рано, что мы проиграли сражение, – и проиграли. А сказали мы это потому, что нам там незачем было драться: поскорее хотелось уйти с поля сражения. «Проиграли – ну так бежать!» – мы и побежали. Ежели бы до вечера мы не говорили этого, бог знает что бы было. А завтра мы этого не скажем. Ты говоришь: наша позиция, левый фланг слаб, правый фланг растянут, – продолжал он, – все это вздор, ничего этого нет. А что нам предстоит завтра? Сто миллионов самых разнообразных случайностей, которые будут решаться мгновенно тем, что побежали или побегут они или наши, что убьют того, убьют другого; а то, что делается теперь, – все это забава. Дело в том, что те, с кем ты ездил по позиции, не только не содействуют общему ходу дел, но мешают ему. Они заняты только своими маленькими интересами.
– В такую минуту? – укоризненно сказал Пьер.
– В такую минуту, – повторил князь Андрей, – для них это только такая минута, в которую можно подкопаться под врага и получить лишний крестик или ленточку. Для меня на завтра вот что: стотысячное русское и стотысячное французское войска сошлись драться, и факт в том, что эти двести тысяч дерутся, и кто будет злей драться и себя меньше жалеть, тот победит. И хочешь, я тебе скажу, что, что бы там ни было, что бы ни путали там вверху, мы выиграем сражение завтра. Завтра, что бы там ни было, мы выиграем сражение!
– Вот, ваше сиятельство, правда, правда истинная, – проговорил Тимохин. – Что себя жалеть теперь! Солдаты в моем батальоне, поверите ли, не стали водку, пить: не такой день, говорят. – Все помолчали.
Офицеры поднялись. Князь Андрей вышел с ними за сарай, отдавая последние приказания адъютанту. Когда офицеры ушли, Пьер подошел к князю Андрею и только что хотел начать разговор, как по дороге недалеко от сарая застучали копыта трех лошадей, и, взглянув по этому направлению, князь Андрей узнал Вольцогена с Клаузевицем, сопутствуемых казаком. Они близко проехали, продолжая разговаривать, и Пьер с Андреем невольно услыхали следующие фразы:
– Der Krieg muss im Raum verlegt werden. Der Ansicht kann ich nicht genug Preis geben, [Война должна быть перенесена в пространство. Это воззрение я не могу достаточно восхвалить (нем.) ] – говорил один.
– O ja, – сказал другой голос, – da der Zweck ist nur den Feind zu schwachen, so kann man gewiss nicht den Verlust der Privatpersonen in Achtung nehmen. [О да, так как цель состоит в том, чтобы ослабить неприятеля, то нельзя принимать во внимание потери частных лиц (нем.) ]
– O ja, [О да (нем.) ] – подтвердил первый голос.
– Да, im Raum verlegen, [перенести в пространство (нем.) ] – повторил, злобно фыркая носом, князь Андрей, когда они проехали. – Im Raum то [В пространстве (нем.) ] у меня остался отец, и сын, и сестра в Лысых Горах. Ему это все равно. Вот оно то, что я тебе говорил, – эти господа немцы завтра не выиграют сражение, а только нагадят, сколько их сил будет, потому что в его немецкой голове только рассуждения, не стоящие выеденного яйца, а в сердце нет того, что одно только и нужно на завтра, – то, что есть в Тимохине. Они всю Европу отдали ему и приехали нас учить – славные учители! – опять взвизгнул его голос.
– Так вы думаете, что завтрашнее сражение будет выиграно? – сказал Пьер.
– Да, да, – рассеянно сказал князь Андрей. – Одно, что бы я сделал, ежели бы имел власть, – начал он опять, – я не брал бы пленных. Что такое пленные? Это рыцарство. Французы разорили мой дом и идут разорить Москву, и оскорбили и оскорбляют меня всякую секунду. Они враги мои, они преступники все, по моим понятиям. И так же думает Тимохин и вся армия. Надо их казнить. Ежели они враги мои, то не могут быть друзьями, как бы они там ни разговаривали в Тильзите.