recursion - ¿Por qué Ocaml necesita tanto "let" como "let rec"?

functional-programming

Question

Posible duplicado:
¿Por qué las funciones en Ocaml / F # no son recursivas por defecto?

OCaml usa let para definir una nueva función, o let rec para definir una función recursiva. ¿Por qué necesita ambos? ¿No podríamos usar let para todo?

Por ejemplo, para definir una función sucesora no recursiva y un factorial recursivo en OCaml (de hecho, en el intérprete OCaml) podría escribir

let succ n = n + 1;;
let rec fact n =
if n = 0 then 1 else n * fact (n-1);;

Mientras que en Haskell (GHCI) puedo escribir

let succ n = n + 1
let fact n =
if n == 0 then 1 else n * fact (n-1)

¿Por qué OCaml distingue entre let y let rec ? ¿Es un problema de rendimiento o algo más sutil?

Answer 1

Bueno, tener ambos disponibles en lugar de uno solo le da al programador un mayor control sobre el alcance. Con let x = e1 in e2 , el enlace solo está presente en el entorno de e2 , mientras que con let rec x = e1 in e2 el enlace está presente en los entornos de e1 y e2 .

(Editar: Quiero enfatizar que no es un problema de rendimiento, eso no hace ninguna diferencia).

Aquí hay dos situaciones donde tener este enlace no recursivo es útil:

• sombreando una definición existente con un refinamiento que usa el enlace anterior. Algo así como: let fx = (let x = sanitize x in ...) , donde sanitize es una función que asegura que la entrada tiene alguna propiedad deseable (por ejemplo, toma la norma de un vector posiblemente no normalizado, etc.) . Esto es muy útil en algunos casos.

• metaprogramación, por ejemplo macro escritura. Imagina que quiero definir un macro SQUARE(foo) que desagrupa en let x = foo in x * x , para cualquier expresión foo . Necesito este enlace para evitar la duplicación de código en la salida (no quiero que SQUARE(factorial n) calcule factorial n dos veces). Esto es solo higiénico si el enlace let no es recursivo, de lo contrario no podría escribir let x = 2 in SQUARE(x) y obtener un resultado correcto.

Por lo tanto, afirmo que es muy importante tener disponible tanto el enlace recursivo como el no recursivo. Ahora, el comportamiento predeterminado de let-binding es una cuestión de convención. Podrías decir que let x = ... es recursivo, y uno debe usar let nonrec x = ... para obtener el let nonrec x = ... no recursivo. Escoger uno por defecto u otro es una cuestión de qué estilo de programación desea favorecer y hay buenas razones para elegir. Haskell sufre¹ por la falta de disponibilidad de este modo no recursivo, y OCaml tiene exactamente el mismo defecto en el nivel de type foo = ... : type foo = ... es recursivo, y no hay ninguna opción no recursiva disponible; consulte esta publicación en el blog .

¹: cuando Google Code Search estaba disponible, lo usé para buscar en el código de Haskell el patrón let x'' = sanitize x in ... Esta es la solución habitual cuando el enlace no recursivo no está disponible, pero es menos seguro porque te arriesgas a escribir x lugar de x'' por error más adelante; en algunos casos quieres tener ambos disponibles, por lo que puedes elegir un nombre diferente. voluntario. Una buena expresión sería usar un nombre de variable más largo para la primera x , como unsanitized_x . De todos modos, simplemente buscando x'' literalmente (sin otro nombre de variable) y x1 se obtuvieron muchos resultados. Erlang (y todos los lenguajes que intentan dificultar el sombreado variable: Coffeescript, etc.) tienen problemas aún peores de este tipo.

Dicho esto, la elección de tener enlaces Haskell recursivos por defecto (en lugar de no recursivo) ciertamente tiene sentido, ya que es consistente con la evaluación diferida por defecto, lo que hace que sea muy fácil construir valores recursivos, mientras que es estricto por defecto los idiomas tienen más restricciones sobre las definiciones recursivas que tienen sentido.