Какой самый минимальный функциональный язык программирования? - PullRequest
32 голосов
/ 06 декабря 2010

Какой самый минимальный функциональный язык программирования?

Ответы [ 5 ]

61 голосов
/ 06 декабря 2010

Это зависит от того, что вы подразумеваете под минимальным.

Для начала, предком функциональных языков является, прежде всего, математическая логика . Вычислительное использование определенных логик последовало за фактом. В некотором смысле многие математические системы (ядра которых обычно весьма минимальны) можно назвать функциональными языками. Но я сомневаюсь, что это то, что вы ищете!

Самым известным является Церковь Алонзо Лямбда-исчисление , из которых есть варианты и потомки:

  • Самая простая форма - это то, что называется нетипизированное лямбда-исчисление ; это не содержит ничего, кроме лямбда-абстракций, без ограничений на их использование. Создание структур данных с использованием только анонимных функций выполняется с помощью так называемой церковной кодировки и представляет данные с помощью фундаментальных операций над ними; число 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, так и комбинатор йоты.

Какой из этих вариантов вы считаете наиболее «минимальным», вероятно, дело вкуса.

7 голосов
/ 06 декабря 2010

Пожалуй, наиболее минимальными функциональными языками являются iota и Jot , потому что они используют только один комбинатор (тогда как unlambda нуждается в двух). Вот краткое объяснение: http://web.archive.org/web/20061105204247/http://ling.ucsd.edu/~barker/Iota/

4 голосов
/ 06 декабря 2010

Я думаю, что самым минимальным функциональным «языком программирования» будет лямбда-исчисление .

1 голос
/ 07 декабря 2017

BrainF * ck - простой и удобный язык программирования. Вот краткое изложение.

Представьте, что у вас есть почти бесконечный диапазон ящиков, каждый из которых пуст. К счастью, вы не одиноки! Вы можете двигаться вперед и назад по линии, складывать вещи в них и вынимать их. Хотя и достаточно простой, но с достаточным количеством времени вы можете делать что угодно: http://www.iwriteiam.nl/Ha_bf_inter.html. Вот команды.

+ | add one to currrent box
- | take one from current box
> | move one box to the right
< | move one box to the left
[] | loop
. | print current value
, | input current value

другие вещи, на которые нужно посмотреть:

P "| упрощенный BF

язык F | более новый упрощенный BF

http://www2.gvsu.edu/miljours/bf.html | классные вещи BF / интро

https://www.esolangs.org/wiki/Language_list | список похожих языков / вариантов

0 голосов
/ 28 ноября 2017

Эзотерический язык программирования (он же esolang) - это язык программирования, разработанный для проверки границ дизайна языка компьютерного программирования, как доказательства концепции, как искусства программного обеспечения, как интерфейса для взлома другого языка (в частности, функционального программирования или процедурного языка программирования) или в шутку.Использование эзотерики отличает эти языки от языков программирования, которые рабочие разработчики используют для написания программного обеспечения.Обычно создатели esolang не предполагают, что язык будет использоваться для массового программирования, хотя некоторые эзотерические функции, такие как визуально-пространственный синтаксис, вдохновили практическое применение в искусстве.Такие языки часто популярны среди хакеров и любителей.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...