# Lisp rules!

[From Chris Cherpas (970821.1006)]

Bill Powers (970821.0849 MDT) --

I guess I'll have to get a book on Logo.

I've just started looking at _Approaching Precalculus Mathematics Discretely_
by Phillip Lewis (1990), MIT Press, ISBN 0-262-12138-7, which uses Logo to
"teach" mathematical problem solving. The premise is interesting, but
I haven't had time to work through any of the problems.

In general, I would prefer to program in Lisp than in any other language,
but _not_ Logo, which looks terrible to me! Logo, if it's not actually
embedded in a Lisp, looks way too specialized for my interests.

Bill Powers (970821.0849 MDT) --

Right now I have trouble thinking about datastructures that are sequentially
ordered as a basic property (that's the eighth order of perception in HPCT!).
There must be some way to let you access the elements of a list randomly
-- that is, to bypass the sequential ordering, and make the list look like
an array.

In Lisp, you can access a list just about anyway you want, plus arrays are there
anyway. But, to appreciate Lisp you have to think about the list structure _in
relation to_ the read-eval-print loop, not as "just" a data structure. John
McCarthy (inventor of Lisp) wasn't interested in lists as static data structures
-- he was interested in representing _functions_. In Lisp, the function _is_
a data type, so you can store functions in variables, pass them around as
arguments to other functions, have other functions return them as their
value(s), etc. Because a Lisp function is also a list data structure, your
program can construct and evaluate functions on the fly. This is nontrivial.

Lists within lists _in relation to the read-eval-print loop_ represent
functionally defined hierarchy (i.e., the point is to be recursive);
sequence is what you see if you just look at somebody else's code and aren't
"thinking Lisp." You look at your own Lisp code and you don't see sequence,
you see embedded processes, elegant recursive definitions.

Lisp is the premier extensible language. The point of Lisp programming
is that you not only write your application from the "language down to the
application," you also create your own embedded language (from the "application
up to the language"). And most applications today are tackling problems that
are too complex to assume that you just write it once, and you're done. You
need extensibility from the get-go. People new to AI would ask me, what
applications would you write in Lisp, and the answer in most cases was:
an embedded language for building and fixing your application.

In my opinion, the basic model of Lisp is much closer to PCT than the
imperative language you are now using. Pascal (or whatever) says,
"here's what to do," whereas Lisp says, "here's what I want to see"
(i.e., return a value from a function which has these properties...).
The Lisp programming environment is oriented towards the assumption
that people will make or experience errors on a regular basis, rather
than thinking you can make the perfect program once for all time.

Lisp is interpreted as well as compiled. That in itself is a nice,
bottom-up, pre-debugging device in itself. But combine that with the
"functional" programming style, in which you minimize storing _anything_
(other than locally to the function), and you can easily test out
your building blocks as you go, handling error conditions before they
get expensive to fix.

I couldn't believe it the first time I wrote some C programs and
had to wait around for minutes compiling and linking to find out I had
some little error (which the compiler missed -- gee, what a surprise)
which I would have caught in seconds doing it in the Lisp environment.

Also, in Lisp, the system types everything on the basis of its
just being in the code. You don't have to type data with declarations
or allocate space. Lisp does its own memory management and garbage
collection. You can add declarations later to make the code more efficient.

If you want to write a PCT tool-kit/language that you and everybody
can extend, consider Lisp. BTW, Java is a step away from C and towards
Lisp.

Sorry to be such a salesperson here. A lot of my intuitions in learning
and using Lisp got a voice recently in a couple of books I'd like to recommend,
both by Paul Graham, and I can't help but echo "the news" here...

_On Lisp: Advanced Techniques for Common Lisp_ (1994), Prentice Hall.

_ANSI Common Lisp_ (1996), Prentice Hall.

[From Bill Powers (970821.1335 MDT)]

Chris Cherpas (970821.1006)--

You have unexpected depths, Chris, for a mere renegade EABer. I don't
pretend to understand more than a little of what you say about Lisp; it
would take a hands-on tutorial to teach me much about it.

However, what you said about functions brought me up short for a moment. It
hit me that perhaps what I have been referring to as the "relationship"
level ought to be called the "function" level -- not meaning a level that
performs functions, but a level that perceives and controls functions, in
the way you suggest that Lisp handles functions (or, I suppose, pointers to
functions) as arguments. I'm not at all sure what I mean by that -- as Mary
puts it I'm just "grooving on the sounds of the words." It's something to
do with perceiving the function that relates some variables to others, and
acting in a way that maintains some particular functional relationship in
effect (as opposed to controlling for any particular values of the
variables). That's more or less how I've thought of relationships.
"Maintaining symmetry" would be controlling a relationship, which is
independent any particular values of the variables being maintained in a
symmetrical relationship. Would "function" be a more general term for the
same thing?

I'd be curious about how you would program a control system in Lisp.
According to my understanding of recursion, a control system is not a
recursive system; it does not call itself as a function, and it doesn't
have to maintain a stack of nested states. Recursion is a neat process;
I've only used it once that I can remember, however, to enumerate
exhaustively the combinations of m nursing schedules taken n at a time.
But it seems to have some pretty serious drawbacks such as slow speed and a
hunger for stack space. Also, I wonder about the basic idea of a
"read-eval-print loop" -- this isn't the basic structure of any programs I
write. It sounds more suited to an S-R model than a control model. What's

I wonder whether all these different languages aren't just evidence of
people thinking at different hierarchical levels. Maybe each of them
emphasizes some particular aspect of perception and control that the
inventor was fascinated with, or especially good at. Maybe they would all
fit together, somehow, into a hierarchy of computing languages. Obviously
the "non-procedural" languages are built out of procedures, with the
details being hidden from the main structure, but being necessary anyhow.
Would they operate at the principle level? With respect to handling
functions, C and Pascal make this pretty awkward; the programmer has to
know what's going on, and the declarations, especially in C, get baroque.
Maybe Lisp does all this in a more natural way.

I have a feeling that anyone who was smart enough to go into this would
find that my few little levels running from relationships to principles are
just a sketch of the structure that is really there.

Best,

Bill P.

[From Oded Maler, again]

Tail recursion (the recursive call is the last one in a procedure)
is equivalent to a loop, because you need not maintain any information
on the stack:

Control_System (State):

output:=f(state,input)
Next_state:=g(state,input)
Write(output)
Control_System(Next_state)

end

[If you want avoid any assignment statements you just replace it
with

write(f(state,input))
Control_System(g(state,input)

]

--Oded

[From Bill Powers (970821.1611 MDT)]

Oded Maler, again --

Tail recursion (the recursive call is the last one in a procedure)
is equivalent to a loop, because you need not maintain any information
on the stack:

Control_System (State):

output:=f(state,input)
Next_state:=g(state,input)
Write(output)
Control_System(Next_state)

end

[If you want avoid any assignment statements you just replace it
with

write(f(state,input))
Control_System(g(state,input)

That doesn't help much when you're writing a simulation of an on-going
process that needs real-time input from somewhere else and has to operate
indefinitely. Your tail-recursion module doesn't have to store the states
of variables, but it does have to store the return address each time it
calls itself, so eventually you run out of stack space. In simulations, I
don't think recursion is very useful, except perhaps as a hidden process
for computing some specific function of a set of inputs to get one output
value (like evaluating a square root).

Best,

Bill P.