codekansas

A blog of language, neuroscience, and deep learning

Functional Programming, LISP, and Compilers

If you’re reading this, you’ve probably heard something or another about Lisp, Scheme, Racket, Haskell or some other language, and you may or may not have used it (for example, in a compilers class in college). Functional programming is cool, and definitely worth exploring more, even if it’s just to geek out about and not for any practical purposes. I’m going to assume a very basic understanding of computer science, but most examples will have a bit about how to get them running.

I’m going to give a (very slanted) perspective on functional programming languages, specifically Lisp. To understand my perspective, you need to know about something called the Abstract Syntax Tree (AST). The AST is the intermediary form which most programming languages are converted to before they can be compiled to assembly or byte code. I think it’s usually easier to see examples, so here’s an example using a pretty simple C program for computing Fibonacci numbers:

#include <stdio.h>

int fib(int n) {
  int a = 1, b = 1, t, i;
  for (i = 2; i < n; i++) {
    t = a;
    a = b;
    b = t + b;
  }
  return b;
}

void main() {
  printf("%d\n", fib(12));
}

To run this program, copy and paste it into a file and do something like gcc fib.c && ./a.out to compile and run the program (note that this requires installing the Gnome Compiler Collection, gcc).

So, back to the Abstract Syntax Tree. The AST is an abstract representation of the program which defines how the program can be parsed and traversed during execution. In a full AST, each node will have extra metadata defining it’s type, but the graph below gives a rough representation of the AST for this program. When the program is compiled, an AST is generated from the text, which is then used to do some optimizations before finally generating the byte or assembly code defining the executable program itself.

This intermediary representation is important, because it makes it easy to do things like check variable scoping (in other words, that you don’t use a function or variable which you haven’t previously defined) or perform optimizations by caching common subtrees, moving around nodes and parsing dependencies.

If you were designing a programming language, and knew that, during compilation, you needed to eventually convert the program into an AST before compiling it, you might think it would be a good idea to make your programming language as similar to an AST as possible. This is what Lisp is! In Lisp (and it’s closely related cousin Scheme) the number of open parentheses corresponds directly to the depth in the corresponding AST.

Perhaps notably, in a functional programming language, you usually try to avoid using loops as much as possible. It forces you to think about problems in a different way, usually using recursion. This comes with some annoying things to think about. Let’s write a simple program in Scheme to do what our original C program above did. If you want to avoid installing Scheme on your local computer to run this code, you can use this cool online interpreter.

(define fib
  (lambda (n)
    (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2))))))

(display (fib 12))

Wow, that’s much more simple than the corresponding AST in C! And, hopefully, it is easier to see how it maps onto the program itself. But can you spot what’s wrong with this implementation? If you try putting in a much larger number, the program will start going very, very slowly (in fact, in O(2^n) time). If we want to write good programs in Scheme, we need to be cleverer about how we do recursion. The program below is a tail recursive version of the Fibonacci Scheme program above:

(define fib
  (lambda (n)
    (define fib-aux
      (lambda (n a b)
        (if (= n 0)
          a
          (fib-aux (- n 1) b (+ a b)))))
    (fib-aux n 0 1)))

(display (fib 12))

Hy

There is a really cool project that I came across on Github a couple months ago called Hy, which bills itself as “a dialect of Lisp that’s embedded in Python”. Before I dive into the actual point of this post (using Hy to build neural networks more expressively), I’d like to show you another example program, this time using Python and Hy.

Installation

The best way to install the required components for this is probably to do:

pip install virtualenv                # Installs virtualenv
virtualenv --python=python3.5 venv    # Creates a new virtual environment
source venv/bin/activate              # Activates that environment
pip3 install hy                       # Installs Hy
pip3 install torch torchvision        # Installs PyTorch

After doing that, you should be able to start the Hy interpreter (I’m running with PyTorch 0.4 on my Mac).

$ hy
hy 0.14.0 using CPython(default) 3.5.1 on Darwin
=> (import torch)
=> (print torch.__version__)
0.4.0

Fibonacci Example

Here is a Python implementation of our C function to compute Fibonacci numbers.

def fib(n):
  '''Loop implementation.'''
  a, b = 1, 1
  for i in range(2, n):
    a, b = b, a + b
  return b

def fib(n):
  '''Naive recursive implementation.'''
  return 1 if n < 3 else fib(n - 1) + fib(n - 2)

def fib(n):
  '''Tail-recursive implementation.'''
  fib_aux = lambda n, a, b: a if n == 0 else fib_aux(n - 1, b, a + b)
  return fib_aux(n, 0, 1)

print(fib(12))

Like before, we can rewrite this function using Hy. If you want to go much more into the details of the language (which you should!), check out the documentation.

(defn fib [n]
  (defn fib-aux [n a b]
    (if (= n 0)
      a
      (fib-aux (- n 1) b (+ a b))))
  (fib-aux n 0 1))

(print (fib 12))

It’s kind of cool to see how the Hy code corresponds to the Python code. Hy is interoperable with Python because it simply gets converted to a Python AST, meaning that you can import Hy functions in Python and vice versa. Pretty neat!

Neural Networks

Ok, now that we have an understanding of Hy and functional programming, let’s get into the weeds of what this post is actually about - extending functional programming to neural networks.

MNIST Example

Let’s replicate the MNIST example from the PyTorch repo using Hy. However, we’re going to do it using our new “functional” programming language, so it won’t exactly be a one-to-one mapping.

WORK IN PROGRESS