R6RS Status Report and mutation

I apologize if this has been discussed; I'm just getting back to the
newsgroup after some months of being too swamped to think about it.

On page 2, confusingly under "Additional extensions," is "remove
set-car! and set-cdr!"  This bullet isn't in the expanded list with
comments on the last page, so I don't know whether to be worried
or not.  Could some kind soul let me know what this is about?
(I.e., is the idea to make Scheme purely functional, or to replace
this form of list mutation with some other form?  Or was it an
April Fools joke?)

Brian Harvey wrote:
> I apologize if this has been discussed; I'm just getting back to the
> newsgroup after some months of being too swamped to think about it.
>
> On page 2, confusingly under "Additional extensions," is "remove
> set-car! and set-cdr!"  This bullet isn't in the expanded list with
> comments on the last page, so I don't know whether to be worried
> or not.  Could some kind soul let me know what this is about?
> (I.e., is the idea to make Scheme purely functional, or to replace
> this form of list mutation with some other form?  Or was it an
> April Fools joke?)

I'm dismissing it as a bad idea that will be rejected.  It's true that
in functional programming you never need set-car! and set-cdr!, and it's
true that there are several optimizations that having immutable conses
would allow.  But...  it becomes impossible to do certain operations
without allocating and reaping, which are now possible and efficient
(think list reversal).  These forms are also useful for building
abstractions: you may use them, for example, in the internals of a
data structure where their mutation effects are hidden from the rest
of the program.  They're just too useful to get rid of.

Bear

Ray Dillinger <bear@sonic.net> writes:

> I'm dismissing it as a bad idea that will be rejected.  It's true that
> in functional programming you never need set-car! and set-cdr!, and it's
> true that there are several optimizations that having immutable conses
> would allow.  But...  it becomes impossible to do certain operations
> without allocating and reaping, which are now possible and efficient
> (think list reversal).  These forms are also useful for building
> abstractions: you may use them, for example, in the internals of a
> data structure where their mutation effects are hidden from the rest
> of the program.  They're just too useful to get rid of.

That item talks about removing `set-car!' and `set-cdr!', not
`vector-set!'.

--
((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
http://www.barzilay.org/                 Maze is Life!

Eli Barzilay wrote:
> Ray Dillinger <bear@sonic.net> writes:
>
> 
>
>
> That item talks about removing `set-car!' and `set-cdr!', not
> `vector-set!'.

I don't know any way to do a nonconsing list reversal using
vector-set!.

Any way, it's true that you could just use two-element vectors
instead of cons cells in the internals of any data structure
where you're abstracting over mutation - but what a pain.

Bear

Ray Dillinger <bear@sonic.net> writes:

> I don't know any way to do a nonconsing list reversal using
> vector-set!.

Umm...  "You could just use two-element vectors instead of cons
cells..."

But seriously, I was on the surprised side too, and using reverse!
after accumulating a list of values is just about the only real
problem I could think of.


> Any way, it's true that you could just use two-element vectors
> instead of cons cells in the internals of any data structure
> where you're abstracting over mutation - but what a pain.

[Pain?  It's only five one-liner functions.]

--
((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
http://www.barzilay.org/                 Maze is Life!

Eli Barzilay <eli@barzilay.org> writes:

> But seriously, I was on the surprised side too, and using reverse!
> after accumulating a list of values is just about the only real
> problem I could think of.

Depending on the runtime, reverse! might be better implemented like
reverse. With generational GC and software write barrier allocation
and mutation have similar cost.

Lisp tradition is to reuse the same cons cells for immutable / mutable
lists / pairs, and I would be surprised if it departed from that. But
for a functional language designed from scratch I made them immutable,
and made lists distinguished from pairs (i.e. the tail of a list must
be a list, but there are also pairs).

Scheme already departed from deep Lisp tradition by distinguishing
(), #f and nil. Case-sensitiveness will probably be next.

Consequences of functional lists:

- Cons, append etc. are not required to allocate a fresh cell. The
question which part of list structure must be copied by quasiquote
disappears. The question whether identity of the argument list must
be preserved by apply and the dot in parameters disappears.

- There are no circular lists. The question which functions must
detect circular lists and which are allowed to loop disappears.

- eqv? on lists descends into elements.

- The question about consequences of mutating list literals disappears.
It remains for vectors and strings.

Consequences of separating pairs from lists, and requiring the tail of
a list to be a list (I'm not advocating changing Scheme this way):

- There are no improper lists. The question how functions should behave
when they encounter them, or how apply behaves for them, disappears.

- The question whether to use ((key1 . value1) (key2 . value2)) or
((key1 value1) (key2 value2)) disappears. There are still people who
would use (key1 value1 key2 value2) however.

--
__("<         Marcin Kowalczyk
\__/       qrczak@knm.org.pl
^^     http://qrnik.knm.org.pl/~qrczak/

> But seriously, I was on the surprised side too, and using reverse!
> after accumulating a list of values is just about the only real
> problem I could think of.

The original poster asked, or at least implied, a question that's not
been addressed at all.  Why are set-car! and set-cdr! being removed?

Is it that they are so very rarely used?  Do they create pitfalls
in making it too easy to create circular structures that are
problematic?  Are there optimization problems?

Why break old code without good justifications?  What are those good
justifications?

-Jordan Henderson
jordan.henderson@gmail.com

jordan.henderson@gmail.com wrote: 
>
>
> The original poster asked, or at least implied, a question that's not
> been addressed at all.  Why are set-car! and set-cdr! being removed?
>
> Is it that they are so very rarely used?  Do they create pitfalls
> in making it too easy to create circular structures that are
> problematic?  Are there optimization problems?
>
> Why break old code without good justifications?  What are those good
> justifications?
>

Well, in the first place, you're too quick to assume they're "being
removed."  As I understood it, the agenda simply includes an item to
make a decision about whether to remove them.  Immutable cons pairs
would mean less support for imperative programming; sometimes people
mistake this for having more support for functional programming and
think that therefore it's a good idea.  On reflection, I'm confident
that the committee will see that this doesn't really improve people's
ability to write functional code; it only hinders those writing
imperative code.

In the second place, the committee is also considering an external
representation standard for data with shared structure.  This,
conversely, would specifically increase the support for imperative
code.  So this is kind of an "opposite" decision that's also being
considered.  If both of these proposals pass, it would be contradictory
in terms of language direction; both increasing and decreasing support
for a particular programming style, while breaking old code.

Bear

I do not wish to express an opinion on whether set-car!
and set-cdr! should be removed.

jordan.henderson@gmail.com wrote:
> Is it that they are so very rarely used?

I don't know how rarely they are used.

> Do they create pitfalls
> in making it too easy to create circular structures that are
> problematic?

Inadvertent creation of circular structures is a pitfall for
beginning programmers, but I'm not sure how large a pitfall.

The semantics of several R5RS procedures (e.g. MAP, EQUAL?)
are potentially more complex in the presence of circular
structures.  I suspect that the descriptions of most of
these procedures explicitly say that circular structures
are not within their domain of definition.  This creates
a conflict between those who would prefer to expand their
domain of definition to include circular structures, and
those who would prefer not.  Eliminating the side effects
would eliminate this conflict with respect to one particular
kind of circular structure.  (It would still be possible to
create circular structures using vectors.)

> Are there optimization problems?

Yes.  Common subexpression elimination of redundant (cdr x)
is desirable but not always possible.  It would be possible
even less often if a fixed order of evaluation were adopted.
Eliminating the side effects that interfere with CSE would
create more opportunities for this optimization.

> Why break old code without good justifications?
> What are those good justifications?

No comment.

Will

> I'm dismissing it as a bad idea that will be rejected.  It's true that
> in functional programming you never need set-car! and set-cdr!, and it's
> true that there are several optimizations that having immutable conses
> would allow.  But...  it becomes impossible to do certain operations
> without allocating and reaping, which are now possible and efficient
> (think list reversal).  These forms are also useful for building
> abstractions: you may use them, for example, in the internals of a
> data structure where their mutation effects are hidden from the rest
> of the program.  They're just too useful to get rid of.

I agree with Bear. Of course, set-car!/cdr! are a way to produce
side effects to a function (the constructs can be used to create
call by reference variables). They are also usefull to create
object constructs. Data hiding has proved very usefull.

--
Hans Oesterholt-Dijkema