跟踪递归计算器

Question

我在 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

问题是，由于计算过程是递归的，所以我根本没有要打印出的整个表达式。

我是否必须以命令式风格重写求值器，还是我遗漏了一些明显的东西？

Answer 1

这个答案使用的是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 评估环境中的表单和 returns 两个值：表单的评估和一个布尔值，指示是否实际发生或如果该术语是自我评估的（文字）。此布尔值用于防止转换子项已通过递归评估进行转换的项。 STEP-EVAL 打印表单并调用 S-EVAL，然后递归调用自身直到计算终止。

跟踪递归计算器

Tracing a recursive evaluator

lisp

evaluation

lua

trace

interpreter

实际轨迹

所需的轨迹