# Y combinator

Y combinator
You are encouraged to solve this task according to the task description, using any language you may know.

In strict functional programming and the lambda calculus, functions (lambda expressions) don't have state and are only allowed to refer to arguments of enclosing functions. This rules out the usual definition of a recursive function wherein a function is associated with the state of a variable and this variable's state is used in the body of the function.

The Y combinator is itself a stateless function that, when applied to another stateless function, returns a recursive version of the function. The Y combinator is the simplest of the class of such functions, called fixed-point combinators.

Define the stateless Y combinator and use it to compute factorials and Fibonacci numbers from other stateless functions or lambda expressions.

Cf

## ALGOL 68

Translation of: Python
Note: This specimen retains the original Python coding style.
Works with: ALGOL 68S version from Amsterdam Compiler Kit ( Guido van Rossum's teething ring) with runtime scope checking turned off.
BEGIN  MODE F = PROC(INT)INT;  MODE Y = PROC(Y)F; # compare python Y = lambda f: (lambda x: x(x)) (lambda y: f( lambda *args: y(y)(*args)))#  PROC y =      (PROC(F)F f)F: (  (Y x)F: x(x)) (  (Y z)F: f((INT arg )INT: z(z)( arg )));   PROC fib = (F f)F: (INT n)INT: CASE n IN n,n OUT f(n-1) + f(n-2) ESAC;   FOR i TO 10 DO print(y(fib)(i)) ODEND

## AppleScript

AppleScript is not particularly "functional" friendly. It can, however, support the Y combinator.

AppleScript does not have anonymous functions, but it does have anonymous objects. The code below implements the latter with the former (using a handler (i.e. function) named 'lambda' in each anonymous object).

Unfortunately, an anonymous object can only be created in its own statement ('script'...'end script' can not be in an expression). Thus, we have to apply Y to the automatic 'result' variable that holds the value of the previous statement.

The identifier used for Y uses "pipe quoting" to make it obviously distinct from the y used inside the definition.

-- Y COMBINATOR --------------------------------------------------------------- on |Y|(f)    script        on |λ|(y)            script                on |λ|(x)                    y's |λ|(y)'s |λ|(x)                end |λ|            end script             f's |λ|(result)        end |λ|    end script     result's |λ|(result)end |Y|  -- TEST -----------------------------------------------------------------------on run     -- Factorial    script fact        on |λ|(f)            script                on |λ|(n)                    if n = 0 then return 1                    n * (f's |λ|(n - 1))                end |λ|            end script        end |λ|    end script      -- Fibonacci    script fib        on |λ|(f)            script                on |λ|(n)                    if n = 0 then return 0                    if n = 1 then return 1                    (f's |λ|(n - 2)) + (f's |λ|(n - 1))                end |λ|            end script        end |λ|    end script     {facts:map(|Y|(fact), enumFromTo(0, 11)), fibs:map(|Y|(fib), enumFromTo(0, 20))}     --> {facts:{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800},      --> fibs:{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,     --           1597, 2584, 4181, 6765}}  end run  -- GENERIC FUNCTIONS FOR TEST ------------------------------------------------- -- map :: (a -> b) -> [a] -> [b]on map(f, xs)    tell mReturn(f)        set lng to length of xs        set lst to {}        repeat with i from 1 to lng            set end of lst to |λ|(item i of xs, i, xs)        end repeat        return lst    end tellend map -- enumFromTo :: Int -> Int -> [Int]on enumFromTo(m, n)    if n < m then        set d to -1    else        set d to 1    end if    set lst to {}    repeat with i from m to n by d        set end of lst to i    end repeat    return lstend enumFromTo -- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Scripton mReturn(f)    if class of f is script then        f    else        script            property |λ| : f        end script    end ifend mReturn
Output:
{facts:{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800}, fibs:{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765}}

 (* ****** ****** *)//#include "share/atspre_staload.hats"//(* ****** ****** *)//funmyfix{a:type}( f: lazy(a) -<cloref1> a) : lazy(a) = $delay(f(myfix(f)))//valfact =myfix{int-<cloref1>int}(lam(ff) => lam(x) => if x > 0 then x * !ff(x-1) else 1)(* ****** ****** *)//implement main0 () = println! ("fact(10) = ", !fact(10))//(* ****** ****** *)  ## BlitzMax BlitzMax doesn't support anonymous functions or classes, so everything needs to be explicitly named. SuperStrict 'Boxed type so we can just use object arrays for argument listsType Integer Field val:Int Function Make:Integer(_val:Int) Local i:Integer = New Integer i.val = _val Return i End FunctionEnd Type 'Higher-order function type - just a procedure attached to a scopeType Func Abstract Method apply:Object(args:Object[]) AbstractEnd Type 'Function definitions - extend with fields as locals and implement apply as bodyType Scope Extends Func Abstract Field env:Scope 'Constructor - bind an environment to a procedure Function lambda:Scope(env:Scope) Abstract Method _init:Scope(_env:Scope) 'Helper to keep constructors small env = _env ; Return Self End MethodEnd Type 'Based on the following definition:'(define (Y f)' (let ((_r (lambda (r) (f (lambda a (apply (r r) a))))))' (_r _r))) 'Y (outer)Type Y Extends Scope Field f:Func 'Parameter - gets closed over Function lambda:Scope(env:Scope) 'Necessary due to highly limited constructor syntax Return (New Y)._init(env) End Function Method apply:Func(args:Object[]) f = Func(args) Local _r:Func = YInner1.lambda(Self) Return Func(_r.apply([_r])) End MethodEnd Type 'First lambda within YType YInner1 Extends Scope Field r:Func 'Parameter - gets closed over Function lambda:Scope(env:Scope) Return (New YInner1)._init(env) End Function Method apply:Func(args:Object[]) r = Func(args) Return Func(Y(env).f.apply([YInner2.lambda(Self)])) End MethodEnd Type 'Second lambda within YType YInner2 Extends Scope Field a:Object[] 'Parameter - not really needed, but good for clarity Function lambda:Scope(env:Scope) Return (New YInner2)._init(env) End Function Method apply:Object(args:Object[]) a = args Local r:Func = YInner1(env).r Return Func(r.apply([r])).apply(a) End MethodEnd Type 'Based on the following definition:'(define fac (Y (lambda (f)' (lambda (x)' (if (<= x 0) 1 (* x (f (- x 1))))))) Type FacL1 Extends Scope Field f:Func 'Parameter - gets closed over Function lambda:Scope(env:Scope) Return (New FacL1)._init(env) End Function Method apply:Object(args:Object[]) f = Func(args) Return FacL2.lambda(Self) End MethodEnd Type Type FacL2 Extends Scope Function lambda:Scope(env:Scope) Return (New FacL2)._init(env) End Function Method apply:Object(args:Object[]) Local x:Int = Integer(args).val If x <= 0 Then Return Integer.Make(1) ; Else Return Integer.Make(x * Integer(FacL1(env).f.apply([Integer.Make(x - 1)])).val) End MethodEnd Type 'Based on the following definition:'(define fib (Y (lambda (f)' (lambda (x)' (if (< x 2) x (+ (f (- x 1)) (f (- x 2))))))) Type FibL1 Extends Scope Field f:Func 'Parameter - gets closed over Function lambda:Scope(env:Scope) Return (New FibL1)._init(env) End Function Method apply:Object(args:Object[]) f = Func(args) Return FibL2.lambda(Self) End MethodEnd Type Type FibL2 Extends Scope Function lambda:Scope(env:Scope) Return (New FibL2)._init(env) End Function Method apply:Object(args:Object[]) Local x:Int = Integer(args).val If x < 2 Return Integer.Make(x) Else Local f:Func = FibL1(env).f Local x1:Int = Integer(f.apply([Integer.Make(x - 1)])).val Local x2:Int = Integer(f.apply([Integer.Make(x - 2)])).val Return Integer.Make(x1 + x2) EndIf End MethodEnd Type 'Now testLocal _Y:Func = Y.lambda(Null) Local fac:Func = Func(_Y.apply([FacL1.lambda(Null)]))Print Integer(fac.apply([Integer.Make(10)])).val Local fib:Func = Func(_Y.apply([FibL1.lambda(Null)]))Print Integer(fib.apply([Integer.Make(10)])).val ## Bracmat The lambda abstraction  (λx.x)y translates to  /('(x.$x))$y in Bracmat code. Likewise, the fixed point combinator Y := λg.(λx.g (x x)) (λx.g (x x)) the factorial G := λr. λn.(1, if n = 0; else n × (r (n−1))) the Fibonacci function H := λr. λn.(1, if n = 1 or n = 2; else (r (n−1)) + (r (n−2))) and the calls (Y G) i and (Y H) i where i varies between 1 and 10, are translated into Bracmat as shown below ( ( Y = /( ' ( g . /('(x.$g'($x'$x)))           $/('(x.$g'($x'$x)))         )       )    )  & ( G    = /(       ' ( r         . /(            ' ( n              .   $n:~>0&1 |$n*($r)$($n+-1) ) ) ) ) ) & ( H = /( ' ( r . /( ' ( n .$n:(1|2)&1                | ($r)$($n+-1)+($r)$($n+-2)              )            )         )       )    )  & 0:?i  &   whl    ' ( 1+!i:~>10:?i      & out$(str$(!i "!=" (!Y$!G)$!i))      )  & 0:?i  &   whl    ' ( 1+!i:~>10:?i      & out$(str$("fib(" !i ")=" (!Y$!H)$!i))      )  &)
Output:
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
fib(1)=1
fib(2)=1
fib(3)=2
fib(4)=3
fib(5)=5
fib(6)=8
fib(7)=13
fib(8)=21
fib(9)=34
fib(10)=55

## C

C doesn't have first class functions, so we demote everything to second class to match.
#include <stdio.h>#include <stdlib.h> /* func: our one and only data type; it holds either a pointer to   a function call, or an integer.  Also carry a func pointer to   a potential parameter, to simulate closure                   */typedef struct func_t *func;typedef struct func_t {        func (*fn) (func, func);        func _;        int num;} func_t; func new(func(*f)(func, func), func _) {        func x = malloc(sizeof(func_t));        x->fn = f;        x->_ = _;       /* closure, sort of */        x->num = 0;        return x;} func call(func f, func n) {        return f->fn(f, n);} func Y(func(*f)(func, func)) {        func g = new(f, 0);        g->_ = g;        return g;} func num(int n) {        func x = new(0, 0);        x->num = n;        return x;}  func fac(func self, func n) {        int nn = n->num;        return nn > 1   ? num(nn * call(self->_, num(nn - 1))->num)                        : num(1);} func fib(func self, func n) {        int nn = n->num;        return nn > 1                ? num(  call(self->_, num(nn - 1))->num +                        call(self->_, num(nn - 2))->num )                : num(1);} void show(func n) { printf(" %d", n->num); } int main() {        int i;        func f = Y(fac);        printf("fac: ");        for (i = 1; i < 10; i++)                show( call(f, num(i)) );        printf("\n");         f = Y(fib);        printf("fib: ");        for (i = 1; i < 10; i++)                show( call(f, num(i)) );        printf("\n");         return 0;}
Output:
fac:  1 2 6 24 120 720 5040 40320 362880
fib:  1 2 3 5 8 13 21 34 55

## C#

using System; static class YCombinator<T> {  delegate Func<T, T> Recursive(Recursive recursive);  public static Func<Func<Func<T, T>, Func<T, T>>, Func<T, T>> Fix =    f => ((Recursive)(g =>        (f(x => g(g)(x)))))((Recursive)(g => f(x => g(g)(x))));} class Program {  static Func<int, int> fac =    YCombinator<int>.Fix(f => x => x < 2 ? 1 : x * f(x - 1));  static Func<int, int> fib =    YCombinator<int>.Fix(f => x => x < 2 ? x : f(x - 1) + f(x - 2));   static void Main() {    Console.WriteLine(fac(10));    Console.WriteLine(fib(10));  }}
Output:
3628800
55

## C++

Works with: C++11

Known to work with GCC 4.7.2. Compile with

g++ --std=c++11 ycomb.cc

#include <iostream>#include <functional> template <typename F>struct RecursiveFunc {	std::function<F(RecursiveFunc)> o;}; template <typename A, typename B>std::function<B(A)> Y (std::function<std::function<B(A)>(std::function<B(A)>)> f) {	RecursiveFunc<std::function<B(A)>> r = {		std::function<std::function<B(A)>(RecursiveFunc<std::function<B(A)>>)>([f](RecursiveFunc<std::function<B(A)>> w) {			return f(std::function<B(A)>([w](A x) {				return w.o(w)(x);			}));		})	};	return r.o(r);} typedef std::function<int(int)> Func;typedef std::function<Func(Func)> FuncFunc;FuncFunc almost_fac = [](Func f) {	return Func([f](int n) {		if (n <= 1) return 1;		return n * f(n - 1);	});}; FuncFunc almost_fib = [](Func f) {	return Func([f](int n) {	 	if (n <= 2) return 1;		return  f(n - 1) + f(n - 2);	});}; int main() {	auto fib = Y(almost_fib);	auto fac = Y(almost_fac);	std::cout << "fib(10) = " << fib(10) << std::endl;	std::cout << "fac(10) = " << fac(10) << std::endl;	return 0;}
Output:
fib(10) = 55
fac(10) = 3628800

Works with: C++14

A shorter version, taking advantage of generic lambdas. Known to work with GCC 5.2.0, but likely some earlier versions as well. Compile with

g++ --std=c++14 ycomb.cc

#include <iostream>#include <functional>int main () {  auto y = ([] (auto f) { return              ([] (auto x) { return x (x); }                 ([=] (auto y) -> std:: function <int (int)> { return                    f ([=] (auto a) { return                          (y (y)) (a) ;});}));});   auto almost_fib = [] (auto f) { return                       [=] (auto n) { return                         n < 2? n: f (n - 1) + f (n - 2) ;};};  auto almost_fac = [] (auto f) { return                        [=] (auto n) { return                          n <= 1? n: n * f (n - 1); };};   auto fib = y (almost_fib);  auto fac = y (almost_fac);  std:: cout << fib (10) << '\n'              << fac (10) << '\n';}
Output:
fib(10) = 55
fac(10) = 3628800


The usual version using recursion, disallowed by the task:

template <typename A, typename B>std::function<B(A)> Y (std::function<std::function<B(A)>(std::function<B(A)>)> f) {	return [f](A x) {		return f(Y(f))(x);	};}

Another version which is disallowed because a function passes itself, which is also a kind of recursion:

template <typename A, typename B>struct YFunctor {  const std::function<std::function<B(A)>(std::function<B(A)>)> f;  YFunctor(std::function<std::function<B(A)>(std::function<B(A)>)> _f) : f(_f) {}  B operator()(A x) const {    return f(*this)(x);  }}; template <typename A, typename B>std::function<B(A)> Y (std::function<std::function<B(A)>(std::function<B(A)>)> f) {  return YFunctor<A,B>(f);}

## Ceylon

Using a class for the recursive type:

Result(*Args) y1<Result,Args>(        Result(*Args)(Result(*Args)) f)        given Args satisfies Anything[] {     class RecursiveFunction(o) {        shared Result(*Args)(RecursiveFunction) o;    }     value r = RecursiveFunction((RecursiveFunction w)        =>  f(flatten((Args args) => w.o(w)(*args))));     return r.o(r);} value factorialY1 = y1((Integer(Integer) fact)(Integer x)    =>  if (x > 1) then x * fact(x - 1) else 1); value fibY1 = y1((Integer(Integer) fib)(Integer x)    =>  if (x > 2) then fib(x - 1) + fib(x - 2) else 2); print(factorialY1(10)); // 3628800print(fibY1(10));       // 110

Using Anything to erase the function type:

Result(*Args) y2<Result,Args>(        Result(*Args)(Result(*Args)) f)        given Args satisfies Anything[] {     function r(Anything w) {        assert (is Result(*Args)(Anything) w);        return f(flatten((Args args) => w(w)(*args)));    }     return r(r);}

Using recursion, this does not satisfy the task requirements, but is included here for illustrative purposes:

Result(*Args) y3<Result, Args>(        Result(*Args)(Result(*Args)) f)        given Args satisfies Anything[]    =>  flatten((Args args) => f(y3(f))(*args));

## Clojure

(defn Y [f]  ((fn [x] (x x))   (fn [x]     (f (fn [& args]          (apply (x x) args)))))) (def fac     (fn [f]       (fn [n]         (if (zero? n) 1 (* n (f (dec n))))))) (def fib     (fn [f]       (fn [n]         (condp = n           0 0           1 1           (+ (f (dec n))              (f (dec (dec n))))))))
Output:
user> ((Y fac) 10)
3628800
user> ((Y fib) 10)
55

Y can be written slightly more concisely via syntax sugar:

(defn Y [f]  (#(% %) #(f (fn [& args] (apply (% %) args)))))

## Common Lisp

(defun Y (f)  ((lambda (g) (funcall g g))   (lambda (g)     (funcall f (lambda (&rest a)		  (apply (funcall g g) a)))))) (defun fac (n)  (funcall   (Y (lambda (f)       (lambda (n)         (if (zerop n)	   1	   (* n (funcall f (1- n)))))))   n)) (defun fib (n)  (funcall   (Y (lambda (f)       (lambda (n a b)         (if (< n 1)           a           (funcall f (1- n) b (+ a b))))))   n 0 1)) ? (mapcar #'fac '(1 2 3 4 5 6 7 8 9 10))(1 2 6 24 120 720 5040 40320 362880 3628800)) ? (mapcar #'fib '(1 2 3 4 5 6 7 8 9 10))(1 1 2 3 5 8 13 21 34 55)

## CoffeeScript

Y = (f) -> g = f( (t...) -> g(t...) )

or

Y = (f) -> ((h)->h(h))((h)->f((t...)->h(h)(t...)))
fac = Y( (f) -> (n) -> if n > 1 then n * f(n-1) else 1 )fib = Y( (f) -> (n) -> if n > 1 then f(n-1) + f(n-2) else n )

## D

A stateless generic Y combinator:

import std.stdio, std.traits, std.algorithm, std.range; auto Y(S, T...)(S delegate(T) delegate(S delegate(T)) f) {    static struct F {        S delegate(T) delegate(F) f;        alias f this;    }    return (x => x(x))(F(x => f((T v) => x(x)(v))));} void main() { // Demo code:    auto factorial = Y((int delegate(int) self) =>        (int n) => 0 == n ? 1 : n * self(n - 1)    );     auto ackermann = Y((ulong delegate(ulong, ulong) self) =>        (ulong m, ulong n) {            if (m == 0) return n + 1;            if (n == 0) return self(m - 1, 1);            return self(m - 1, self(m, n - 1));    });     writeln("factorial: ", 10.iota.map!factorial);    writeln("ackermann(3, 5): ", ackermann(3, 5));}
Output:
factorial: [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
ackermann(3, 5): 253

## Déjà Vu

Translation of: Python
Y f:	labda y:		labda:			call y @y		f	labda x:		x @x	call labda f:	labda n:		if < 1 n:			* n f -- n		else:			1set :fac Y labda f:	labda n:		if < 1 n:			+ f - n 2 f -- n		else:			1set :fib Y !. fac 6!. fib 6
Output:
720
13

## Delphi

May work with Delphi 2009 and 2010 too.

Translation of: C++

(The translation is not literal; e.g. the function argument type is left unspecified to increase generality.)

YX=. (1 :'('':''<@;(1;~":0)<@;<@((":0)&;))u')($:)(:6) ### Tacit version The Y combinator can be implemented indirectly using, for example, the linear representations of verbs (Y becomes a wrapper which takes an ad hoc verb as an argument and serializes it; the underlying self-referring system interprets the serialized representation of a verb as the corresponding verb): Y=. ((((&>)/)((((^:_1)b.)((<'0';_1)))(:6)))(&([ 128!:2 ,&<))) The factorial and Fibonacci examples:  u=. [ NB. Function (left) n=. ] NB. Argument (right) sr=. [ apply f. ,&< NB. Self referring fac=. (1:(n * u sr n - 1:)) @. (0 < n) fac f. Y 103628800 Fib=. ((u sr n - 2:) + u sr n - 1:) ^: (1 < n) Fib f. Y 1055 The stateless functions are shown next (the f. adverb replaces all embedded names by its referents):  fac f. Y NB. Factorial...'1:(] * [ ([ 128!:2 ,&<) ] - 1:)@.(0 < ])&>/'&([ 128!:2 ,&<) fac f. NB. Factorial step...1:(] * [ ([ 128!:2 ,&<) ] - 1:)@.(0 < ]) Fib f. Y NB. Fibonacci...'(([ ([ 128!:2 ,&<) ] - 2:) + [ ([ 128!:2 ,&<) ] - 1:)^:(1 < ])&>/'&([ 128!:2 ,&<) Fib f. NB. Fibonacci step...(([ ([ 128!:2 ,&<) ] - 2:) + [ ([ 128!:2 ,&<) ] - 1:)^:(1 < ]) A structured derivation of Y follows:  sr=. [ apply f.,&< NB. Self referring lv=. (((^:_1)b.)((<'0';_1)))(:6) NB. Linear representation of a verb argument Y=. (&>)/lv(&sr) NB. Y with embedded states Y=. 'Y'f. NB. Fixing it... Y NB. ... To make it stateless (i.e., a combinator)((((&>)/)((((^:_1)b.)(_1))(:6)))(&([ 128!:2 ,&<))) ### Explicit alternate implementation Another approach: Y=:1 :0 f=. u Defer (5!:1<'f') f y) Defer=: 1 :0: g=. x&(x:6) (5!:1<'g') u y) almost_factorial=: 4 :0 if. 0 >: y do. 1 else. y * x:6 y-1 end.) almost_fibonacci=: 4 :0 if. 2 > y do. y else. (x:6 y-1) + x:6 y-2 end.) Example use:  almost_factorial Y 9362880 almost_fibonacci Y 934 almost_fibonacci Y"0 i. 100 1 1 2 3 5 8 13 21 34 Or, if you would prefer to not have a dependency on the definition of Defer, an equivalent expression would be: Y=:2 :0(0 :0)NB. this block will be n in the second part: g=. x&(x:6) (5!:1<'g') u y) f=. u (1 :n) (5!:1<'f') f y) That said, if you think of association with a name as state (because in different contexts the association may not exist, or may be different) you might also want to remove that association in the context of the Y combinator. For example:  almost_factorial f. Y 103628800 ## Java Works with: Java version 8+ import java.util.function.Function; public interface YCombinator { interface RecursiveFunction<F> extends Function<RecursiveFunction<F>, F> { } public static <A,B> Function<A,B> Y(Function<Function<A,B>, Function<A,B>> f) { RecursiveFunction<Function<A,B>> r = w -> f.apply(x -> w.apply(w).apply(x)); return r.apply(r); } public static void main(String... arguments) { Function<Integer,Integer> fib = Y(f -> n -> (n <= 2) ? 1 : (f.apply(n - 1) + f.apply(n - 2)) ); Function<Integer,Integer> fac = Y(f -> n -> (n <= 1) ? 1 : (n * f.apply(n - 1)) ); System.out.println("fib(10) = " + fib.apply(10)); System.out.println("fac(10) = " + fac.apply(10)); }} Output: fib(10) = 55 fac(10) = 3628800  The usual version using recursion, disallowed by the task:  public static <A,B> Function<A,B> Y(Function<Function<A,B>, Function<A,B>> f) { return x -> f.apply(Y(f)).apply(x); } Another version which is disallowed because a function passes itself, which is also a kind of recursion:  public static <A,B> Function<A,B> Y(Function<Function<A,B>, Function<A,B>> f) { return new Function<A,B>() { public B apply(A x) { return f.apply(this).apply(x); } }; } Works with: Java version pre-8 We define a generic function interface like Java 8's Function. interface Function<A, B> { public B call(A x);} public class YCombinator { interface RecursiveFunc<F> extends Function<RecursiveFunc<F>, F> { } public static <A,B> Function<A,B> fix(final Function<Function<A,B>, Function<A,B>> f) { RecursiveFunc<Function<A,B>> r = new RecursiveFunc<Function<A,B>>() { public Function<A,B> call(final RecursiveFunc<Function<A,B>> w) { return f.call(new Function<A,B>() { public B call(A x) { return w.call(w).call(x); } }); } }; return r.call(r); } public static void main(String[] args) { Function<Function<Integer,Integer>, Function<Integer,Integer>> almost_fib = new Function<Function<Integer,Integer>, Function<Integer,Integer>>() { public Function<Integer,Integer> call(final Function<Integer,Integer> f) { return new Function<Integer,Integer>() { public Integer call(Integer n) { if (n <= 2) return 1; return f.call(n - 1) + f.call(n - 2); } }; } }; Function<Function<Integer,Integer>, Function<Integer,Integer>> almost_fac = new Function<Function<Integer,Integer>, Function<Integer,Integer>>() { public Function<Integer,Integer> call(final Function<Integer,Integer> f) { return new Function<Integer,Integer>() { public Integer call(Integer n) { if (n <= 1) return 1; return n * f.call(n - 1); } }; } }; Function<Integer,Integer> fib = fix(almost_fib); Function<Integer,Integer> fac = fix(almost_fac); System.out.println("fib(10) = " + fib.call(10)); System.out.println("fac(10) = " + fac.call(10)); }} The following code modifies the Function interface such that multiple parameters (via varargs) are supported, simplifies the y function considerably, and the Ackermann function has been included in this implementation (mostly because both D and PicoLisp include it in their own implementations). import java.util.function.Function; @FunctionalInterfacepublic interface SelfApplicable<OUTPUT> extends Function<SelfApplicable<OUTPUT>, OUTPUT> { public default OUTPUT selfApply() { return apply(this); }} import java.util.function.Function;import java.util.function.UnaryOperator; @FunctionalInterfacepublic interface FixedPoint<FUNCTION> extends Function<UnaryOperator<FUNCTION>, FUNCTION> {} import java.util.Arrays;import java.util.Optional;import java.util.function.Function;import java.util.function.BiFunction; @FunctionalInterfacepublic interface VarargsFunction<INPUTS, OUTPUT> extends Function<INPUTS[], OUTPUT> { @SuppressWarnings("unchecked") public OUTPUT apply(INPUTS... inputs); public static <INPUTS, OUTPUT> VarargsFunction<INPUTS, OUTPUT> from(Function<INPUTS[], OUTPUT> function) { return function::apply; } public static <INPUTS, OUTPUT> VarargsFunction<INPUTS, OUTPUT> upgrade(Function<INPUTS, OUTPUT> function) { return inputs -> function.apply(inputs); } public static <INPUTS, OUTPUT> VarargsFunction<INPUTS, OUTPUT> upgrade(BiFunction<INPUTS, INPUTS, OUTPUT> function) { return inputs -> function.apply(inputs, inputs); } @SuppressWarnings("unchecked") public default <POST_OUTPUT> VarargsFunction<INPUTS, POST_OUTPUT> andThen( VarargsFunction<OUTPUT, POST_OUTPUT> after) { return inputs -> after.apply(apply(inputs)); } @SuppressWarnings("unchecked") public default Function<INPUTS, OUTPUT> toFunction() { return input -> apply(input); } @SuppressWarnings("unchecked") public default BiFunction<INPUTS, INPUTS, OUTPUT> toBiFunction() { return (input, input2) -> apply(input, input2); } @SuppressWarnings("unchecked") public default <PRE_INPUTS> VarargsFunction<PRE_INPUTS, OUTPUT> transformArguments(Function<PRE_INPUTS, INPUTS> transformer) { return inputs -> apply((INPUTS[]) Arrays.stream(inputs).parallel().map(transformer).toArray()); }} import java.math.BigDecimal;import java.math.BigInteger;import java.util.Arrays;import java.util.HashMap;import java.util.Map;import java.util.function.Function;import java.util.function.UnaryOperator;import java.util.stream.Collectors;import java.util.stream.LongStream; @FunctionalInterfacepublic interface Y<FUNCTION> extends SelfApplicable<FixedPoint<FUNCTION>> { public static void main(String... arguments) { BigInteger TWO = BigInteger.ONE.add(BigInteger.ONE); Function<Number, Long> toLong = Number::longValue; Function<Number, BigInteger> toBigInteger = toLong.andThen(BigInteger::valueOf); /* Based on https://gist.github.com/aruld/3965968/#comment-604392 */ Y<VarargsFunction<Number, Number>> combinator = y -> f -> x -> f.apply(y.selfApply().apply(f)).apply(x); FixedPoint<VarargsFunction<Number, Number>> fixedPoint = combinator.selfApply(); VarargsFunction<Number, Number> fibonacci = fixedPoint.apply( f -> VarargsFunction.upgrade( toBigInteger.andThen( n -> (n.compareTo(TWO) <= 0) ? 1 : new BigInteger(f.apply(n.subtract(BigInteger.ONE)).toString()) .add(new BigInteger(f.apply(n.subtract(TWO)).toString())) ) ) ); VarargsFunction<Number, Number> factorial = fixedPoint.apply( f -> VarargsFunction.upgrade( toBigInteger.andThen( n -> (n.compareTo(BigInteger.ONE) <= 0) ? 1 : n.multiply(new BigInteger(f.apply(n.subtract(BigInteger.ONE)).toString())) ) ) ); VarargsFunction<Number, Number> ackermann = fixedPoint.apply( f -> VarargsFunction.upgrade( (BigInteger m, BigInteger n) -> m.equals(BigInteger.ZERO) ? n.add(BigInteger.ONE) : f.apply( m.subtract(BigInteger.ONE), n.equals(BigInteger.ZERO) ? BigInteger.ONE : f.apply(m, n.subtract(BigInteger.ONE)) ) ).transformArguments(toBigInteger) ); Map<String, VarargsFunction<Number, Number>> functions = new HashMap<>(); functions.put("fibonacci", fibonacci); functions.put("factorial", factorial); functions.put("ackermann", ackermann); Map<VarargsFunction<Number, Number>, Number[]> parameters = new HashMap<>(); parameters.put(functions.get("fibonacci"), new Number[]{20}); parameters.put(functions.get("factorial"), new Number[]{10}); parameters.put(functions.get("ackermann"), new Number[]{3, 2}); functions.entrySet().stream().parallel().map( entry -> entry.getKey() + Arrays.toString(parameters.get(entry.getValue())) + " = " + entry.getValue().apply(parameters.get(entry.getValue())) ).forEach(System.out::println); }} Output: (may depend on which function gets processed first): factorial = 3628800ackermann[3, 2] = 29fibonacci = 6765 ## JavaScript The standard version of the Y combinator does not use lexically bound local variables (or any local variables at all), which necessitates adding a wrapper function and some code duplication - the remaining locale variables are only there to make the relationship to the previous implementation more explicit: function Y(f) { var g = f((function(h) { return function() { var g = f(h(h)); return g.apply(this, arguments); } })(function(h) { return function() { var g = f(h(h)); return g.apply(this, arguments); } })); return g;} var fac = Y(function(f) { return function (n) { return n > 1 ? n * f(n - 1) : 1; };}); var fib = Y(function(f) { return function(n) { return n > 1 ? f(n - 1) + f(n - 2) : n; };}); Changing the order of function application (i.e. the place where f gets called) and making use of the fact that we're generating a fixed-point, this can be reduced to function Y(f) { return (function(h) { return h(h); })(function(h) { return f(function() { return h(h).apply(this, arguments); }); });} A functionally equivalent version using the implicit this parameter is also possible: function pseudoY(f) { return (function(h) { return h(h); })(function(h) { return f.bind(function() { return h(h).apply(null, arguments); }); });} var fac = pseudoY(function(n) { return n > 1 ? n * this(n - 1) : 1;}); var fib = pseudoY(function(n) { return n > 1 ? this(n - 1) + this(n - 2) : n;}); However, pseudoY() is not a fixed-point combinator. The usual version using recursion, disallowed by the task: function Y(f) { return function() { return f(Y(f)).apply(this, arguments); };} Another version which is disallowed because it uses arguments.callee for a function to get itself recursively: function Y(f) { return function() { return f(arguments.callee).apply(this, arguments); };} ### ECMAScript 2015 (ES6) variants Since ECMAScript 2015 (ES6) just reached final draft, there are new ways to encode the applicative order Y combinator. These use the new fat arrow function expression syntax, and are made to allow functions of more than one argument through the use of new rest parameters syntax and the corresponding new spread operator syntax. Also showcases new default parameter value syntax: let Y= // Except for the η-abstraction necessary for applicative order languages, this is the formal Y combinator. f=>((g=>(f((...x)=>g(g)(...x)))) (g=>(f((...x)=>g(g)(...x))))), Y2= // Using β-abstraction to eliminate code repetition. f=>((f=>f(f)) (g=>(f((...x)=>g(g)(...x))))), Y3= // Using β-abstraction to separate out the self application combinator δ. ((δ=>f=>δ(g=>(f((...x)=>g(g)(...x))))) ((f=>f(f)))), fix= // β/η-equivalent fix point combinator. Easier to convert to memoise than the Y combinator. (((f)=>(g)=>(h)=>(f(h)(g(h)))) // The Substitute combinator out of SKI calculus ((f)=>(g)=>(...x)=>(f(g(g)))(...x)) // S((S(KS)K)S(S(KS)K))(KI) ((f)=>(g)=>(...x)=>(f(g(g)))(...x))), fix2= // β/η-converted form of fix above into a more compact form f=>(f=>f(f))(g=>(...x)=>f(g(g))(...x)), opentailfact= // Open version of the tail call variant of the factorial function fact=>(n,m=1)=>n<2?m:fact(n-1,n*m); tailfact= // Tail call version of factorial function Y(opentailfact); ECMAScript 2015 (ES6) also permits a really compact polyvariadic variant for mutually recursive functions: let polyfix= // A version that takes an array instead of multiple arguments would simply use l instead of (...l) for parameter (...l)=>( (f=>f(f)) (g=>l.map(f=>(...x)=>f(...g(g))(...x)))), [even,odd]= // The new destructive assignment syntax for arrays polyfix( (even,odd)=>n=>(n===0)||odd(n-1), (even,odd)=>n=>(n!==0)&&even(n-1)); A minimalist version: var Y = f => (x => x(x))(y => f(x => y(y)(x)));var fac = Y(f => n => n > 1 ? n * f(n-1) : 1); ## Joy DEFINE y == [dup cons] swap concat dup cons i; fac == [ [pop null] [pop succ] [[dup pred] dip i *] ifte ] y. ## Julia  julia> """ # Y combinator * λf. (λx. f (x x)) (λx. f (x x)) """ Y = f -> (x -> x(x))(y -> f((t...) -> y(y)(t...)))  Usage:  julia> "# Factorial" fac = f -> (n -> n < 2 ? 1 : n * f(n - 1)) julia> "# Fibonacci" fib = f -> (n -> n == 0 ? 0 : (n == 1 ? 1 : f(n - 1) + f(n - 2))) julia> [Y(fac)(i) for i = 1:10]10-element Array{Any,1}: 1 2 6 24 120 720 5040 40320 362880 3628800 julia> [Y(fib)(i) for i = 1:10]10-element Array{Any,1}: 1 1 2 3 5 8 13 21 34 55  ## Kitten define y<S..., T...> (S..., (S..., (S... -> T...) -> T...) -> T...): -> f; { f y } f call define fac (Int32, (Int32 -> Int32) -> Int32): -> x, rec; if (x <= 1) { 1 } else { (x - 1) rec call * x } define fib (Int32, (Int32 -> Int32) -> Int32): -> x, rec; if (x <= 2): 1 else: (x - 1) rec call -> a; (x - 2) rec call -> b; a + b 5 \fac y say // 12010 \fib y say // 55  ## Kotlin // version 1.1.2 typealias Func<T, R> = (T) -> R class RecursiveFunc<T, R>(val p: (RecursiveFunc<T, R>) -> Func<T, R>) fun <T, R> y(f: (Func<T, R>) -> Func<T, R>): Func<T, R> { val rec = RecursiveFunc<T, R> { r -> f { r.p(r)(it) } } return rec.p(rec)} fun fac(f: Func<Int, Int>) = { x: Int -> if (x <= 1) 1 else x * f(x - 1) } fun fib(f: Func<Int, Int>) = { x: Int -> if (x <= 2) 1 else f(x - 1) + f(x - 2) } fun main(args: Array<String>) { print("Factorial(1..10) : ") for (i in 1..10) print("${y(::fac)(i)}  ")     print("\nFibonacci(1..10)   : ")       for (i in 1..10) print("${y(::fib)(i)} ") println()} Output: Factorial(1..10) : 1 2 6 24 120 720 5040 40320 362880 3628800 Fibonacci(1..10) : 1 1 2 3 5 8 13 21 34 55  ## Lambdatalk  1) defining the Ycombinator{def Y {lambda {:f :n} {:f :f :n}}} 2) defining non recursive functions2.1) factorial {def almost-fac {lambda {:f :n} {if {= :n 1} then 1 else {* :n {:f :f {- :n 1}}}}}} 2.2) fibonacci{def almost-fibo {lambda {:f :n} {if {< :n 2} then 1 else {+ {:f :f {- :n 1}} {:f :f {- :n 2}}}}}} 3) testing{Y almost-fac 6} -> 720{Y almost-fibo 8} -> 34 We could also forget the Ycombinator and names: 1) fac:{{lambda {:f :n} {:f :f :n}} {lambda {:f :n} {if {= :n 1} then 1 else {* :n {:f :f {- :n 1}}}}} 6} -> 720 2) fibo:{{lambda {:f :n} {:f :f :n}} {{lambda {:f :n} {if {< :n 2} then 1 else {+ {:f :f {- :n 1}} {:f :f {- :n 2}}}}}} 8} -> 34  ## Lua Y = function (f) return function(...) return (function(x) return x(x) end)(function(x) return f(function(y) return x(x)(y) end) end)(...) endend  Usage: almostfactorial = function(f) return function(n) return n > 0 and n * f(n-1) or 1 end endalmostfibs = function(f) return function(n) return n < 2 and n or f(n-1) + f(n-2) end endfactorial, fibs = Y(almostfactorial), Y(almostfibs)print(factorial(7)) ## M2000 Interpreter Lambda functions in M2000 are value types. They have a list of closures, but closures are copies, except for those closures which are reference types. Lambdas can keep state in closures (they are mutable). But here we didn't do that. Y combinator is a lambda which return a lambda with a closure as f function. This function called passing as first argument itself by value.  Module Ycombinator { \\ y() return value. no use of closure y=lambda (g, x)->g(g, x) Print y(lambda (g, n)->if(n=0->1, n*g(g, n-1)), 10) Print y(lambda (g, n)->if(n<=1->n,g(g, n-1)+g(g, n-2)), 10) \\ Using closure in y, y() return function y=lambda (g)->lambda g (x) -> g(g, x) fact=y((lambda (g, n)-> if(n=0->1, n*g(g, n-1)))) Print fact(6), fact(24) fib=y(lambda (g, n)->if(n<=1->n,g(g, n-1)+g(g, n-2))) Print fib(10)}Ycombinator   Module Checkit { \\ all lambda arguments passed by value in this example \\ There is no recursion in these lambdas \\ Y combinator make argument f as closure, as a copy of f \\ m(m, argument) pass as first argument a copy of m \\ so never a function, here, call itself, only call a copy who get it as argument before the call. Y=lambda (f)-> { =lambda f (x)->f(f,x) } fac_step=lambda (m, n)-> { if n<2 then { =1 } else { =n*m(m, n-1) } } fac=Y(fac_step) fib_step=lambda (m, n)-> { if n<=1 then { =n } else { =m(m, n-1)+m(m, n-2) } } fib=Y(fib_step) For i=1 to 10 Print fib(i), fac(i) Next i}CheckitModule CheckRecursion { fac=lambda (n) -> { if n<2 then { =1 } else { =n*Lambda(n-1) } } fib=lambda (n) -> { if n<=1 then { =n } else { =lambda(n-1)+lambda(n-2) } } For i=1 to 10 Print fib(i), fac(i) Next i}CheckRecursion  ## Maple  > Y:=f->(x->x(x))(g->f((()->g(g)(args)))):> Yfac:=Y(f->(x->if(x<2,1,x*f(x-1)))):> seq( Yfac( i ), i = 1 .. 10 ); 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800> Yfib:=Y(f->(x->if(x<2,x,f(x-1)+f(x-2)))):> seq( Yfib( i ), i = 1 .. 10 ); 1, 1, 2, 3, 5, 8, 13, 21, 34, 55  ## Mathematica / Wolfram Language Y = Function[f, #[#] &[Function[g, f[g[g][##] &]]]];factorial = Y[Function[f, If[# < 1, 1, # f[# - 1]] &]];fibonacci = Y[Function[f, If[# < 2, #, f[# - 1] + f[# - 2]] &]]; ## Moonscript Z = (f using nil) -> ((x) -> x x) (x) -> f (...) -> (x x) ...factorial = Z (f using nil) -> (n) -> if n == 0 then 1 else n * f n - 1 ## Objective-C Works with: Mac OS X version 10.6+ Works with: iOS version 4.0+ #import <Foundation/Foundation.h> typedef int (^Func)(int);typedef Func (^FuncFunc)(Func);typedef Func (^RecursiveFunc)(id); // hide recursive typing behind dynamic typing Func Y(FuncFunc f) { RecursiveFunc r = ^(id y) { RecursiveFunc w = y; // cast value back into desired type return f(^(int x) { return w(w)(x); }); }; return r(r);} int main (int argc, const char *argv[]) { @autoreleasepool { Func fib = Y(^Func(Func f) { return ^(int n) { if (n <= 2) return 1; return f(n - 1) + f(n - 2); }; }); Func fac = Y(^Func(Func f) { return ^(int n) { if (n <= 1) return 1; return n * f(n - 1); }; }); Func fib = fix(almost_fib); Func fac = fix(almost_fac); NSLog(@"fib(10) = %d", fib(10)); NSLog(@"fac(10) = %d", fac(10)); } return 0;} The usual version using recursion, disallowed by the task: Func Y(FuncFunc f) { return ^(int x) { return f(Y(f))(x); };} ## OCaml The Y-combinator over functions may be written directly in OCaml provided rectypes are enabled: let fix f g = (fun x a -> f (x x) a) (fun x a -> f (x x) a) g Polymorphic variants are the simplest workaround in the absence of rectypes: let fix f = (fun (X x) -> f(x (X x))) (X(fun (X x) y -> f(x (X x)) y));; Otherwise, an ordinary variant can be defined and used: type 'a mu = Roll of ('a mu -> 'a);; let unroll (Roll x) = x;; let fix f = (fun x a -> f (unroll x x) a) (Roll (fun x a -> f (unroll x x) a));; let fac f = function 0 -> 1 | n -> n * f (n-1);; let fib f = function 0 -> 0 | 1 -> 1 | n -> f (n-1) + f (n-2);; (* val unroll : 'a mu -> 'a mu -> 'a = <fun>val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>val fac : (int -> int) -> int -> int = <fun>val fib : (int -> int) -> int -> int = <fun> *) fix fac 5;;(* - : int = 120 *) fix fib 8;;(* - : int = 21 *) The usual version using recursion, disallowed by the task: let rec fix f x = f (fix f) x;; ## Oforth These combinators work for any number of parameters (see Ackermann usage) With recursion into Y definition (so non stateless Y) : : Y(f) #[ f Y f perform ] ; Without recursion into Y definition (stateless Y). : X(me, f) #[ me f me perform f perform ] ;: Y(f) #X f X ; Usage : : almost-fact(n, f) n ifZero: [ 1 ] else: [ n n 1 - f perform * ] ;#almost-fact Y => fact : almost-fib(n, f) n 1 <= ifTrue: [ n ] else: [ n 1 - f perform n 2 - f perform + ] ;#almost-fib Y => fib : almost-Ackermann(m, n, f) m 0 == ifTrue: [ n 1 + return ] n 0 == ifTrue: [ 1 m 1 - f perform return ] n 1 - m f perform m 1 - f perform ;#almost-Ackermann Y => Ackermann  ## Order #include <order/interpreter.h> #define ORDER_PP_DEF_8y \ORDER_PP_FN(8fn(8F, \ 8let((8R, 8fn(8G, \ 8ap(8F, 8fn(8A, 8ap(8ap(8G, 8G), 8A))))), \ 8ap(8R, 8R)))) #define ORDER_PP_DEF_8fac \ORDER_PP_FN(8fn(8F, 8X, \ 8if(8less_eq(8X, 0), 1, 8times(8X, 8ap(8F, 8minus(8X, 1)))))) #define ORDER_PP_DEF_8fib \ORDER_PP_FN(8fn(8F, 8X, \ 8if(8less(8X, 2), 8X, 8plus(8ap(8F, 8minus(8X, 1)), \ 8ap(8F, 8minus(8X, 2)))))) ORDER_PP(8to_lit(8ap(8y(8fac), 10))) // 3628800ORDER_PP(8ap(8y(8fib), 10)) // 55 ## Oz declare Y = fun {$ F}         {fun {$X} {X X} end fun {$ X} {F fun {$Z} {{X X} Z} end} end} end Fac = {Y fun {$ F}              fun {$N} if N == 0 then 1 else N*{F N-1} end end end} Fib = {Y fun {$ F}              fun {$N} case N of 0 then 0 [] 1 then 1 else {F N-1} + {F N-2} end end end}in {Show {Fac 5}} {Show {Fib 8}} ## PARI/GP As of 2.8.0, GP cannot make general self-references in closures declared inline, so the Y combinator is required to implement these functions recursively in that environment, e.g., for use in parallel processing. Y(f)=x->f(f,x);fact=Y((f,n)->if(n,n*f(f,n-1),1));fib=Y((f,n)->if(n>1,f(f,n-1)+f(f,n-2),n));apply(fact, [1..10])apply(fib, [1..10]) Output: %1 = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800] %2 = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] ## Perl sub Y { my$f = shift;                                # λf.    sub { my $x = shift;$x->($x) }->( # (λx.x x) sub {my$y = shift; $f->(sub {$y->($y)(@_)})} # λy.f λz.y y z )}my$fac = sub {my $f = shift; sub {my$n = shift; $n < 2 ? 1 :$n * $f->($n-1)}};my $fib = sub {my$f = shift;    sub {my $n = shift;$n == 0 ? 0 : $n == 1 ? 1 :$f->($n-1) +$f->($n-2)}};for my$f ($fac,$fib) {    print join(' ', map Y($f)->($_), 0..9), "\n";}
Output:
1 1 2 6 24 120 720 5040 40320 362880
0 1 1 2 3 5 8 13 21 34

The usual version using recursion, disallowed by the task:

sub Y { my $f = shift; sub {$f->(Y($f))->(@_)}} ## Perl 6 sub Y (&f) { sub (&x) { x(&x) }( sub (&y) { f(sub ($x) { y(&y)($x) }) } ) }sub fac (&f) { sub ($n) { $n < 2 ?? 1 !!$n * f($n - 1) } }sub fib (&f) { sub ($n) { $n < 2 ??$n !! f($n - 1) + f($n - 2) } }say map Y($_), ^10 for &fac, &fib; Output: (1 1 2 6 24 120 720 5040 40320 362880) (0 1 1 2 3 5 8 13 21 34) Note that Perl 6 doesn't actually need a Y combinator because you can name anonymous functions from the inside: say .(10) given sub (Int$x) { $x < 2 ?? 1 !!$x * &?ROUTINE($x - 1); } ## Phix Translation of: C After (over) simplifying things, the Y function has become a bit of a joke, but at least the recursion has been shifted out of fib/fac Before saying anything too derogatory about Y(f)=f, it is clearly a fixed-point combinator, and I feel compelled to quote from the Mike Vanier link above: "It doesn't matter whether you use cos or (lambda (x) (cos x)) as your cosine function; they will both do the same thing." Anyone thinking they can do better may find some inspiration at Currying, Closures/Value_capture, Partial_function_application, and/or Function_composition function call_fn(integer f, n) return call_func(f,{f,n})end function function Y(integer f) return fend function function fac(integer self, integer n) return iff(n>1?n*call_fn(self,n-1):1)end function function fib(integer self, integer n) return iff(n>1?call_fn(self,n-1)+call_fn(self,n-2):n)end function procedure test(string name, integer rid=routine_id(name)) integer f = Y(rid) printf(1,"%s: ",{name}) for i=1 to 10 do printf(1," %d",call_fn(f,i)) end for printf(1,"\n");end proceduretest("fac")test("fib") Output: fac: 1 2 6 24 120 720 5040 40320 362880 3628800 fib: 1 1 2 3 5 8 13 21 34 55  ## PHP Works with: PHP version 5.3+ <?phpfunction Y($f) {  $g = function($w) use($f) { return$f(function() use($w) { return call_user_func_array($w($w), func_get_args()); }); }; return$g($g);}$fibonacci = Y(function($f) { return function($i) use($f) { return ($i <= 1) ? $i : ($f($i-1) +$f($i-2)); };}); echo$fibonacci(10), "\n"; $factorial = Y(function($f) {  return function($i) use($f) { return ($i <= 1) ? 1 : ($f($i - 1) *$i); };}); echo $factorial(10), "\n";?> The usual version using recursion, disallowed by the task: function Y($f) {  return function() use($f) { return call_user_func_array($f(Y($f)), func_get_args()); };} Works with: PHP version pre-5.3 and 5.3+ with create_function instead of real closures. A little far-fetched, but... <?phpfunction Y($f) {  $g = create_function('$w', '$f = '.var_export($f,true).';    return $f(create_function(\'\', \'$w = \'.var_export($w,true).\'; return call_user_func_array($w($w), func_get_args()); \')); '); return$g($g);} function almost_fib($f) {  return create_function('$i', '$f = '.var_export($f,true).'; return ($i <= 1) ? $i : ($f($i-1) +$f($i-2)); ');};$fibonacci = Y('almost_fib');echo $fibonacci(10), "\n"; function almost_fac($f) {  return create_function('$i', '$f = '.var_export($f,true).'; return ($i <= 1) ? 1 : ($f($i - 1) * $i); ');};$factorial = Y('almost_fac');echo $factorial(10), "\n";?> A functionally equivalent version using the $this parameter in closures is also possible:

Works with: PHP version 5.4+
<?phpfunction pseudoY($f) {$g = function($w) use ($f) {        return $f->bindTo(function() use ($w) {            return call_user_func_array($w($w), func_get_args());        });    };    return $g($g);} $factorial = pseudoY(function($n) {    return $n > 1 ?$n * $this($n - 1) : 1;});echo $factorial(10), "\n";$fibonacci = pseudoY(function($n) { return$n > 1 ? $this($n - 1) + $this($n - 2) : $n;});echo$fibonacci(10), "\n";?>

However, pseudoY() is not a fixed-point combinator.

## PicoLisp

Translation of: Common Lisp
(de Y (F)   (let X (curry (F) (Y) (F (curry (Y) @ (pass (Y Y)))))      (X X) ) )

### Factorial

# Factorial(de fact (F)   (curry (F) (N)      (if (=0 N)         1         (* N (F (dec N))) ) ) ) : ((Y fact) 6)-> 720

### Fibonacci sequence

# Fibonacci(de fibo (F)   (curry (F) (N)      (if (> 2 N)         1         (+ (F (dec N)) (F (- N 2))) ) ) ) : ((Y fibo) 22)-> 28657

### Ackermann function

# Ackermann(de ack (F)   (curry (F) (X Y)      (cond         ((=0 X) (inc Y))         ((=0 Y) (F (dec X) 1))         (T (F (dec X) (F X (dec Y)))) ) ) ) : ((Y ack) 3 4)-> 125

## Pop11

define Y(f);    procedure (x); x(x) endprocedure(        procedure (y);            f(procedure(z); (y(y))(z) endprocedure)        endprocedure    )enddefine; define fac(h);    procedure (n);       if n = 0 then 1 else n * h(n - 1) endif    endprocedureenddefine; define fib(h);    procedure (n);        if n < 2 then 1 else h(n - 1) + h(n - 2) endif    endprocedureenddefine; Y(fac)(5) =>Y(fib)(5) =>
Output:
** 120
** 8


## PostScript

Translation of: Joy
Library: initlib
y {    {dup cons} exch concat dup cons i}. /fac {    { {pop zero?} {pop succ} {{dup pred} dip i *} ifte }    y}.

## PowerShell

Translation of: Python

PowerShell Doesn't have true closure, in order to fake it, the script-block is converted to text and inserted whole into the next function using variable expansion in double-quoted strings. For simple translation of lambda calculus, $lambda$ translates as param inside of a ScriptBlock, $(\ldots )$ translates as Invoke-Expression "{}", invocation (written as a space) translates to InvokeReturnAsIs. ${\begin{array}{lcl}fac&:=&\lambda f.(\lambda n.{\mbox{if }}n\leq 0{\mbox{ then }}1{\mbox{ else }}n*(f\ n-1))\\fib&:=&\lambda f.(\lambda n.{\mbox{if }}n=0{\mbox{ or }}n=1{\mbox{ then }}1{\mbox{ else }}(f\ n-1)+(f\ n-2))\\Z&:=&\lambda f.(\lambda x.f\ (\lambda y.x\ x\ y))\ (\lambda x.f\ (\lambda y.x\ x\ y))\\\end{array}}$

$fac = { param([ScriptBlock]$f)    	invoke-expression @"    	{    		param([int] $n) if ($n -le 0) {1}    		else {$n * {$f}.InvokeReturnAsIs($n - 1)} }"@ }$fib = {	param([ScriptBlock] $f) invoke-expression @" { param([int] $n)		switch ($n) { 0 {1} 1 {1} default {{$f}.InvokeReturnAsIs($n-1)+{$f}.InvokeReturnAsIs($n-2)} } }"@}$Z = {    param([ScriptBlock] $f) invoke-expression @" { param([ScriptBlock] $x)        {$f}.InvokeReturnAsIs($(invoke-expression @"        {            param($y) {$x}.InvokeReturnAsIs({$x}).InvokeReturnAsIs($y)        }"@))    }.InvokeReturnAsIs({        param([ScriptBlock] $x) {$f}.InvokeReturnAsIs($(invoke-expression @" { param($y)            {$x}.InvokeReturnAsIs({$x}).InvokeReturnAsIs($y) }"@)) })"@}$Z.InvokeReturnAsIs($fac).InvokeReturnAsIs(5)$Z.InvokeReturnAsIs($fib).InvokeReturnAsIs(5) GetNewClosure() was added in Powershell 2, allowing for an implementation without metaprogramming. The following was tested with Powershell 4. $Y = {    param ($f) { param ($x)         $f.InvokeReturnAsIs({ param ($y)             $x.InvokeReturnAsIs($x).InvokeReturnAsIs($y) }.GetNewClosure()) }.InvokeReturnAsIs({ param ($x)         $f.InvokeReturnAsIs({ param ($y)             $x.InvokeReturnAsIs($x).InvokeReturnAsIs($y) }.GetNewClosure()) }.GetNewClosure())}$fact = {    param ($f) { param ($n)         if ($n -eq 0) { 1 } else {$n * $f.InvokeReturnAsIs($n - 1) }     }.GetNewClosure()} $fib = { param ($f)     {        param ($n) if ($n -lt 2) { 1 } else { $f.InvokeReturnAsIs($n - 1) + $f.InvokeReturnAsIs($n - 2) }     }.GetNewClosure()} $Y.invoke($fact).invoke(5)$Y.invoke($fib).invoke(5)

## Prolog

Works with SWI-Prolog and module lambda, written by Ulrich Neumerkel found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl.

Original code is from Hermenegildo and al : Hiord: A Type-Free Higher-Order Logic Programming Language with Predicate Abstraction, pdf accessible here http://www.stups.uni-duesseldorf.de/asap/?id=129.

:- use_module(lambda). % The Y combinatory(P, Arg, R) :-	Pred = P +\Nb2^F2^call(P,Nb2,F2,P),	call(Pred, Arg, R).  test_y_combinator :-    % code for Fibonacci function    Fib   = \NFib^RFib^RFibr1^(NFib < 2 ->			         RFib = NFib			      ;			         NFib1 is NFib - 1,			         NFib2 is NFib - 2,			         call(RFibr1,NFib1,RFib1,RFibr1),			         call(RFibr1,NFib2,RFib2,RFibr1),			         RFib is RFib1 + RFib2			      ),     y(Fib, 10, FR), format('Fib(~w) = ~w~n', [10, FR]),     % code for Factorial function    Fact =  \NFact^RFact^RFactr1^(NFact = 1 ->			            RFact = NFact                                 ;			            NFact1 is NFact - 1,			            call(RFactr1,NFact1,RFact1,RFactr1),			            RFact is NFact * RFact1			         ),     y(Fact, 10, FF), format('Fact(~w) = ~w~n', [10, FF]).
Output:
 ?- test_y_combinator.
Fib(10) = 55
Fact(10) = 3628800
true.

## Python

>>> Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))>>> fac = lambda f: lambda n: (1 if n<2 else n*f(n-1))>>> [ Y(fac)(i) for i in range(10) ][1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]>>> fib = lambda f: lambda n: 0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2))>>> [ Y(fib)(i) for i in range(10) ][0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

The usual version using recursion, disallowed by the task:

Y = lambda f: lambda *args: f(Y(f))(*args)
Y = lambda b: ((lambda f: b(lambda *x: f(f)(*x)))((lambda f: b(lambda *x: f(f)(*x)))))

## R

Y <- function(f) {  (function(x) { (x)(x) })( function(y) { f( (function(a) {y(y)})(a) ) } )}
fac <- function(f) {  function(n) {    if (n<2)      1    else      n*f(n-1)  }} fib <- function(f) {  function(n) {    if (n <= 1)      n    else      f(n-1) + f(n-2)  }}
for(i in 1:9) print(Y(fac)(i))for(i in 1:9) print(Y(fib)(i))

## Racket

The lazy implementation

 #lang lazy (define Y (λ(f)((λ(x)(f (x x)))(λ(x)(f (x x)))))) (define Fact  (Y (λ(fact) (λ(n) (if (zero? n) 1 (* n (fact (- n 1))))))))(define Fib  (Y (λ(fib) (λ(n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))))))))
Output:
> (!! (map Fact '(1 2 4 8 16)))
'(1 2 24 40320 20922789888000)
> (!! (map Fib '(1 2 4 8 16)))
'(0 1 2 13 610)


Strict realization:

 #lang racket(define Y (λ(b)((λ(f)(b(λ(x)((f f) x))))                (λ(f)(b(λ(x)((f f) x)))))))

Definitions of Fact and Fib functions will be the same as in Lazy Racket.

Finally, a definition in Typed Racket is a little difficult as in other statically typed languages:

 #lang typed/racket (: make-recursive : (All (S T) ((S -> T) -> (S -> T)) -> (S -> T)))(define-type Tau (All (S T) (Rec this (this -> (S -> T)))))(define (make-recursive f)  ((lambda: ([x : (Tau S T)]) (f (lambda (z) ((x x) z))))   (lambda: ([x : (Tau S T)]) (f (lambda (z) ((x x) z)))))) (: fact : Number -> Number)(define fact (make-recursive              (lambda: ([fact : (Number -> Number)])                (lambda: ([n : Number])                  (if (zero? n)                    1                    (* n (fact (- n 1)))))))) (fact 5)

## REBOL

Y: closure [g] [do func [f] [f :f] closure [f] [g func [x] [do f :f :x]]]
usage example
fact*: closure [h] [func [n] [either n <= 1  [n * h n - 1]]]fact: Y :fact*

## REXX

Programming note:   length,   reverse,   and   trunc   are REXX BIFs   (Built In Functions).

/*REXX program implements and displays  a  stateless   Y   combinator.        */numeric digits 1000                                      /*allow big numbers. */say '    fib' Y(fib     (50))                            /*Fibonacci series.  */say '    fib' Y(fib     (12 11 10 9 8 7 6 5 4 3 2 1 0))  /*Fibonacci series.  */say '   fact' Y(fact    (60))                            /*single    factorial*/say '   fact' Y(fact    (0 1 2 3 4 5 6 7 8 9 10 11))     /*single    factorial*/say '  Dfact' Y(dfact   (4 5 6 7 8 9 10 11 12 13))       /*double    factorial*/say '  Tfact' Y(tfact   (4 5 6 7 8 9 10 11 12 13))       /*triple    factorial*/say '  Qfact' Y(qfact   (4 5 6 7 8 40))                  /*quadruple factorial*/say ' length' Y(length  (when for to where whenceforth)) /*lengths   of words.*/say 'reverse' Y(reverse (23 678 1007 45 MAS I MA))       /*reverses  strings. */say '  trunc' Y(trunc   (-7.0005 12 3.14159 6.4 78.999)) /*truncates numbers. */exit                                   /*stick a fork in it,  we're all done. *//*────────────────────────────────────────────────────────────────────────────*/    Y: parse arg Y _; $= /*the Y combinator.*/ do j=1 for words(_); interpret '$=$' Y"("word(_,j)')'; end; return$  fib: procedure; parse arg x;  if x<2  then return x;   s=0;   a=0;    b=1       s=0;  a=0;  b=1;             do j=2  to x; s=a+b; a=b; b=s; end; return sdfact: procedure; parse arg x; !=1; do j=x  to 2  by -2; !=!*j; end;    return !tfact: procedure; parse arg x; !=1; do j=x  to 2  by -3; !=!*j; end;    return !qfact: procedure; parse arg x; !=1; do j=x  to 2  by -4; !=!*j; end;    return ! fact: procedure; parse arg x; !=1; do j=2  to x       ; !=!*j; end;    return !

output

    fib  12586269025
fib  144 89 55 34 21 13 8 5 3 2 1 1 0
fact  8320987112741390144276341183223364380754172606361245952449277696409600000000000000
fact  1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800
Dfact  8 15 48 105 384 945 3840 10395 46080 135135
Tfact  4 10 18 28 80 162 280 880 1944 3640
Qfact  4 5 12 21 32 3805072588800
length  4 3 2 5 11
reverse  32 876 7001 54 SAM I AM
trunc  -7 12 3 6 78


## Ruby

Using a lambda:

y = lambda do |f|  lambda {|g| g[g]}[lambda do |g|      f[lambda {|*args| g[g][*args]}]    end]end fac = lambda{|f| lambda{|n| n < 2 ? 1 : n * f[n-1]}}p Array.new(10) {|i| y[fac][i]}   #=> [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880] fib = lambda{|f| lambda{|n| n < 2 ? n : f[n-1] + f[n-2]}}p Array.new(10) {|i| y[fib][i]}   #=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Same as the above, using the new short lambda syntax:

Works with: Ruby version 1.9
y = ->(f) {->(g) {g.(g)}.(->(g) { f.(->(*args) {g.(g).(*args)})})} fac = ->(f) { ->(n) { n < 2 ? 1 : n * f.(n-1) } } p 10.times.map {|i| y.(fac).(i)} fib = ->(f) { ->(n) { n < 2 ? n : f.(n-2) + f.(n-1) } } p 10.times.map {|i| y.(fib).(i)}

Using a method:

Works with: Ruby version 1.9
def y(&f)  lambda do |g|    f.call {|*args| g[g][*args]}  end.tap {|g| break g[g]}end fac = y {|&f| lambda {|n| n < 2 ? 1 : n * f[n - 1]}}fib = y {|&f| lambda {|n| n < 2 ? n : f[n - 1] + f[n - 2]}} p Array.new(10) {|i| fac[i]}# => [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]p Array.new(10) {|i| fib[i]}# => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

The usual version using recursion, disallowed by the task:

y = lambda do |f|  lambda {|*args| f[y[f]][*args]}end

## Rust

Works with: Rust version 1.35.0 stable
//! A simple implementation of the Y Combinator// λf.(λx.xx)(λx.f(xx))// <=> λf.(λx.f(xx))(λx.f(xx)) // CREDITS: A better version of the previous code that was posted here, with detailed explanation.// See <y> and also <y_apply>. // A function type that takes its own type as an input is an infinite recursive type.// We introduce a trait that will allow us to have an input with the same type as self, and break the recursion.// The input is going to be a trait object that implements the desired function in the interface.// NOTE: We will be coercing a reference to a closure into this trait object. trait Apply<T, R> {  fn apply(    &self,    &Apply<T, R>,    T  ) -> R;} // In Rust, closures fall into three kinds: FnOnce, FnMut and Fn.// FnOnce assumed to be able to be called just once if it is not Clone. It is impossible to// write recursive FnOnce that is not Clone.// All FnMut are also FnOnce, although you can call them multiple times, they are not allow to// have a reference to themselves. So it is also not possible to write recursive FnMut closures// that is not Clone.// All Fn are also FnMut, and all closures of Fn are also Clone. However, programmers can create// Fn objects that are not Clone // This will work for all Fn objects, not just closures// And it is a little bit more efficient for Fn closures as it do not clone itself.impl<T, R, F> Apply<T, R> for F where F:  Fn(&Apply<T, R>, T) -> R{  fn apply(    &self,    f: &Apply<T, R>,    t: T  ) -> R {    self(f, t)     // NOTE: Each letter is an individual symbol.    // (λx.(λy.xxy))(λx.(λy.f(λz.xxz)y))t    // => (λx.xx)(λx.f(xx))t    // => (Yf)t  }} // This works for all closures that is Clone, and those are Fn.// impl<T, R, F> Apply<T, R> for F where F: FnOnce( &Apply<T, R>, T ) -> R + Clone {//     fn apply( &self, f: &Apply<T, R>, t: T ) -> R {//         (self.clone())( f, t ) //         // If we were to pass in self as f, we get -//         // NOTE: Each letter is an individual symbol.//         // λf.λt.sft//         // => λs.λt.sst [s/f]//         // => λs.ss//     }// } // Before 1.26 we have some limitations and so we need some workarounds. But now impl Trait is stable and we can// write the following: fn y<T,R>(f:impl Fn(&Fn(T) -> R, T) -> R) -> impl Fn(T) -> R {  move |t| (    |x: &Apply<T,R>, y| x.apply(x, y)  ) (    &|x: &Apply<T,R>, y| f(      &|z| x.apply(x,z),      y    ),    t  )} // fn y<T,R>(f:impl FnOnce(&Fn(T) -> R, T) -> R + Clone) -> impl FnOnce(T) -> R {//    |t| (|x: &Apply<T,R>,y| x.apply(x,y))//        (&move |x:&Apply<T,R>,y| f(&|z| x.apply(x,z), y), t) //     // NOTE: Each letter is an individual symbol.//     // (λx.(λy.xxy))(λx.(λy.f(λz.xxz)y))t//     // => (λx.xx)(λx.f(xx))t//     // => (Yf)t// } // Previous version removed as they are just hacks when impl Trait is not available. fn fac(n: usize) -> usize {  let almost_fac = |f: &Fn(usize) -> usize, x|    if x == 0 {      1    } else {      x * f(x - 1)    }  ;  let fac = y( almost_fac );  fac(n)} fn fib( n: usize ) -> usize {  let almost_fib = |f: &Fn(usize) -> usize, x|    if x < 2 {      1    } else {      f(x - 2) + f(x - 1)    };  let fib = y(almost_fib);  fib(n)} fn optimal_fib( n: usize ) -> usize {  let almost_fib = |f: &Fn((usize,usize,usize)) -> usize, (i0,i1,x)|     match x {      0 => i0,      1 => i1,      x => f((i1,i0+i1, x-1))    }          ;  let fib = |x| y(almost_fib)((1,1,x));  fib(n)} fn main() {  println!("{}", fac(10));  println!("{}", fib(10));  println!("{}", optimal_fib(10));}
Output:
3628800
89
89

## Scala

Credit goes to the thread in scala blog

def Y[A,B](f: (A=>B)=>(A=>B)) = {  case class W(wf: W=>A=>B) {    def apply(w: W) = wf(w)  }  val g: W=>A=>B = w => f(w(w))(_)  g(W(g))}

Example

val fac = Y[Int, Int](f => i => if (i <= 0) 1 else f(i - 1) * i)fac(6)  //> res0: Int = 720 val fib = Y[Int, Int](f => i => if (i < 2) i else f(i - 1) + f(i - 2))fib(6)  //> res1: Int = 8

## Scheme

(define Y                 ; (Y f) = (g g) where  (lambda (f)             ;         (g g) = (f  (lambda a (apply (g g) a)))    ((lambda (g) (g g))   ; (Y f) ==        (f  (lambda a (apply (Y f) a)))     (lambda (g)              (f  (lambda a (apply (g g) a)))))))  ;; head-recursive factorial(define fac                ; fac = (Y f) = (f      (lambda a (apply (Y f) a)))   (Y (lambda (r)           ;     = (lambda (x) ... (r     (- x 1)) ... )       (lambda (x)         ;        where   r    = (lambda a (apply (Y f) a))         (if (< x 2)       ;               (r ... ) == ((Y f) ... )             1             ;     == (lambda (x) ... (fac  (- x 1)) ... )             (* x (r (- x 1)))))))) ;; tail-recursive factorial(define fac2  (lambda (x)                ((Y (lambda (r)        ;       (Y f) == (f     (lambda a (apply (Y f) a)))           (lambda (x acc)  ;          r         == (lambda a (apply (Y f) a))            (if (< x 2)    ;         (r ... )   == ((Y f) ... )                acc                (r (- x 1) (* x acc))))))     x 1))) ; double-recursive Fibonacci(define fib  (Y (lambda (f)       (lambda (x)         (if (< x 2)             x             (+ (f (- x 1)) (f (- x 2)))))))) ; tail-recursive Fibonacci(define fib2  (lambda (x)    ((Y (lambda (f)          (lambda (x a b)            (if (< x 1)                a                (f (- x 1) b (+ a b))))))     x 0 1))) (display (fac 6))(newline) (display (fib2 134))(newline)
Output:
720
4517090495650391871408712937

If we were allowed to use recursion (with Y referring to itself by name in its body) we could define the equivalent to the above as

(define Yr        ; (Y f) == (f  (lambda a (apply (Y f) a)))  (lambda (f)    (f  (lambda a (apply (Yr f) a)))))

And another way is:

(define Y2r  (lambda (f)    (lambda a (apply (f (Y2r f)) a))))

Which, non-recursively, is

(define Y2                ; (Y2 f) = (g g) where  (lambda (f)             ;          (g g) = (lambda a (apply (f (g g)) a))    ((lambda (g) (g g))   ; (Y2 f) ==       (lambda a (apply (f (Y2 f)) a))     (lambda (g)       (lambda a (apply (f (g g)) a))))))

## Shen

(define y  F -> ((/. X (X X))        (/. X (F (/. Z ((X X) Z)))))) (let Fac (y (/. F N (if (= 0 N)                      1                      (* N (F (- N 1))))))  (output "~A~%~A~%~A~%"    (Fac 0)    (Fac 5)    (Fac 10)))
Output:
1
120
3628800

## Sidef

var y = ->(f) {->(g) {g(g)}(->(g) { f(->(*args) {g(g)(args...)})})} var fac = ->(f) { ->(n) { n < 2 ? 1 : (n * f(n-1)) } }say 10.of { |i| y(fac)(i) } var fib = ->(f) { ->(n) { n < 2 ? n : (f(n-2) + f(n-1)) } }say 10.of { |i| y(fib)(i) }
Output:
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]


## Slate

The Y combinator is already defined in slate as:

Method traits define: #Y &builder:  [[| :f | [| :x | f applyWith: (x applyWith: x)]	   applyWith: [| :x | f applyWith: (x applyWith: x)]]].

## Smalltalk

Works with: GNU Smalltalk
Y := [:f| [:x| x value: x] value: [:g| f value: [:x| (g value: g) value: x] ] ]. fib := Y value: [:f| [:i| i <= 1 ifTrue: [i] ifFalse: [(f value: i-1) + (f value: i-2)] ] ]. (fib value: 10) displayNl. fact := Y value: [:f| [:i| i = 0 ifTrue:  ifFalse: [(f value: i-1) * i] ] ]. (fact value: 10) displayNl.
Output:
55
3628800

The usual version using recursion, disallowed by the task:

Y := [:f| [:x| (f value: (Y value: f)) value: x] ].

## Standard ML

- datatype 'a mu = Roll of ('a mu -> 'a)  fun unroll (Roll x) = x   fun fix f = (fn x => fn a => f (unroll x x) a) (Roll (fn x => fn a => f (unroll x x) a))   fun fac f 0 = 1    | fac f n = n * f (n-1)   fun fib f 0 = 0    | fib f 1 = 1    | fib f n = f (n-1) + f (n-2);datatype 'a mu = Roll of 'a mu -> 'aval unroll = fn : 'a mu -> 'a mu -> 'aval fix = fn : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'bval fac = fn : (int -> int) -> int -> intval fib = fn : (int -> int) -> int -> int- List.tabulate (10, fix fac);val it = [1,1,2,6,24,120,720,5040,40320,362880] : int list- List.tabulate (10, fix fib);val it = [0,1,1,2,3,5,8,13,21,34] : int list

The usual version using recursion, disallowed by the task:

fun fix f x = f (fix f) x

## SuperCollider

Like Ruby, SuperCollider needs an extra level of lambda-abstraction to implement the y-combinator. The z-combinator is straightforward:

// z-combinator(z = { |f|	{ |x| x.(x) }.(		{ |y|			f.({ |args| y.(y).(args) })		}	)};) // the same in a shorter form (r = { |x| x.(x) };z = { |f| r.({ |y| f.(r.(y).(_)) }) };)  // factorialk = { |f| { |x| if(x < 2, 1, { x * f.(x - 1) }) } }; g = z.(k); g.(5) // 120 (1..10).collect(g) // [ 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 ]   // fibonacci k = { |f| { |x| if(x <= 2, 1, { f.(x - 1) + f.(x - 2) }) } }; g = z.(k); g.(3) (1..10).collect(g) // [ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]

## Swift

Using a recursive type:

struct RecursiveFunc<F> {  let o : RecursiveFunc<F> -> F} func Y<A, B>(f: (A -> B) -> A -> B) -> A -> B {  let r = RecursiveFunc<A -> B> { w in f { w.o(w)($0) } } return r.o(r)} let fac = Y { (f: Int -> Int) in {$0 <= 1 ? 1 : $0 * f($0-1) }}let fib = Y { (f: Int -> Int) in  { $0 <= 2 ? 1 : f($0-1)+f($0-2) }}println("fac(5) = \(fac(5))")println("fib(9) = \(fib(9))") Output: fac(5) = 120 fib(9) = 34  Without a recursive type, and instead using Any to erase the type: Works with: Swift version 1.2+ (for Swift 1.1 replace as! with as) func Y<A, B>(f: (A -> B) -> A -> B) -> A -> B { typealias RecursiveFunc = Any -> A -> B let r : RecursiveFunc = { (z: Any) in let w = z as! RecursiveFunc; return f { w(w)($0) } }  return r(r)}

The usual version using recursion, disallowed by the task:

func Y<In, Out>( f: (In->Out) -> (In->Out) ) -> (In->Out) {    return { x in f(Y(f))(x) }}

 // YCombinator is not needed since tailspin supports recursion readily, but this demonstrates passing functions as parameters templates [email protected]{stepper:}  templates [email protected]{rec:}    $it -> [email protected]{next: [email protected]{rec: rec}} ! end makeStep$it -> [email protected]{rec: makeStep} !end combinator templates factorial  templates [email protected]{next:}    <0> 1 !    <>      $it * ($it - 1 -> next) !  end seed  $it -> [email protected]{stepper: seed} !end factorial 5 -> factorial -> 'factorial 5:$it;' -> stdout templates fibonacci  templates [email protected]{next:}    <..1> $it ! <> ($it -2 -> next) + ($it - 1 -> next) ! end seed$it -> [email protected]{stepper: seed} !end fibonacci 5 -> fibonacci -> 'fibonacci 5: $it;' -> stdout  Output: factorial 5: 120 fibonacci 5: 5  ## Tcl Y combinator is derived in great detail here. ## TXR This prints out 24, the factorial of 4: ;; The Y combinator:(defun y (f) [(op @1 @1) (op f (op [@@1 @@1]))]) ;; The Y-combinator-based factorial:(defun fac (f) (do if (zerop @1) 1 (* @1 [f (- @1 1)]))) ;; Test:(format t "~s\n" [[y fac] 4]) Both the op and do operators are a syntactic sugar for currying, in two different flavors. The forms within do that are symbols are evaluated in the normal Lisp-2 style and the first symbol can be an operator. Under op, any forms that are symbols are evaluated in the Lisp-2 style, and the first form is expected to evaluate to a function. The name do stems from the fact that the operator is used for currying over special forms like if in the above example, where there is evaluation control. Operators can have side effects: they can "do" something. Consider (do set a @1) which yields a function of one argument which assigns that argument to a. The compounded @@... notation allows for inner functions to refer to outer parameters, when the notation is nested. Consider (op foo @1 (op bar @2 @@2)) . Here the @2 refers to the second argument of the anonymous function denoted by the inner op. The @@2 refers to the second argument of the outer op. ## Ursala The standard y combinator doesn't work in Ursala due to eager evaluation, but an alternative is easily defined as shown (r "f") "x" = "f"("f","x")my_fix "h" = r ("f","x"). ("h" r "f") "x" or by this shorter expression for the same thing in point free form. my_fix = //~&R+ ^|H\~&+ ; //~&R Normally you'd like to define a function recursively by writing $f=h(f)$, where $h(f)$ is just the body of the function with recursive calls to $f$ in it. With a fixed point combinator such as my_fix as defined above, you do almost the same thing, except it's $f=$my_fix "f". $h$("f"), where the dot represents lambda abstraction and the quotes signify a dummy variable. Using this method, the definition of the factorial function becomes #import nat fact = my_fix "f". ~&?\1! product^/~& "f"+ predecessor To make it easier, the compiler has a directive to let you install your own fixed point combinator for it to use, which looks like this, #fix my_fix with your choice of function to be used in place of my_fix. Having done that, you may express recursive functions per convention by circular definitions, as in this example of a Fibonacci function. fib = {0,1}?</1! sum+ fib~~+ predecessor^~/~& predecessor Note that this way is only syntactic sugar for the for explicit way shown above. Without a fixed point combinator given in the #fix directive, this definition of fib would not have compiled. (Ursala allows user defined fixed point combinators because they're good for other things besides functions.) To confirm that all this works, here is a test program applying both of the functions defined above to the numbers from 1 to 8. #cast %nLW examples = (fact* <1,2,3,4,5,6,7,8>,fib* <1,2,3,4,5,6,7,8>) Output: ( <1,2,6,24,120,720,5040,40320>, <1,2,3,5,8,13,21,34>) The fixed point combinator defined above is theoretically correct but inefficient and limited to first order functions, whereas the standard distribution includes a library (sol) providing a hierarchy of fixed point combinators suitable for production use and with higher order functions. A more efficient alternative implementation of my_fix would be general_function_fixer 0 (with 0 signifying the lowest order of fixed point combinators), or if that's too easy, then by this definition. #import sol #fix general_function_fixer 1 my_fix "h" = "h" my_fix "h" Note that this equation is solved using the next fixed point combinator in the hierarchy. ## VBA Translation of: Phix The IIf as translation of Iff can not be used as IIf executes both true and false parts and will cause a stack overflow. Private Function call_fn(f As String, n As Long) As Long call_fn = Application.Run(f, f, n)End Function Private Function Y(f As String) As String Y = fEnd Function Private Function fac(self As String, n As Long) As Long If n > 1 Then fac = n * call_fn(self, n - 1) Else fac = 1 End IfEnd Function Private Function fib(self As String, n As Long) As Long If n > 1 Then fib = call_fn(self, n - 1) + call_fn(self, n - 2) Else fib = n End IfEnd Function Private Sub test(name As String) Dim f As String: f = Y(name) Dim i As Long Debug.Print name For i = 1 To 10 Debug.Print call_fn(f, i); Next i Debug.PrintEnd Sub Public Sub main() test "fac" test "fib"End Sub Output: fac 1 2 6 24 120 720 5040 40320 362880 3628800 fib 1 1 2 3 5 8 13 21 34 55  ## Verbexx /////// Y-combinator function (for single-argument lambdas) /////// y @FN [f]{ @( x -> { @f (z -> {@(@x x) z}) } ) // output of this expression is treated as a verb, due to outer @( ) ( x -> { @f (z -> {@(@x x) z}) } ) // this is the argument supplied to the above verb expression}; /////// Function to generate an anonymous factorial function as the return value -- (not tail-recursive) /////// fact_gen @FN [f]{ n -> { (n<=0) ? {1} {n * (@f n-1)} }}; /////// Function to generate an anonymous fibonacci function as the return value -- (not tail-recursive) /////// fib_gen @FN [f]{ n -> { (n<=0) ? { 0 } { (n<=2) ? {1} { (@f n-1) + (@f n-2) } } }}; /////// loops to test the above functions /////// @VAR factorial = @y fact_gen;@VAR fibonacci = @y fib_gen; @LOOP init:{@VAR i = -1} while:(i <= 20) next:{i++}{ @SAY i "factorial =" (@factorial i) }; @LOOP init:{ i = -1} while:(i <= 16) next:{i++}{ @SAY "fibonacci<" i "> =" (@fibonacci i) }; ## Vim Script There is no lambda in Vim (yet?), so here is a way to fake it using a Dictionary. This also provides garbage collection. " Translated from Python. Works with: Vim 7.0 func! Lambx(sig, expr, dict) let fanon = {'d': a:dict} exec printf(" \func fanon.f(%s) dict\n \ return %s\n \endfunc", \ a:sig, a:expr) return fanonendfunc func! Callx(fanon, arglist) return call(a:fanon.f, a:arglist, a:fanon.d)endfunc let g:Y = Lambx('f', 'Callx(Lambx("x", "Callx(a:x, [a:x])", {}), [Lambx("y", ''Callx(self.f, [Lambx("...", "Callx(Callx(self.y, [self.y]), a:000)", {"y": a:y})])'', {"f": a:f})])', {}) let g:fac = Lambx('f', 'Lambx("n", "a:n<2 ? 1 : a:n * Callx(self.f, [a:n-1])", {"f": a:f})', {}) echo Callx(Callx(g:Y, [g:fac]), )echo map(range(10), 'Callx(Callx(Y, [fac]), [v:val])')  Update: since Vim 7.4.2044 (or so...), the following can be used (the feature check was added with 7.4.2121):  if !has("lambda") echoerr 'Lambda feature required' finishendiflet Y = {f -> {x -> x(x)}({y -> f({... -> call(y(y), a:000)})})}let Fac = {f -> {n -> n<2 ? 1 : n * f(n-1)}} echo Y(Fac)(5)echo map(range(10), 'Y(Fac)(v:val)')  Output: 120 [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880] ## Wart # Better names due to Jim Weirich: http://vimeo.com/45140590def (Y improver) ((fn(gen) gen.gen) (fn(gen) (fn(n) ((improver gen.gen) n)))) factorial <- (Y (fn(f) (fn(n) (if zero?.n 1 (n * (f n-1)))))) prn factorial.5 ## XQuery Version 3.0 of the XPath and XQuery specifications added support for function items. let$Y := function($f) { (function($x) { ($x)($x) })( function($g) {$f( (function($a) {$g($g) ($a)})  ) } )  }let $fac :=$Y(function($f) { function($n) { if($n < 2) then 1 else$n * $f($n - 1) } })let $fib :=$Y(function($f) { function($n) { if($n <= 1) then$n else $f($n - 1) + $f($n - 2) } })return (    $fac(6),$fib(6))
Output:
720 8

## Yabasic

sub fac(self$, n) if n > 1 then return n * execute(self$, self$, n - 1) else return 1 end ifend sub sub fib(self$, n)    if n > 1 then        return execute(self$, self$, n - 1) + execute(self$, self$, n - 2)    else        return n    end ifend sub sub test(name$) local i print name$, ": ";    for i = 1 to 10        print execute(name$, name$, i);    next    printend sub test("fac")test("fib")

## zkl

fcn Y(f){ fcn(g){ g(g) }( 'wrap(h){ f( 'wrap(a){ h(h)(a) }) }) }

Functions don't get to look outside of their scope so data in enclosing scopes needs to be bound to a function, the fp (function application/cheap currying) method does this. 'wrap is syntactic sugar for fp.

fcn almost_factorial(f){ fcn(n,f){ if(n<=1) 1 else n*f(n-1) }.fp1(f) }Y(almost_factorial)(6).println();[0..10].apply(Y(almost_factorial)).println();
Output:
720
L(1,1,2,6,24,120,720,5040,40320,362880,3628800)

fcn almost_fib(f){ fcn(n,f){ if(n<2) 1 else f(n-1)+f(n-2) }.fp1(f) }Y(almost_fib)(9).println();[0..10].apply(Y(almost_fib)).println();
Output:
55
L(1,1,2,3,5,8,13,21,34,55,89)