Минималистичный язык высшего порядка называется лямбда-исчислением. Это простая математическая нотация для размышлений о функциях, созданная Алонзо Черчем в 1929 году. В те времена её ещё не называли языком программирования, так как компьютеров не существовало. Однако вскоре Алан Тьюринг показал эквивалентность его работы и Тьюринг-машины: любую функцию из лямбда-исчисления можно реализовать на машине Тьюринга, и наоборот. В основе всего функционального программирования — таких языков как Haskell, Scheme, ML, JavaScript, Python, Ruby и даже Java — лежат всего три типа выражений: ссылки на переменные, анонимные функции и вызовы этих функций. Анонимные функции пишутся через нотацию «лямбда-точка», где (λ v . e) принимает аргумент v и возвращает значение e. Вызов функции выполняется просто соседним стоянием выражений (f e), что в привычном виде выглядит как f(e). Программа может возвращать аргумент без изменений или применять функцию к самой себе, что приводит к бесконечной петле.
Как же такой язык становится всеобщим? Секрет в двух хитростях: церковных кодировках и Y-комбинаторе, позволяющих реализовать числа, булевы значения и условия без специальной поддержки. Ламбда-исчисление не поддерживает рекурсию или итерацию явно, но достигает Тьюринг-полноты через эти трюки. Чтобы понять суть, можно написать собственный интерпретатор всего за семь строк на Scheme. Функция eval принимает выражение и окружение, возвращая значение, а apply применяет функцию к аргументу. Окружение представляет собой таблицу, связывающую переменные со значениями, а замыкание (closure) кодирует пару функции и её окружения. В языке Racket, который предоставляет мощные возможности для паттерн-матчинга, интерпретатор получается чище и понятнее. Он обрабатывает аргументы, вызывает функции и работает с замыканиями.
Такой подход масштабируется. Всего на сотню строк кода можно реализовать интерпретатор для значительной части самого Scheme. К базовому языку добавляют переменные, числа, булевы константы, примитивные операции вроде сложения, условные переходы через if, блоки let и letrec для рекурсии, а также мутацию переменных через set!. Финальный код включает тесты: функция eval-program преобразует верхнеуровневый код в выражение letrec и запускает его. Это позволяет быстро тестировать новые идеи для языков программирования, разделяя синтаксический дизайн от семантического.