Home > Archive > Scheme > November 2004 > R6RS Status Report and mutation
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
R6RS Status Report and mutation
|
|
| Brian Harvey 2004-10-29, 3:58 pm |
| 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?)
| |
| Ray Dillinger 2004-10-30, 3:56 am |
| 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
| |
| Eli Barzilay 2004-10-30, 3:56 am |
| 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!
| |
| Ray Dillinger 2004-10-30, 8:56 am |
| 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
| |
| Eli Barzilay 2004-10-30, 8:56 am |
| 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!
| |
| Marcin 'Qrczak' Kowalczyk 2004-10-30, 8:56 am |
| 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/
| |
| jordan.henderson@gmail.com 2004-10-31, 3:57 pm |
| > 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
| |
| Ray Dillinger 2004-10-31, 3:57 pm |
| 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
| |
| William D Clinger 2004-11-01, 3:56 am |
| 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
| |
| Hans Oesterholt-Dijkema 2004-11-01, 3:58 pm |
| > 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
| |
| Jens Axel Søgaard 2004-11-01, 3:58 pm |
| Hans Oesterholt-Dijkema wrote:
s[color=darkred]
[color=darkred]
> I agree with Bear. Of course, set-car!/cdr! are a way to produce=20
> 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.
If they were to be abolished, then I am sure a mutable alternative
would be provided. E.g mcons and set-mcar! for mutable pairs.
--=20
Jens Axel S=F8gaard
| |
| Brian Harvey 2004-11-01, 3:58 pm |
| =?ISO-8859-1?Q?Jens_Axel_S=F8gaard?= <usenet@soegaard.net> writes:
>If they were to be abolished, then I am sure a mutable alternative
>would be provided. E.g mcons and set-mcar! for mutable pairs.
In order to make this really useful (maintaining the convenience of
lists compared to two-element vectors), you'd also need mlist,
mappend, mmap, mfor-each, and so on. This strikes me as hideous;
I'd even prefer saying "#pragma pairs-not-mutated" to having two
sets of list procedures!
Fwiw, I think the biggest strength of Scheme is still its power
as a teaching language -- and, in particular, one that supports
the teaching of multiple programming paradigms.
| |
| Bradd W. Szonye 2004-11-01, 8:57 pm |
| Marcin 'Qrczak' Kowalczyk wrote:
> Consequences of functional lists: ... There are no circular lists.
How does that follow? It implies that you couldn't use CONS to build
circular lists, but you could still do it with a (new) function that
builds cycles atomically.
--
Bradd W. Szonye
http://www.szonye.com/bradd
| |
| Marcin 'Qrczak' Kowalczyk 2004-11-02, 8:57 am |
| "Bradd W. Szonye" <bradd+news@szonye.com> writes:
>
> How does that follow? It implies that you couldn't use CONS to build
> circular lists, but you could still do it with a (new) function that
> builds cycles atomically.
Sure. But I view it as a positive thing: such function would not be
provided for lists, we would use other types to represent graphs with
cycles, and operations dealing with lists would not have to consider
how they should behave on circular lists, for example whether
(eval `(quote ,a-circular-list) (null-environment 6)) is valid.
(Unfortunately problems would remain for vectors, which also have
a literal syntax.)
--
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
| |
| Bradd W. Szonye 2004-11-02, 3:58 pm |
| Marcin 'Qrczak' Kowalczyk <qrczak@knm.org.pl> wrote:
> "Bradd W. Szonye" <bradd+news@szonye.com> writes:
>
> Sure. But I view it as a positive thing: such function would not be
> provided for lists, we would use other types to represent graphs with
> cycles ....
That makes sense. A list ADT doesn't have cycles, so you define the
language's "list" type such that it can't have cycles.
--
Bradd W. Szonye
http://www.szonye.com/bradd
| |
| Brian Harvey 2004-11-02, 3:58 pm |
| "Bradd W. Szonye" <bradd+news@szonye.com> writes:
>That makes sense. A list ADT doesn't have cycles, so you define the
>language's "list" type such that it can't have cycles.
In my youth, people all the time did things along the lines of
(define (add-one-to-each lst)
(map + lst (make-cycle 1)))
|
|
|
|
|