Lambda Calculus (Лямбда исчисление) в Javascript?
Перевод статьи Michele Riva Lambda Calculus in JavaScript?
Lambda Calculus (Лямбда-исчисление) – это формальная система математической логики, введенная Алонзо Черчем в 1930-х годах. В настоящее время ему уделяется все больше и больше внимания благодаря росту парадигмы функционального программирования в растущем числе языков (Scala, ReasonML и т. д.), И знаете что? Функциональное программирование основано на лямбда-исчислении.
Итак, чтобы понять, что такое функциональное программирование, давайте посмотрим, как выглядит Lambda Calculus… но в JavaScript!
Почему JavaScript?
Знаете ли вы, что JS был создан с целью внедрения языка программирования Scheme (Scheme Programming Language) в веб-браузер Netscape Navigator? И угадай что! Схема (Scheme) – это функциональный язык! Так что у JS все еще есть некоторые функциональные возможности программирования, которые очень нам помогут в нашей повседневной работе!
Начнем
Как написано выше, Lambda Calculus является формальной системой для выражения вычислений, и она основана на концепции выражения и составления функций. Выражение может быть переменной, абстракцией или функции. Чтобы быть более понятным, мы можем обобщить эти три концепции следующим образом:
Переменаня (Variable)
Переменная – это выражение, которое оценивается как значение:
const x;
его аналог в Lambda Calculus:
x
Абстракция (Abstraction)
Абстракция – это выражение, которое оценивает анонимную функцию:
x => x;
Его аналогом является:
λx.x
Как видите, греческая лямбда (λ) представляет «объявление функции», x это первый аргумент и все после . это просто тело функции.
Давайте посмотрим на другой пример:
λx.x²
В приведенном выше примере мы просто возвращаем квадрат переменной x, и все довольно просто!
Как бы вы реализовали это в JavaScript?
x => x ** 2
Ооочень просто! Но что, если мы хотим применить переменную к этой функции? Давайте узнаем больше о Function Application (аппликации).
Function Application
Мы говорим о Function Application, когда пишем выражение, которое применяет значение к функции (то есть запускаем функцию):
(x => x)(10)
и в Lambda Calculus:
λx.x 10
Давайте попробуем применить эту концепцию аппликации к примеру выше, где мы возвращаем квадрат данной числовой переменной:
(λx.x²) (y)
Супер! В этом примере y может быть любым числовым значением, и мы применяем его к функции λx.x². Но как мы можем это реализовать в JavaScript?
(x => x ** 2)(y)
Итак, в чем разница между абстракцией (Abstraction) и аппликации (Application)?
Следующий код представляет абстракцию (Abstraction), потому что мы просто определяем функцию, не применяя к ней какого-либо значения:
const SQUARE = x => x ** 2
И следующий пример – это Аппликация (Application), потому что мы применяем x к SQUARE Abstraction:
SQUARE(x)
Почему важно понимать эти три маленьких понятия? Потому что они – основа Lambda Calculus, а любое другое выражение – просто абстракция над ними!
Каррирование (Currying)
Функции в Lambda Calculus должны иметь только один аргумент. Давайте представим, что нам нужно вычислить простую сумму из двух целых чисел … что невозможно сделать, передав только один аргумент! Здесь приходит понятие карринга (Currying). То есть преобразование функции от многих аргументов в набор функций, каждая из которых является функцией от одного аргумента.
const SUM = (x, y) => x + y;
Просто чтобы быть ясно, решение выше не будет работать в Lambda Calculus, потому что функция SUM получает два аргумента. Но как насчет этого?
const SUM = x => y => x + y;
Вместо того, чтобы возвращать сумму заданных аргументов x и y, мы создаем функцию SUM, которая принимает x и возвращает анонимную функцию, которая принимает y в качестве единственного аргумента. Эта анонимная функция вернет сумму x и y. Как вы уже догадались, мы только что написали абстракцию SUM, поэтому давайте посмотрим на ее применение (Application):
SUM(5)(10); // => 15
Эта техника называется карривание (Currying) и была введена математиком Хаскеллом Карри (Haskell Curry).
Итак, как бы мы вычислили сумму двух целых чисел в Lambda Calculus?
Довольно просто:
λx.(λy.x + y)
Типы
В Lambda Calculus функция является единственным примитивным типом данных. Но мы все еще можем вводить определенные типы, записывая их выражения в чистом Lambda Calculus! Давайте возьмем Boolean в качестве примера:
λx.(λy.x) // TRUE λx.(λy.y) // FALSE
Что тут происходит? Мы можем думать о булевой логике как о выборе значения ИСТИНА (TRUE) или ЛОЖЬ (FALSE).
Итак, мы объявляем функцию, которая принимает TRUE в качестве аргумента и возвращает функцию, которая принимает FALSE в качестве аргумента. Затем мы решаем, должно ли возвращаемое значение быть ИСТИНА или ЛОЖЬ.
В JavaScript:
const TRUE = x => y => x; const FALSE = x => y => y;
Теперь мы задали условие, которое решает, является ли значение ИСТИНА или ЛОЖЬ.
Мы можем использовать структуру if / then / else следующим образом:
λz.(λx.(λy. z x y))
Аналог в JavaScript:
const IF = COND => THEN => ELSE => COND(THEN)(ELSE);
Это только базовый пример, но вы можете видеть, как Lambda Calculus может быть действительно модульным и может позволить нам строить сложные управляющие структуры всего за несколько строк!
Зачем нужно Lambda Calculus
Мы просто слегка коснулись Lambda Calculus. Его изучение позволит вам понять, как справляться с повседневными проблемами функционального программирования, а также поможет по новому взглянут на них.
Современные языки программирования (включая JavaScript) становятся все более и более сложными, но все они могут быть сведены к Lambda Calculus.
После 80 лет эта математическая запись все еще достаточно мощна, чтобы справляться с повседневными проблемами.
Если вы хотите узнать больше о Lambda Calculus, я бы порекомендовал это потрясающее видео от Грэма Хаттона:
и если вы хотите обучить своим знаниям и навыкам Lambda Calculus, я бы порекомендовал вам HackerRank, где вы можете найти множество проблем и получить помощь от других разработчиков.