lambda - 在 Scheme 中实现 lambda 语句？

Question

我正在尝试使用 Scheme 为 Scheme 编写解释器，我实现了 if let define 语句和一些其他数值操作，但我不知道如何开始实现 lambda 过程。下面是我目前的情况。如果您能指出正确的方向，我们将不胜感激。

(define get-operator (lambda (op-symbol)
  (cond
    ((equal? op-symbol '+) +)
    ((equal? op-symbol '-) -)
    ((equal? op-symbol '*) *)
    ((equal? op-symbol '/) /)
    (else (error "s6-interpret: operator not implemented -->" op-symbol)))))

(define if-stmt? (lambda (e)
  (and (list? e) (equal? (car e) 'if) (= (length e) 4))))

(define letstar-stmt? (lambda (e)
  (and (list? e) (equal? (car e) 'letstar) (= (length e) 3))))

(define let-stmt? (lambda (e)
  (and (list? e) (equal? (car e) 'let) (= (length e) 3))))

(define define-stmt? (lambda (e)
  (and (list? e) (equal? (car e) 'define) (symbol? (cadr e)) 
                                            (= (length e) 3))))

(define get-value (lambda (var env)
  (cond
    ((null? env) (error "s6-interpret: unbound variable -->" var))
    ((equal? (caar env) var) (cdar env))
    (else (get-value var (cdr env))))))

(define extend-env (lambda (var val old-env)
  (cons (cons var val) old-env)))

(define repl (lambda (env)
  (let* (
    (dummy1 (display "cs305> "))
    (expr (read))
    (new-env (if (define-stmt? expr)
               (extend-env (cadr expr) (s6-interpret (caddr expr) env) env)
               env))
    (val (if (define-stmt? expr)
           (cadr expr)
           (s6-interpret expr env)))
    (dummy2 (display "cs305: "))
    (dummy3 (display val))
    (dummy4 (newline))
    (dummy4 (newline)))
   (repl new-env))))

(define s6-interpret (lambda (e env)
  (cond
    ((number? e) e)
    ((symbol? e) (get-value e env))
    ((not (list? e)) (error "s6-interpret: cannot evaluate -->" e))
    ((if-stmt? e) (if (eq? (s6-interpret (cadr e) env) 0) 
                    ( s6-interpret (cadddr e) env) 
                    ( s6-interpret (caddr e) env)))
    ((let-stmt? e)
      (let ((names (map car  (cadr e)))
            (inits (map cadr (cadr e))))
        (let ((vals (map (lambda (init) (s6-interpret init env)) 
                         inits)))
          (let ((new-env (append (map cons names vals) env)))
            (s6-interpret (caddr e) new-env)))))
    (else
      (let ((operands (map s6-interpret (cdr e)
                        (make-list (length (cdr e)) env)))
            (operator (get-operator (car e))))
        (apply operator operands))))))

(define cs305 (lambda () (repl '())))

Answer 1

您将在 SICP 中找到所有开始所需的信息。 ，在标题为“Representing procedures”和“Combinations”的部分下，请参阅链接的书籍以获取所有引用代码。

基本上，您必须在 eval 中添加两个额外的情况，一个用于评估 lambda 表达式(很简单!)，另一个用于实际执行它们:最后一个必须检查正在评估的表达式是否是过程应用程序，如果是，它会评估(即找到值)运算符和操作数列表，然后将运算符的值应用于这些操作数的值。

这是它的要点，请注意评估 lambda 形式非常简单，有趣的部分是 apply 的实现，根据运算符类型调用操作数上的原始过程或复合过程(lambda)——反过来，应用复合过程需要评估其指令序列并捕获和扩展其环境。您必须根据自己的实现进行调整:

(define (eval exp env)
  (cond ... ; other cases
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ... ; other cases
        ((application? exp)
         (apply (eval (operator exp) env) ; eval calls apply
                (list-of-values (operands exp) env)))
        (else (error "Unknown expression type -- EVAL" exp))))

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence ; apply calls eval
          (procedure-body procedure)
          (extend-environment
           (procedure-parameters procedure)
           arguments
           (procedure-environment procedure))))
        (else (error "Unknown procedure type -- APPLY" procedure))))

(define (lambda? exp)
  (tagged-list? exp 'lambda))

(define (compound-procedure? p)
  (tagged-list? p 'procedure))

(define (make-procedure parameters body env)
  (list 'procedure parameters body env))

(define (list-of-values exps env)
  (if (no-operands? exps)
      '()
      (cons (eval (first-operand exps) env)
            (list-of-values (rest-operands exps) env))))

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

(define (extend-environment vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (make-frame vars vals) base-env)
      (if (< (length vars) (length vals))
          (error "Too many arguments supplied" vars vals)
          (error "Too few arguments supplied" vars vals))))