Re: mutable/immutable

[Michael R. Blair <ziggy@martigny.ai.mit.edu>]

Matthias,

I have sent a more clear formal proposal to the Revised Authors list. I wish to
thank you for your correspondence on the topic and I feel the proposal has
benefitted from your expression of concerns.

Nonetheless, I feel obliged to respond directly to your concerns so you can
elaborate on points you have made which are not addressed in my proposal. I
hope you find this helpful. Again, thank you for your feedback.


>    Date: Thu, 30 Sep 93 17:07:05 -0400
>    From: Michael R. Blair <ziggy@martigny.ai.mit.edu>
> 
>    Is this an oversight or is there some subtle rationale behind the
>    following:
> 
>     literals are constants and therefore immutable.
>     other constructed composite data are mutable.
> 
>     There is/are no predicate(s) to test mutability.
> 
> I think (tell me if I'm wrong) that constants are immutable to allow
> sharing of constants.  Predicates to decide mutability would require
> to maintain run-time information about mutability -- which could be
> expensive in some implementations.

R^4 Report states [p.7, sec.3.5]:

  In many systems it is desirable for constant (i.e, the val-
  ues of literal expressions) to reside in read-only-memory.
  To express this, it is convenient to imagine that every ob-
  ject that denotes locations is associated with a flag telling
  whether that object is mutable or immutable.  The con-
  stants and the strings returned by SYMBOL->STRING are
  then the immutable objects, while all objects created by
  the other procedures listed in this report are mutable. It
  is an error to attempt to store a new value into a location
  that is denoted by an immutable object.

This says nothing about sharing, although I agree that issues of sharing are
important practical motivations to implement the above. My concern is with the
last line of this passage: IT IS AN ERROR TO ATTEMPT TO STORE A NEW VALUE INTO
A LOCATION THAT IS DENOTED BY AN IMMUTABLE OBJECT. What troubles me is that no
(standard) mechanism is provided to avoid committing this error in
implementations that enforce (i.e., signal) this error. At least a sentence
encouraging implementations that signal this to kindly provide (IMMUTABLE? obj)
would be a good idea. Just as implementations are encouraged, but not required,
to signal various errors, I think they should be further encouraged to provide
run-time mechanisms to detect when an error *is* detected or reported by an
implementation so that errors can be avoided dynamically.

Note that storing objects in read-only memory, so far as I have ever seen or
heard, usually involves reserving a contiguous region of memory for this
purpose. Thus, the overhead of run-time tagging of immutable objects is made
manifest in their address. Generally, any system I have encountered that
distinguishes mutable from immutable objects segregates to reduce GC overhead
anyway, so the address-encoded mut/immut tag is a happy consequence
(serendipity?). Testing this range is thus a very inexpensive address range
check. Note that no Scheme mutators (like SET-CAR!) actually must test this
mutability, just as CAR is not compelled to enforce input domain constraints
(it is just an error to violate them). I just want a handle on a test that *I*
can manually call when I want to be safe (and paranoid).

Of course, you are correct that in *some* implementations this could be
expensive, just as in some implementations GC is expensive. I don't consider
this a compelling argument against the proposal, though. I consider it more a
compelling example of inertia ;-). I don't see any compelling reason why
IMMUTABLE? should increase the expense of reasonable implementations in which
the ``Non-Mutable Immutable'' error is already detected or reported. Perhaps
you can help me appreciate the subtleties of this expense which you perceive
which I am currently at a loss to appreciate?

Aguing for IMMUTABLE?, having an IMMUTABLE? predicate would enhance portability
in practice, would permit more efficient code in practice (e.g., in-place
marking strategies), and would have very little impact on existing
implementations in practice (since it merely *encourages* mutability-sensitive
implementations to expose their sensitivity to the coder in a way which, in
practice, should bear marginal impact on the implementation).

Sorry, I don't find your suggested run-time info overhead complaint compelling
in practice. Can you be more specific about the expense you allude to? Can any
other implementors comment on the severity of this concern for their
implementations?  Is there something I'm not thinking of?

> Also, some systems use Scheme itself to compile the Scheme code.  Those
> systems would need to be augmented by procedures like
> 
> 	(immutable-cons <obj1> <obj2>)
> 	(list->immutable-vector <list>)
> 
> etc.  (The ``constants'' of the user program are not ``constant'' in
> the compiler.)
> 
> -Matthias

I'm sure I probably don't understand what you are worried about here. I fear
you have taken me to be asking for much more that I thought myself to be asking
for. Let me try to explain why I think your concern is not an issue with what I
have requested. I imagine that any Scheme system that behaves as you describe
*already* essentially does exactly what you are worried about having to augment
your system with. That is, if some implementation like you describe actually
performs the sharing you alluded to above, then in order to be a faithful
implementation of the R^4 Report it must already be pulling some tricks to
distinguish mutable from immutable reads so that EQUAL? literals can be
coallesced into EQ? storage: how else does it ``decide'' when to share and when
not to? Using a hashing CONS within READ of literals? Common sub-expression
eliminating at compile time? In that case, READ's the hashing CONS table is the
immutable region. For compile-time CSE, the CSE'd literals are compile-time
detected so can be allocated in read-only memory. Thus, (IMMUTABLE? x) is then
just a membership test on that READ hashing table, or on the read-only region
of memory, no?

Or are you concerned that what I am really asking for is (SHARED? object). Well
relax, it is not. I appreciate the subtle pitfalls of a truly global SHARED?
predicate so I don't mind computing my own approximate SHARED? predicate given
IMMUTABLE? as a means of supporting *SAFE* in-place marking. At any rate, if I
have misunderstood you, please help me to understand. I have played with ideas
and techniques in partial evaluation and I've tried to stay abreast of the MIX
work at DIKU, so I am not insensitive to the point I think you are raising.  I
have even dabbled in Denotational Semantics for many consecutive waking hours
over several months without vacation. It isn't that I disagree with your
concern it's just that I think it is not in response to the point I thought I
raised.  Have I overlooked something? I hope I did not misrepresent myself.


All I am suggesting is that when a system chooses to enforce the ``Non-Mutable
Immutables'' error that implementation should also provide IMMUTABLE?. Nothing
in the report compells an implementation to enforce that error, let along even
detect it. In fact, nothing in the report compells an implementation to even
distinguish mutable from immutable at all. What are you worried about? I have
said nothing about sharing or read-only memory, only about detected/reported
errors. I fear I may have inadvertently upset you about a sensitive matter I
do not perceive. In what way would IMMUTABLE? damage your implementation?

In summary: *If* an implementation *is* going to distinguish mutable from
immutable cells *for purposes of enforcing non-mutability of immutables*, then
that implementations *should* be encouraged to provide a *standard* mechanism
to avoid the error. I proposed that that standard mechanism be named IMMUTABLE?
and that it be a Boolean predicate on Scheme objects that return true only on
immutable objects for which the storage error would be detected or reported.


I just want a portable handle so I don't have to hate implementations that
crash but provide no predicate (like TI Exploder PseudoScheme [blame TICL, not
Jar's fine embedding]) and so I don't have to get annoyed by implementors who
cannot decide on whether to provide MUTABLE?, IMMUTABLE?, or whether to be
excessive and provide tons of different predicates like IMMUTABLE-PAIR?,
MUTABLE-VECTOR?, etc. I wish the report could acknowledge for posterity that
IMMUTABLE? suffices and should be considered a standard extension for implemen-
tations which enforce the ``Non-Mutable Immutables'' error.

I have not suggested that any mechanism other than quotation of literals be
provided to create immutable objects. Frankly, I don't see why you brought that
up. I don't see how my original question had anything to do with making an
implementation ``need'' to be augmented with immutable-cons etc. in any way
that the programmer need have access to them.  Perhaps my original post was
unduly concise and therefore permitted the unintended interpretation that I was
asking that all implementations provide IMMUTABLE?  and that they must return
true on literal/constant/immutable data. Let me be very clear then: I do not
intend either branches of that conjunction. I don't think it should be required
(``essential'') since it is silly to make implementations provide a predicate
that may always return #f (e.g., no mut/immut distinctions made) and I don't
think it really has anything to do with literals/constants/sharing/immutable
data per se: It has to do only with avoiding potential run-time errors via
providing a run-time guard.


Please retract your suggestion that this would require IMMUTABLE-CONS and so
on or explain to me how my proposal entails these augmentations. The proposal:

-------------------------------------------------------------------------------
 PROPOSED NEW SENTENCE TO BE APPENDED TO THE END OF THE LAST PARAGRAPH OF 3.5

  Systems which detect or report this error are encouraged to provide the
  predicate IMMUTABLE? which returns #t on objects for which the error would
  be detected or reported if a store of a new value into their denoted location
  were attempted.
-------------------------------------------------------------------------------


Please, if you forsee problems in this, help me to understand the issue. If, on
the other hand, your concerns are addressed by the refined proposal put forth
here than please acknowledge this to the other Revised Authors subcribers so
that approval of this proposal will not be unduly obstructed.


I don't think this is as difficult or subtle a problem as shallow/deep binding
or macros or records/modules or the plethora of other very important and very
difficult unsettled open problems of our generation, but I sure would like to
have it (IMMUTABLE?) around just to appease that dirty little portability itch
that keeps me awake at night when I actually try to do something practical.

I know it's not Hilbert's Nth, but there's still some practical value in it.


Thanks for your efforts in addressing this issue. I hope we can come to a
mutually agreeable understanding on this issue. Let me know what of your
concerns I can more clearly address to ensure an efficient resolution of the
proposal. Or let me know why this proposal is untenable if I am making a
grievous oversight.

-------------------------------------------------------------------------------
ziggy@lcs.mit.edu    Michael R. Blair   MIT Laboratory for Computer Science
(617) 253-8576 [O]         -.           545 Technology Square --- Room 434
(617) 577-1167 [H]          /\.         Cambridge, MA   02139