lambdafunctional-programmingcommon-lispleton-lisp

Are (let) and (lambda) equivalent in Common Lisp


I'm reading On Lisp by Paul Graham, trying to better understand the functional style of programming. In Chapter 3, he mentions that functional programs "work by returning values" rather than performing side effects. I don't quite understand the implications this statement makes on how to manipulate and represent intermediate results of a procedure. If a functional program returns a value, is capturing it using (let) equivalent to using a (lambda) function?

Here's an example showing the definition of a function, (group), using a lambda function to capture the intermediate result. (group) takes a list, src, and a number, n, and subdivides the list elements into k groups of size n.

(defun group (src n acc)
  (funcall
    #'(lambda (back)
       (cond 
         ((consp back)
          (group back n (cons (subseq src 0 n) acc)))
         (t
          (reverse (cons src acc)))))
    (nthcdr n src)))

The last line of the function grabs the back partition of the list by taking the (nthcdr n src). Then, this result is passed as an argument to a lambda function which decides how to process src conditioned on the argument. This is purely functional code, and has no side effects. On the other hand I could have defined (group) in the following way:

(defun group (src n acc)
   (let ((back (nthcdr n src)))
     (cond ((consp back)
            (group back n (cons (subseq src 0 n) acc)))
           (t
            (reverse (cons src acc))))))

where we use (let) to first bind the variable back to the (nthcdr n src). I'm not sure how functional this version of (group) is because (let) binds variables to values in an imperative-like way.


Solution

  • Well, a way to regard let is that it is a more syntactically convenient form of a particular usage of lambda.

    To clarify some notation, in Common Lisp several forms are equivalent.

    • (function (lambda (...) ...)) can be written as #'(lambda (...) ...) since #' is a reader macro.
    • #'(lambda (...) ...) can then be written as (lambda (...) ...), since lambda is a macro whose expansion is (function (lambda (...) ...)).
    • Finally (funcall (lambda (...) ...) ...), which is equivalent to (funcall (function (lambda (...) ...) ...) from above, can be written as ((lambda (...) ...) ...), as a special case of a compound form (see 3.1.2.1.2.4).

    None of this is necessary in a Lisp-1, but in CL it is.

    Below I am going to write ((lambda (...) ...) ...) rather than the clunky (funcall #'(lambda (...) ...) ...) that I think Graham probably uses.

    So, now, the important point:

    (let ((x ...) ...) ...) is entirely equivalent to ((lambda (x ...) ...) ...).

    Although it is not implemented this way in CL (let is a special operator), you can think of let as if it were a macro defined in terms of lambda like this. In particular here is a definition for a macro called allow which is like let (you can't redefine let itself in CL of course, hence this name):

    (defmacro allow (bindings &body decls/forms)
      `((lambda ,(mapcan (lambda (b)
                           (typecase b
                             (null '())     ;elide ()'s in binding list as special caee
                             (symbol (list b))
                             (cons
                              (unless (eql 2 (list-length b))
                                (error "mutant binding ~S" b))
                              (list (first b)))
                             (t
                              (error "what even is ~S" b))))
                         bindings)
          ,@decls/forms)
        ,@(mapcan (lambda (b)
                    (typecase b
                      (null '())
                      (symbol (list 'nil))
                      (cons (list (second b)))
                      (t (error "what even is ~S" b))))
                  bindings)))
    

    And now, for instance, using a macroexpansion tracer:

    > (allow ((x 1) (y 2)) (+ x y))
    (allow ((x 1) (y 2)) (+ x y))
     -> ((lambda (x y) (+ x y)) 1 2)
    3
    

    As I said, in CL let isn't defined like this as it is a special operator, but it could be, and there could be corresponding definitions of let* and so on. Here is a definition of allow* which is let*:

    (defmacro allow* (bindings &body decls/forms)
      (if (null (rest bindings))
          `(allow ,bindings ,@decls/forms)
        `(allow (,(first bindings))
           (allow* ,(rest bindings) ,@decls/forms))))
    

    (And at this point I get to laugh at people who say 'macros with recursive expansions baaad, baaaad'.)

    So from the perspective of the semantics of the language there is no difference at all: (let (...) ...) is entirely equivalent to ((lambda (...) ...) ...). In particular, since any program involving let can trivially be rewritten to one using only lambda, and lambda is a purely functional construct, then let is also a purely functional construct.

    There are then two differences in practical terms.

    Readability. This is the important one. Programs are not just ways of instructing a machine to do something: they are a way of communicating your intent to other human beings. For almost everyone (and I think, probably actually for everyone) it is easier to read code which says, in English

    let x be ..., and now ... things involving x ...

    Rather than something which is extremely hard to even write in natural language, but might be

    x will have a value in here, and now ... things involving x ..., and the value is ...

    And that's even worse when comparing

    let x be ... and y be ..., and now ...

    with the really awful

    x and y will have values in here, and now ..., things involving x and y ..., and the values are ... and ...

    That's just an awful way of writing something: the values are widely-separated from the variables being bound, there is no indication which value belongs to which variable when you finally reach them, and finally there's a serial dependency which is generally harder for humans to parse.

    If you came across natural-language text written like this you'd correct it, because it's awful. Well, that's what let does: it turns the hard-to-read lambda form to a much more understandable one, where the initial values are next to the variables.

    Possible historical ease of implementation. It is possible, I think, that it was once easier for a compiler if let was treated as a special case rather than as simply a macro which expands into a lambda form. I am not sure about this, especially as I am fairly sure I have read somewhere I can't find just now that let originated as a macro, but it seems plausible as a reason that let is a special operator in CL. Certainly I find it hard to imagine that it was not possible for a compiler to see ((lambda (...) ...) ...) and compile that form in some optimal way (ie don't compile a function at all), even a very long time ago when compilers were made of mud and goose fat.

    I think it is safe to ignore this second reason today.