Day 6

At the sixth day, you need to define rewrite rules for desugaring, type projection, and type constraints for MiniJava.

Desugaring

A uniform representation of unary and binary expressions eases type analysis and code generation (next milestone). To get such a uniform representation, you need to desugar abstract syntax trees during the analysis phase.

Signatures

Signatures declare sorts and constructors for terms. In Spoofax, terms are used to represent abstract syntax trees. The corresponding signature is generated from the constructors in a syntax definition. You can find a signature for MiniJava in assignment1/MiniJava.str. It was generated from a syntax definition, which itself is not included in the initial project.

Tip: If you write your own syntax definition, the generated signature can be found in include/.str.

Before you can implement a desugaring, you need to define a signature for the uniform representation of expressions:

1. Identify unary and binary operators in MiniJava.
2. Specify new constants for these operators in a signature. Use UnOp and BinOp as types of these operators.
3. Define constructors UnExp and BinExp, which combine an operator and an expression (respectively two expressions) to an expression.

Tip: Signatures can be defined in Stratego files. These files typically end in .str. In a Spoofax project, user-defined Stratego files should be placed inside the trans/ directory.

Rewrite Rules

Rewrite rules are local transformations. They consist of a name, a left-hand side pattern, a right-hand side pattern, and optional constraints. For example, the following rule defines a rule to desugar an addition:

rules 

  desugar: Add(e1, e2) -> BinExp(Plus(), e1, e2)

This rule is named desugar. On the left-hand side, the rule matches an addition. During the match, variables e1 and e2 are bound to actual terms. On the right-hand side, the rule instantiates a binary expression (in a uniform representation). During the instantiation, variables e1 and e2 are replaced with the terms they are bound to.

You can extend desugar to replace the different unary and binary expressions in the abstract syntax tree with a uniform representation of these expressions. Define a rewrite rule desugar for every unary or binary operator, which transforms the original expression into a uniform representation.

Tip: In Stratego, rewrite rules typically share the same name, when they cover different cases of the same transformation. Thereby, the order of rules is irrelevant. Thus, it is important to ensure rules to be mutually exclusive.

%GS% Challenge: Define a desugaring for octal numbers. In Java, octal numbers start with leading zeros. Define a rewrite rule which matches such numbers and transforms them to decimal integers. See the API docs for useful helper rules.

Editor Integration

To test your transformation, you need to define a builder. This is done similar to the builder for pretty-printing. Add the following rewrite rule to trans/minijava.str:

editor-desugar:
  (selected, position, ast, path, project-path) -> (filename, text)
  where
    filename := <guarantee-extension(|"desugared.mjv")> path ;
    text     := <desugar> selected

Again, the rule follows Spoofax' convention for strategies which implement editor services. On the left-hand site, it matches a tuple of the selected node, its position in the ast, the path of the current file and the project path. On the right-hand site, it instantiates a pair, consisting of a filename and the designated text of the file. Both variables are bound in the where clause. The file name is derived from the path of the current file, while the content of the file is a desugared version of the selected AST node.

You also need to hook your strategy into the editor, making desugaring available in the Transform menu. You can do this in editor/MiniJava-Builders.esv:

builder : "Desugar AST (selection)" = editor-desugar (openeditor) (realtime) (meta) (source)

This rule defines a builder, its label in the Transform menu, and its implementation strategy editor-desugar. Annotations can be used for different variants of builders. (openeditor) ensures that a new editor window is opened for the result. (realtime) requires this editor to be updated whenever the content in the original editor changes. (meta) restricts the builder to be only available to the language engineer, but not to the language user. While you can invoke the builder, people who install your MiniJava plugin cannot. Finally, (source) tells Spoofax to run the builder on an unanalysed (and also not desugared) AST.

Strategies

Rewrite rules typically define local transformations inside an AST. Strategies can orchestrate rewrite rules to complex transformations of complete ASTs. A strategy consists of a name and a definition, which is typically a combination of strategy applications. For example, the following strategy orchestrates local desugarings to a desugaring of complete ASTs:

strategies

  desugar-all = innermost(desugar)

Tip: Rewrite rules with the same name define a strategy of this name. Thus, the term strategy might either refer to a strategy or to a group of rewrite rules.

This strategy is named desugar-all. It applies local desugar rules. The application is guided by a generic traversal strategy innermost, which tries to apply its parameter inside a tree, starting at the leaves (bottom-up, left-to-right). Whenever an application is successful, the result is traversed again. While this is needed for many desugarings, this is might not be necessary for MiniJava. Same results can be achieved with different generic traversals. You should try different traversals. Try to understand what is going on and decide for a suitable one.

Tip: You can use the library strategy debug to print the currently visited node. For example, innermost(debug; desugar) will debug all nodes before it tries to desugar them. You can find more library strategies in the API docs.

Editor Integration Revisited

With a builder, you can invoke a transformation manually from the Transform menu. However, desugaring should be an automatic transformation as part of static analysis. In Spoofax, static analysis is performed by an observer strategy. The observer strategy needs to be specified in editor/MiniJava-Builders.esv. In the initial project, this strategy is called editor-analyse. It is implemented in trans/minijava.str:

editor-analyse:
  (ast, path, project-path) -> (ast, errors, warnings, notes)
  with
    editor-init ; 
    // add analysis here
    <collect-all(fail, conc)> ast => errors ;
    <collect-all(fail, conc)> ast => warnings ;
    <collect-all(fail, conc)> ast => notes

On the left-hand side, it matches the current ast, the path of the current file, and the project-path of the Spoofax project. On the right-hand side, it returns an analysed ast and lists of errors, warings, and notes. Currently, the analysed AST is just the original AST. Integrate your desugaring strategy into editor-analyse. Make sure to return the desugared abstract syntax tree as the first component of the resulting tuple.

To test your implementation, you can use a modified version of the builder labeled Show abstract syntax. You can find its definition in editor/MiniJava-Builders.esv. In its current version, it applies generate-aterm on the original AST (cf. the (source) annotation). Try to understand what generate-aterm does. Next, define a new builder labeled Show analysed syntax, which applies generate-aterm on the analysed AST instead. Finally, open a MiniJava program and run the new builder. At this point, you can get rid of your old desugaring builder.

Type Analysis

Type analysis is part of the static analysis of programs. It typically consists of a type projection, which maps language constructs to their types, and type constraints, which restrict a language to a set of well-typed programs.

Type Projection

You need to define a projection type-of from MiniJava expressions to their types:

1. Define a rewrite rule which rewrites integer constants to type integer.
2. Define similar rewrite rules for boolean constants.

Next, you need to extend this projection to unary and binary operators:

1. Define a rewrite rule for each unary operator which rewrites the operator to a pair of its input and output type.
2. Define a rewrite rule for each binary operator which rewrites the operator to a triple of its two input types and its output type.

Finally, you can extend type-of to work on unary and binary expressions. Ensure to yield only the type of well-typed expressions.

Tip: In Stratego, you can use terms without constructors as tuples. For example, the term ("1", "2") represents a pair of strings "1" and "2".

Editor Integration

To test your implementation, you can give the type of an expression as hover help. Of course, hover help is provided by a strategy. This needs to be specified in editor/MiniJava-References.esv. See the accompanying generated file for documentation how to do this. The strategy itself should be implemented in trans/minijava.str. It should rewrite a tuple (target, position, ast, path, project-path) to the hover text as a string. Therby, target is the AST node the mouse is hovering over, position is a path from the root of the AST to that node, ast is the complete AST, path is the path of the current file, and project-path is the path of the current Spoofax project.

Tip: Some of your test cases might still fail, even when your implementation is correct. There are two reasons: The selected term is a leaf. In this case, Spoofax might apply type-of only to the leaf, for example "1". But type-of can only handle IntValue("1"). You can ignore these cases. The selected term is desugared. In this case, Spoofax will apply type-of to the original term, not to the desugared term. Thus, type-of will fail, since it assumes desugared terms. You can fix this by changing run type-of to ... into run type-of-helper to ... in your test cases. Then you can define a strategy type-of-helper which first calls desugar-all, before it calls type-of.

Type Constraints

You can now use type-of to report type errors on unary and binary expressions. You should report errors on subexpressions which have a type different from the one expected by the operator. Appropriate rules need to transform AST nodes to an error term and an error message:

editor-error: 
  UnExp(op, exp) -> (exp, $[Type mismatch.])
  where
    (t1, _) := <type-of> op;
    t2      := <type-of> exp;
    <not(eq)> (t1, t2)

This rule reports type errors in unary expressions. First, it determines the type of the unary operator, which is a pair of an input type t1 and an (irrelevant) output type. Next, it determines the type t2 of the subexpression. If t1 and t2 are not equal, it rewrites the unary expression to a pair. The first component determines the error location. Thus, the error will be reported on the subexpression. The second component is the error message.

Tip: Error messages are important for the user to understand and fix errors. The example error message does not provide much information. You can improve this by reporting the actual and the expected type.

Errors, warnings, and notes are collected in editor-analyse. Here, you can use editor-error for collecting errors. You can then build your project and test your type checks either interactively in a MiniJava editor or by running your test cases.

Finally, you should also implement error checking in print statements, if statements, and while loops.

-- GuidoWachsmuth - 11 Oct 2012