Really un-mutable Scheme

Didn't notice this being mentioned on LtU yet: PLT is going really really un-mutable, which seems like a rather cool and worthy experiment to my mind, and will probably highlight some of the more pragmatic and cultural aspects of managing the development of a language in light of the user community.

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.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Get it while it's hot

This has already happened, in prerelease form - you can download it from here (version 3.99).

Kudos for gutsy language changes!

I would recommend fixing equality next.

What's wrong with equality?

PLT Scheme has a number of different equivalence predicates (eq?, eqv?, equal?). What about them should be fixed?


Scheme has a number of different equivalence predicates (eq?, eqv?, equal?). What about them should be fixed?

Well, I just tried to build and install 3.99 to see if it has also changed eqv? or not, but install failed while trying to copy docs (I used a non-standard install prefix), so I couldn't. But fortunately I don't need to figure out what was wrong. Searching the blog page, I can see someone mentioning the issue and the response was that it hasn't been fixed. eqv? compares cons cells by identity. Now that cons cells are immutable values, that is no longer the right thing to do and should be fixed.

Here is how equality should work. Mutable objects with identity should only be considered equal iff their identities are equal (the objects are the one and same object). This makes equality invariant with respect to mutation. Immutable values without identity should be considered equal iff they have equal tags (type) and their parts are pairwise equal. Equality should also be reflexive, symmetric, and transitive. This is particularly tricky when comparing floating point numbers (with nan).

That Scheme has so many equivalence predicates is a symptom of the problem. The problem goes somewhat beyond equality itself, though. The problem really is that Scheme has traditionally not offered any immutable aggregate/compound data types. Nevertheless, Scheme programmers (including me while programming in Scheme) frequently wish to treat some mutable objects as immutable values. A symptom of this is the use of the equal? predicate, which doesn't work correctly for objects that have both mutable and (wishfully) immutable parts.

Still need test for object identity

I think the eq? semantics is still indispensible, if one can create immutable cyclic structures (and as I gather PLT scheme can), since one may wish to know when one has surveyed the whole representation. I don't see how one can code this without something like eq?

But you still want `eqv?'

Two things:

1. It would be easy to write such an equality predicate, keeping in mind some limitations with respect to structures (you can't tell if structures are immutable, I think, and also structures can be opaque). Obviously functions can still only be compared for intensional equality.

2. You still need `eq?'/`eqv?', since they have very different performance behavior from `equal?' or from the predicate you describe. You probably could collapse `eq?' and `eqv?', since they only differ on numbers and characters.

Just conses though

Not entirely 'really un-mutable': variables, vectors, and various other data structures will remain mutable, it seems. (Which is probably a good idea, though the differences in implementing a compiler and garbage collector for a pure Scheme would be interesting.)

Does this imply...

...any sort of real "breakage" from standard scheme? As a complete neophyte, if I start learning scheme with this version, how warped will my code be compared to "regular" scheme?

Mutable conses enable a few

Mutable conses enable a few 'hacks' -- sometimes to prevent allocating new pairs (possibly wrong-headed), sometimes to implement mutable structures using pairs -- but are not that common in typical Scheme code.

Not much breakage, not very warped.

This would be a fine way to approach Scheme. Mutable pairs are rarely used, and are generally recommended against. The PLT announcement makes it pretty clear that they were willing to do this only because it seems like a fairly reasonable and conservative change at this point.

This does not imply mental warping (the bad kind at least)

One manifestation of this change is that you can not modify a list over which you are iterating. This is not surprising for anyone coming from other programming languages.

Here is an example of how you might utilize mutable cons cells from TSPL: set-car! and set-cdr!.

Cyclic data structures

I've written a fair amount of scheme code that mutates cons cells to create cyclic data structures. I don't think it would be terribly easy to rework this code to use immutable data structures, but I think it would be easy and issue-free to use mcons cells instead.

In fact, I shall shortly add the following snippet to my scheme48 library:

(define mcons cons)
(define mcar car)
(define mcdr cdr)
(define set-mcar! set-car!)
(define set-mcdr! set-cdr!)
(define set-car! *undefined*)
(define set-cdr! *undefined*)

where I already have (define *undefined* (if #f #t)). That doesn't provide me with much in the way of useful guarantees, but it should reinforce my intent...

PLT supports immutable cyclic data structures

cf. Matthew Flatt's response to Shiro Kawai's question along these lines.