…or so they say! And you know what people? Your language has too many variations and rules in it. They’re too complicated, and your weirdo representations of programs with { } and [ ] and ; and tabs and operator precedences and all that other junk is horrifically stunting your language.
What is Lisp? The LISt Processor I’ve heard.
Nope. Lisp doesn’t even have lists. Would you say C has lists? No. You can of course make lists in C, but you’re really just juggling pointers below a few abstractions you made. Does Python have lists? I guess so. They have a separate data type called “list” and is a fundamental structure in the sense that it’s not built up by anything else.
Lisp is kind of the same as C. There are no lists. All we have are cells and atoms. Let’s denote the set of cells by $C$ and atoms by $A$. Cells are just pairs of either other cells or atoms. What kind of structural things can we do with cells? Well, let $p=(x,y)$ be a cell.
- We can get the first part of $p$. Let’s call this part the anterior region. To get the Cell’s Anterior Region, we write $\operatorname{car} p = x$.
- We can get the second part of the cell. Let’s call this part the dorsal region (why not posterior? The meaning of dorsal makes more sense with lists, in that the dorsal region of a list $[1,2,3]$ is the part “near the end”, $[2,3]$, whereas the posterior would just be $3$). To get the Cell’s Dorsal Region, we’ll write $\operatorname{cdr} p = y$.
- We can take two things, and construct a cell out of them. We’ll write $\operatorname{cons}(x,y)=(x,y)$.
We can easily “emulate” lists by having a special atom $\Lambda$ for empty lists, and then having special cells of the form $(x,y)$ where $x$ is a cell or atom and $y$ is $\Lambda$ or itself one of these special cells. Let’s call these special cells (as well as $\Lambda$) links and denote them $L$ So, \[(a,((x,(y,(z,\Lambda))),(c,(1,(2,(3,\Lambda))))))\] is a list. For simplicity, let’s use the notation \[ [a,[x,y,z],c,1,2,3]. \] So we know with Lisp’s basic construct, we can make things that resemble lists. They are, however, still just cells.
As said, all of Lisp is constructed by these cells and atoms, and usually come in the form of lists (since a lot of data is aggregate). However, this is not what Lisp is, it is just what it is made of. I am a human made of cells and atoms (albeit a different type of cell and atom), but it is not who I am nor what I represent. I am just represented by atoms and cells.
So then, what is Lisp?
Well, it is a sort of tree that lives and thrives in an artificial world, and are consumed by these creatures called Evals (pronounced roughly like “eh-vulz” as in “bevels”) and, unlike the natural process of digestion here on Earth, the Evals give us back another tree (depending on the environment it’s in).
A tree is an object with an operator or root and operands or leaves. Consider $2+6$. Itself, this not-yet-computed computation is a tree whose root is $+$ and whose leaves are $2$ and $6$. Feed this to an Eval and it will return to you a nice lump of $8$. Feed him $2+\text{bone}$, and the poor thing probably won’t be able to digest it and either choke until you revive it or die.
Anyway, these Evals eat these trees of the species Lisp. More (or perhaps less?) concretely, these trees are merely abstract representations of a kind of structure. A Lisp program, when sitting in memory, is just a structure. Of course we have a useful way to represent these programs so they can be communicated by us humans. We cannot see Lisp in its native form. We can, however, see a projection of Lisp in the form of characters, which we are all too familiar with. The projections look something like this:
(DEFUN DIFF (EXPR X) (COND ((EQUAL EXPR X) 1) ((EQUAL (CAR EXPR) 'PLUS) (LIST 'PLUS (DIFF (CADR EXPR) X) (CADDR EXPR) X)) ((EQUAL (CAR EXPR) 'TIMES) (LIST 'PLUS (LIST 'TIMES (CADR EXPR) (DIFF (CADDR EXPR) X)) (LIST 'TIMES (DIFF (CADR EXPR) X) (CADDR EXPR)))) (T 0)))
I hear what you’re going to say already.
See?! Too many parentheses!
However, this is not Lisp. A picture of the Eiffel Tower is not the Eiffel Tower. It is just a depiction of it. Therefore, saying Lisp has too many parentheses is like saying the Eiffel Tower has too much ink, when you’re just looking at a photograph of it.
The reason these projections of Lisp have so many parentheses is because it’s very simple. They all stem from one simple syntax:
(operator operand-1 operand-2 ...)
Now, keep in mind the image of Lisp has syntax, not Lisp itself. It is a way to describe what the Evals eat; Evals don’t literally eat our descriptions. They eat the trees we describe.
What makes Lisp beautiful then? I mean, the real actual Lisp Lisp, not the way we describe it with parentheses.
Well, since Lisp is something I can only show you pictures of, it’s very hard to explain why it is beautiful. You have to experience it for yourself. A photograph of Paris won’t replace the experience of drinking the wine or smelling the bread from within the streets. I can give a little “taste” however.
Going back to our discussion of cells, Lisp trees are built up from these cells. We represent the trees as lists. $[1,2,3]$ translates to (1 2 3), etc. And we know how these lists are built from cells: $[1,2,3]=(1,(2,(3,\Lambda)))$, which in turn translates to (1 . (2 . (3 . NIL))), and therefore (1 2 3) is really just shorthand for (1 . (2 . (3 . NIL))).
So where’s the beauty?
Well those structural operations on cells also have their Lisp equivalents:
- $\operatorname{car} p$ is just (car p),
- $\operatorname{cdr} p$ is just (cdr p), and
- $\operatorname{cons} (x,y)$ is just (cons x y).
I’m still not seeing anything remarkable.
Well, the operations on cells are built up from cells themselves. (cons x y) is just (cons . (x . (y . NIL))). So these inherently datum-like objects — lists, cells, atoms, trees — are also code objects. And they can mix and mingle and act on each other. This is why Lisp is called the programmable programming language.
Oh, and I might add, those Evals are just eval in Lisp and when they eat a tree called tree, one writes (eval tree); Eval, as well as the concept of an Eval “eating”, is just made of the same stuff the trees are made of: atoms and cells.
This post was inspired by this Usenet post, which talks about generally the same thing, but in a much different fashion. Highly recommend.
Thanks for this.
Contents of Address Register
Contents of Decrement Register
I didn’t know the 704 had an “address register” or “decrement register”.
It was actually “address *portion*” of the register, same for decrement (or data).
704 had each instruction formed from a tuple of 3 bits, 15 bits, 15bits and 3 bits again, which were represented by assembler macros CPR (prefix), CAR (address), CDR (Decrement/data), CTR (tag). CONS macro had 4 arguments :)
My comment was snide. See http://symbo1ics.com/blog/?p=275#comment-895
(princ ‘(This god-alike essay deserves at least one comment))
Nope, lisp has too many parentheses.
Nice try, Joseph Stalin.
Hi,
Couldn’t help a little snicker when I first read:
“Your language has too many variations and rules in it. They’re too complicated, and your weirdo representations of programs with { } and [ ] and ; and tabs and operator precedences and all that other junk is horrifically stunting your language.”
and then later see this:
“So,
(a,((x,(y,(z,^))),(c,(1,(2,(3,^))))))
is a list. For simplicity, let’s use the notation
[a,[x,y,z],c,1,2,3],
”
:-).
Cheers
– Jan
Where did this car = Cell’s Anterior Region and cdr = Cell’s Dorsal Region come from?
The correct derivation is from the original IBM 704 implementation of lisp where car = Content of the Address Register and cdr = Contents of the Decrement Register.
Actually that is incorrect, and underlines my point that (a) it doesn’t matter and (b) few people actually do remember the real meanings of CAR and CDR.
There is only one register from which CAR and CDR take data.
http://www.iwriteiam.nl/HaCAR_CDR.html. Here Steve Russel himself says that CAR/CDR mean Contents of Address/Decrement Register. Are the Cell Anterior/Dorsal Region meanings of your own devising (for better understanding maybe)?
What I wrote was conjured by myself, yes. The correct expansion is “contents of the address part of register number” and “contents of the decrement part of register number”.
The “register” refers to that of an IBM 704 CPU register, 36-bits in length. It is divided into four segments as follows:
The segments are respectively called the “tag”, “prefix”, “address”, and “decrement”. The number of bits wide is indicated in the box.
The CAR held a pointer to an atom or another cell, as did the CDR, thus forming a cell.
Say what you want, but arguing on syntax is nothing more then trolling.
Some people like the Lisp syntax, some don’t. Get over it.
Lisp is a very powerful and interesting language. And as some people say: It’s a spawn of pure math so it never gets old. And the semantic power is a part of its elegance and beauty.
Yes indeed, that is what I tried to get across.
Amen, brother. Agreed.
I have glanced several times at Lisp because a close friend is getting heavily into it, but every time I try to read it, my brain just twitches.
Your examples between Lisp notation “(a((x(y(z)))(c(1(2(3))))))” and simpler notation “[a[xyz]c123]” kinda proves the point of too many parens.
I can glance at the simple notation and know exactly what is represented, looking at the Lisp notation takes a fair amount of time to stop and figure out what paren goes with what and what does it represent. I have not been able to see any readability advantages and without readability, maintainability goes out the window.
I am not saying Lisp could not be useful, just that the syntax, to me anyway, is rather nasty to try and read.
It’s kinda funny that way, in that I have the opposite experience. Some people seem almost naturally-inclined toward Lisp. As far as aesthetics go, I can’t really articulate it. It’s almost a musical thing… ok, that sounds totally nuts. Lock me up.
From what I’ve seen, the kinds of examples people invent to criticize Lisp (e.g. (+ 3 2) are code no one would write: the sum of 3 and 2 is 5, so you just write 5 where you needed that. What you might write is (+ num input) which is very clear and makes it immediately obvious what operation will be performed. The real criticisms I’ve seen are at a higher level and by people who want to do serious things. There is an excellent example here:
http://programmers.stackexchange.com/q/41045/2515
The line you are quoting is an arbitrary mathematical expression of a list and has no purpose except to demonstrate the concept of a list. For that purpose, it might be clearer to use pictures instead.
Parentheses are really a non-issue. Any decent editor for Lisp (e.g. DrRacket) will highlight matching parentheses and may even highlight nested levels differently. You can also make the parentheses as light or dark as you wish to blend into the background.
Here are some questions with good answers:
http://programmers.stackexchange.com/questions/60012/why-isnt-lisp-more-widespread
http://stackoverflow.com/questions/130475/why-is-lisp-used-for-ai
LISP is OK, but why all the RetConning? I remember C(ontents) of A(ddress) R(egister) and C(ontents) of D(estination) R(egister) …
Actually that is incorrect, and underlines my point that (a) it doesn’t matter and (b) few people actually do remember the real meanings of CAR and CDR.
(Destination -> Decrement part of)
Dear Quad, Nice blog post.
Re Lisp. see “interpreting Lisp” =
http://www.civilized.com/files/lispbook.pdf
Thanks for the link. I’m printing it out as I type this comment. Looks like a fun read!
I stand corrected and now see that lisp does not have too many parentheses.
Lisp programs have too many parentheses. Maybe if you give me lisp without lisp programs I’ll be happy. Oh wait, I think they called that Smalltalk-72.
(Good job on an astute rebuttal of the common tendency to reject lisp without understanding what it really is. IMO, though, until lisp advocates begin to understand aesthetics as well as they understand purity, they will be condemned to be forever misunderstood.)
lisp DO have too many parentheses.
A simpler syntax doesn’t necessarily means simpler programs.
Just try code reviewing a medium sized lisp program NOT written by yourself.
all the parenthesis make lisp very hard to read that’s why I prefer rebol it’s kinda lisp and much more without these clunky parenthesis :)
Your lisp will forever be a fringe. You’re wasting words.
Yes, lisp appears to have too many parentheses… unless they’re something else when you put some special glasses on.
Three cheers for reductive materialism in lieu of learning.
With each post I’m more sure that I’m too dumb to learn functional programming. =/
Not true! I have explained functional programming in either an abstract or mathematical way. In many ways, functional programming can actually be conceptually simpler. I was thinking about writing an introduction to lisp for those who don’t know a lot about programming in general, especially functional programming. Don’t let any of my posts deter you. :)
[...] a family of languages which emphasize a few points (essentially the idea I explained in this blog post). Arguably, both Scheme and CL are renditions of the number of lisps that preceded [...]
Starting with 0, increment and decrement functions (inc x) and (dec x) over the natural numbers, a conditional function (if P A B), and a lambda syntax to define new functions, use Gödel numbering to encode all possible data structures as an injective mapping to natural numbers, and define car, cdr, cons, list, etc. Then define a Turing machine capable of executing all programs in the system. Ready? Go!
(Actually kind of easy and fun: mrob.com/pub/math/functional-computation.html, unless you care about efficiency :-)
The explanation dances around the question of what all the parens are for. For example, says certain statements have the equivalence of
carp is just (car p),
cdrp is just (cdr p), and
cons(x,y) is just (cons x y)
It does not explain why Lisp uses (car P) and not just car p.
I suppose that the parens surround statements. Of course, in Pascal one has semicolons, so Pathcal (Pascal with a Lisp) would be
car(p);cdr(p);cons(p).Forthtran (FORTRAN with a lisp would be
or PothScript (PostScript with a list would be
Interestingly, the Pascal and FORTRAN formulations have just as many parenthesis. Perhaps the idea is that the parameters are passed to the evaluator rather than the function. The postfix notation on PostScript eliminates the parens altogether.
The explanation is right after that:
In pascal and friends,
car(p)is just code. It’s not a data structure at the same time. In lisp,(car p)is a list containing the symbolscarandp, and when this list is passed to the evaluator, it is interpreted as code.I was recently flipping through some old Lisp books from the 80′s while trying to decide which ones to learn Common Lisp from. Each author acknowledged that Lisp was an old language by the time they wrote their book (2nd oldest). A few of the authors suggested that Lisp is easy for beginners partly due to its consistency and syntax. They then acknowledged that some of the procedure names were rather cryptic for historical reasons, suggesting that rote memorization would just have to suffice in the cases where the names didn’t hint very well as to their purpose (they each gave close variations of the same acronym definitions having to do with the extinct IBM 704).
I was irritated by the fact that NO ONE had backronym’d the outdated CAR and CDR acronyms to something more meaningful, considering that their original wording no longer applied. This lack of clarity only added to the cryptic atmosphere around Lisp for newbies like me. It’s seems that the original CAR and CDR acronyms were mnemonic hints to help the programmer remember what they WERE meant for in a device dependent (physically constrained) manner. If we were to be stuck with these ancient names, I didn’t see any reason why new mnemonics couldn’t be used to give the new Lisp student relevant hints as to what they ARE meant for in a device independent (logical, conceptual) manner.
It just seemed unproductive and unhelpful to be chained to a bygone era in IBM’s hardware history. To keep from doing any more work than necessary (I’m a calorie conservationist), I searched Google looking to see if someone had already come up with a better acronym. Nothing seemed to be coming up (as an aside, I’ve read somewhere that Google puts you in a search bubble so that two different households may see different search results, and previous searches may have prejudiced Google’s results against my keywords for whatever reason). Lisp programmers are reputed to be creative, so this was a disappointing development. I took some time today brainstorming to come up with the following possibilities after reading a little more about Lisp…
Assumptions:
1. CONS is short for CONStruct.
2. A CONStruct is an object (and a noun) that is returned from CONStruct the procedure (and verb).
3. A Construct is something made from parts. In Lisp, a CONStruct as an object consists of two pointers as its parts.
4. Anterior means “situated before or at the front of; fore.” This word is something that should be known from either High School Biology or Body Building magazines. Your doctor may have scared you with this word in some medical context.
5. Dorsal means “of, pertaining to, or situated at the back, or dorsum.” This word is something that should be known from either High School Biology, Body Building magazines, Fishing or just watching Jaws.
6. Reference is a synonym for Pointer (“Points to”).
Backronyms:
CAR = Construct’s Anterior Reference
CDR = Construct’s Anterior Reference
Or
CONStruct “Cell’s Anterior Reference”
CONStruct “Cell’s Dorsal Reference”
It then occurred to me that maybe the words Anterior or Dorsal might be unique enough to be good Google search terms along with CDR. That’s when I found the article on this web page. If a Lisp newbie like myself, and an experienced Lisp developer like the article’s author, can both arrive at the same key verbiage independently, 3 years apart, then it’s a good enough indicator that the correct semantics have been identified given the contextual limitations of working with the letters A and D.
An advantage of the words Anterior and Dorsal is that they don’t break the semantics for procedures such as:
CAAR, CADR, CDAR, CDDR…etc.
In fact, using Anterior (front) and Dorsal (back) conveys the meaning of those procedures even better than the defunct “Address” or “Decrement” from the bygone IBM 704 era.
Another backronym appeared during brainstorming that resolved a personal dissatisfaction for the origin of the word “LISP”. According to these old Lisp books, it’s said to be from “LISt Processing”. I thought that was weak. The name “Lisp” is bad enough in itself, but to come up with it by taking only certain letters from those two words in order to contrive a silly name seemed unnecessarily forced.
On the other hand, the Lisp authors created an important programming language that has long been reputed to be the most powerfully expressive, so who was I to question their choice of names as unimaginative? Does that mean Lisp is safe from being backronym’d? Based on the number of “…Silly or Stupid Parentheses” backronyms all over Internet, I’d say no.
At the risk of falling short of meeting the full original semantics of the name, I’ll offer the following backronym suggestion to fellow newbies as a mnemonic…
For any meaningful processing to be done, LISP programs consist of…Links Inside Surrounding Parentheses.
Of course, I meant…
Backronyms:
CAR = Construct’s Anterior Reference
CDR = Construct’s DORSAL Reference
Another obvious mnemonic is…
For any meaningful processing to be done, LISP programs consist of…”Lists Inside Surrounding Parentheses”.
However, I do like “Links” slightly better as part of a mnemonic that might help remind the new learner the mechanism by which CONStructs, and therefore Lists, are made.
Also, if I’m reading some of these old texts correctly, the parentheses are a required part of the printed notation to indicate Lists and CONStructs (this is aside from their actual object structures in memory). When written or read, they’re not really visually separable from Lists and CONStructs, and should probably be considered part of every List and CONStruct “description”; meaning that Lists aren’t really INSIDE the parentheses, and that parentheses TELL you that you are looking at a List (or a CONStruct).
However, Links of CONStructs ARE inside the parentheses, and the Links and the parentheses TOGETHER denote the List or CONStruct. This is all with the assumption that a List is a chain, or Links, of CONStructs OR the Empty List () (aka “NIL”). And, that while all CONStructs are Lists (dotted lists or proper lists), all Lists are not CONStructs (the Empty List (), aka NIL, is not a CONStruct).