website | twitter

Tuesday, September 14, 2010

Tamacola (3)

How a lisp program is compiled to Tamarin VM

Now I'm going to talk a bit about how a lisp (almost Scheme) program is compiled into Tamarin's byte code. This topic is especially interesting if you are curious to make your own language or VM.

Tamarin VM is made for ActionScript, so its byte code is also specifically designed for ActionScript. In other words, it is a slightly tricky to implement other language than ActionScript. In case if you don't know about ActionScript, it is almost identical as JavaScript in the execution model. Difference between them is about optimization with explicit type notion and static field.

ActionScript and Scheme are common for those aspects:

  • Lexical scope.
  • Function object.
  • Variable arguments with no curring.
  • Dynamic typing (a value has type, not variable).

But there are significant difference.

  • ActionScript doesn't have a simple function call. Everything is a method call.
  • In ActionScript, a function has a scope. No scope block or let expression.
  • Tail call optimization is not supported.
  • Call stack can not be accessed.

Those limitations sound like that Tamarin VM is inferior. But no, actually those limitations come from Tamarin VM's advantage and optimization. If you happen to have a chance to design your VM, please learn from the lesson. There ain't no such thing as a free optimization. Any optimization kills some generality. I'll explain each case.

ActionScript doesn't have a simple function call neither Tamarin VM. This is rather harmless though. When you see a function like expression like trace("hello"), this is actually mean (the global object).trace("hello"), and eventually, the receiver passes to the function as the first argument. In other words, if you want to construct a function call with two arguments, you need to make three arguments where the first argument is "this" object. A slightly tricky part is primitive operators like + or -, which don't have "this" object. Those primitives are special case.

ActionScript also has lexical scope, but only a function has a scope. So I have to be careful when I compile let expression in Scheme. Most simplest way to implement a let expression is to use a function. A let expression can be always translated to a lambda in theory though, this is a huge performance disadvantage. So I use "with" expression in ActionScript. "With" expression is an unpopular syntax in ActionScript, but you can use any object as a scope object. I borrowed this idea from Happy-ABC project

Lack of the tail call optimization in Tamarin VM was the most disappointed thing to me. It prevents a functional programming style. I simply gave up it. Tail call optimization is not difficult topic at all. If the target were a native code like x86, it would be a matter of swapping stack and jump. But Tamarin VM doesn't allow direct access of stack or jump to other function. I understand that it might cause a security issue though, it would be wonderful if VM would provide special byte code for tail call.

Finally, you can't access the call stack directly, therefore you can't implement call/cc. The reason why I can't call Tamacola as Scheme is the lack of tail call optimization and call/cc. It prevents many experimental language features like generator, process, or so. But considering rich libraries provided by the Flash API, I would say Tamacola will be a reasonably useful language eventually.

I'll tell you convolved self hosting process and macros tomorrow.

No comments:

Post a Comment

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 Unported License.