Comment voulez-vous mettre en œuvre une fonction de réduction de la bêta en F #?
-
27-09-2019 - |
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!
La solution
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.