在Scheme中實現lambda語句？

Question

我正在嘗試爲Scheme使用Scheme編寫一個解釋器，我實現瞭如果讓定義語句和一些其他數值操作，但我不知道如何開始實現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開始，題爲「代表程序」和「組合」的章節下，參考鏈接的書都引用代碼。基本上，您必須在eval中添加兩個額外的案例，一個用於評估lambda表達式（很簡單！），另一個用於實際執行它們：最後一個必須檢查被評估的表達式是否爲過程應用程序，如果是這樣，則評估操作符和操作數列表，然後將操作符應用於這些操作數。

下面是它的要點，注意評估lambda形式是非常簡單的，有趣的部分是apply的實現中，根據操作類型調用任一個原始程序或上的化合物方法（a 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))))