Julia Language Combinators The Y or Z Combinator


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)

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 {
  %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"