Friday, July 8, 2011

Applied Lambda Calculus

I made a slide presentation introducing Lambda Calculus and some functional concepts (lazy evaluation, how to represent data, etc.). It also talks about a Lambda Calculator I wrote, which does LC in three ways:
  • compiles into JavaScript
  • interprets through substitution (alpha, beta, and eta) and shows the steps
  • compiles into virtual machine code (and can execute it)
The VM still fails on some complex cases, but when I have that working, I want to make it generate native code, using LLVM.

I open sourced all this, under the ZLIB license.

Oh, I also started on a Lambda Calculus version of space invaders, which is in there, too :)

LC is a really nice language. I wasn't able to find a modern, untyped, lazy language. It seems like functional languages have all gone the way of static typing, but I'm hoping it doesn't have to end that way. Looking at what Anders Møller and co. are doing with TAJS at Aarhus University and BRICS gives me hope that some day, the computer will tell the type information to the programmer and not the other way around like it is, today.

So I wrote my own "Lambda Calculator." Really, it was so I could teach a friend about computers, but I am relatively new to LC and I thought I really ought to write something in it, which is why I chose Space Invaders. So far, I have 55 lines of space invader code written. It doesn't do all that much, but I think it's still informative. In the mean time, I had to make that slide presentation and fix bugs in the calculator.

I had a lot of fun writing space invaders and I think I'm starting to understand the power of having lazy evaluation, currying, etc. built into a language (shame on me for not using Haskell, yet). Check out the slides for more info :)