Come implementeresti un operatore a virgola fissa (combinatore Y) in F#?

Question

Sto usando F# per creare un lambda calcolo.Al momento sono bloccato nel tentativo di capire come implementare l'operatore di virgola fissa (chiamato anche combinatore Y).

Penso che tutto il resto sia in ordine.Le espressioni sono rappresentate dalla seguente unione discriminata:

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

Mio eval la funzione sembra funzionare.Tutti gli esempi seguenti producono i risultati attesi.
Esempio 1:
> eval (Fun("x",Plus(Const 7,Var("x"))));;
val it : Expr = Fun ("x",Plus (Const 7,Var "x"))
esempio 2:
> eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3));;
val it : Expr = Const 10
esempio 3:
> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

Ma come ho già detto, ho difficoltà a implementare l'operatore di virgola fissa nel mio lambda calcolo.È definito Qui COME:
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

Qualcuno ha qualche suggerimento?Ho esaminato altre domande riguardanti il ​​combinatore Y, ma non sono riuscito a trovare nulla che potessi adottare con successo.

Tutto l'aiuto è apprezzato.

Modificare: Risolto un errore di battitura nel codice...in precedenza avevo Mult invece di Minus nell’unione discriminata.Strano che l'abbia appena notato!

Answer 1

La versione a cui ti riferisci funziona solo con un linguaggio pigro e se il tuo linguaggio non utilizza una strategia di valutazione pigra, rimarrai bloccato in un ciclo infinito.Prova a tradurre questo:

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

Answer 2

Per quanto ricordo, esiste un'intera classe di combinatori Y nel lambda calcolo non tipizzato, ma diventa difficile implementarne anche uno se la tua lingua è rigorosamente tipizzata, sebbene le persone abbiano provato a fare casi speciali in ML e anche F#.Non sembra essere molto utile se la tua lingua supporta la ricorsione (cosa che il lambda calcolo non supporta).Dai un'occhiata alle discussioni su quell'argomento che Stackoverflow ha visto contrassegnato con generica "programmazione funzionale" o ML, penso che ci siano alcuni approfondimenti da avere:

Esempio pratico del combinatore Y