лямбда-исчисление

Статья

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

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

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

Статья

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

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

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

Статья

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

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

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

Статья

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

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

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

Статья

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

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

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

Статья

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

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

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

Статья

Продолжения и CPS: откуда взялись колбэки, генераторы и async/await

Одно преобразование лямбда-термов, из которого выросли колбэки, промисы, обработка исключений, генераторы и async/await: что такое продолжение, как работает …

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

Статья

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

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

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

Статья

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

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

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

Статья