Applying "let" in scheme?

1
votes

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

2
schemeinterpreterlet
Can you repost after you get the above to compile and run w/o an argument count error? - GoZoner
@GoZoner well, actually i am still thinking about how to implement let statement, i could not solve it. You mean reposting after solving it? - yrazlik
Just like you cannot apply if you cannot apply let. let is actually just syntactic sugar for a anonymous procedure so you should implement lambda-calls first, like ((lambda (x) x) 5) should evaluate to 5. Then you can implement so that (let ((x 5)) x) is synonymous to that. - Sylwester
You shouldn't implement let before implementing lambda. let is not a normal form, it's a derived expression that after a syntactical transformation gets evaluated as a lambda. - Óscar López

2 Answers

4
votes

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)
1
votes

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.