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

¿Por qué las funciones en F # y Ocaml (y posiblemente en otros lenguajes) no son recursivas por defecto?

En otras palabras, ¿por qué los diseñadores del lenguaje decidieron que era una buena idea hacerte escribir explícitamente recuna declaración como:

let rec foo ... = ...

y no dar a la función la capacidad recursiva por defecto? ¿Por qué la necesidad de una recconstrucción explícita ?

Los descendientes franceses y británicos del ML original tomaron decisiones diferentes y sus elecciones se han heredado a lo largo de las décadas hasta las variantes modernas. Esto es solo un legado, pero afecta los modismos en estos idiomas.

Las funciones no son recursivas de forma predeterminada en la familia de idiomas CAML en francés (incluido OCaml). Esta opción facilita la sustitución de las definiciones de función (y variable) que se utilizan leten esos lenguajes porque puede hacer referencia a la definición anterior dentro del cuerpo de una nueva definición. F # heredó esta sintaxis de OCaml.

Por ejemplo, reemplazando la función pal calcular la entropía de Shannon de una secuencia en 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

Observe cómo el argumento pde la shannonfunción de orden superior es reemplazado por otro pen la primera línea del cuerpo y luego por otro pen la segunda línea del cuerpo.

Por el contrario, la rama británica SML de la familia de lenguajes ML tomó la otra opción y las funfunciones vinculadas de SML son recursivas de forma predeterminada. Cuando la mayoría de las definiciones de funciones no necesitan acceso a enlaces previos de su nombre de función, esto da como resultado un código más simple. Sin embargo, las funciones reemplazadas están hechas para usar diferentes nombres ( f1, f2etc.) lo que contamina el alcance y hace posible invocar accidentalmente la "versión" incorrecta de una función. Y ahora hay una discrepancia entre funfunciones vinculadas implícitamente recursivas y funciones vinculadas no recursivas val.

Haskell hace posible inferir las dependencias entre definiciones restringiéndolas para que sean puras. Esto hace que las muestras de juguetes parezcan más simples, pero tiene un costo elevado en otros lugares.

Tenga en cuenta que las respuestas dadas por Ganesh y Eddie son pistas falsas. Explicaron por qué los grupos de funciones no se pueden colocar dentro de un gigante let rec ... and ...porque afecta cuando las variables de tipo se generalizan. Esto no tiene nada que ver con recser predeterminado en SML pero no OCaml.

Una razón crucial para el uso explícito de rectiene que ver con la inferencia de tipo Hindley-Milner, que subyace a todos los lenguajes de programación funcional de tipado estático (aunque cambiado y extendido de varias formas).

Si tiene una definición let f x = x, esperaría que tenga un tipo 'a -> 'ay sea aplicable en diferentes 'atipos en diferentes puntos. Pero igualmente, si escribe let g x = (x + 1) + ..., esperaría xser tratado como inten el resto del cuerpo de g.

La forma en que la inferencia de Hindley-Milner trata esta distinción es mediante un paso de generalización explícito . En ciertos puntos al procesar su programa, el sistema de tipos se detiene y dice "ok, los tipos de estas definiciones se generalizarán en este punto, de modo que cuando alguien las use, cualquier variable de tipo libre en su tipo será recién instanciada y, por lo tanto, no interferirá con ningún otro uso de esta definición ".

Resulta que el lugar sensato para hacer esta generalización es después de verificar un conjunto de funciones recursivas entre sí. Si lo hace antes, generalizará demasiado, lo que conducirá a situaciones en las que los tipos podrían colisionar. Más adelante, generalizará muy poco, haciendo definiciones que no se pueden usar con instancias de múltiples tipos.

Entonces, dado que el verificador de tipos necesita saber qué conjuntos de definiciones son recursivas entre sí, ¿qué puede hacer? Una posibilidad es simplemente hacer un análisis de dependencia de todas las definiciones en un alcance y reordenarlas en los grupos más pequeños posibles. Haskell en realidad hace esto, pero en lenguajes como F # (y OCaml y SML) que tienen efectos secundarios sin restricciones, esta es una mala idea porque también podría reordenar los efectos secundarios. Entonces, en cambio, le pide al usuario que marque explícitamente qué definiciones son recursivas entre sí y, por lo tanto, por extensión, dónde debería ocurrir la generalización.

Hay dos razones clave por las que esta es una buena idea:

Primero, si habilita las definiciones recursivas, entonces no puede hacer referencia a un enlace anterior de un valor del mismo nombre. Suele ser un modismo útil cuando se hace algo como ampliar un módulo existente.

En segundo lugar, los valores recursivos, y especialmente los conjuntos de valores recursivos entre sí, son mucho más difíciles de razonar, entonces son definiciones que proceden en orden, cada nueva definición se construye sobre lo que ya se ha definido. Al leer dicho código, es bueno tener la garantía de que, a excepción de las definiciones marcadas explícitamente como recursivas, las nuevas definiciones solo pueden referirse a definiciones anteriores.

Algunas conjeturas:

• letno solo se usa para vincular funciones, sino también otros valores regulares. La mayoría de las formas de valores no pueden ser recursivas. Se permiten ciertas formas de valores recursivos (por ejemplo, funciones, expresiones perezosas, etc.), por lo que necesita una sintaxis explícita para indicar esto.
• Podría ser más fácil optimizar funciones no recursivas
• El cierre creado al crear una función recursiva debe incluir una entrada que apunte a la función en sí (para que la función pueda llamarse a sí misma de forma recursiva), lo que hace que los cierres recursivos sean más complicados que los cierres no recursivos. Por lo tanto, sería bueno poder crear cierres no recursivos más simples cuando no necesite la recursividad
• Le permite definir una función en términos de una función previamente definida o un valor del mismo nombre; aunque creo que esto es una mala práctica
• ¿Más seguridad? Se asegura de que está haciendo lo que pretendía. Por ejemplo, si no tiene la intención de que sea recursivo, pero accidentalmente utilizó un nombre dentro de la función con el mismo nombre que la función en sí, lo más probable es que se queje (a menos que el nombre haya sido definido antes)
• La letconstrucción es similar a la letconstrucción en Lisp y Scheme; que no son recursivas. Hay una letrecconstrucción separada en Scheme para recursiva Let's

Dado este:

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

Comparar:

let f a = f (g a)

Con este:

let rec f a = f (g a)

El primero redefine fpara aplicar el definido previamente fpara el resultado de aplicar ga a. Este último redefine fa un bucle infinito aplicando ga a, que por lo general no es lo que desea en las variantes ML.

Dicho esto, es una cuestión de estilo de diseñador de idiomas. Sígueme el rollo.

Una gran parte de esto es que le da al programador más control sobre la complejidad de sus ámbitos locales. El espectro de let, let*y let recofrecen un creciente nivel de potencia y costo. let*y let recson, en esencia, versiones anidadas de lo simple let, por lo que usar cualquiera de las dos es más costoso. Esta calificación le permite microgestionar la optimización de su programa, ya que puede elegir qué nivel de permiso necesita para la tarea en cuestión. Si no necesita recursividad o la capacidad de hacer referencia a enlaces anteriores, puede recurrir a un simple let para ahorrar un poco de rendimiento.

Es similar a los predicados de igualdad graduados en Scheme. (es decir eq?, eqv?y equal?)