Really immutable pairs
Abdulaziz Ghuloum
Traditionally, pairs in Scheme/Lisp are mutable
data structures. How much breakage would making
pairs immutable cause?
Note: I'm not talking only about getting rid of
set-car! and set-cdr![1]. This is only one part
of the equation. By making pairs immutable, I
mean really immutable. That is:
* cons does not have to allocate, and therefore,
* eq/eqv on two pairs with eq/eqv cars and cdrs
would be undefined
Getting rid of set-car! and set-cdr! is really
easy since you can "grep" for them in your code
and do the necessary changes to eliminate them.
How much breakage would really immutable pairs
cause? Do you depend on identity of pairs even
in the absence of set-car! and set-cdr!?
Aziz,,,
[1]
http://blog.plt-scheme.org/2007/11/getting-rid-of-set-car-and-set-cdr.html
leppie
wrote:
For identity, do you mean something like:
(let ((init (list #f)))
...
init possibly gets re-assigned along the way
....
(if (eq? init foo)
...
... ))
If so, yes I do use it, but in the presence of immutable pairs, using
a vector could also work in the above case, I think.
Cheers
leppie
Aaron W. Hsu
>How much breakage would really immutable pairs
>cause? Do you depend on identity of pairs even
>in the absence of set-car! and set-cdr!?
I think I can recall one or two programs in which I wrote code that
relied on the EQ-ness of pairs. I am not sure it was the best way
to write things, but I am sure that code out there does exist that
uses this.
Is it that hard to infer the mutability of given pairs inside code
simply by checking whether they are even SET*!'d or used in EQ[V]?
comparisons?
--
Aaron W. Hsu <arc...@sacrideo.us> | <http://www.sacrideo.us>
"Government is the great fiction, through which everybody endeavors to
live at the expense of everybody else." -- Frederic Bastiat
+++++++++++++++ ((lambda (x) (x x)) (lambda (x) (x x))) ++++++++++++++
Jens Axel Soegaard
> By making pairs immutable, I
> mean really immutable. That is:
> * cons does not have to allocate, and therefore,
What do you mean by this?
--
Jens Axel Søgaard
Abdulaziz Ghuloum
> Abdulaziz Ghuloum wrote:
>
>> By making pairs immutable, I
>> mean really immutable. That is:
>> * cons does not have to allocate, and therefore,
>
> What do you mean by this?
>
Meaning: the compiler can transform (cons 1 '()) to '(1).
So, if you have a procedure defined as:
(define (f) (cons 1 '()))
You lose the guarantee that (eq? (f) (f)) must evaluate to
#f (which is what Scheme guarantees since cons in Scheme
has to allocate).
Aziz,,,
Abdulaziz Ghuloum
> Abdulaziz Ghuloum <aghu...@cee.ess.indiana.edu> writes:
>
>> How much breakage would really immutable pairs
>> cause? Do you depend on identity of pairs even
>> in the absence of set-car! and set-cdr!?
>
> I think I can recall one or two programs in which I wrote code that
> relied on the EQ-ness of pairs. I am not sure it was the best way
> to write things, but I am sure that code out there does exist that
> uses this.
I have code that uses eq? on pairs too, but the pairs in my
case are immutable. The eq? test is just an optimization.
So, even if equal? pairs get coalesced, lose their identity,
and magically become eq? (say after GC), then all the better.
> Is it that hard to infer the mutability of given pairs inside code
> simply by checking whether they are even SET*!'d or used in EQ[V]?
> comparisons?
Simple data-flow analysis is not that hard, but it doesn't
take you far either. So, you pay the cost for little or no
benefit in general. Compare to some other immutable data in
Scheme like procedures, numbers, characters, booleans, where
the system is free to do copy-propagation, constant-folding,
coalescing, etc., without having to worry about mutations.
Just imagine the horror that a compiler must go through if
numbers are mutable.
Aziz,,,
Jens Axel Soegaard
Okay. This gives the compiler writer the option to
implement cons as hash-cons [1]. That would indeed give
a more functional feel.
Hmm. Would you ban constructs that create, say,
cyclic structures? If not graph traversal is
tricky to implement without a working eq? .
[1]
http://planet.plt-scheme.org/package-source/dyoo/hash-cons.plt/1/0/doc.txt
--
Jens Axel Søgaard
Michele Simionato
wrote:
I cannot think of a practical use case for relying on (eq? (f) (f))
equal to #f. It is surely a matter of ignorance on my part, but I
would really like to see a meaningful use case. Does anybody have one?
Michele Simionato
Lauri Alanko
Michele Simionato <michele....@gmail.com> wrote:
> > (define (f) (cons 1 '()))
> >
> > You lose the guarantee that (eq? (f) (f)) must evaluate to
> > #f (which is what Scheme guarantees since cons in Scheme
> > has to allocate).
>
> I cannot think of a practical use case for relying on (eq? (f) (f))
> equal to #f. It is surely a matter of ignorance on my part, but I
> would really like to see a meaningful use case. Does anybody have one?
In various contexts there's often a need to have a unique tag that is
guaranteed to be distinct from all other values. In pre-R6RS Scheme a
portable way to have such a tag is simply:
(list 'tag-name)
where 'tag-name is just an informal description, and the true
uniqueness is guaranteed by the allocation behavior of cons.
Lauri
Abdulaziz Ghuloum
> Okay. This gives the compiler writer the option to
> implement cons as hash-cons [1]. That would indeed give
> a more functional feel.
It does give the option, yes. But it also allows the
compiler to translate, say,
(define r
(let ([x (+ 1 2)]
[y (/ 1 2)])
`(,x ,y))
(define s (f r))
(define t (apply + r))
to
(define r '(3 1/2))
(define s (f r))
(define t '7/2)
and thus you get all the benefits of many optimizations
that only apply to numbers, characters, and booleans, to
aggregate lists almost for free.
> Hmm. Would you ban constructs that create, say,
> cyclic structures?
It's tricky. The compiler can block-allocate pairs and
wire them together to make cycles without mutation in
the same way it can block-allocate recursive procedures.
But the decisions for how to make recursive procedures
is done at compile time, so it's relatively easy to emit
code that does the wiring. Not so if you want to make
cyclic lists at runtime.
> If not graph traversal is
> tricky to implement without a working eq? .
Traversing cyclic graphs is hard even with a "working"
eq?. :-) But that's why there are other mutable data
structures that can be used for that.
Aziz,,,
Helmut Eller
> How much breakage would really immutable pairs
> cause? Do you depend on identity of pairs even
> in the absence of set-car! and set-cdr!?
I think this idiom would no longer work:
(let ((probe (assq key alist)))
(when probe
... do something with (cdr probe) ...
(set! alist (remq probe alist))))
Don't know how often this is used.
Helmut.
Abdulaziz Ghuloum
Well, the meaning of the procedure f there is: *make* me
a new pair whose car and cdr are 1 and ().
So, you can rely on doing:
(let ([t (f)])
(set-cdr! t (f))
t)
to create (1 . (1 . ())).
In the absence of mutation, Lauri's example applies. You
can call (f) to return a new "tag" that's distinct from
all other tags in memory. It's not ideal since you lose
the tag if you write it out to file and read it back later.
(and this is why I always use gensyms for that purpose)
One more use of these "tags" is to define:
(define (hashtable-exists? h x)
(let ([t (cons 1 1)])
(not (eq? t (hashtable-ref h x t)))))
If pairs are immutable, then there might be a key in the
table that maps to (1 . 1), and you'd incorrectly get #f
in that case.
Aziz,,,
Abdulaziz Ghuloum
> In various contexts there's often a need to have a unique tag that is
> guaranteed to be distinct from all other values. In pre-R6RS Scheme a
> portable way to have such a tag is simply:
>
> (list 'tag-name)
>
> where 'tag-name is just an informal description, and the true
> uniqueness is guaranteed by the allocation behavior of cons.
The question is: can you easily identify the places in your
code where you do this so that you can change them to, say,
(vector 'tag-name)? Or would making pairs immutable break
your code in unpredictable ways that you cannot easily repair?
Aziz,,,
Michele Simionato
wrote:
>
> One more use of these "tags" is to define:
>
> (define (hashtable-exists? h x)
> (let ([t (cons 1 1)])
> (not (eq? t (hashtable-ref h x t)))))
>
> If pairs are immutable, then there might be a key in the
> table that maps to (1 . 1), and you'd incorrectly get #f
> in that case.
Ok, I see what you mean. This is a possible implementation of the
sentinel pattern
in absence of gensym. I have always used gensym for this kind of
things and it would
never have occurred to me to use conses. I suspect that all the usages
of comparing
conses with eq are of this kind. I have no idea how serious the
breaking would be in
legacy Scheme code. Certainly it would not break anything I have ever
written
(for the record, I am strongly in favor of immutable pairs).
Michele Simionato
Abdulaziz Ghuloum
> (and this is why I always use gensyms for that purpose)
Just in case you're not familiar with the concept, a gensym is
a special kind of symbol whose whole purpose in life is to be
different from everything else (including other gensyms).
Chez and Ikarus preseve gensym identity when you write them
out to file and read them later, and if you compile a library
whose data contains a gensym and reload it in another session.
Aziz,,,
Jens Axel Soegaard
>> If not graph traversal is
>> tricky to implement without a working eq? .
>
> Traversing cyclic graphs is hard even with a "working"
> eq?. :-) But that's why there are other mutable data
> structures that can be used for that.
It would slightly annoying to risk length, display
and others to choke on cyclic lists [not that
I can remember whether it is mandatory to signal
an error, but most implementations do].
--
Jens Axel Søgaard
Abdulaziz Ghuloum
I think we're agreeing that having lists that are both
immutable and cyclic is problematic. Having one (x)or
the other is fine by itself. Right?
Aziz,,,
Abdulaziz Ghuloum
> Okay. This gives the compiler writer the option to
> implement cons as hash-cons [1].
Hash-consing is one "potential" benefit as it does not
always pay for itself, e.g., cons is always faster than
hash-cons. Using hash-tables at the user level is both
slow and yields memory leaks unless additional support
is provided by the memory management system. Anyways,
the ML implementors have beaten this topic to death by
now. One can probably start with Appel and Goncalves's
http://www.cs.princeton.edu/research/techreps/TR-412-93
and trace the references and citations for what's good
and what's bad about hash-consing.
There are of course many other benefits to eliminating
mutations or making pairs immutable. No need to site
them now. I was just wondering about what problems
people may have.
Aziz,,,
Sam TH
wrote:
> Jens Axel Soegaard wrote:
> > Okay. This gives the compiler writer the option to
> > implement cons as hash-cons [1]. That would indeed give
> > a more functional feel.
>
> It does give the option, yes. But it also allows the
> compiler to translate, say,
>
> (define r
> (let ([x (+ 1 2)]
> [y (/ 1 2)])
> `(,x ,y))
> (define s (f r))
> (define t (apply + r))
>
> to
>
> (define r '(3 1/2))
> (define s (f r))
> (define t '7/2)
>
> and thus you get all the benefits of many optimizations
> that only apply to numbers, characters, and booleans, to
> aggregate lists almost for free.
What would the result of optimization look like if you just took the
'ban set-car! and set-cdr!' route? Can you do as well as:
(define r (list 3 1/2))
(define s (f r))
(define t '7/2)
sam th
Abdulaziz Ghuloum
> What would the result of optimization look like if you just took the
> 'ban set-car! and set-cdr!' route? Can you do as well as:
>
> (define r (list 3 1/2))
> (define s (f r))
> (define t '7/2)
Yes you can, and that would be better than what we have.
There are many cases that I sometimes try to write and I
know are trivial to optimize when lists are immutable but
cannot be optimized without very involved analysis if one
has to preserve eq?-ness even though none of these cases
care about eq?-ness at all.
Aziz,,,
Kjetil S. Matheussen
On Wed, 17 Dec 2008, Abdulaziz Ghuloum wrote:
> Here's something (hopefully) useful to discuss.
>
> Traditionally, pairs in Scheme/Lisp are mutable
> data structures. How much breakage would making
> pairs immutable cause?
>
> Note: I'm not talking only about getting rid of
> set-car! and set-cdr![1]. This is only one part
> of the equation. By making pairs immutable, I
> mean really immutable. That is:
> * cons does not have to allocate, and therefore,
> * eq/eqv on two pairs with eq/eqv cars and cdrs
> would be undefined
>
> Getting rid of set-car! and set-cdr! is really
> easy since you can "grep" for them in your code
> and do the necessary changes to eliminate them.
>
> How much breakage would really immutable pairs
> cause?
>
I've quickly grepped through my scheme code in snd (snd.sf.net),
and it seems like I've only used set-cdr! for changing
elements in assocation lists. Mostly doing something
like this:
(define (add-stalin-func name body)
(let ((hit (assq name stalin-funcs)))
(if hit
(set-cdr! hit (list body))
(push! (list name body) stalin-funcs))))
So it would break, but only code which should have
used hash tables instead. :-)
set-car! is used a lot more though. But I also have a big
problem understanding what is actually happening
those places set-car! is used, so I guess the absence
of it could have forced me to write better code.
In addition, set-car! is most likely responsible for
a bug I haven't bothered to fix yet, causing
this hack instead:
...
(or cached
(let ((new-rt (rt-2 (deep-list-copy term)))) ;; <- Hmm. Thats really bad. Seems like a set-car! is performed
(hash-set! *rt-cached-funcs* key new-rt) ;; on term somewhere. Fix it with a deep-list-copy for now.
new-rt))))
...
"rt-2" is a function compiling a scheme-like
input into a c-like output. Unfortunately, "rt-2"
seems to perform a set-car! on the input somewhere,
for some reason, causing me to take a deep copy of
the input first to make memoization work.
> Do you depend on identity of pairs even
> in the absence of set-car! and set-cdr!?
Doubt it.
Shiro Kawai
wrote:
> Getting rid of set-car! and set-cdr! is really
> easy since you can "grep" for them in your code
> and do the necessary changes to eliminate them.
>
> How much breakage would really immutable pairs
> cause? Do you depend on identity of pairs even
> in the absence of set-car! and set-cdr!?
If I had immutable pairs from the first place, I wouldn't have missed
mutable pairs;
for the cases I'm using them I'd be able to use other mutable
structures instead.
The change of legacy code, though, isn't simple, I'm afraid. There
seems quite
a lot of cruft of habit of mutable pairs as convenient and fast
mutable structure.
Using circular lists as ring buffers, and using a list whose last cdr
is
terminated by a generator as a fast alternative of lazy streams, are a
couple of
examples I can remember I've used in the production code I don't dare
to touch it now :-)
--shiro
Jens Axel Soegaard
> I think we're agreeing that having lists that are both
> immutable and cyclic is problematic. Having one (x)or
> the other is fine by itself. Right?
Right.
--
Jens Axel Søgaard
Jens Axel Soegaard
> Jens Axel Soegaard wrote:
>
>> Okay. This gives the compiler writer the option to
>> implement cons as hash-cons [1].
>
> Hash-consing is one "potential" benefit as it does not
> always pay for itself, e.g., cons is always faster than
> hash-cons.
Right, in general it is a bad idea. It just happens
that I am playing with some symbolic algebra code
right now, and in this area it has some benefits.
--
Jens Axel Søgaard
Aaron W. Hsu
>One more use of these "tags" is to define:
>(define (hashtable-exists? h x)
> (let ([t (cons 1 1)])
> (not (eq? t (hashtable-ref h x t)))))
>If pairs are immutable, then there might be a key in the
>table that maps to (1 . 1), and you'd incorrectly get #f
>in that case.
On the topic of hashtables, doesn't Chez Scheme also do something
like return a cons pair of a key and a value, where the value can
be SET-CDR!'d to change the value in the hashtable? I seem to
remember using this a few times as well. I am sure you could use
another structure for this task, then, but ... what, now we have
mcons and cons like in PLT? Seems... confusing.
Sam TH
wrote:
Do you have any of these examples handy? I haven't thought of any in
the 30 seconds I tried. :)
sam th
Aaron W. Hsu
>The question is: can you easily identify the places in your
>code where you do this so that you can change them to, say,
>(vector 'tag-name)? Or would making pairs immutable break
>your code in unpredictable ways that you cannot easily repair?
I would think that for the most part, you should be abel to easily
identify places in your code where this could be a potential problem,
but that's just knowing the code you write, which every good
programmer would be able to do. On the other hand, I question
whether we would lose some convenience in being able to say, wrap
objects up in pairs, to pass them around, SET them and do the like,
and then be able to plop them nicely into lists later on or compose
them naturally, which is somewhat unnatural to do with VECTORs.
I'm not saying that it couldn't be done naturally, but to me at
least, it would feel weird to have to start having one set of
procedures for handling my mutable stuff, and the other for my
immutable. I kind of like being able to use the same operations
on both. *shrug*
Still, maybe the benefits are worth it. Is there a real world
benefit that I would be able to see?
Aaron W. Hsu
back was first written by using cons pairs as keys to an EQ hashtable,
which allowed me to use the data I was getting in three different
(IIRC) structures and work between them all pretty naturally, without
the need to constantly call a hashing procedure. It was also nice
that I could change the value in one of those pairs on the fly, and
have it reflected in the hashtable and the rest of my structures.
I don't know if this was a good thing, but maybe there are more
people who do this?
Ray Dillinger
> Abdulaziz Ghuloum wrote:
>
>> By making pairs immutable, I
>> mean really immutable. That is:
>> * cons does not have to allocate, and therefore,
>
> What do you mean by this?
One thing it could mean is that cons cells might be interned,
so that when you call 'cons' on two things for which a cons
cell already exists, the cons cell you get back is the one
that was allocated the first time. In the absence of mutation,
this has the same effective semantics as allocating a new cons
cell.
Bear
Barry Margolin
Abdulaziz Ghuloum <aghu...@cee.ess.indiana.edu> wrote:
What's the point of getting rid of mutable pairs if you still have other
mutable data structures, like vectors?
ISTM that you either want to go full-blown functional, or there's no
point to this. What's so special about pairs that they should be
immutable?
--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Abdulaziz Ghuloum
I was just (15 minutes ago) writing a macro that generates:
(define names '(a b c d ---)
(define labels (list (ct-gensym a) (ct-gensym b) ---)
(define names->labels-alist (map cons names labels))
(ct-gensym a) expands to a quoted fresh gensym, so, I end up with
(define names '(a b c d ---)
(define labels (list 'g0 'g1 'g2 ---))
(define names->labels-alist (map cons names labels))
In the absence of mutation and hard eq?-ness requirements,
the above would become:
(define names '(a b c d ---)
(define labels '(g0 g1 g2 ---))
(define names->labels-alist '([a . g0] [b . g1] [c . g2] ---))
and all other optimizations would cascade naturally, like:
(cond
[(assq 'a names->labels->list) => cdr]
--)
would simply fold to just: 'g0
without having to do anything fancy beyond what any compiler
already knows how to handle. In ikarus, I just have to mark
the primitives map, cons, and list "foldable" and it would
just work. It's a petty that it doesn't.
Aziz,,,
Abdulaziz Ghuloum
> On the topic of hashtables, doesn't Chez Scheme also do something
> like return a cons pair of a key and a value, where the value can
> be SET-CDR!'d to change the value in the hashtable?
Maybe long time ago, before the implementation of hash table
became "generational" which required new kinds of chain links
for recording feedback from the GC. See "Generation-friendly
Eq hash tables" http://sfp2007.ift.ulaval.ca/procPaper3.pdf
Aziz,,,
Abdulaziz Ghuloum
> Abdulaziz Ghuloum <aghu...@cee.ess.indiana.edu> writes:
>
>> The question is: can you easily identify the places in your
>> code where you do this so that you can change them to, say,
>> (vector 'tag-name)? Or would making pairs immutable break
>> your code in unpredictable ways that you cannot easily repair?
>
> I would think that for the most part, you should be abel to easily
> identify places in your code where this could be a potential problem,
> but that's just knowing the code you write, which every good
> programmer would be able to do.
Right. Though it would be hard if you're maintaining somebody
else's code.
> On the other hand, I question
> whether we would lose some convenience in being able to say, wrap
> objects up in pairs, to pass them around, SET them and do the like,
> and then be able to plop them nicely into lists later on or compose
> them naturally, which is somewhat unnatural to do with VECTORs.
I agree. I didn't say making pairs immutable would be convenient
or natural in all places. Being able to do
(cond
[(assq x ls) => (lambda (p) (set-cdr! p y))]
---)
is very convenient.
> I'm not saying that it couldn't be done naturally, but to me at
> least, it would feel weird to have to start having one set of
> procedures for handling my mutable stuff, and the other for my
> immutable. I kind of like being able to use the same operations
> on both. *shrug*
Well yes. But I doubt you actually use the same operation on both
pairs that you do mutate and those that you don't mutate. Like
you never mutate a list while mapping over it, right?
> Still, maybe the benefits are worth it. Is there a real world
> benefit that I would be able to see?
Many, and I won't even begin to list them all. Matthew Flatt's
blog post lists some of the benefits. Hash-consing is potentially
another. Being able to constant-fold "cons" and copy-propagate
the result is another. Better garbage collection behavior for
immutable data (maybe). Apply/variadic-lambda can be done way
more efficiently (O(N) vs. O(N^2) if you use them recursively).
You get simpler semantics and more efficient implementation for
all higher-order functions: map, for-each, andmap, ormap, fold,
..., which are all pretty sad now since they have to walk the
lists very carefully just in case you mutate the lists being
traversed*. The list goes on and on about the benefits.
Aziz,,,
[*] Have you seen how ugly these are in real implementations?
Take a look, you'd be disgusted!
Michele Simionato
wrote:
> Aaron W. Hsu wrote:
> > Abdulaziz Ghuloum <aghul...@cee.ess.indiana.edu> writes:
> > Still, maybe the benefits are worth it. Is there a real world
> > benefit that I would be able to see?
>
> Many, and I won't even begin to list them all. Matthew Flatt's
> blog post lists some of the benefits. Hash-consing is potentially
> another. Being able to constant-fold "cons" and copy-propagate
> the result is another. Better garbage collection behavior for
> immutable data (maybe). Apply/variadic-lambda can be done way
> more efficiently (O(N) vs. O(N^2) if you use them recursively).
> You get simpler semantics and more efficient implementation for
> all higher-order functions: map, for-each, andmap, ormap, fold,
> ..., which are all pretty sad now since they have to walk the
> lists very carefully just in case you mutate the lists being
> traversed*. The list goes on and on about the benefits.
>
> Aziz,,,
>
> [*] Have you seen how ugly these are in real implementations?
> Take a look, you'd be disgusted!
Aziz is listing a lots of benefits from the point of view of the
language implementor. Still, I think the most important benefits are
from the point of view of the application programmer. Immutability
means that your program becomes easier to understand and to debug. If,
while you are debugging, you see that the content of a list is not
what you would expect, if the list is mutable you potentially have to
wonder about you whole code base, since everything could have mutated
the list. If the list if immutable, you are sure that the bug must be
in the procedure which created the list at the beginning, and in no
other place. Also immutability means less bug, less problems with
multithreaded code, etc. etc.
Michele Simionato
Michael Sperber
Abdulaziz Ghuloum <aghu...@cee.ess.indiana.edu> writes:
> Do you depend on identity of pairs even in the absence of set-car! and
> set-cdr!?
I don't know that *I* do, but I've seen a lot of code that does
something like this:
(define unique-tag (list 'unique-tag))
...
(if (eq? thing unique-tag)
...
...)
...
--
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla
Matthias Blume
> What's the point of getting rid of mutable pairs if you still have other
> mutable data structures, like vectors?
Funny, I would pose the question exactly the other way: "What's the
point of having mutable pairs if there are other mutable data structures
that you can use when you really want and need mutability?"
(By the way, I would not want to use vectors most of the time. Instead,
I'd rather have something like ML's "ref" type officially in the
language.)
> ISTM that you either want to go full-blown functional, or there's no
> point to this.
Actually, people in this thread have already listed a lot of very good
reasons. For those very same reasons you'll find immutable lists and a
lot of other immutable data structures in other (impure) functional
programming languages.
> What's so special about pairs that they should be
> immutable?
Nothing, really. Except maybe that in Scheme programs they are used in
the vast majority of data structures while rarely do they need to
be mutable for algorithmic reasons.
Matthias
Aaron W. Hsu
>Aaron W. Hsu wrote:
Well, I just looked at the hashtables in 7.4, and just such a features
appears. It is called EQ-HASHTABLE-CELL or HASHTABLE-CELL.
Barry Margolin
Matthias Blume <bl...@hana.uchicago.edu> wrote:
> Barry Margolin <bar...@alum.mit.edu> writes:
>
> > What's the point of getting rid of mutable pairs if you still have other
> > mutable data structures, like vectors?
>
> Funny, I would pose the question exactly the other way: "What's the
> point of having mutable pairs if there are other mutable data structures
> that you can use when you really want and need mutability?"
> (By the way, I would not want to use vectors most of the time. Instead,
> I'd rather have something like ML's "ref" type officially in the
> language.)
And once you have vectors, pairs are essentially redundant to begin
with. They're just two-element vectors.
Barak A. Pearlmutter
> Here's something (hopefully) useful to discuss.
>
> Traditionally, pairs in Scheme/Lisp are mutable
> data structures. How much breakage would making
> pairs immutable cause?
Aziz, thank you for the opportunity to wax sardonic.
Some slots in some objects mutable, others not.
Excellent idea! Perhaps we could also have some
special things that are just like cons cells except
that the car is mutable but the cdr is immutable?
It might also be efficient if we had different
sorts of closures: some that can be passed as
arguments, and others that can be called but not
passed. And some globals could be immutable, and
others not. The opportunities for introducing new
distinctions by making a new thing which is just
like some old thing but with some restriction are
endless!
"Programming languages should be designed not by
piling feature on top of feature, but by removing
the weaknesses and restrictions that make additional
features appear necessary."
--
Barak A. Pearlmutter
Hamilton Institute & Dept Comp Sci, NUI Maynooth, Co. Kildare, Ireland
http://www.bcl.hamilton.ie/~barak/
Abdulaziz Ghuloum
> Abdulaziz Ghuloum wrote:
>
>> Here's something (hopefully) useful to discuss.
>>
>> Traditionally, pairs in Scheme/Lisp are mutable
>> data structures. How much breakage would making
>> pairs immutable cause?
>
> Aziz, thank you for the opportunity to wax sardonic.
I have no idea what you mean by that. Sorry.
> Some slots in some objects mutable, others not.
> Excellent idea!
Do we not already have such thing? Let me remind you.
Vectors and strings have immutable length slots, and
mutable contents. Pairs also have immutable tag bits
(ones that allow you to do pair? and disallow you from
destructively making a pair into another object).
Maybe you meant composite immutable data structures
that hold in their slots mutable structures? We have
those too. Closure are immutable, yet they close over
mutable and immutable bindings. Or do you only object
to having *immutable pairs*? Because we do have those
too in R5RS (and maybe R4RS or even before that).
> ["sardonic wax"??? snipped]
Please, state your objections clearly and directly if
you have something worthwhile to say.
Aziz,,,
William D Clinger
> Please, state your objections clearly and directly if
> you have something worthwhile to say.
I can't speak for Barak, but it appears to me that
his position is based in part on Alan Perlis's
observation [1] that
It is better to have 100 functions operate on
one data structure than 10 functions on 10 data
structures.
If you want to design a simple, powerful language
with lots of reusable code that supports general
data structures, then you want to design a small
number of very general data structures and then
put most of your effort into developing reusable
libraries for those data structures.
If you want to design a complicated, weak language
with little reusable support for general data
structures, then you should provide a large number
of special-purpose data structures, each with its
own special-purpose syntax and procedures, and
then encourage programmers to proliferate new
special-purpose data structures with accompanying
syntax and procedures.
If you advocate complicated, weak languages, then
you could promote special-purpose data structures
by forbidding implementations to extend the domains
of functions that operate on special-purpose data
structures, and by arguing that the proliferation
of data structures with special-purpose operations
is a Good Thing because it makes accidental misuse
of a data structure less likely. By "misuse", you
would mean the use of it for some purpose other
than its intended special purpose.
The R6RS definitely took some steps in the direction
of making Scheme into a more complicated and weaker
language, but I think the worst instincts of some
R6RS editors were at least partially thwarted by
other editors. No one is particularly happy about
the result, but it could have been worse.
If Perlis's epigram is one of the main bases for
Barak's argument, then I don't quite agree with
Barak's argument concerning immutable pairs. He
is arguing as though someone were suggesting that
we have two different kinds of pairs, one mutable
and the other immutable, as in PLT Scheme. No one
in their right mind would advocate that kind of
design.
Aziz's proposal, I think, is that there continue
to be only one kind of pair, but that it be
immutable; and that there continue to be only one
kind of vector, and that vectors continue to be
mutable.
I think that's an excellent design. I also think
immutable strings plus mutable string builders is
an excellent design; it would be better than the
mutable strings we now have in Scheme.
On the other hand, Scheme has been around for 33
years. If we're talking about changes to Scheme,
then we don't have the opportunity of making a
fresh start; we'd have to figure out what to do
about all the code that's currently written in
Scheme and uses mutable pairs or strings. Some
of that code could just be abandoned, but other
code would need to be converted. Converting
code that uses mutable pairs to use immutable
lists of mutable cells isn't all that hard, just
as converting code that uses mutable strings to
use a mix of immutable strings and mutable string
builders isn't all that hard, but it isn't trivial
either, and it wouldn't happen overnight.
There would have to be a transitional period.
During that transitional period, implementations
could support a single data structure augmented
with machinery to detect attempted mutations on
pairs that were intended to be immutable, or
they could support distinct data types of mutable
and immutable pairs, as PLT Scheme is doing now.
The first approach achieves some interoperability
but is a trifle complex to implement efficiently,
while the second approach forces programmers to
face the interoperability problems head on. (For
example, you can't pass an R5RS/R6RS list to a
PLT procedure that expects to receive one of the
newfangled immutable lists, and vice versa.)
In implementations that use PLT Scheme's approach
to the transition, effort that would normally be
devoted to developing reusable libraries for
general lists would be divided between mutable
and immutable, and every choice of a list data
structure would involve weighing the pros and
cons of old-style and new-style lists. That's
not a Good Thing.
And, of course, we'd have to ask whether the
benefits of immutable pairs justify the pain
of the transitional period (which, as I have
outlined above, involves more pain than just
the pain of converting legacy code).
That, I think, is part of what Barak had in mind.
He probably had other things in mind also.
Will
[1] Alan Perlis. Epigrams in Programming. ACM
SIGPLAN, September 1982.
http://www.cs.yale.edu/quotes.html
andreu...@yahoo.com
wrote:
> Or do you only object
> to having *immutable pairs*? Because we do have those
> too in R5RS
That is IMO a wart on the language. Either make them all
mutable (including quoted literal lists), or all immutable.
Andre
Ray Dillinger
Allowing a program to destructively manipulate its own source
code at runtime is semantically .... "interesting". Do you know
of any way to handle it without a recompile after each such
mutation? Or are we now talking "interpreted language only?"
Bear
Abdulaziz Ghuloum
> Aziz addressing Barak Pearlmutter:
>> Please, state your objections clearly and directly if
>> you have something worthwhile to say.
>
> I can't speak for Barak, but it appears to me that
> his position is based in part on Alan Perlis's
> observation [1] that
>
> It is better to have 100 functions operate on
> one data structure than 10 functions on 10 data
> structures.
Yes, it appears that his position is based on that
quote (which I happen to like a lot), yet I still
don't know what his position exactly is (since I
said none of the things he listed).
> Aziz's proposal, I think, is that there continue
> to be only one kind of pair, but that it be
> immutable; and that there continue to be only one
> kind of vector, and that vectors continue to be
> mutable.
Correct, though technically I was just asking about
"what would break if ..." to collect views that can
be used either as arguments or as counter arguments.
Aziz,,,
Abdulaziz Ghuloum
I didn't say that it was good or bad design. I was
merely pointing out that the idea of immutable pairs
is already there, along with the other ideas that
Barak seems to object to like data structures having
mixed mutable and immutable slots.
Aziz,,,
andreu...@yahoo.com
Huh? A quoted list can be trivially transformed to an equivalent
expression using CONS during the one compilation.
Ray Dillinger
I do not think that the ways in which you and I are using the
word "equivalent" are equivalent.
We're not just talking about quoted lists. We're talking about
the source code of the program itself. When you modify the structure
of a quoted list, you're also modifying the structure (and therefore
the semantics) of the source code expression which contains it. If
that source code expression should be evaluated again (say, the next
time something enters the routine where the list is used to initialize
a local value) a different result will arise from the mutated
'initialization' of the local variable.
For example,
(define tailchaser (lambda ()
(define local-list '(1 2 3))
(define val (cddr local-list))
(set-cdr! local-list local-list)
val)
will return
(3)
the first time you call it, and
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... )
thereafter.
Bear
andreu...@yahoo.com
No. Not if, as I stated, '(1 2 3) were compiled to (cons 1 (cons 2
(cons 3 '()))), which is what you would have to do if quoted literal
pairs are to be mutable.
Ray Dillinger
> No. Not if, as I stated, '(1 2 3) were compiled to (cons 1 (cons 2
> (cons 3 '()))), which is what you would have to do if quoted literal
> pairs are to be mutable.
Okay, now you're talking about changing the semantics of quote and
*leaving* source code pairs immutable. Quote is supposed to return
the actual structure quoted, not a copy of it made on the spot.
This leaves you out of luck when the semantics of quote were what
you actually wanted; for example eq? comparisons on the same element
of the same quoted list are supposed to return #t. For another
example, people use quote for efficiency when they're trying to not
allocate any memory and not run the garbage collector. In both cases,
screwing with the semantics of quote as you're suggesting would change
critical program behavior.
As an aside, would we be having this conversation at all if there
were a copy-structure command that had a simple one-character syntax
like quote? Because I hear you wanting the brevity of the simpler
syntax and the semantics of a copy constructor, and those are
reasonable things to want, but the instinct to abandon some very
precise and useful semantics in order to get there is IMO misguided.
Bear
andreu...@yahoo.com
> andreuri2...@yahoo.com wrote:
> > No. Not if, as I stated, '(1 2 3) were compiled to (cons 1 (cons 2
> > (cons 3 '()))), which is what you would have to do if quoted literal
> > pairs are to be mutable.
>
> Okay, now you're talking about changing the semantics of quote and
> *leaving* source code pairs immutable. Quote is supposed to return
> the actual structure quoted, not a copy of it made on the spot.
No. There is no such requirement in R5RS or R6RS. A conformant
implementation is perfectly entitled to create a new copy every time a
QUOTE expression is evaluated.
> This leaves you out of luck when the semantics of quote were what
> you actually wanted; for example eq? comparisons on the same element
> of the same quoted list are supposed to return #t. For another
> example, people use quote for efficiency when they're trying to not
> allocate any memory and not run the garbage collector.
These people would be misguided. There is no such efficiency
guarantee in R5RS or R6RS.
> In both cases,
> screwing with the semantics of quote as you're suggesting would change
> critical program behavior.
The semantics you think of is not in the standard.
> As an aside, would we be having this conversation at all if there
> were a copy-structure command that had a simple one-character syntax
> like quote? Because I hear you wanting the brevity of the simpler
> syntax and the semantics of a copy constructor, and those are
> reasonable things to want, but the instinct to abandon some very
> precise and useful semantics in order to get there is IMO misguided.
Again, there is no such semantics to abandon.
Abdulaziz Ghuloum
> No. There is no such requirement in R5RS or R6RS. A conformant
> implementation is perfectly entitled to create a new copy every
> time a QUOTE expression is evaluated.
No, I don't think this is correct. Refer to section "A.3 Quote"
in the operational semantics of R6RS and section "7.2.3. Semantic
functions" in the denotational semantics of R5RS for how quote
and quoted constants are evaluated.
Aziz,,,
Ray Dillinger
> The semantics you think of is not in the standard.
...
> Again, there is no such semantics to abandon.
With all due respect, you are wrong. The formal semantics sections
of the reports are very clear about what quote does and what requirements
a conforming implementation must meet.
If you want a one-character syntactic shortcut, like the syntactic
shortcut for quote, for a copy constructor, that's actually a pretty
good idea. But it is most definitely not the same idea as quote.
Bear