[bitc-dev] Objects vs. Modules

Jonathan S. Shapiro shap at eros-os.org
Sat Feb 12 09:30:01 EST 2005


As we were looking at objects, Mark Miller (MarkM) asserted that Modules
were just objects and we should try not to have two mechanisms. We spent
a fair bit of time sorting out why that is not right in BitC.

For those of you who are not familiar with MarkM's work on E, I need to
back-fill some information to make some sense out of this.  In E, every
symbol that is defined at top level is deeply immutable, meaning that
nothing *reachable* from it (including the top-level binding) is
mutable. The E community refers to such values as "deep frozen" values.

Being "deep frozen" is a property of values, but it is not a property of
types. The rules are:

  All values of primary type are deep frozen
  It cannot be determined from a function type whether the
    corresponding value is deep frozen.
  All non-lambda values of deeply immutable type are deep frozen,
    provided they do not (recursively) contain a value of
    function type.
  A lambda value is deep frozen exactly if all of the values
    over which it is closed are deep frozen.
  A value binding is deep frozen if (a) its value
    is deep frozen and (b) the binding is immutable.

So for data values it is pretty easy to work out whether they are deep
frozen, and a given binding is either mutable or not, but for lambda
values there is a subtle issue:

  (define (f x) ;; deep frozen
    (let ((capture-me (mutable init-expr)))
      (lambda (y)
        (+ x y))))

  (define g ;; NOT deep frozen
    (let ((capture-me (mutable init-expr)))
      (lambda (x)
        (lambda (y)
          (+ x y)))))

That is, a deep-frozen method invocation of a method can allocate state
and can return a value that is closed over that state, but the method
itself can only be closed over state that is deep frozen.

Note that f and g have the same type. We cannot determine, based solely
on the type of a function, whether that function value is deep frozen.
Since interfaces introduced by DEFINTERFACE are composed of function
signatures, this applies to interfaces as well.


The reason that the "deep frozen" concept is useful is that it
guarantees a certain kind of separation of concerns: if modules are
required to be deep frozen, then two distinct importers of a module
cannot establish a communication channel merely by importing the same
module. This helps to isolate the transitive impact of computations,
which leads to more robust code and simpler verifications.

There is a second reason: if module instances are deep frozen, then two
parties invoking the same module method on the same arguments are
guaranteed to get the same result (assuming the invocation returns at
all).

The deep frozen assumption led to MarkM's assertion that objects and
modules are interchangeable. If an object type is deep frozen and its
constructor has no parameters (note that module constructors have no
parameters) then two instances of that object type cannot be told apart
because they are behaviorally indistinguishable. They can differ only by
'eq-ness' on their identity. This means that in E, objects can subsume
modules.

This isn't going to work in BitC, because BitC modules need to define
types as well as value bindings, and it is exceedingly inconvenient in
the grammar for a BitC type to define other types internally. If we were
to extend DEFINTERFACE in order to allow it to wrap a type definition,
the parser would pretty well go over a cliff.


A second issue here is: what is the result of importing a module? Is it
a name or a value? In E the answer is clearly "a value". The reason it
matters is it determines whether it is possible to write things like

  (define (import-wrapper s)
    (import s))

  (define modname (import-wrapper s))

The idea that the use-name of the imported module should be defined by
the importer is the right idea, but letting the imported thing be a
value imposes the cost of an extra pointer dereference on every cross-
module invocation. It also creates another ambiguity in the grammar,
because now if 'a' is a value,

	a.b

can be either a value or a type. The entire pattern/type/value
constructor pun relies on contextual sensitivity in the parse, and this
violates that.

Because of these issues, and because of the issue of nested type
definitions, BitC will not unify objects and modules.


shap



More information about the bitc-dev mailing list