Почему функции в F # и Ocaml (и, возможно, в других языках) по умолчанию не рекурсивны?
Другими словами, почему разработчики языка решили, что было бы неплохо явно заставить вас ввести rec
такое объявление, как:
let rec foo ... = ...
и не дать функции рекурсивную возможность по умолчанию? Зачем нужна явная rec
конструкция?
Ответы:
Французские и британские потомки оригинального ML сделали разный выбор, и их выбор на протяжении десятилетий унаследовал современные варианты. Так что это просто наследие, но оно влияет на идиомы в этих языках.
По умолчанию функции не рекурсивны во французском семействе языков CAML (включая OCaml). Этот выбор упрощает замену определений функций (и переменных), используемых
let
на этих языках, поскольку вы можете ссылаться на предыдущее определение внутри тела нового определения. F # унаследовал этот синтаксис от OCaml.Например, замена функции
p
при вычислении энтропии Шеннона последовательности в OCaml:Обратите внимание, как аргумент
p
функции высшего порядкаshannon
заменяется другимp
в первой строке тела, а затем другимp
во второй строке тела.И наоборот, британская ветвь SML семейства языков ML
fun
выбрала другой вариант, и связанные функции SML по умолчанию рекурсивны. Когда большинству определений функций не требуется доступ к предыдущим привязкам их имени функции, это приводит к упрощению кода. Однако замененные функции используют разные имена (f1
иf2
т. Д.), Что загрязняет область видимости и делает возможным случайный вызов неправильной «версии» функции. И теперь существует расхождение между неявно-рекурсивными связаннымиfun
функциями и нерекурсивными связаннымиval
функциями.Haskell позволяет делать выводы о зависимостях между определениями, ограничивая их чистоту. Это делает образцы игрушек более простыми, но в других местах обходится дорого.
Обратите внимание, что ответы Ганеша и Эдди - отвлекающий маневр. Они объяснили, почему группы функций нельзя размещать внутри гиганта,
let rec ... and ...
потому что это влияет на то, когда переменные типа обобщаются. Это не имеет ничего общего с тем,rec
что используется по умолчанию в SML, но не в OCaml.источник
Одна из важнейших причин явного использования
rec
- связана с выводом типа Хиндли-Милнера, который лежит в основе всех языков функционального программирования со статической типизацией (хотя и измененных и расширенных различными способами).Если у вас есть определение
let f x = x
, вы ожидаете, что оно будет иметь тип'a -> 'a
и применимо к разным'a
типам в разных точках. Но в равной степени, если вы напишетеlet g x = (x + 1) + ...
, вы ожидаете, что васx
будут рассматривать как объектint
в остальной части телаg
.Вывод Хиндли-Милнера справляется с этим различием посредством явного шага обобщения . В определенные моменты при обработке вашей программы система типов останавливается и говорит: «Хорошо, типы этих определений будут обобщены на этом этапе, так что, когда кто-то их использует, любые переменные свободного типа в их типе будут заново созданы, и, таким образом, не будет препятствовать любому другому использованию этого определения ".
Оказывается, разумным местом для этого обобщения является проверка взаимно рекурсивного набора функций. Что-нибудь раньше, и вы будете слишком много обобщать, что приведет к ситуациям, когда типы действительно могут столкнуться. Немного позже, и вы слишком мало обобщите, сделав определения, которые нельзя использовать с экземплярами нескольких типов.
Итак, учитывая, что средство проверки типов должно знать, какие наборы определений являются взаимно рекурсивными, что он может сделать? Одна из возможностей - просто провести анализ зависимостей для всех определений в области видимости и переупорядочить их по минимально возможным группам. На самом деле Haskell делает это, но для таких языков, как F # (и OCaml и SML), которые имеют неограниченные побочные эффекты, это плохая идея, потому что это может также изменить порядок побочных эффектов. Поэтому вместо этого он просит пользователя явно отметить, какие определения являются взаимно рекурсивными, и, следовательно, по расширению, где должно произойти обобщение.
источник
rec
а SML - нет, является очевидным противоположным примером. Если бы вывод типа был проблемой по причинам, которые вы описываете, OCaml и SML не могли бы выбрать другие решения, как они. Причина, конечно, в том, что вы говорите о томand
, чтобы сделать Haskell актуальным.Это хорошая идея по двум причинам:
Во-первых, если вы включите рекурсивные определения, вы не сможете ссылаться на предыдущую привязку значения с тем же именем. Часто это полезная идиома, когда вы делаете что-то вроде расширения существующего модуля.
Во-вторых, рекурсивные значения, и особенно наборы взаимно рекурсивных значений, гораздо труднее рассуждать, чем определения, которые идут по порядку, каждое новое определение строится поверх того, что уже было определено. При чтении такого кода приятно иметь гарантию, что, за исключением определений, явно отмеченных как рекурсивные, новые определения могут ссылаться только на предыдущие определения.
источник
Некоторые догадки:
let
используется не только для привязки функций, но и других обычных значений. Большинство форм значений не могут быть рекурсивными. Разрешены определенные формы рекурсивных значений (например, функции, ленивые выражения и т. Д.), Поэтому для обозначения этого требуется явный синтаксис.let
конструкция аналогичнаlet
конструкции в Lisp и Scheme; которые не рекурсивны. Вletrec
Scheme есть отдельная конструкция для рекурсивного letисточник
let rec xs = 0::ys and ys = 1::xs
.Учитывая это:
Сравните:
С этим:
Первый переопределяет,
f
чтобы применить ранее определенноеf
к результату примененияg
кa
. Последние переопределяетf
в цикл навсегда применяяg
кa
, который, как правило , не то , что вы хотите в ML варианты.Тем не менее, это стиль языкового дизайнера. Просто смирись.
источник
Большая часть этого заключается в том, что это дает программисту больше контроля над сложностью своих локальных областей видимости. Спектр
let
,let*
аlet rec
предложение растет уровень как мощности и стоимости.let*
иlet rec
по сути являются вложенными версиями простогоlet
, поэтому использование любого из них дороже. Эта оценка позволяет вам контролировать оптимизацию вашей программы, поскольку вы можете выбрать, какой уровень допуска вам нужен для текущей задачи. Если вам не нужна рекурсия или возможность ссылаться на предыдущие привязки, вы можете вернуться к простому let, чтобы немного сэкономить производительность.Это похоже на предикаты градуированного равенства в Scheme. (то есть
eq?
,eqv?
иequal?
)источник