Algebraic Data Types

We implement an algebraic data type to model abstract syntax trees formed by the grammar below.

Grammar of a Simple Programming Language

Expr ::=   Number
         | Expr '+' Expr 
         | Expr '-' Expr 
         | Expr '*' Expr
         | '(' Expr ')'
         | Ident
         | Expr '>=' Expr
         | Ident ':=' Expr
         | Expr ';' Expr
         | 'if' Expr 
              'then' Expr 
              'else' Expr 'fi'
         | 'while' Expr 'do' 
              Expr 
           'od'

enum Expr:
  // Arithmetic expressions
  case N(n:Int)
  case Plus(l:Expr, r:Expr)
  case Minus(l:Expr, r:Expr)
  case Times(l:Expr, r:Expr)

  // Parenthesized expressions (e)
  case Par(e:Expr)

  // Identifiers
  case I(n:String)

  // Comparisons l>=r
  case GEq(l:Expr, r:Expr)
  
  // Programs
  
  // Assignment x := v
  case Assign(x:I, v:Expr)

  // Sequential composition p ; r
  case Seq(p:Expr, r:Expr)  
  
  // Conditional if p then t else e
  case If(p:Expr, t:Expr, e:Expr)
  
  // Loop while p do b
  case While(p:Expr, b:Expr)

Formal Semantics of a Simple Programming Language

The formal semantics, a structural operational big-step semantics, is a detailed specification for an interpreter that almost literally translates to Scala.

Store and Judgments

• Store: maps variables to values

• Judgments: \(\langle \mathtt{e},\xi \rangle \Downarrow \langle v,\xi' \rangle\)

  Evaluating expression \(\mathtt{e}\) in state \(\xi\) yields (\(\Downarrow\)) value \(v\) and new state \(\xi'\)

We use the judgments as guidance to define the signature of the interpreter.

type Store = Map[I, Int]
type FunctionStore = Map[I, Expr]

// Evaluate expression
def eval(e: Expr, s: Store, f: FunctionStore): (Int, Store, FunctionStore) = e match

Integer Arithmetic

• Numbers
  • \(\frac{}{\langle\mathtt{n},\xi\rangle \Downarrow \langle n,\xi\rangle} \text{\tiny(Num)}\)
• Addition etc.
  • \(\frac{\begin{array}\ \langle \mathtt{e}_1,\xi_0 \rangle \Downarrow \langle v_1,\xi_1 \rangle ~~ \langle \mathtt{e}_2,\xi_1 \rangle \Downarrow \langle v_2,\xi_2 \rangle\end{array}}{\langle \mathtt{e}_1 \mathtt{+} \mathtt{e}_2,\xi_0\rangle \Downarrow \langle v_1 + v_2,\xi_2\rangle}\text{\tiny(Add)}, \ldots\)
• Parentheses
  • \(\frac{\langle\mathtt{e},\xi\rangle \Downarrow \langle v, \xi_1\rangle}{\langle\mathtt{(e)},\xi\rangle \Downarrow \langle v,\xi_1\rangle} \text{\tiny(Par)}\)

  case N(n)           => (n, s, f)
  
  case Plus(e1, e2)   => chain2(e1, e2, s, f, _ + _)    
  case Minus(e1, e2)  => chain2(e1, e2, s, f, _ - _)
  case Times(e1, e2)  => chain2(e1, e2, s, f, _ * _)
  
  case Par(e)         => eval(e, s, f)

Note that the common functionality of chaining the operator evaluation in addition, subtraction, and multiplication, is refactored into the higher-order function chain2 that is parameterized with the concrete operation (+,-,*).

def chain2(e1: Expr, e2: Expr, s: Store, f: FunctionStore, op: (Int,Int)=>Int) = 
  val (v1, s1, f1) = eval(e1, s, f)
  val (v2, s2, f2) = eval(e2, s1, f1)
  (op(v1,v2), s2, f2)
end chain2

Variables, Assignment, and Sequential Composition

• Variable lookup
  • \(\frac{}{\langle \mathtt{x},\xi \rangle \Downarrow \langle \xi(\mathtt{x}), \xi \rangle}\text{\tiny(Var)}\)
• Assignment
  • \(\frac{\langle \mathtt{e},\xi_0 \rangle \Downarrow \langle v,\xi_1 \rangle}{\langle \mathtt{x := e}, \xi_0 \rangle \Downarrow \langle v,\xi_1\{\mathtt{x} \mapsto v\} \rangle}\text{\tiny(:=)}\)
    
• Sequential expression composition
  • \(\frac{\begin{array}\ \langle \mathtt{e}_1, \xi_0 \rangle \Downarrow \langle v_1,\xi_1 \rangle \quad \langle \mathtt{e}_2, \xi_1 \rangle \Downarrow \langle v_2,\xi_2 \rangle \end{array}}{\langle \mathtt{e}_1 \mathtt{;} \mathtt{e}_2, \xi_0 \rangle \Downarrow \langle v_2,\xi_2 \rangle} \text{\tiny(;)}\)

  case x: I           => (s(x), s, f)
  
  case Assign(x, e)   =>
    val (v,s1,f1) = eval(e, s, f)
    (v, s1.updated(x,v), f1)

  case Seq(e1, e2)    => chain2(e1, e2, s, f, (_,v2)=>v2)

Comparison, Conditional, and Loop

• Comparison
  • \(\frac{\langle \mathtt{e}_1,\xi_0\rangle \Downarrow \langle v_1,\xi_1\rangle \quad \langle \mathtt{e}_2,\xi_1 \rangle \Downarrow \langle v_2,\xi_2\rangle}{\langle \mathtt{e}_1 \mathtt{>=} \mathtt{e}_2,\xi_0 \rangle \Downarrow \langle \max(0,v_1-v_2+1),\xi_2 \rangle}\text{\tiny(\(\geq\))}\)
• Conditional
  • \(\frac{\langle \mathtt{e}_1,\xi_0 \rangle \Downarrow \langle v_1,\xi_1 \rangle \quad v_1 \neq 0 \quad \langle \mathtt{e}_2,\xi_1 \rangle \Downarrow \langle v_2,\xi_2 \rangle}{\langle \mathtt{if}\ \mathtt{e}_1\ \mathtt{then}\ \mathtt{e}_2\ \mathtt{else}\ \mathtt{e}_3\ \mathtt{fi},\xi_0 \rangle \Downarrow \langle v_2,\xi_2 \rangle}\text{\tiny(iftrue)}\)
  • \(\frac{\langle \mathtt{e}_1,\xi_0 \rangle \Downarrow \langle v_1,\xi_1 \rangle \quad v_1 = 0 \quad \langle \mathtt{e}_3,\xi_1 \rangle \Downarrow \langle v_2,\xi_2 \rangle}{\langle \mathtt{if}\ \mathtt{e}_1\ \mathtt{then}\ \mathtt{e}_2\ \mathtt{else}\ \mathtt{e}_3\ \mathtt{fi},\xi_0 \rangle \Downarrow \langle v_2,\xi_2 \rangle}\text{\tiny(iffalse)}\)
• Loop
  • \(\frac{\langle \mathtt{e}_1,\xi_0 \rangle \Downarrow \langle v_1,\xi_1 \rangle \quad v_1 = 0}{\langle \mathtt{while}\ \mathtt{e}_1 \ \mathtt{do}\ \mathtt{e}_2\ \mathtt{od},\xi_0 \rangle \Downarrow \langle 0,\xi_1 \rangle} \text{\tiny(whileend)}\)
  • \(\frac{\begin{array}\ \langle \mathtt{e}_1,\xi_0 \rangle \Downarrow \langle v_1,\xi_1 \rangle \quad v_1 \neq 0 \quad \langle \mathtt{e}_2; \mathtt{while}\ \mathtt{e}_1 \ \mathtt{do}\ \mathtt{e}_2\ \mathtt{od},\xi_1 \rangle \Downarrow \langle v_2,\xi_2 \rangle \end{array}}{\langle \mathtt{while}\ \mathtt{e}_1 \ \mathtt{do}\ \mathtt{e}_2\ \mathtt{od}, \xi_0 \rangle \Downarrow \langle v_2,\xi_2 \rangle} \text{\tiny(whilerec)}\)

  case GEq(e1, e2)    => chain2(e1, e2, s, f, (v1,v2)=>math.max(0, v1-v2+1))    

  case If(e1, e2, e3) =>
    val (v1, s1, f1) = eval(e1, s, f)
    if v1!=0 
      then eval(e2, s1, f1)
      else eval(e3, s1, f1)

  case w@While(e1, e2)  =>
    val (v1, s1, f1) = eval(e1, s, f)
    if v1==0 
      then (0, s1, f1)
      else eval(Seq(e2, w), s1, f1)

Full Algebraic Data Type and Interpreter

/** Expressions */
enum Expr:
  // Arithmetic expressions
  case N(n:Int)
  case Plus(l:Expr, r:Expr)
  case Minus(l:Expr, r:Expr)
  case Times(l:Expr, r:Expr)

  // Parenthesized expressions (e)
  case Par(e:Expr)

  // Identifiers
  case I(n:String)

  // Comparisons l>=r
  case GEq(l:Expr, r:Expr)
  
  // Programs
  
  // Assignment x := v
  case Assign(x:I, v:Expr)

  // Sequential composition p ; r
  case Seq(p:Expr, r:Expr)  
  
  // Conditional if p then t else e
  case If(p:Expr, t:Expr, e:Expr)
  
  // Loop while p do b
  case While(p:Expr, b:Expr)

  // Function definition and application
  case FunctionDef(name: I, body: Expr)
  case FunctionApp(name: I)
end Expr

import Expr.*

type Store = Map[I, Int]
type FunctionStore = Map[I, Expr]

// Evaluate expression
def eval(e: Expr, s: Store, f: FunctionStore): (Int, Store, FunctionStore) = e match
  case N(n)           => (n, s, f)
  
  case Plus(e1, e2)   => chain2(e1, e2, s, f, _ + _)    
  case Minus(e1, e2)  => chain2(e1, e2, s, f, _ - _)
  case Times(e1, e2)  => chain2(e1, e2, s, f, _ * _)
  
  case Par(e)         => eval(e, s, f)
  case x: I           => (s(x), s, f)
  
  case Assign(x, e)   =>
    val (v,s1,f1) = eval(e, s, f)
    (v, s1.updated(x,v), f1)

  case Seq(e1, e2)    => chain2(e1, e2, s, f, (_,v2)=>v2)

  case GEq(e1, e2)    => chain2(e1, e2, s, f, (v1,v2)=>math.max(0, v1-v2+1))    

  case If(e1, e2, e3) =>
    val (v1, s1, f1) = eval(e1, s, f)
    if v1!=0 
      then eval(e2, s1, f1)
      else eval(e3, s1, f1)

  case w@While(e1, e2)  =>
    val (v1, s1, f1) = eval(e1, s, f)
    if v1==0 
      then (0, s1, f1)
      else eval(Seq(e2, w), s1, f1)

  case FunctionDef(n, e) => 
    (0, s, f.updated(n, e))
  case FunctionApp(n) => 
    // val e = f(n)
    // val (v, s1, f1) = eval(e, s, f)
    // (v, s1, f1)
    eval(f(n), s, f)
end eval

Examples of Using the Algebraic Data Type and Interpreter

Absolute value of a number:

// Absolute value of n: if n>=0 then n else 0-n
def abs(n: Expr) =
  If(
    GEq(n, N(0)),
    n,
    Minus(N(0), n)
  )
eval(abs(N(-2)), Map.empty, Map.empty)

Imperative factorial of a number:

// // Factorial n: i:=abs(n); f:=1; while(i>=1) do f:=f*i; i:=i-1 od; f
def fact(n: Int) =
  Seq(
    Assign(I("i"), abs(N(n))),
    Seq(
      Assign(I("f"), N(1)),
      Seq(
        While(
          GEq(I("i"), N(1)),
          Seq(
            Assign(I("f"), Times(I("f"), I("i"))),
            Assign(I("i"), Minus(I("i"), N(1)))
          )
        ),
        I("f")
      )

Recursive factorial of a number:

// Recursive factorial with global store
// n:=<n>; 
// def fact = if n>=1 then n*(n:=n-1;fact) else 1 fi; 
// fact()
def factRec(n: Int) =
  Seq(
    Assign(I("n"), N(n)),
    Seq(
      FunctionDef(
        I("fact"),
        If(
          GEq(I("n"), N(1)),
          Times(I("n"), Seq(
            Assign(I("n"), Minus(I("n"), N(1))), 
            FunctionApp(I("fact")))),
          N(1)
        )
      ),
      FunctionApp(I("fact"))      
    )
  )
eval(factRec(5), Map.empty, Map.empty)