## 03 April 2009

### WHY Java

Y in Java.

Y is a cute concept from lambda calculus. It's easy to define in Haskell.

y f = f (y f)
fact r 0 = 1
fact r n = n * r (n-1)
f = y fact


An execution of f 3 computes 3!:

f 3
= y fact 3
= fact (y fact) 3
= 3 * y fact 2
= 3 * fact (y fact) 2
= 3 * 2 * y fact 1
= 3 * 2 * fact (y fact) 1
= 3 * 2 * 1 * y fact 0
= 3 * 2 * 1 * 1


While showing this to Claudia I realized that I never coded Y in Java. It's interesting to see how long it is.

interface Fun { int go(int n); }
interface UntiedFun { int go(Fun f, int n); }

public class Rec {
public static void main(String[] args) {
System.out.println(f(10));
}

public static int fact(Fun f, int n) {
if (n == 0) return 1;
return n * f.go(n-1);
}

public static int Y(final UntiedFun f, int n) {
return f.go(new Fun() {
public int go(int n) { return Y(f, n); }
}, n);
}

public static int f(int n) {
return y(new UntiedFun() {
public int go(Fun f, int n) {return fact(f, n);}
}, n);
}
}


Great stuff you can do with recursion. Which reminds me: Did you figure out the last puzzle?