[plt-scheme] append!?

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Tue Oct 23 08:59:42 EDT 2007

On Oct 23, 2007, at 1:50 AM, Majorinc, Kazimir wrote:

> You didn't answered me on this :
> <... on that way there is no significant difference between empty  
> and non-empty list, both are mutable. Obviously, it is not the Lisp  
> way - but it begs for the question, why not? Did original designer  
> or anyone else discussed it in some serious publication, or it was  
> taken for granted without much questioning?>

Anton gave you a good answer. Here is mine:

Remember the classification of operations I included in my mail?
I forgot one but the essence is

  -- construct
  -- destruct
  -- recognize (predicates)
  -- mutate

A list consists of two constructors: one, a constant, NULL; the other  
one a struct builder, cons. One is mutable, one is not.

When they designed LISP -- and this is one of the things we inherited  
from them -- languages were designed for specific domains: Formula  
translation, Algorithmic processing, String processing, and List  
processing, which was considered the most advanced (and therefore a  
part of AI). I suspect -- but don't know -- that the Lispers looked  
at a whole bunch of algorithms for lists, played with them, and  
developed a compromise that they thought was good for memory  
(scarce), performance (argh), programmability, etc. Your data type  
may have come up but the indirections inherent in it add 30% space  
overhead, indirection at every step of processing, etc. Making the  
set-cXr! available, however, didn't violate much, did most of the  
work for append! except for one border case, and was easily  
translated to a machine.

In short, I am claiming a mix of historical constraints and thinking.

;; ---

 From a modern-day perspective, when you want things uniform, you  
have two choices: make the empty list also mutable with a datatype  
like yours; or make all lists immutable. Our experience suggests that  
the latter course of action is definitely beneficial for programming  
style and could also be a good thing for the compiler. (Indeed some  
multi-core people think that it is the way to go.)

-- Matthias

Posted on the users mailing list.