Wie würden Sie eine Beta-Reduktion Funktion in F # implementieren?

Question

Ich bin ein Lambda-Kalkül in F # zu schreiben, aber ich bin fest auf der Umsetzung die Beta-Reduktion (formale Parameter mit den tatsächlichen Parametern ersetzt).

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

Beispiel für die Verwendung:

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

Also ich würde gerne einige Vorschläge in Bezug auf die hören, wie andere über diese gehen könnte. Irgendwelche Ideen wäre sehr geschätzt.

Danke!

Answer 1

Angenommen, Ihre Darstellung eines Ausdrucks sieht aus wie

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

Sie haben eine Funktion subst (x:ident) (e1:expression) (e2:expression) : expression, die alle freien Vorkommen von x mit e1 in e2 ersetzt, und Sie wollen normale Reihenfolge Bewertung, Ihr Code sollte wie folgt aussehen:

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

Die subst Funktion sollte funktionieren wie folgt:

Für eine Funktionsanwendung sollte es sich auf beiden Teilausdrücke rekursiv aufrufen.

Für lambdas sie sich auf die Körperausdruck des Lambda nennen sollte es sei denn, das Argument Name Lambda gleich der Kennung Sie ersetzen möchten (in diesem Fall können Sie einfach verlassen kann der Lambda sein, weil die Kennung kann ‚t erscheinen frei überall im Inneren).

Für eine Variable sollte es entweder die Variable unverändert zurückkommen oder den Ersatz-Ausdruck je nachdem, ob der Variablenname auf die Kennung gleich ist.