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

recursion

Question

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

En otras palabras, ¿por qué los diseñadores de idiomas decidieron que era una buena idea hacer explícitamente que rec en una declaración como:

let rec foo ... = ...

y no le da la función de capacidad recursiva por defecto? ¿Por qué la necesidad de una construcción rec explícita?

Answer 1

Algunas conjeturas:

• let no solo se usa para enlazar 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 las funciones no recursivas
• El cierre creado al crear una función recursiva necesita incluir una entrada que apunta a la función en sí (para que la función pueda llamarse recursivamente), 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 se necesita recurrencia
• Le permite definir una función en términos de una función o valor previamente definido con el mismo nombre; aunque creo que esto es una mala práctica
• Seguridad extra? Asegura que estás haciendo lo que pretendías. 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 se haya definido anteriormente)
• La construcción let es similar a la construcción let en Lisp y Scheme; que no son recursivos Hay una construcción letrec separada en Scheme para letrec ''s recursivos

Answer 2

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

En primer lugar, si habilita las definiciones recursivas, no puede hacer referencia a un enlace anterior de un valor del mismo nombre. Esto a menudo es una expresión útil cuando estás haciendo algo como extender un módulo existente.

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

Answer 3

Una razón crucial para el uso explícito de rec es hacer con la inferencia de tipo Hindley-Milner, que subyace a todos los lenguajes de programación funcionales de tipo estático (aunque modificados y ampliados de varias maneras).

Si tiene una definición let fx = x , esperaría que tuviera el tipo ''a -> ''a y que fuera aplicable en diferentes ''a tipos en diferentes puntos. Pero igualmente, si escribe let gx = (x + 1) + ... , esperaría que x se tratara como int en el resto del cuerpo de g .

La forma en que la inferencia de Hindley-Milner trata esta distinción es a través de un paso de generalización explícito. En ciertos puntos al procesar su programa, el sistema de tipo se detiene y dice "ok, los tipos de estas definiciones se generalizarán en este punto, de modo que cuando alguien los use, cualquier variable de tipo libre en su tipo será instanciada recientemente , 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 mutuamente recursivo de funciones. Antes, y generalizarás demasiado, lo que te llevará a situaciones en las que los tipos podrían colisionar. Más adelante, y generalizará muy poco, haciendo definiciones que no se pueden usar con instancias de tipos múltiples.

Entonces, dado que el verificador de tipos necesita saber qué conjuntos de definiciones son mutuamente recursivas, ¿qué puede hacer? Una posibilidad es simplemente hacer un análisis de dependencia en todas las definiciones en un alcance y reordenarlas en los grupos más pequeños posibles. Haskell realmente hace esto, pero en idiomas 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. Por lo tanto, le pide al usuario que marque explícitamente qué definiciones son mutuamente recursivas, y por lo tanto, por extensión, donde debe darse la generalización.

Answer 4

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 rec ofrece un nivel cada vez mayor de potencia y costo. let* y let rec son, en esencia, versiones anidadas del let simple, por lo que usar cualquiera de ellas es más caro. Esta calificación le permite microgestionar la optimización de su programa ya que puede elegir el nivel de necesidad que necesita para la tarea en cuestión. Si no necesita recurrencia o la capacidad de referirse a enlaces anteriores, puede recurrir a un simple dejar para guardar un poco de rendimiento.

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

Answer 5

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 f para aplicar el f previamente definido al resultado de aplicar g a a . Este último redefine f al bucle aplicando siempre g a a , que generalmente no es lo que desea en las variantes de ML.

Dicho esto, es un estilo de diseño de lenguaje. Sígueme el rollo.

Answer 6

Los descendientes franceses y británicos del NM original tomaron decisiones diferentes y sus elecciones han sido heredadas a través de las décadas a las variantes modernas. Así que esto es solo un legado, pero afecta las expresiones idiomáticas en estos idiomas.

Las funciones no son recursivas por defecto en la familia de lengua francesa CAML (incluyendo OCaml). Esta elección facilita la sustitución de las definiciones de funciones (y variables) con let en esos lenguajes, ya que puede consultar la definición anterior dentro del cuerpo de una nueva definición. F # heredó esta sintaxis de OCaml.

Por ejemplo, supercediendo la función p al 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 p de la función shannon orden superior es reemplazado por otra p en la primera línea del cuerpo y luego otra p en la segunda línea del cuerpo.

Por el contrario, la rama SML británica de la familia de idiomas ML tomó la otra opción y las funciones de enlace de fun de SML son recursivas por defecto. Cuando la mayoría de las definiciones de función no necesitan acceso a enlaces anteriores de su nombre de función, esto da como resultado un código más simple. Sin embargo, las funciones sustituidas están hechas para usar nombres diferentes ( f1 , f2 , etc.) que contaminan el alcance y hacen que sea posible invocar accidentalmente la "versión" incorrecta de una función. Y ahora existe una discrepancia entre las funciones fun -bound recursivas implícitamente recursivas y las funciones val -bound no recursivas.

Haskell hace posible inferir las dependencias entre definiciones al restringirlas a ser puras. Esto hace que las muestras de juguetes parezcan más simples, pero tiene un costo grave 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 ubicar dentro de un let rec ... and ... gigante let rec ... and ... porque afecta cuando las variables de tipo se generalizan. Esto no tiene nada que ver con que rec esté predeterminado en SML pero no en OCaml.