Parallel Type Checkers/Inferencers

In this lesson you learn how to define parallel type checkers or inferencers. For the sake of a choice, we will parallelize the one in the previous lesson, but the ideas are general. We are using the same idea to define type checkers for other languages in the K tool distribution, such as SIMPLE and KOOL.

The idea is in fact quite simple. Instead of one monolithic typing task, we generate many smaller tasks, which can be processed in parallel. We use the same approach to define parallel semantics as we used for threads in IMP++ in Part 4 of the tutorial, that is, we add a cell holding all the parallel tasks, making sure we declare the cell holding a task with multiplicity *. For the particular type inferencer that we chose here, the one in Lesson 5, each task will hold an expression to type together with a type environment (so it knows where to lookup its free variables). We have the following configuration then:

configuration <tasks color="yellow">
                <task color="orange" multiplicity="*">
                  <k color="green"> $PGM:Exp </k>
                  <tenv color="red"> .Map </tenv>
                </task>
              </tasks>
              <mgu color="blue"> .Mgu </mgu>

Now we have to take each typing rule we had before and change it to yield parallel typing. For example, our rule for typing multiplication was the following in Lesson 5:

rule T1:Type * T2:Type => T1 = int ~> T2 = int ~> int

Since * was strict, its two arguments eventually type, and once that happens the rule above fires. Unfortunately, the strictness of multiplication makes the typing of the two expressions sequential in our previous definition. To avoid typing the two expressions sequentially and instead generating two parallel tasks, we remove the strict attribute of multiplication and replace the rule above with the following:

rule <k> E1 * E2 => int ...</k> <tenv> Rho </tenv>
     (. => <task> <k> E1 = int </k> <tenv> Rho </tenv> </task>
           <task> <k> E2 = int </k> <tenv> Rho </tenv> </task>)

Therefore, we generate two tasks for typing E1 and E2 in the same type environment as the current task, and let the current task continue by simply optimistically reducing E1*E2 to its expected result type, int. If E1 or E2 will not type to int, then either their corresponding tasks will get stuck or the <mgu/> cell will result into a clash or cycle, so the program will not type overall in spite of the fact that we allowed the task containing the multiplication to continue. This is how we get maximum of parallelism in this case.

Before we continue, note that the new tasks hold equalities in them, where one of its arguments is an expression, while previously the equality construct was declared to take types. What we want now is for the equality construct to possibly take any expressions, and first type them and then generate the type constraint like before. This can be done very easily by just extending the equality construct to expressions and declaring it strict:

syntax KItem ::= Exp "=" Exp  [strict]

Unlike before, where we only passed types to the equality construct, we now need a runtime check that its arguments are indeed types before we can generate the updateMgu command:

rule <k> T:Type = T':Type => . ...</k>
     <mgu> Theta:Mgu => updateMgu(Theta,T,T') </mgu>

Like before, an equality will therefore update the <mgu/> cell and then it dissolves itself, letting the <k/> cell in the corresponding task empty. Such empty tasks are unnecessary, so they can be erased:

rule <task>... <k> . </k> ...</task> => .

We can now follow the same style as for multiplication to write the parallel typing rules of the other arithmetic constructs, and even for the conditional.

To parallelize the typing of lambda we generate two fresh types, one for the variable and one for the body, and make sure that we generate the correct type constraint and environment in the body task:

rule <k> lambda X . E => Tx -> Te ...</k> <tenv> TEnv </tenv>
     (. => <task> <k> E = Te </k> <tenv> TEnv[Tx/X] </tenv> </task>)
  when fresh(Tx:Type) andBool fresh(Te:Type)

Note that the above also allows us to not need to change and then recover the environment of the current cell.

For function application we also need to generate two fresh types:

rule <k> E1 E2 => T ...</k> <tenv> Rho </tenv>
     (. => <task> <k> E1 = T2 -> T </k> <tenv> Rho </tenv> </task>
           <task> <k> E2 = T2 </k> <tenv> Rho </tenv> </task>)
  when fresh(T2:Type) andBool fresh(T:Type)

The only rule left is that of mu X . E. In this case we only need one fresh type, because X, E and mu X . E have all the same type:

rule <k> mu X . E => T ...</k>  <tenv> TEnv </tenv>
     (. => <task> <k> E = T </k> <tenv> TEnv[T/X] </tenv> </task>)
  when fresh(T:Type)

We do not need the type environment recovery operation, so we delete it.

We can now kompile and krun all the programs that we typed in Lesson 5. Everything should work.

In this lesson we only aimed at parallelizing the type inferencer in Lesson 5, not to improve its expressiveness; it still has the same limitations in terms of polymorphism. The next lessons are dedicated to polymorphic type inferencers.

Go to Lesson 7, Type Systems: A Naive Substitution-based Polymorphic Type Inferencer.