Тема: Лямбда-Исчисление

Статья

Числа Чёрча: арифметика без чисел

Как из одних только функций получаются натуральные числа, сложение, умножение, степень и коварный предшественник — с полной раскруткой каждой редукции и рабочим кодом на …

#лямбда-исчисление#кодирование Чёрча#функциональное программирование

Статья

Типизированное лямбда-исчисление и соответствие Карри-Ховарда

Что происходит, когда к лямбда-исчислению приделывают типы: часть программ перестаёт компилироваться, зато оставшиеся гарантированно завершаются — и внезапно оказывается, …

#лямбда-исчисление#типы#функциональное программирование

Статья

Теория вычислимости: машина Тьюринга, лямбда-исчисление, проблема остановки

Что значит «вычислимо»: машина Тьюринга со строгим определением и работающим симулятором, лямбда-исчисление с нумералами Чёрча и комбинатором неподвижной точки, тезис …

#математика#вычислимость#машина тьюринга

Статья

Стратегии вычисления: нормальный порядок, аппликативный, ленивость

Почему одно и то же лямбда-выражение может завершиться или зациклиться в зависимости от того, какой редекс вы сократили первым — и как из этого выросли строгие языки, …

#лямбда-исчисление#функциональное программирование#ленивые вычисления

Статья

Свободные и связанные переменные, подстановка и захват имён

Разбираем, чем переменная-параметр отличается от переменной из внешнего мира, как правильно подставлять выражение вместо переменной и почему наивная замена букв ломает …

#лямбда-исчисление#функциональное программирование#замыкания

Статья

Рекурсия без имён: комбинатор неподвижной точки Y

Как написать факториал в языке, где у функций нет имён: приём открытой рекурсии, вывод комбинатора Y с полной раскруткой редукций, его боевой вариант Z для JavaScript и …

#лямбда-исчисление#рекурсия#комбинаторы

Статья

Пары, списки и структуры данных из одних лямбд

Как построить кортеж, запись и связный список, когда в языке есть только функции: пара Чёрча, два способа кодировать списки, полные раскрутки редукций и рабочий код на …

#лямбда-исчисление#структуры данных#функциональное программирование

Статья

Нотация: переменная, абстракция, аппликация и как читать выражения

Весь синтаксис лямбда-исчисления — три конструкции и два соглашения о скобках; учимся читать выражения вслух и переводить их в стрелочные функции JavaScript и Python.

#лямбда-исчисление#синтаксис#функциональное программирование

Статья

Лямбда-исчисление Чёрча: зачем оно программисту и что это вообще такое

Язык программирования из трёх правил, придуманный до появления компьютеров: зачем он нужен практикующему разработчику и как читать первые редукции.

#лямбда-исчисление#функциональное программирование#теория вычислений

Статья

Лямбда-исчисление в живых языках: от Lisp до современных стрелочных функций

Где именно лямбда-исчисление живёт в языках, на которых вы пишете каждый день: стрелочные функции как абстракции, вызов как бета-редекс, let как сахар, замыкания как …

#лямбда-исчисление#функциональное программирование#компиляторы

Статья

Кодирование Чёрча: истина, ложь и условия из одних функций

В лямбда-исчислении нет true, false и if — и они не нужны: булево значение оказывается функцией выбора из двух аргументов, а весь набор логических операций собирается из …

#лямбда-исчисление#функциональное программирование#логика

Статья

Альфа, бета и эта: три преобразования, из которых всё состоит

Разбираем три правила переписывания лямбда-исчисления — переименование, вызов и упрощение — с полной пошаговой раскруткой редукций и рабочим редуктором на Python и …

#лямбда-исчисление#редукция#функциональное программирование