Sharing information computed by monad actions

Question

I am studying compiler construction using Haskell. I am using fixed point data type recursion to represent abstract syntax trees (ast).

I am investigating how to write the type checker for a toy language having simple expressions (numeric and logic constants, binary operations and local variable declarations).

The type checker is a read-write-state (RWS) monad:

reader because it uses a context consisting of an environment with symbol definitions (an association list of a symbol and its type);
writer because it generates a list of error messages;
state will be needed later for implementing nominal type equivalence, and by now I am just counting how many variables are defined in the program (just as a demonstration of its use).

The value returned by the monad is an ast annotated with types (for expressions) or environments (for declarations).

The function checker receives an ast of the input program and results in a new ast annotated with RWS monad actions that, when run, gives the type (if the ast is an expression) or the environment (if the ast is a declaration).

For instance, consider the input program

let x = 2 + 3 in 1 + x

with the corresponding ast:

                    Let                     
                     |                      
          -----------------------           
         |                      |           
     VarDec: x               Bin Add        
         |                      |           
         |                ------------      
         |                |          |      
      Bin Add          Num 1.0     Var x    
         |                                  
    -----------                             
   |          |                             
Num 2.0    Num 3.0

Type checking it will produce the following ast:

                  action1
                    Let                     
                     |                      
          -----------------------           
         |                      |           
      action2                action3
     VarDec: x               Bin Add        
         |                      |           
         |                ------------      
         |                |          |      
      action4          action5    action6
      Bin Add          Num 1.0     Var x    
         |                                  
    -----------                             
   |          |                   
action7    action8      
Num 2.0    Num 3.0

which is recursively annotated with RWS monad actions.

Later phases of the compiler will need to know the information produced by the annotations in the ast (and its children, recursively). Therefore it will be needed to run the corresponding action to get it.

A root action is constructed by composing the actions of the children, according to the rules of the language.

For instance, in order to get the type of the root expression (a let expression), action1 has to be run, and that will make action2 and action3 to be run as well, because when action1 was created, it used action2 and action3.

When the type of the addition 1+x is needed, action3 has to be run in order to get it.

So actions will be run repeatedly. The way the type checker is structured (using RWS monad actions) loses sharing of the computed information for each node of the ast.

Is there any technique to recover this sharing, eliminating the need of recomputing actions?

Chris Kuklewicz Chris Kuklewicz · Accepted Answer · 2012-05-18T08:17:24

It sounds like your design has turned into a blind alley. You are showing us a bit of how it looks.

I am studying compiler construction using Haskell.

Studying implies you could read how other people do type checking (e.g. GHC or an example from Oleg). Or it may be your mean to learn more by trying invent.

The way the type checker is structured...loses sharing of the computed information for each node of the ast.

So don't lose the information. If the type checker is run inside a monad then you can, eventually, design it to remember the state.

Is there any technique to recover this sharing, eliminating the need of recomputing actions?

More concretely, you want to replace the actionX with its results after it has been run. This looks very very very much like a desire for a lazy value: compute once and memorize the result (only slightly tricky with errors).

Perhaps each action recalculates the subtree from its node, including itself. The children's actions are replaced by their results (and recalculated subtrees).

Or if your AST is one immutable thing then perhaps the state should be a parallel AST.

Sharing information computed by monad actions

2 Answers