Lambda Calculus (Лямбда исчисление) в Javascript?

Spread the love

Перевод статьи 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, где вы можете найти множество проблем и получить помощь от других разработчиков.


Spread the love

Добавить комментарий

Ваш e-mail не будет опубликован.