Какой FP-язык следует за лямбда-исчислением ближе всего?

Question

Какой язык FP следует за лямбда-исчислением, ближайший с точки зрения его кода, выглядящий, чувствующий, действуя как абстракции лямбда-исчисления?

Answer 1

Lambda calculus - очень, очень ограниченная модель программирования. У вас есть только функции. Нет литералов, нет встроенных арифметических операторов, нет структур данных. Все кодируется как функции. Таким образом, большинство функциональных языков пытаются расширить лямбда-исчисление, чтобы сделать его более удобным для повседневного программирования.

Haskell использует современное расширение лямбда-исчисления в качестве основного языка: System F, расширенный с использованием типов данных. (GHC с тех пор расширило это на System Fc, поддерживая равенство равенства типов).

Поскольку все Haskell могут быть написаны непосредственно на его основном языке, а его основной язык является расширением типизированного лямбда-исчисления (в частности, лямбда-исчисления второго порядка), можно сказать, что Хаскелл следует за лямбда-исчислением, по модулю встроенные операторы для параллелизма; параллелизм; и побочные эффекты памяти (и FFI). Это значительно облегчает разработку новых оптимизаторов компилятора, а также позволяет понять семантику данной программы.

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

Единственные люди, к которым это относится: люди, изучающие исчисление лямбда; и компиляторы.

Answer 2

Это может быть не реальный ответ, это скорее догадка о том, что вы на самом деле хотите.

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

Как сказал Дон, Схема очень близка к «равному» нетипизированному лямбда-исчислению, и, вероятно, это очень подходит в вашем случае, если вы проходите через «Маленький Schemer». Если вы действительно хотите использовать «правильный» LC, вам нужно убедиться, что вы используете только только функции (проблемы, как указано выше); но есть некоторые дополнительные проблемы, с которыми вы столкнетесь, особенно когда вы читаете различные другие тексты по этому вопросу. Во-первых, большинство текстов будет использовать ленивую оценку, которую вы не войти в схему. Во-вторых, поскольку LC имеет только унарные функции, очень часто приходится сокращать сроки и использовать, например, λxyz.zxy вместо «реальной» формы, которая в этом случае равна λx.(λy.(λz.((z x) y))) или (lambda (x) (lambda (y) (lambda (z) ((z x) y)))) на схеме. (Это называется Currying.)

Итак, схема очень близка к LC, но это не говорит со всеми этими проблемами. Haskell, возможно, лучший кандидат, так как он ленив и делает такое видение нескольких аргументов для функций. OTOH, вы имеете дело с типизированным языком, который представляет собой довольно большой кусок багажа, чтобы внести в эту игру - и вы столкнетесь с серьезной грязью, если попытаетесь сделать примеры стиля TLS ...

Если вы хотите получить все (ленивы, сокращенные, нетипизированные, достаточно близко к Схеме), то Racket имеет еще один момент для рассмотрения. На высоком уровне он очень близок к Scheme, но он намного продвинулся в том, что вы можете быстро погладить язык, который является ограничением языка Racket, всего лишьвыражениями и функциональными приложениями. С некоторой дополнительной работой вы также можете заставить ее делать карри, и вы даже можете сделать это ленивым. На самом деле это не упражнение, которое вы должны попробовать сделать сами в этот момент - но если это звучит так, как вы хотите, я могу указать вам на my course (ищите «Schlac» в примечаниях к классу), где мы используем язык, который делая все вышеизложенное, и он чрезвычайно ограничен, поэтому вы получаете не что иное, как базовые конструкции LC. (Например, 3 - это несвязанный идентификатор до , который вы определяете.) Обратите внимание, что это не какой-то интерпретатор - он скомпилирован в код Racket, что означает, что он работает достаточно быстро, что вы даже можете писать код, который использует числа. Вы также можете получить реализацию для этого языка, и как только вы установите его, вы получите этот язык, если вы начнете файлы с #lang pl schlac.