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

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

Si tiene una definición let f x = x, esperaría que tuviera el tipo 'a -> 'a y que fuera aplicable en diferentes tipos 'a en diferentes puntos. Pero igualmente, si escribes let g x = (x + 1) + ..., esperarías que x sea tratado como un int en el resto del cuerpo de g.

La forma en que La inferencia de Hindley-Milner trata esta distinción a través de un paso explícito de generalización . 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 los use, cualquier variable de tipo libre en su tipo será recién creada, y por lo tanto no interferirá con ningún otro uso de esta definición."

Resulta que el lugar sensato para hacer esto la generalización es después de comprobar un conjunto de funciones mutuamente recursivas. Cualquier anterior, y generalizarás demasiado, llevando a situaciones donde los tipos realmente podrían chocar. Más tarde, generalizarás muy poco, haciendo definiciones que no se pueden usar con múltiples instancias de tipo.

Entonces, dado que el comprobador 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 ámbito, y reordenarlos en los grupos más pequeños posibles. Haskell realmente hace esto, pero en lenguajes como F# (y OCaml y SML) que tienen efectos secundarios sin restricciones, esto es una mala idea porque podría reordenar los efectos secundarios también. Por lo tanto, pide al usuario que marque explícitamente qué definiciones son mutuamente recursivas y, por extensión, dónde debería generalizarse.

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

Primero, si habilita definiciones recursivas, entonces no puede hacer referencia a un enlace anterior de un valor del mismo nombre. Este es a menudo un modismo útil cuando se está 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, entonces son las definiciones que proceden en orden, cada nueva definición construyendo sobre lo que ya ha sido definido. Es bueno al leer dicho código 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:

• 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 cuando se crea una función recursiva debe incluir una entrada que apunte a la propia función (por lo que la función puede llamarse recursivamente a sí misma), lo que hace que los cierres recursivos sean más complicados que los cierres no recursivos. Por lo tanto, podría ser bueno poder crear cierres no recursivos más simples cuando no necesita recursión
• Permite definir una función en términos de una función previamente definida o valor del mismo nombre; aunque creo que esta es una mala práctica
• ¿Seguridad adicional? Se asegura de que usted está haciendo lo que pretendía. por ejemplo, si no tiene la intención de que sea recursivo, pero accidentalmente usaste 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 antes)
• La construcción let es similar a la construcción let en Lisp y Scheme; que no son recursivas. Hay una construcción separada letrec en Scheme para recursivo let's

Dado esto:

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

Compare:

let f a = f (g a)

Con esto:

let rec f a = f (g a)

El primero redefine f para aplicar lo previamente definido f al resultado de aplicar g a a. Este último redefine f para hacer un bucle para siempre aplicando g a a, que generalmente no es lo que desea en las variantes de ML.

Dicho esto, es una cosa de estilo de diseñador de lenguaje. Sígueme la corriente.

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 ofrecen un nivel cada vez mayor de potencia y costo. let* y let rec son en esencia versiones anidadas del simple let, 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 qué nivel de licencia necesita para la tarea en cuestión. Si usted no necesita recursión o la capacidad de consulte los enlaces anteriores, luego puede recurrir a un simple let para ahorrar un poco de rendimiento.

Es similar a los predicados de igualdad calificados en Scheme. (i. e.eq?, eqv? y equal?)