One AST, Several Phases

V. E. McHale

23 Aug. 2026

Often in a compiler a pass will transform the AST so that some variant is no longer present, so that further passes need only handle a smaller subset of cases.

Consider desugaring; suppose the syntax [max x^2+max y] means λx.λy. max x^2 + max y; x and y are implicitly the bound variables.


type Name = { Int Str `name };
type ResVar = { `x ⊕ `y };

type AbsAST a = { a a `ap ⊕ a Name `lam ⊕ Name `var };
type AST = AbsAST(AST);

type DExpr = AbsAST(DExpr) ∪ { DExpr `dfn ⊕ ResVar `resVar };
type Syn = AbsAST(Syn) ∪ { DExpr `dfn };

fresh : Int -- Int Name Name
      := [ 1 + dup 1 + dup ["x" `name] dip "y" `name ]

dedfn : Int Name Name DExpr -- Int AST
      := [ { `resVar⁻¹ { `x⁻¹ drop & `y⁻¹ nip } `var
           & `lam⁻¹ [dedfn] dip `lam
           & `var⁻¹ drop2 `var
           & `dfn⁻¹ [drop2 fresh] dip dedfn
           & `ap⁻¹ [dup2] dip2 (243) [dedfn] dip3 (45) dedfn (32) `ap
           } ]

desugar : Int Syn -- Int AST
        := [ { `dfn⁻¹ [fresh] dip dedfn
             & `lam⁻¹ [desugar] dip `lam
             & `var⁻¹ `var
             & `ap⁻¹ [desugar] dip (32) desugar (23) `ap
             }

This does check pattern-match exhaustiveness; if we had written

dedfn : Int Name Name DExpr -- Int AST
      := [ { `resVar⁻¹ { `x⁻¹ drop & `y⁻¹ nip } `var
           & `lam⁻¹ [dedfn] dip `lam
           & `var⁻¹ drop2 `var
           & `dfn⁻¹ [drop2 fresh] dip dedfn
           } ]

it would raise the objection

examples/ast.piz:15:23: {DExpr DExpr `ap ⊕ DExpr Name `lam ⊕ Name `var ⊕
                        DExpr `dfn ⊕ ResVar `resVar} ⊀ {DExpr Name `lam ⊕
                                                       Name `var ⊕ DExpr `dfn ⊕
                                                       ResVar `resVar}

And the result is guaranteed to be of type AST; if we had written

dedfn : Int Name Name DExpr -- Int AST
      := [ { `resVar⁻¹ { `x⁻¹ drop & `y⁻¹ nip } `var
           & `lam⁻¹ [dedfn] dip `lam
           & `var⁻¹ drop2 `var
           & `dfn⁻¹ `dfn
           & `ap⁻¹ [dup2] dip2 (243) [dedfn] dip3 (45) dedfn (32) `ap
           } ]

it would fail with

examples/ast.piz:65:65: occurs check failed: ‘'A’, ‘'A Int ρ₁’

We can define e.g. pretty-printers on AST variants without needlessly repeating ourselves like so:

printName : Name -- Str
          := [ { `name⁻¹ nip } ]

brackets : Str -- Str
         := [ ["["] dip strcat "]" strcat ]

printAbs : [a -- Str] AbsAST(a) -- Str
         := [ { `var⁻¹ printName nip
              & `lam⁻¹ printName ["λ"] dip strcat " " strcat [swap $] dip swap strcat
              & `ap⁻¹ [dup] dip2 (24) [$] dip2 (13) [$ parens] dip strcat
              }
            ]

printAST : AST -- Str
         := [ [[printAST]] dip printAbs ]

printDExpr : DExpr -- Str
           := [ { `resVar⁻¹ { `x⁻¹ "x" & `y⁻¹ "y" }
                & `dfn⁻¹ printDExpr brackets
                & [[printDExpr]] dip printAbs
                }
              ]

Anything that works on a DExpr should work on an AST, which is the case:

 0 "b" `name `var 0 "a" `name `var `ap 0 "a" `name `lam printAST
"λa (a)b"
 0 "b" `name `var 0 "a" `name `var `ap 0 "a" `name `lam printDExpr
"λa (a)b"

And supplying a DExpr to printAST is a type error, viz.

 `x `resVar `dfn printAbs
1:12: ‘{ (ρ₁ ⊃ {`resVar: (ρ₁ ⊃ {`x})}) `dfn
       }’ is not an acceptable argument, expected
‘{a a `ap ⊕ a (ρ₂ ⊃ {`name: Int Str}) `lam ⊕ (ρ₁ ⊃ {`name: Int Str}) `var}’
"λa (a)b"
 `x `resVar `dfn printDExpr
"[x]"