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"
}
