Language Constructs

• Integer expressions
• Statements
  • Assignment
  • Statement lists
  • Conditional
  • Loop

Example Program: Factorial

n := -5;
if n>=0
  then i := n 
  else i := 0-n
fi;
f := 1;
while i do
  f := f * i;
  i := i-1
od

Syntax

Expr ::= Number
       | Expr '+' Expr 
       | Expr '-' Expr 
       | Expr '*' Expr 
       | '(' Expr ')'

Example

2+3*4
(2+3) * 4

enum Expr:
  // Arithmetic expressions
  case Number(n:Int)
  case Plus(l:Expr, r:Expr)
  case Minus(l:Expr, r:Expr)
  case Times(l:Expr, r:Expr)
  // Identifiers a,...,x,y,z
  case Ident(c:Char)
  // Parenthesized expressions (e)
  case Par(e:Expr)

• Integer expression as an abstract syntax tree: 2+3*x

val expr = 
  Plus(
    Number(2),
    Times(Number(3), Ident('x'))
  )  

• Numbers
  
• Addition etc.
  
• Parentheses
  

def eval(e: Expr, s: Store): (Int, Store) = e match
  case Number(n)      => (n, s)
  case Plus(e1, e2)   => 
    val (v1, s1) = eval(e1, s)
    val (v2, s2) = eval(e2, s1)
    (v1+v2, s2)
  
  ...
  
  case Par(e)         => eval(e, s)

Syntax

Expr   ::= Number
         | Expr '+' Expr 
         | Expr '-' Expr 
         | Expr '*' Expr 
         | Ident
         | PrgSeq
         | '(' Expr ')'         
Ident  ::= 'a' | 'b' | ... | 'z'
PrgSeq ::= Prg | Prg ';' PrgSeq
Prg    ::= Ident ':=' Expr

Example

a := 2+3;
b := (a:=a+1)*4;
a := b-5

enum Expr:
  // Arithmetic expressions
  case Number(n:Int)
  case Plus(l:Expr, r:Expr)
  case Minus(l:Expr, r:Expr)
  case Times(l:Expr, r:Expr)
  // Identifiers a,...,x,y,z
  case Ident(c:Char)
  // Parenthesized expressions (e)
  case Par(e:Expr)

  // Programs
  // Assignment x := v
  case Assign(x:Ident, v:Expr)
  
  // Sequential composition p ; r
  case Seq(p:Expr, r:Expr)
end Expr

• Variable lookup
  
• Assignment
  
• Sequential expression composition
  

def eval(e: Expr, s: Store): (Int, Store) = e match
  ...
  case Ident(c)       => (s(c), s)
  
  case Assign(Ident(x), e)   =>
    val (v,s1) = eval(e, s)
    (v, s1.updated(x,v))
  
  case Seq(e1, e2)    =>
    val (v1, s1) = eval(e1, s)
    val (v2, s2) = eval(e2, s1)
    (v2, s2)

Syntax

Expr   ::= Number
         | Expr '+' Expr 
         | Expr '-' Expr 
         | Expr '*' Expr
         | Ident
         | Expr '>=' Expr
         | PrgSeq
         | '(' Expr ')'         
Ident  ::= 'a' | 'b' | ... | 'z'
PrgSeq ::= Prg | Prg ';' PrgSeq
Prg    ::= Ident ':=' Expr
         | 'if' Expr 
              'then' Expr 
              'else' Expr 'fi'
         | 'while' Expr 'do' 
              Expr 
           'od'

enum Expr:
  // Arithmetic expressions
  case Number(n:Int)
  case Plus(l:Expr, r:Expr)
  case Minus(l:Expr, r:Expr)
  case Times(l:Expr, r:Expr)
  // Identifiers a,...,x,y,z
  case Ident(c:Char)
  // Comparisons l>=r
  case GEq(l:Expr, r:Expr)
  
  // Parenthesized expressions (e)
  case Par(e:Expr)

  // Programs
  // Assignment x := v
  case Assign(x:Ident, v: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)
  
  // Sequential composition p ; r
  case Seq(p:Expr, r:Expr)
end Expr

Reduction rules for conditionals and loops

• Comparison
  
  
  
• Conditional
  
  
  
  
• Loop
  
  

def eval(e: Expr, s: Store): (Int, Store) = e match
  ...
  case GEq(e1, e2)    => 
    val (v1, s1) = eval(e1, s)
    val (v2, s2) = eval(e2, s1)
    (math.max(0,v1-v2+1), s2)    
    
  case If(e1, e2, e3) =>
    val (v1, s1) = eval(e1, s)
    if v1!=0 
      then eval(e2, s1)
      else eval(e3, s1)
  case w@While(e1, e2)  =>
    val (v1, s1) = eval(e1, s)
    if v1==0 
      then (0, s1)
      else eval(Seq(e2, w), s1)