Immutable code and quoted data

[Andy Freeman <ANDY@SU-SUSHI.ARPA>]

Summary:
 1. Immutable structures raise lots of issues in the reader and other places
    that should be settled before they are added to the language.
 2. Interpreters must copy the source, unless ....
 3. Side-effects on quote'd structures really aren't different from
    other things the language must have.
 4. Immutable quoted structures might be acceptable (and may even be a good
    idea) if everything is done right; it isn't yet.

Andy Freeman (me) wrote:

    Immutable cons structures bother me.
    Every other immutable structure in Scheme has a distinct reader
    syntax.

Will Clinger replied:

    I think the idea is that QUOTE would mark structures as immutable.

Jonathan's proposal was that QUOTE mark structures in code as
immutable, but QUOTE isn't external syntax for immutable.  (I should
have said distinct EXTERNAL syntax instead of reader syntax.)  The
value of (read)ing (quote (a b)) is not the same as (read)ing (a b);
(write '(a b)) has the same output that (write (list 'a 'b)) does.

JAR's reply to my objection is that write and read lose address
information so why shouldn't they be allowed to lose the immutability
bit?  Accepting this point raises the question, should read return
mutable structures?  (I believe the answer is no.)  If not, then every
immutable structure has the obvious external syntax and no mutable
structure has a reader syntax.  (Requiring write's arguments to be
immutable structures is going too far.)

Everything that can be quoted will need an immutable counterpart and
it seems arbitrary to restrict immutable structures to the domain of
the interpreter.  In other words, not only is immutable? necessary,
but so is immutable-cons, immutable-vector, and immutable-string.  (To
put it another way, many structures will require mutable ones as
well.)  We also need to decide whether the arguments to the immutable
constructors can be mutable.  (I don't think they can be.)

Will Clinger continues:

    I think immutable pairs are motivated by the fact that in many systems
    side effects to quoted list structure alter the source code, particularly
    when the code is interpreted rather than compiled.  This can make it hard
    to debug, so the implementors want to discourage such side effects by
    calling them "errors".

Not that I've done this right either, but since compilation must copy
the source code, interpreters should behave as if they are using a
copy of the source.  This has other advantages.  For example, is it
legal for a program to modify its source to affect its behavior or for
the source to be circular?  (I think not.)

If all of the above is accepted (read returns immutable structures and
immutable structures can't contain mutable ones) and code and quoted
data must be immutable and acyclic, then the copy seems unnecessary.

Note that this last position is extreme; both code and quoted data are
immutable.  JAR's proposal was that quoted data should be immutable.
I'd like immutable code.  The issues are separate.  Currently Scheme
has mutable code and quoted data.  I believe that Scheme should change
to at least "immutable" code, which can be accomplished by copying the
source.  (No, it actually doesn't require new data types or
operations.)  JAR proposes immutable quoted data, which can be
accomplished in the ways he described with the additions I suggest.

True constant data structures, such as JAR proposes, are rare.  Apart
from functional and logic languages, like FP and Prolog (and they're a
special case in Prolog), ML is the only language I know of with
constant data.  (c++ may have constant structures, but c definitely
doesn't.)

I don't see side effects on quoted structure as being something odd;
QUOTE is a convenient short-hand, but it isn't a syntax for constants.

-andy

@begin(tangent)
Obviously the following procedure can return 97.

    (let ((x (list 'a)))		; procedure-a
      (lambda (flag)
	(if flag (set-car! x flag)
	    (car x))))

On the other hand, many of you object to the same behavior by the
following procedure

    (let ((x '(a)))			; procedure-b
      (lambda (flag)
	(if flag (set-car! x flag)
	    (car x))))

or an equivalent one.

    (lambda (flag)			; procedure-c
      (let ((x '(a)))
	(if flag (set-car! x flag)
	    (car x))))

I believe procedure-b and procedure-c are the same because I believe
that quote'd structures are built at load time (or possibly read or
compile time).  In other words, I believe that the following must be
#t.

    (let ((x (lambda ()
	       (lambda () '(a)))))
      (eq? ((x)) ((x))))
@end(tangent)
-------