Почему ключевое слово rec необходимо в F #?

28

В F # необходимо использовать recключевое слово. В Haskell нет необходимости явно указывать, является ли данная функция рекурсивной или нет.

Учитывая роль рекурсии в функциональном программировании, дизайн F # кажется мне довольно странным. Это хорошее решение для разработки языка или оно существует только по историческим причинам или из-за ограничений реализации?

Саймон Бергот
источник

Ответы:

16

В семантике Haskell и F # есть существенное различие. В Haskell вызов функции не выполняет никаких реальных вычислений, но выделяет объект кучи, известный как «thunk». Для thunk совершенно нормально иметь ссылку на себя или другой thunk. Однако в F # вызов функции - это фактический вызов, делающий выражения как let x = 1 : 2 : x in xнедопустимые - как это требуется xдля построения перед 1 : 2 : xсозданием. Тем не менее, это все еще более или менее разумное определение для бесконечного списка, какой-то способ определить его должен существовать. Здесь кроются корни rec. Если вы хотите больше, ищите и читайте операционную семантику для SML и Haskell - это другое.

permeakra
источник
2
AFAIK, Haskell целенаправленно не имеет операционной семантики.
dan_waterworth
@dan_waterworth невозможно скомпилировать без определенной операционной семантики.
Permeakra
8
Язык Haskell не определяет операционную семантику, но вместо этого предоставляет денотационную семантику. Когда вы создаете компилятор, операционная семантика неявно определяется, но это не означает, что она является частью стандарта языка Haskell.
dan_waterworth
6
@dan_waterworth На практике существует только одна реализация и стандарт языка Haskell: ghc, а также существует только один стандарт F #: его реализация Microsoft. Так что теоретически вы можете быть правы, но на практике это совершенно другой зверь.
Permeakra
19

На этот вопрос ответили на SO , и он включает в себя некоторые серьезные исторические предпосылки для того, почему используется «rec».

Вот важная цитата для потомков:

Функции не являются рекурсивными по умолчанию во французском семействе языков CAML (включая OCaml). Этот выбор позволяет легко заменить определения функций (и переменных), используя let в этих языках, потому что вы можете ссылаться на предыдущее определение внутри тела нового определения. F # унаследовал этот синтаксис от OCaml.

Крис Питман
источник
12

Рекурсив letопределяет значительно более сложную семантику, чем нормальная. Поэтому, для простоты и ясности языкового дизайна, есть веская причина иметь и то, и другое, как разделение let, так let*и letrecв Scheme.

Простое let x = y in zэквивалентно ((fun x -> z) y). Рекурсивное let намного сложнее и может включать использование комбинатора с фиксированной точкой.

SK-логика
источник