我用 Moonscript Lua 编写了一个简单的 Lisp 解释器。 评估器看起来像这样:
eval = ( env, expr ) ->
if is_symbol expr
lookup env, expr
elseif is_define expr
eval_define env, expr
elseif is_lambda expr
eval_lambda env, expr
else call (map (partial eval, env), expr)
效果很好。 但现在我真的很想以如下方式追踪整个过程:
(+ (+ a b) (+ a c))
(+ (+ 1 2) (+ 1 4))
(+ 3 5)
8
问题是,由于求值过程是递归的,所以我永远无法打印出整个表达式。
我是否必须以命令式方式重写评估器,或者我是否遗漏了一些明显的东西?
最佳答案
这个答案是使用 Common Lisp,因为我不太了解 Lua。
实际轨迹
通常,您希望跟踪代码中实际发生的情况。 以下是您的函数的重写以及跟踪工具可以执行的操作的示例:
(defun normal-eval (form env)
(etypecase form
(cons (destructuring-bind (op . args) form
(apply op
(mapcar (lambda (u)
(normal-eval u env))
args))))
(null nil)
(symbol (cdr (assoc form env)))
(t form)))
> (trace normal-eval)
> (normal-eval '(+ (+ 1 3 a) 2) '((a . 5)))
0: (NORMAL-EVAL (+ (+ 1 3 A) 2) ((A . 5)))
1: (NORMAL-EVAL (+ 1 3 A) ((A . 5)))
2: (NORMAL-EVAL 1 ((A . 5)))
2: NORMAL-EVAL returned 1
2: (NORMAL-EVAL 3 ((A . 5)))
2: NORMAL-EVAL returned 3
2: (NORMAL-EVAL A ((A . 5)))
2: NORMAL-EVAL returned 5
1: NORMAL-EVAL returned 9
1: (NORMAL-EVAL 2 ((A . 5)))
1: NORMAL-EVAL returned 2
0: NORMAL-EVAL returned 11
所需的轨迹
据我所知,没有简单的方法可以通过您提供的代码获得您想要的输出。 但是,如果您愿意更改代码,则只需逐步重写该术语,就可以以纯函数的方式获得所需的跟踪。然而,你必须防止评估一个已经被评估过的术语,以便让形式逐渐改变。
(defun s-eval (x env)
(etypecase x
(cons (destructuring-bind (new-list . some-evalp)
(reduce
(lambda (element R)
(destructuring-bind (rec-list . some-evalp) R
(multiple-value-bind (value evalp) (s-eval element env)
(cons (list* value rec-list)
(or some-evalp evalp)))))
(rest x)
:from-end t
:initial-value (cons nil nil))
(values
(if some-evalp
;; a least one element required some work
;; so we return the modified term.
(cons (first x) new-list)
;; all elements are literal, we can actually
;; replace this form by its evaluation
(apply (first x) new-list))
T)))
(null (values nil nil))
(symbol (values (cdr (assoc x env)) t))
(t (values x nil))))
(defun step-eval (form &optional env)
(print form)
(multiple-value-bind (value evalp)
(s-eval form env)
(if evalp
(step-eval value env)
value)))
> (step-eval '(+ (+ 1 3 a) 2) '((a . 5)))
(+ (+ 1 3 A) 2)
(+ (+ 1 3 5) 2)
(+ 9 2)
11
> (step-eval '(+ (+ 1 3 a) (* b a)) '((a . 5) (b . 0)))
(+ (+ 1 3 A) (* B A))
(+ (+ 1 3 5) (* 0 5))
(+ 9 0)
9
> (step-eval '(+ (+ a b) (+ a c)) '((a . 1)
(b . 2)
(c . 4)))
(+ (+ A B) (+ A C))
(+ (+ 1 2) (+ 1 4))
(+ 3 5)
8
S-EVAL
在环境中评估表单并返回两个值:表单的评估和一个 bool 值,指示是否实际发生了某些评估或者该术语是否已发生 self 评估(字面意思)。此 bool 值用于防止转换通过递归计算转换子项的项。
STEP-EVAL
打印表单并调用 S-EVAL
,然后递归调用自身直至评估终止。
关于lua - 追踪递归求值器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38559402/