Return to Answer

A lot of programming languages (PHP,C++0x,Java...) were just added lambda expression facilities recently.

However their lambda expression definitions usually does not allow direct recursion. But we can always do this:

1. Define a type WRAP that can

   a) Be constructed from a function closure receives a WRAP and returns an generic type. this is equivalent to the surjective condition.

   b) Be executed with another WRAP object and evaluate the function used to construct the object at this point. This is equivlent to a morphism $WRAP \to X^{WRAP}$

2. Now apply the trick garanteed by Lawvere's fixed point theorem, which says every function X -> X have a fixed point (of type X). Since we don't even know whether X have an accessable constructor, the only way we can construct such an X is by recursion. Implement a function that receive such a function and return the fixed point, now we obtained the Y combinator for the programming language.

See this code review post for an instance of how the above trick applies to C++1x.

A lot of programming languages (PHP,C++0x,Java...) were just added lambda expression facilities recently.

However their lambda expression definitions usually does not allow direct recursion. But we can always do this:

1. Define a type WRAP that can

   a) Be constructed from a function closure receives a WRAP and returns an generic type. this is equivalent to the surjective condition.

   b) Be executed with another WRAP object and evaluate the function used to construct the object at this point. This is equivlent to a morphism $WRAP \to X^{WRAP}$

2. Now apply the trick garanteed by Lawvere's fixed point theorem, which says every function X -> X have a fixed point (of type X). Since we don't even know whether X have an accessable constructor, the only way we can construct such an X is by recursion. Implement a function that receive such a function and return the fixed point, now we obtained the Y combinator for the programming language.

See this code review post for an instance of how the above trick applies to C++1x.

A lot of programming languages (PHP,C++0x,Java...) were just added lambda expression facilities recently.

However their lambda expression definitions usually does not allow direct recursion. But we can always do this:

1. Define a type WRAP that can

   a) Be constructed from a function closure receives a WRAP and returns an generic type. this is equivalent to the surjective condition.

   b) Be executed with another WRAP object and evaluate the function used to construct the object at this point. This is equivlent to a morphism $WRAP \to X^{WRAP}$

2. Now apply the trick garanteed by Lawvere's fixed point theorem, which says every function X -> X have a fixed point (of type X). Since we don't even know weather X have an accessable constructor, the only way we can construct such an X is by recursion. Implement a function that receive such a function and return the fixed point, now we obtained the Y combinator for the programming language.

See this code review post for an instance of how the above trick applies to C++1x.

A lot of programming languages (PHP,C++0x,Java...) were just added lambda expression facilities recently.

However their lambda expression definitions usually does not allow direct recursion. But we can always do this:

1. Define a type WRAP that can

   a) Be constructed from a function closure receives a WRAP and returns an generic type. this is equivalent to the surjective condition.

   b) Be executed with another WRAP object and evaluate the function used to construct the object at this point. This is equivlent to a morphism $WRAP \to X^{WRAP}$

2. Now apply the trick garanteed by Lawvere's fixed point theorem, which says every function X -> X have a fixed point (of type X). Since we don't even know whether X have an accessable constructor, the only way we can construct such an X is by recursion. Implement a function that receive such a function and return the fixed point, now we obtained the Y combinator for the programming language.

See this code review post for an instance of how the above trick applies to C++1x.

A lot of programming languages were just added lambda expression facilities recently.

However their lambda expression definitions usually does not allow direct recursion. But we can always do this:

1. Define a type WRAP that can

   a) Be constructed from a function closure receives a WRAP and returns an generic type. this is equivalent to the surjective condition.

   b) Be executed with another WRAP object and evaluate the function used to construct the object at this point. This is equivlent to a morphism $WRAP \to X^{WRAP}$

2. Now apply the trick garanteed by Lawvere's fixed point theorem, which says every function X -> X have a fixed point (of type X). Since we don't even know weather X have an accessable constructor, the only way we can construct such an X is by recursion. Implement a function that receive such a function and return the fixed point, now we obtained the Y combinator for the programming language.

See this code review post for an instance of how the above trick applies to C++1x.

A lot of programming languages (PHP,C++0x,Java...) were just added lambda expression facilities recently.

However their lambda expression definitions usually does not allow direct recursion. But we can always do this:

1. Define a type WRAP that can

   a) Be constructed from a function closure receives a WRAP and returns an generic type. this is equivalent to the surjective condition.

   b) Be executed with another WRAP object and evaluate the function used to construct the object at this point. This is equivlent to a morphism $WRAP \to X^{WRAP}$

2. Now apply the trick garanteed by Lawvere's fixed point theorem, which says every function X -> X have a fixed point (of type X). Since we don't even know weather X have an accessable constructor, the only way we can construct such an X is by recursion. Implement a function that receive such a function and return the fixed point, now we obtained the Y combinator for the programming language.

See this code review post for an instance of how the above trick applies to C++1x.