Comment voulez-vous mettre en œuvre une fonction de réduction de la bêta en F #?

Question

Je suis en train d'écrire un calcul lambda en F #, mais je suis bloqué sur la mise en œuvre de la bêta-réduction (en remplaçant les paramètres formels avec les paramètres réels).

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

Exemple d'utilisation:

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

J'aimerais entendre quelques suggestions en ce qui concerne la façon dont d'autres pourraient aller à ce sujet. Toutes les idées seraient grandement appréciés.

Merci!

Answer 1

En supposant que votre représentation d'une apparence d'expression comme

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

, vous avez une subst (x:ident) (e1:expression) (e2:expression) : expression fonction qui remplace toutes les occurrences libres de x avec e1 dans e2, et que vous voulez l'évaluation de l'ordre normal, votre code devrait ressembler à ceci:

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

La fonction subst devrait fonctionner comme suit:

Pour une application de fonction, il doit s'appeler récursive sur les deux sous-expressions.

Pour lambdas, il devrait se faire appel à l'expression corporelle du lambda moins le nom de l'argument du lambda est égale à l'identifiant que vous souhaitez remplacer (dans ce cas, vous pouvez laisser le lambda-être parce que la boîte d'identification « t apparaissent librement partout à l'intérieur).

Pour une variable, il doit soit renvoyer la variable inchangée ou l'expression de remplacement selon que le nom de la variable est égale à l'identifiant.