[bitc-dev] Internal and External function types

Jonathan S. Shapiro shap at eros-os.org
Tue Jul 25 02:11:57 EDT 2006

This note assumes that you have read the note entitled

   Mutability, Copies, and Surprises

You may want to browse that thread first.

Because of the "strip outermost mutability" rule, there is an
interesting conundrum: what type should be assigned to the following

  (define (mut-c c)
    (set! c #\a)

Obviously, "c" must be mutable, and since this is correctly recognized
by the symbol resolver, the type of MUT-C must surely be:

  [a] (fn ((mutable char)) (mutable char))

However, note that values are copied at procedure return, so it would be
perfectly reasonable to assign the type:

  [b] (fn ((mutable char)) char)

But note that the argument "c" is copied at procedure call, so from the
caller perspective it is also reasonable to assign the type:

  [c] (fn (char) char)

on the theory that it is none of the caller's business what MUT-C does
with its private copy of the argument!

Within the BitC group, we have taken to referring to [c] as the
"external type" and [a] as the "internal type". The rule for forming the
external type is simply to discard any MUTABLE that appears as the
outermost wrapper of an argument or return type.

This has raised a curious question: when writing procedure types
explicitly, which type should be written?

At the moment, the answer is "the inner type", but I actually do not
like this -- especially for PROCLAIM. What makes the most sense is for
PROCLAIM to declare the type from the caller perspective (it is, after
all, stating a type for use by the caller).

But it would also be nice if the PROCLAIM'd type and the DEFINE'd type
agree, which would lead to the following rather strange situation:

  (define (mut-c:(fn (char) char) c:(mutable char))
    (set! c #\a)
  [Note that type declared on argument does not agree with type
   declared on function name.]

Or even worse, consider:

  (define (mut-c:(fn (char) char) c)
    (set! c #\a)

where mutability of the argument type for "c" is inferred by the symbol
resolver, and we now have an ambiguity: did the programmer really mean
that "c" should be immutable (in which case an error is in order) or not
(in which case this is just fine).

At the moment, note that ALL of the cases where the internal and
external types disagree are cases where the symbol resolver can
correctly infer the mutability, because they all involve assignments to
simple identifiers (because all parameters happen to fit that pattern).

Here are my intuitions about all of this:

  1. The PROCLAIMED type should always be an external (caller
     perspective) type.

  2. If argument types are given at DEFINE, they should be the
     *internal* argument types, because we really want to get errors if
     a "declared immutable" argument is modified.

  3. To avoid confusion, the defined identifier in the convenience
     syntax for procedures should NOT accept a type qualifier. This
     would make both of the examples above illegal. One can still write:

       (define (mut-c c:(mutable char)) (set! c #\a) c)


       (define mut-c:(fn (char) char)
         (lambda (c) (set! c #\a) c))

     visually, I do not find that the second form is confusing, because
     the left side and the right side of the binding are clearly

  4. When running in interactive mode, the compiler should report
     the *external* type of the procedure.

I would be interested in other opinions, and/or arguments about why all
of this should be left alone for the moment and maybe we should come
back to it at a later time. I'm not so interested in changing the
compiler right away as understanding what is the more usable thing.


More information about the bitc-dev mailing list