Javascript: Числа Чёрча

JS: Функциональное программирование 57 сообщений
Обновлено: 05 янв., 17:27
2039
Студентов
63%
Завершения

В 30-х годах прошлого века перед математиками встала так называемая проблема разрешения (Entscheidungsproblem), сформулированная Давидом Гильбертом. Суть её в том, что вот есть у нас некий формальный язык, на котором можно написать какое-либо утверждение. Существует ли алгоритм, за конечное число шагов определяющий его истинность или ложность? Ответ был найден двумя великими учёными того времени Алонзо Чёрчем и Аланом Тьюрингом. Они показали (первый — с помощью изобретённого им λ-исчисления, а второй — теории машины Тьюринга), что для арифметики такого алгоритма не существует в принципе, т.е. Entscheidungsproblem в общем случае неразрешима.

Так лямбда-исчисление впервые громко заявило о себе, но ещё пару десятков лет продолжало быть достоянием математической логики. Пока в середине 60-х Питер Ландин не отметил, что сложный язык программирования проще изучать, сформулировав его ядро в виде небольшого базового исчисления, выражающего самые существенные механизмы языка и дополненного набором удобных производных форм, поведение которых можно выразить путем перевода на язык базового исчисления. В качестве такой основы Ландин использовал лямбда-исчисление Чёрча. И всё заверте…

В основе лямбда-исчисления лежит понятие, известное ныне каждому программисту, — анонимная функция. В нём нет встроенных констант, элементарных операторов, чисел, арифметических операций, условных выражений, циклов и т. п. — только функции, только хардкор. Потому что лямбда-исчисление — это не язык программирования, а формальный аппарат, способный определить в своих терминах любую языковую конструкцию или алгоритм. В этом смысле оно созвучно машине Тьюринга, только соответствует функциональной парадигме, а не императивной.

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

Натуральные числа, реализованные посредством лямбда-исчисления, называются числами Чёрча и являются отличной разминкой для мозга. В основе реализации по-прежнему будут лежать функции, ведущие себя в заданном контексте подобно единице, двойке и т.д. Собственно, это одна из особенностей лямбда-исчисления: сущности, записанные в его терминах, не обладают самодостаточностью, поскольку воплощают поведение того или иного объекта.

Источник

P.S. Вероятно, это задание не решить без чтения статей по лямбда-исчислению, но поверьте, оно того стоит.

numerals.js

Реализуйте алгоритм числа Zero() и операции Succ() (увеличение числа на единицу) в соответствии с арифметикой Чёрча. Не забудьте про экспорт.

Пример:

const two = Succ(Succ(Zero));

// Немного хитрый способ трансформировать число Чёрча в обычное представление.
// Откровенно говоря, устройство самих чисел еще хитрее ;)
two(x => x + 1)(0); // 2

const four = Succ(Succ(two));
four(x => x + 1)(0); // 4

Для полного доступа к испытанию нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
900
упражнений
2000+
часов теории
3200
тестов

Впечатления

Хорошее задание.\ Окунулся с головой в эти статьи. Но это все как-будто совершенно другая область. Сложно, блин.

Хекслет не перестает радовать. Спасибо за перевороты в сознании :]