[plt-scheme] append!?
Matthias Felleisen wrote:
<In short, I am claiming a mix of historical constraints and thinking.>
I've read carefully McCarthy's History of Lisp and although he doesn't
deal explicitly with that topic, few paragraphs are related:
<This involved representing information about the world by sentences in
a suitable formal language and a reasoning program that would decide
what to do by making logical inferences. Representing sentences by list
structure seemed appropriate - it still is - and a list processing
language also seemed appropriate for programming the operations involved
in deduction - and still is. ( .... ) Therefore, the compounds /car/,
standing for ``Contents of the Address part of Register number'', and
its analogs /cdr/, /cpr/, and /ctr/ were defined. The motivation for
implementing /car/ and /cdr/ separately was strengthened by the vulgar
fact that the IBM 704 had instructions (connected with indexing) that
made these operations easy to implement. ... At some point a
/cons(a,d,p,t)/ was defined ... >
McCarthy on side effects:
<"One mathematical consideration that influenced LISP was to express
programs as applicative expressions built up from variables and
constants using functions. I considered it important to make these
expressions obey the usual mathematical laws allowing replacement of
expressions by expressions giving the same value. The motive was to
allow proofs of properties of programs using ordinary mathematical
methods. This is only possible to the extent that side-effects can be
avoided. Unfortunately, side-effects are often a great convenience when
computational efficiency is important, and ``functions'' with
side-effects are present in LISP. However, the so-called pure LISP is
free of side-effects, and (Cartwright 1976) and (Cartwright and McCarthy
1978) show how to represent pure LISP programs by sentences and schemata
in first order logic and prove their properties. This is an additional
vindication of the striving for mathematical neatness, because it is now
easier to prove that pure LISP programs meet their specifications than
it is for any other programming language in extensive use. (Fans of
other programming languages are challenged to write a program to
concatenate lists and prove that the operation is associative).">
I am somehow surprised with this argument, because "ordinary
mathematical methods" can deal with side effects easily. One only needs
to introduce time coordinate and stop to think about, say, (set! x 1) as
a "command for a change of the state of x" and start to think about it
as a statement describing, say, relation between values of Comp(x, t)
and Comp(x, succ(t)).
<"b. Insertion of elements in lists and their deletion. One of the
original advertised virtues of list processing for AI work was the
ability to insert and delete elements of lists. Unfortunately, this
facility coexists uneasily with shared list structure. Moreover,
operations that insert and delete don't have a neat representation as
functions. LISP has them in the form of the /rplaca//rplacd/
pseudo-functions, but programs that use them cannot be conveniently
represented in logic, because, regarded as functions, they don't permit
replacement of equals by equals.">
----
Interesting work in a different direction is Phil Bagwell's Visp,
described in his paper "Fast Functional Lists ... "
<lampwww.epfl.ch/papers/tech*lists*.pdf>