Come si implementa una funzione beta-riduzione di F #?

Question

Sto scrivendo un lambda calcolo in F #, ma io sono bloccato in atto del beta-riduzione (sostituendo parametri formali con i parametri attuali).

(lambda x.e)f
--> e[f/x]

esempio di utilizzo:

(lambda n. n*2+3) 7
--> (n*2+3)[7/n]
--> 7*2+3

Così mi piacerebbe sentire alcuni suggerimenti in relazione al modo altri potrebbero andare su questo. Tutte le idee sarebbe molto apprezzato.

Grazie!

Answer 1

Assumendo che il rappresentazione di un aspetto di espressione come

type expression = App of expression * expression
                | Lambda of ident * expression
                (* ... *)

, si dispone di una funzione di subst (x:ident) (e1:expression) (e2:expression) : expression che sostituisce tutte le occorrenze libere di x con e1 in e2, e si desidera che la valutazione normale ordine, il codice dovrebbe essere simile a questo:

let rec eval exp =
  match exp with
  (* ... *)
  | App (f, arg) -> match eval f with Lambda (x,e) -> eval (subst x arg e)

La funzione subst dovrebbe funzionare come segue:

Per un'applicazione funzione si deve chiamare se stesso in modo ricorsivo su entrambe le sottoespressioni.

Per lambda dovrebbe chiamarsi sull'espressione corpo del lambda meno nome argomento della lambda è uguale alla identificatore che si desidera sostituire (nel qual caso si può semplicemente lasciare il lambda essere perché la lattina identificatore 't appaiono liberamente in qualsiasi punto all'interno di esso).

Per una variabile o esso deve restituire la invariato variabile o la sostituzione espressione a seconda che il nome della variabile è uguale al identificatore.