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

104

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

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

let rec foo ... = ...

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

nsantorello
источник
См. Также stackoverflow.com/questions/3739628/…
Брайан

Ответы:

87

Французские и британские потомки оригинального 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.

JD
источник
3
Я не думаю, что это отвлекающий маневр: если бы не ограничения на вывод, вполне вероятно, что целые программы или модули автоматически обрабатывались бы как взаимно рекурсивные, как это делают большинство других языков. Это сделало бы конкретное дизайнерское решение о том, требуется ли «rec», спорным.
GS - извиняюсь перед Моникой
«... автоматически рассматривается как взаимно рекурсивный, как и в большинстве других языков». BASIC, C, C ++, Clojure, Erlang, F #, Factor, Forth, Fortran, Groovy, OCaml, Pascal, Smalltalk и Standard ML - нет.
JD
3
C / C ++ требует только прототипов для прямых определений, что на самом деле не связано с явной маркировкой рекурсии. Java, C # и Perl определенно имеют неявную рекурсию. Мы могли бы вести бесконечные дебаты о значении слова «большинство» и важности каждого языка, поэтому давайте просто остановимся на «очень многих» других языках.
GS - Извинитесь перед Моникой
3
«C / C ++ требует прототипов только для прямых определений, что на самом деле не касается явной маркировки рекурсии». Только в частном случае саморекурсии. В общем случае взаимной рекурсии форвардные объявления являются обязательными как в C, так и в C ++.
JD
2
На самом деле форвардные объявления не требуются в C ++ в областях действия класса, т.е. статические методы могут вызывать друг друга без каких-либо объявлений.
polkovnikov.ph
52

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

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

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

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

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

GS - Извинитесь перед Моникой
источник
3
Эээ нет. Ваш первый абзац неверен (вы говорите о явном использовании «and», а не «rec») и, следовательно, остальное не имеет значения.
JD
5
Меня это требование никогда не устраивало. Спасибо за объяснение. Еще одна причина, почему Haskell превосходит дизайн.
Бент Расмуссен,
9
НЕТ !!!! КАК ЭТО МОГЛО СЛУЧИТЬСЯ?! Это совершенно неверный ответ! Пожалуйста, прочтите ответ Харропа ниже или ознакомьтесь с Определением стандартного
машинного обучения
9
Как я сказал в своем ответе, проблема вывода типа является одной из причин необходимости rec, а не единственной причиной. Ответ Джона также является очень правильным ответом (кроме обычного ехидного комментария о Haskell); Я не думаю, что эти двое противостоят.
GS - Извинитесь перед Моникой
16
«проблема вывода типа - одна из причин необходимости rec». Тот факт, что OCaml требует, recа SML - нет, является очевидным противоположным примером. Если бы вывод типа был проблемой по причинам, которые вы описываете, OCaml и SML не могли бы выбрать другие решения, как они. Причина, конечно, в том, что вы говорите о том and, чтобы сделать Haskell актуальным.
JD
10

Это хорошая идея по двум причинам:

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

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

zrr
источник
4

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

  • letиспользуется не только для привязки функций, но и других обычных значений. Большинство форм значений не могут быть рекурсивными. Разрешены определенные формы рекурсивных значений (например, функции, ленивые выражения и т. Д.), Поэтому для обозначения этого требуется явный синтаксис.
  • Может быть проще оптимизировать нерекурсивные функции
  • Замыкание, создаваемое при создании рекурсивной функции, должно включать в себя запись, указывающую на саму функцию (чтобы функция могла рекурсивно вызывать себя), что делает рекурсивные замыкания более сложными, чем нерекурсивные замыкания. Так что было бы неплохо иметь возможность создавать более простые нерекурсивные закрытия, когда вам не нужна рекурсия.
  • Он позволяет вам определять функцию в терминах ранее определенной функции или значения с тем же именем; хотя я считаю это плохой практикой
  • Дополнительная безопасность? Убедитесь, что вы делаете то, что планировали. например, если вы не хотите, чтобы он был рекурсивным, но вы случайно использовали имя внутри функции с тем же именем, что и сама функция, он, скорее всего, будет жаловаться (если имя не было определено ранее)
  • Эта letконструкция аналогична letконструкции в Lisp и Scheme; которые не рекурсивны. В letrecScheme есть отдельная конструкция для рекурсивного let
newacct
источник
«Большинство форм значений не могут быть рекурсивными. Разрешены определенные формы рекурсивных значений (например, функции, ленивые выражения и т. Д.), Поэтому для обозначения этого требуется явный синтаксис». Это верно для F #, но я не уверен, насколько это верно для OCaml, где вы можете это сделать let rec xs = 0::ys and ys = 1::xs.
JD
4

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

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 варианты.

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

Джеймс Вудятт
источник
1

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

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

Эван Мигер
источник