球拍：（评估 t lst）

Question

我实现了一个接受算术表达式和 returns 值的函数：

; an arithmetic expression (t) is one of the following:
; - a number
; - a list of the form '(a operator b) where a and b are arithmetic expressions
; arithmetic expression -> number

; computes the value of the arithmetic expression

(define (eval t)
  (cond
    [(number? t) t]
    [else ((cond
            [(equal? (second t) '+) +]
            [(equal? (second t) '-) -]
            [(equal? (second t) '*) *]
            [(equal? (second t) '/) /])
           (eval (first t)) (eval (third t)))]))

它工作得很好，但显然它不能接受常量。所以我想做的是扩展程序，使其适用于类似的东西：

(eval '(1 + (3 * x)) (make-const 'x 3)                     -> 10
(eval '((3 - x) * y) ((make-const 'x 1) (make-const 'y 2)) -> 4
(eval '(1 + (y * x)) (make-const 'x 3)                     -> "error"

我的想法是定义一个结构：

(define struct const (symbol number))


(define (eval. t x)
  (cond
    [(number? t) t]
    [(symbol?  t) ???]
    [else ((cond
            [(equal? (second t) '+) +]
            [(equal? (second t) '-) -]
            [(equal? (second t) '*) *]
            [(equal? (second t) '/) /])
           (eval. (first t) lst) (eval. (third t) lst))]))

任何人都可以告诉我我的方向是否正确并且可能会给我提示吗？将不胜感激！

Answer 1

首先，请注意您的示例略有错误：

(eval '(1 + (3 * x)) (make-const 'x 3)
; you need a closing parenthesis

(eval '((3 - x) * y) ((make-const 'x 1) (make-const 'y 2))
; same as above. also, ((make-const 'x 1) (make-const 'y 2)) doesn't make
; sense. Do you mean (list (make-const 'x 1) (make-const 'y 2))

无论如何，有两种方法可以做到这一点。

第一种方法是让eval有两个阶段：第一个阶段是先代入所有变量。如果一切顺利，你会得到一个没有标识符的表达式。第二步是调用你的第一个版本 eval（我将在这里称为 eval-helper）。

; eval :: expr, listof const -> number
(define (eval t vars)
  (eval-helper (subst-all t vars)))

确实，困难的部分是 subst-all 正确。为了简化事情，您可能想要编写一个名为 subst 的函数，它一次只替换一个标识符。这可以通过对表达式进行递归并在符号匹配时用数字替换符号来完成。然后 subst-all 可以使用 subst 作为辅助函数。

（这样怎么知道有没有未绑定的标识符？）

第二种方法是遵循您的代码模板：

(define struct const (symbol number))

(define (eval t env)
  (cond
    [(number? t) t]
    [(symbol?  t) ???]
    [else ((cond
            [(equal? (second t) '+) +]
            [(equal? (second t) '-) -]
            [(equal? (second t) '*) *]
            [(equal? (second t) '/) /])
           (eval (first t) env) (eval (third t) env))]))

按照规范，此函数的第二个参数（例如 (list (make-const 'x 1) (make-const 'y 2))）称为 environment。当您看到一个符号时，您只需查找环境和 return 与您正在查找的符号关联的值。

; lookup :: symbol, listof const -> number
(define (lookup sym env)
  (cond
   [(empty? env) ???]
   [else (if (equal? sym (const-symbol (first env)))
             ??? ; you want to return the value!
             ??? ; recursively call lookup on the rest of the environment
             )]))

（这样怎么知道有没有未绑定的标识符？）

另请参阅：

球拍：（评估 t lst）

racket: (evaluate t lst)

eval

arithmetic-expressions

racket