The Y Combinator in Arc and Java

It's nice to see such a rational comparison of languages. So often, I see blogs written by people who only understand one language and blindly compare its' elegant solutions to arcane versions in another language because they don't understand the other enough to recognize their blunder. This post, on the other hand, is written by somebody with a strong understanding of both languages and how to approach the same problem with two different hats.

So, rather than another "Lisp rocks, Java sucks" post, we get to read a intellectually sound argument. Refreshing.

See also: The Y Combinator in Scala http://scala-blogs.org/2008/09/y-combinator-in-scala.html

Recursive factorial computed entirely with anonymous functions in Python:

  >>> (lambda n: (lambda f, n: f(f, n))(
  ... lambda f, n: n*f(f, n-1) if n > 0 else 1,n)
  ... )(10)
  3628800

http://stackoverflow.com/questions/481692/can-a-lambda-funct...

Here's the java version extended to work for various input/output types (I also renamed some things to make the code clearer):

public class Z {

    public interface Function<In,Out> {
        public Out apply(In param);
    }

    public interface RecFunction<In,Out>
        extends Function<Function<In,Out>,Function<In,Out>> {
    }

    private interface FixBody<In,Out>
        extends Function<FixBody<In,Out>,Function<In,Out>> {
    }

    public static <In,Out> Function<In,Out> fix(final RecFunction<In,Out> r) {
        return (new Function<FixBody<In,Out>,Function<In,Out>>() {
                public Function<In,Out> apply(FixBody<In,Out> f) {
                    return f.apply(f);
                }
            }).apply(new FixBody<In,Out>() {
                    public Function<In,Out> apply(final FixBody<In,Out> f) {
                        return r.apply(
                                new Function<In,Out>() {
                                    public Out apply(In x) {
                                        return f.apply(f).apply(x);
                                    }
				});
                    }
		});
    }

    public static final RecFunction<Integer,Integer> fact =
	new RecFunction<Integer,Integer>() {
	public Function<Integer,Integer> apply(
		final Function<Integer,Integer> self) {
            return new Function<Integer,Integer>() {
		public Integer apply(Integer n) {
                    if (n == 0)
			return 1;
                    else
                        return n * self.apply(n-1);
		}
            };
	}
    };

    public static void main(String[] args) {
	Function<Integer,Integer> factorial = fix(fact);
	for (int i = 0; i < 10; i++) {
            System.out.println("Factorial " + i + ": " + factorial.apply(i));
	}
    }
}

I'd wager that Io has the shortest:

block(x, if(x == 0, 1, x * call activated call(x - 1)))

I've tried to create Y combinator in common-lisp, but I get errors with this:

-----------------

(defun Y (r) (funcall #'(lambda (f) (funcall f f)) #'(lambda (f) (funcall r #'(lambda (x) (funcall (funcall f f) x))))))

(defun fact-gen (fact-in) #'(lambda (n) (if (eq n 0) 1 (* n (funcall fact-in (- n 1))))))

(funcall (Y #'fact-gen) 1)

----------------- Any suggestions? Thanks!

Y combinator in JavaScript: http://thraxil.org/users/anders/posts/2008/09/15/My-Own-Java...

http://agent101.livejournal.com/5601.html <-- A ycombinator in Php. It can be done in 5.3, pretty it isn't.

Somebody, please, kill the author of that article!

If you are green, then you should think about effectiveness of your code. I mean, how much watts your code will use. Ideal program should produce result without using of any computation at all. Programs with lazy evaluation is very close to that ideal. Y Combinator is very green in such languages. But Y Combinator in call-by-value languages? Code, which produces code, to run code, which produces new code, to run code, which produces new code, ...? Author want to boil our planet?