CODEWITHSUNDEEP
lambdaschemelambda-calculuslet
user3100209
user3100209

Reputation: 367

How to implement let* using lambda

I am doing lambda calculus and in my textbook, it says how would your write let* using lambda calculus.

My answers: x, y and z are the parameters; v1, v2 and v3 the arguments; e is the body:

((lambda (x y z) (e)) v1 v2 v3)

Answer in the book:

  ((lambda(x)
    ((lambda(y)
      ((lambda(z) e) v3))
      v2))
    v1)

I'm not sure if my answer is equivalent. If not, why is my answer wrong and how can the original answer be derived?

Upvotes: 2

Views: 387

Answers (2)

C. K. Young
C. K. Young

Reputation: 223013

Istvan's answer is correct, but basically, the difference between your code and your textbook's is the difference between let and let*. Basically, let* is a nested series of lets, and in fact, a typical definition of let* is as follows:

(define-syntax let*
  (syntax-rules ()
    ;; if no bindings, same as let
    ((let* () body ...)
     (let () body ...))

    ;; otherwise, take one binding, then nest the rest
    ((let* (binding next ...) body ...)
     (let (binding)
       (let* (next ...)
         body ...)))))

Upvotes: 0

lily
lily

Reputation: 2998

Update 2: I've realized that my original answer was correct and rolled back to the original, but will add some clarifying notes.

In Scheme, let* allows later values to depend on earlier ones. So for instance, you can write (in the usual syntax):

(let* ((foo 3)
       (bar (+ foo 1))
       (baz (* bar 2)))
  (* foo bar baz))

which binds foo to 3, bar to 4, baz to 8, and returns 72. Your textbook's implementation allows for this.

However, your implementation doesn't allow this- it requires all the values to be evaluated independently. It is, however, a correct implementation of let, just not of let*.

The way your textbook's answer works is that the earlier values are bound before later ones. So for instance, the above code in the textbook's implementation is as follows:

((lambda (foo)
  ((lambda (bar)
    ((lambda (baz) (* foo bar baz)) (* bar 2)))
    (+ foo 1)))
  3)

However, if you try to use your implementation in the same way:

((lambda (foo bar baz) (* foo bar baz)) 8 (+ foo 1) (* bar 2))
; Error - foo and bar aren't bound

then the foo in (+ foo 1) will be unbound, as foo isn't in scope there (same for the bar in (* bar 2).

As a side note, the (e) in your implementation should really just be e, as in the textbook's implementation; the former is a thunk call, while the latter is just an expression.

Upvotes: 10

Related Questions