Tail call `optimization' has arrived.

pdcawley on 2002-04-18T09:12:08

Yay! I've now got my Scheme Interpreter running on an abstract machine implemented in perl, doing tail optimization with partial continuations and stuff. It's, um, scary. And it's one more step closer to a parrot implementation (or a scheme to parrot compiler, whichever comes first).

But right now I'm not sure which scares me more. The code, the fact that I understand it, or the fact that I've not had to change any of my top level environment bindings to get it working. I 'just' subclassed my 'generic' Scheme::SchemeEvaluator and redid it as an abstract machine. I've had to add a couple of methods to my datatypes, but nothing dramatic...

It is, of course, dog slow. Maintaining your own call stacks etc and doing perl OO dispatch is never going to make for blinding speed. But hey, Parrot will solve that. He stated, blithely.

---

Keep it up!

jdavidb on 2002-04-18T19:47:31

I'm really enjoying reading about this. I tried to write a scheme interpreter in perl three years ago during my programming languages concepts class, but got hung up on the parsing. (Hadn't taken a compilers course, yet.)

Congrats, and keep coding!

Parsing's easy

pdcawley on 2002-04-19T00:25:40

At least, it is when you do it in perl. Coming up on my todo list is to move 'peekc' and 'getc' into the toplevel environment and then implement 'read' in Scheme.

Then there's the small matter of doing similar to the 'environment', though I may be tempted not to break them down into something implemented in perl, instead using making sure that I've got a representation of the various scheme datatypes and hand hacking some parrot for their methods...

Ah yes, how to do partial continuations/tail call magic in Parrot. Say 'I1' is your continuation register:

  # tail call:
 
          branch foo_tail
 
  # none tail call
          bsr foo
 
  foo:    restore I1   # Gets the return address                   off the stack and saves it on the cont register
  foo_tail:
          ...
          save I1
          ret          # returns to appropriate partial continuation

At least, I *think* it should work. Unless there's two different stacks, but that would be nasty.
     

Re:Parsing's easy

pdcawley on 2002-04-19T06:09:32

Ghod, I'm being dim. Of course there's two different kinds of stack. Hoom...

Re:Parsing's easy

Elian on 2002-04-25T14:59:35

Three kinds, actually. (Well, OK, either six or seven. Or four, depending on how you're counting) There's the call stack, the user stack, and the 4 register stacks. (You may or may not count them separately)

We're probably going to get a generic integer stack soonish, for regexes. (Faster than the generic stack by rather a bit, and that's important for regexes)

tail optimisation

Matts on 2002-04-25T12:19:09

I notice you used a loop for the tail call stuff. Would it be any more efficient to piggy back on top of exception objects instead?

Re:tail optimisation

pdcawley on 2002-04-25T13:35:14

Ooh... I'd not thought of that. I really don't know, but it might be conceptually neater. I'm not entirely happy about the current trick of unwinding the stack using redo, it works but if feels, well, naughty. Replacing $self->method(...) with die Call->new('method') or something isn't exactly a 'nice' thing to do either.

I think I'm going to have to release the code with a TODO list sketching out an 'ExeptionMachine' implementation and welcome patches. I really want to be concentrating on implementing the whole thing in parrot...

Re:tail optimisation

Matts on 2002-04-25T14:57:25

Well you can wrap the die() inside a method. And you probably also need to do my "unblessed" exceptions trick in a __DIE__ handler.