Applying "let" in scheme?

Question

I am trying to write an interpreter for scheme. So far i implemented define, if and some arithmetic expressions. Here is the grammar for my interpreter:

<s6> -> <expr>
        | <define>

<expr> -> NUMBER
          | IDENT
          | <if>
          | <let>

<define> -> ( define IDENT <expr> )

<if> -> ( if <expr> <expr> <expr> )

<let> -> ( let ( <var_binding_list> ) <expr> )

<var_binding_list> -> ( IDENT <expr> ) <var_binding_list>
                      | ( IDENT <expr> )

Here is the code i have written so far:

(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 let-stmt? (lambda (e)
(and (list? e) (equal? (car e) 'let) (= (length e) 3))))

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

(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? (cadr e) 0) ( s6-interpret (cadddr e) env) ( s6-interpret(caddr e) env)))
    ((let-stmt? e) (apply let (map s6-interpret (cdr e))))
    (else
        (let ((operands (map s6-interpret (cdr e) (make-list (length (cdr e)) env)))
                (operator (get-operator (car e))))
            (apply operator operands))))))


(define cs305-interpreter (lambda () (repl '())))

Everything i have written except "let" works fine. let-stmt? procedure also works as i want but the part of the code ((let-stmt? e) (apply let (map s6-interpret (cdr e)))) in s6-interpret does not work fine, it gives me an error saying that "syntactic keyword may not be used as an expression". Can anyone help me with the implementation of the interpreter for "let" statement as given in the grammar?

Thank you

Answer 1

It is easy to implement let without worrying about lambda as let just extends the environment and evaluates the body in the newly extended environment. As so:

...
((let-stmt? e)
 (let ((names (map car  (cadr e)))
       (inits (map cadr (cadr e))))
   ;; Evaluate inits in env
   (let ((vals (map (lambda (init) (s6-interpret init env)) inits)))
     ;; Extend env with names+vals
     (let ((new-env (append (map cons names vals) env)))
       ;; Eval body in new env
       (s6-interpret (caddr e) new-env)))))   ; assumes 'body' is one form...
...

You also get to avoid worrying about general function calls using this approach.

Answer 2

You can't apply the special form let. The error is clear: it's not a procedure, it's syntax (a macro). One possible solution would be to implement a syntactic transformation at the evaluator level, once a let is detected, transform it into a lambda expression and evaluate it.

Take a look at exercise 4.6 in SICP, look for the topic "Derived Expressions". The key idea here is that if you find an expression such as this one:

(let ((x 1)
      (y 2))
  (+ x y))

You must transform it into this expression, that can be easily evaluated:

((lambda (x y)
   (+ x y))
 1 2)