Anonymous Wrapper Functions Revisited

Some definitions:

In [1]:

# I made the fixed-point combinator using recursion for simplicity
function fix(fn)
    Z = fn( (input...) -> Z(input...) ) # named after the strict Z combinator (which I'm using)
end

Out[1]:

fix (generic function with 1 method)

In [2]:

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

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

Out[2]:

(anonymous function)

In [3]:

fix(fac)(6)

Out[3]:

720

In [4]:

fix(fib)(5)

Out[4]:

5

More wrappers:

Now to do something interesting. I want to make a trace wrapper that will print out the function name with its arguments whenever its called. First I make a type. The name holds the function name as a string. The funcall element holds the anonymous definition. Eventually I'd like to do this with mutually recursive functions.

In [5]:

type Function
    name
    funcall
end

In [6]:

function trace(f)
    (Yf) -> (input) -> begin
        output = f.funcall(Yf)(input)
        println(f.name, "(", input, ") = ", output)
        output
    end
end

Out[6]:

trace (generic function with 1 method)

In [7]:

fix( trace( Function("factorial", fac) ) )(8)

factorial(1) = 1
factorial(2) = 2
factorial(3) = 6
factorial(4) = 24
factorial(5) = 120
factorial(6) = 720
factorial(7) = 5040
factorial(8) = 40320

Out[7]:

40320

Beautiful!

In [8]:

fix( trace( Function("fibonacci", fib) ) )(6)

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(1) = 1
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(1) = 1
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(1) = 1
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8

Out[8]:

8

Eh...less beautiful but still cool. Obviously memoization is needed to keep fibonacci from being exponential.

In [9]:

function memoize(f)
    inputs = []
    outputs = []

    (Yf) -> (input) -> begin
        # test to see if input already given
        match = find( (elem)->(elem == input), inputs )

        if length(match) == 0
            # result hasn't been found
            output = f(Yf)(input)
            inputs = [inputs, input]
            outputs = [outputs, output]
        else
            # result has already been memoized
            output = outputs[match[1]]
        end

        output
    end
end

Out[9]:

memoize (generic function with 1 method)

I like this version of memoization much better than my previous version. It's nowhere near as cluttered.

In [10]:

fix( memoize( trace( Function("fibonacci", fib) ) ) )(6)

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8

Out[10]:

8

Yeeeeessssssssss!!!! Okay the fixed-point combinator has the ability to work with multiple inputs. How about a tail recursive fibonacci function?

Multiple inputs:

In [11]:

fib_tail = (fib) -> (n, a, b) -> if (n < 2) b else fib(n-1, b, a+b) end

Out[11]:

(anonymous function)

In [12]:

fix(fib_tail)(100, 0, 1)

Out[12]:

3736710778780434371

In [13]:

@time fix(fib_tail)(100, 0, 1)

elapsed time: 0.002422741 seconds (19344 bytes allocated)

Out[13]:

3736710778780434371

In [14]:

# better trace wrapper for functions with multiple inputs
function trace_(f)
    (Yf) -> (input...) -> begin
        println(f.name, input)
        f.funcall(Yf)(input...)
    end
end

Out[14]:

trace_ (generic function with 1 method)

In [15]:

fix( trace_( Function("fib", fib_tail) ) )(6, 0, 1)

fib(6,0,1)
fib(5,1,1)
fib(4,1,2)
fib(3,2,3)
fib(2,3,5)
fib(1,5,8)

Out[15]:

8