scheme/r7rs

Fork 1

Deprecating pair mutation #192

New issue

Open

opened 2023-11-30 13:21:15 +00:00 by dpk · 4 comments

dpk commented

2023-11-30 13:21:15 +00:00

Owner

It has been proposed that set-car! and set-cdr! should have deprecation warnings attached to them like the one we plan to apply to string-set!.

In principle, I’m not against this. But I feel it will be harder to justify in the report text than string-set! deprecation.

R6RS’s rationale volume offers four motivations for its somewhat half-hearted deprecation of set-car! and set-cdr!:

The presence of mutable pairs causes numerous problems:

It complicates the specification of higher-order procedures that operate on lists.

It inhibits certain compiler optimizations such as deforestation.

It complicates reasoning about programs that use lists.

It complicates the implementation of procedures that accept variable numbers of arguments.

(They are not numbered in the R6 text; I have numbered the list here for clarity.)

A general issue with all four of these is that they’re quite vaguely worded, especially 3 and 4, and to a lesser extent 1. (These points don’t explain why or how things are complicated by these. In the case of 1, the reader can at least refer to the specifications of map and friends to see how the specification of higher-order procedures that operate on lists has had to be made more complicated; 3 and 4 have no examples.) 2 also mentions by name an optimization I hadn’t previously heard of. I have no idea why the R6RS editors thought 4 was the case: I’ve never noticed any problems with implementing variadic procedures which would specifically be solved by forbidding their mutation.

Another issue is that problems 1 to 3 are not unique to mutation of lists. As @johnwcowan likes to say, the argument proves too much. Why not forbid mutation of other structures too, such as vectors and records? Mutation complicates very many higher-order procedures, as well as reasoning about programs that use it. Experienced Schemers already know to be careful with mutation. I doubt they’ll be convinced this is an argument to move towards forbidding it.

Compare this situation to strings, where requiring both string-set! and string-ref to be efficient puts significant constraints on an implementation’s representation of strings, and programmers can easily appreciate the drawbacks involved. (Nobody likes UTF-32’s waste of at least 25% of memory per character.)

It has been proposed that `set-car!` and `set-cdr!` should have deprecation warnings attached to them like the one we plan to apply to `string-set!`. In principle, I’m not against this. But I feel it will be harder to justify in the report text than `string-set!` deprecation. R6RS’s rationale volume offers four motivations for its somewhat half-hearted deprecation of `set-car!` and `set-cdr!`: > The presence of mutable pairs causes numerous problems: > > 1. It complicates the specification of higher-order procedures that operate on lists. > > 2. It inhibits certain compiler optimizations such as deforestation. > > 3. It complicates reasoning about programs that use lists. > > 4. It complicates the implementation of procedures that accept variable numbers of arguments. (They are not numbered in the R6 text; I have numbered the list here for clarity.) A general issue with all four of these is that they’re quite vaguely worded, especially 3 and 4, and to a lesser extent 1. (These points don’t explain *why* or *how* things are complicated by these. In the case of 1, the reader can at least refer to the specifications of `map` and friends to see how the specification of higher-order procedures that operate on lists has had to be made more complicated; 3 and 4 have no examples.) 2 also mentions by name an optimization I hadn’t previously heard of. I have no idea why the R6RS editors thought 4 was the case: I’ve never noticed any problems with implementing variadic procedures which would specifically be solved by forbidding their mutation. Another issue is that problems 1 to 3 are not unique to mutation of lists. As @johnwcowan likes to say, the argument proves too much. Why not forbid mutation of other structures too, such as vectors and records? Mutation complicates very many higher-order procedures, as well as reasoning about programs that use it. Experienced Schemers already know to be careful with mutation. I doubt they’ll be convinced this is an argument to move towards forbidding it. Compare this situation to strings, where requiring both `string-set!` and `string-ref` to be efficient puts significant constraints on an implementation’s representation of strings, and programmers can easily appreciate the drawbacks involved. (Nobody likes UTF-32’s waste of at least 25% of memory per character.)

dpk added this to the Valued Fascicle milestone 2023-11-30 13:21:15 +00:00

dpk added the

Foundations

label 2023-11-30 13:21:15 +00:00

mnw commented

2023-11-30 13:36:42 +00:00

Owner

It has been proposed that set-car! and set-cdr! should have deprecation warnings attached to them like the one we plan to apply to string-set!.

In principle, I’m not against this. But I feel it will be harder to justify in the report text than string-set! deprecation.

R6RS’s rationale volume offers four motivations for its somewhat half-hearted deprecation of set-car! and set-cdr!:

The presence of mutable pairs causes numerous problems:

It complicates the specification of higher-order procedures that operate on lists.

It inhibits certain compiler optimizations such as deforestation.

It complicates reasoning about programs that use lists.

It complicates the implementation of procedures that accept variable numbers of arguments.

The last point is actually one of the most important points. Apply and the implementation of rest arguments by the compiler suffer greatly (in terms of efficiency) because of the mutability of lists. Apply has to copy a rest argument list in general; a procedure with a rest argument list cannot, in general, just forward it to callees.

Code that uses apply often becomes accidentally quadratic because of this.

See also https://legacy.cs.indiana.edu/~dyb/pubs/LaSC-3-3-pp229-244.pdf (which actually introduced case-lambda under a different name and which also proposed a much better rest argument facility not relying on actual lists, but which regrettably didn't make it into the Scheme standard)

Point 4 alone is much stronger than any reason for deprecating string-set! simply because pairs and lists are found every where in Scheme programs and because they are deeply tied to the language through the rest argument machinery.

[...]

Another issue is that problems 1 to 3 are not unique to mutation of lists. As @johnwcowan likes to say, the argument proves too much. Why not forbid mutation of other structures too, such as vectors and records? Mutation complicates very many higher-order procedures, as well as reasoning about programs that use it. Experienced Schemers already know to be careful with mutation. I doubt they’ll be convinced this is an argument to move towards forbidding it.

The argument does not prove too much when one considers the context. Lists are often used in a functional context, yet Scheme does not truly provide such a functional context. The point is not that people ("experienced schemers") have to pay for mutation by being careful, but that they also have to pay (or the procedures they call) when they actually don't want to use mutation.

Compare this situation to strings, where requiring both string-set! and string-ref to be efficient puts significant constraints on an implementation’s representation of strings, and programmers can easily appreciate the drawbacks involved. (Nobody likes UTF-32’s waste of at least 25% of memory per character.)

Again, the situation with strings is a relative sideshow.

> It has been proposed that `set-car!` and `set-cdr!` should have deprecation warnings attached to them like the one we plan to apply to `string-set!`. > > In principle, I’m not against this. But I feel it will be harder to justify in the report text than `string-set!` deprecation. > > R6RS’s rationale volume offers four motivations for its somewhat half-hearted deprecation of `set-car!` and `set-cdr!`: > > > The presence of mutable pairs causes numerous problems: > > > > 1. It complicates the specification of higher-order procedures that operate on lists. > > > > 2. It inhibits certain compiler optimizations such as deforestation. > > > > 3. It complicates reasoning about programs that use lists. > > > > 4. It complicates the implementation of procedures that accept variable numbers of arguments. The last point is actually one of the most important points. `Apply` and the implementation of rest arguments by the compiler suffer greatly (in terms of efficiency) because of the mutability of lists. `Apply` has to copy a rest argument list in general; a procedure with a rest argument list cannot, in general, just forward it to callees. Code that uses `apply` often becomes accidentally quadratic because of this. See also https://legacy.cs.indiana.edu/~dyb/pubs/LaSC-3-3-pp229-244.pdf (which actually introduced `case-lambda` under a different name and which also proposed a much better rest argument facility not relying on actual lists, but which regrettably didn't make it into the Scheme standard) Point 4 alone is much stronger than any reason for deprecating `string-set!` simply because pairs and lists are found every where in Scheme programs and because they are deeply tied to the language through the rest argument machinery. [...] > Another issue is that problems 1 to 3 are not unique to mutation of lists. As @johnwcowan likes to say, the argument proves too much. Why not forbid mutation of other structures too, such as vectors and records? Mutation complicates very many higher-order procedures, as well as reasoning about programs that use it. Experienced Schemers already know to be careful with mutation. I doubt they’ll be convinced this is an argument to move towards forbidding it. The argument does not prove too much when one considers the context. Lists are often used in a functional context, yet Scheme does not truly provide such a functional context. The point is not that people ("experienced schemers") have to pay for mutation by being careful, but that they also have to pay (or the procedures they call) when they actually don't want to use mutation. > Compare this situation to strings, where requiring both `string-set!` and `string-ref` to be efficient puts significant constraints on an implementation’s representation of strings, and programmers can easily appreciate the drawbacks involved. (Nobody likes UTF-32’s waste of at least 25% of memory per character.) Again, the situation with strings is a relative sideshow.

johnwcowan commented

2023-12-01 05:52:54 +00:00

Owner

The last point is actually one of the most important points. Apply and the implementation of rest arguments by the compiler suffer greatly (in terms of efficiency) because of the mutability of lists. Apply has to copy a rest argument list in general; a procedure with a rest argument list cannot, in general, just forward it to callees.

Code that uses apply often becomes accidentally quadratic because of this.

I agree with this, and have referred to it in the past as the "variadic recursion bug". However, it can be resolved by making rest-argument lists immutable (i.e. it is an error to mutate them) rather than by making all pairs immutable. The CL standard says: "The value of a rest parameter is permitted, but not required, to share structure with the last argument to apply."

> The last point is actually one of the most important points. `Apply` and the implementation of rest arguments by the compiler suffer greatly (in terms of efficiency) because of the mutability of lists. `Apply` has to copy a rest argument list in general; a procedure with a rest argument list cannot, in general, just forward it to callees. > > Code that uses `apply` often becomes accidentally quadratic because of this. I agree with this, and have referred to it in the past as the "variadic recursion bug". However, it can be resolved by making rest-argument lists immutable (i.e. it is an error to mutate them) rather than by making all pairs immutable. The CL standard says: "The value of a rest parameter is permitted, but not required, to share structure with the last argument to `apply`."

mnw commented

2023-12-01 09:57:15 +00:00

Owner

I agree with this, and have referred to it in the past as the "variadic recursion bug". However, it can be resolved by making rest-argument lists immutable (i.e. it is an error to mutate them) rather than by making all pairs immutable. The CL standard says: "The value of a rest parameter is permitted, but not required, to share structure with the last argument to apply."

This would only be fully resolved if it would also be an error to mutate any list given as an argument to apply.

It would be very hard for a Scheme implementation to guard against these instances of an error.

This resolution would also not solve the other three points.

> I agree with this, and have referred to it in the past as the "variadic recursion bug". However, it can be resolved by making rest-argument lists immutable (i.e. it is an error to mutate them) rather than by making all pairs immutable. The CL standard says: "The value of a rest parameter is permitted, but not required, to share structure with the last argument to `apply`." This would only be fully resolved if it would also be an error to mutate any list given as an argument to `apply`. It would be very hard for a Scheme implementation to guard against these instances of an error. This resolution would also not solve the other three points.

johnwcowan commented

2024-01-12 13:17:33 +00:00

Owner

It would be very hard for a Scheme implementation to guard against these instances of an error.

We could require that immutablize! (bad name) is performed by apply on its final argument. As things stand, anyone who writes a procedure with variadic recursion must guard against it. But I was proposing something simpler: explicitly allowing variadic recursive functions to treat their list arguments as immutable. This means that the cost of copying is imposed in the (probably tiny) minority of cases where mutation of the rest-list is desired rather than the majority of cases where it is not.

> It would be very hard for a Scheme implementation to guard against these instances of an error. We could require that `immutablize!` (bad name) is performed by `apply` on its final argument. As things stand, anyone who writes a procedure with variadic recursion must guard against it. But I was proposing something simpler: explicitly allowing variadic recursive functions to treat their list arguments as immutable. This means that the cost of copying is imposed in the (probably tiny) minority of cases where mutation of the rest-list is desired rather than the majority of cases where it is not.

No labels

Macrological Fascicle