[plt-scheme] append!?

From: Majorinc, Kazimir (kazimir at chem.pmf.hr)
Date: Sat Oct 27 07:42:43 EDT 2007

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 ... "


Posted on the users mailing list.