Ackermann's Function

By selectively specializing on a subset of the argument, we can turn a recursive function into an automaton, i.e. a set of mutually recursive functions.

Outline:

package scala.lms.tutorial

Ackermann's Function

We define Ackermann's function using a static first argument m and a dynamic second argument n. Our definition is also curried so that we can treat any partial static application as a function to specialize and re-use.

trait Ackermann extends Dsl {
  def a(m: Int): Rep[Int => Int] = fun { (n: Rep[Int]) =>
    generate_comment("ack_"+m) // to navigate the generated code
    if (m==0) n+1
    else if (n==0) a(m-1)(1)
    else a(m-1)(a(m)(n-1))
  }
}

Specialization

The example is due to Neil Jones, via Oleg Kiselyov on LtU.

The stated goal is to specialize Ackermann's function for m=2.

ack(2,n) should specialize to this tower of recursive functions:

ack_2(n) = if n=0 then ack_1(1) else ack_1(ack_2(n-1)) ack_1(n) = if n=0 then ack_0(1) else ack_0(ack_1(n-1)) ack_0(n) = n+1

class AckermannTest extends TutorialFunSuite {
  val under = "ack"
  def specialize(m: Int): DslDriver[Int,Int] = new DslDriver[Int,Int] with Ackermann {
    def snippet(n: Rep[Int]): Rep[Int] = a(m)(n)
  }

  test("specialize ackermann to m=2") {
    val ack2 = specialize(2)
    check("m2", ack2.code)
  }
}

Generated Code

The code generated by LMS matches the desired specialization.

/*****************************************
Emitting Generated Code
*******************************************/
class Snippet extends ((Int)=>(Int)) {
  def apply(x0:Int): Int = {
    var x5 = null.asInstanceOf[scala.Function1[Int, Int]]
    var x1 = null.asInstanceOf[scala.Function1[Int, Int]]
    val x9 = {x10: (Int) =>
      // ack_0
      val x12 = x10 + 1
      x12: Int
    }
    x5 = {x6: (Int) =>
      // ack_1
      val x8 = x6 == 0
      val x20 = if (x8) {
        val x14 = x9(1)
        x14
      } else {
        val x16 = x6 - 1
        val x17 = x5(x16)
        val x18 = x9(x17)
        x18
      }
      x20: Int
    }
    x1 = {x2: (Int) =>
      // ack_2
      val x4 = x2 == 0
      val x28 = if (x4) {
        val x22 = x5(1)
        x22
      } else {
        val x24 = x2 - 1
        val x25 = x1(x24)
        val x26 = x5(x25)
        x26
      }
      x28: Int
    }
    val x30 = x1(x0)
    x30
  }
}
/*****************************************
End of Generated Code
*******************************************/

What's next?

Go back to the tutorial index or continue with the Automata-Based Regex Matcher.

Comments? Suggestions for improvement? View this file on GitHub.