# Julia Language Combinators The Y or Z Combinator

## Example

Although Julia is not a purely functional language, it has full support for many of the cornerstones of functional programming: first-class functions, lexical scope, and closures.

The fixed-point combinator is a key combinator in functional programming. Because Julia has eager evaluation semantics (as do many functional languages, including Scheme, which Julia is heavily inspired by), Curry's original Y-combinator will not work out of the box:

``````Y(f) = (x -> f(x(x)))(x -> f(x(x)))
``````

However, a close relative of the Y-combinator, the Z-combinator, will indeed work:

``````Z(f) = x -> f(Z(f), x)
``````

This combinator takes a function and returns a function that when called with argument `x`, gets passed itself and `x`. Why would it be useful for a function to be passed itself? This allows recursion without actually referencing the name of the function at all!

``````fact(f, x) = x == 0 ? 1 : x * f(x)
``````

Hence, `Z(fact)` becomes a recursive implementation of the factorial function, despite no recursion being visible in this function definition. (Recursion is evident in the definition of the `Z` combinator, of course, but that is inevitable in an eager language.) We can verify that our function indeed works:

``````julia> Z(fact)(10)
3628800
``````

Not only that, but it is as fast as we can expect from a recursive implementation. The LLVM code demonstrates that the result is compiled into a plain old branch, subtract, call, and multiply:

``````julia> @code_llvm Z(fact)(10)

define i64 @"julia_#1_70252"(i64) #0 {
top:
%1 = icmp eq i64 %0, 0
br i1 %1, label %L11, label %L8

L8:                                               ; preds = %top
%2 = add i64 %0, -1
%3 = call i64 @"julia_#1_70060"(i64 %2) #0
%4 = mul i64 %3, %0
br label %L11

L11:                                              ; preds = %top, %L8
%"#temp#.0" = phi i64 [ %4, %L8 ], [ 1, %top ]
ret i64 %"#temp#.0"
}
`````` PDF - Download Julia Language for free