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 :)
Posted by at

3 comments:

  1. Chris HellerJuly 8, 2011 at 11:11 AM

    Hi Bill,

    Nice hack. A further exploration into what it takes to target your code to the LLVM would be very interesting!

    For fun, I thought I would share with you a Lambda Calculator I made a few years ago. This one has a JavaScript evaluator, and uses the DOM for input and the environment:

    http://hellertime.github.com/lambda.js/prelude.html

    Needless to say, entering lambda expressions is rather tedious!

    ReplyDelete
  2. This Statement Is FalseJuly 8, 2011 at 11:22 AM

    Very cool! I didn't see yours when I went searching all over the place a couple months ago.

    I started on the LLVM code gen, but it's mostly notes, at this point. I haven't committed that yet, but to do it, I have a wrapper that runs in node.js. Eventually, I'd like to make LC self-hosting :), but for the first rev, you'll need node.js and LLVM.

    ReplyDelete
  3. This Statement Is FalseMarch 24, 2012 at 3:36 PM

    BTW, this is going somewhere; I'm making a standalone language, called Lazp -- check out this post: http://this-statement-is-false.blogspot.com/2012/03/lazp-untyped-lazy-functional-language.html

    ReplyDelete

Subscribe to: Post Comments (Atom)