https://gist.github.com/jackrusher/5139396

Skip to content
 
[                    ]
All gists Back to GitHub Sign in Sign up
 
Sign in Sign up
You signed in with another tab or window. Reload to refresh your
session. You signed out in another tab or window. Reload to refresh
your session. You switched accounts on another tab or window. Reload
to refresh your session. Dismiss alert
{{ message }}

Instantly share code, notes, and snippets.

@jackrusher

jackrusher/gist:5139396

Last active October 17, 2024 07:41

Show Gist options

  * Download ZIP

  * Star (65) 65 You must be signed in to star a gist
  * Fork (10) 10 You must be signed in to fork a gist

  * Embed
      + Embed Embed this gist in your website.
      + Share Copy sharable link for this gist.
      + Clone via HTTPS Clone using the web URL.
      + 
      + Learn more about clone URLs
    Clone this repository at <script src="https://
    gist.github.com/jackrusher/5139396.js"></script>
    [<script src="https:/]
  * Save jackrusher/5139396 to your computer and use it in GitHub
    Desktop.

Code Revisions 15 Stars 65 Forks 10
Embed

  * Embed Embed this gist in your website.
  * Share Copy sharable link for this gist.
  * Clone via HTTPS Clone using the web URL.
  * 
  * Learn more about clone URLs

Clone this repository at &lt;script src=&quot;https://gist.github.com
/jackrusher/5139396.js&quot;&gt;&lt;/script&gt;
[<script src="https:/]
Save jackrusher/5139396 to your computer and use it in GitHub
Desktop.
Download ZIP
Hofstadter on Lisp: Atoms and Lists, re-printed in Metamagical
Themas.
Raw
gistfile1.md

Hofstadter on Lisp

 

In the mid-80s, while reading through my roommate's collection of
Scientific American back issues, I encountered this introduction to
Lisp written by Douglas Hofstadter. I found it very charming at the
time, and provide it here (somewhat illegally) for the edification of
a new generation of Lispers.

In a testament to the timelessness of Lisp, you can still run all the
examples below in emacs if you install these aliases:

(defalias 'plus #'+)
(defalias 'quotient #'/)
(defalias 'times #'*)
(defalias 'difference #'-)

Lisp: Atoms and Lists

 

February, 1983

IN previous columns I have written quite often about the field of
artificial intelligence - the search for ways to program computers so
that they might come to behave with flexibility, common sense,
insight, creativity, self awareness, humor, and so on. The quest for
AI started in earnest over two decades ago, and since then has
bifurcated many times, so that today it is a very active and
multifaceted research area. In the United States there are perhaps a
couple of thousand people professionally involved in AI, and there
are a similar number abroad. Although there is among these workers a
considerable divergence of opinion concerning the best route to AI,
one thing that is nearly unanimous is the choice of programming
language. Most AI research efforts are carried out in a language
called "Lisp". (The name is not quite an acronym; it stands for "list
processing".)

Why is most AI work done in Lisp? There are many reasons, most of
which are somewhat technical, but one of the best is quite simple:
Lisp is crisp. Or as Marilyn Monroe said in The Seven-Year Itch, "I
think it's just elegant!" Every computer language has arbitrary
features, and most languages are in fact overloaded with them. A few,
however, such as Lisp and Algol, are built around a kernel that seems
as natural as a branch of mathematics. The kernel of Lisp has a
crystalline purity that not only appeals to the esthetic sense, but
also makes Lisp a far more flexible language than most others.
Because of Lisp's beauty and centrality in this important area of
modern science, then, I have decided to devote a trio of columns to
some of the basic ideas of Lisp.

The deep roots of Lisp lie principally in mathematical logic.
Mathematical pioneers such as Thoralf Skolem, Kurt Godel, and Alonzo
Church contributed seminal ideas to logic in the 1920's and 1930's
that were incorporated decades later into Lisp. Computer programming
in earnest began in the 1940's, but so-called "higher-level"
programming languages (of which Lisp is one) came into existence only
in the 1950's. The earliest list-processing language was not Lisp but
IPL ("Information Processing Language"), developed in the mid-1950's
by Herbert Simon, Allen Newell, and J. C. Shaw. In the years 1956-58,
John McCarthy, drawing on all these previous sources, came up with an
elegant algebraic list-processing language he called Lisp. It caught
on quickly with the young crowd around him at the newly-formed MIT
Artificial Intelligence Project, was implemented on the IBM 704,
spread to other AI groups, infected them, and has stayed around all
these years. Many dialects now exist, but all of them share that
central elegant kernel.

Let us now move on to the way Lisp really works. One of the most
appealing features of Lisp is that it is interactive, as contrasted
with most other higher-level languages, which are noninteractive.
What this means is the following. When you want to program in Lisp,
you sit down at a terminal connected to a computer and you type the
word "lisp" (or words to that effect). The next thing you will see on
your screen is a so-called "prompt" - a characteristic symbol such as
an arrow or asterisk. I like to think of this prompt as a greeting
spoken by a special "Lisp genie", bowing low and saying to you, "Your
wish is my command - and now, what is your next wish?" The genie then
waits for you to type something to it. This genie is usually referred
to as the Lisp interpreter, and it will do anything you want but you
have to take great care in expressing your desires precisely,
otherwise you may reap some disastrous effects. Shown below is the
prompt, showing that the Lisp genie is ready to do your bidding:

>

The genie is asking us for our heart's desire, so let us type in a
simple expression:

> (plus 2 2)

and then a carriage return. (By the way, all Lisp expressions and
words will be printed in Helvetica in this and the following two
chapters.) Even non-Lispers can probably anticipate that the Lisp
genie will print in return. the value 4. Then it will also print a
fresh prompt, so that the screen will now appear this way:

> (plus 2 2)
4
>

The genie is now ready to carry out our next command - or, more
politely stated, our next wish - should we have one. The carrying-out
of a wish expressed as a Lisp statement is called evaluation of that
statement. The preceding short interchange between human and computer
exemplifies the behavior of the Lisp interpreter: it reads a
statement, evaluates it, prints the appropriate value, and then
signals its readiness to read a new statement. For this reason, the
central activity of the Lisp interpreter is referred to as the
read-eval-print loop.

The existence of this Lisp genie (the Lisp interpreter) is what makes
Lisp interactive. You get immediate feedback as soon as you have
typed a "wish" - a complete statement - to Lisp. And the way to get a
bunch of wishes carried out is to type one, then ask the genie to
carry it out, then type another, ask the genie again, and so on.

By contrast, in many higher-level computer languages you must write
out an entire program consisting of a vast number of wishes to be
carried out in some specified order. What's worse is that later
wishes usually depend strongly on the consequences of earlier wishes
- and of course, you don't get to try them out one by one. The
execution of such a program may, needless to say, lead to many
unexpected results, because so many wishes have to mesh perfectly
together. If you've made the slightest conceptual error in designing
your wish list, then a total foul-up is likely - in fact, almost
inevitable. Running a program of this sort is like launching a new
space probe, untested: you can't possibly have anticipated all the
things that might go wrong, and so all you can do is sit back and
watch, hoping that it will work. If it fails, you go back and correct
the one thing the failure revealed, and then try another launch. Such
a gawky, indirect, expensive way of programming is in marked contrast
to the direct, interactive, one-wish-at-atime style of Lisp, which
allows "incremental" program development and debugging. This is
another major reason for the popularity of Lisp.

What sorts of wishes can you type to the Lisp genie for evaluation,
and what sorts of things will it print back to you? Well, to begin
with, you can type arithmetical expressions expressed in a rather
strange way, such as (times (plus 6 3) (difference 6 3)). The answer
to this is 27, since (plus 6 3) evaluates to 9, and (difference 6 3)
evaluates to 3, and their product is 27. This notation, in which each
operation is placed to the left of its operands, was invented by the
Polish logician Jan Lukasiewicz before computers existed.
Unfortunately for Lukasiewicz, his name was too formidable-looking
for most speakers of English, and so this type of notation came to be
called Polish notation. Here is a simple problem in this notation for
you, in which you are to play the part of the Lisp genie:

> (quotient (plus 2113) (difference 23 (times 2 (difference 7 (plus 2 2)))))

Perhaps you have noticed that statements of Lisp involve parentheses.
A profusion of parentheses is one of the hallmarks of Lisp. It is not
uncommon to see an expression that terminates in a dozen right
parentheses! This makes many people shudder at first - and yet once
you get used to their characteristic appearance, Lisp expressions
become remarkably intuitive, even, charming, to the eye, especially
when pretty printed, which means that a careful indentation scheme is
followed that reveals their logical structure. All of the expressions
in displays in this article have been pretty-printed.

The heart of Lisp is its manipulable structures. All programs in Lisp
work by creating, modifying, and destroying structures. Structures
come in two types: atomic and composite, or, as they are usually
called, atoms and lists. Thus, every Lisp object is either an atom or
a list (but not both). The only exception is the special object
called nil, which is both an atom and a list. More about nil in a
moment. What are some other typical Lisp atoms? Here are a few:

hydrogen, helium, j-s-bach, 1729, 3.14159, pi, arf, foo, bar, baz,
buttons-&-bows

Lists are the flexible data structures of Lisp. A list is pretty much
what it sounds like: a collection of some parts in a specific order.
The parts of a list are usually called its elements or members. What
can these members be? Well, not surprisingly, lists can have atoms as
members. But just as easily, lists can contain lists as members, and
those lists can in turn contain other lists as members, and so on,
recursively. Oops! I jumped the gun with that word. But no harm done.
You certainly understood what I meant, and it will prepare you for a
more technical definition of the term to come later.

A list printed on your screen is recognizable by its parentheses. In
Lisp, anything bounded by matching parentheses constitutes a list.
So, for instance, (zonk blee strill (croak flonk)) is a four-element
list whose last element is itself a two-element list. Another short
list is (plus 2 2), illustrating the fact that Lisp statements
themselves are lists. This is important because it means that the
Lisp genie, by manipulating lists and atoms, can actually construct
new wishes by itself. Thus the object of a wish can be the
construction - and subsequent evaluation - of a new wish!

Then there is the empty list - the list with no elements at all. How
is this written down? You might think that an empty pair of
parentheses - () - would work. Indeed, it will work - but there is a
second way of indicating the empty list, and that is by writing nil.
The two notations are synonymous, although nil is more commonly
written than () is. The empty list, nil, is a key concept of Lisp; in
the universe of lists, it is what zero is in the universe of numbers.
To use another metaphor for nil, it is like the earth in which all
structures are rooted. But for you to understand what this means, you
will have to wait a bit.

The most commonly exploited feature of an atom is that it has (or can
be given) a value. Some atoms have permanent values, while others are
variables. As you might expect, the value of the atom 1729 is the
integer 1729, and this is permanent. (I am distinguishing here
between the atom whose print name or pname is the four-digit string
1729, and the eternal Platonic essence that happens to be the sum of
two cubes in two different ways - i.e., the number 1729.) The value
of nil is also permanent, and it is - nil! Only one other atom has
itself as its permanent value, and that is the special atom t.

Aside from t, nil, and atoms whose names are numerals, atoms are
generally variables, which means that you can assign values to them
and later change their values at will. How is this done? Well, to
assign the value 4 to the atom pie, you can type to the Lisp genie
(setq pie 4). Or you could just as well type (setq pie (plus 2 2)) -
or even (setq pie (plus 1 1 1 1)). In any of these cases, as soon as
you type your carriage return, pie's value will become 4, and so it
will remain forevermore - or at least until you do another setq
operation on the atom pie.

Lisp would not be crisp if the only values atoms could have were
numbers. Fortunately, however, an atom's value can be set to any kind
of Lisp object - any atom or list whatsoever. For instance, we might
want to make the value of the atom pi be a list such as (a b c) or
perhaps (plus 2 2) instead of the number 4. To do the latter, we
again use the setq operation. To illustrate, here follows a brief
conversation with the genie:

> (setq pie (plus 2 2))
4
> (setq pi '(plus 2 2))
(plus 2 2)

Notice the vast difference between the values assigned to the atoms
pie and pi as a result of these two wishes asked of the Lisp genie,
which differ merely in the presence or absence of a small but
critical quote mark in front of the inner list (plus 2 2). In the
first wish, containing no quote mark, that inner (plus 2 2) must be
evaluated. This returns 4, which is assigned to the variable pie as
its new value. On the other hand, in the second wish, since the quote
mark is there, the list (plus 2 2) is never executed as a command,
but is treated merely as an inert lump of Lispstuff, much like meat
on a butcher's shelf. It is ever so close to being "alive", yet it is
dead. So the value of pi in this second case is the list (plus 2 2),
a fragment of Lisp code. The following interchange with the genie
confirms the values of these atoms.

> pie
4
> pi
(plus 2 2)
> (eval pi)
4
>

What is this last step? I wanted to show how you can ask the genie to
evaluate the value of an expression, rather than simply printing the
value of that expression. Ordinarily, the genie automatically
performs just one level of evaluation, but by writing eval, you can
get a second stage of evaluation carried out. (And of course, by
using eval over and over again, you can carry this as far as you
like.) This feature often proves invaluable, but it is a little too
advanced to discuss further at this stage.

Every list but nil has at least one element. This first element is
called the list's Car. Thus the car of (eval pi) is the atom eval.
The cars of the lists (plus 2 2), (setq x 17), (eval pi), and (car
pi) are all names of operations, or, as they are more commonly called
in Lisp, functions. The car of a list need not be the name of a
function; it need not even be an atom. For instance, ((1)(2 2) (3 3
3)) is a perfectly fine list. Its car is the list (1), whose car in
turn is not a function name but merely a numeral.

If you were to remove a list's car, what would remain? A shorter
list. This is called the list's cdr, a word that sounds about halfway
between "kidder" and "could'er". (The words "car" and "cdr" are
quaint relics from the first implementation of Lisp on the IBM 704.
The letters in "car" stand for "Contents of the Address part of
Register" and those in "cdr" for "Contents of the Decrement part of
Register referring to specific hardware features of that machine, now
long since irrelevant.) The cdr of (a b c d) is the list (b c d),
whose cdr is (c d), whose cdr is (d), whose cdr is nil. And nil has
no cdr, just as it has no car. Attempting to take the car or cdr of
nil causes (or should cause) the Lisp genie to cough out an error
message, just as attempting to divide by zero should evoke an error
message.

Here is a little table showing the car and cdr of a few lists, just
to make sure the notions are unambiguous.

list                car          cdr
((a) b (c))         (a)          (b (c))
(plus 2 2)          plus         (2 2)
((car x) (car y))   (car x)      ((car y))
(nil nil nil nil)   nil          (nil nil nil)
(nil)               nil          nil
nil                 **ERROR**    **ERROR**

Just as car and cdr are called functions, so the things that they
operate on are called their arguments. Thus in the command (plus pie
2), plus is the function name, and the arguments are the atoms pie
and 2. In evaluating this command (and most commands), the genie
figures out the values of the arguments, and then applies the
function to those values. Thus, since the value of the atom pie is 4,
and the value of the atom 2 is 2, the genie returns the atom 6.

---------------------------------------------------------------------

Suppose you have a list and you'd like to see a list just like it,
only one element longer. For instance, suppose the value of the atom
x is (cake cookie) and you'd like to create a new list called y just
like x, except with an extra atom-say pie - at the front. You can
then use the function called cons (short for "construct"), whose
effect is to make a new list out of an old list and a suggested car.
Here's a transcript of such a process:

>(setq x '(cake cookie))
(cake cookie)
>(setq y (cons 'pie x))
(pie cake cookie)
> x
(cake cookie)

Two things are worth noticing here. I asked for the value of x to be
printed out after the cons operation, so you could see that x itself
was not changed by the cons. The cons operation created a new list
and made that list be the value of y, but left x entirely alone. The
other noteworthy fact is that I used that quote mark again, in front
of the atom pie. What if I had not used it? Here's what would have
happened.

> (setq z (cons pie x))
(4 cake cookie)

Remember, after all, that the atom pie still has the value 4, and
whenever the genie sees an unquoted atom inside a wish, it will
always use the value belonging to that atom, rather than the atom's
name. (Always? Well, almost always. I'll explain in a moment. In the
meantime, look for an exception - you've already encountered it.)

Now here are a few exercises - some a bit tricky - for you. Watch out
for the quote marks! Oh, one last thing: I use the function reverse,
which produces a list just like its argument, only with its elements
in reverse order. For instance, the genie, upon being told (reverse '
((a b) (c d e))) will write ((c d e) (a b)). The genie's lines in
this dialogue are given afterward.

> (setq w (cons pie '(cdr z)))
> (setq v (cons 'pie (cdr z)))
> (setq u (reverse v))
> (cdr (cdr u))
> (car (cdr u))
> (cons (car (cdr u)) u)
> u
> (reverse '(cons (car u) (reverse (cdr u))))
> (reverse (cons (car u) (reverse (cdr u))))
> u
> (cons 'cookie (cons 'cake (cons 'pie nil)))

Answers (as printed by the genie):

(4 cdr z)
(pie cake cookie)
(cookie cake pie)
(pie)
cake
(cake cookie cake pie)
(cookie cake pie)
((reverse (cdr u)) (car u) cons)
(cake pie cookie)
(cookie cake pie)
(cookie cake pie)

The last example, featuring repeated use of cons, is often called, in
Lisp slang "consing up a list". You start with nil, and then do
repeated cons operations. It is analogous to building a positive
integer by starting at zero and then performing the successor
operation over and over again. However, whereas at any stage in the
latter process there is a unique way of performing the successor
operation, given any list there are infinitely many different items
you can cons onto it, thus giving rise to a vast branching tree of
lists instead of the unbranching number line. It is on account of
this image of a tree growing out of the ground of nil and containing
all possible lists that I earlier likened nil to "the earth in which
all structures are rooted".

As I mentioned a moment ago, the genie doesn't always replace
(unquoted) atoms by their values. There are cases where a function
treats its arguments, though unquoted, as if quoted. Did you go back
and find such a case? It's easy. The answer is the function setq. In
particular, in a setq command, the first atom is taken straight-not
evaluated. As a matter of fact, the q in setq stands for "quote",
meaning that the first argument is treated as if quoted. Things can
get quite tricky when you learn about set, a function similar to setq
except that it does evaluate its first argument. Thus, if the value
of the atom x is the atom k, then saying (set x 7) will not do
anything to x-its value will remain the atom k-but the value of the
atom k will now become 7. So watch closely:

> (setq a 'b)
> (setq b 'c)
> (setq c 'a)
> (set a c)
> (set c b)

Now tell me: What are the values of the atoms a, b, and c? Here comes
the answer, so don't peek. They are, respectively: a, a, and a. This
may seem a bit confusing. You may be reassured to know that in Lisp,
set is not very commonly used, and such confusions do not arise that
often.

Psychologically, one of the great powers of programming is the
ability to define new compound operations in terms of old ones, and
to do this over and over again, thus building up a vast repertoire of
ever more complex operations. It is quite reminiscent of evolution,
in which ever more complex molecules evolve out of less complex ones,
in an ever-upward spiral of complexity and creativity. It is also
quite reminiscent of the industrial revolution, in which people used
very simple early machines to help them build more complex machines,
then used those in turn to build even more complex machines, and so
on, once again in an ever-upward spiral of complexity and creativity.
At each stage, whether in evolution or revolution, the products get
more flexible and more intricate, more "intelligent" and yet more
vulnerable to delicate "bugs" or breakdowns.

Likewise with programming in Lisp, only here the "molecules" or
"machines" are now Lisp functions defined in terms of previously
known Lisp functions. Suppose, for instance, that you wish to have a
function that will always return the last element of a list, just as
car always returns the first element of a list. Lisp does not come
equipped with such a function, but you can easily create one. Do you
see how? To get the last element of a list called lyst, you simply do
a reverse on lyst and then take the car of that: (car (reverse
lyst)). To dub this operation with the name rac (car backwards), we
use the def function, as follows:

> (def rac (lambda (lyst) (car (reverse lyst))))

Using def this way creates a function definition. In it, the word
lambda followed by (lyst) indicates that the function we are defining
has only one parameter, or dummy variable, to be called lyst. (It
could have been called anything; I just happen to like the atom
lyst.) In general, the list of parameters (dummy variables) must
immediately follow the word lambda. After this "def wish" has been
carried out, the rac function is as well understood by the genie as
is car. Thus (rac '(your brains)) will yield the atom brains. And we
can use rac itself in definitions of yet further functions. The whole
thing snowballs rather miraculously, and you can quickly become
overwhelmed by the power you wield.

Here is a simple example. Suppose you have a situation where you know
you are going to run into many big long lists and you know it will
often be useful to form, for each such long list, a short list that
contains just its car and rac. We can define a one-parameter function
to do this for you:

> (def readers-digest-condensed-version
    (lambda (biglonglist)
     (cons (car biglonglist) (cons (rac biglonglist) nil))))

Thus if we apply our new function readers-digest-condensed-version to
the entire text of James Joyce's Finnegans Wake (treating it as a big
long list of words), we will obtain the shorter list (riverrun the).
Unfortunately, reapplying the condensation operator to this new list
will not simplify it any further.

It would be nice as well as useful if we could create an inverse
operation to readers-digest-condensed-version called rejoyce that,
given any two words, would create a novel beginning and ending with
them, respectively - and such that James Joyce would have written it
(had he thought of it). Thus execution of the Lisp statement (rejoyce
'Stately 'Yes) would result in the Lisp genie generating from scratch
the entire novel Ulysses. Writing this function is left as an
exercise for the reader. To test your program, see what it does with
(rejoyce 'karma 'dharma).

One goal that has seemed to some people to be both desirable and
feasible using Lisp and related programming languages is (1) to make
every single statement return a value and (2) to have it be through
this returned value and only through it that the statement has any
effect. The idea of (1) is that values are handed "upward" from the
innermost function calls to the outermost ones, until the full
statement's value is returned to you. The idea of (2) is that during
all these calls, no atom has its value changed at all (unless the
atom is a dummy variable). In all dialects of Lisp known to me, (1)
is true, but (2) is not necessarily true.

Thus if x is bound to (a b c d e) and you say (car (cdr (reverse
x))), the first thing that happens is that (reverse x) is calculated;
then this value is handed "up" to the cdr function, which calculates
the cdr of that list; finally, this shorter list is handed to the car
function, which extracts one element-namely the atom d-and returns
it. In the meantime, the atom x has suffered no damage; it is still
bound to (a b c d e).

It might seem that an expression such as (reverse x) would change the
value of x by reversing it, just as carrying out the oral command
"Turn your sweater inside out" will affect the sweater. But actually,
carrying out the wish (reverse x) no more changes the value of x than
carrying out the wish (plus 2 2) changes the value of 2. Instead,
executing (reverse x) causes a new (unnamed) list to come into being,
just like x, only reversed. And that list is the value of the
statement; it is what the statement returns. The value of x itself,
however, is untouched. Similarly, evaluating (cons 5 pi) will not
change the list named pi in the slightest; it merely returns a new
list with 5 as its car and whatever pi's value is as its cdr.

Such behavior is to be contrasted with that of functions that leave
"side effects" in their wake. Such side effects are usually in the
form of changed variable bindings, although there are other
possibilities, such as causing input or output to take place. A
typical "harmful" command is a setq, and proponents of the
"applicative" school of programming - the school that says you should
never make any side effects whatsoever - are profoundly disturbed by
the mere mention of setq. For them, all results must come about
purely by the way that functions compute their values and hand them
to other functions.

The only bindings that the advocates of the applicative style approve
of are transitory "lambda bindings" - those that arise when a
function is applied to its arguments. Whenever any function is
called, that function's dummy variables temporarily assume "lambda
bindings". These bindings are just like those caused by a setq,
except that they are fleeting. That is, the moment the function is
finished computing, they go away - vanishing without a trace. For
example, during the computation of (rac '(a b c)), the lambda binding
of the dummy variable lyst is the list (a b c); but as soon as the
answer c is passed along to the function or person that requested the
rac, the value of the atom lyst used in getting that answer is
totally forgotten. The Lisp interpreter will tell you that lyst is an
"unbound atom" if you ask for its value. Applicative programmers much
prefer lambda bindings to ordinary setq bindings.

I personally am not a fanatic about avoiding setq's and other
functions that cause side effects. Though I find the applicative
style to be jus-telegant, I find it impractical when it comes to the
construction of large AI-style programs. Therefore I shall not
advocate the applicative style here, though I shall adhere to it when
possible. Strictly speaking, in applicative programming, you cannot
even define new functions, since a def statement causes a permanent
change to take place in the genie's memory - namely, the permanent
storage in memory of the function definition. So the ideal
applicative approach would have functions, like variable bindings,
being created only temporarily, and their definitions would be
discarded the moment after they had been used. But this is extreme
"applicativism".

For your edification, here are a few more simple function
definitions.

> (def rdc (lambda (lyst) (reverse (cdr (reverse lyst)))))
> (def snoc (lambda (x lyst) (reverse (cons x (reverse lyst)))))
> (def twice (lambda (n) (plus n n)))

The functions rdc and snoc are analogous to cdr and cons, only
backwards. Thus, the rdc of (a b c d e) is (a b c d), and if you type
(snoc 5 '(1 2 3 4)), you will get (1 2 3 4 5) as your answer.

All of this is mildly interesting so far, but if you want to see the
genie do anything truly surprising, you have to allow it to make some
decisions based on things that happen along the way. These are
sometimes called "conditional wishes". A typical example would be the
following:

> (cond ((eq x 1) 'land) ((eq x 2) 'sea))

The value returned by this statement will be the atom land if x has
value 1, and the atom sea if x has value 2. Otherwise, the value
returned will be nil (i.e., if x is 5). The atom eq (pronounced
"eek") is the name of a common Lisp function that returns the atom t
(standing for "true") if its two arguments have the same value, and
nil (for "no" or "false") if they do not.

A cond statement is a list whose car is the function name cond,
followed by any number of cond clauses, each of which is a
two-element list. The first element of each clause is called its
condition, the second element its result. The clauses' conditions are
checked out by the Lisp genie one by one, in order; as soon as it
finds a clause whose condition is "true" (meaning that the condition
returns anything other than nil!), it begins calculating that
clause's result, whose value gets returned as the value of the whole
cond statement. None of the further clauses is even so much as
glanced at! This may sound more complex than it ought to. The real
idea is no more complex than saying that it looks for the first
condition that is satisfied, then it returns the corresponding
result.

Often one wants to have a catch-all clause at the end whose condition
is sure to be satisfied, so that, if all other conditions fail, at
least this one will be true and the accompanying result, rather than
nil, will be returned. It is easy as pie to make a condition whose
value is non-nil; just choose it to be t for instance, as in the
following:

(cond ((eq x 1) 'land)
      ((eq x 2) 'sea)
       (t 'air))

Depending on what the value of x is, we will get either land, sea, or
air as the value of this cond, but we'll never get nil. Now here are
a few sample cond statements for you to play genie to:

> (cond ((eq (oval pi) pie) (oval (snot pie pi)))
(t (eval (snoc (rac pi) pi))))
> (cond ((eq 2 2) 2) ((eq 3 3) 3))
> (cond (nil 'no-no-no)
((eq '(car nil) '(cdr nil)) 'hmmm)
(t 'yes-yes-yes))

The answers are: 8, 2, and yes-yes-yes. Did you notice that (car nil)
and (cdr nil) were quoted?

I shall close this portion of the column by displaying a patterned
family of function definitions, so obvious in their pattern that you
would think that the Lisp genie would just sort of "get the hang of
it" after seeing the first few... Unfortunately, though, Lisp genies
are frustratingly dense (or at least they play at being dense), and
they will not jump to any conclusion unless it has been completely
spelled out. Look first at the family:

> (def square (lambda (k) (times k k)))
> (def cube (lambda (k) (times k (square k))))
> (def 4th-power (lambda (k) (times k (cube k))))
> (def 5th-power (lambda (k) (times k (4th-power k))))
> (def 6th-power (lambda (k) (times k (5th-power k))))
> .
> .
> .
> .

My question for you is this: Can you invent a definition for a two
parameter function that subsumes all of these in one fell swoop? More
concretely, the question is: How would one go about defining a
two-parameter function called power such that, for instance, (power 9
3) yields 729 on being evaluated, and (power 7 4) yields 2,401 ? I
have supplied you, in this column, with all the necessary tools to do
this, provided you exercise some ingenuity.

I thought I would end this column with a newsbreak about a freshly
discovered beast - the homely Glazunkian porpuquine, so called
because it is found only on the island of Glazunkia (claimed by Upper
Bitbo, though it is just off the coast of Burronymede). And what is a
porpuquine, you ask? Why, it's a strange breed of porcupine, whose
quills - of which, for some reason, there are always exactly nine (in
Outer Glazunkia) or seven (in Inner Glazunkia) - are smaller
porpuquines. Oho! This would certainly seem to be an infinite
regress! But no. It's just that I forgot to mention that there is a
smallest size of porpuquine: the zero-inch type, which, amazingly
enough, is totally bald of quills. So, quite luckily (or perhaps
unluckily, depending on your point of view), that puts a stop to the
threatened infinite regress. This remarkable beast is shown in a rare
photograph in Figure 17-1.

Students of zoology might be interested to learn that the quills on
5-inch porpuquines are always 4-inch porpuquines, and so on down the
line. And students of anthropology might be equally intrigued to know
that the residents of Glazunkia (both Outer and Inner) utilize the
nose (yes, the nose) of the zero-inch porpuquine as a unit of barter
- an odd thing to our minds; but then, who are you and I to question
the ancient wisdom of the Outer and Inner Glazunkians? Thus, since a
largish porpuquine - say a 3-incher or 4-incher - contains many, many
such tiny noses, it is a most valuable commodity. The value of a
porpuquine is sometimes referred to as its "buying power", or just
"power" for short. For instance, a 2-incher found in Inner Glazunkia
is almost twice as powerful as a 2-incher found in Outer Glazunkia.
Or did I get it backward? It's rather confusing!

Anyway, why am I telling you all this? Oh, I just thought you'd like
to hear about it. Besides, who knows? You just might wind up visiting
Glazunkia (Inner or Outer) one of these fine days. And then all of
this could come in mighty handy.

---------------------------------------------------------------------

I hope you enjoyed Hofstadter's idiosyncratic tour of Lisp. You can
find more like this re-printed in his book Metamagical Themas.

@susam
Copy link

susam commented Oct 16, 2024

    In a testament to the timelessness of Lisp, you can still run all
    the examples below in emacs if you install these aliases:

    (defalias 'plus #'+)
    (defalias 'quotient #'/)
    (defalias 'times #'*)
    (defalias 'difference #'-)

Looks like we also need a defmacro for the def expressions used in
the article. The first such expression in the article is:

    (def rac (lambda (lyst) (car (reverse lyst))))

But this fails in Emacs:

ELISP> (def rac (lambda (lyst) (car (reverse lyst))))
*** Eval error ***  Symbol's function definition is void: def

If we want the above example to work, we need to define def like
this:

ELISP> (defmacro def (name lambda-def) `(defalias ',name ,lambda-def))
def

Now the previous example, as presented in the article, works fine:

ELISP> (def rac (lambda (lyst) (car (reverse lyst))))
rac
ELISP> (rac '(your brains))
brains

Sorry, something went wrong.

@susam
Copy link

susam commented Oct 16, 2024

The functions eval and snoc are misspelled as oval and snot,
respectively, in the following code example:

> (cond ((eq (oval pi) pie) (oval (snot pie pi)))
(t (eval (snoc (rac pi) pi))))

This should be written as the following instead:

(cond ((eq (eval pi) pie)
       (eval (snoc pie pi)))
      (t (eval (snoc (rac pi) pi))))

Sorry, something went wrong.

@Welding-Torch
Copy link

Welding-Torch commented Oct 16, 2024

And yet, LISP wasn't used to write ChatGPT. What did Hofstadter
believe that LISP was going to be used for AI?

Sorry, something went wrong.

@KingAl
Copy link

KingAl commented Oct 17, 2024

@Welding-Torch Lisp was used for AI, like in the MIT AI lab. That's
pretty much all he says: he's describing the fact that at the time,
Lisp was used in a lot of AI research. Lisp's ability to manipulate
its own language structures made it particularly useful for
strategies like symbolic artificial intelligence.

AI has always been a fairly fuzzy term, loosely problem solving
strategies that work by analogy with human cognition & reasoning.
LLMs are just the thing that it's trendiest to describe as AI at
present - but just calling it "AI" can serve to obscure the
properties of the actual technology under the hood.

Sorry, something went wrong.

@Welding-Torch
Copy link

Welding-Torch commented Oct 17, 2024

Thanks for the explanation. This Symbolic Artificial Intelligence
(also called Classical Artificial Intelligence) is pretty different
from how I see AI as a younger person. I'm one who associates AI with
LLMs, or rather, ChatGPT.

Sorry, something went wrong.

@ak-1
Copy link

ak-1 commented Oct 17, 2024

Lisp also inspired and influenced the development of Python besides
many other languages. So it is very much part of the history of LLMs
as well.

Sorry, something went wrong.

Sign up for free to join this conversation on GitHub. Already have an
account? Sign in to comment

Footer

 (c) 2024 GitHub, Inc.

Footer navigation

  * Terms
  * Privacy
  * Security
  * Status
  * Docs
  * Contact
  * Manage cookies
  * Do not share my personal information

You can't perform that action at this time.