3

I'm learning Lisp, and I've just gotten to let, which I don't quite understand (the implementation of).

A common definition for it is given in terms of lambda as a macro. However, nowhere have I seen that let must be implemented as a macro or in terms of lambda.

Is it possible to define let without using a macro or lambda?

I know it can be implemented as a primitive, but I want to know whether it can be implemented in Lisp without creating a macro -- by creating a special form or a function.

Improve this question
6
  • I'm asking because it seems to me that macros are 'outside' the runtime environment.
    – user39685
    Commented Jul 2, 2012 at 0:39
  • 2
    You either have it as an axiom, or you have to define it as a rewrite rule (i.e., a macro) lowering to some existing primitive forms. There is no other way, and there should not be any alternatives. It is just clean, simple and beautiful.
    – SK-logic
    Commented Jul 2, 2012 at 9:15
  • there is no other way, there should not be any alternatives -- do you have links where I can read more about these statements? Otherwise I just have to take your word for it.
    – user39685
    Commented Jul 2, 2012 at 10:34
  • it is pretty easy to prove - take a look at the semantics of the lexically scoped names (any decent book on denotational semantics would cover this topic). In the pure lambda calculus names are only introduced as lambda arguments - i.e., if your language is based on it, any name declaration facility have to translate to an explicit lambda. Otherwise, if you do not want to use this axiom, it is pretty obvious you have to introduce a new one, with a similar name handling semantics.
    – SK-logic
    Commented Jul 2, 2012 at 11:00
  • links please ...
    – user39685
    Commented Jul 2, 2012 at 11:45

3 Answers 3

Reset to default
5

It is not strictly necessary that let must be implemented as a macro. It would be possible for let to be defined as a primitive form, where the expression evaluator understands directly what let is supposed to mean.

However, since Lispers are typically a minimalist bunch, let is usually defined in terms of existing facilities (a macro and lambda). This kind of definition saves having to do extra work. For example, in Scheme R5RS, the let construct is defined as "library syntax":

library syntax: (let <bindings> <body>)

where library syntax means:

To aid in understanding and implementing Scheme, some features are marked as library. These can be easily implemented in terms of the other, primitive, features.

Improve this answer
2
  • Good point about implementing it as a primitive. I have to apologize for an unclear question though: what I actually wanted to know was whether let can be implemented in Lisp (i.e. not as a primitive) without using a macro.
    – user39685
    Commented Jul 2, 2012 at 10:26
  • 2
    @MattFenwick: Oh I see. The answer is no, because if it isn't a macro, its arguments will be evaluated, and you can't evaluate let bindings (they are not expressions).
    – Greg Hewgill
    Commented Jul 2, 2012 at 19:48
4

Typically, "no". LET mixes evaluated and unevaluated forms, in a way that's hard to deal with without some kind of rewriting. So, if it's not a special form (that is, a form that is treated in a uniqeu way by the evaluator), it probably needs to be a macro.

Saying that, the transformation is (relatively) easy.

(let ((var1 value1) (var2 value2) ...) body)

is simply turned into:

((lambda (var1 var2 ...) body) value1 value2 ...)

So even if you can't implement LET without macros, you can certainly implement the same functionality (local, lexical bindings) without anything special.

Improve this answer
0

For beginners nested function calls like the following might be very difficult to understand:

 (+ (fibonacci (- N 1)) (fibonacci (- N 2)))))

To make such expressions easier to write and comprehend, one could define local name bindings to represent intermediate results: (

let
    ((F1 (fibonacci (- N 1)))
     (F2 (fibonacci (- N 2))))
      (+ F1 F2))

The let special form above defines two local variables, F1 and F2, which binds to Fib(N-1) and Fib(N-2) respectively. Under these local bindings, let evaluates (+ F1 F2). The fibonacci function can thus be rewritten as follows:

(defun fibonacci (N)
  "Compute the N'th Fibonacci number."
  (if (or (zerop N) (= N 1))
      1
    (let
    ((F1 (fibonacci (- N 1)))
     (F2 (fibonacci (- N 2))))
      (+ F1 F2))))
Improve this answer
1
  • 1
    I just want to clarify that I'm looking for a clarification of the implementation, not the use, of let.
    – user39685
    Commented Jul 2, 2012 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.