4.1 Environment Handling

The polyinstantiator needs an environment in which we have the entries from all interfaces and modules so that newly instantiated definitions can be R&Ted (see Section 4.3). We refer to this environment as Mega-ENV, and it contains symbol, type and typeclass-instance information from all UOCs. Moreover, since the Mega-ENV contains inter-UOC information, it must always be indexed by the fully qualified names (FQNs) of all variables. In order to polyinstantiate a definition completely, we must construct such an environment and pass it to the specializer.

How should the Mega-ENV be built? Of course, for the first time, we must build it by iterating over all the environments of all interfaces and source modules and build a new environment based on their FQNs. However, we don't want to do it every time we enter the instantiator. Since here is that the interface-list and the source-module list are append-only -- they are append-only in the case of an interactive interpreter; in the case of static compiler, these lists are frozen -- we can note the previously last processed indices into these lists, and only processes additions each time. In the case of a compiler, interfaces and source module environments are immutable once the entire module is processed. However, in the case of an interactive interpreter, there is exactly one unit of compilation that is ever expanding, and the instantiator must cope with this. So, we mark this UOC as ``dynamic,'' so that the instantiator will re-process it every-time.

Once the Mega-UOC is built, we set it up as the parent of the unified-UOC's environment into which new definitions are emitted. Thus, when we try to R&T a newly instantiated definition, not only are all the old definitions and instances available but also all the polyinstantiated definitions. Appropriate name mangling is used to ensure that no polyinstantiated definition will ever collide with an original definitions. Moreover, all typeclass instances are required to be globally distinguishable with respect to the whole program. Thus, we will have no collisions here either.

Once we have updated the Mega-ENV, we call the Specializer(Section 4.3 on each (input) entry-point.

4.2 Name mangling

Every identifier id with FQN fqn and type typ is replaced with the mangled name:

_ + length(fqn) + fqn + # + mangled_string(type)

The `+' operator is meta-syntax for string pasting, and is not a part of the new identifier's name. length is the obvious string length function and mangled_string function returns a unique string representation of every type.

For example, the type list defined in the interface bitc.prelude, if instantiated to the type (list int32) will have the name _17bitc.prelude.list#UR1_4list_5int32.

4.3 The Specializer

The following is the algorithm for the Specializer: It takes as input the AST of a (possibly polymorphic) definition, and a concrete type to which this definitions must be instantiated. In the case of polyinstantiating a local definition, it takes in a let-binding. It returns the newly instantiated identifier (not the entire defining form).

The Specializer maintains a worklist of definitions currently being processed, to ensure that recursive definitions do not cause the instantiator to go into an infinite loop. All R&Ts in the following algorithm should be understood to be performed with respect to the environment of the Unified-UOC.

1. See if the desired identifier has been instantiated for the desired type by searching the Unified-UOC's environment. If found, just return the identifier for the corresponding definition.

2. Examine the worklist whether we are in the process of instantiating the current definition. If so, emit a declaration if we are instantiating a global, and return the identifier being declared. If we are in the process of instantiating a local definition, we don't need a declaration; so just make-up the right name for the local instantiation and return it.

3. Copy the incoming AST -- always copy the definition (rather than the declaration) if one exists.

4. If we are instantiating a type definition to a concrete type typ, instantiate the structure to the maximally mutable type that is copy-compatible with typ (See Appendix D.)

5. Mangle the name of the identifier being defined depending on the desired type, and also change any recursive usages of the same name within the current definition. For example:

   (define _8myMod.id#Fn_4bool_4bool (lambda (x) x))

6. Clamp the type of this AST to the desired type by introducing a qualifier. For example, to instantiate id to (fn (bool) bool), we write:

   (define _8myMod.id#fn_4bool_4bool:(fn (bool) bool) (lambda (x) x))

   Here, we must overwrite any qualifications already done by the user because we will have strictly more information, and we cannot write the qualification anywhere else (for example, on the RHS) due to copy-compatibility[6].

   If we are specializing a type definition (defstruct / defunion), then replace the usage of type-arguments to that type with concrete types, and erase the argument list of that type.

7. R&T the new definition (or let-binding) so that the types in the body of the definition get clamped aiding further instantiation. After successful R&T, throw away any changes to the environment.¹

   In the case of a let-binding, we must R&T the let-binding with respect to the local environment(which the resolver, type-inference engine will have as part of the AST). However, if we receive a let-binding as input, we must be called from recInstantiate (Section 4.4, which means that the containing definition has already been R&Ted in the Unified-UOC environment. So, the local environment will have the Unified-UOC's environment and thus the Mega-ENV as parents.

8. Add the mangled name plus a unique identifier of the AST being instantiated onto the worklist. The unique ID is required because names of local instantiations might collide.

9. Recursively instantiate the body of the newly instantiated AST (Section 4.4).

10. After the current AST is completely instantiated:

    • In the case of a global instantiation, append it to the module in the Unified-UOC. R&T it once more but keep changes to the environments so that further instantiations can use it.

    • In the case of a local instantiation, add the instantiated let-binding to the inner-wrapper of the current let expression (Section 4.4).

11. Remove the current definition from the worklist, and return the identifier corresponding to the definition just instantiated.

4.4 The recursive Instantiator

The recursive instantiation propagator (recInst, for short), will walk through newly instantiated definitions and look for usages of other definitions and call the specializer on these definitions. There are a couple of special cases that recInst must handle:

1. Case Lambda / switch²: These expressions bind new variables (argument/local name) but not polymorphically. Therefore, just replace the names of all bound identifiers with their mangled-names. Also, replace all use-cases of these identifiers. Later, recInstantiate the body (rest of the AST).

2. Case Type-qualified expression: Replace the type-qualification with an explicitly concrete type from the type-obtained. Otherwise, type-variable scoping will play havoc, especially while dealing with let-polyinstantiation. R∧T the (AST for) type-qualification, and recInstantiate it.

3. Case Int/Float Literal: Since we no longer have type classes after polyinstantiation, every int / float literal must be qualified with the precise type.

4. Case Identifier usage: We should now fetch the definition and (poly)instantiate it. However, this has some sub-cases:

   • If the identifier is a value constructor, instantiate its container type fully.

   • If the identifier is a type-class method, fetch the implementation from the appropriate instance. Note that there must exist an instance that will satisfy this usage as the program was declared type-correct. An instance may provide, as implementation for a method of this typeclass, a method from another class. Therefore, this process must be repeated until we find a ``real'' function to instantiate.

   • Otherwise, this is a ``normal'' identifier usage, just fetch the definition of this identifier. In the case of a local definition, the definition is the corresponding let-binding.

   After fetching the right definition to instantiate, call specializer with this definition, and the type required by the use of the definition. In case the type of the use case of the definition is non-concrete, fix it to some concrete type (say unit³) before calling the specializer. Replace the identifier usage with the identifier returned by the specializer.

5. Case let / letrec:

   • Wrap the body of the current definition with another (respective) let / letrec container with empty bindings⁴ (See Appendix C). For example:

     (let ((id (lambda (x) x))
       (id ())
       (id #t))

     is changed to

     (let ((id (lambda (x) x))
       (let ()
         (id ())
          (id #t)))

   • Now recInst the body of the let-expression (not the bindings). This will (probably) trigger instantiations of the local bindings, while the specializer will add to the inner let expression.

   • After the body is completely instantiated, carry forward (by recInstantiating) all non-polymorphic bindings in the outer definition onto the inner definition. This must be done in order to preserve their side-effects. Note that polymorphic expressions cannot have side-effects due to the value-restriction[1].

   • Finally, discard the outer wrapper, and declare the inner let expression as ``the'' real AST. In case no bindings are carried forward (all the bindings were polymorphic, and unused in the body), just drop the let and declare the body as the instantiated expression.