ocaml - OCaml/ML 中的评估器

Question

type bool_exp =
    TT
  | FF
  | Var of string
  | And of bool_exp * bool_exp
  | Not of bool_exp ;;

 eval : bool_exp -> (string -> bool) -> bool

我正在尝试编写一个名为eval. 我对 OCaml 很陌生，不习惯这种语法。我可以从哪里开始写这篇文章？

Answer 1

使用像您这样的数据类型时的主要设备bool_exp是模式匹配。也就是说，对于您的函数输入的每种可能情况，您分别指定其行为。您的功能的骨架eval可能看起来像

let rec eval e env =
  match e with
    TT -> ...
  | FF -> ...
  | Var x -> ...
  | And (e1, e2) -> ...
  | Not e
;;

第一个参数e是应该被评估的表达式，第二个env通常称为环境，将变量（由字符串表示）映射到值（这里只是布尔常量）。

每当定义的rec函数是递归的（即在函数体中使用自身）时都需要 ，并且由于您的数据类型是递归定义的，因此也eval将是递归的。例如，为了评估And (e1, e2)，您首先必须知道相同环境的值e1和wrt。e2

这应该让你开始。

Answer 2

继续 Chris 的回答，您的函数看起来非常像这样：

let rec eval e env =
  match e with
    TT -> true
  | FF -> false
  | Var x -> x env
  | And (e1, e2) -> (eval e1 env) && (eval e2 env)
  | Not e -> not (eval e env) ;;

然后在运行代码进行测试时，您将声明一个名为 env 的函数，如下所示：

let env y = true;;

或者...

let env y = false;;

由于类型是“eval : bool_exp -> (string -> bool) -> bool”，因此在使用函数之前，您需要定义 (string -> bool) 的函数是什么。

所以，

1. Declare data type bool_exp.
2. Declare that function I gave you.
3. Declare env as a function, either one you want, there's only two possible ones.
4. You can now use the function.

祝你快乐的函数式编程。=)