List Processing Capabilities

[Alex Martelli]

"Jim Richardson" <warlock at eskimo.com> wrote in message
news:slrn8rq8p0.2c2.warlock at gargoyle.myth...
    [snip]
> <Raising hand to expose his ignorance>
> What's list processing and how does it help with AI programming?

"List processing" is the processing of lists.  "List" is a heavily
overloaded word (aren't they all?), but in this context it refers to
a pretty general recursive data structure, made up of a "head" and
"tail", each of which can be a list or an "atom" (a non-list datum
which can generally be a symbol, number, or string, for example).

This structure offers a very handy way to model just about anything
you can think of -- including both programs and data -- in a manner
that is very uniform.  The ability to smoothly and transparently
treat programs as data and vice versa was traditionally considered
one of the keys to "Artificial Intelligence"; AFAIK, the link was
first firmly drawn in 1956, in the first draft of what soon became
the programming language "LISP" (the second-oldest language that is
still in use, the oldest one being Fortran; both, of course, are in
use in modernized dialects, not literally in their original forms
of 40+ years ago).  Most of the literature in the field of AI rests
upon this data structure, and its zillion uses to model this, that,
and the other thing.  Modern approaches may de-emphasize the structure
itself and focus on very different issues (including languages, such
as Logic and Functional ones, where the program/data equivalence is
not very much in evidence), but you will generally find such lists
to be quite pervasive 'under the covers' if you just peek under them.

Python's lists are different, but not less powerful, since any
'slot' in a list (or tuple) may refer to any type.  In Python as
in most other modern languages (almost all, except the still
thriving Lisp-family, now including Scheme, Guile, ...) the
data/program equivalence is de-emphasized, with programs being
normally presented in pretty syntax and data in very different
and also-pretty syntax of their own, but it's still quite feasible
to have programs that 'reason about' themselves (or other programs),
inspect their structure, generate new pieces, etc; this capability
nowadays is generally called "reflection" or "introspection".  It's
not quite as easy and natural as in Lisp-dialects, because you do
have to 'peek under covers' to get at the substance, while in Lisp
there are hardly any covers at all.

"Everything is permissible, but not everything is beneficial", quoth
St. Paul.  He might well have been talking about Python.  Yes, you
*can* use Python for just about any kind of processing you can think
of.  However, the language-to-problem match will be *excellent* for
some areas, *good to fair* for others, *pretty poor* for others yet.
"List-processing" in the AI sense falls in the "good to fair" area,
I think.  It's not bad, but there are better languages.  If your key
purpose is to inspect/manipulate/build programs, then a language
which has basically no syntax differences between programs and data
(a language of the Lisp family, in other words) will probably be
more convenient; and some of them offer very good compilers, able to
generate machine code that will run very fast (this has long been
true for Common Lisp, but, even without the complexities of CL, you
can now get it for simple Scheme with such tools as the stalin
compiler).  To work at a more abstract level, functional languages
are good, and, again, some of them have really good compilers; take
your pick between, say, Haskell (for purity and elegance, including
pretty-clean syntax), ML (for practical power & compiler quality),
Erlang (if you're keen to avoid static typing issues, which ML and
Haskell, differently from Python/Lisp/Erlang, bring to the fore most
forcefully).

Not to say you _can't_ do these things in Python -- you can, and
pretty well too.  But, there are even-better tools for them.  And,
no good craftsperson limits himself or herself to one single tool;
rather, a panoply of tools must be mastered, as well as the skill
to choose the right combination of tools for any given task...


Alex