Lemur Scheme

• It’s way more fun than programming for work.
• You feel super-smart, even when you’re just implementing boolean?.
• The moment when you can start writing your language in your language feels like getting a new puppy.

In my last post, I made this assumption:

The closure’s only supposed to capture the environment at the time it was created. Defining x later shouldn’t let fx access that new variable.

It ends up that I’m probably wrong about that, at least according to MzScheme:

cnixon:~$ mzscheme 
Welcome to MzScheme v372 [3m], Copyright (c) 2004-2007 PLT Scheme Inc.
> (define fx (lambda () x))
> (fx)
reference to undefined identifier: x
> (define x 1)
> (fx)
1

Chicken Scheme backs me up on this. Ruby, on the other hand, behaves differently:

cnixon:~$ irb
irb(main):001:0> fx = lambda { x }
=> #<Proc:0x010b15d4@(irb):1>
irb(main):002:0> fx
=> #<Proc:0x010b15d4@(irb):1>
irb(main):003:0> fx.call
NameError: undefined local variable or method `x' for main:Object
	from (irb):1
	from (irb):3:in `call'
	from (irb):3
irb(main):004:0> x = 1
=> 1
irb(main):005:0> fx.call
NameError: undefined local variable or method `x' for main:Object
	from (irb):1
	from (irb):5:in `call'
	from (irb):5

Thanks to Dave Cleaver and Topher Cyll for help on figuring this out.

I was reading Practical Ruby Projects tonight and working on implementing lambdas when I found an example of closures not working right:

(define fx (lambda () x))
(fx) ; ERROR: No value for symbol x
(define x 1)
(fx) ; 1

The closure’s only supposed to capture the environment at the time it was created. Defining x later shouldn’t let fx access that new variable. PRP says that most ways to fix this problem are “a little tricky” and gives the idea of creating a new environment for each line of code evaluated in the same scope.

I solved this a different way, but it was simple enough that I’m afraid it’s naive and prone to being busted.

module Lemur

  class Env
    def copy
      Env.new(@parent, @defs.clone)
    end
  end

  class Lambda
    def initialize(env, forms, params, *code)
      # was this: @env = env
      @env = env.copy
      @forms = forms
      @params = params.to_array
      @code = code
    end
  end
  
end

If anyone out there has an idea of where the bugs in this are (or thinks it’s a good solution), drop me an email or leave a comment.

All the tools I need to pull this interpreter thing off:

For this project, I am going to implement a Scheme interpreter, and hopefully a compiler, for the Java Virtual Machine. The closest I’ve come to anything like this is simple parsing of arithmetic expressions and compiling them into assembly code. I have no real idea of how to write an interpreter, which is why I’m doing it.

Part of this project is teaching myself how to write an interpreter and a compiler. I’ve spent a few days researching how to do this, and I’ve come up with a solid list of references:

Books

• Practical Ruby Projects by Topher Cyll - has a good chapter on implementing Scheme in Ruby
• Programming Languages: Application and Interpretation by Shriram Krishnamurthi
• Modern Compiler Implementation in Java by Andrew W. Appel

Online articles and reference

• How to Build an Interpreter in Java by Chuck McManis
• Programming Languages for the JVM - looking at other people’s implementations of non-Scheme languages could certainly help.
• Write Yourself a Scheme in 48 Hours by Jonathan Tang - while this uses Haskell to build the interpreter, it’s a good reference to follow.
• An Incremental Approach to Compiler Construction by Abdulaziz Ghuloum
• JScheme: Design Decisions by Peter Norvig - while I am not going to look at the code for Norvig’s Scheme until after this project is done, his design decisions document is a good read.

I’ve got a set of readings, but now I need a set of assignments for myself. My planned mode of attack is to:

• First, write a minimal Scheme interpreter in JRuby. It doesn’t have to meet much of a standard, but should be a good proof of concept. I’m familiar with Ruby and it’s dynamically typed, which helps. Technically, this will be an interpreter running on the JVM, but the point is to write this in a statically typed language such as Java or Scala.
• Next, write the same interpreter in Scala. Scala’s combinator parsing lets me eliminate the work of a real lexer, as I can write out my Scheme specification in a format very near Extended Backus-Naur Form. Combinator parsers are slow, but that’s OK for now.
• Optional: rewrite my parser using JFlex to make a lexer first.
• Start trying to meet the standard. There are going to be some tricky concepts in here. Tail-call recursion and the full Scheme numerical stack aren’t going to be easy. I’ll decide what order to tackle tasks in when I get here.
• Build a compiler.

I’ll be updating this blog with reports as I move forward.