This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.
Since we established last time that I'm going to blatantly steal stuff from Lisp, Scheme and friends (as well as from all over the place - I feel no need to be original with this project... Not until we're much further along, anyway), now is the right time to start introducing some more powerful concepts.
Lambdas, or anonymous functions, can be passed around like values and called at your convenience (or not at all). Generally, they can access variables from the surrounding scope that gets "bound" to the function as an environment that allows it to pass state. That's a closure. What we're going to do this time is not going to bring full closure support, but it's the start, and we'll get to full closures down the road.
Let's be clear: As almost everything in programming languages, they are syntactic sugar. You can consider them equivalent to defining a class with a single method to call it and instance variables to be the environment, for example (or you can treat closures as a way of building an object system instead - a concept explored by Wouter van Oortmerssen who has been a hero of mine ever since I discovered Amiga E. If you're a programming language geek you need to take a look at the stuff Wouter has done over the years) - many concepts are reasonably orthogonal.
(As further digression, have you noticed a lot of people like me who are obsessed with programming languages that have this horrible tendency to nest sentence fragments and abuse punctuation to interject random thoughts all over the place, or is that just me?)
But instead of having to go to all that trouble, and litter your namespace with small functions, lambdas let you define them inline, and return a value representing the function instead of executing it.
For now, we'll add these constructs:
(lambda (args) body) (call f (args))
The former will return the function - for now just the address - instead of executing the body. "call" will call the address passed with the arguments it's given, no surprise there.
So how does this differ from "real" closures?
The tricky part about real closures is that if you refer to variables from the surrounding scope, they are supposed to "stay live" for the next invocation. That is, they are meant to be kept around whenever you call the closure later on. It should be clear that returning just the address to the function isn't sufficient to achieve that. So let's look at one way of doing it, so you get an idea of the work involved (it's not huge, but not trivial either):
Ok, so for now just lets get the "anonymous function" in place. As usual I'll go through the changes step by step, but note that I've done some minor cleanups that are inconsequential to these changes as well, that I won't go through because they'll lust clutter things up.
The first piece is the code to handle the "lambda" expression:
def compile_lambda args, body
name = "lambda__#{@seq}"
@seq += 1
compile_defun(name, args,body)
puts "\tmovl\t$#{name},%eax"
return [:subexpr]
end
Hopefully this is pretty self-explanatory. All it does is create a function name on the form lambda__[number] that we'll use to refer to the function, since we won't actually output it inline. Nothing really prevents us from spitting it out inline, but I find it messy, so for now anyway, I'll treat it as just another function. We then call compile_defun to generate just another named function - so it's only anonymous for the user. We then move the address of the function into %eax, which is where we've established the result of our subexpressions go. Note that this is yet another shortcut - eventually we'll need to do something more sophisticated to handle more complex expressions properly, but register allocation is a complex subject (and the alternative, to push everything onto the stack works but is slow).
Last we return [:subexpr] to indicate to the caller where/how to find the result of this expression.
Next we'll do some refactoring. You may have noticed that the inner loop of #compile_exp was getting ugly, handling different types of arguments. So we extract this:
def compile_eval_arg arg
atype, aparam = get_arg(arg)
return "$.LC#{aparam}" if atype == :strconst
return "$#{aparam}" if atype == :int
return aparam.to_s if atype == :atom
return "%eax"
end
Notice the appearance of :atom, too. This allows us to take the address of C functions and pass them to :call. It was so simple to add, I figured why not. To go with that, we add this to #get_arg:
return [:atom, a] if (a.is_a?(Symbol))
Next up, as part of the refactoring, :call falls out almost by itself:
def compile_call func, args
stack_adjustment = PTR_SIZE + (((args.length+0.5)*PTR_SIZE/(4.0*PTR_SIZE)).round) * (4*PTR_SIZE)
puts "\tsubl\t$#{stack_adjustment}, %esp"
args.each_with_index do |a,i|
param = compile_eval_arg(a)
puts "\tmovl\t#{param},#{i>0 ? i*4 : ""}(%esp)"
end
res = compile_eval_arg(func)
res = "*%eax" if res == "%eax" # Ugly. Would be nicer to retain some knowledge of what "res" contains
puts "\tcall\t#{res}"
puts "\taddl\t$#{stack_adjustment}, %esp"
return [:subexpr]
end
This might look familiar. It's because it's the guts of #compile_exp, with #compile_eval_arg replacing some of the more ugly bits. The main other change is that it calls compile_eval_arg to get the function too, and does something weird to "%eax" - it prepends a "*".
Either you're confused now, or you might start seeing possibilities - both of doing nice things and of shooting yourself in the foot. The above is the equivalent of casting an arbitrary expression into a pointer and jumping to it with no validation. It makes it deliciously easy to cause a segfault by jumping to random addresses. It also, incidentally, makes things like a virtual pointer table for a class system trivially easy, and a number of other things. Safety will have to come later. As it turns out, the "*" is needed in front of indirect "call"'s.
So what does #compile_exp look like now? The obvious answer is "a hell of a lot cleaner":
def compile_do(*exp)
exp.each { |e| compile_exp(e) }
return [:subexpr]
end
def compile_exp(exp)
return if !exp || exp.size == 0
return compile_do(*exp[1..-1]) if exp[0] == :do
return compile_defun(*exp[1..-1]) if (exp[0] == :defun)
return compile_ifelse(*exp[1..-1]) if (exp[0] == :if)
return compile_lambda(*exp[1..-1]) if (exp[0] == :lambda)
return compile_call(exp[1],exp[2]) if (exp[0] == :call)
return compile_call(exp[0],exp[1..-1])
end
Nice, isn't it? compile_call, as it turns out does almost exactly the same as what the guts of compile_exp used to do, apart from what was farmed out to the other functions.
So we do a little test:
prog = [:do,
[:call, [:lambda, [], [:puts, "Test"]], [] ]
]
(yeah, not exactly earth-shattering)
Compile and run:
$ ruby step6.rb >step6.s
$ make step6
cc step6.s -o step6
$ ./step6
Test
The full code for this step is here
Since I combined three parts last time, here's an updated list of the remaining pre-written "just-in-need-of-cleanup" parts - I guess I better free up some time to write some new stuff soon, as I'm fairly sure I might end up combining a couple of the parts below when I get around to cleaning them up (such much for posting it as 30 parts...)