Comment voulez-vous mettre en œuvre un opérateur de point fixe (Y Combinator) en F #?

Question

J'utilise F # pour créer un calcul lambda. Je suis actuellement coincé à essayer de comprendre comment je mettre en œuvre l'opérateur de point fixe (également appelé Y Combinator).

Je pense que tout le reste dans l'ordre. Les expressions sont représentés par le syndicat discriminé suivant:

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

Ma fonction eval semble fonctionner. Les exemples suivants donnent tous les résultats escomptés.
Exemple 1:
> eval (Fun("x",Plus(Const 7,Var("x"))));;
val it : Expr = Fun ("x",Plus (Const 7,Var "x"))
Exemple 2:
> eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3));;
val it : Expr = Const 10
Exemple 3:
> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

Mais comme je l'ai mentionné, je vais avoir du mal mise en œuvre de l'opérateur point fixe dans mon calcul lambda. Il est défini comme:
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

Quelqu'un at-il des suggestions? Je l'ai regardé d'autres questions concernant le combinateur Y, mais n'a pas pu trouver quelque chose que je suis en mesure d'adopter avec succès.

Toute aide est appréciée.

Edit: Correction d'une faute de frappe dans le code ... Auparavant, j'avais Mult au lieu de Minus dans l'union discriminée. Drôle que je viens de remarquer que!

Answer 1

La version que vous faites référence à des œuvres uniquement avec une langue paresseuse, et si votre langue est de ne pas utiliser une stratégie d'évaluation paresseuse, vous êtes coincé dans une boucle infinie. Essayez traduire ceci:

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

Answer 2

Pour autant que je le rappelle, il y a toute une classe de Y Combinator dans le calcul typées lambda, mais il devient difficile de mettre en œuvre même un si votre langue est strictement typé, bien que les gens ont essayé de faire des cas particuliers en ML et aussi F#. Il ne semble pas être très utile si votre langue prend en charge la récursivité (qui lambda-calcul ne fonctionne pas). Jetez un oeil sur les discussions sur ce sujet que Stackoverflow a signalé avec Aperçu « programmation fonctionnelle » générique ou ML, je pense qu'il ya quelques idées à avoir:

Y-combinateur Exemple pratique