immutable pairs (was Re: [plt-scheme] scribblings on PLT Scheme 4.0)

As a concrete example, consider

 (define (chop! l)
   (unless (null? l)
     (let ([next (cdr l)])
       (set-cdr! l '())
       (chop! next))))

 (let ([l (cons 1 (cons 2 (cons 3 '())))])
   (map (lambda (a) (chop! l))
        l))

What will `map' produce, given that the list that it's working on is
mutated by the callback? Just a few years ago, the answer for MzScheme
was "crash". Surprisingly, back then, the usually rock-solid Chez
Scheme also crashed on this kind of example.

The problem is that we write lots of procedures that take list
arguments, and it's difficult to keep in mind that the list can be
mutated. That's just not the way that we think about lists, because we
know that `set-car!' and `set-cdr!' are bad style.

A crashing built-in procedure is just one possible danger if mutable
pairs. A security hole (check the elements of a list, then proceed to
use them) is another easy-to-imagine possibility.


I'll add that we don't take this change lightly. We've considered
making the change many times in the past, but we left pairs mutable.
The R6RS editors considered removing `set-car!' and `set-cdr!', but
didn't; for one thing, no one had any experience with the transition to
immutable pairs.

Since we keep running into problems with mutable pairs (e.g., the
contract system), now seems like a good time to try the experiment. We
can't be sure that the change will work out, since we want a log of old
code to run without too much porting effort; 4.0 will have to keep
mutable pairs if it turns out to be too big of a change. I'm betting
that will make things much better, though.

Matthew

At Wed, 23 May 2007 23:03:34 -0500, "Robby Findler" wrote:
> There are many good reasons. The most basic one is that the programmer
> knows more about the behavior of the program (once a cons is created,
> its fields can't be changed). This is useful to know in a
> multi-threading context, for example. It also means that program
> analysis can be more effective, both for optimization purposes and to
> help programmers reason about their code. It also means that the
> contract library will work slightly better (you can have contracts for
> lists of functions without having to specially make immutable lists).
> Things like that.
> 
> Robby
> 
> On 5/23/07, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> > At Thu, 24 May 2007 09:13:52 +0530, "Sridhar Ratna" wrote:
> > > On 5/24/07, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> > > >
> > > > At the language level, we are considering a few changes for version
> > > > 4.0. The most significant are:
> > > >
> > > >  * Pairs will become immutable by default. This is the big change that
> > > >    will break backward compatibility. We can provide a compatibility
> > > >    `mzscheme' library, but we can't do that for all the libraries whose
> > > >    public interface mentions lists.
> > >
> > > Does this mean that standard procedures like `set-car!' and `set-cdr!'
> > > will be deprecated?
> >
> > We'd still have mutable pairs, `set-car!', `set-cdr!', and a
> > `mutable-cons' procedure that is bound to `cons' in various
> > compatibility libraries.
> >
> > But `cons' in the main language that we use would create immutable
> > pairs, and `set-car!' would fail when applied to an immutable pair.
> >
> > Matthew
> >
> > _________________________________________________
> >   For list-related administrative tasks:
> >   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> >