Lisp orginally had no object oriented features, but it was able to add them in later without changing the language itself through a clever use of macros and closures.

Julia however already has some elements of OOP built in like subtype polymorphism, multiple dispatch, container types with constructors, and methods. One thing Julia currently doesn't have is encapsulation. However, Julia's closures allow us to simulate encapsulation just like they do in Lisp.

First, we create a type with all the members we want private and another one for the ones we want public. Next, we make a class constructor with an object defined inside it with private member type. Then, we write the functions we want to be public - letting them close over the internal private variables/functions. Finally, we assign these functions to the external object.

Class Definition

In [1]:

## Private members
type Rectangle_Private
    width
    height
    area
end

In [2]:

## Public members
type Rectangle
    set_values
    get_area
end

In [3]:

## Class instance
function makeClass(object::Rectangle)
    self = Rectangle_Private(1,1,1) # constructor with default values
    
    # functions below close over internal environment
    function set_values(w, h)
        (self.width, self.height) = (w, h)
        self.area = w*h
    end
    
    function get_area()
        self.area
    end
    
    (object.set_values, object.get_area) = (set_values, get_area)
end

Out[3]:

makeClass (generic function with 1 method)

Instantiation

In [4]:

myRect1 = Rectangle(nothing, nothing) # constructor with empty args
makeClass(myRect1) # actual instantiation

Out[4]:

(set_values,get_area)

In [5]:

myRect2 = Rectangle(nothing, nothing)
makeClass(myRect2)

Out[5]:

(set_values,get_area)

Usage

In [6]:

myRect1.set_values(1, 2)
myRect2.set_values(3, 4)

Out[6]:

Note: Separate objects have separate internal members as we expected

In [7]:

myRect1.get_area()

Out[7]:

In [8]:

myRect2.get_area()

Out[8]:

In [9]:

myRect1 # type info

Out[9]:

Rectangle(set_values,get_area)

Technically speaking the set_values and get_area fields in type Rectangle are different names from the internal ones defined in makeClass. I named them identically for convenience. It would be distracting to see it named something else.

In [10]:

myRect1.get_area

Out[10]:

get_area (generic function with 1 method)

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) =>

fac_( () -> () )(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)

Idiot's Blackboard

Monday, January 19, 2015

Encapsulation Test

Class Definition

Instantiation

Usage

Thursday, January 1, 2015

Anonymous Recursive Wrappers

Test Post

Blog Archive