你将如何实现在F＃β-减弱功能？

Question

我写在F＃一个演算，但我卡在执行所述β-减少（与实际的参数代形式参数）。

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

示例用法：

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

所以我很乐意听到的问候别人会如何去这一些建议。任何想法将不胜感激。

谢谢！

Answer 1

假设表达式看起来像您的表示

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

，你有一个函数subst (x:ident) (e1:expression) (e2:expression) : expression它取代x的所有自由出现在e1 e2，你想正常秩序的评价，你的代码看起来应该是这样的：

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

在subst函数应该作为工作如下：

有关的功能的应用程序应该递归调用自身在两个子表达式。

有关lambda表达式应该调用本身的拉姆达的身体表达的除非的拉姆达的参数名称等于要替换的标识符（在这种情况下，你可以离开拉姆达是因为标识符可以“T自由的任何地方出现在其内部）。

有关的变量应该要么返回变量不变或取决于变量的名称是否等于标识符替换表达式。