Реализация лямбда-заявления на схеме?

Question

Я пытаюсь написать интерпретатор для Схемы с использованием Схемы, я реализовал, если разрешить определение операторов и некоторых других числовых операций, но я понятия не имею, как начать реализацию лямбда-процедуры. Ниже моя текущая ситуация. Было бы очень признательно, если бы вы могли указать мне в правильном направлении.

(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 формы действительно просто, интересная часть является реализация 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))))