Random numbers

[Bjorn Lisper]

Richard Lobb:
>I appreciate the beauty of referential transparency, but as I explained in an
>earlier posting, it can be a real nuisance in practical contexts. Is it not
>possible to have controlled loss of referential transparency? Can you not
>provide facilities in functional languages that let me use non-ref transp
>functions if I really want to, on the understanding that by doing so I will
>significantly reduce the range of optimisations that the compiler can
>perform? [I assume it's possible for the compiler to propagate the non
>ref transp property, and disable optimisations that are not legitimate
>in the abence of referential transparency.]

I have done some theoretical work in that direction (to be reported at
CAAP'95 in april). In essence, my results are that under certain conditions,
fold/unfold-transformations are still OK provided they do mimic the runtime
behaviour exactly (sharing must, for instance, not be tampered with).
"Unfolding" here also includes transformations like evaluation of constant
"deterministic" subexpressions, and, in general, any "non-committing"
symbolic execution.

Elimination of common subexpressions is, however, not OK in general since it
may change the sharing properties (in the theoretical framework I set up,
this shows in non-left-linear rewrite rules which can destroy commutation
properties for rewrite relations).

I should say my work is quite abstract and there is some ground left to
cover before it can be applied to "real" programming languages. But I think
this can be done with some effort.

Bjorn Lisper

lisper@it.kth.se