Anonymous Recursive Wrappers

So I recently came across fixed point combinators in lambda calculus. Fixed point combinators allow you to implement recursion while still using anonymous functions. It's a really slick technique for implementing recursion. I decided to try it out using Julia, a dynamic programming language I've been using for a while.

To start take an anonymous function that takes another function as input as well as another variable.

fac_ = f -> n -> if (n < 2) 1 else n*f(n-1) end

In Julia's syntax f is a function to be input to the base fac_. Similarly n is to be input next. The base function is called as:

fac_( some_other_func() )(n)

where some_other_func can be literally any other function and n is an integer. To keep things simple input the null function into fac_. The null function is the function taking no inputs and providing no outputs.

() -> ()

We can now call the base function for the values of 0 and 1.

fac_( () -> () )(0) =>

1

fac_( () -> () )(1) =>

1

 If we try to input 2 or any other number we get ERROR: wrong number of arguments. This is because the if condition in the base function fails, so it tries to input n-1 into the null function - which doesn't take any arguments. The simplest fix is to input the base function into itself. Once the first if statement fails it will evaluate the second base function fac_. This allows to calculate 2 factorial. If we string together base functions we can calculate factorials of any size input.

fac_(fac_(fac_(fac_(fac_( () -> () )))))(n)

This is terribly inefficient, but it works. Each base is a crappy function that only computes so many factorials. Taking the fac_ of this chain gives us a slightly less crappy version. Obviously a perfect factorial function could self apply itself an infinite number of times if necessary. Therefore we know the factorial function is:

fac = fac_(fac_(...inifinitely many base functions...))

We also know that if we apply the base function to the regular factorial we'll just get the regular factorial right back. This means the factorial function is the solution to the fixed point problem fac_(fac) = fac. Amazingly we can construct the fixed point combinator that will immediately solve for fac.

fix(fac_) = fac_( fix(fac_) )

The fixed point combinator (also known as the Y combinator) takes the base function and a variable as input. It then self applies the base function to itself allowing you to construct the infinite tower of base functions.

U = f -> f(f) # self applicator

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

While theoretically possible to implement, the standard fixed point combinator thought up by Haskell Curry is hard to implement in practice due to eager evaluation by Julia. It can be fixed by inserting an extra number to be input that prevents the Y combinator from being evaluated instantly. The simplest implementation is:

fix = f -> g = f( (x...) -> g(x...) )

fix(fac_)(5) =>

120

Now we can define fac = fix(fac_) which works for all inputs.

If that wasn't cool enough we can also define wrapper functions as described here. These wrapper functions can modify the function at runtime and at every single computational step. You can print the input values, print the output values, check the types on variables, do bounds checks, or even memoize results.

For printing results, catch all the  parameters, print what you want, and then return the result of evaluating the expression last.

printInput = base -> func -> (args...) ->

        (println(args...);

        base(func)(args...))

printOutput = base -> func -> (args...) ->
        (result = base(func)(args...);

        println(result);

        result)

fix(printOutput(fac_))(5) =>

1
2
6
24
120
120

Errors doing anonymous recursion are nearly impossible to decipher. I spent countless hours trying to track down my mistakes when first writing these functions. To do custom error checking, catch the inputs and provide the error you want.

nonnegative = base -> func -> n -> if (n < 0)
        error("input must be nonnegative")
        else base(func)(n) end

integersOnly = base -> func -> n -> if (typeof(n) != Int)
        error("input must be an integer")
        else base(func)(n) end

fix(integersOnly(nonnegative(fac_)))("hello") =>

ERROR: input must be an integer

fix(integersOnly(nonnegative(fac_)))(-1)

ERROR: input must be nonnegative

It's also possible to provide memoization for these recursive functions.  The main thing to do is create a cache that stores inputs and outputs. I chose to use an array with each input first and the result second. I first created a helper function to search the cache for previous results.

function look_up(a, n)
        if (length(a) == 0) return nothing end

        for i = 1:(length(a)/2)
                if (a[2*i-1] == n) return a[2*i] end

                # 2*i-1 gets odd indexed elements

                # 2*i gets even indexed elements
        end

        return nothing # if value not found
end

Now to carry out the memoized version I create an empty cache, lookup entries each iteration, return previous results if they're been computed, and calculate new entries.

memoize = base ->
        let cache = []
                func -> arg ->
                let val = look_up(cache,arg)
                        if (val == nothing)
                        let result = base(func)(arg)
                                if (length(cache) == 0) cache = [arg result] # first time through

                                else cache = [cache [arg result]] end
                                result # return to function above
                        end
                        else val end
                end
        end

fib_ = f -> n -> if (n < 2) n else f(n-1)+f(n-2) end

@time fix(memoize(fib_))(164) =>

elapsed time: 0.001400088 seconds (298952 bytes allocated)
7278316983633677837

(edit: I just realized that the standard int implementation here can only compute fibonacci numbers up to 92 before overflow kicks in => this answer is wrong, but the time is all I care about, and I'm too lazy to rerun it haha)