¿Cómo se implementa un operador de coma fija (Y Combinator) en F #?

Question

Estoy usando C # para crear un cálculo lambda. Actualmente estoy atascado tratando de averiguar cómo iba a aplicar el operador de punto fijo (también llamado combinador Y).

Creo que todo lo demás está en orden. Las expresiones se representan por la siguiente unión discriminada:

type Expr =
 | Const of int
 | Plus  of Expr * Expr
 | Times of Expr * Expr
 | Minus of Expr * Expr
 | Div   of Expr * Expr
 | Neg   of Expr
 | Var   of string
 | Fun   of string * Expr
 | App   of Expr * Expr
 | If    of Expr * Expr * Expr

Mi función eval parece funcionar. Todos los ejemplos siguientes dan los resultados esperados.
Ejemplo 1:
> eval (Fun("x",Plus(Const 7,Var("x"))));;
val it : Expr = Fun ("x",Plus (Const 7,Var "x"))
Ejemplo 2:
> eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3));;
val it : Expr = Const 10
Ejemplo 3:
> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

Sin embargo, como he mencionado, estoy teniendo dificultades para implementar el operador de punto fijo dentro de mi cálculo lambda. Se define aquí como:
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

¿Alguien tiene alguna sugerencia? He mirado en otras preguntas relacionadas con el combinador Y, pero no pude encontrar nada de lo que yo era capaz de adoptar con éxito.

Toda la ayuda es apreciada.

Editar Se ha corregido un error en el código ... Yo antes tenía Mult en lugar de Minus en la unión discriminada. Es curioso que me he dado cuenta de que!

Answer 1

La versión que se está refiriendo a las obras sólo con un lenguaje vago, y si su lengua materna no es el uso de una estrategia de evaluación perezosa, se le queda atascado en un bucle infinito. Intente traducir esto:

Y = lambda G. (lambda g. G(lambda x. g g x)) (lambda g. G(lambda x. g g x))

Answer 2

Por lo que yo recuerdo, hay toda una clase de Y Combinator en el cálculo lambda sin tipo, pero se vuelve difícil de aplicar, incluso uno si su idioma está estrictamente escrito, aunque las personas han tratado de hacer casos especiales de lavado de dinero y también F#. No parece ser muy útil si su idioma es compatible con la recursividad (que el cálculo lambda no lo hace). Echar un vistazo a los debates sobre este tema que Stackoverflow ha visto marcado con "programación funcional" genérico o ML, creo que hay algunos puntos de vista que se tenía:

Y-Combinator Ejemplo Práctico