Это зависит от того, что вы подразумеваете под минимальным.
Для начала, предком функциональных языков является, прежде всего, математическая логика . Вычислительное использование определенных логик последовало за фактом. В некотором смысле многие математические системы (ядра которых обычно весьма минимальны) можно назвать функциональными языками. Но я сомневаюсь, что это то, что вы ищете!
Самым известным является Церковь Алонзо Лямбда-исчисление , из которых есть варианты и потомки:
Самая простая форма - это то, что называется нетипизированное лямбда-исчисление ; это не содержит ничего, кроме лямбда-абстракций, без ограничений на их использование. Создание структур данных с использованием только анонимных функций выполняется с помощью так называемой церковной кодировки и представляет данные с помощью фундаментальных операций над ними; число 5 становится «повторить что-то 5 раз» и т. д.
Языки семейства Lisp - это не что иное, как нетипизированное лямбда-исчисление, дополненное атомарными значениями, cons-ячейками и несколькими другими вещами. Я подозреваю, что Схема - самый минималистичный здесь, как будто память служит мне, она была сначала создана как язык обучения.
Первоначальная цель лямбда-исчисления, то есть описание логических доказательств, потерпела неудачу, когда было показано, что нетипизированная форма является непоследовательной, что является вежливым термином для «позволяет доказать, что ложь истинна». ( Исторические мелочи: документ, доказывающий это, что было значительным в то время, сделал это, написав логическое доказательство того, что в вычислительном отношении пошел в бесконечный цикл. ) В любом случае, использование в качестве логика была восстановлена введением типизированного лямбда-исчисления . Однако они, как правило, не могут быть непосредственно полезны в качестве языков программирования, тем более что логически обоснованный делает язык неполным по Тьюрингу.
Однако, подобно тому, как Лиспс выводится из нетипизированного лямбда-исчисления, типизированное лямбда-исчисление, расширенное за счет встроенной рекурсии, алгебраических типов данных и нескольких других вещей, дает вам расширенное семейство языков ML. Они имеют тенденцию быть довольно минимальными
в глубине души, с синтаксическими конструкциями, имеющими прямые переводы к лямбда-терминам во многих случаях. Помимо очевидных диалектов ML, это также включает в себя Haskell и несколько других языков. Однако я не знаю каких-либо особенно минималистичных типизированных функциональных языков; такой язык, скорее всего, будет страдать от плохого удобства использования гораздо хуже, чем минималистский нетипизированный язык.
Итак, что касается вариантов лямбда-исчисления, чистое нетипизированное лямбда-исчисление без каких-либо дополнительных функций является полным по Тьюрингу и настолько минимальным, насколько вы можете получить!
Однако, возможно, более минимальным является полное исключение понятия «переменные» - фактически, это было первоначально сделано для упрощения метаматематических доказательств о логических системах, если память мне служит, - и использования только функций высшего порядка. называется комбинаторы . Здесь мы имеем:
Сама комбинационная логика , изначально изобретенная Moses Schönfinkel и развитая Haskell Curry . Каждый комбинатор определяется простым правилом подстановки, например Sxyz = xz(yz)
. Строчные буквы используются как переменные в этом определении, но имейте в виду, что сама комбинаторная логика не использует переменные или присваивает имена чему-либо вообще. Конечно, комбинаторная логика минимальна, но не слишком дружелюбна, как язык программирования. Самым известным является комбинаторное основание SK . S определяется как в примере выше; К Kxy = x
. Этих двух комбинаторов достаточно, чтобы сделать его полным по Тьюрингу! Это почти пугающе минимально.
Unlambda - язык, основанный на комбинаторах SK, расширяющий его несколькими дополнительными комбинаторами со специальными свойствами. Менее минимальный, но позволяет писать «Hello World».
Даже два комбинатора - это больше, чем нужно.Существуют различные однокомбинаторные базы;пожалуй, самым известным является iota Combinator , определяемый как ιx = xSK
, который используется на минималистском языке, также называемом Iota
ТакжеСледует отметить Lazy K , который отличается от Unlambda тем, что не вводит дополнительных комбинаторов, не имеет побочных эффектов и использует ленивую оценку.По сути, это Хаскель из мира эзотерических языков на основе комбинаторов.Он поддерживает как базу SK, так и комбинатор йоты.
Какой из этих вариантов вы считаете наиболее «минимальным», вероятно, дело вкуса.