Как обозначается лямбда в калькулятор
В этой главе мы узнаем о лямбда-исчислении. Лямбда-исчисление описывает понятие алгоритма. Ещё до появления компьютеров в 30-е годы двадцатого века математиков интересовал вопрос о возможности создания алгоритма, который мог бы на основе заданных аксиом дать ответ о том верно или нет некоторое логическое высказывание. Например у нас есть базовые утверждения и логические связки такие как “и”, “или”, “для любого из”, “существует один из”, с помощью которых мы можем строить из базовых высказываний составные. Некоторые из них окажутся ложными, а другие истинными. Нам интересно узнать какие. Но для решения этой задачи прежде всего необходимо было понять а что же такое алгоритм?
Ответ на этот вопрос дали Алонсо Чёрч (Alonso Church) и Алан Тьюринг (Alan Turing). Чёрч разработал лямбда-исчисление, а Тьюринг теорию машин Тьюринга. Оказалось, что задача автоматического определения истинности формул в общем случае не имеет решения.
В основе лямбда-исчисление лежит понятие функции. Мы можем составлять сложные функции из простейших, а также подставлять в функции аргументы, которые могут быть как константами так и другими функциями. Как только мы составили выражение мы можем передать его вычислителю. Он подставляет аргументы в функции и возвращает такое выражение, в котором невозможно далее проводить подстановки аргументов. Этот процесс проведения подстановок считается вычислением алгоритма.
В рамках теории машин Тьюринга алгоритм описывается по-другому. Машина Тьюринга имеет внутреннее состояние, Состояние содержит некоторое значение, которое изменяется по ходу работы машины. Машина живёт не сама по себе, она читает ленту символов. Лента символов – это большая цепочка букв. На каждую букву машина реагирует серией действий. Она может изменить значение состояния, обновить букву в ленте или перейти к следующему или предыдущему символу. Есть состояния, которые обозначают конец работы, они называются терминальными. Как только машина дойдёт до терминального состояния мы считаем, что вычисление алгоритма закончилось. После этого мы можем считать результат из состояний машины.
Функциональные языки программирования основаны на лямбда-исчислении. Поэтому мы будем говорить именно об этом описании алгоритма.
Лямбда исчисление без типов
Составление термов
Можно считать, что лямбда исчисление это такой маленький язык программирования. В нём есть множество символов, которые считаются переменными, они что-то обозначают и неделимы. В лямбда-исчислении программный код называется термом. Для написания программного кода у нас есть всего три правила:
Переменные $x$ , $y$ , $z$ … являются термами.
Если $M$ и $N$ – термы, то $(MN)$ – терм.
Если $x$ – переменная, а $M$ – терм, то $(\lambda x .M)$ – терм
В формальном описании добавляют ещё одно правило, оно говорит о том, что других термов нет. Первое правило, говорит о том, что у нас есть алфавит символов, который что-то обозначает, эти символы являются базовыми строительными блоками программы. Второе и третье правила говорят о том как из базовых элементов получаются составные. Второе правило – это правило применения функции к аргументу. В нём $M$ обозначает функцию, а $N$ обозначает аргумент. Все функции являются функциями одного аргумента, но они могут принимать и возвращать функции. Поэтому применение трёх аргументов к функции $Fun$ будет выглядеть так:
$$(((Fun\ Arg1)\ Arg2)\ Arg3)$$
Третье правило говорит о том как создавать функции. Специальный символ лямбда ( $\lambda$ ) в выражении $(\lambda x .M)$ говорит о том, что мы собираемся определить функцию с аргументом $x$ и телом функции $M$ . С такими функциями мы уже сталкивались. Это безымянные функции. Приведём несколько примеров функций. Начнём с самого простого, определим тождественную функцию:
Функция принимает аргумент $x$ и тут же возвращает его в теле. Теперь посмотрим на константную функцию:
$$(\lambda x .(\lambda y .x))$$
Константная функция является функцией двух аргументов, поэтому наш терм принимает переменную $x$ и возвращает другой терм функцию $(\lambda y .x)$ . Эта функция принимает $y$ , а возвращает x . В Haskell мы бы написали это так:
Точка сменилась на стрелку, а лямбда потеряла одну ножку. Теперь определим композицию. Композиция принимает две функции одного аргумента и направляет выход второй функции на вход первой:
$$(\lambda f .(\lambda g .(\lambda x .(f(gx)))))$$
Переменные $f$ и $g$ – это функции, которые участвуют в композиции, а $x$ это вход результирующей функции. Уже в таком простом выражении у нас пять скобок на конце. Давайте введём несколько соглашений, которые облегчат написание термов:
Целые числа вводятся обычным способом, например: 4 ; 18 ; 56
Для ввода отрицательного числа необходимо поставить знак минус: -19 ; -45 ; -90
Рациональные числа вводятся с использованием символа / , например: 3 / 4 ; -5 / 3 ; 5 / (-19)
Вещественные числа вводятся с использованием точки в качестве разделителя целой и дробной частей: 4.5 ; -0.4
Ввод переменных и констант:
Переменные и константы вводятся латинскими буквами, например: x ; y ; z ; a ; b .
Константы π и e вводятся как pi и e - соответственно.
Символ бесконечности ∞ вводится двумя маленькими латинскими буквами oo или словом inf .
Соответственно, плюс бесконечность задается как +oo, и минус бесконечность как -oo.
Сумма и разность:
Сумма и разность задаются при помощи знаков + и - соответственно, например: 3 + a ; x + y ; 5 - 4 + t ; a - b + 4 ; ВНИМАНИЕ! Никаких пробелов между операндами быть не должно, например ввод: x + a - неправильный , правильно вводить так: x + a - без пробелов.
Умножение:
Умножение задается знаком * , например: 3 * t ; x * y ; -5 * x .
ВНИМАНИЕ! Ввод знака * необходим всегда, т.е. запись типа: 2 x - недопустима . Следует всегда использовать знак * , т.е правильная запись: 3 * x .
Деление:
Деление задается знаком / , например: 15 / a ; y / x ;.
Степень:
Степень задается знаком ^ , например: x ^ 2 ; 4 ^ 2 ; y ^ (-1 / 2) .
Приоритет операций:
Для указания (или изменения) приоритета операций необходимо использовать скобки () , например: ( a + b ) / 4 - тут вначале будет произведено сложение a + b , а потом сумма разделится на 4 , тогда как без скобок: - сначала b разделится на 4 и к полученному прибавится a . ВНИМАНИЕ! В непонятных случаях лучше всегда использовать скобки для получения нужного результата, например: 2 ^ 4 ^ 3 - неясно как будет вычислено это выражение: cначала 2 ^ 4 , а затем результат в степень 3 , или сначала 4 ^ 3 = 64 , а затем 2 ^ 64 ? Поэтому, в данном случае, необходимо использовать скобки: (2 ^ 4) ^ 3 или 2 ^ (4 ^ 3) - смотря что нужно.
Также распространенной ошибкой является запись вида: x ^ 3 / 4 - непонятно: вы хотите возвести x в куб и полученное выражение разделить на 4 , или хотите возвести x в степень 3 / 4 ? В последнем случае необходимо использовать скобки: x ^ (3 / 4) .
Ввод функций:
Функции вводятся с использованием маленьких латинских букв: sin ; cos ; tan ; log .
ВНИМАНИЕ! Аргумент функции всегда берется в скобки () , например: sin( 4 ) ; cos( x ) ; log( 4 + y ) .
Запись типа: sin 4 ; cos x ; log 4 + y - недопустима . Правильная запись: sin( 4 ) ; cos( x ) ; log( 4 + y ) .
Если необходимо возвести функцию в степень, например: синус x и все это в квадрате, это записывается вот так: (sin( x )) ^ 2 . Если необходимо возвести в квадрат аргумент, а не функцию (т.е синус от x ^ 2 ), тогда это выглядит вот так: sin( x ^ 2) . Запись типа: sin ^ 2 x - недопустима .
Как уже говорилось ранее, в чистом бестиповом лямбда-исчислении отсутствует всё, кроме функций. Так что даже такие элементарные вещи, как числа или булевы значения необходимо реализовывать самим. Точнее, надо создать некие активные сущности, которые будут вести себя подобно необходимым нам объектам. И, естественно, процесс кодирования будет заключаться в написании соответствующих функций.
Начнём мы с самого простого: True и False . Два терма, воплощающие поведение этих констант, выглядят следующим образом:
| tru = λt.λf.t | Двухаргументная функция, всегда возвращающая первый аргумент |
| fls = λt.λf.f | Двухаргументная функция, всегда возвращающая второй аргумент |
Оператор if под такие булевы константы будет имеет вид:
if = λb. λx. λy.b x y
Здесь b — tru или fls , x — ветка then , y — ветка else .
Посмотрим, как это будет работать:
if fls t e
Поскольку условие if ложно ( fls ), то должно возвращаться выражение из ветки else ( e в нашем случае).
| (λb. λx. λy. b x y) fls t e | по определению if |
| (λx. λy. fls x y) t e | редукция подчёркнутого выражения из предыдущей строки |
| (λy. fls t y) e | редукция подчёркнутого выражения из предыдущей строки |
| fls t e | редукция подчёркнутого выражения из предыдущей строки |
| (λt.λf. f) t e | по определению fls |
| (λf. f) e | редукция подчёркнутого выражения из предыдущей строки |
| e | редукция подчёркнутого выражения из предыдущей строки |
or = λx.λy. x tru y
not = λx. x fls tru
Числа Чёрча
Мы с вами будем кодировать только натуральные числа, для чего вспомним аксиомы Пеано, определяющие их множество. В основе реализации по-прежнему будут лежать функции, ведущие себя в заданном контексте подобно единице, двойке и т.д. Собственно, это одна из особенностей лямбда-исчисления: сущности, записанные в его терминах, не обладают самодостаточностью, поскольку воплощают поведение того или иного объекта.
Итак, нам нужна функция, принимающая два аргумента: фиксированное начальное значение и функцию для определения следующего элемента (функцию следования). Число будет закодировано в количестве применений функции следования к начальному значению:
| 0 ≡ λs.λz. z | функция s применяется к начальному значению z нуль раз |
| 1 ≡ λs.λz. s z | функция s применяется к начальному значению z один раз |
| 2 ≡ λs.λz. s (s z) | функция s применяется к начальному значению z два раза |
| . | и так далее |
Легко заметить, что нуль кодируется так же, как и логическое False. Тем не менее, не стоит делать из этого какие-либо далеко идущие выводы: это всего лишь совпадение.
Задача функции следования состоит в том, чтобы прибавить к заданному числу единицу. Т.е. в качестве аргумента она будет принимать значение, которое требуется увеличить, и которое тоже является функцией двух аргументов. Таким образом, суммарно функция (+1) имеет три аргумента: предшествующее число Чёрча n , функцию, которую надо будет применить n+1 раз к начальному значению, и само начальное значение. Выглядит это так:
scc = λn. λs. λz. s (n s z)
Здесь n s z — n раз применённая к z функция s . Но нам нужно применить её n+1 раз, откуда и берётся явное s (n s z) .
Арифметические операции
Сложение
Функция, осуществляющая сложение двух чисел Чёрча, будет принимать два слагаемых: x и y , которые в свою очередь тоже имеют по два аргумента — s (функцию следования) и z (начальное значение). Сложение будет состоять в том, чтобы сначала применить s к z x раз, а потом ещё y раз.
plus = λx. λy. λs. λz. x s (y s z)
В качестве примера сложим one = λs.λz. s z и two = λs.λz. s (s z) . Ответ должен будет выглядеть так: three = λs.λz. s (s (s z)) .
| plus one two s' z' | s' и z' — чтобы не путать подставляемые значения с именами переменных |
| (λx. λy. λs. λz. x s (y s z)) one two s' z' | по определению plus |
| one s' (two s' z') | после проведения редукции |
| (λs.λz. s z) s' (two s' z') | по определению one |
| s' (two s' z') | после проведения редукции |
| s' (( λs.λz. s (s z) s' z') | по определению two |
| s' (s' (s' z')) | после проведения редукции |
| three s' z' | по определению three |
Умножение
Функцию для умножения можно определить через функцию сложения. В конце-концов, умножить x на y означает сложить x копий y .
times = λx. λy. x (plus y) z
Есть ещё один способ определения умножения на числах Чёрча, без использования plus . Его идея заключается в том, что для получения произведения x и y нужно x раз взять y раз применённую к начальному значению функцию s :
times' = λx.λy.λs.λz. x (y s) z
Для примера умножим two = λs.λz. s (s z) на three = λs.λz. s (s (s z)) . Результат должен будет иметь вид: six = λs.λz. s (s (s (s (s (s z))))) .
| times' two three s' z' | s' и z' — чтобы не путать подставляемые значения с именами переменных |
| (λx.λy.λs.λz. x (y s) z) two three s' z' | по определению times' |
| two (three s') z' | после проведения редукции |
| (λs.λz. s (s z)) (three s') z' | по определению two |
| three s' ((three s') z') | после проведения редукции |
| (λs.λz. s (s (s z))) s' ((three s') z') | по определению three |
| s' (s' (s' ((three s') z'))) | после проведения редукции |
| s' (s' (s' (((λs.λz. s (s (s z))) s') z'))) | по определению three |
| s' (s' (s' (( (λz. s' (s' (s' z))) z' ))) | после проведения редукции |
| s' (s' (s' (s' (s' (s' z'))))) | редукция подчёркнутого выражения |
| six s' z' | по определению six |
Определите терм для возведения числа в степень
Для x в степени y :
power = λx.λy.λs.λz . y x s z
Заключение
Как видим, технически ничего сложного в лямбда-исчислении нет: всё сводится к элементарным подстановкам и редукциям. Но столь малого набора инструментов вполне хватает, чтобы при желании реализовать активные сущности, ведущие себя подобно парам, спискам, рекурсивным функциям и т.п. Они будут достаточно громоздкими, но, как уже говорилось, λ-исчисление предназначено не для написания программ, а для исследования и спецификации языков программирования и систем типов. С чем, собственно, и прекрасно справляется.
А сегодня немного теории. Я не считаю, что лямбда-исчисление является необходимым знанием для любого программиста. Однако, если вам нравится докапываться до истоков, чтобы понять на чем основаны многие языки программирования, вы любознательны и стремитесь познать все в этом мире или просто хотите сдать экзамен по функциональном программированию (как, например, я), то этот пост для вас.
Что это такое
Лямбда-исчисление - это формальная система, то есть набор объектов, формул, аксиом и правил вывода. Благодаря таким системам с помощью абстракций моделируется теория, которую можно использовать в реальном мире, и при этом выводить в ней новые математически доказуемые утверждения. Например, язык запросов SQL основан на реляционном исчислении. Благодаря математической базе, на которой он существует, оптимизаторы запросов могут анализировать алгебраические свойства операций и влиять на скорость работы.
Но речь сегодня не о SQL, а о функциональных языках. Именно для них лямбда-исчисление является основой. Функциональные языки далеко не столь популярны, как, например, объектно-ориентированные, но тем не менее прочно занимают свою нишу. Кроме того, многие идеи из функционального программирования и лямда-исчисления постепенно прокрадываются в другие языки, под видом новых фич.
Если вы изучали формальные языки, то знаете о таком понятии как Машина Тьюринга. Эта вычислительная абстракция определяет класс вычислимых функций. Этот класс столь важен, так как по тезису Черча он эквивалентен понятию алгоритма. Другими словами, любую программу, которую можно запрограммировать на вычислительном устройстве, можно воспроизвести и на машине Тьюринга. А для нас главное то, что лямбда-исчисление по мощности эквивалентно машине Тьюринга и определяет этот же класс функций. Причем создателем лямбда-исчисления является тот самый Алонзо Черч!
Основные понятия
В нотации лямбда-исчисления есть всего три типа выражений:
- Переменные: ` x, y, z `
- Абстракция - декларация функции: ` lambda x.E ` . Определяем функцию с параметром ` x ` и телом ` E `.
- Аппликация - применение функции ` E_1 ` к аргументу ` E_2 ` : ` E_1 E_2`
Сразу пара примеров:
- Тождественная функция: ` lambda x. x `
- Функция, вычисляющая тождественную функцию: ` lambda x.(lambda y . y) `
Соглашения
Несколько соглашений для понимания, в каком порядке правильно читать выражения:
- Аппликация лево-ассоциативна. То есть выражение ` x y z ` читается как ` (x y) z `.
- В абстракции группируем скобки вправо. Другими словами, читая абстракцию необходимо распространять ее максимально вправо насколько возможно. Пример: выражение ` lambda x. x \ lambda y . x y z ` эквивалентно ` lambda x. (x \ (lambda y . ((x y) z))) ` , так как абстракция функции с аргументом ` x ` включила в себя все выражение. Следом было проведено включение абстракцией с аргументом ` y ` и ,наконец, в теле этой функции были расставлены скобки для аппликации.
Области видимости переменных
Определим контекст переменной, в котором она может быть использована. Абстракция ` lambda x.E ` связывает переменную ` x `. В результате мы получаем следующие понятия:
- ` x ` - связанная переменная в выражении .
- ` E ` - область видимости переменной ` x `.
- Переменная свободна в ` E ` , если она не связана в ` E ` . Пример: ` lambda x. x (lambda y. x y z) ` . Cвободная переменная - ` z ` .
Взглянем на следующий пример: ` lambda x. x (lambda x. x) x ` .
Понимание лямбда-выражений существенно усложняется, когда переменные с разными значениями и контекстами используют идентичные имена. Поэтому впредь мы будем пользоваться следующим соглашением: связанные переменные необходимо переименовывать для того, чтобы они имели уникальные имена в выражении. Это возможно благодаря концептуально важному утверждению: выражения, которые могут быть получены друг из друга путем переименования связанных переменных, считаются идентичными. Важность этого утверждения в том, что функции в исчислении определяются лишь своим поведением, и имена функций не несут никакого смысла. То есть, функции ` lambda x. x ` , ` lambda y. y ` , ` lambda z. z ` на самом деле одна тождественная функция.
Вычисление лямбда-выражений
Вычисление выражений заключается в последовательном применении подстановок. Подстановкой ` E’ ` вместо ` x ` в ` E \ ` (запись: ` [E’//x]E ` ) называется выполнение двух шагов:
- Альфа-преобразование. Переименование связанных переменных в ` E ` и ` E’ ` , чтобы имена стали уникальными.
- Бета-редукция. По сути единственная значимая аксиома исчисления. Подразумевает замену ` x ` на ` E’ ` в ` E ` . Рассмотрим несколько примеров подстановок:
- Преобразование к тождественной функции. ` (lambda f. f (lambda x. x)) (lambda x. x) -> ` (пишем подстановку) ` -> [lambda x. x // f] f ( lambda x. x)) = ` (делаем альфа-преобазование) ` = [(lambda x. x) // f] f (lambda y. y)) = ` (производим бета-редукцию) ` = (lambda x. x) (lambda y. y) -> ` (еще одна подстановка) ` -> [lambda y. y // x] x = lambda y. y `
- Бесконечные вычисления. ` (lambda x. x x)(lambda x. x x) -> [lambda x. x x // x]x x = [lambda y. y y // x] x x = ` ` = (lambda y. y y)(lambda y. y y) -> … `
- Также небольшой пример, почему нельзя пренебрегать альфа-преобразованием. Рассмотрим выражение ` (lambda x. lambda y. x) y ` . Если не выполнить первый шаг, результатом будет тождественная функция ` lambda y. y ` . Однако, после правильного выполнения подстановки с заменой ` y ` на ` z ` мы получим совсем другой результат ` lambda z. y ` , то есть константную функцию.
Функции нескольких переменных
Для того чтобы использовать функции нескольких переменных добавим в исчисление новую операцию ` add ` : она применяется к двум аргументам и является синтаксическим сахаром для следующих вычислений: ` (lambda x. lambda y. add \ x y) E_1 E_2 -> ([E_1 // x] lambda y. add \ x y) E_2 = ` ` (lambda y. add \ E_1 y) E_2 -> ` ` [E_2 // y] add \ E_1 y = add \ E_1 E_2 `
Как результат мы получили функцию от одного аргумента, которая возвращает еще одну функцию от одного аргумента. Такое преобразование называется каррирование (в честь Хаскелла Карри назвали и язык программирования, и эту операцию), а функция, возвращающая другую, называется функцией высшего порядка.
Порядок вычислений
Бывают ситуации, когда произвести вычисление можно несколькими способами. Например, в выражении ` (lambda y. (lambda x. x) y) E ` сначала можно подставлять ` y ` вместо ` x ` во внутреннее выражение, либо ` E ` вместо ` y ` во внешнее. Теорема Черча-Рассера говорит о том, что в не зависимости от последовательности операций, если вычисление завершится, результат будет одинаков. Тем не менее, эти два подхода принципиально отличаются. Рассмотрим их подробнее:
- Вызов по имени. В вычислении всегда в первую очередь применяются самые внешние подстановки. Другими словами, нужно вычислять аргумент уже после подстановки в функцию. Кроме того нельзя использовать редукцию внутри абстракции. Пример: ` (lambda y. (lambda x. x) y) ((lambda u. u) (lambda v. v)) -> ` (применяем редукцию к внешней функции) ` -> (lambda x. x) ((lambda u. u) (lambda v. v)) -> ` (вновь подставляем, не меняя аргумент) ` -> (lambda u. u) (lambda v. v) = lambda v. v `
- Вызов по значению. В этом способе вычисление проходит ровно наоборот, то есть сначала вычисляется аргумент функции. При этом редукция внутри абстракции также не применяется. Пример: ` (lambda y. (lambda x. x) y) ((lambda u. u) (lambda v. v)) -> ` (вычисляем аргумент функции) ` -> (lambda y. (lambda x. x) y) (lambda v. v) -> (lambda x. x) (lambda v. v) -> lambda v. v `
Из практических отличий этих двух подходов отметим, то что вычисление по значению более сложно в реализации и редко используется для всех вычислений в неисследовательских языках. Однако, второй подход может не привести к завершению вычисления. Пример: ` (lambda x. lambda z.z) ((lambda y. y y) (lambda u. u u)) ` . При вычислении аргумента мы попадаем в бесконечный цикл, в то время как, проводя вычисления по имени функции, мы сразу получим тождественную функцию.
Кодирование типов
В чистом лямбда-исчислении есть только функции. Однако, программирование трудно представить без различных типов данных. Идея заключается в том, чтобы закодировать поведение конкретных типов в виде функций.
- Булевые значения. Поведение типа можно описать как функцию, выбирающую одно из двух. Тогда значения выглядят так: ` true = lambda x. lambda y. x ` и ` false = lambda x. lambda y. y `
- Натуральные числа. Каждое натуральное число может быть описано как функция, проитерированная заданное число раз. Выпишем несколько первых чисел ( ` f ` - функция, которую итерируем, а ` s ` - начальное значение):
- ` 0 = lambda f. lambda s. s `
- ` 1 = lambda f. lambda s. f s `
- ` 2 = lambda f. lambda s. f (f s) `
- Операции с натуральными числами.
- Следующее число. ` \s\u\c\c \ n = lambda f. lambda s. f (n f s) ` . Аргумент функции - число ` n ` , которое, будучи так же функцией, принимает еще два аргумента: начальное значение и итерируемую функцию. Для числа ` n ` один раз применяем функцию ` f ` и получаем следующее число.
- Сложение. ` add \ n_1 n_2 = n_1 \ \s\u\c\c \ n_2 ` . Для сложения чисел ` n_1 ` и ` n_2 ` нужно одному из слагаемых передать в параметры функцию ` \s\u\c\c `, как итерруемую функцию, и другое слагаемое, как начальное значение. В результате мы увеличим заданное число на единицу необходимое число раз.
- Умножение. ` \m\u\l\t \ n_1 n_2 = n_1 (add \ n_2) 0 ` . В роли итерируемой функции для множителя ` n_1 ` выступает функция ` \s\u\c\c ` с аргументом ` n_2 ` , а в роли начального значения уже определенное число ` 0 ` . То есть мы определяем умножение как прибавление ` n_2 ` к нулю ` n_1` раз.
Аналогично, с помощью лямбда-исчисления можно выразить любые конструкции языков программирования, такие как циклы, ветвления, списки и тд.
Заключение
Лямбда-исчисление - очень мощная система, которая позволяет писать любые программы. Однако, непосредственно программирование на лямбда-исчислении получается черезчур громоздким и неудобным. Тем не менее, чистое лямбда-исчисление предназначено вовсе не для программирования на нем, а для изучения существующих и создания новых языков программирования. А следующим шагом на пути к типовым функциональным языкам является типизированное лямбда-исчисление - расширение чистого исчисления типовыми метками.
Читайте также: