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

Playing with streams in Julia

Delays and yields:

We need two definitions to make streams work. First, delay is a macro that replaces a function with an anonymous function with it's body equal to the function. Later when we need to evaluate the function, we only have to call the anonymous function. This is what yield does. Yield isn't as necessary, but it makes it clear what's happening.

In [1]:

macro delay(f)
    return quote
        # put the function inside a lambda
        function ()
            $f
        end
    end
end

In [2]:

function yield(delayed_function)
    delayed_function() # call it
end

Out[2]:

yield (generic function with 1 method)

In [3]:

something = @delay(println("text"))

Out[3]:

(anonymous function)

In [4]:

yield(something)

text

Making a stream type:

Now with that done we create a stream type. The first element is the actual value held there. The second element is a delayed stream constructor. We then create head and tail to access elements of the stream. Nth takes successive head and tails of a stream.

In [5]:

type IntStream
    literal
    next

    function IntStream(num)
        self = new()
        self.literal = num
        self.next = @delay(IntStream(num+1))
        return self
    end
end

In [6]:

function head(item::IntStream)
    return item.literal
end

Out[6]:

head (generic function with 1 method)

In [7]:

function tail(item::IntStream)
    return yield(item.next)
end

Out[7]:

tail (generic function with 1 method)

In [8]:

integers = IntStream(1)

Out[8]:

IntStream(1,(anonymous function))

In [9]:

head(integers)

Out[9]:

1

In [10]:

head(tail(tail(integers)))

Out[10]:

3

In [11]:

function nth(stream, n)
    if n == 1
        return head(stream)
    else
        return nth(tail(stream), n-1)
    end
end

Out[11]:

nth (generic function with 1 method)

In [12]:

nth(integers, 50)

Out[12]:

50

More general definitions:

For more general streams it is simple to add a next method for each object.

In [13]:

type Stream
    obj
    next
    
    function Stream(obj, next) # next is the method for generating the next object
        self = new()
        self.obj = obj
        self.next = @delay(Stream(next(obj), next))
        return self
    end
end

In [14]:

function head(item::Stream)
    return item.obj
end

Out[14]:

head (generic function with 2 methods)

In [15]:

function tail(item::Stream)
    return yield(item.next)
end

Out[15]:

tail (generic function with 2 methods)

In [16]:

function nth(stream, n)
    if n == 1
        return head(stream)
    else
        return nth(tail(stream), n-1)
    end
end

Out[16]:

nth (generic function with 1 method)

Fibonacci list stream:

Now to try it on the Fibonacci numbers. Instead of making each element the nth Fibonacci number we'll make it the list of the first n+1 Fibonacci numbers.

In [17]:

function next_fib_list(list)
    return [ list, (list[end] + list[end-1]) ]
end

Out[17]:

next_fib_list (generic function with 1 method)

In [18]:

fib_list = Stream([0, 1], next_fib_list)

Out[18]:

Stream([0,1],(anonymous function))

In [19]:

nth(fib_list, 5)

Out[19]:

6-element Array{Int64,1}:
 0
 1
 1
 2
 3
 5

In [20]:

nth(fib_list, 10)

Out[20]:

11-element Array{Int64,1}:
  0
  1
  1
  2
  3
  5
  8
 13
 21
 34
 55

In [21]:

for idx = 1:15
    println(nth(fib_list, idx))
end

[0,1]
[0,1,1]
[0,1,1,2]
[0,1,1,2,3]
[0,1,1,2,3,5]
[0,1,1,2,3,5,8]
[0,1,1,2,3,5,8,13]
[0,1,1,2,3,5,8,13,21]
[0,1,1,2,3,5,8,13,21,34]
[0,1,1,2,3,5,8,13,21,34,55]
[0,1,1,2,3,5,8,13,21,34,55,89]
[0,1,1,2,3,5,8,13,21,34,55,89,144]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]

It is also possible to memoize the function calls so that expensive operations aren't run more than once.