Lisp evaluation of let statements

Question

I am writing a Scheme interpreter, and I am faced with a valid let statement such as:

;; should print 7
(let ((a 4) (b 3))
    (let ((a (* a a)) 
          (b (* b b)))
       (+ a b)
       (- a b)))

My interpreter implements only a purely functional subset of Scheme, so there will be no side effects such as set!. In a purely functional language, why would you allow multiple expressions inside of a let statement such as above?

And in writing my interpreter, is there any reason I should evaluate anything but the last expression in the let? It seems they could never affect the outcome of the last statement evaluated.

Answer 1

Okay, the let is just creating a binding, like a define. There's nothing there that is changing a bound variable like set! would. So now, think about what the scope of your names is: is the a of the '(+ a b) the same as the a` you bound to 4? (Hint: no.)

The real point here is that you need to behave correctly even in hinky cases like this: the scoping and binding rules are simple and well-defined, and doing something like this, which looks confusing, is just a consequence of them. It's convenient, because by having local lexically scoped bindings with let, you can write clearer programs, even if there are perverse side cases.

update Oh, I left off a point. You're right that the (+ a b) invocation has no lasting effect, but then you can't in the general case assume that would be true, and you can't determine whether it's true by examining the program text there alone. (Consider: there could be other functions there in place of "+".) On the rest of it, though, if you think you will get the correct result without evaluating the various let clauses, you don't understand what it's trying to do yet.

Answer 2

You're right (almost): if you're implementing a purely functional subset of Scheme (i.e. no set!, set-car!, set-cdr!) then any expression but the last in a let will have their return value thrown away, and since you're guaranteed not to have side effects, there's no danger in silently ignoring them.

However, there is one small case you need to consider, and that is when the preceding expressions are defines:

(let ((x 3))
  (define y 4)
  (+ x y))

This is both legal and functional. However, there is some good news - inside a block (like a let) you have to have all your defines at the top. As in, this is not considered legal Scheme:

(let ((x 3))
  (+ 2 3)
  (define y 4)
  (+ x y))

This means that when evaluating a block, all you have to do is scan the top for defines and wrap them up into the equivalent letrec expression, then proceed to ignore all but the last expression (which you would then return).

edit: antti.huima makes an excellent point about call/cc. If you're going to include continuations in your implementation, you really can't make many assumptions about when things will be evaluated.

Answer 3

Hi,

actually you cannot "drop" all but the last statement, because the previous statements could be non-terminating. For example:

(define (func) (func))

(let ()
  (func) ;; does not return
  1)

Here if you leave (func) unevaluated, you get the wrong result (which is 1), whereas you should get non-terminating computation.

Another issue is that call/cc (call-with-current-continuation) (and yes, it belongs to the functional subset) can be used to actually return from the computation from non-tail position, e.g.:

(call-with-current-continuation
  (lambda (ret)
    (let ()
      (ret 3)
      4)))

which will return 3 and not 4. This is still purely functional.

Note BTW that (let () x y z) is equivalent to the single-statement form (let () (begin x y z)) so the real question is if you need begin :)