4 ms·

The Y Combinator in Arc and Java

57 points by wheels 18y ago

jorgeortiz85 18y ago
See also: The Y Combinator in Scala http://scala-blogs.org/2008/09/y-combinator-in-scala.html http://scala-blogs.org/2008/09/y-combinator-in-scala.html
richcollins 18y ago
I'd wager that Io has the shortest: block(x, if(x == 0, 1, x * call activated call(x - 1)))
- dreish 18y ago
  This is cheating but it works, in Arc: [let f nil (= f (_ [f _])) f]
yarek 18y ago
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!
- newt0311 18y ago
  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.
  - yarek 18y ago
    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
  - parenthesis 18y ago
    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.)
    - newt0311 18y ago
      Already have: http://www.nhplace.com/kent/Papers/Technical-Issues.html http://www.nhplace.com/kent/Papers/Technical-Issues.html
- jockc 18y ago
  works for me in ACL 8.1
caustic 18y ago
Y combinator in JavaScript: http://thraxil.org/users/anders/posts/2008/09/15/My-Own-Javascript-Y-Combinator/ http://thraxil.org/users/anders/posts/2008/09/15/My-Own-Java...
- zmimon 18y ago
  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.
  - Avshalom 18y ago
    the duplication is to allow it to be anonymous. Your version names a function.
Agent101 18y ago
http://agent101.livejournal.com/5601.html http://agent101.livejournal.com/5601.html <-- A ycombinator in Php. It can be done in 5.3, pretty it isn't.
RWilson 18y ago
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.
procrastitron 18y ago
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)); } } }
d0mine 18y ago
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-function-call-itself-recursively-in-python http://stackoverflow.com/questions/481692/can-a-lambda-funct...
vlisivka 18y ago
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?

57 points by wheels 18y ago

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

richcollins 18y ago

I'd wager that Io has the shortest: block(x, if(x == 0, 1, x * call activated call(x - 1)))

dreish 18y ago
This is cheating but it works, in Arc: [let f nil (= f (_ [f _])) f]

yarek 18y ago

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!

newt0311 18y ago
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.
- yarek 18y ago
  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
- parenthesis 18y ago
  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.)
  - newt0311 18y ago
    Already have: http://www.nhplace.com/kent/Papers/Technical-Issues.html http://www.nhplace.com/kent/Papers/Technical-Issues.html
jockc 18y ago
works for me in ACL 8.1

caustic 18y ago

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

zmimon 18y ago
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.
- Avshalom 18y ago
  the duplication is to allow it to be anonymous. Your version names a function.

Agent101 18y ago

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

RWilson 18y ago

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.

procrastitron 18y ago

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

d0mine 18y ago

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-function-call-itself-recursively-in-python http://stackoverflow.com/questions/481692/can-a-lambda-funct...

vlisivka 18y ago

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?