Clarify Perlis dictum, "LISP programmers know the value of everything and the cost of nothing."

I have been pondering on a Perlis dictum,

LISP programmers know the value of everything and the cost of nothing.

I could find some hints and brief explanations, but not a clear, insightful explanation of what that quote really means, especially in respect of a Lisp programmer.

Could you please explain Perlis' dictum, possibly with simple words first, something comprehensible to CS beginners, and more technical aspects later, by describing the relevant structure, operation or circumstances implied by the dictum, possibly with code or pseudo code examples?

Solution

As with many of his epigrams this is at least partly intended to make you think rather than to actually mean anything really concrete.

However it is reasonably simple to understand what he's getting at here. The quote has two parts.

A LISP programmer knows the value of everything ...

This refers to the fact that Lisp is, unlike many programming languages an expression language. What this means is that in Lisp there is only one sort of thing: an expression, which has a value (or in recent Lisps, some number of values). So, for instance, in CL, I can say:

(let ((y (setq z 3))) ...)

because (setq ...) is an expression whose value is the last value it assigns. Similarly I can say

(setq y (let (...) ...))

because (let (...) ...) is an expression whose value (or values) is the value (or values) of the last form in its body, or nil if there are no forms.

So Lisp programmers know the value of everything because, in Lisp, everything is an expression which has a value.

Contrast this with, say, C. In C there are expressions which have values, and there are also statements which don't. So I can't, in C, say:

int x = if (...) ... else ...;

because if (...) ... else ... is a statement in C, not an expression. Instead I have to use a special conditional expression:

int x = ...? ... : ...;

And so on.

(I can, however, say int x = y = 4;: assignment is an expression in C.)

The same is true for many languages (Python has the same thing for instance).

I confess to not understanding why these languages make this distinction: there must be a reason other than making the syntax & semantics of the language more fiddly I suppose.

... but the cost of nothing.

This part of the quote refers to the fact that various operations in Lisp have time (& possibly space) complexity – that is cost – which is not constant. This is essentially because the most distinctive & important compound data structure (never the only one) in Lisp is the singly-linked-list made of conses, and getting at the nth element of such a list takes time proportional to *n$.

Beginning Lisp programmers, or just Lisp programmers who are not thinking very hard thus end up writing code which is terribly slow, and which scales very badly. For instance consider this:

(defun terrible-sum-list (list)
  (let ((sum 0))
    (dotimes (i (length list) sum)
      (incf sum (nth i list)))))

This is quadratic in the length of the list, because it repeatedly walks down the list to get the nth element. But if the list was an array this would be a perfectly reasonable approach. Instead in Lisp you want to write something like this (I am intentionally writing this as if a lot of CL did not exist: this is not meant to be idiomatic CL code!):

(defun sum-list (list)
  (let ((sum 0))
    (mapc (lambda (e)
            (incf sum e))
          list)
    sum))

Or if you want to be really primitive (but using CL's names for the primitivness):

(defun caveman-sum-list (list)
  (let ((sum 0)
        (tail list))
    (tagbody
     loop
     (if (null tail)
         (go end))
     (setq sum (+ sum (first list))
           tail (rest tail))
     (go loop)
     end)
    sum))

Lisp is, or at least was unusual among programming languages in that it provided operations and data structures whose cost was not trivial to understand. Compare Lisp to, say, Fortran, especially to the Fortran of the day.

Of course, the quote really only applies to very small or simple programs, because large & complicated programs also start having complexities which may not be obvious, leading to an alternative version of this quote:

Fortran programmers know the values of a few things and the costs of a few very small things

(This is not intended to be rude to Fortran programmers: I have been a Fortran programmer.)