Mutable Pairs
David Rush
--
GPG Public key at http://cyber-rush.org/drr/gpg-public-key.txt
John Cowan
> I am having a very bad experience with PLT 4.2.1 at the moment and it
> appears to trace back to what is at least an implied semantic change in
> R6RS where pairs are *not* mutable by default and that you must import
> the (rnrs mutable-pairs (6)) library just to have set-car! available.
That is indeed a requirement on R6RS implementations. In general R6RS
programs are not backward compatible with R5RS, so you need to be sure to
run R5RS programs on R5RS implementations, or be prepared to change the
programs. I'm not familiar with PLT, but I'd be surprised if it did not provide
an R5RS-compatible mode of operation.
> Additionally, the "teaching language" mandate of WG1 would seem to
> advocate in favor of changing the default behavior here.
There is *no* requirement that either WG1 Scheme or WG2 Scheme be
compatible with R6RS in any way. WG2 must consider R6RS features (and
complaints about them), but is free to provide backward-incompatible
specifications or none at all. For WG1 purposes, R6RS is at most a
source of ideas.
--
Only do what only you can do. John Cowan <co...@ccil.org>
--Edsger W. Dijkstra's advice
to a student in search of a thesis
Aaron W. Hsu
In this case, the problem isn't with R6RS. All pairs in R6RS are
mutable, but the procedures to mutate them are not exported by default.
Theoretically this provides better hints to the compiler, but in
practice I think it's mostly just an annoyance.
At any rate, this is an issue with PLT, not R6RS. PLT actually goes way
beyond what R6RS dictates and changes pairs to be immutable. Not just
difficult to mutate, but they are immutable. If you want to use mutable
pairs, you have to use their mcons, mcar, &c. procedures, which create
mutable pairs. So, immutable and mutable pairs are actually completely
separate datatypes.
In R6RS, if you want to operate on pairs, it's as simple as importing a
library. All the pairs you get from other libraries that may or may not
import that library are mutable, so that's all you have to do. On the
other hand, if you work with PLT, many of the pairs that might be
generated from other libraries will not be mutable pairs, and you'll end
up with trouble.
Aaron W. Hsu
Aaron W. Hsu
> David Rush scripsit:
>
> > I am having a very bad experience with PLT 4.2.1 at the moment and it
> > appears to trace back to what is at least an implied semantic change in
> > R6RS where pairs are *not* mutable by default and that you must import
> > the (rnrs mutable-pairs (6)) library just to have set-car! available.
>
> That is indeed a requirement on R6RS implementations. In general R6RS
> programs are not backward compatible with R5RS, so you need to be sure to
> run R5RS programs on R5RS implementations, or be prepared to change the
> programs. I'm not familiar with PLT, but I'd be surprised if it did not provide
> an R5RS-compatible mode of operation.
PLT provides #lang r6rs, which should give you mutable pairs. There is a
distinction between PLT's mutable pairs, and R6RS's requirement that the
mutation procedures be exported by the (rnrs) library. In particular,
whether you import (rnrs mutable-pairs) or not, the pairs can still be
mutated later on by other code that has these available, this is not the
case with PLT's pairs.
Aaron W. Hsu
Brian Harvey
John Cowan
> In this case, the problem isn't with R6RS. All pairs in R6RS are
> mutable, but the procedures to mutate them are not exported by default.
If the mutation procedures are not (transitively) imported by an R6RS
program, in what sense are the pairs mutable? An R6RS compiler might
note the failure to import the library and supply a very different
run-time system that relies on the immutability of pairs.
--
I marvel at the creature: so secret and John Cowan
so sly as he is, to come sporting in the pool co...@ccil.org
before our very window. Does he think that http://www.ccil.org/~cowan
Men sleep without watch all night?
Aaron W. Hsu
> If the mutation procedures are not (transitively) imported by an R6RS
> program, in what sense are the pairs mutable? An R6RS compiler might
> note the failure to import the library and supply a very different
> run-time system that relies on the immutability of pairs.
A compiler may optimize the pairs to take advantage of this when
compiling a whole program, but it cannot do this with just a library.
(library (a)
(export my-pair)
(import (rnrs))
(define hidden-pair (cons #f #f))
(define (my-pair) hidden-pair))
In this library, if the compiler makes the above pair immutable, it
would be wrong. After the compilation of this code, we could import the
compiled library into another library that in fact mutates that hidden
pair. The main point being that pairs in R6RS are mutable. The compiler
could do some optimization to prove that they are not mutated in a given
program, but that's very different than saying that pairs are not
mutable.
Aaron W. Hsu
Brian Harvey
So, do we get to levy a fine against PLT? :-)
Alex Shinn
> Aaron W. Hsu scripsit:
>
>> In this case, the problem isn't with R6RS. All pairs in R6RS are
>> mutable, but the procedures to mutate them are not exported by default.
>
> If the mutation procedures are not (transitively) imported by an R6RS
> program, in what sense are the pairs mutable? An R6RS compiler might
> note the failure to import the library and supply a very different
> run-time system that relies on the immutability of pairs.
As Aaron points out, when compiling a library you don't
know whether it will be used in a program with mutable
pairs or not, so in general you have to assume that all
R6RS pairs are mutable.
With either a global optimizing compiler, or a compiler
smart enough to detect locally constructed, non-mutated,
non-escaping pairs, you can optimize them as immutable.
In either case, you already have the information
needed to perform the optimization, and whether or not
set-car! and set-cdr! are imported is irrelevant. From a
technical standpoint, moving these to a library serves
absolutely no purpose.
From a community standpoint, it says "we think mutable
pairs were a mistake, and while we can't change that now
because of compatibility reasons, we'd like to discourage
their use." If you need to type an extra import form to
mutate your pairs, you're less likely to do so. If the
usage of set-car! and set-cdr! decreases because of
this, in the future it may be more realistic to remove
them entirely from the language.
So if you think eventually all Scheme pairs should
be immutable, it makes sense to move the mutators
to a library. But this is a long-term, social movement.
There is _zero_ immediate technical benefit.
--
Alex
Alex Shinn
> I am having a very bad experience with PLT 4.2.1 at the moment and it
> appears to trace back to what is at least an implied semantic change in R6RS
> where pairs are *not* mutable by default and that you must import the (rnrs
> mutable-pairs (6)) library just to have set-car! available.
> This breaks a *lot* of code. It would also seem to be incompatible with the
> IEEE standard.
PLT is not Scheme, it's a family of languages for which the
default language was largely backwards compatible with R5RS
up until the 4.0 release, and which is now slowly diverging -
so much so that they are planning on changing the name
away from Scheme this summer.
PLT will no doubt continue to support Scheme (e.g. with
#lang r6rs and perhaps r7rs later), though the immutable pair
split has made mixing and matching modules from the default
language and Scheme more difficult. This could possibly be
alleviated with units parameterized over the core pair operators.
--
Alex
Benjamin L. Russell
> I vote we put in the WG1 standard that the pairs made by CONS are mutable.
I agree; however, just for the record, an argument explaining the
rationale behind switching to immutable pairs in PLT Scheme (now
"Racket") is stated in the following blog entry by Matthew Flatt:
PLT Scheme Blog: Getting rid of set-car! and set-cdr!
http://blog.plt-scheme.org/2007/11/getting-rid-of-set-car-and-set-cdr.html
Flatt's argument can be summarized as follows:
Suppose we had the following function:
(define (map f l)
(cond
[(null? l) '()]
[else (cons (f (car l)) (map f (cdr l)))]))
If f is functionally written without side-effects, then there is no
problem, but if f has side-effects, then the above implementation is
inconsistent with map's traditional definition of not specifying the
order of processing for its list argument.
To guard against map receiving a non-list as an argument, we write a
wrapper function, checked-map, as follows:
(define (checked-map f l)
(if (list? l)
(map f l)
(error 'map "not a list")))
The problem with mutable pairs arises if someone calls checked-map as
follows:
(define l (list 1 2 3 4 5))
(checked-map (lambda (x)
(set-cdr! (cddr l) 5))
l)
Here, since l is initially a list, the check for whether l is a list in
checked-map initially succeeds, so the error message is not printed.
However, the call to set-cdr! mutates the cddr of l from '(3 4 5) to 5,
which is not a list. Then, a call to car within map later results in an
error, because 5 is not a list.
When I ran the above code in Petite Chez Scheme Version 7.4d, the
following error message occurred:
[Repl(16)] Error in car: 5 is not a pair.
Type (debug) to enter the debugger.
Flatt summarizes his argument as follows:
> Library implementors who deal in lists must still either set up
> elaborate guards against mutation, pretend that the problem doesn't
> matter, or require the use of a special immutable-list datatype that is
> incompatible with libraries whose authors set up elaborate guards or
> ignore the problem.
> Why all this hassle? If most Scheme code really does use and expect
> pairs in a functional way, can't we just switch to immutable pair? Most
> Scheme code will still work, untold security holes will have been
> closed, specifications will become instantly tighter, and language
> extensions like contracts will work better.
> Schemers have been reluctant to make this leap, because it has never
> been clear just how much code relies on mutable pairs. We don’t know how
> much the switch will cost in porting time and long-term incompatibility,
> and we don’t really know how much we will gain. We won't know until we
> try it.
> For PLT Scheme v4.0, we’re going to try it. In our main dialects of
> Scheme (such as the mzscheme language), cons will create immutable
> pairs, and pair? and list? will recognize only immutable pairs and
> lists. The set-car! and set-cdr procedures will not exist. A new set of
> procedure mcons, mcar, mcdr, set-mcar!, and set-mcdr! will support
> mutable pairs. (A related v4.0 change is that define-struct by default
> creates immutable structure types.)
> Of course, PLT Scheme v4.0 will support an R5RS language where cons is
> mcons, and so on, so many old programs can still run easily in the new
> version. The difference is that interoperability between R5RS libraries
> and PLT Scheme libraries will be less direct than before.
Despite Flatt's argument, however, I don't think that requiring that
pairs be immutable is a good idea for the purpose of this working group,
which is, according to the charter, "to facilitate sharing of Scheme
code" (see
http://www.scheme-reports.org/2009/working-group-1-charter.html):
> The purpose of this work is to facilitate sharing of Scheme code. One
> goal is to be able to reuse code written in one conforming
> implementation in another conforming implementation with as little
> change as possible. Another goal is for users of this work to be able to
> understand each other's code based on a shared and unambiguous
> interpretation of its meaning.
Requiring immutable pairs undermines sharing of Scheme code between
implementations, breaking compatibility with code that was previously
compliant with R5RS. Therefore, I vote against requiring immutable
pairs.
-- Benjamin L. Russell
--
Benjamin L. Russell / DekuDekuplex at Yahoo dot com
http://dekudekuplex.wordpress.com/
Translator/Interpreter / Mobile: +011 81 80-3603-6725
"Furuike ya, kawazu tobikomu mizu no oto." -- Matsuo Basho^
Brian Harvey
> Therefore, I vote against requiring immutable pairs.
My proposal was actually stronger than that; it /requires mutable/ pairs.
More precisely, it requires that CONS return a mutable pair.
As others have pointed out, this is not as controversial as I had thought
it might be, since the PLT people are careful not to pretend that their
language is Scheme.
Benjamin L. Russell
Wow, you're really in favor of giving PLT the proverbial kick in the
rear-end. Regardless of how much I use PLT (I tend to use Gauche and
Chez Scheme more), I am somewhat hesitant of booting PLT completely from
the Scheme-camp, if only because they have many users who use Scheme
(even if Racket is not Scheme). Requiring mutable pairs creates a clear
division between the Scheme and Racket camps, which could backfire if
more users later prefer Racket to Scheme.
My preference is to opt for the middle ground, and not require immutable
pairs, but not require mutable pairs, either. Generally, I think that
usage of immutable pairs encourages a more functional style of
programming, which allows program correctness to be proved more easily,
as well as confering various other benefits--a lesson learned from
Haskell, which is a purely functional programming language. The problem
with doing this in Scheme is that it breaks backwards-compatibility with
existing implementations. However, immutable pairs does not seem to be
a bad goal for the future.
It seems that immutable pairs should be a gradually introduced goal for
the future, but that it shouldn't be ignored completely. Scheme
programmers should be encouraged to program in a functional style, as in
such languages as Haskell and Clojure. For the time being, to preserve
backwards-compatibility, I would keep mutable pairs as the default, but
keep procedures for mutating pairs to a separate library, so that
programmers would be discouraged from using them. I would also
encourage immutable pairs to be used by allowing them as a separate
datatype by default.
Over time, as such languages that encourage programmers to program in a
functional style as Haskell and Clojure catch on, more programmers
should adopt the functional style, and more Scheme textbooks should
encourage the use of immutable pairs. Eventually, immutable pairs
could become the default, with mutable pairs relegated to a separate
library. By then, with luck, the dominant trend is Scheme would be the
functional style of programming, so that this change should not break
too many existing implementations, while allowing proofs of correctness
for Scheme programs to be written much more easily, as well as confering
various other benefits, including improved robustness of code and easier
introduction of language extensions.
John Cowan
> My preference is to opt for the middle ground, and not require immutable
> pairs, but not require mutable pairs, either.
Does that mean you are arguing for set-car! and set-cdr! to be optional
in the standard?
--
So they play that [tune] on John Cowan
their fascist banjos, eh? co...@ccil.org
--Great-Souled Sam http://www.ccil.org/~cowan
Benjamin L. Russell
> Benjamin L. Russell scripsit:
>
>> My preference is to opt for the middle ground, and not require immutable
>> pairs, but not require mutable pairs, either.
>
> Does that mean you are arguing for set-car! and set-cdr! to be optional
> in the standard?
For the time being, I think that set-car! and set-cdr! should be
relegated to modules.
Brian Harvey
> Wow, you're really in favor of giving PLT the proverbial kick in the
> rear-end.
That is not how I would characterize the situation. PLT have chosen,
as they say explicitly, to design a language that is based on Scheme
but is not Scheme. More power to them! May the best language win.
> My preference is to opt for the middle ground, and not require immutable
> pairs, but not require mutable pairs, either. ... The problem
> with doing this in Scheme is that it breaks backwards-compatibility with
> existing implementations. However, immutable pairs does not seem to be
> a bad goal for the future.
>
> It seems that immutable pairs should be a gradually introduced goal for
> the future... Scheme
> programmers should be encouraged to program in a functional style, as in
> such languages as Haskell and Clojure.
> Over time, as such languages that encourage programmers to program in a
> functional style as Haskell and Clojure catch on, more programmers
> should adopt the functional style, and more Scheme textbooks should
> encourage the use of immutable pairs. Eventually, immutable pairs
> could become the default, with mutable pairs relegated to a separate
> library.
NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO!
NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO!
I can't believe I'm reading this.
Yes, functional programming is great. I teach functional programming.
I urge my students to program functionally whenever they possibly can.
Over fifty years ago, John McCarthy brilliantly invented a programming
language loosely based on lambda calculus, but designed to be used, not
just to be reasoned about -- even though reasoning about programming was
at the core of his own concerns. Because of that choice, Lisp has
survived to become the second oldest programming language still in use,
and /not/, as in the case of Fortran, only because people are stuck with
a mass of unmaintainable legacy code.
The philosophy of Lisp is to give people a rich toolkit and not get in
their way with stupidities such as variable type declarations, idiosyncratic
syntax, etc, but /not/ to dictate to the programmer about how to program.
As the theoreticians of bondage and discipline languages continue to invent
flash-in-the-pan languages such as Pascal and Ada, Lisp sails on,
cooperating with its users instead of straitjacketing them.
Since then, /inspired by Lisp/, many people have invented purely functional
languages. How many are there by now? Haskell, ML, ... let's even throw
in the declarative languages like Prolog. These are elegant languages.
Add them all together and they don't have a tenth the usership of Lisp.
Why? I believe it's because programmers, good programmers, will always
choose good toolkits over straitjackets.
I want Scheme to be a Lisp, not an ultra-leftist sectarian dual of Pascal.
If you want to build an immutable-pair library, go ahead. But (in the face
of this attack on the core nature of Scheme) both WG1 and WG2 should make
it absolutely clear that any immutable pair library provided as part of the
language may not rebind the names CAR, CDR, CONS, LIST, APPEND, MAP,
FILTER, ASSOC, ASSQ, MEMBER, PAIR?, LIST?, APPLY, C[A|D]*R, FOR-EACH,
LENGTH, LIST->STRING, LIST->VECTOR, LIST-REF, LIST-TAIL, MEMQ, REVERSE,
READ, STRING->LIST, VECTOR-LIST, WRITE, and DISPLAY. In particular,
PAIR? must return #F for any immutable pairs provided, and LIST? must
return #F for any structure whose spine includes immutable pairs, and
the notation (...) must return a list made of mutable pairs when read
and printed, and any structure made of mutable pairs may not print as (...).
The language of the standard should make it clear that this is not a stopgap
provision, not a concession to legacy code, but is meant to be binding on our
children's children until the end of time.
I guess it's language implementors who need straitjackets, not
language users.
I close with a barefaced appeal to authority:
Background: I have been programming computers, in almost
every possible language, (including horizontal microcode)
since 1962 when, as a high-school student in Brooklyn, NY
I took a course in computer programming at Columbia U.,
given by an undergraduate named Joel Moses. I have loved
programming ever since.
In the past year I have probably written 1e4 lines of Scheme
code; some of it very pretty, and some of it very ugly.
For me a computer is an expressive instrument, like a musical
instrument. I program to express thoughts in a way that can
be unambiguously understood, by both my electromagnetic and
my biological friends. Thus, for me, the most important value
of a computer language is that it be as expressive and as free
of unnecessary restrictions as is technically possible.
I also feel strongly that it is not my duty to tell others how to
program, and I don't want others to legislate my style either.
Gerald Jay Sussman
Brian Harvey
> and printed, and any structure made of mutable pairs may not print as (...).
I meant "immutable" of course. :-/
John Cowan
> For the time being, I think that set-car! and set-cdr! should be
> relegated to modules.
Being in a module is not the same as being optional. Most of the
syntax keywords and identifiers in R6RS are in modules, but every
last one of them is mandatory for R6RS implementations.
My view is that "in a module" should mean "optional" and vice versa,
but I don't know that everyone agrees with me.
--
John Cowan co...@ccil.org http://www.ccil.org/~cowan
Any day you get all five woodpeckers is a good day. --Elliotte Rusty Harold
Benjamin L. Russell
> Benjamin L. Russell scripsit:
>
>> For the time being, I think that set-car! and set-cdr! should be
>> relegated to modules.
>
> Being in a module is not the same as being optional. Most of the
> syntax keywords and identifiers in R6RS are in modules, but every
> last one of them is mandatory for R6RS implementations.
>
> My view is that "in a module" should mean "optional" and vice versa,
> but I don't know that everyone agrees with me.
In this case, I think that the module should be optional, not required.
Requiring the module is equivalent to stating, "Mutable pairs should be
required." Making the module optional is equivalent to stating,
"Mutable pairs should be allowed, but made optional." While
implementations should be free to allow mutable pairs, they shouldn't be
forced to require them.
David Rush
> My preference is to opt for the middle ground, and not require immutable> pairs, but not require mutable pairs, either. ... The problem
> with doing this in Scheme is that it breaks backwards-compatibility with> the future...
> existing implementations. However, immutable pairs does not seem to be
> a bad goal for the future.
>
> It seems that immutable pairs should be a gradually introduced goal for
NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO!
NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO! NO!
David Rush
Benjamin L. Russell scripsit:
Being in a module is not the same as being optional.
> For the time being, I think that set-car! and set-cdr! should be
> relegated to modules.
My view is that "in a module" should mean "optional" and vice versa,
but I don't know that everyone agrees with me.
Alex Shinn
>> From: DekuDe...@Yahoo.com (Benjamin L. Russell)
>> Wow, you're really in favor of giving PLT the proverbial kick in the
>> rear-end.
>
> That is not how I would characterize the situation. PLT have chosen,
> as they say explicitly, to design a language that is based on Scheme
> but is not Scheme. More power to them! May the best language win.
For those not subscribed, one of the PLT developers has responded
on the scheme-reports public discussion list:
http://lists.scheme-reports.org/pipermail/scheme-reports/2010-June/000029.html
--
Alex
Benjamin L. Russell
To quote Barzilay's response in part:
> The problem is demonstrated by Matthew's post, the one that Benjamin
> mentioned, but in a later post he (Benjamin) made the mistake of
> saying:
> | [...] allowing proofs of correctness for Scheme programs to be
> | written much more easily [...]
> and following this line, you reply:
> > Over fifty years ago, John McCarthy brilliantly invented a
> > programming language loosely based on lambda calculus, but designed
> > to be used, not just to be reasoned about [...]
> and all of this is as if immutable pairs are something that fills a
> kind of a theoretical/masochistic need for self punishment in the form
> of correctness proofs. Something that *real* programmers never have
> to deal with, only "theoreticians of bondage and discipline
> languages". That couldn't be more *wrong*. On the side of proofs of
> correctness, there is nothing interesting, really. The bottom line is
> that this:
> (define (map f l)
> (define (loop l)
> (if (null? l) '() (cons (f (car l)) (loop (cdr l)))))
> (if (list? l)
> (loop l)
> (error "poof!")))
> can be proved as a correct implementation of map *assuming* no changes
> to the list ever occur in the call to `f', or more generally during
> the dynamic extent of the call to `map'. If you're one of these
> theoretical people, there's not much else to see here.
> The problem is on the side of the *working* programmer -- the one who
> lives in the *real* world. These people will often make the same
> assumption (and as Matthew points out, they almost always do), so they
> write the above definition and then they're done with it, or rather
> they *think* that they're done. But the problem starts with the fact
> that Scheme is a language with first-class values -- and `map' happens
> to be a function that uses that: it is a higher order function. This
> means that you're passing a mutable value to random code -- and this
> random code can now break invariants that your own code (`map', in
> this case) depends on unless you're extra careful.
Point acknowledged. So Barzilay's view is that the main problem with
mutable pairs is not about the difficulty of writing proofs of
correctness, but about introducing "mutable value[s] to random code,"
which can now "break invariants that your own code ... depends on." For
a "working programmer," this is the main concern.
Aaron W. Hsu
I have mostly stayed out of the mutable pair discussion taking place here and
on Scheme-reports because I've been too busy. However, I would like to point
out a few things about the discussion that I have not seen mentioned yet. I've
included the closest relevant message set I could find below, but I'll be
talking about the whole discussion.
Firstly, let's talk about the code in question: MAP. The proposed dangerous
code is:
(define (map proc lst)
(define (loop lst)
(if (null? lst)
'()
(cons (proc (car lst)) (loop (cdr lst)))))
(if (list? lst)
(loop lst)
(error 'map "not a list" lst)))
Aside from the obvious point that you wouldn't actually want to check if it
were a list before you started processing. People seem to have ignored what
R6RS did to address these issues when it comes to the MAP function. The R5RS
definition is flawed because it is underspecified. It doesn't explain what to
do in cases when the PROC is mutating the list. At least, I don't see any
language in there to deal with that. On the other hand, let's take a look at
the R6RS language for this procedure:
R6RS Section 11.9 on MAP says:
> The lists should all have the same length. Proc should accept as many
> arguments as there are lists and return a single value. Proc should not
> mutate any of the lists.
>
> The map procedure applies proc element-wise to the elements of the lists
> and returns a list of the results, in order. Proc is always called in the
> same dynamic environment as map itself. The order in which proc is applied
> to the elements of the lists is unspecified. If multiple returns occur
> from map, the values returned by earlier returns are not mutated.
>
> (map cadr ’((a b) (d e) (g h)))
>
> ⇒ (b e h)
>
> (map (lambda (n) (expt n n))
>
> ’(1 2 3 4 5))
>
> ⇒ (1 4 27 256 3125)
>
> (map + ’(1 2 3) ’(4 5 6)) ⇒ (5 7 9)
>
> (let ((count 0))
>
> (map (lambda (ignored)
>
> (set! count (+ count 1))
> count)
>
> ’(a b))) ⇒ (1 2) or (2 1)
>
> Implementation responsibilities: The implementation should check that the
> lists all have the same length. The implementation must check the
> restrictions on proc to the extent performed by applying it as described.
> An implementation may check whether proc is an appropriate argument before
> applying it.
Let's first notice the primary characteristics:
*) MAP does not have a specified order of evaluating the list elements.
*) PROC should not mutate the list
*) MAP must return a fresh copy of the lists when it returns multiple times.
*) Implementations must check the list lengths
*) Implementations must check the PROC but only to the extent of applying
it.
I'm not sure what the last point means, but it appears that even the most
compliant of Scheme implementations doesn't actually check the entire
procedure code for assignments to the list elements, or anything of that
nature, so I'm going to wait until one of the designers of R6RS explains what
that means.
In the mean time, let's revisit the above example of MAP. Obviously it doesn't
match the above specification, but it can avoid some of this because it's only
dealing with one list. From a standards point of view, we can assume that the
procedure doesn't mutate the list. And then we can say that its the
programmer's fault if something bad happens because a bad PROC was passed to
MAP. From the discussion, I gather that this sort of thinking is frowned upon
by some.
Nonetheless, that's the only problem I see with the above definition. I've
seen statements that the MAP *over* specifies because it enforces an order of
evaluation on the arguments, but that's not true. In fact, you aren't
guaranteed to get an error when you run this function with a bad PROC.
Chez Scheme Transcript [Mon Jun 14 20:30:12 2010]
> (define (my-map proc lst)
(define (loop lst)
(if (null? lst)
'()
(cons (proc (car lst)) (loop (cdr lst)))))
(if (list? lst)
(loop lst)
(error 'map "not a list" lst)))
> (define lst (iota 5))
> (define (bad-proc x) (set-cdr! (cddr lst) #f) #f)
> (my-map bad-proc lst)
(#f #f #f #f #f)
> (transcript-off)
Well wait a tick, wasn't this supposed to fail? At least, that's what we've
been told would happen. The example code above says that we should have
encountered an unexpected error that we haven't handled. Moreover, the claim
that we have overspecified the MAP isn't accurate, because that's exactly
what's happening here, we're evaluating the order in the opposite direction,
right to left.
If we evaluate the order from right to left instead of left to right, then we
can avoid this entire problem. If we grab all the pairs in the list before we
ever apply the procedure, we can avoid the mutation of the list causing us
problems like an unencountered error. We can still see the effects of the
mutation to the list if, instead, we mutate the CAR cell. However, this is
much less problematic.
So, we can write a "safe" MAP, and it's not that hard either. Unfortunately,
this would require us to specify an order of evaluation on the lists. Still,
no one has pointed this out yet, that I can see. Forgive me if someone already
has.
So, there is still some benefit to immutable pairs, because it let's us use
the straightforward idiom for these sorts of things. Still, I don't think this
is strong enough a reason. Especially -- and now we're moving into opinion
territory -- I really don't think that having two different copies of the
exact same structure, with one mutable, and the other not, is a good idea. So
we should have immutable bytevectors, and mutable ones? Vectors? Strings? I'm
sorry, but I don't think that we should have this sort of duality by forcing
two disjoint types to exist for every primitive datatype for which we could do
so. I'm saying that on a point of design I don't like the choice to go with
two different data structures as the solution.
Another point that I don't think people have brought up, though David, I
think, alluded to it, is that if the procedure you're passing can mutate this
list, it's safe to assume that the list came from the outside world. That is,
you can't construct a situation in which your private structures are in danger
because a procedure from the outside world is altering some lists. Thus, it is
possible to ensure that your code and data is safe, because if the malicious
code at hand can already mutate your data, it can already do so; it doesn't
need to use MAP.
This does require some programming discipline: we expect a programmer not to
write a procedure that mutates the lists also being passed. Scheme is full of
these situations. We expect them not to call string-set! on vectors, for
example. I'm not saying that it isn't an issue, but I don't think it's an
issue strong enough to warrant breaking backwards compatibility and
introducing a separate, redundant data type that is exactly the same as the
previous one, except that you can't mutate it. I'm not in favor of this as a
core approach to the language in the standard.
Still, I think Eli is right that we shouldn't be so quick to dismiss immutable
pairs outright. We need to be honest about the issues they address and their
advantages, of which there are plenty of good things.
Aaron W. Hsu
Benjamin L. Russell
> This does require some programming discipline: we expect a programmer not to
> write a procedure that mutates the lists also being passed. Scheme is full of
> these situations. We expect them not to call string-set! on vectors, for
> example.
This is exactly the gist of the problem, however; how do you know
whether a given programmer follows this discipline? The whole point of
functional programming is to make it less likely for the programmer to
write dangerous code.
While maintaining backwards-compatibility with legacy code is important,
I don't see why it should constrain the evolution of the language.
This issue is as much a social as a technology issue, if not more so;
the choice of a language where programmers can do almost anything that
they want (including shooting themselves in the foot) vs. a language
designed so that programmers normally cannot shoot themselves in the
foot is a social one, not a technological one. It comes down to how
intelligent we assume the programmer to be.
Of course if we assume that the programmer is intelligent enough not to
shoot himself/herself in the foot, then we would prefer the language
with more freedom to do anything, but mistaken assumptions can occur,
and how do we guarantee that they won't occur? Are we to assume that
programmers never use Scheme for mission-critical applications, or that
all Scheme programmers are intelligent enough never to shoot themselves
in the foot? Schemers must be allowed to be as creative as possible,
but I don't see why mutable lists promotes a better style of programming
than immutable lists for the potential future.
If all Schemers were star programmers who never made mistakes, then why
did anybody bother to invent immutable lists in one implementation with
many users in the first place? At least some users of that
implementation thought that the problem was significant enough to
conduct an experiment and make lists immutable by default, even at the
cost of changing the language into something that was no longer Scheme.
While I *don't* think that immutable lists are a good idea now for the
standard, I *do* think that they are a good goal for the future.
Backwards-compatibility with legacy code must be maintained, but Scheme
should also evolve toward becoming a language which reduces unnecessary
burden on programmers. I think that the way to do this now is to keep
mutable lists as default for this standard, but relegant set-car! and
set-cdr! to modules, and to make those modules optional, so that
implementations are less likely to include them in the future.
>
> Still, I think Eli is right that we shouldn't be so quick to dismiss immutable
> pairs outright. We need to be honest about the issues they address and their
> advantages, of which there are plenty of good things.
There seems to have been a lot of misunderstanding in the related discussion
thread on Scheme-Reports at
http://lists.scheme-reports.org/pipermail/scheme-reports/2010-June/000029.html
(for some reason, the site seems unavailable at the moment). Just for
the record, let me point out that Barzilay was only opposed to mutable
*lists* by default, not to other mutable data structures.
-- Benjamin L. Russell
--
Brian Harvey
>I don't see why it should constrain the evolution of the language.
I think this is a red herring. All the arguments I've seen have been for
the /desirability/ of retaining programmer choice, not about the need to
maintain reluctant compatibility with old code.
I vote that set-car! and set-cdr! be mandatory and not hidden in optional
modules in WG1. Not for the sake of old code but for the sake of what I
guess is an old philosophy: that computer programs should not think
they're smarter than their users.
Alaric Snell-Pym
> This issue is as much a social as a technology issue, if not more so;
> the choice of a language where programmers can do almost anything that
> they want (including shooting themselves in the foot) vs. a language
> designed so that programmers normally cannot shoot themselves in the
> foot is a social one, not a technological one. It comes down to how
> intelligent we assume the programmer to be.
This, I think, is a key observation: not to make it impossible, just
less likely.
I think there's a common misconception that (if I may exaggerate!) the
choice is between languages that give you raw pointers and the ability
to self-modify your code through destructive mutation of procedures...
and languages that don't give you conditionals as they make static
analysis difficult and the programmer might forget to do something
important in one of the branches so they might introduce bugs.
The suggestion here isn't to make mutation impossible - merely to make
it require more explicit effort, so it is more 'obvious', and therefore
less likely to happen in unexpected places.
Whether to make pairs immutable by default, or just their cdrs, or just
to make set-car! and set-cdr! require an explicit import to 'enable'
them in any given module, is really just the detail of how this might be
done.
The fact that much library code might be surprised by list mutations in
code from outside the library is a good argument in favour of making
list mutations more difficult; however, the burden can also be placed on
the other side - somebody who mutates a list should, perhaps, as that is
the exception rather than the rule, take the time to carefully consider
who else might have a reference to that list, and how they might be
affected by the mutation. That suggests the "make set-*! be in a module
that needs explicit loading" approach.
However, making cons cells by immutable *has* worked well for PLT, as
far as I have heard - apparently the uses of cons cell mutation are few,
far between, and often handled well by other approaches; which does
indeed suggest that making too many sacrifices (both in terms of the
complexity of analysis cases due to the possibility of mutation, and in
terms of implementation efficiency by prohibiting various tricks that
can be performed when things are immutable) might not actually be worth it.
It's a tough decision; certainly not an open-and-shut case!
> While I *don't* think that immutable lists are a good idea now for the
> standard, I *do* think that they are a good goal for the future.
> Backwards-compatibility with legacy code must be maintained, but Scheme
> should also evolve toward becoming a language which reduces unnecessary
> burden on programmers. I think that the way to do this now is to keep
> mutable lists as default for this standard, but relegant set-car! and
> set-cdr! to modules, and to make those modules optional, so that
> implementations are less likely to include them in the future.
Yes, I also think that's quite a pragmatic solution for the short term.
ABS
--
Alaric Snell-Pym
http://www.snell-pym.org.uk/alaric/
Neil Van Dyke
> However, making cons cells by immutable *has* worked well for PLT, as
> far as I have heard - apparently the uses of cons cell mutation are few,
That's my understanding, as well. That's what I heard from the few PLT
people I talked with the other day, and is pretty much my own experience.
I did feel some major pain having to convert *one* library of mine not
to return mutable pairs. It was the very first Scheme library I ever
wrote, which wasn't what I'd call idiomatic Scheme. My CSV-parsing
library required a somewhat unfortunate but trivial change. The only
other pain I felt was in making a DrScheme language for SICP exercises.
Also, if I had to choose between immutable and mutable pairs, I would
choose immutable. For example, before PLT moved the default for pairs
to be immutable, I had already begin using immutable pairs in one of my
libraries, for time&space-efficient representation of paths of Web URLs,
especially when relative URLs are resolved wrt a base URL. (Using
mutable pairs would've been a nightmare, as exposing the representation
could mean that one not-unlikely oops by a library user could corrupt
every URL in the system, or it would've meant lots and lots more consing
to expose only copies and would've taken away one of my algorithmic
efficiencies from shared tails as well.) The specifics here are just
one concrete example of why I like immutable pairs -- I've often found
similar situations when trying to write robust libraries that share
lists with calling code.
David Rush
Alaric Snell-Pym wrote at 06/16/2010 05:16 AM:That's my understanding, as well. That's what I heard from the few PLT people I talked with the other day, and is pretty much my own experience.
However, making cons cells by immutable *has* worked well for PLT, as far as I have heard - apparently the uses of cons cell mutation are few,
John Cowan
> Maybe, but SET-CAR! and SET-CDR! are not bound by default in an R6RS
> top-level. That certainly invokes a level of annoyance that makes them as
> good as optional for most practical purposes.
Given the required machinery of an R6RS program (R6RS doesn't have a REPL),
adding one extra import isn't a big deal. I'm proposing that for WG1
purposes, a REPL is allowed to pre-import an implementation-defined set
of modules.
> Module-izing SET-CAR! and SET-CDR! is more than a little bit different from
> module-izing IO.
Doubtless. But what differences do you have in mind?
--
"Well, I'm back." --Sam John Cowan <co...@ccil.org>
John Cowan
> *) Implementations must check the PROC but only to the extent of
> applying it.
>
> I'm not sure what the last point means, but it appears that even the
> most compliant of Scheme implementations doesn't actually check the
> entire procedure code for assignments to the list elements, or anything
> of that nature, so I'm going to wait until one of the designers of
> R6RS explains what that means.
Actually it says "check the restrictions on PROC", not "check the PROC".
The restrictions on PROC are that it is actually a procedure, that it
accepts the relevant number of arguments, and that it returns exactly
one result. These all can be checked by applying the procedure, but
may be checked in advance of applying it.
--
John Cowan co...@ccil.org http://www.ccil.org/~cowan
Most languages are dramatically underdescribed, and at least one is
dramatically overdescribed. Still other languages are simultaneously
overdescribed and underdescribed. Welsh pertains to the third category.
--Alan King
John Cowan
> I vote that set-car! and set-cdr! be mandatory and not hidden in optional
> modules in WG1. Not for the sake of old code but for the sake of what I
> guess is an old philosophy: that computer programs should not think
> they're smarter than their users.
I do not think that word ("mandatory") means what you think it means.
To make something mandatory is to say that an implementation that does
not provide it is non-conformant. Put otherwise, an optional feature is
one that a conformant program cannot rely on a conformant implementation
providing. R5RS examples are COS, MAKE-RECTANGULAR, WITH-INPUT-FROM-FILE,
and LOAD.
But perhaps I miss your point here.
--
Here lies the Christian, John Cowan
judge, and poet Peter, http://www.ccil.org/~cowan
Who broke the laws of God co...@ccil.org
and man and metre.
Brian Harvey
> I do not think that word ("mandatory") means what you think it means.
> To make something mandatory is to say that an implementation that does
> not provide it is non-conformant.
That's exactly what I meant. An implementation that does not provide
SET-CAR! and SET-CDR! automatically (that is, without the user having
to import modules or anything else other than just use them) should be,
I propose, non-conformant. Not Scheme. Some other language, maybe even
a good language, but not Scheme.
IMO this should be true of both WG1 and WG2 dialects. Nothing called
"Scheme" is allowed not to provide SET-CAR! and SET-CDR!.
Aaron W. Hsu
> Actually it says "check the restrictions on PROC", not "check the PROC".
> The restrictions on PROC are that it is actually a procedure, that it
> accepts the relevant number of arguments, and that it returns exactly
> one result. These all can be checked by applying the procedure, but
> may be checked in advance of applying it.
Looking at the documentation, it says that PROC should not mutate the lists.
That's also a restriction on PROC.
Aaron W. Hsu
Aaron W. Hsu
I agree that every Scheme should provide mutable pairs. It doesn't make sense
to allow them to get ride of these. However, as you will have read in my other
proposal, I think that it makes sense to allow other Schemes to choose to make
immutable pairs the default if they so choose. This won't adversely affect
you, but it will allow others to take advantage of immutable pairs in their
own code if they want.
Aaron W. Hsu