Comments on The Racket Blog: Getting rid of set-car! and set-cdr!

Mike, mcons, mcar, mcdr, set-mcar!, and set-mcdr! ...

2010-05-13T18:35:41.494-04:00

Mike, mcons, mcar, mcdr, set-mcar!, and set-mcdr! are provided by scheme already. Just add (require scheme/mpair) to your definitions to get more mutable pair functionality. You will need to use slightly different function names, e.g. mlist, mlength, etc. The /scheme/mpair module is well documented.

When I first wrote N-Queens, returning the solutions was a requirement. So naturally I built the solutions with cons for later return. After my earlier post, I realized that two additional lines of code would eliminate all cons operations. Now, it doesn't garbage collect until N = 17:

> (begin (collect-garbage) (time (N-Queens 17)))
cpu time: 6670485 real time: 6702624 gc time: 618
95815104
618ms time in gc while taking 1 hour and 51 minutes to determine 95,815,104 solutions isn't bad.

The key is:
(else
..(set-mcdr! prior-column (mcdr column)) ..(set-mcdr! column solution)
..(begin0
....(next-queen safe-columns column new-count)
....(set-mcdr! column (mcdr prior-column))
....(set-mcdr! prior-column column)))

Gene

Way to go PLT Scheme 4.x. You've just made it...

2010-04-14T17:01:12.269-04:00

Way to go PLT Scheme 4.x. You've just made it impossible for me to use your Scheme to work through the exercises in The Scheme Programming Language (4th edition) -- see for example Exercise 2.9.3 on page 55.

As if learning a language like Scheme isn't hard enough for us poor suckers trying to break out of the imperative/object world. Do you really have to add yet more beautiful impediments?

I know this is an old, and probably dead thread, b...

2010-01-27T22:25:42.975-05:00

I know this is an old, and probably dead thread, but I did want to respond to one post.

----Quote----
Robby said...
...
But, in any case, these abstract arguments (either way) ultimately need to be backed up with real programs. Let me encourage you once again to provide some to back up your arguments. We have found none in a large body of code. Have you investigated a body of code and found some?
December 16, 2007 6:56 PM
----End Quote----

Over 25 years ago, I used set-cdr! in a PC Scheme implementation of N-Queens for an AI class. Besides using set-cdr!, calls to move a queen were properly tail recursive. I noticed the PLT Scheme benchmark didn't use tail recursion for moves, so I modified my code to match the benchmark. The following times compare the improvements for just using set-cdr! and for using set-cdr! combined with tail recursion:

PLT Scheme Benchmark:
> (begin (collect-garbage) (time (nqueens 15)))
cpu time: 158899 real time: 158982 gc time: 16920
2279184
(execution time = cpu time - gc time = 142.0s)

set-cdr! version:
> (begin (collect-garbage) (time (N-Queens 15)))
cpu time: 138616 real time: 138787 gc time: 3286
2279184
(execution time = cpu time - gc time = 135.3s)

set-cdr! plus properly tail recursive moves:
> (begin (collect-garbage) (time (N-Queens 15)))
cpu time: 119845 real time: 120061 gc time: 3284
2279184
(execution time = cpu time - gc time = 116.5s)

As you can see, using set-cdr! improved overall cpu time by about the same amount as using properly tail recursive moves. The major performance improvement for set-cdr! came from reduced garbage collection. N-Queens is just one example of back-tracking used to traverse a search space. Any time the search space can be pruned before the back-tracking call is made, and restored on return from the call, set-cdr! should yield improved performance. It's also very localized, as shown by the following code snippet:

(else
..(set-mcdr! prior-column (mcdr column))
..(begin0
....(place&move safe-columns
...........(mcdr safe-columns) safe-columns
...........(cons (mcar column) solution) count)
....(set-mcdr! prior-column column))))))

In the above example, prior-column and column traverse the list, while safe-columns always points to it's beginning. The list is never copied, just manipulated with set-mcdr! as the search space is traversed. Also, the list goes from 0 to N to simplify handling prior-column.

Gene Snider

T: You do realize, don't you, that set-car!...

2008-06-24T22:03:00.000-04:00

T: You do realize, don't you, that set-car! and set-cdr! are still available in PLT Scheme 4.0, only as a library instead of as a built-in feature? Given that, I don't see what you are so upset about. You're free to use set-car! and set-cdr! as much as you want.

T: In fact, most modern languages
dropped the...

2008-06-24T10:51:00.000-04:00

T: In fact, *most* modern languages
dropped the number zero as a
pointer. Most languages also
restrict you from using a ton of
other features, so which
implementation are you going to
install: C? assembler? maybe
you'll get a soldering iron?

Don't you just love it when language maintainers d...

2008-06-24T06:42:00.000-04:00

Don't you just love it when language maintainers drop a feature because someone, somewhere, might misuse it?

What's next? Dropping the number zero, because it can cause a divide-by-zero error?

I'm de-installing PLT today and switching to an implementation which doesn't think I'm an idiot.

Existential Type: From this side of the fence I ca...

2008-01-26T22:05:00.000-05:00

Existential Type: From this side of the fence I can say that Scheme covers all of ML, with all types that were and will be written. But this is a second pointless flame, and still irrelevant to the context. I could just as well point at the many limitations of ML types (eg, what's the real type of map? sqrt? printf? collatz? GetFunction("foo","bar.dll")?). But that's not going to do any good, so I'll stop replying. Feel free to continue on the PLT list, or email me.

Michael: I'm talking about several efforts that attempt to get the benefits of a dynamic language into a static language like ML. There was some work done on reflecting types (or reifying types) which makes it possible to sort of package a value together with a type object (in the run-time sense; it becomes a value). IIRC, there was also something related to universal types that goes in the same direction.

Personally, I found that MLers who blindly bash Scheme for it's lack of types are just as bad as Schemers who blindly bash all static typing. IMO (and in the opinion of many other good people I've talked to) there are very good advantages on both sides -- and the real challenge is to get dynamic languages like Scheme to benefit from the advantages of statically typed languages like ML, and vice versa. Some people choose to work on just that (from either side), some people don't but appreciate those who do, and some people will inevitably continue to spit out useless comments even in a completely unrelated context, like the above anonymous poster.

Eli, I agree with you about the pointlessness of a...

2008-01-26T21:30:00.000-05:00

Eli, I agree with you about the pointlessness of an ML-vs-Scheme flame war. Can you be more explicit about what you mean by "type reflection"? That sounds interesting, but I have no idea what you're talking about.

Eli, you seem forget that all Scheme fits into tin...

2008-01-26T19:59:00.000-05:00

Eli, you seem forget that all Scheme fits into tiny corner of ML, namely a single recursive datatype.

The conversion of my code took less than a day (ab...

2008-01-26T19:41:00.000-05:00

The conversion of my code took less than a day (about 10000 lines, a guess, for I never counted the nr of lines) There are two types of instances in which I used set-cdr!: for assoclists and imperative queues. Assoclists now have become immutable lists of mutable pairs with a hybrid-assq procedure added. The imperative queues remain mutable lists, the cdr of the last pair being the only one being updated. My code did not contain anything like append! or reverse!. I found no trouble in swithing to v3.99.0.9. I say yes to the better conditions for optimization.
Jos Koot

"Existential Type": your comment begs the exact sa...

2008-01-25T23:27:00.000-05:00

"Existential Type": your comment begs the exact same reply with macros, except that five years is probably optimistic, and twenty years is an underestimate. Or type reflection that maybe some day will get ML some of the advantages of Scheme.

(But this is, of course, a pointless flame, just like your comment. FWIW, the main issue is legacy code, and switching to Scheme with immutable lists is slightly easier than switching to ML. At least for us Scheme freaks.)

In another five years or so you'll be where ML was...

2008-01-25T23:12:00.000-05:00

In another five years or so you'll be where ML was twenty years ago! Better late than never, I suppose, but, really, what is the point?

The problems you describe with mutability remind m...

2007-12-28T09:39:00.000-05:00

The problems you describe with mutability remind me of type-theory where each kind of thing is separated into its own type. Then you can always use the types in conjunction with each other if you need the functionality of both.

For example, if you had the types `list' and `mutable' you could distinguish between an immutable list of immutable elements, an immutable list of mutable elements, a mutable list of immutable elements, and so on, and put this in your "contract system" (whatever that is).

This not only documents the usage of things like mutability, but also allows the compiler (in theory) to check such constraints on inputs and outputs.

When a function like `map' expects an immutable list, it will simply use the `list' type without restricting the mutation of elements. But in places where that could be harmful, a different type can be used. The conventional Scheme way of allowing everything to be mutable prevents this separation of distinct properties of values.

I'm not too familiar with how Scheme implements things, but the general way this is done is to box things that are mutable.

Paul, this is not what I meant by concrete. No one...

2007-12-16T18:56:00.000-05:00

Paul, this is not what I meant by concrete. No one said (or attempted to prove) that mutable cons cells were useless. Indeed, we still support them, but we just do not use them by default anymore.

The comment "justifying mutable list removal because large classes of programs do not require them" misses half of the problem with mutable lists. The first half of the problem, in fact. Matthew's post clearly explains why mutable lists cause problems in concrete ways and, if you permit me to say so, makes a far more convincing abstract case against mutable pairs than your abstract arguments for them.

But, in any case, these abstract arguments (either way) ultimately need to be backed up with real programs. Let me encourage you once again to provide some to back up your arguments. We have found none in a large body of code. Have you investigated a body of code and found some?

Somewhat more concrete:

- presume the run-...

2007-12-16T18:45:00.000-05:00

Somewhat more concrete:

- presume the run-time creation, storage and/or retrieval of arbitrarily recursive list structured data is useful (or please prove otherwise).

(Personally see no value in presenting any particular program utilizing such capabilities, as the potential usefulness of such data structures representing state transition graphs, or more generally arbitrarily self recursive data representations are self evident; just as I see no value in any example given of how list mutation may yield indeterminate behavior in the absents of the specification of evaluation order; as overall the less flexible and deterministic a language is, the less useful it tends to be. Thereby I view dropping native mutable lists in an effort to improve determinism, in effect an attempt to improve a deficiency by removing utility; as opposed to improving its utility, by removing a deficiency.)

Implying:

- a facility to create/manipulate such data at run-time is required.

- mcons (and friends) are only rudimentarily facilitates, which exclusively operate on a now severely crippled data type because mutable lists have been alienated from the language (incompatible with car and friends) and thereby incompatible with the majority of all native list functions and thereby now require an entirely redundant and largely absent collection of functions to specified to operate on and utilize them (inclusive of their inability to be evaluated as code):

- a facility to store and retrieve such data at run-time is required.

- as there is no current reader support to denote mutable lists:

- (mcons 'a '{b}) -> {a . (b)} ; not {a b} as likely
(cons 'a '(b)) -> (a b) ; expected by analogy

- (define x (mcons '+ (mcons 1 (mcons 2 null)))) ; i.e. {+ 1 2}
(with-output-to-file "f" (lambda () (print x)) 'text 'replace)
(with-input-from-file "f" (lambda () (read)))
=> (+ 1 2) ; wrong

- (define x (mcons 1 null)) (set-mcdr! x x) ; i.e. #0={1 . #0}
(with-output-to-file "f" (lambda () (print x)) 'text 'replace)
(with-input-from-file "f" (lambda () (read)))
=> #0=(1 . #0#) ; wrong

[not to mention (define x '#0=(1 . #0#)) isn't accepted anymore]

So overall, scheme absent mutable lists removes an entire class of capabilities which which was never proven to be useless, in fact arguably known to be otherwise, nor given analogous facilities of comparable utility.

Yes, such facilities may be structured from non-native structured data types and a corresponding new set of support functions; just as in most languages; however scheme was previously unique in that such a capability was inherent. (while were at it, maybe list data types and functions should be removed entirely, as after all, they're not strictly necessary as evidenced by most all other languages).

In hind sight, justifying mutable list removal because large classes of programs do not require them, or that the language's specification may be easier in their absents, or because the contract facility implementation isn't capable determining if list data is in fact potentially mutated; hardly seems reasonable. IMHO

The entire purpose of this experiment was to avoid...

2007-12-15T22:35:00.000-05:00

The entire purpose of this experiment was to avoid caveats like "seems", "likely" and "potentially". If you have real examples to show, that would be interesting. So far we have far better abstract arguments against mutation than for it, and no concrete experience suggesting it should be brought back.

Also, I should remind you that mcons (and friends) exist, as do mutable structs. These are as "native" as it gets.

A little late, but ...

Once one acknowledge...

2007-12-15T22:30:00.000-05:00

A little late, but ...

Once one acknowledges value of circular/recursive list data, it follows that there is likely value in the native runtime creation of such data as may be used for example to express arbitrarily recursively defined hierarchical information; which beyond the trivial, seems seems like a significant loss to the language to push such capability outside the baseline scope of the language by default.

Yes, such capability may be defined and utilized as required although not as elegantly as if it were native; however it seems a shame to seriously consider alienating the previously native capability to dynamically formulate native list data from datum not known at program specification/compile time (i.e. the ability to formulate and manipulate such list datum from information extracted during run-time, as data bases typically are, can not be performed natively without set-car! set-cdr!, nor specified purely functionally); as the loss of such a potentially powerful and useful capability seems
like a poor trade in exchange for the questionable value of default immutable lists, especially as the mutability of function argument can most typically be easily determined within a function, and optimizations applied accordingly, and in the few cases where it can't, so what, presume it may be mutated. (If the concern is limited to map, then simply specify that map's arguments are presumed to not be mutated until terminated, or generally forbidden).

We have so far not changed the interaction of `con...

2007-11-27T11:32:00.000-05:00

We have so far not changed the interaction of `cons' with `eq?' or `eqv?'. Specifically, `cons', `list', etc. are guaranteed to create fresh cons cells, in the sense that `eq?' distinguishes them, even though the cons cells are immutable. I think we may want to remove this guarantee eventually, because it would make some constant-folding optimizations easier and enable hash-consing, but we'll take one step at a time.

On replacing set! with set-box!: in a sense, this ...

2007-11-27T11:27:00.000-05:00

On replacing set! with set-box!: in a sense, this is so easy that the compiler does it automatically. That is, mutable variables are already implemented via boxes. You always know statically whether a variable needs to be boxed and unboxed due to lexical scope plus rules on mutating module-defined identifiers. For essentially the same reason, `set!' doesn't really cause much trouble; programmers usually see `set!'s and know to treat the relevant variable with care --- in contrast with `set-car!'s, which could be in a library that you don't see.

Wow, did I make a mistake.

Background.
2007-11-27T11:12:00.000-05:00
Wow, did I make a mistake.

Background. In PLT Redex, the stepper uses mutable lists to represent the currently visible portion of the reduction graph. When someone clicks the "next" button, it does a set-cdr! to add something to the end of that graph.

The Mistake. When I converted the code to v4, I figured that I should preserve the mutation, so I went in and changed a few set-car!s to set-mcar!s and then changed about 15 or 20 uses of filter, for-each, ormap, list-ref, and friends to versions of those that worked on mutable pairs instead of immutable ones. This took about 2 hours.

Not too bad, you might think. Two hours? Sometimes fixing one little bug can take longer than that, days even. Got away cheaply, you might think ...

What I Should Have Done. Today I decided that I wanted the code to work in both v4 and in earlier versions of PLT Scheme, since the code'll be on PLaneT, after all and not everyone is using v4 yet. Sigh. So now I need to go undo that work and copy the list instead of mutating its tail. So I did that.

5 minutes. Done. Working code.

10 more minutes: removing all of the now useless helper functions that dealt with the mutable-pair versions of filter, for-each, ormap, list-ref.

Oh well. Lesson learned, I suppose.

Are you considering changing the behaviour of eq? ...

2007-11-26T16:14:00.000-05:00
Are you considering changing the behaviour of eq? or eqv? on (now immutable) pairs? Currently, two immutable pairs whose cars and cdrs are eq? can only be distinguished by eq? or eqv?. As such, should they really be considered to be distinct or is their apparent distinctiveness simply an artifact of the implementation that should be hidden from the programmer?

How difficult would it be to replace set! with exp...

2007-11-21T13:18:00.000-05:00
How difficult would it be to replace set! with explicit boxes?

Did not observe any problem beyond the typical usa...

2007-11-18T16:15:00.000-05:00
Did not observe any problem beyond the typical usages noted in the article when I moved SSAX and SXML to R6RS libraries.

Typical use is in implementing "efficient" queues. I expect an applicative queue such as found in Okasaki would work fine on modern hardware and scheme implementations.

I doubt there is a systemic problem out there.

Well, I've been online now for over 30 minutes, an...

2007-11-18T00:55:00.000-05:00
Well, I've been online now for over 30 minutes, and AFAIK, I haven't been hacked. This is a banner day. Hi Matt; great article! Out of necessity, from a security standpoint, I have converted all my boxes to some flavor of *nix. As soon as I can download 3.99, I'll try to reproduce the flavor of the data from my flatten benchmark article. This time it will be different, simply because they'll be on a new OS. However, I have a bunch of varients of the flatten algorithm, using both muttable and immutable methods. As I recall from my earlier results, the biggest difference advantage to using mutation came about when a poor algorithm had been choosen to begin with, that required the reversal of the result list. These quite substantially improved their performance with the use of reverse! However, the more elegant functional solutions, under favorable conditions, actually out performed even the fastest mutable algorithms. Not typically, but definitely always in the race. The success of building functional solutions, which are also efficient is certainly achieved with other functional languages. I'll have to redesign my queue routine, as you mentioned, but it will be worth the effort. I'm looking forward to getting a copy on my box as soon as possible.

Take care.

--kylr

Yes. Version 3.99.0.2 has `make-reader-graph' for ...

2007-11-13T22:16:00.000-05:00
Yes. Version 3.99.0.2 has `make-reader-graph' for creating cycles built from immutable pairs. We need a better name, but the current name reflects that `read' still supports the #n= and #n# graph notation. (We've dropped support for cyclic syntax objects, though, so `read-syntax' no longer supports the graph notation).