• Compiler HyperBook
• – compilation_passes.ml
• ▷ cps
  • ▷ cpsbase.mli
    • – cpsast.ml
    • – cpscheck.ml
    • ▷ cpsdef.mli
      • – cpsdef.ml
    • – cpsprint.ml
    • ▷ cpsvar.mli
      • – cpsvar.ml
  • – cpsconvertclosures.ml
  • – cpsfree.ml
  • ▷ cpstransform
    • – base.ml
    • – definition.ml
    • – expression.ml
    • – rules.ml
• ▷ llvm
  • ▷ cpsllvm.mli
    • – cpsllvm.ml
• ▷ parser
  • – common.ml
  • – definition.ml
  • – expression.ml
  • – path.ml
  • ▷ tdop.mli
    • – tdop.ml
• ▷ support
  • ▷ union_find.mli
    • – union_find.ml
  • ▷ unique.mli
    • – unique.ml

Module Rules

1.  This module compile the pattern matching of a set of rules. A rule is composed of a pattern, matched against a value; and an expression (the body of the rule), to be executed if the pattern succeeds in matching the value.

The match(expression){rules} expression matches an expression against a set of rules; its behaviour is to evaluate the expression once, and try to match the resulting value against the patterns in rules until one succeeds, in which case the corresponding body is executed.

The order of the rules is thus important: a value can be matched by the patterns of two rules, e.g. (5,6) is matched by (5,_) and (_,6); but only the body of the first rule is executed. This implies that two successive rules in a match can be reordered if, and only if, they are disjoint, i.e. they cannot match the same value.

But when allowed, reordering and factorizing the compilation of rules matching lead to more compact, faster code. Trying to produce the most efficient code for matching against a set of rules is a NP-complete problem (the complexity arise when compiling multiple independent patterns, for instance tuple patterns). Rather than attempting to solve this problem, L specifies how pattern matching is compiled, which allows the developer to visualize the costs of its pattern matching.

Pattern matching rewrites

The compiler maintains a list of patterns that remain to be matched for each rule, and a list of values against which each rule is matched. The list of the first pattern to be matched in each rules is the first column, and is matched against the first value. Several cases can occur (see in the book "The implementation of functional programming languages" by Simon Peyton Jones, the chapter 5: "Efficient compilation of pattern matching", by Philip Wadler):

There is no more column

When there are no remaining patterns to match, and no remaining values, it means that all the rules match. As pattern matching selects the first rule that matches, we execute the body of the first rule, and discard the other rules with a warning.

For instance in

match(){
 () → body1
 () → body2
}

body1 matches and is executed; body2 also matches, but is superseded by body1, and is just discarded.

The column contain only variables

In this case, in each rule the variable is bound to the value, and matching continues. For instance in

match(expr1,...){
 (a,...) → body1
 (b,...) → body2
}

a is bound to v1 in the first rule, and b in the second rule; where v1 is a CPS variable representing the result of computing expr1 in the condition of the match (computation in the condition is thus not repeated). Matching then proceeds, starting from the second column.

This rule can be extended to incorporate wildcard (_) patterns (where nothing is bound), and all irrefutable patterns. A pattern is irrefutable if it does not contain any variant.

For instance, consider

match((expr1,expr2),...){
 (a,...) → body1
 (_,...) → body2
 ((c,d),...) → body3
}

The column contains only irrefutable patterns. Let v1 be a CPS variable containing the evaluation of expr1, and v2 containing the evaluation of expr2. Then a is bound to (v1,v2), c to v1, and d to v2.

The column contains only calls to constructors

A constructor is a specific version of a variant type; for instance 3 is a constructor of Int, True a constructor of Bool, and Cons(1,Nil) a constructor of List<Int>.

Note that if the column contain a variant, then all the constructors that it contains are of the same type: this is necessary for the pattern matching to typecheck.

When two contiguous rules have different constructors at the same place, they cannot match the same value simultaneously: they are thus disjoint, and can be swapped. This allows to group the rules according to the constructor in their first column (the order of the rules within a group being preserved).

For instance,

match(expr1, expr2){
 (Cons(a,Cons(b,Nil)),Nil) → body1
 (Nil,Nil) → body2
 (Nil,c) → body3
 (Cons(d,e),_) → body4 
}

can be grouped as (preserving the order between rules 1 and 4, and 2 and 3) :

match(expr1, expr2){
 (Cons(a,Cons(b,Nil)),Nil) → body1
 (Cons(d,e),_) → body4
 (Nil,Nil) → body2
 (Nil,c) → body3
}

Then, the matching of contiguous rules with the same constructor can be factorized out, as follow:

let v1 = expr1 and v2 = expr2 in
match(v1){
 Cons(hd,tl) → match((hd,tl),v2){
     ((a,Cons(b,Nil)), Nil) → body1 
     ((d,e),_) → body4 
 }
 Nil → match(v2){
     Nil → body2 
     c → body3 
 }
}

Note that the L compiler matches the values in the constructor before matching the other columns of the tuple, as was exemplified in the Cons rules.

The construct of matching only the constructors of a single variant type can be transformed directly into the CPS case expression. It is generally compiled very efficiently into a jump table, and dispatching to any rule is done in constant time. (Note that the compiler may not generate a jump table if the list of constructors to check is sparse).

The first column contains both refutable and irrefutable patterns

If the first column contains both kind of patterns, the list of rules is split into groups such that the ordering between rules is preserved, and either all the rules in the group have their first pattern that is refutable, or they are all irrefutable.

For instance, the following match:

match((v1,v2),v3){
 (_,1) → 1
 ((a,b),2) → a+b+2
 ((3,_),3) → ...
 ((4,_),_) → ...
 ((_,5),_) → ...
 ((a,b),c) → a+b+c
}

is split into three groups, with respectively rules 1-2 (_ and (a,b) are both irrefutable patterns), rules 3-5, and rule 6. Then the groups are matched successively, the next group being matched only if no rule matched in the first one. This amount to performing the following transformation:

let c = ((v1,v2),v3) in
match(c){
 (_,1) → 1
 ((a,b),2) → a+b+2
 _ → match(c){
     ((3,_),3) → ...
     ((4,_),_) → ...
     ((_,5),_) → ...
     _ → match(c){
         ((a,b),c) → a+b+c
         }
     }
}

Note that rules 3,4,5 also need to be split and transformed further using this method.

Compiling pattern matching

Compilation order

The order in which checking is made for a set of patterns is a choice, done by the compiler. L chooses to match the tuples from left to right, and the contents of the constructor as soon as they are matched; and to split rules according to the refutability of the pattern in their first remaining column. This choice may not be optimal in every case (but minimizing the number of matches is a NP-hard problem), but allows for a simple, visual analysis of the cost of pattern matching. The user is free to rearrange the set of patterns to improve performance (possibly guided by compiler hints).

Element retrieval

At the beginning of a match, all the components, needed by at least one rule, that can be retrieved (i.e. components in a tuple etc., but not those that are under a specific constructor) are retrieved. When a constructor is matched, all the components that can be retrieved that were under this constructor are retrieved. This behaviour produces the most compact code (avoid duplicating retrieval of elements in the compilation of several rules), but maybe not the most efficient (sometimes elements are retrieved that are not used). Optimizations, such as shrinking reductions, are allowed to move down or even duplicate code performing retrieval of elements into the case.

CPS

Compilation of pattern matching is done during the CPS transformation, which transforms source code from the AST language to the CPS language. There are several reasons for that:

• The CPS transformation of expression fixes the order of their evaluation; compiling pattern matching fixes the order in which patterns are matched. So it makes sense to do both at the same time, to have a single pass that fixes all the order of evaluation.

  As a side note, it makes sense to keep pattern matching in the AST language, because patterns are easy to type, and any typing error can be more easily returned to the user.

• The CPS language provides continuations, which allows to express explicit join points in the control flow, something not possible in the AST language (without creating new functions). These joint points are necessary notably to factorize the compilation of pattern matching (this problem is similar to compilation of boolean expressions with the short-circuit operators && and ||). For instance, compiling:

  match(v){ (4,5) → 1; _ → 2 }

  gives:

  let k_not4_5() = { kreturn(2) }
match(#0(v)){
 4 → match(#1(v)){
   5 → kreturn(1)
   _ → k_not4_5()
 }
 _ → k_not4_5()
}

  Matching against (4,5) can fail at two different steps, and the action to perform in these two cases are the same, so they should be factorized using the same continuation.

  The L compiler does not yet allow it, but "or-patterns" (i.e. in match(l){ Cons(Nil∣Cons(_,Nil)) → 0 _ → 1 }) also need join points. Finally, there is also a joint point (in expr_env.kcontext) to which the value of the bodies in each rule is returned.

All the functions that involve building CPS code are themselves in CPS style; see the Cps_transform_expression module for an explanation.

A complete example

Here is a (contrived) example of a complete pattern matching:

This pattern is compiled as follows. We begin by creating a join continuation, which is where the result of the match is returned. This allows to factorize the following computation (the addition to 17 in our case).

let kfinal(x) = { let x17 = x + 17 in halt(x17) }

Then, the condition of the match e is evaluated, and its result stored in a temporary value.

let v = ... eval e ...

Then, analysis of the patterns show that v contains a tuple.

let v.0 = #0(v)
let v.1 = #1(v)

Analysis of the patterns also show that v.0 contain a tuple. v.1 is a variant type, so its elements cannot be retrieved yet.

let v.0.0 = #0(v.0)
let v.0.1 = #1(v.0)

We begin by analysis the whole pattern (i.e. column c₀). All the rules are refutable, except the last one, so we split them into two contiguous blocks b_i and b_ii; b_ii is executed if matching against all the rules in b_i fail.

decl kb_ii

All the rules in b_i are tuples, so we inspect them from left to right (i.e. we begin by column c₁, then proceed with c₄). Analysis of column c₁ yields three contiguous blocks: the patterns in column c₁ are all irrefutable for block b_i.a, refutable for block b_i.b, and irrefutable again for block b_i.c.

decl kb_i.b, kb_i.c

As the patterns of column c₁ in rules in b_i.a are all irrefutable, we just have to associate the variable x to v.0.0 and a to v.0.1 for the translation of the body of the rules. (x and a are unused in the rules of the example).

We can then proceed with the analysis of column c₂ (still in block b_i.a). It is a variant, so we can regroup the rules according to the constructor, and perform a simple case analysis.

decl kcons
match(v.1){
 Nil → { kfinal(2) }
 Cons(x) → { kcons(x) } 
}

For the Nil constructor, we are already done. For Cons, we have to discriminate against the patterns inside the Cons. But first, we analyze these patterns to retrieve all the elements that are needed:

let kcons(x) = {
 let x.0 = #0(x)
 let x.1 = #1(x)
 let x.0.0 = #0(x.0)
 let x.0.1 = #1(x.0)

There are two contiguous blocks: one with rule 1 and 3 (since rule 2 has been regrouped with the Nil), and one with rule 4. We begin with the 1-3 block:

 decl knext
 match(x.0.0){
   1 → { kfinal(1)}
   3 → { kfinal(3)}
   _ → { knext()}
 }

If matching against the 1-3 block fails, we match against rule 4. If this fails, then matching against all the rules in b_i.a failed, and we try to match against the rules in b_i.b.

 let knext() = {
   match(x.0.1){
     4 → { kfinal(4)}
     _ → { kb_i.b()}
   }
 }
}

The rest of the matching is very similar. In b_i.b.1, the matching against rules 5 and 7 is factorized, because there is a common constructor. (Note that there is no factorization on Cons between rules 4 and 5, because they are in different blocks). Then blocks b_i.b.2, b_i.b.3, b_i.c are tried successively. In b_i.c, the test of Cons is factorized, but not the test for Nil, because testing Nil is done after testing 10.

Finally, the pattern matching always succeeds since rule 12 is irrefutable, so there is no need to introduce code that perform match_failure in case nothing succeeds in matching.

Note that the presentation would have been clearer if the patterns had been regrouped differently; in particular, grouping rules who share a constructor matched as the same time (e.g. exchanging rules 1 and 2, and rule 5 and 6) would improve the presentation.

This module is mutually recursive with the module performing transformation into CPS of expressions, from which we require the transform function.
2.  Identifying the structure of patterns; retrieving needed components.
The Structure module allows to analyze a list of patterns, and build the code to retrieve all the components needed by at least one pattern. This ensures that (whenever possible) the components are retrieved only once, which makes the code more compact.

This code also checks that the components are compatible (e.g. that the matched tuples have the same arity), in case that type checking failed to do it.

   The aim of this module is to produce a value of type t, which is a CPS variable together with the CPS variables for each of its sub-components. Note that structures do not go into variants, because we cannot: the contents in variants can be obtained only once they are matched.
   build v patts k analyze patts to create a structure containing all the CPS variables needed for compiling the rules, and "returns" (in CPS style) by calling k with that structure. v is the CPS variable against which the patts are matched.
   The implementation is done in two steps:

• First we identify the structure (in normal style, by unification of the patterns);
• Then we build the code to retrieve the CPS variables (in CPS style).

   Identification works by first-order unification of all the patterns. The unit structure type is a special representation of a pattern, containing the results of the previous unifications. We do not enter variant types, because we will not retrieve their components until they are matched (and we redo an identification when this happens).
     No new information about the structure, and we do not enter in variants.
   Second step: build all the necessary CPS vars, in CPS style. Takes a CPS variable and its identified structure, and "return" (in CPS style, using the k argument) the structure completed with the CPS variable of its components.
   The main algorithm: first identify the structure, and then fill it with the CPS variables.
   The current status of pattern matching compilation is represented by a list of rules and one pattern_env. rule contains information per rule being matched, while pattern_env contains information common to all the rules.
     The list of patterns that still have to be matched. Always have the same length than env.remaining_vs.
     If all the elements in env.remaining_vs match remaining_patts, then this body is executed.
     The continuation to call if nothing matches: this continuation can raise a match_failure exception, or match another list of rules.
     The value against which the rules are matched (with their structures).
     We are compiling a set of patterns in an expression: this is the environment corresponding to that expression. expr_env is used only when compiling the body of a rule.
   A mapping from AST variables to CPS variables.
   The continuation function, to which we "return" the result of executing the body of the rule.
3.  Helper functions for transform_rules: define refutability, irrefutability, rules splitting by contiguous blocks.
   A pattern is refutable if contains a specific variant. A variant is currently an integer, a boolean, or an injection (i.e. user-defined variant).

A pattern is irrefutable if it never refers to a specific variant.

   split_firsts pred rules returns two lists of rules, (selected,other), with selected the first elements of rules that satisfy the predicate pred, and other the remaining elements (i.e. other is [ ] or so that pred (List.hd other) =  false).
   split_on_first_pattern pred l returs two lists of rules, split according to whether their first pattern is satisfied by pred.
4.  Entry point to the pattern compilation loop.
   Requires that env.remaining_vs and all rule.remaining_patts have the same length; and that the set of rules is not empty.
     No remaining pattern: we managed to match everything. Just execute the body of first, and discard the other rules.
     At least one remaining pattern. If the pattern is refutable, select the rules beginning by a refutable pattern, else select the rules beginning by an irrefutable pattern. Try to match against these rules; if that fails, execute the other rules.
           Patterns refering to a specific variant, compiled into a case.
           Structural patterns that increase the remaining_patts.
5.  Irrefutable patterns.
   As all values of the components of the tuple have already been retrieved (and are in structv), the only responsibility of this function is to update the map_addition of the rules.
     Jointly traverse a pattern (containing the AST variable names) and a structure (containing the CPS variables) to improve the map_addition (containing a map from AST variables to CPS variables).
6.  Structural refutable patterns.
   Replace the head of remaining_patts and remaining_vs, which is a Tuple, by the contents of this tuple.
   Replace the head of remaining_patts and remaining_vs, which is a Fold, by the contents of the fold.
7.  Specific variants, that are compiled into a case.
   map_into_casemap is similar to List.map, except that rather than returning a linear list, it splits the list into a casemap according to the key returned by the f function.
   build_rules_casemap compiles the code that matches v against the rules in rules_casemap. To each key in the casemap corresponds a list of rules, which is compiled into a continuation using transform_rules; when all continuations are obtained, the actual case instruction can be built.

The g functional parameter allows to build code and change env before the list of rules are compiled.

   Compilation of integers and boolean is straightforward: we just have to extract the integer number corresponding to the case.
   In addition to extracting the number for the case, injection also add the pattern they contain to the head of remaining_patts. At the beginning of the continuation k corresponding to a set of rules that match a variant, the structure needed to these rules are identified and obtained against the CPS var argument of k, and added at the head of remaining_vs.
   Entry point of the module.
     Note: we could directly call match_failure. But should we allow this degenerate case? For now we fail if this happens.
     If there is only one rule (e.g. compiling let), keep the context. Else, create a "join" continuation, to avoid code duplication.
       If there is an irrefutable rule, then match_failure is never raised. We avoid creating a defaultk continuation using Obj.magic 0; we shorten l to ensure that defaultk will never be used.
         Initialize pattern compilation.

---