Sunday 24 August 2008

Tail calls don't exist - So why look for them?


import java.util.Stack;

interface Term { public Term whnf(); }
class Function implements Term { public Term whnf() { return this; } public Term apply(Term value) { System.out.println("Not implemented"); return null; } }

class Apply implements Term {
Term x, y;
boolean computed;
Term value;

public Apply(Term x, Term y) {
this.x = x;
this.y = y;
computed = false;
}

/* // This is the first version of whnf I wrote, it's buggy, it crashes with a stack overflow
public Term whnf() {
if(!computed) {
x = x.whnf();
if(x instanceof Constructor) {
value = ((Constructor)x).add(y);
}
else if(x instanceof Function) {
value = ((Function)x).apply(y);
value = value.whnf(); // this is the recursion in question, which causes it
}
else {
System.out.println("ERROR");
}
computed = true;
}
return value;
}*/


public Term whnf() {
while(true) { // the usual fix is to use one of javas many loop constructs instead of recursion
if(!computed) {
x = x.whnf();
if(x instanceof Constructor) {
value = ((Constructor)x).add(y);
}
else if(x instanceof Function) {
value = ((Function)x).apply(y);
if(value instanceof Apply) {
x = ((Apply)value).x;
y = ((Apply)value).y;
continue;
}
}
else {
System.out.println("ERROR");
}
computed = true;
}
return value;
}
}
}

class Constructor implements Term {
String name;
Term[] args;

public Constructor(String name, Term... args) {
this.name = name;
this.args = args;
}

public Term whnf() {
return this;
}

public Constructor add(Term t) {
int i; Term[] oldArgs = args;
args = new Term[oldArgs.length+1];
for(i = 0; i < oldArgs.length; i++)
args[i] = oldArgs[i];
args[i] = t;
return this;
}
}

class Add extends Function { public Term apply(Term value) { return new Add1(value); } }
class Add1 extends Function {
Term x;
public Add1(Term x) { this.x = x; }
public Term apply(Term y) {
x = x.whnf();
if(((Constructor)x).name == "Z") { return y; } // add Z y = y
else if(((Constructor)x).name == "S") { // add (S x) y = S (add x y)
return new Constructor("S", new Apply(new Apply(new Add(), ((Constructor)x).args[0]), y));
}
System.out.println("Pattern match fell through");
return null;
}
}

class Tail extends Function { public Term apply(Term value) { return ((Constructor)value.whnf()).args[1]; } }

class ZipWith extends Function { public Term apply(Term f) { return new ZipWith1(f); } }
class ZipWith1 extends Function { Term f; public ZipWith1(Term f) { this.f = f; } public Term apply(Term xs) { return new ZipWith2(f,xs); } }
class ZipWith2 extends Function {
Term f, xs;
public ZipWith2(Term f, Term xs) { this.f = f; this.xs = xs; }
public Term apply(Term ys) {
xs = xs.whnf();
if(((Constructor)xs).name == "[]") return ys; // zipWith f [] y = y
ys = ys.whnf();
if(((Constructor)ys).name == "[]") return xs; // zipWith f x [] = x
Term x = ((Constructor)xs).args[0]; Term y = ((Constructor)ys).args[0];
Term xss = ((Constructor)xs).args[1]; Term yss = ((Constructor)ys).args[1];
// zipWith f (x:xss) (y:yss) = f x y : zipWith f xss yss
return new Constructor(":", new Apply(new Apply(f,x), y), new Apply(new Apply(new Apply(new ZipWith(), f), xss), yss));
}
}

class F extends Function { public Term apply(Term x) { return new Apply(new F(), x); } }

interface Instruction { public void execute(Stack<Instruction> todo); }

class OpenBracket implements Instruction {
public void execute(Stack<Instruction> todo) {
System.out.print("(");
}
}

class CloseBracket implements Instruction {
public void execute(Stack<Instruction> todo) {
System.out.print(")");
}
}

class EvalTerm implements Instruction {
Term t;

public EvalTerm(Term t) {
this.t = t;
}

public void execute(Stack<Instruction> todo) {
Constructor c = (Constructor)t.whnf();
t = c;

System.out.print(c.name + " ");

todo.push(new CloseBracket());
for(int i = c.args.length-1; i >= 0; i--) {
todo.push(new EvalTerm(c.args[i]));
}
todo.push(new OpenBracket());
}
}

class Evaluator {
Stack<Instruction> todo;

public Evaluator(Term program) {
todo = new Stack<Instruction>();
todo.push(new EvalTerm(program));
}

public void evaluate() {
while(!todo.empty()) todo.pop().execute(todo);
}
}

public class NoTCO {
public static void main(String args[]) {
Term one = new Apply(new Constructor("S"), new Constructor("Z"));
Term two = new Apply(new Constructor("S"), new Apply(new Constructor("S"), new Constructor("Z")));
Term four = new Apply(new Constructor("S"), new Apply(new Constructor("S"), new Apply(new Constructor("S"), new Apply(new Constructor("S"), new Constructor("Z")))));

// 1 : 1 : zipWith (+) fibs (tail fibs)
Term fibs =
new Apply(new Apply(new Constructor(":"), one),
new Apply(new Apply(new Constructor(":"), one),
null));
((Apply)((Apply)fibs).y).y =
new Apply(new Apply(new Apply(new ZipWith(), new Add()), fibs), new Apply(new Tail(), fibs));

//new Evaluator(fibs).evaluate();
new Evaluator(new Apply(new F(), new Constructor("3"))).evaluate();
System.out.println();
}
}


// Important thing to note is,
// 1) This code does not analyze the input program to detect and 'optimize' tail recursion
// 2) This program doesn't stack overflow when evaluating a "tail recursive" program
//
// NB. I put "tail recursive" in quotes because it's actually irrelevant that the code is what you'd call in a strict language by that term
// as I said in my previous post, the reason it doesn't stack overflow is not at all related to that.



3 comments:

Unknown said...

You claim it's important that your code doesn't look for tail calls, and yet you've hand eliminated them so this claim rings false.

Your first version of whnf stack overflows because it does not eliminate tail calls. Replacing the function call ("recursion") with a goto ("loop") is exactly doing TCO. Since whnf is your evaluator it is the only thing meaningfully using the stack and so you've implemented TCO for all evaluations.

What do you think TCO means?

Muad`Dib said...

> Your first version of whnf stack overflows because it does not eliminate tail calls.
That is correct, if java had TCO I could write tail recursive methods and it would work fine.

> Since whnf is your evaluator it is the only thing meaningfully using the stack and so you've implemented TCO for all evaluations.
You're confusing the object language with the implementation language here. I've _not_ implemented TCO, and I don't have to. I wrote this code just to show that, and show why that is the case.

What perhaps wasn't noticed, but is crucial is this part:
x = ((Apply)value).x;
y = ((Apply)value).y;

When you lazy evaluate terms in a strict language you actually mutate the graph while you evaluate it. that's why something like let x = square 3 in x + x only calculates square 3 once, It's exactly this same process which lets you do loops without using up stack.

> What do you think TCO means?
I use this definition:
http://schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-6.html#%_sec_3.5
It should be blatantly clear that I have not implemented a tail call recognizer when you see the 'inductive' definition in that page.

Muad`Dib said...

(Just to elaborate a tiny bit on my answer to
> Your first version of whnf stack overflows because it does not eliminate tail calls.
If java had tail calls and we used that commented out version of Apply.whnf we would have non-strict evaluation but not lazy evaluation)