Intermezzo: Small-stepping environments

[nalintmo]

I am currently working on an interpreter written in C, with the intention that it should support continuations and call/cc. I am doing this with continuation-machine semantics, which means small-step evaluation. In the process of figuring out how continuations interact with environments, I think I've discovered that my small-step evaluator in SML

Comments

[aleffert]

Intermezzo!

[wjl]

This episode's pointer to the literature: Landin's SECD machine. I think the S is for "stack", and that's what you were missing; but I can never remember what the D "dump" does, so maybe it's that instead.

Man, this project is great for reinventing the last 30 years of PL research in 30 days :D you've already knocked out at least three of the classics; for your next trick, you should invent domain theory!

[gwillen]

I'm mostly trying not to read the literature since I feel like it makes it less a creative activity and more of a rehash of what's been said. I have read about the SECD machine before, though. I forget the exact details.

I'm also not restricting myself to a strict rewrite-rule semantics: I'm only going to bother capturing the state of execution right before function application, since that's the only place the continuation can be captured. Between function applications I'm freely doing as much work as I can.

[wjl]

Yeah, I get the not reading the literature bit -- I really do think it's pretty cool (and very in keeping with the challenge) that you're reinventing so much so fast. I hope you don't mind my pointers though; perhaps you'll want to follow up on them later.

[aleffert]

Teehee. The dump. Teehee. If I remember right, the SECD machine is basically the right thing, but is a little more baroque than it needs to be.

[roseandsigil]

You realize that this "saving environments" thing is how call stacks work, right?

[gwillen]

Wellll, there are many different things you can save and ways you can save them. Call stacks in C are one point in that space. They save an environment and an instruction pointer.

Currently my continuation datatype saves an interpreter-structure (specific to the particular special form being interpreted) and a pointer down the stack to the next continuation. I think it's a good point that, to follow the C analogy, I should just stick an environment pointer in there as well. Probably what I actually need, by close analogy with C (and based on my comments about what I broke in the SML version) is to have a saved-environment pointer only in the function-application continuation-frames.