Почему функции в Ocaml / F # не являются рекурсивными по умолчанию?

Question

Почему функции в F # и Ocaml (и, возможно, других языках) по умолчанию не являются рекурсивными?

Другими словами, почему разработчики языка решили, что было бы неплохо явно сделать так, чтобы вы печатали rec в объявлении вроде:

let rec foo ... = ...

а не дают ли функции рекурсивную возможность по умолчанию? Зачем нужна явная конструкция rec?

Answer 1

Французские и британские потомки оригинального ML сделали различные выборы, и их выбор был унаследован в течение десятилетий к современным вариантам. Так что это просто наследие, но оно влияет на идиомы в этих языках.

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

Например, замена функции p при вычислении энтропии Шеннона последовательности в OCaml:

let shannon fold p =
  let p x = p x *. log(p x) /. log 2.0 in
  let p t x = t +. p x in
  -. fold p 0.0

Обратите внимание, как аргумент p функции высшего порядка shannon заменяется другим p в первой строке тела и затем другим p во второй строке тела.

И наоборот, британская ветвь SML семейства языков ML выбрала другой вариант, и функции SML, связанные с fun, по умолчанию рекурсивны. Когда большинству определений функций не требуется доступ к предыдущим привязкам их имен функций, это приводит к упрощению кода. Однако в заменяемых функциях используются разные имена (f1, f2 и т. Д.), Что загрязняет область действия и позволяет случайно вызвать неправильную «версию» функции. И теперь существует несоответствие между неявно-рекурсивными fun -связанными функциями и нерекурсивными val -связанными функциями.

Haskell позволяет вывести зависимости между определениями, ограничивая их чистотой. Это делает образцы игрушек более простыми, но в других местах это обходится дорого.

Обратите внимание, что ответы, данные Ганешем и Эдди, - это красная сельдь. Они объяснили, почему группы функций нельзя поместить в гигантский let rec ... and ..., потому что это влияет на то, когда переменные типа обобщаются. Это не имеет ничего общего с rec по умолчанию в SML, но не с OCaml.

Answer 2

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

Если у вас есть определение let f x = x, вы ожидаете, что оно будет иметь тип 'a -> 'a и будет применимо к различным 'a типам в разных точках. Но в равной степени, если вы напишите let g x = (x + 1) + ..., вы ожидаете, что x будет рассматриваться как int в остальной части тела g.

Способ, которым вывод Хиндли-Милнера имеет дело с этим различием, заключается в явном обобщении шаге. В определенные моменты при обработке вашей программы система типов останавливается и говорит: «Хорошо, типы этих определений будут обобщены на этом этапе, поэтому, когда кто-то их использует, любые переменные свободного типа в их типе будут freshly , и, следовательно, не будет мешать любому другому использованию этого определения. "

Оказывается, разумным местом для этого обобщения является проверка взаимно рекурсивного набора функций. Раньше, и вы будете обобщать слишком много, что приведет к ситуациям, когда типы могут фактически сталкиваться. Позже, и вы будете слишком мало обобщать, делая определения, которые нельзя использовать с множественными экземплярами типов.

Итак, учитывая, что средство проверки типов должно знать, какие наборы определений являются взаимно рекурсивными, что оно может делать? Одна из возможностей - просто провести анализ зависимостей для всех определений в области и переупорядочить их в наименьшие возможные группы. Haskell на самом деле делает это, но в таких языках, как F # (и OCaml и SML), которые имеют неограниченные побочные эффекты, это плохая идея, потому что это может также изменить порядок побочных эффектов. Поэтому вместо этого он просит пользователя явно пометить, какие определения являются взаимно рекурсивными, и, следовательно, путем расширения, где должно произойти обобщение.

Answer 3

Есть две основные причины, по которым это хорошая идея:

Во-первых, если вы включите рекурсивные определения, вы не сможете ссылаться на предыдущую привязку значения с тем же именем. Это часто полезная идиома, когда вы делаете что-то вроде расширения существующего модуля.

Во-вторых, рекурсивные значения, и особенно наборы взаимно рекурсивных значений, гораздо сложнее рассуждать, чем определения, которые идут по порядку, каждое новое определение строится поверх того, что уже было определено. При чтении такого кода полезно иметь гарантию, что, за исключением определений, явно помеченных как рекурсивные, новые определения могут ссылаться только на предыдущие определения.

Answer 4

Некоторые догадки:

• let используется не только для привязки функций, но и для других обычных значений. Большинство форм значений не могут быть рекурсивными. Разрешены определенные формы рекурсивных значений (например, функции, ленивые выражения и т. Д.), Поэтому для указания этого необходим явный синтаксис.
• Может быть проще оптимизировать нерекурсивные функции
• Замыкание, созданное при создании рекурсивной функции, должно включать запись, которая указывает на саму функцию (чтобы функция могла рекурсивно вызывать себя), что делает рекурсивные замыкания более сложными, чем нерекурсивные замыкания. Поэтому было бы неплохо иметь возможность создавать более простые нерекурсивные замыкания, когда вам не нужна рекурсия
• Позволяет определить функцию в терминах ранее определенной функции или значения с тем же именем; хотя я думаю, что это плохая практика
• Дополнительная безопасность? Уверен, что вы делаете то, что вы хотели. например Если вы не хотите, чтобы оно было рекурсивным, но вы случайно использовали имя внутри функции с тем же именем, что и сама функция, скорее всего, он будет жаловаться (если имя не было определено ранее)
• Конструкция let аналогична конструкции let в Лиспе и Схеме; которые не являются рекурсивными. В Схеме есть отдельная конструкция letrec для рекурсивного давайте

Answer 5

Учитывая это:

let f x = ... and g y = ...;;

Для сравнения:

let f a = f (g a)

С этим:

let rec f a = f (g a)

Первый переопределяет f, чтобы применить ранее определенный f к результату применения g к a. Последний переопределяет f для цикла навсегда, применяя g к a, что обычно не то, что вы хотите в вариантах ML.

Тем не менее, это вещь в стиле дизайнера языков. Просто иди с ним.

Answer 6

Большая часть этого в том, что он дает программисту больше контроля над сложностью их локальных областей. Спектр let, let* и let rec предлагает увеличивающийся уровень как мощности, так и стоимости. let* и let rec по сути являются вложенными версиями простого let, поэтому использование любого из них обходится дороже. Эта оценка позволяет вам микроуправлять оптимизацией вашей программы, так как вы можете выбрать, какой уровень разрешения вам нужен для выполнения поставленной задачи. Если вам не нужна рекурсия или возможность ссылаться на предыдущие привязки, то вы можете воспользоваться простым разрешением, чтобы сэкономить немного производительности.

Это похоже на предикаты градуированного равенства в Схеме. (т.е. eq?, eqv? и equal?)