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.

<table style="border: 2px solid #D0D0D0; padding: 5px; width: 80%; background-color: #f0f9ff; margin-left:auto; margin-right:auto; border-spacing: 5px"><tr><td>
%T% _Tip:_ If you write your own syntax definition, the generated signature can be found in =include/<LanguageName>.str=.
</td></tr>
</table>

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.
	1. Specify new constants for these operators in a signature. Use =UnOp= and =BinOp= as types of these operators.
	1. Define constructors =UnExp= and =BinExp=, which combine an operator and an expression (respectively two expressions) to an expression.

<table style="border: 2px solid #D0D0D0; padding: 5px; width: 80%; background-color: #f0f9ff; margin-left:auto; margin-right:auto; border-spacing: 5px"><tr><td>
%T% _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.
</td></tr>
</table>

---+++ 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:

<verbatim>
rules 

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

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.

<table style="border: 2px solid #D0D0D0; padding: 5px; width: 80%; background-color: #f0f9ff; margin-left:auto; margin-right:auto; border-spacing: 5px"><tr><td>
%T% _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.
</td></tr>
</table>

<table style="border: 2px solid #D0D0D0; padding: 5px; width: 80%; background-color: #fff9f0; margin-left:auto; margin-right:auto; border-spacing: 5px"><tr><td>
%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 [[http://releases.strategoxt.org/docs/api/libstratego-lib/stable/docs/][API docs]] for useful helper rules.
</td></tr>
</table>

---+++ 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=:

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

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=:

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

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:

<verbatim>
strategies

  desugar-all = innermost(desugar)
</verbatim>

<table style="border: 2px solid #D0D0D0; padding: 5px; width: 80%; background-color: #f0f9ff; margin-left:auto; margin-right:auto; border-spacing: 5px"><tr><td>
%T% _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.
</td></tr>
</table>

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.

<table style="border: 2px solid #D0D0D0; padding: 5px; width: 80%; background-color: #f0f9ff; margin-left:auto; margin-right:auto; border-spacing: 5px"><tr><td>
%T% _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 [[http://releases.strategoxt.org/docs/api/libstratego-lib/stable/docs/][API docs]].
</td></tr>
</table>

---+++ 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=:

<verbatim>
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
</verbatim>

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.
	1. 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.
	1. 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.

<table style="border: 2px solid #D0D0D0; padding: 5px; width: 80%; background-color: #f0f9ff; margin-left:auto; margin-right:auto; border-spacing: 5px"><tr><td>
%T% _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"=.
</td></tr>
</table>

---+++ 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.

<table style="border: 2px solid #D0D0D0; padding: 5px; width: 80%; background-color: #f0f9ff; margin-left:auto; margin-right:auto; border-spacing: 5px"><tr><td>
%T% _Tip:_ Some of your test cases might still fail, even when your implementation is correct. There are two reasons:
	1. 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.
	2. 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=.
</td></tr>
</table>

---+++ 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:

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

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.

<table style="border: 2px solid #D0D0D0; padding: 5px; width: 80%; background-color: #f0f9ff; margin-left:auto; margin-right:auto; border-spacing: 5px"><tr><td>
%T% _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.
</td></tr>
</table>

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.

-- Main.GuidoWachsmuth - 11 Oct 2012