Proposal: IMMUTABLE?

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

Proposal for R^5 Report:

-------------------------------------------------------------------------------
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.

-------------------------------------------------------------------------------
 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.

-------------------------------------------------------------------------------
 FORMAL INTENT
---------------

(IMMUTABLE? x) ==> #T when there exists a mutation procedure M and a value V
such that (M x V) would denote a ``Non-Mutable Immutable'' error [as defined
in sec.3.5].


[The new value V could, of course, be embedded in the procedure M but I prefer
 to make it explicit. E.g, M = (lambda (lst) (set-car! lst 4)).]

-------------------------------------------------------------------------------
 RATIONALE
-----------

Having an IMMUTABLE? predicate would enhance portability of an important class
of space-efficient algorithms in Scheme code by allowing in-place marking algo-
rithms to peacefully coexist with mutable data which contain immutable aggre-
gate sub-components.

It 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 since implementations which already detect/report
``non-mutable immutable'' errors essentially already compute this predicate in
the process).

All I am suggesting is that when a system chooses to enforce the ``Non-Mutable
Immutables'' error then 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. NB: This does not concern
issues of sharing or read-only memory: it concerns only detected/reported
storage errors on immutable data.

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 a storage error would be detected or reported in
practice.

-------------------------------------------------------------------------------
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