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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

То, как вывод Hindley-Milner имеет дело с этим различием, заключается в явном обобщении. В некоторых случаях при обработке вашей программы система типов останавливается и говорит «ok», типы этих определений будут обобщены в этот момент, так что, когда кто-то их использует, любые свободные переменные типа в их типе будут свежее, и, таким образом, не будет мешать другим применениям этого определения ».

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

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

Answer 5

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

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

Answer 6

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

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.

Это говорит о том, что это стиль дизайнерского стиля. Просто иди с ним.