Questions and Completion

There is nothing to hand in for the worksheet, but you should definitely work through it in order to prepare for the quiz and homework.

If you have questions as you go through this worksheet, please feel free to post them on the discussion forum.

Language Interpreter

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'
         | 'def' Ident '()' '=' 
              Expr
           'end'
         | Ident '()'

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

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)

Implement the sequential expression composition case.

Solution: Sequential Composition

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)

Implement the while loop:

  case w@While(e1, e2)  =>

Solution: While Loop

Function Definition and Application

For a basic first implementation of reducing code duplication, we allow functions with access to the global store (global variables, but no arguments and no local variables):

• \(\frac{}{\langle \mathtt{def\ f() = e\ end},\xi,\phi \rangle \Downarrow \langle 0,\xi,\phi\{\mathtt{f} \mapsto \mathtt{e}\} \rangle}\text{\tiny(FunDef)}\)

When functions are applied (invoked), the function body is looked up and evaluated:

• \(\frac{\phi(\mathtt{f})=e \quad \langle e,\xi,\phi \rangle \Downarrow \langle v,\xi',\phi' \rangle}{\langle \mathtt{f()},\xi,\phi \rangle \Downarrow \langle v,\xi',\phi' \rangle}\text{\tiny(FunApp)}\)

Note that this language semantics allows us to define functions in the body of other functions; they will be available globally once the outer function is invoked. Such a simple meaning of functions is rarely what we want in a programming language, and we will see later in this class how additional stores for local variables and local functions allow us to restrict the scope of our identifiers.

The interpreter case for function definition is listed below.

  case FunctionDef(n, e) => 
    (0, s, f.updated(n, e))

Implement function application:

  case FunctionApp(n) => 

Solution: Function Application

Programming with 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")
      )

Implement the 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) =

Solution: Recursive Factorial of a Number

Solutions

Solution: Sequential Composition

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

Solution: While Loop

  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)

Solution: Function Application

  case FunctionApp(n) => 
    // val e = f(n)
    // val (v, s1, f1) = eval(e, s, f)
    // (v, s1, f1)
    eval(f(n), s, f)

Solution: 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)

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

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