评估算术语法树表达式

Question

你能不能帮我下一个任务： 我应该有一个功能

fun eval (fn : (string * int) list -> expression -> int) 

那得到一个元组列表（变量名，值）的表达式。该函数使用currying并返回表达式的评估值。它至少应该支持运营商+, -, *, /, %表示加，减，乘，整数除法和余

对于接下来的数据类型：

datatype expression = Constant of int 
        | Variable of string 
        | Operator of string * expression 
        | Pair of expression list 
        | List of expression list 

任何建议或解释，将不胜感激！

Answer 1

这里是一个骨架：

fun lookup var1 ((var2,value)::rest) = ... 
    | lookup var1 [] = raise Fail ("Variable "^var1^" not found") 

fun eval vtable exp = 
    case exp of 
     Constant i => i 
     | Variable v => lookup ... 
     | Operator (oper, subexp) => evalOp vtable oper subexp 
     | Pair _ => raise Fail "Pair at unexpected position in syntax tree!" 
     | List _ => raise Fail "List at unexpected position in syntax tree!" 

and evalOp vtable oper exp = 
    let val operands = 
      case exp of ... (* calling eval on sub-expressions allowed *) ... 
    in case oper of 
      "+" => ...add operands... 
      | "-" => ...subtract operands... 
      | ... 
    end 

这里有一些想法：

• 解决问题的智慧：划分问题分成几个子部分。例如，使用vtable查找变量的帮助函数是给定的。处理操作员在一个单独的帮手功能有没有明显的好处 - 主要是我只是想避免嵌套案件的 s易读性。因为数据类型具有太多的灵活性（可以表达，在我看来，无意义的表达式），在正确的位置处理这种灵活性似乎也需要在这里进行划分。

• 如果Pair应该总是包含两个操作数，你可以写这个部分作为val (op1, op2) = case exp of ...，但如果他们有时会降低到值的列表上，操作者必须具有关联性的一些假设的工作，或许仅仅map eval sub_exps哪里sub_exps是在Pair或List内找到的表达式的评估列表。

• 正如约翰所说，你给出的语法树似乎反映了一些不受欢迎的属性。例如，Pair [Constant 1, Constant 2, Constant 3]是一对奇特的。 Operator ("-", Pair [Constant 1, Constant 2, Constant 3])是什么意思？那么Operator ("/", [])呢？为什么即使同时有Pair和List他们都列出了？ List何时适合？为什么会配对法律表达？他们应该评估什么样的整数值？

  道德：良好的数据类型只有有意义的价值。

  另一种数据类型，它可能做的伎俩：

  datatype expression = Constant of int 
          | Variable of string 
          | Operator of string * expression * expression 
        (* or: | Operator of string * expression list *) 
  

  此数据类型是比较容易评估，也因为有少奇/错角的情况来处理：

  fun getOp "+" = op + 
      | getOp "-" = op - 
      | getOp "*" = op * 
      | getOp "/" = op div 
      | getOp "%" = op mod 
      | getOp oper = raise Fail ("Unsupported operator "^oper) 
  
  fun eval vtable (Constant i) = i 
      | eval vtable (Variable s) = lookup ... 
      | eval vtable (Operator (oper, exp1, exp2)) = 
       getOp oper (eval vtable exp1, eval vtable exp2) 
  

  不幸的是，你的语法树需要对无效值进行大量的探测。

• 如果这是作业，请记住在源代码中进行适当的版权归属。;-)