[bitc-dev] Die, die, DI-FN*
Jonathan S. Shapiro
shap at eros-os.org
Thu Aug 11 22:44:42 EDT 2005
Okay, let me try to explain the DI-FN confusion (which was mine). If you
don't care about the details, the summary is:
1. We don't need DI-FN
2. The rule is simple: any instantiation of a deeply immutable type
class must be performed using deeply immutable specializations.
3. We already have enough information to know which functions are deeply
immutable, so no further mechanism is needed.
The long version:
A deeply immutable function is not permitted to close over any
modifiable state. It can neither access nor mutate any mutable value via
its closure. However, it CAN both access and mutate its arguments --
even if they are mutable. It can also *form* a closure at run time
capturing those mutable arguments, and return that closure as a return
value. This means that procedures that do constructor-style
initialization are able to initialize and return mutable objects, but
they can only do so deterministically and without remembering what they
have previously done.
There are two ways that you can know that a function is deeply
1. It is proclaimed or defined within a deeply immutable interface.
2. It is defined above you in the same source unit of compilation (and
is therefore directly checkable).
In all other cases, the function is conservatively assumed NOT to be
Rule 1: If a type class is deeply immutable, then all of its
instantiations are required to be performed using deeply immutable
Rule 2: A type class defined within a deeply immutable interface is
So the question is: in the absence of DI-FN, do we know enough to
satisfy rule 1? The answer is yes, so there is no need to introduce DI-
FN for this reason.
There is *one* case that might appear to motivate DI-FN, but it doesn't.
I want to lay it out so that it is captured for archival why this is NOT
a motivating case.
Under the conservative rule, the compiler will pessimistically treat all
procedures exported by a stateful interface as stateful, even though
some may not be in practice. If such an interface defines a type, it
would be pleasant if it could also define the appropriate
specializations for type classes (as appropriate). In particular, we
would very much like to define specializations for equality testing.
But now we have a conflict of objectives, because we *also* want to be
able to use the equality test inside a deeply non-mutating function.
This implies that the Eql type class must be deeply immutable, and that
our instantiation for the new type must therefore be deeply immutable.
So: it might seem desirable for an otherwise stateful interface to be
able to voluntarily export deeply immutable functions.
Regrettably, this doesn't work, because a deeply immutable interface
cannot import a stateful interface, and therefore would not be able to
import either the type declaration or the instantiation of Eql.
A better solution -- and one which does not demand DI-FN -- is to notice
that it is perfectly okay to define a mutable type within a deeply
immutable interface. What is *not* okay is to instantiate a value of
this type that is proclaimed in a deeply immutable interface.
So: in the obscure case where you wanted to export a deeply immutable
type class instantiation from a stateful interface, the solution is to
split the interface into stateful and deeply immutable parts, move the
type declaration into the deeply immutable interface, and place its
My opinion is that this will prove mildly awkward, but only in rare
cases, and the alternative is to significantly complicate a language
that is already making my head hurt.
I'm less and less convinced that deeply immutable was worth it, but now
that we are here, let's give it a try.
More information about the bitc-dev