Contagious mutability #74

johnwcowan commented 2022年04月21日 02:45:00 +02:00

One case I didn't discuss before is that of mutability contagion. R7RS-small backward compat requires that if all arguments are mutable, the result is mutable; by the same token, if all arguments are immutable, the result is naturally immutable. But if a procedure is passed both mutable and an immutable arguments of the same type, what should be returned?

• an immutable object (immutable contagion)
• a mutable object (mutable contagion)
• decided case-by-case for each procedure and/or each type

Programmer-written code will be decided by the programmer, so we need to decide only for the standard library. SRFI 135 chose uniform immutable contagion of strings without R7RS-small backward compatibility. SRFI 135x provides for uniform immutable contagion. The relevant procedures are string-replace, string-append, string-concatenate, string-concatenate-reverse, string-join, string-map, string-map-index. The SRFI 1 counterparts would be append, concatenate, zip, map, append-map, map-in-order, filter-map, and the lset-* procedures; the SRFI 133 counterparts would be vector-append, vector-concatenate, vector-append-subvectors, vector-map.

One case I didn't discuss before is that of mutability contagion. R7RS-small backward compat requires that if all arguments are mutable, the result is mutable; by the same token, if all arguments are immutable, the result is naturally immutable. But if a procedure is passed both mutable and an immutable arguments of the same type, what should be returned? * an immutable object (immutable contagion) * a mutable object (mutable contagion) * decided case-by-case for each procedure and/or each type Programmer-written code will be decided by the programmer, so we need to decide only for the standard library. SRFI 135 chose uniform immutable contagion of strings without R7RS-small backward compatibility. [SRFI 135x](https://htmlpreview.github.io/?https://raw.githubusercontent.com/johnwcowan/r7rs-work/master/srfi-135x.html) provides for uniform immutable contagion. The relevant procedures are `string-replace`, `string-append`, `string-concatenate`, `string-concatenate-reverse`, `string-join`, `string-map`, `string-map-index`. The SRFI 1 counterparts would be `append`, `concatenate`, `zip`, `map`, `append-map`, `map-in-order`, `filter-map`, and the `lset-*` procedures; the SRFI 133 counterparts would be `vector-append`, `vector-concatenate`, `vector-append-subvectors`, `vector-map`.

mnw commented 2022年04月21日 08:31:32 +02:00

By R7RS-small compatibility, there's no choice for procedures like append. At least not if literals coincide with immutable versions of pairs/vectors/strings.

I would also advise against too much of such polymorphism. I doubt it can be implemented efficiently, and by general principles, I think it is better if the behavior of a procedure does not depend too much on the types of its inputs - at least not in a dynamically-typed language.

By R7RS-small compatibility, there's no choice for procedures like `append`. At least not if literals coincide with immutable versions of pairs/vectors/strings. I would also advise against too much of such polymorphism. I doubt it can be implemented efficiently, and by general principles, I think it is better if the behavior of a procedure does not depend too much on the types of its inputs - at least not in a dynamically-typed language.

johnwcowan commented 2022年04月21日 14:04:38 +02:00

By R7RS-small compatibility, there's no choice for procedures like append. At least not if literals coincide with immutable versions of pairs/vectors/strings.

Yes, that's a difficulty, which is why SRFI 135x says that literals are mutable strings that you can't mutate. If we are to change them to istrings, then (string-append "foo: ", foo) would return an immmutable string per SRFI 135x, which is obviously undesirable. So we have to double up on everything in the standard library that returns a string.

I would also advise against too much of such polymorphism.

For these types that ship has already sailed: we cannot consistently with R7RS-small demand monomorphic procedures mcar for mpairs and icar for ipairs if literals are ipairs: the bulk of the standard procedures dealing with pairs, vectors, and strings are unavoidably mutability polymorphic in their arguments. The issue here is result polymorphism, where the types of the results depends on the types of the arguments.

I doubt it can be implemented efficiently

Removing run-time polymorphism from dynamic languages is a bog-standard optimization for compilers nowadays. Something like 90% of all polymorphic calls are in fact monomorphic or oligomorphic.

I think it is better if the behavior of a procedure does not depend too much on the types of its inputs - at least not in a dynamically-typed language.

That's mostly true in Scheme (I/O and the numeric tower being the exceptions), but it is an outlier among dynamically typed languages, most of which are heavily polymorphic, even ones as close as CL. I often hear complaints about the relentless monomorphism of R7RS-large and Scheme in general, where the type has to be reiterated constantly: (string-append (substring x 0 3) (string-ref y 4)) specifies the type three times over, where polymorphism would allow it not to be specified at all.

These complaints are an additional reason why I think it is important to solve the problem of generic functions in a satisfying way, so that one can write something like (append+ (slice+ x 0 3) (ref+ y 4)), where trailing + is a convention for generic functions. Of course, the underlying functions are still exposed to the programmer (unlike in most languages) if that extra bit of optimization is actually necessary.

> By R7RS-small compatibility, there's no choice for procedures like `append`. At least not if literals coincide with immutable versions of pairs/vectors/strings. Yes, that's a difficulty, which is why SRFI 135x says that literals are mutable strings that you can't mutate. If we are to change them to istrings, then `(string-append "foo: ", foo)` would return an immmutable string per SRFI 135x, which is obviously undesirable. So we have to double up on everything in the standard library that returns a string. > I would also advise against too much of such polymorphism. For these types that ship has already sailed: we cannot consistently with R7RS-small demand monomorphic procedures `mcar` for mpairs and `icar` for ipairs if literals are ipairs: the bulk of the standard procedures dealing with pairs, vectors, and strings are unavoidably mutability polymorphic in their arguments. The issue here is result polymorphism, where the types of the results depends on the types of the arguments. > I doubt it can be implemented efficiently Removing run-time polymorphism from dynamic languages is a bog-standard optimization for compilers nowadays. Something like 90% of all polymorphic calls are in fact monomorphic or oligomorphic. > I think it is better if the behavior of a procedure does not depend too much on the types of its inputs - at least not in a dynamically-typed language. That's mostly true in Scheme (I/O and the numeric tower being the exceptions), but it is an outlier among dynamically typed languages, most of which are heavily polymorphic, even ones as close as CL. I often hear complaints about the relentless monomorphism of R7RS-large and Scheme in general, where the type has to be reiterated constantly: `(string-append (substring x 0 3) (string-ref y 4))` specifies the type three times over, where polymorphism would allow it not to be specified at all. These complaints are an additional reason why I think it is important to solve the problem of generic functions in a satisfying way, so that one can write something like `(append+ (slice+ x 0 3) (ref+ y 4))`, where trailing `+` is a convention for generic functions. Of course, the underlying functions are still exposed to the programmer (unlike in most languages) if that extra bit of optimization is actually necessary.