New lexical syntaxes and immutability #80

johnwcowan commented 2022年05月08日 15:12:24 +02:00

Based on CL practice, people have found it useful to have lexical syntax for arrays, bitvectors, and transparent record types in addition to the ones in Scheme. But I realized that every time we introduce a novel lexical syntax for the various container types of the large language (I don't mean a variant like #vu8 vs #u8), we have to deal with the existence of mutable and immutable variants of the underlying data types. I had been hoping to put off the question of lexical syntax, as it will require a unified design, but for every such lexically representable type, there will need to be some way for the standard library functions of that type to return mutable or immutable values.

1. We can say that read and eval are the only way to generate immutable values, but this makes it very annoying to use them when immutability is an important property (e.g. when sharing data between threads).

2. We can have a function or set of functions that creates an immutable copy of a mutable container, but this not only involves extra data motion, it also makes it hard or impossible for immutable containers to share their contents freely (this is especially important when dealing with immutable strings).

3. We can say that R7RS-large implementations are required to copy lexically apparent containers in code, so that there is no absolute need for immutable objects, although they are still useful for sharing.

I don't like any of these.

Based on CL practice, people have found it useful to have lexical syntax for arrays, bitvectors, and transparent record types in addition to the ones in Scheme. But I realized that every time we introduce a novel lexical syntax for the various container types of the large language (I don't mean a variant like `#vu8` vs `#u8`), we have to deal with the existence of mutable and immutable variants of the underlying data types. I had been hoping to put off the question of lexical syntax, as it will require a unified design, but for every such lexically representable type, there will need to be some way for the standard library functions of that type to return mutable or immutable values. 1. We can say that `read` and `eval` are the only way to generate immutable values, but this makes it very annoying to use them when immutability is an important property (e.g. when sharing data between threads). 2. We can have a function or set of functions that creates an immutable copy of a mutable container, but this not only involves extra data motion, it also makes it hard or impossible for immutable containers to share their contents freely (this is especially important when dealing with immutable strings). 3. We can say that R7RS-large implementations are required to copy lexically apparent containers in code, so that there is no absolute need for immutable objects, although they are still useful for sharing. I don't like any of these.

mnw commented 2022年05月08日 16:39:16 +02:00

1. This solution would also force read and eval to be primitives, which would be bad. They should be implementable in Scheme if possible. (For eval, this is currently only approximately true because there are no other primitives dealing with environments.)

[...] it also makes it hard or impossible for immutable containers to share their contents freely (this is especially important when dealing with immutable strings).

What do you mean by this?

1. This solution would also force `read` and `eval` to be primitives, which would be bad. They should be implementable in Scheme if possible. (For `eval`, this is currently only approximately true because there are no other primitives dealing with environments.) > [...] it also makes it hard or impossible for immutable containers to share their contents freely (this is especially important when dealing with immutable strings). What do you mean by this?

johnwcowan commented 2022年05月08日 21:20:58 +02:00

Suppose we have SRFI 153 or some similar library, where all procedures that return strings return mutable strings, plus a way of making immutable copies of mutable strings. Mutable strings cannot share storage, but immutable strings can: a substring S' of an immutable string S can share storage with S. But if substring returns a mutable string S'', we have lost the connection to S, and so an immutable copy S''' of S'' cannot share storage with S. In code:

(define s "abcdefghi") ; s is immutable
(define s1 (substring/immutable s 3 6)) ; s1 and s can share storage
(define s2 (substring s 3 6)) ; s2 cannot share storage with s
(define s3 (immutable-copy s2)) ; s3 cannot share storage with s

Suppose we have SRFI 153 or some similar library, where all procedures that return strings return mutable strings, plus a way of making immutable copies of mutable strings. Mutable strings cannot share storage, but immutable strings can: a substring S' of an immutable string S can share storage with S. But if `substring` returns a mutable string S'', we have lost the connection to S, and so an immutable copy S''' of S'' cannot share storage with S. In code: ``` (define s "abcdefghi") ; s is immutable (define s1 (substring/immutable s 3 6)) ; s1 and s can share storage (define s2 (substring s 3 6)) ; s2 cannot share storage with s (define s3 (immutable-copy s2)) ; s3 cannot share storage with s ```

mnw commented 2022年09月08日 21:21:26 +02:00

The use case of sharing data between threads securely has a solution that does not rely on the form of immutability we have discussed here.

Namely, instead of sharing (raw) data, only objects (in the wider sense of object-oriented programming) could be exchanged. Say, instead of providing a different thread access to a vector v, just a procedure of the form

(lambda (i)
 (vector-ref v i))

is made accessible.

This does not solve all problems for which immutable data structures are a solution (e.g. effective sharing of substructures), but it handles one major use case so we can possibly concentrate on the other needs in the further discussion.

The use case of sharing data between threads securely has a solution that does not rely on the form of immutability we have discussed here. Namely, instead of sharing (raw) data, only objects (in the wider sense of object-oriented programming) could be exchanged. Say, instead of providing a different thread access to a vector `v`, just a procedure of the form ```scheme (lambda (i) (vector-ref v i)) ``` is made accessible. This does not solve all problems for which immutable data structures are a solution (e.g. effective sharing of substructures), but it handles one major use case so we can possibly concentrate on the other needs in the further discussion.

johnwcowan commented 2022年09月08日 23:29:58 +02:00

What about vector-length? That would have to be passed along too. And then all the non-primitive vector procedures would have to be rewritten. And either they would have to be monomorphic (two versions of vector-append, one for mutable and one for immutable vectors) or ad hoc polymorphic, in which case the existing problems would remain unsolved, including the relationship between these OO immutable vectors and vector literals.

I think this is a complete non-solution.

What about `vector-length`? That would have to be passed along too. And then all the non-primitive vector procedures would have to be rewritten. And either they would have to be monomorphic (two versions of `vector-append`, one for mutable and one for immutable vectors) or ad hoc polymorphic, in which case the existing problems would remain unsolved, including the relationship between these OO immutable vectors and vector literals. I think this is a complete non-solution.

mnw commented 2022年09月09日 08:07:33 +02:00

That would indeed be a complete non-solution, but this is not what I have in mind. Instead of providing all vector-related procedures just send what would be called in other languages a proxy object. The proxy object would be an implementation of the abstract interface necessary for communication and that would usually not include all vector-related procedures, say. As Scheme has no particular object data type, such a proxy object can be anything. In my simplified example above, it was just an accessor procedure. It could also be a record value or a procedure accepting and dispatching messages.

That would indeed be a complete non-solution, but this is not what I have in mind. Instead of providing all vector-related procedures just send what would be called in other languages a proxy object. The proxy object would be an implementation of the abstract interface necessary for communication and that would usually not include all vector-related procedures, say. As Scheme has no particular object data type, such a proxy object can be anything. In my simplified example above, it was just an accessor procedure. It could also be a record value or a procedure accepting and dispatching messages.