符号表将一些信息与每个符号相关联。在解释器中,您可能会将值与符号相关联。Map
是一种特别适用于函数式解释器的实现。
如果您想优化您的解释器,请在运行时摆脱对符号表的需求。一种方法是De Bruijn idexing。
还有一些关于从函数式解释器机械派生优化解释器、VM 和编译器的很好的文献,例如:
http://www.brics.dk/RS/03/14/BRICS-RS-03-14.pdf
举个简单的例子,考虑使用 De Bruijn 索引编码的常量的 lambda 演算。请注意,评估器没有符号表,因为它可以使用整数进行查找。
type exp =
| App of exp * exp
| Const of int
| Fn of exp
| Var of int
type value =
| Closure of exp * env
| Number of int
and env = value []
let lookup env i = Array.get env i
let extend value env = Array.append [| value |] env
let empty () : env = Array.empty
let eval exp =
let rec eval env exp =
match exp with
| App (f, x) ->
match eval env f with
| Closure (bodyF, envF) ->
let vx = eval env x
eval (extend vx envF) bodyF
| _ -> failwith "?"
| Const x -> Number x
| Fn e -> Closure (e, env)
| Var x -> lookup env x
eval (empty ()) exp