Привет! В этой статье я хочу в очередной раз взглянуть на лямбда-исчисление. Теоретическую сторону вопроса на хабре обсуждали уже множество раз, поэтому взглянем на то, как лямбда-исчисление может выглядеть на практике, например, на языке JavaScript (чтобы примеры можно было выполнять прямо в браузере).
Итак, основная идея: всё есть функция. Поэтому мы ограничим себя очень узким кругом возможностей языка: любое выражение будет либо анонимной функцией с одним аргументом (
Поскольку результатом работы функций будут другие функции, нам понадобится способ интерпретировать результат. Это единственное место, в котором пригодятся нетривиальные возможности JavaScript.
Начнём, как это принято, с условного ветвления. Введём две константы:
Это функции «двух аргументов»,
Данные константы представляют логические истину и ложь, и позволяют написать функцию
Это уже похоже на традиционный оператор
Следующим делом введём первую «структуру данных» — пару. Определение выглядит следующим образом:
Оно выглядит немного страннее, но в нём есть смысл. Пара в данном случае есть функция, инкапсулирующая внутри себя 2 значения и способная передать их своему параметру при вызове. Подобным образом можно описать кортеж любой длины:
Вообще говоря, с подобным арсеналом мы уже могли бы определить
Арифметика Чёрча описывает множество натуральных чисел с нулём как функции от двух аргументов:
Первый аргумент — это функция, второй аргумент — это что-то, к чему функция применяется
Тут стоит ещё описать способ преобразования чисел Чёрча во всем нам знакомый
Аналогично определяются операции сложения, умножения и т.д.:
Таки образом можно продолжать реализовывать стрелочную нотацию, но смысла в этом нет: к этому моменту принцип работы с числами должен быть понятен.
Следующий шаг — вычитание. Следуя только что появившейся традиции, его реализация будет вот такой:
но остаётся проблемой реализация функции Pred. К счастью, Клини придумал её за нас.
История гласит, что эта идея возникла у него во время приёма у дантиста, а анестезия тогда была посильнее, чем сейчас. Не буду с этим спорить, а объясню, что тут творится. Для получения предыдущего числа мы строим пару
Для полноты картины приведу реализации операций сравнения:
Списки кодируются практически так же, как и натуральные числа — это тоже функции двух аргументов.
Интересно отметить, что
Если вы знакомы с функциональными операциями на списках, то, вероятно, уже заметили, что эта структура описывает правую свёртку. Поэтому и реализуется она тривиально:
Теперь реализуем стандартные операции для персистентных списков — добавление в начало, получение «головы» и «хвоста» списка.
Пустые скобки в конце описания
Функция получения хвоста списка практически полностью повторяет функцию получения предыдущего натурального числа. По той же причине хвост пустого списка будет пустым списком.
Как пример использования, приведу реализацию функции
К этому моменту работа исключительно с функциями стала подозрительно похожей на «нормальное» программирование. Пришло время всё испортить. Поскольку мы ограничили себя лишь объявлением и вызовом функций, у нас полностью отсутствует любой синтаксический сахар, а значит, многие простые вещи нам придётся записывать сложным образом.
Например, я хочу написать функцию
Видите ошибку? Если
Теперь
Вторая проблема — рекурсия. Внутри функции мы можем обращаться только к её формальным аргументам. Это значит, что функция не может ссылаться сама на себя по имени.
Но решение есть, это пресловутый «Комбинатор Неподвижной Точки». Обычно после этих слов приводится описание комбинатора Y, но для аппликативного порядка он не годится. Вместо него мы будем использовать комбинатор
Комбинатор — это функция, выбираемая исходя из ровно одного свойства:
«Главное свойство» комбинатора даёт прекрасный «побочный эффект»: возможность реализации рекурсии. Например, запись:
эквивалентна записи:
а значит первый формальный параметр анонимной функции фактически совпадает с самой функцией
После этого можно реализовать наш первый полезный алгоритм — алгоритм Евклида. Забавно, но он вышел ничуть не сложнее поиска остатка от деления.
Последняя структура данных, которой я коснусь, это «бесконечные списки», или последовательности. Функциональное программирование славится возможностью работать с подобными объектами, и я просто не могу обойти их стороной.
Объявляются последовательности следующим образом:
Хвост последовательности в конструкторе — это функция вычисления новой последовательности, а не готовый результат. Такой подход обеспечивает возможность генерировать хвост бесконечной длины.
Для возможности тестирования напишем функцию получения первых
Если хотите поупражняться — реализуйте
Теперь стоит привести пример какой-нибудь последовательности. Пусть это будут натуральные числа — всё-таки приходится работать только с тем, что уже реализовано:
Тут используется вспомогательная функция
Осталось совсем немного, последние 2 функции, и они самые громоздкие из тех, что есть в данном тексте. Первая — функция фильтрации последовательности. Она находит в передаваемой последовательности все элементы, удовлетворяющие переданному предикату:
В случае, если головной элемент не выполняет предикат,
Вторая — последовательность простых чисел. Очередной вариант Решета Эратосфена в моём исполнении:
Эту функцию можно назвать кульминацией статьи. Принцип её работы проще будет понять на псевдокоде:
Вот тест:
Не знаю, как вас, а меня всё ещё удивляет, что подобные вещи возможно написать с помощью лишь чистых функций!
В итоге у меня получилось такое вот странное введение в LISP на примере языка JavaScript. Надеюсь я смог показать, что абстрактные математические идеи на самом деле очень близки к реальности программирования. И после подобного взгляда лямбда-исчисление перестанет выглядеть чем-то чересчур академичным.
Ну и, конечно, вот ссылка на Github со всем кодом из статьи.
Спасибо!
Итак, основная идея: всё есть функция. Поэтому мы ограничим себя очень узким кругом возможностей языка: любое выражение будет либо анонимной функцией с одним аргументом (
x => expr), либо вызовом функции (f (x)). То есть весь код будет выглядеть похожим образом:id = x => x
double = f => x => f (f (x))
Поскольку результатом работы функций будут другие функции, нам понадобится способ интерпретировать результат. Это единственное место, в котором пригодятся нетривиальные возможности JavaScript.
Базовые вещи
Начнём, как это принято, с условного ветвления. Введём две константы:
True = t => f => t
False = t => f => f
Это функции «двух аргументов»,
True возвращает первый аргумент, False возвращает второй аргумент. То есть, справедливы следующие утверждения:console.assert(1 == True (1) (2))
console.assert(2 == False (1) (2))
Данные константы представляют логические истину и ложь, и позволяют написать функцию
If:If = b => t => f => b (t) (f)
console.assert(1 == If (True) (1) (2))
console.assert(2 == If (False) (1) (2))
Это уже похоже на традиционный оператор
if, просто синтаксически выглядит немного иначе. Имея условное ветвление, можно легко реализовать стандартные булевы операторы:Not = x => If (x) (False) (True)
And = x => y => If (x) (y) (False)
Or = x => y => If (x) (True) (y)
Следующим делом введём первую «структуру данных» — пару. Определение выглядит следующим образом:
Pair = x => y => (f => f (x) (y))
Fst = p => p (True)
Snd = p => p (False)
p = Pair (1) (2)
console.assert(1 == Fst (p))
console.assert(2 == Snd (p))
Оно выглядит немного страннее, но в нём есть смысл. Пара в данном случае есть функция, инкапсулирующая внутри себя 2 значения и способная передать их своему параметру при вызове. Подобным образом можно описать кортеж любой длины:
Triplet = x => y => z => (f => f (x) (y) (z))
Pentuplet = x => y => z => u => v => (f => f (x) (y) (z) (u) (v))
Вообще говоря, с подобным арсеналом мы уже могли бы определить
Byte как кортеж из 8 логических значений, Int как кортеж из 4 Byte и реализовать на них машинную арифметику, но дело это рутинное и удовольствия никакого не принесёт. Есть более красивый способ описать натуральные числа — арифметика Чёрча.Арифметика
Арифметика Чёрча описывает множество натуральных чисел с нулём как функции от двух аргументов:
Zero = s => z => z
One = s => z => s (z)
Two = s => z => s (s (z))
Three = s => z => s (s (s (z)))
Первый аргумент — это функция, второй аргумент — это что-то, к чему функция применяется
n раз. Для их построения, по сути, нужны только ноль и функция +1:Succ = n => (s => z => s (n (s) (z)))
Succ накидывает слева ещё один вызов s на уже имеющуюся цепочку вызовов, тем самым возвращая нам следующее по порядку натуральное число. Если данная функция кажется сложной, есть альтернативный вариант. Результат его работы будет абсолютно таким же, но накидывание s здесь происходит справа:Succ = n => (s => z => n (s) (s (z)))
Тут стоит ещё описать способ преобразования чисел Чёрча во всем нам знакомый
int — это в точности применение функции x => x + 1 к нулю n раз:toInt = n => n (x => x + 1) (0)
console.assert(0 == toInt (Zero))
console.assert(1 == toInt (One))
console.assert(2 == toInt (Two))
Аналогично определяются операции сложения, умножения и т.д.:
Add = n => m => m (Succ) (n)
Mul = n => m => m (Add (n)) (Zero)
Pow = n => p => p (Mul (n)) (One)
//? = n => m => m (Pow (n)) (One)
Таки образом можно продолжать реализовывать стрелочную нотацию, но смысла в этом нет: к этому моменту принцип работы с числами должен быть понятен.
Следующий шаг — вычитание. Следуя только что появившейся традиции, его реализация будет вот такой:
Sub = n => m => m (Pred) (n)
но остаётся проблемой реализация функции Pred. К счастью, Клини придумал её за нас.
Pred = n => Fst
(n (p => Pair (Snd (p))
(Succ (Snd (p))))
(Pair (Zero) (Zero)))
История гласит, что эта идея возникла у него во время приёма у дантиста, а анестезия тогда была посильнее, чем сейчас. Не буду с этим спорить, а объясню, что тут творится. Для получения предыдущего числа мы строим пару
(n-1, n) следующим образом: применяем n раз функцию (x, y) -> (y, y+1) к паре (0, 0) и у результата извлекаем левый компонент. Как следствие, легко заметить, что число, предыдущее для нуля, тоже будет нулём. Это спасает от неопределённости и даёт множество других преимуществ.Для полноты картины приведу реализации операций сравнения:
IsZero = n => n (_ => False) (True)
Lte = n => m => IsZero (Sub (n) (m))
Lt = n => m => Lte (Succ (n)) (m)
Eq = n => m => And (Lte (n) (m)) (Lte (m) (n))
Max = n => m => If (Lte (n) (m)) (m) (n)
Min = n => m => If (Lte (n) (m)) (n) (m)
Списки
Списки кодируются практически так же, как и натуральные числа — это тоже функции двух аргументов.
Nil = f => x => x
L1 = f => x => f (a0) (x)
L2 = f => x => f (a0) (f (a1) (x))
L3 = f => x => f (a0) (f (a1) (f (a2) (x)))
//...
Интересно отметить, что
False, Zero и Nil являются одинаковыми функциями.Если вы знакомы с функциональными операциями на списках, то, вероятно, уже заметили, что эта структура описывает правую свёртку. Поэтому и реализуется она тривиально:
Foldr = f => z => l => l (f) (z)
Теперь реализуем стандартные операции для персистентных списков — добавление в начало, получение «головы» и «хвоста» списка.
Append = a => l => (f => x => f (a) (l (f) (x)))
Head = l => l (a => _ => a) ()
list = Append (1) (Append (2) (Nil))
console.assert(1 == Head (list))
Пустые скобки в конце описания
Head — это голова пустого списка. В корректной программе данное значение никогда не должно быть использовано, поэтому я и выбрал синтаксически наименьшую величину. Вообще говоря, внутри этих скобок можно писать всё, что угодно. Позднее в статье будет ещё одно место, где я буду использовать пустые скобки по абсолютно той же причине.Функция получения хвоста списка практически полностью повторяет функцию получения предыдущего натурального числа. По той же причине хвост пустого списка будет пустым списком.
Tail = l => Fst (
l (a => p => Pair (Snd (p))
(Append (a) (Snd (p))))
(Pair (Nil) (Nil))
)
console.assert(2 == Head (Tail (list)))
Как пример использования, приведу реализацию функции
map и ещё некоторых других:Map = m => l => (f => x => l (a => f (m (a))) (x))
Length = l => Foldr (_ => Succ) (Zero) (l)
IsEmpty = l => IsZero (Length (l))
// конвертация в стандартный список языка JavaScript
toList = l => Foldr (x => y => [x].concat(y)) ([]) (l)
toIntList = l => toList (Map (toInt) (l))
function arraysEqual(a,b) { return !(a < b) && !(b < a); } // надо для ассертов
Map заменяет каждый элемент списка результатом вызова функции f на нём.Length и IsEmpty говорят сами за себя. toList и toIntList будут полезны для тестирования и для вывода списков в консоль.Рекурсия
К этому моменту работа исключительно с функциями стала подозрительно похожей на «нормальное» программирование. Пришло время всё испортить. Поскольку мы ограничили себя лишь объявлением и вызовом функций, у нас полностью отсутствует любой синтаксический сахар, а значит, многие простые вещи нам придётся записывать сложным образом.
Например, я хочу написать функцию
OnNonEmpty : fun => list => result, которая будет вызывать функцию fun на списке list только если он не пуст. Попробуем:OnNonEmpty = f => l => If (IsEmpty (l)) (Nil) (f (l))
Видите ошибку? Если
f не останавливается на пустом списке, то и OnNonEmpty не остановится, хотя должна. Дело в том, что JavaScript предоставляет нам аппликативный порядок вычислений, то есть все аргументы функции вычисляются до её вызова, никакой ленивости. А оператор If должен вычислять лишь одну ветку в зависимости от условия. Поэтому функцию нужно переписать, и красивее она от этого не станет.OnNonEmpty = f => l => (If (IsEmpty (l)) (_ => Nil) (_ => f (l))) ()
Теперь
If, в зависимости от условия, возвращает функцию, которую нужно вычислить. И только после этого производится вычисление, только так мы можем гарантировать ленивость.Вторая проблема — рекурсия. Внутри функции мы можем обращаться только к её формальным аргументам. Это значит, что функция не может ссылаться сама на себя по имени.
Но решение есть, это пресловутый «Комбинатор Неподвижной Точки». Обычно после этих слов приводится описание комбинатора Y, но для аппликативного порядка он не годится. Вместо него мы будем использовать комбинатор
Z, бессовестно подсмотренный в этой замечательной статье.Z = f => (x => f (y => x (x) (y)))
(x => f (y => x (x) (y)))
Комбинатор — это функция, выбираемая исходя из ровно одного свойства:
Z (f) == f (Z (f)), то есть Z(f) — это такое значение x, что x == f (x). Отсюда и термин «неподвижная точка». Но не нужно думать, что каким-то чудом комбинатор способен решать уравнения, вместо этого он представляет собой бесконечный рекурсивный вызов Z(f) = f (f (f (f ( ... )))).«Главное свойство» комбинатора даёт прекрасный «побочный эффект»: возможность реализации рекурсии. Например, запись:
MyFun = Z (myFun => ...)
эквивалентна записи:
MyFun = (myFun => ...) MyFun // если бы мы разрешили так делать
а значит первый формальный параметр анонимной функции фактически совпадает с самой функцией
MyFun, и мы можем осуществлять в ней настоящие рекурсивные вызовы. Попробуем на примере поиска остатка от деления:Rem = Z (rem => n => m => (
If (Lt (n) (m)) (_ => n)
(_ => rem (Sub (n) (m)) (m))
) ())
console.assert(1 == toInt (Rem (Three) (Two)))
console.assert(0 == toInt (Rem (Three) (One)))
После этого можно реализовать наш первый полезный алгоритм — алгоритм Евклида. Забавно, но он вышел ничуть не сложнее поиска остатка от деления.
Gcd = Z (gcd => n => m => (
If (IsZero (m)) (_ => n)
(_ => gcd (m) (Rem (n) (m)))
) ())
Последовательности
Последняя структура данных, которой я коснусь, это «бесконечные списки», или последовательности. Функциональное программирование славится возможностью работать с подобными объектами, и я просто не могу обойти их стороной.
Объявляются последовательности следующим образом:
Seq = head => tail => Pair (head) (tail)
SeqHead = seq => Fst (seq)
SeqTail = seq => (Snd (seq)) ()
Хвост последовательности в конструкторе — это функция вычисления новой последовательности, а не готовый результат. Такой подход обеспечивает возможность генерировать хвост бесконечной длины.
Для возможности тестирования напишем функцию получения первых
n элементов:SeqTake = Z (take => n => seq => (
If (IsZero (n)) (_ => Nil)
(_ => Append (SeqHead (seq))
(take (Pred (n)) (SeqTail (seq))))
) ())
Если хотите поупражняться — реализуйте
SeqTake без рекурсии. Это возможно, я гарантирую.Теперь стоит привести пример какой-нибудь последовательности. Пусть это будут натуральные числа — всё-таки приходится работать только с тем, что уже реализовано:
Nat = (Z (natFrom => n => Seq (n) (_ => natFrom (Succ (n))))) (Zero)
console.assert(arraysEqual([0, 1, 2], toIntList (SeqTake (Three) (Nat))))
Тут используется вспомогательная функция
natFrom (n), возвращающая последовательность натуральных чисел, начинающуюся с n. Nat — это просто результат natFrom (Zero).Осталось совсем немного, последние 2 функции, и они самые громоздкие из тех, что есть в данном тексте. Первая — функция фильтрации последовательности. Она находит в передаваемой последовательности все элементы, удовлетворяющие переданному предикату:
SeqFilter = Z (filter => cond => seq => (
If (cond (SeqHead (seq))) (_ => Seq (SeqHead (seq))
(_ => filter (cond) (SeqTail (seq))))
(_ => filter (cond) (SeqTail (seq)))
) ())
В случае, если головной элемент не выполняет предикат,
SeqFilter возвращает отфильтрованный хвост. В противном случае это будет последовательность из текущей головы и всё того же отфильтрованного хвоста.Вторая — последовательность простых чисел. Очередной вариант Решета Эратосфена в моём исполнении:
Primes = (Z (sieve => nums =>
Seq (SeqHead (nums))
(_ => sieve (SeqFilter (p => Not (IsZero (Rem (p) (SeqHead (nums)))))
(SeqTail (nums)))
))) (SeqTail (SeqTail (Nat)))
Эту функцию можно назвать кульминацией статьи. Принцип её работы проще будет понять на псевдокоде:
sieve (nums) {
p = head (nums)
rest = tail (nums)
return append (p, sieve (filter (n -> n % p != 0, rest)))
}
primes = sieve [2, 3, 4, ...]
Вот тест:
Ten = Mul (Two) (Add (Two) (Three)) // s => z => s (s (s (s (s (s (s (s (s (s (z))))))))))
console.assert(arraysEqual([2, 3, 5, 7, 11, 13, 17, 19, 23, 29],
toIntList (SeqTake (Ten) (Primes))))
Не знаю, как вас, а меня всё ещё удивляет, что подобные вещи возможно написать с помощью лишь чистых функций!
Заключение
В итоге у меня получилось такое вот странное введение в LISP на примере языка JavaScript. Надеюсь я смог показать, что абстрактные математические идеи на самом деле очень близки к реальности программирования. И после подобного взгляда лямбда-исчисление перестанет выглядеть чем-то чересчур академичным.
Ну и, конечно, вот ссылка на Github со всем кодом из статьи.
Спасибо!
Поделиться с друзьями
lookid
true
NikSelite
TheShock
Статья о том, как написать js-код после которого тебя не смогут уволить.
mannaro
Да после такого кода и ультиматум о повышении зп можно ставить
(шутка).klylex
js-террорист
Drag13
Дошел до конца, не нашел тега brainfuck.
zede
Не поверите, но я как раз собирался писать статью о лямбда исчислении на JS и даже написал под нее библиотеку.
Статья очень хорошо переварена для неподготовленного читателя(статья на викиконспектах зашла далеко не с первого раза)
На самом деле неплохо было бы раскрыть понятия: каррирования/декаррирования и частичного применения функций, которые тут показаны, но не указано, что это они и есть, а прочитавшие статью могут так и не понять, что страшные термины, которых они ранее избегали весьма безобидные и понятные.
xGromMx
Идея в том, что имея бедное ЛИ можно закодировать почти любую конструкцию
shuhray
Вот вычисление лямбда-термов в браузере (не моё)
https://www.npmjs.com/package/inet-lib
Sirikid
Меня больше удивляет что люди используют язык в котором практически полностью отсутствуют типы:
Почему в лисп?
Ну и ещё немного LC:
ibessonov
Ну согласитесь, практически один в один!
Что касается комбинаторной логики — основные комбинаторы описать не сложно, но я бы с удовольствием глянул на реализацию того же алгоритма Евклида в подобном стиле.
xGromMx
Ну комбинаторы были предшественниками лямбда исчислению. Их идея в том что у них есть только одна метаоперация в отличии от лямбда исчисления где их две (абстракция и аппликация) Вот вам задание напишите дерево на js потом на Черче и попробуйте написать изоморфны функции чтобы через обычное дерево считать для Черча (у меня все это написано на хаскель через ана и катаморфизмы используя F-algebra) На js я вроде тоже подобное видел называется excursion (от DrBoolean) Но как было замечено что лучше использовать языки типа хаскель для таких забав которыми вы тут занимались =)
ibessonov
Увы, haskell подходит только для типизированного лямбда-исчисления, я пробовал. Именно поэтому пришлось прибегнуть к языку с динамической типизацией.
xGromMx
Если я говорю, что можно использовать Черча в хаскель то это так и есть. И выглядит даже лучше
ibessonov
Продемонстрируйте, пожалуйста, операцию вычитания для чисел Чёрча на хаскеле. Вероятно, я просто не смог её написать, поэтому хочу взглянуть, как это делается.
xGromMx
Позже, нет доступа к компьютеру сейчас
shuhray
Вычитание единицы для чисел Чёрча довольно трудно сделать (сам Чёрч не справился, придумал Клини, сидя под наркозом у зубного врача). Вот в этой книге поищите
gen.lib.rus.ec/search.php?req=методы+рекурсивного+программирования&lg_topic=libgen&open=0&view=simple&res=25&phrase=1&column=def
ibessonov
Спасибо! В статье уже есть классическая реализация вычитания, и даже история про дантиста :)
Беда в том, что на хаскеле придётся писать типизированное лямбда-исчисление, и типы будут основной проблемой.
Sirikid
В принципе всегда можно написать
(или это будет считаться читерством?)
ibessonov
Это уже написание интерпретатора внутри хаскеля. Можно, конечно, но это не тот результат, который хотелось бы иметь)
xGromMx
Описываешь нат числа через ADT с RankNTypes и дальше пойдет)
Sirikid
Не соглашусь, большая часть скобок появились из-за JS, а не из-за самого лямбда-исчисления.
Вообще в распространенных лиспах неудобно использовать каррирование и частичное применение, а Haskell и компания, опять же, не требуют столько скобок.
ibessonov
Верно, скобки от JS, а каррирование из лямбда-исчисления. Идея в том, что избавление от этих вещей, ровно как и введение if и let, — это просто синтаксический сахар, который мало меняет суть.
xGromMx
Это M комбинатор, в энергичных языках его определить можно, а в ленивых типа хаскеля нет (это если все что у ас есть то примитивы как функции)
Nakosika
Соглашусь, никаким лиспом тут и не пахнет. К Хаскелю гораздо ближе. Лисп проще раз в тыщу.
В лиспе только простейшие операции над списками типа «первый элемент», «добавить элемент к началу», «следующие за первым элементы» и т.п. Рекурсивный вызов и лямбды есть, но они имеет явно не математическое обоснование.
ibessonov
Можно немного конкретнее, чем лямбда-исчисление ближе к Хасеклю, чем к Лиспу?
Мне кажется, что система типов в этой ситуации решает далеко не в сторону Хаскеля.
Nakosika
Тем что на Хаскеле любая операция выражается через реальные функциональные трансформации, а в лиспе слово «лямбда» присутствует из уважения к Чарчу, и сама работа идет при помощи обычных функций как мы их понимаем в Питоне, Яве и других более близких к народу языках.
ibessonov
Статья ровно о том, что "обычные функции" и лямбды это одно и то же. Мне не пришлось в JS придумывать какие-то особые функции, чем-то отличающиеся от Питона и Явы.
Sirikid
В википедии написано что в основе лиспа лежит ЛИ, какое именно правда не указано, может быть и нетипизированное. В любом случае термов зависящих от типов тут нет, выходит что лисп ближе.
Nakosika
Пол Грехм, «On Lisp» вот тут: http://www.paulgraham.com/onlisptext.html
Ни арифметики Черча, ни «все есть функция», ничего подобного.
Просто есть ячейка «значение + следующий элемент», и на основании таких ячеек строится язык.
Википедия конечно может тоже правду пишет, на все можно посмотреть с разных сторон. И на Луне можно сыр найти.
Вот еще интересная ссылка: http://norvig.com/lispy.html реализация Лиспа на Питоне, около 40-а строк. Математикой и не пахнет, чистая работа с данными.
А Хаскель как раз вокруг математики Чарча и построен, именно из-за этой математики у всех при изучении Хаскеля такая головная боль.
ibessonov
Интересно видеть символ лямбды на титульной странице! И почему вас не удивляет, что в Лиспе все функции префиксные (в отличие от того же Хаскеля). Так или иначе — в книге нет ни слова о истории создания Лиспа. Да и числа Чёрча там, естественно, не будут использоваться, ибо машинное представление эффективнее на практике.
Есть так же другая уважаемая книга:
Гарольд Абельсон и Джералд Джей Сассман, "Структура и интерпретация компьютерных программ".
Советую взглянуть на параграф 2.1.3, там как раз про
cons,carиcdr.В первую очередь он построен вокруг идеи функционального программирования, появившейся с Лиспом, и вокруг системы типов Хиндли-Милнера (да, она имеет корни в математике, но головной боли ни у кого не вызывает).
Nakosika
Какое отношение лямбды имеют к нашему диалогу?
Лисп: все есть список
Хаскель: все есть функция
Мне как-бы все очевидно.
Вы ссылку мне дали и там черным по белому написано: «Демонстрировать процедурную реализацию имеет смысл не для того, чтобы показать, как работает наш язык (Scheme, и вообще Лисп-системы, реализуют пары напрямую из соображений эффективности), а в том, чтобы показать, что он мог бы работать и так. »
То есть лисп работает на реальных списках, а не на функциях. Списки можно выразить при помощи функций, равно как и функции можно представить в виде списков. Но то что car и cdr являются одними из (шести кажется) форм, которые принципиально нельзя выразить другими операциями, как-бы намекает.
Nakosika
То что Хиндли-Милнеры что-то там выразили в математике, вовсе не означает что без математики такой штуки нет. Лично для меня было очевидно как выводить типы еще до того как я узнал об этих ребятах, думаю для многих других тоже. Но мне потребовалось пол дня потратить чтобы разобраться с ихними формулами, и понять что там ничего эзотерического, просто ребята повеселились используя математику для описания простых вещей.
Это как если ты используешь счеты, и тут приходит перец и говорит: смотри, я выразил твои исчисления при помощи матанализа, вот книга которую ты должен изучить чтобы научиться считать на счетах, и ты должен меня уважать, так как я придумал счеты, я математик. Че??
Хиндли-Милнер как раз очевиден и не вызывает головной боли, если не пытаться его читать в оригинале.
Я о математике выражения всего через функции говорил. Про вот эту запись: «L3 = f => x => f (a0) (f (a1) (f (a2) (x)))» для вас может это и очевидно, а для обычных людей это белиберда. Когда математики начинают разжевывать, оказывается что они просто все запутали излишним использованием символизации в месте где можно было использовать обычную человеческую речь, а сама идея и выеденного яйца не стоит.
ibessonov
Меня возмущает то, как легко вы плюёте на математику, лежащую в основе программирования.
Цель статьи — показать, насколько лямбда-исчисление, которому без малого 100 лет, по факту близко к современному программированию. Что это не просто бесполезная заумная теория, какой её себе представляют люди подобные вам.
Если вы не хотите задумываться над тем, что читаете, то данная статья не для вас. У меня отбито всё желание продолжать данный диалог, извините.
Nakosika
В основе современного программирования лежит обработка данных. Математика *используется* в программировании а вовсе не является его основой. Раньше программирование применялось исключительно ради математики. Теперь это две очень разные области.
Ну если не хотите продолжать диалог, то жалко. Статья на самом деле мне понравилась, и выражение примитивных операций при помощи функций — довольно интересная для меня тема.
michael_vostrikov
Который раз читаю про это и всегда удивляюсь. Почему для сложения есть простое решение, а для вычитания сложное и на сложение непохожее? Неужели никто не обращает внимание, что это выглядит как костыль?
Если мы вводим функцию +1, почему нельзя ввести функцию -1?
Какие тут преимущества, если банальную параболу нельзя построить? Кстати, а что насчет дробных чисел?
ibessonov
Операция "+1" вводится для натуральных чисел аксиоматически, а вот для реализации "-1" нужно перебирать числа, начиная с нуля, пока не найдём подходящее. Так уж числа устроены. Введение "-1" в аксиоматику избыточно и только бы всё усложнило.
Не совсем понимаю, причём тут парабола. Кодировались неотрицательные целые числа. Если нужны числа со знаком, можно и для них структуру данных создать, например пара
(знак, модуль). Дроби тоже кодируются парой(числитель, знаменатель).Как было сказано в начале статьи, всегда в распоряжении есть булевы значения и кортежи любой длины, хоть IEEE 754 реализуй, никаких ограничений!
michael_vostrikov
Мы же не перебираем все числа до миллиона при вычислении выражения 1000000 — 1. Мы пользуемся правилами вычисления.
В примере с натуральными числами они не были реализованы через кортеж битов. Потому и возник вопрос про аналогичное построение отрицательных а заодно и дробных чисел. Потому что никаких преимуществ в отсутствии отрицательных чисел нет.
ibessonov
Преимущества есть в том, что перед нулём находится ноль, это позволяет легко определить операции сравнения. Реализация
Lte, например, именно этим фактом и пользуется.Касательно 1000000-1 — в теории (в арифметике Пеано) вычисление происходит именно перебором чисел от 0 до 999999. На практике же мы используем более продвинутые инструменты.
michael_vostrikov
А, то есть если мне понадобятся отрицательные числа, то у меня еще и функция Lte сломается)
Как я понял, в арифметике Пеано и нет отрицательных чисел, она только про возрастающие положительные. Но если идет разговор о красоте и мощности функционального исчисления, значит в нем должны быть средства реализовать такие простые вещи.
ibessonov
Lte рассчитана на целые неотрицательные числа, для сравнения знаковых целых понадобится другая функция.
Средства есть, числа со знаком реализуются в виде пар. Неплохое объяснение есть в википедии: https://en.wikipedia.org/wiki/Church_encoding#Signed_numbers
Вам стоит понять, что, как и в школьной арифметике, в первую очередь вводятся натуральные числа, а уже потом на их основании целые и рациональные. И это вовсе не говорит о каких-то проблемах в лямбда-исчислении.
michael_vostrikov
Ок. То есть, я правильно понял, там есть отрицательные числа, но в операциях с ними все равно поиск предыдущего используется?
Но ведь, если ввести -1, то все вычисления станут проще, разве нет?
ibessonov
Числа изначально вводятся через понятие количества, или длины цепочки вызовов. Это наиболее естественный способ, не подразумевающий под собой наличие константы "-1". Те же числа потом и используются похожим образом — индекс в списке, длина списка, длина подпоследовательности… Наличие знака при этом было бы избыточным и ничего бы не упростило.
Вы верно поняли, описанное представление чисел со знаком всё равно требует трудоёмких операций поиска соседнего числа. Я представляю себе только один способ избавиться от этого — кодировать числа в позиционной системе счисления. Но подобная тема по своему объёму сама заслуживает отдельной статьи.
К вопросу о том, станут ли вычисления проще — если вычисления требуют отрицательных чисел, то мы можем и должны их предоставить. Не знаю, что тут ещё можно добавить.
michael_vostrikov
Почему избыточным, если они нам нужны и мы все равно вводим их через пары? Я бы даже сказал, имитируем. Причем вводим при этом две дополнительные константы для знаков вместо одной операции.
ibessonov
Избыточным потому, что за всю статью отрицательные числа ни разу не пригодились, а если многое можно сделать без них, то есть смысл иметь беззнаковые числа.
Sirikid
В данном случае важнее то, что о таких числах удобно рассуждать с точки зрения логики, а не алгоритмическая сложность вычитания.
michael_vostrikov
Я не столько про алгоритмическую сложность, сколько про сам подход. Сложение сделано так, а обратная операция абсолютно по-другому. Нелогично.
Sirikid
Все потому что числа у нас натуральные, а вычитание для них не замкнуто.
michael_vostrikov
Вот я и говорю, зачем нам только натуральные. Можно же и дополнительные множества определить, и вычитание нормально сделать. Неужели в функциональном программировании нет такого способа?
Sirikid
Покажите как.
michael_vostrikov
Не знаю, потому и спросил) Если б знал, сразу бы написал. Просто то, что есть сейчас, не выглядит логичным, значит теоретически есть возможность сделать лучше.
Sirikid
Доказать это утверждение вы можете только одним способом — предложить своё решение.