F＃表达式树解释器的实现

Question

我试图构建一个可以在F＃中添加或乘法的表达式树的解释器，但是我遇到了一些麻烦。我还试图使用选项类型，以便解释器在该表达式中不包含变量时返回None。

这是我给的代码。

type Exptree = 
    | Const of int 
    | Var of string 
    | Add of Exptree * Exptree 
    | Mul of Exptree * Exptree 

type Bindings = (string * int) list 

let rec eval(exp : Exptree, env:Bindings) = 
    match exp with 
    | 

我很困惑与exp匹配的是什么，因为有这么多选项。我的想法是查看Add和Mul，并尝试在每个递归步骤中删除它，直到我得到一个整数，但是我完全失去了。

我可以做类似的事吗？

match exp with 
| Some(Add) -> int + int? 
| Some(Mul) -> int * int? 

Answer 1

您的Exptree类型有四种可能的构造函数：Const，Var，Add和Mul。所以，你的对手将是对那些：

match exp with 
| Const c -> 
| Var s -> 
| Add (e1,e2) -> 
| Mul (e1,e2) -> 

对于每一个这种情况下，你会做相应的操作（加法，乘法，查找环境变量，返回一个常数）。在add和mul的情况下，你会解释eval在子表达式（e1和e2）上递归调用的结果，看看该值是None还是Some（s），并相应地作用于它。

Answer 2

因此，scrwtp是正确的，Map<string, int>对于您的一组绑定更有意义，因为您可以在O（log n）时间内执行查找，而不是使用list进行O（n）时间查找。

的eval功能的第一部分很简单：

1. 如果该值是恒定的，我们只需要返回不变的Some。
2. 如果该值是一个变量，我们需要在地图上查找它，如果该键存在，我们返回值为Some。如果他们的钥匙不存在，我们将返回None。我们可以使用Map.tryFind来做到这一点。

我们能做到这一点的部分是这样的：

let rec eval bindings tree = 
    match tree with 
    |Const i -> Some i 
    |Var varName -> Map.tryFind varName bindings 

执行加法和乘法需要一些更多的思考。为了抽象地合并两个子树，定义一个函数将两个选项作为参数是有意义的，并且如果它们都是Some value，则可以将函数应用于两个结果。这就是所谓的lift2功能，我们可以将其定义为Option：

/// Combines two option values using a supplied function 
let lift2 f opt1 opt2 = 
    match (opt1, opt2) with 
    |Some val1, Some val2 -> Some <| f val1 val2 
    |_ -> None 

欲了解更多的lift家庭的功能，看到这个伟大的教程：http://fsharpforfunandprofit.com/posts/elevated-world/#lift

现在我们可以扩展我们eval功能的加法并通过调用这个函数来乘法情况。现在

/// Evaluates the result of an expression tree 
let rec eval bindings tree = 
    match tree with 
    |Const i -> Some i // Const always returns some value 
    |Var varName -> Map.tryFind varName bindings // Returns some value if it exists in the binding table 
    |Add (tree1, tree2) -> 
     lift2 (+) (eval bindings tree1) (eval bindings tree2) // add expressions if both expressions return Some val 
    |Mul (tree1, tree2) -> 
     lift2 (*) (eval bindings tree1) (eval bindings tree2) // multiply expressions if both expressions return Some val 

，添加的情况下使用lift2功能地说，如果两个子表达式计算为一个真正的价值，结果加在一起，否则返回None。

乘法情况遵循完全相同的逻辑，我们只是交换操作符。

快速旁白：作为GuyCoder指出，建立自己的绑定表的便捷方式将被使用的语法：

let bindings = Map.ofList [("a",1); ("b",2); ("c",3)]