# 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.