Closure Conversion of Object Expressions

General Strategy Overview

1. The top-level main visitor is ObjectExpressionVisitor.

First, it issues a visitor FreeNameCollector at the top level (forComponent) that
collects free references occured within object expressions.

A reference is defined to be free within an object expression, if the name of the
reference is not declared at the top-level, within the object expression, or within the
super traits of the object expression.

These references may include the following:

  • VarRef - reference to a variable, mutable or immutable
  • FnRefs - reference to a function or method, which need to be disambiguated later
  • OpRef - reference to an operator
  • DimRef - reference to a dimension
  • UnitRef - reference to a unit
  • IntRef - reference to a static parameter of kind int
  • BoolRef - reference to a static parameter of kind bool
  • VarType - reference to a static parameter used in a type context
    (If a static parameter is used in an expression context, it is parsed as a VarRef.)

2. Convert the object expression (ObjectExpr) to a top-level object declaration
(ObjectDecl), and convert the original object expression to a constrcutor call to the
lifted object declaration.

3. Lifting object expression to the top level involves passing free references to the
lifted object declaration as value parameteres.

  • If the reference is immutable and not a static type parameter, pass it in as a value parameter.
  • If the reference is mutable (which must be parsed as a VarRef), box the variable
    (by wrapping it as an object) and pass it in the box reference. Note that an object
    expression can only capture free references to mutable variables that are declared
    as a field in the enclosing object declaration (ObjectDecl), or as a local
    variable (LocalVarDecl).
  • All static type parameters declared by the trait / object declaration
    enclosing the object expression are passed to the lifted object as static
    parameters. Static parameters can not possibly occur in other context.

4. Handle reference to free labels: if an exit expression occurs in an object expression
where the label is free, wrap the exit expression with a function, and pass the function as
a value parameter to the lifted object. (This is Not Yet Implemented.)

5. Handle nested object expressions: lift one level of object expression at a time;
recursively perform the closure conversion on the lifted object declarations. (This is Not Yet Implemented.)

Discussion

1. At the moment, the closure conversion pass creates one box per mutable variable captured
by an object expression. A better way (in terms of the object life span and space usage) to
handle mutable variables are described below:

Imagine the following scenario: in an object declaration, 3 object expressions occur:

object expression A refers to a, b, c
object expression B refers to b, c, d
object expression C refers to c, f

This should generate boxes as follows:

After parsing object expression A: {a, b, c}
After parsing object expression B: {a}, {b, c}, {d}
After parsing object expression C: {a}, {b}, {c}, {d}, {f}

One should come back and implement this approach later ... but for now, this is not the priority.

2. For now, an object expression (oe) nested inside an object declaration (o) by default
gets all of o's static parameters. Maybe a better (not sure) way to do is to figure out
which static parameters are actually referred by the oe and use those only.
This is slightly trickier than one may think at first glance:

(Fill in the details later)

3. A mutable variable with an arrow type is parsed as VarRef. Therefore, when we box for mutable variables,
we only need to worry about VarRef.

Interactions with Other Compiler Passes

1. Type Checker: The closure conversion pass expects and depends on an output generated
by the type checker, TypeCheckerOutput. The TypeCheckerOutput provides
the type information such as type environments associated with a subset of AST nodes.
In particular, it means to support two public methods:

  • getTypeEnv(Node n): TypeEnv
    This method takes in an AST node n and returns the TypeEnv associated with n
    (i.e. The TypeEnv contains only types that are visible before entering node n.
    That is, it does not contain any types defined within n or within its subtree).
    The node n is identified by the values of its fields and its span.

    Furthermore, this method only recognizes AST nodes with the following types:
    TraitDecl, ObjectDecl, FnExpr, FnDef, IfClause, For, LetFn, LocalVarDecl,
    Label, Catch, Typecase, GeneratedExpr, While, and ObjectExpr. The reason is
    that, these are the only nodes that introduce new lexical scopes, thus, the type
    environments can change only after entering these nodes. The method returns null if
    it receives an argument that are not recognized.

    This is done in r2715.
  • populateTypes(Node old, Node new): Pair<Node, TypeCheckerOutput>
    This method provides a mean for a later compiler pass to update the type information
    stored in TypeCheckerOutput. If the compiler pass updates a node from n to n'
    which changes the type environment, it should invoke the method populateTypes(n, n'),
    which returns a pair of the new node n' with type information filled in, and the
    updated TypeCheckerOutput. The compiler pass is then responsible for propagating
    the updated TypeCheckerOutput to the later passes.
    (This is Not Yet Implemented.)

    This is required for handling nested object expressions.

2. Getter / Setter Desugarer:

  • If some mutable variables are being boxed by the closure conversion pass, and those
    mutable variables are declared as fields of some object declaration, the getter / setter
    desugarer needs to be aware of their existence, and refer to the boxed version in the
    generated getter / setter methods. Thus, the getter / setter desugarer, DesugaringVisitor,
    gets a map from ObjectExpressionVisitor after the closure conversion is done,
    which provides the information on boxed references. The information is contained
    in the map, mapping from a pair of the name of the object declaration and the name of
    the boxed field (Pair<Id,Id>) to the field reference of its corresponding box (FieldRef)
    created during the closure conversion.

    This is done in r2734.

Related Bugs Filed

1. Ticket #246: The type checker assigns a wrong type to a field declared as an abstract field in a super trait.

  • Problem: In trunk/ProjectFortress/tests/objectCC_immutable.fss, definition of trait XTrait declares an abstract
    field v which is later referenced by XObj that extends XTrait. When XObj declares
    the actual value parameter v and refers to it, the type checker assigns v an arrow type
    that is the corresponding type for its getter.
  • Work around: Sukyoung fixed the getter / setter desugarer to output abstract getter / setter
    declarations in the trait, which seems to work with the type checker.

2. Ticket #266: The interpreter does not handle a declaration of _ with a type annotation:

  • Problem: In trunk/ProjectFortress/tests/objectCC_staticParams.fss, line 42, the original code was:
    _ = O[\X, b, 3\](v, s)
    which is desugared and unparsed as:
    _ : O[\X, b, 3\] = O[\X, b, 3\](v, s)
    and causes an error.
  • Work around: change the code to o = O[\X, b, 3\](v, s)
  • FIXME: change line 42 back to _ = O[\X, b, 3\](v, s) when the bug is fixed.

3. Ticket #267: The ObjectExpressionVisitor does not resolve references shadowed within object expressions correctly.

4. In trunk/ProjectFortress/tests/objectCC_immutable.fss, there is a part commented out, where a local function is referred
within an object expression. The interpreter does not accept the desugared and then unparsed
version, because in the unparsed version, the local function is passed as a value to the lifted
object declaration, and it is not annotated with a type (the type is represented as an internal node,
which is omitted during unparsing).

  • Problem: the interpreter does not handle a variable with an arrow type well if no type information is given.
    The Fortress unparse tool has to omit the type information in this case, because the type is represented by
    internal AST nodes, which is not a proper Fortress syntax.
  • No work around. The interpreter needs to be able to handle the internal AST nodes.
  • FIXME: Once the interpreter is able to handle the internal AST nodes, uncomment the code and remove
    the alternative definition for the method y().

5. Ticket #275: The type checker does not detect illegal shadowings of local functions over top-level functions.

  • Problem: this does not really effect he closure conversion. It's just that, in the example given
    in the ticket, the object expression would refer to the top-level one instead of the local one.
  • No work around.

6. Ticket #287: The type checker does not recognize static parameters declared by nested FnDefs (in particular,
the static parameters declared by the inner FnDef).

  • Problem: I am not sure what the problem is. If there is only one level of FnDef, then the static parameters declared
    by it is recognized. The type checker only throws an error (type not in scope) when the FnDefs are nested and when
    referring to the static type parameter declared by the inner one.
  • No work around.
  • FIXME: Once the type checker is fixed, uncomment the test cases related to the nested FnDef in
    trunk/ProjectFortress/tests/objectCC_staticParams.fss

Related Test Cases

All test cases that test the closure conversion are prefixed with objectCC in the trunk/ProjectFortress/tests directory.

Not Yet Implemented

1. Exiting a label captured by an object expression

2. Nested object expressions (Need TypeCheckerOutput.populateTypes to be implemented)

3. Captured operator parameters (ASAIK, TypeCheckerOutput does not include this but I am not sure)

4. Captured DimRef (ASAIK, TypeCheckerOutput does not include this)

5. Captured UnitRef (ASAIK, TypeCheckerOutput does not include this)