3  Compilation

• 3.1  Output of the match compiler
• 3.2  Initial state
• 3.3  Classical scheme

3.1  Output of the match compiler

• Let-bindings: let (x l_x) l, nested let-bindings are abbreviated as:

  let (x1 l1) (x2 l2) ⋯ (xn ln) l

  
  
  
• Static exceptions, exit and traps, catch l₁  with l₂. If, when evaluating the body l₁, exit is encountered, then the result of evaluating catch l₁  with l₂ is ther result evaluating the handler l₂, otherwise it is the result of evaluating l₁. By contrast with dynamic exceptions, static exceptions are directly compiled as jumps to the associated handlers (plus some environment adjustment, such as stack pops), whereas traps do not generate any code.
  
  
• Switch constructs:

  switch l  with    case c1: l1 ⋯  case ck: lk    default: d

  
  The result of a switch construct is the evaluation of the l_i corresponding to the constructor c_i appearing as the head of the value v of l. If the head constructor of v doesn't appear in the case list, the result is the evaluation of the default d expression.
  
  The default clause default: d can be omitted. In such a case the switch behavior is unspecified on non-recognized values. Scheme C can thus omit the default clause when it is known that case lists will cover all possibilities at runtime. We use the keyword switch*  to highlight switch constructs with no default clause.
  
  Those switch constructs are quite sophisticated, they compile later into more basic constructs: tests, branches and jump tables. We in fact modified the Objective Caml compiler to improve the compilation of switch constructs, using techniques first introduced in the context of compiling the case statement of Pascal [3]. The key points are using range tests, which can typically be performed by one single (unsigned) test and branch plus possibly one addition, cutting sparse case lists into denser ones, and deciding which of jump tables or test sequence is more appropriate to each situation. A survey of these techniques can be found in [19].
  
  
• Accessors: field n x, where x is a variable and n is an integer offset. By convention, the first argument of non-constant constructors stands at offset zero.
  
  
• Sequences: l₁; l₂ and units: ()

3.2  Initial state

3.3  Classical scheme

1. If n is zero (i.e. when there are no more columns), then the first row of P matches the empty vector ():

   C((),

   ⎛ ⎜ ⎜ ⎜ ⎝      →  l1      →  l2 ⋮      →  lm ⎞ ⎟ ⎟ ⎟ ⎠

   ) = l1

   
   
   
2. If n is not zero, then a simple compilation is possible, using the following four rules.
   1. If all patterns in the first column of p are variables, y¹, y², ..., y^m, then:
      C(x, P → L) = C((x₂  x₃… x_n), P' → L')
      where

      P' → L' =

      ⎛ ⎜ ⎜ ⎜ ⎝ p21 ⋯ pn1  →  let (y1 x1) l1 p22 ⋯ pn2  →  let (y2 x1) l2 ⋮ p2m ⋯ pnm  →  let (ym x1) lm ⎞ ⎟ ⎟ ⎟ ⎠

      )

      We call this rule, the variable rule. This case also handles wild-card patterns: they are treated like variables except that the let-binding is omitted.
      
      
   2. If all patterns in the first column of P are constructor patterns c(q₁, … , q_a), then let C be the set of matched constructors, that is, the set of the head constructors of the p₁ⁱ's.
      
      Then, for each constructor c in C, we define the specialized clause matrix S(c,P → L) by mapping the following transformation on the rows of P.

      	p1i	S(c,P → L)
      	c(q1i, … , qai)	q1i	⋯	qai	p2i	⋯	pni	→	li
      	c'(q1i, … , qa'i)   (c' ≠ c)	No row

      (Matrices S(c,P → L) and P → L define the same matching predicate when x₁ is bound to some value c(v₁, … , v_a).) Furthermore, for a given constructor c of arity a, let y₁, … ,y_a be fresh variables. Then, for any constructor c in C, we define the lambda-expression r(c):

      (let (y1 (field 0 x1))    ...    (ya (field (a−1)  x1))    C((y1, … ,ya,x2, … ,xn),S(c,P → L)))

      
      Finally, assuming C = {c₁,…, c_k}, the compilation result is:

      switch x1  with    case c1: r(c1) ⋯ case ck: r(ck)    default: exit

      (Note that the default clause can be omitted when C makes up a full signature.) We call this rule, the constructor rule.
      
      
   3. If P has only one row and that this row starts with an or-pattern:

      P =

      ⎛ ⎝   (q1 ∣... ∣qo)   p2  ⋯  pn  →  l ⎞ ⎠

      ,

      
      
      Then, compilation result is:

      C((x1),

      ⎛ ⎜ ⎜ ⎝   q1  →  () ⋮   qo  →  () ⎞ ⎟ ⎟ ⎠

      ); C( (x2… xn), ( p2…pn → l ))

      This rule is the orpat rule. Observe that it does not duplicate any pattern nor action. However, variables in or-patterns are not supported, since, in clause q_i → (), the scope of q_i variables is the action “()”.
      
      
   4. Finally, if none of the previous rules applies, the clause matrix P → L is cut in two clause matrices P₁ → L₁ and P₂ → L₂, such that P₁ → L₁ is the largest prefix of P → L for which one of the variable, constructor or orpat rule applies.
      
      Then, compilation result is:

      catch C(x, P1 → L1)  with C(x, P2 → L2)

      This rule is the mixture rule.