LET versus LET* in Common Lisp

Question

I understand the difference between LET and LET* (parallel versus sequential binding), and as a theoretical matter it makes perfect sense. But is there any case where you've ever actually needed LET? In all of my Lisp code that I've looked at recently, you could replace every LET with LET* with no change.

Edit: OK, I understand why some guy invented LET*, presumably as a macro, way back when. My question is, given that LET* exists, is there a reason for LET to stay around? Have you written any actual Lisp code where a LET* would not work as well as a plain LET?

I don't buy the efficiency argument. First, recognizing cases where LET* can be compiled into something as efficient as LET just doesn't seem that hard. Second, there are lots of things in the CL spec that simply don't seem like they were designed around efficiency at all. (When's the last time you saw a LOOP with type declarations? Those are so hard to figure out I've never seen them used.) Before Dick Gabriel's benchmarks of the late 1980's, CL was downright slow.

It looks like this is another case of backwards compatibility: wisely, nobody wanted to risk breaking something as fundamental as LET. Which was my hunch, but it's comforting to hear that nobody has a stupidly-simple case I was missing where LET made a bunch of things ridiculously easier than LET*.

Answer 1

LET itself is not a real primitive in a Functional Programming Language, since it can replaced with LAMBDA. Like this:

(let ((a1 b1) (a2 b2) ... (an bn))
  (some-code a1 a2 ... an))

is similar to

((lambda (a1 a2 ... an)
   (some-code a1 a2 ... an))
 b1 b2 ... bn)

But

(let* ((a1 b1) (a2 b2) ... (an bn))
  (some-code a1 a2 ... an))

is similar to

((lambda (a1)
    ((lambda (a2)
       ...
       ((lambda (an)
          (some-code a1 a2 ... an))
        bn))
      b2))
   b1)

You can imagine which is the simpler thing. LET and not LET*.

LET makes code understanding easier. One sees a bunch of bindings and one can read each binding individually without the need to understand the top-down/left-right flow of 'effects' (rebindings). Using LET* signals to the programmer (the one that reads code) that the bindings are not independent, but there is some kind of top-down flow - which complicates things.

Common Lisp has the rule that the values for the bindings in LET are computed left to right. Just how the values for a function call are evaluated - left to right. So, LET is the conceptually simpler statement and it should be used by default.

Types in LOOP? Are used quite often. There are some primitive forms of type declaration that are easy to remember. Example:

(LOOP FOR i FIXNUM BELOW (TRUNCATE n 2) do (something i))

Above declares the variable i to be a fixnum.

Richard P. Gabriel published his book on Lisp benchmarks in 1985 and at that time these benchmarks were also used with non-CL Lisps. Common Lisp itself was brand new in 1985 - the CLtL1 book which described the language had just been published in 1984. No wonder the implementations were not very optimized at that time. The optimizations implemented were basically the same (or less) that the implementations before had (like MacLisp).

But for LET vs. LET* the main difference is that code using LET is easier to understand for humans, since the binding clauses are independent of each other - especially since it is bad style to take advantage of the left to right evaluation (not setting variables as a side effect).

Answer 2

You don't need LET, but you normally want it.

LET suggests that you're just doing standard parallel binding with nothing tricky going on. LET* induces restrictions on the compiler and suggests to the user that there's a reason that sequential bindings are needed. In terms of style, LET is better when you don't need the extra restrictions imposed by LET*.

It can be more efficient to use LET than LET* (depending on the compiler, optimizer, etc.):

• parallel bindings can be executed in parallel (but I don't know if any LISP systems actually do this, and the init forms must still be executed sequentially)
• parallel bindings create a single new environment (scope) for all the bindings. Sequential bindings create a new nested environment for every single binding. Parallel bindings use less memory and have faster variable lookup.

(The above bullet points apply to Scheme, another LISP dialect. clisp may differ.)

Answer 3

I come bearing contrived examples. Compare the result of this:

(print (let ((c 1))
         (let ((c 2)
               (a (+ c 1)))
           a)))

with the result of running this:

(print (let ((c 1))
         (let* ((c 2)
                (a (+ c 1)))
           a)))

Answer 4

In LISP, there's often a desire to use the weakest possible constructs. Some style guides will tell you to use = rather than eql when you know the compared items are numeric, for example. The idea is often to specify what you mean rather than program the computer efficiently.

However, there can be actual efficiency improvements in saying only what you mean, and not using stronger constructs. If you have initializations with LET, they can be executed in parallel, while LET* initializations have to be executed sequentially. I don't know if any implementations will actually do that, but some may well in the future.

Answer 5

The main difference in Common List between LET and LET* is that symbols in LET are bound in parallel and in LET* are bound sequentially. Using LET does not allow the init-forms to be executed in parallel nor does it allow the order of the init-forms to be changed. The reason is that Common Lisp allows functions to have side-effects. Therefore, the order of evaluation is important and is always left-to-right within a form. Thus, in LET, the init-forms are evaluated first, left-to-right, then the bindings are created, left-to-right in parallel. In LET*, the init-form is evaluated and then bound to the symbol in sequence, left-to-right.

CLHS: Special Operator LET, LET*

Answer 6

I was recently writing a function of two arguments, where the algorithm is expressed most clearly if we know which argument is larger.

(defun foo (a b)
  (let ((a (max a b))
        (b (min a b)))
    ; here we know b is not larger
    ...)
  ; we can use the original identities of a and b here
  ; (perhaps to determine the order of the results)
  ...)

Supposing b was larger, if we'd used let*, we would have accidentally set a and b to the same value.

Answer 7

i go one step further and use bind that unifies let, let*, multiple-value-bind, destructuring-bind etc., and it's even extensible.

generally i like using the "weakest construct", but not with let & friends because they just give noise to the code (subjectivity warning! no need to try convincing me of the opposite...)

Answer 8

(let ((list (cdr list))
      (pivot (car list)))
  ;quicksort
 )

Of course, this would work:

(let* ((rest (cdr list))
       (pivot (car list)))
  ;quicksort
 )

And this:

(let* ((pivot (car list))
       (list (cdr list)))
  ;quicksort
 )

But it's the thought that counts.

Answer 9

Presumably by using let the compiler has more flexibility to reorder the code, perhaps for space or speed improvements.

Stylistically, using parallel bindings shows the intention that the bindings are grouped together; this is sometimes used in retaining dynamic bindings:

(let ((*PRINT-LEVEL* *PRINT-LEVEL*)
      (*PRINT-LENGTH* *PRINT-LENGTH*))
  (call-functions that muck with the above dynamic variables)) 

Answer 10

There is definitely an efficiency argument between let and let*. But the main reason why we have let is historic, due to the relationship with lambda.

let is easier, simpler and more efficient to implement in a code-walking Lisp interpreter. This is particularly true if there is some half decent data structure for environments, rather than just an assoc list.

Suppose that the interpreter implements environments as a chain of objects. So for isntance (let (a b) (let (c d) (let (e f)))) will add three environment nodes to the environment chain. Each of these new nodes contains two bindings (in an individual list, or hash table or whatever).

When we interpret the let form, we can evaluate all of the initializing expressions in the incoming environment chain. We can create a single environment node for all of the new bindings, in a single operation, and populate the bindings with the values.

When we interpret the let* form, we cannot do this. For each successive binding mentioned in the let*, we have to call make-environment, populate it, and add it to the environment chain, so that we then interpret the next initialization form in the extended environment.

This leads to a degenerate run-time environment structure. Whereas (let (a b c d ...)) produces one environment object with a nice hash table in it, (let* (a b c d ...)) produces an inefficient chain that requires O(n) traversal to find a binding.

We can erase the difference between the interpreter performance of let and let*, but only by dragging the performance of let down to let*. If we represent the environment chain as a naive assoc list, then this issue doesn't matter; all variable lookups are a linear search. In fact let* is then easier to implement: evaluate each init expression, and push a new binding onto the current environment.

Now, enter compilation into the picture. A Lisp compiler can use a devilish trick to implement let* by just making a few tweaks to the compilation strategy for let. To compile let*, we can allocate a single environment for all the bindings (a move which would result in incorrect scoping in the interpreter). We leave that environment empty, and add it to the compile-time environment chain. We thus compile the init expressions in the scope of that new environment. As we iterate over the init expressions to compile them, we add each corresponding variable to that environment one by one, so that the compilation of subsequent init expressions will have that variable in scope.

let* is a simple hack that becomes obvious when you have a Lisp compiler that handles let.

A Lisp compiler easily produces efficient representations of environments, regardless of scoping rules, which is not necessarily true of an interpreter.

Since interpreters came first, that explains why let is parallel. At least partially. The other reason is that let was realized as a syntactic sugar over lambda. But lambda (originally) oes not have initializing expressions at all in its own scope; it just specifies variables. The lambda expression produces a run-time object, such that the binding of the values to the parameters happens at run time, when the function is invoked. The evaluation of the argument expressions is in a totally different scope.

Now in the immediately-called lambda, this is still true: the scope of the expressions is entirely outside of the lambda:

((lambda (a b) (+ a b)) 1 2)

The expressions 1 and 2 have nothing to do with the lambda; they are not enclosed in it.

So it is obvious that if we want a let sugar notation which corresponds to the above, we must carefully preserve this property:

(let ((a 1) (b 2))
  (+ a b))

If we want this let to be the same as the previous lambda, we must make it look as if a and b are function parameters, and 1 and 2 are argument expressions.

If you're a researcher working with a language that has lambda and no let, longing for a nicer way to write immediately-called lambdas, it is unlikely that you will invent let* binding semantics. You will invent something that has a clear translation strategy to the existing construct you are using all over your code, so that you can refactor the code to use it without surprises.

Note that the modern lambda in dialects like Common Lisp does have embedded expressions in it: namely optional and keyword arguments!

(lambda (a &optional (b x) (c y) ...))

These default value expressions x and y are evaluated in the surrounding lexical scope, whenever the argument is missing, every time time the function is called. And, so, what scoping discipline do these expression use? Why, serial, not parallel!

[1]> (defun foo (x &optional (y (1+ x)) (z (1+ y)))
       (list x y z))
FOO
[2]> (foo 10)
(10 11 12)

So, things went full circle. In the beginning, there was LAMBDA. LAMBDA begat LET. LET begat LET*, and LET* begat newer LAMBDA with sequential binding for optional argument init-forms. :)

The result is that translating a modern immediately-called lambda into let is quite complicated. For instance:

(funcall (lambda (x y &optional (z x) (w (1+ z))) a b c)

can compile into:

 (let ((x a) (y b))   ;; we put the fixed params into a let
   (let* ((z c))      ;; z arg present, so refer to c, not x
          (w (1+ z))) ;; w arg absent, use (1+ z)
     ...))

Answer 11

Under let, all of the variable initializing expressions see exactly the same lexical environment: that which surrounds the let. If those expressions happen to capture lexical closures, they can all share the same environment object.

Under let*, every initializing expression is in a different environment. For each successive expression, the environment must be extended to create a new one. At least in the abstract semantics, if closures are captured, they have different environment objects.

A let* must be well-optimized to collapse the unnecessary environment extensions in order to suitable as an everyday replacement for let. There has to be a compiler which works out which forms are accessing what and then converts all of the independent ones into larger, combined let.

(This is true even if let* is just a macro operator that emits cascaded let forms; the optimization is done on those cascaded lets).

You cannot implement let* as a single naive let, with hidden variable assignments to do the initializations because the lack of proper scoping will be revealed:

(let* ((a (+ 2 b))  ;; b is visible in surrounding env
       (b (+ 3 a)))
  forms)

If this is turned into

(let (a b)
  (setf a (+ 2 b)
        b (+ 3 a))
  forms)

it will not work in this case; the inner b is shadowing the outer b so we end up adding 2 to nil. This sort of transformation can be done if we alpha-rename all of these variables. The environment is then nicely flattened:

(let (#:g01 #:g02)
  (setf #:g01 (+ 2 b) ;; outer b, no problem
        #:g02 (+ 3 #:g01))
  alpha-renamed-forms) ;; a and b replaced by #:g01 and #:g02

For that we need to consider the debug support; if the programmer steps into this lexical scope with a debugger, do we want them dealing with #:g01 instead of a.

So basically, let* is the complicated construct which has to be optimized well to perform as well as let in cases when it could reduce to let.

That alone wouldn't justify favoring let over let*. Let's assume we have a good compiler; why not use let* all the time?

As a general principle, we should favor higher-level constructs that make us productive and reduce mistakes, over error-prone lower-level constructs and rely as much as possible on good implementations of the higher-level constructs so that we rarely have to sacrifice their use for the sake of performance. That's why we are working in a language like Lisp in the first place.

That reasoning doesn't nicely apply to let versus let*, because let* is not clearly a higher level abstraction relative to let. They are about "equal level". With let*, you can introduce a bug that is solved by simply switching to let. And vice versa. let* really is just a mild syntactic sugar for visually collapsing let nesting, and not a significant new abstraction.

Answer 12

The OP enquires "ever actually needed LET"?

When Common Lisp was created there was a boat load of existing Lisp code in assorted dialects. The brief the folks who designed Common Lisp accepted was to create a dialect of Lisp that would provide common ground. They "needed" to make it easy and attractive to port existing code into Common Lisp. Leaving LET or LET* out of the language might have served some other virtues, but it would have ignored that key goal.

I use LET in preference to LET* because it tells the reader something about how the data flow is unfolding. In my code, at least, if you see a LET* you know that values bound early will be used in a later binding. Do I "need" to do that, no; but I think it's helpful. That said I've read, rarely, code that defaults to LET* and the appearance of LET signals that the author really wanted it. I.e. for example to swap meaning of two vars.

(let ((good bad)
     (bad good)
...)

There is debatable scenario that approaches 'actual need'. It arises with macros. This macro:

(defmacro M1 (a b c)
 `(let ((a ,a)
        (b ,b)
        (c ,c))
    (f a b c)))

works better than

(defmacro M2 (a b c)
  `(let* ((a ,a)
          (b ,b)
          (c ,c))
    (f a b c)))

since (M2 c b a) isn't going to work out. But those macros are pretty sloppy for assorted reasons; so that undermines the 'actual need' argument.

Answer 13

With Let you use parallel binding,

(setq my-pi 3.1415)

(let ((my-pi 3) (old-pi my-pi))
     (list my-pi old-pi))
=> (3 3.1415)

And with Let* serial binding,

(setq my-pi 3.1415)

(let* ((my-pi 3) (old-pi my-pi))
     (list my-pi old-pi))
=> (3 3)

Answer 14

In addition to Rainer Joswig's answer, and from a purist or theoretical point of view. Let & Let* represent two programming paradigms; functional and sequential respectively.

As of to why should I just keep using Let* instead of Let, well, you are taking the fun out of me coming home and thinking in pure functional language, as opposed to sequential language where I spend most of my day working with :)

Answer 15

I mostly use LET, unless I specifgically need LET*, but sometimes I write code that explicitly needs LET, usually when doing assorted (usually complicated) defaulting. Unfortunately, I do not have any handy code example at hand.

Answer 16

who feels like re-writing letf vs letf* again? the number of unwind-protect calls?

easier to optimize sequential bindings.

maybe it effects the env?

allows continuations with dynamic extent?

sometimes (let (x y z) (setq z 0 y 1 x (+ (setq x 1) (prog1 (+ x y) (setq x (1- x))))) (values () ))

[ I think that works ] point is, simpler is easier to read sometimes.