Fibonacci Numbers: Dynamic Programming

A dynamic programming solution of fibonacci numbers.

import scala.collection.*
def fibonacci(n: Int, memo: mutable.Map[Int, Int] = mutable.Map()): Int = 
  if n <= 0 then return 0
  if n == 1 then return 1
  if memo.contains(n) then return memo(n)
  // Calculate Fibonacci and store in the map
  val result = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
  memo(n) = result
  result
end fibonacci

Since this method is not tail-recursive, the stack size can be exceeded (try fibonacci(45000)), resulting in a StackOverflowError.

Java Stack Limits

Change the stack limits of a Java virtual machine on startup:

java -Xss 10M MyApplication

Tail-Recursive or Not?

• Not recursive

  def f(x: Int, y: Int) : Int = 
    if (x>5) 
      then 1
      else 0

• Not tail-recursive

  def f(x: Int, y: Int) : Int = 
    val z = 5
    if (x>5) 
      then 1 + f(x-1, y)
      else 5

  def f(x: Int, y: Int) : Int = 
    val z = 5
    if (x>5) 
      then 1 + f(x-1, y)
      else f(x-2, y+1)

• Tail-recursive

  @scala.annotation.tailrec
  def f(x: Int, y: Int) : Int = 
    val z = 5
    if (x>5) 
      then f(x-1, y)
      else 5

  @scala.annotation.tailrec
  def f(x: Int, y: Int) : Int = 
    val z = 5
    if (x>5) 
      then f(x-1, y)
      else f(x-2, y+1)

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 Number(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 a,...,x,y,z
  case Ident(c:Char)

  // Comparisons l>=r
  case GEq(l:Expr, r:Expr)
  
  // Programs
  
  // Assignment x := v
  case Assign(x:Ident, 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)
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[Char, Int]

// Evaluate expression
def eval(e: Expr, s: Store): (Int, Store) = 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)}\)

def eval(e: Expr, s: Store): (Int, Store) = e match
  case Number(n)      => (n, s)
  case Plus(e1, e2)   => chain2(e1, e2, s, _ + _)
  case Minus(e1, e2)  => chain2(e1, e2, s, _ - _)
  case Times(e1, e2)  => chain2(e1, e2, s, _ * _)
  case Par(e)         => eval(e, s)

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, op: (Int, Int)=>Int) = 
  val (v1, s1) = eval(e1, s)
  val (v2, s2) = eval(e2, s1)
  (op(v1, v2), s2)
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 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)

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, (v1,v2)=>math.max(0,v1-v2+1))

  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)
end eval

Full Algebraic Data Type and Interpreter

/** Expressions */
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)

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

  // Identifiers a,...,x,y,z
  case Ident(c:Char)

  // Comparisons l>=r
  case GEq(l:Expr, r:Expr)
  
  // Programs
  
  // Assignment x := v
  case Assign(x:Ident, 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)
end Expr

import Expr.*

type Store = Map[Char, Int]

// Evaluate expression
def eval(e: Expr, s: Store): (Int, Store) = e match
  case Number(n)      => (n, s)
  case Plus(e1, e2)   => chain2(e1, e2, s, _ + _)
  case Minus(e1, e2)  => chain2(e1, e2, s, _ - _)
  case Times(e1, e2)  => chain2(e1, e2, s, _ * _)
  case Par(e)         => eval(e, s)
  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)

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

  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)
end eval

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

Examples of Using the Algebraic Data Type and Interpreter

Absolute value of a number:

// Absolute value of i
val abs = (n: Expr) =>
  Seq(
    Assign(Ident('i'), n),
    If(
      GEq(Ident('i'), Number(0)),
      Assign(Ident('i'), Ident('i')),
      Assign(Ident('i'), Minus(Number(0), Ident('i')))
    )
  )
eval(abs(Number(-2)), Map.empty)

Factorial of a number:

// Factorial n
val fact = (n: Int) =>
  Seq(
    Assign(Ident('n'), Number(n)),
    Seq(
      abs(Ident('n')),
      Seq(
        Assign(Ident('f'), Number(1)),
        While(
          Ident('i'),
          Seq(
            Assign(Ident('f'), Times(Ident('f'), Ident('i'))),
            Assign(Ident('i'), Minus(Ident('i'), Number(1)))
          )
        )
      )
    )
  )
eval(fact(-5), Map.empty)