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)))

This is cheating but it works, in Arc:

[let f nil (= f (_ [f _])) f]

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!

works for me in ACL 8.1

Works for me. Using SBCL 1.0.14-gentoo on x86. Which common lisp runtime are you using?

And yeah... Lisp-2 is a stupid idea.

Please don't conclude that lisp-2 is a bad idea until you've considered that:

• there are disadvantages as well as advantages to lisp-1; and

• there is nothing about lisp-2-ness itself that requires the verbosity of (funcall #'…)-ing in Common Lisp:

Firstly, even in Common Lisp, (funcall (lambda …) …) and (funcall 'car list) are valid. (And many implementations allow ((lambda …) …) — though I can't remember whether the standard defines this.)

Secondly, funcall can be renamed something shorter (e.g. fun).

And finally, for those lispers not against a little syntax, a lisp-2 could define some syntax so that one could write, e.g. (#f …) for (funcall f …) and (##f …) for (funcall 'f …).

Then the above code would be:

  (defun Y (r)
    ((lambda (f) (#f f))
      (lambda (f)
        (#r (lambda (x)
              (fun (#f f) x))))))

etc.. (And we can make it even shorter if we call lambda something shorter, e.g. fn.)

Already have: http://www.nhplace.com/kent/Papers/Technical-Issues.html

Oops, messed my linux instance somehow. Works fine on the fresh instance of SBCL-x86-64 1.20.

As to Lisp-2, dude that's a debate that I don't want to get into. :) I'm just happy I can use any kind of Lisp -- the rest is just details.

Yarek

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

I'm not very literate in functional programming ... so excuse such a dumb question. But I'm curious why you write the recursing function duplicated? eg. isn't this version of your code equivalent?

    function Y(X) {
      var fn = function(procedure) {
        return X(function(arg) {
          return procedure(procedure)(arg);
        });
      };
      return fn(fn);
    }

Or am I missing something vital here about how it is all working? The shorter version seems clearer to me (not that any of this is clear to me), and functionally equivalent.

the duplication is to allow it to be anonymous. Your version names a function.

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?