London SICP Study Group Message Board › Scheme implementation

Scheme implementation

Christian J.
user 31450652
London, GB
Post #: 1
So, I've mentioned that I'm ready to start a Scheme-from-scratch implementation project where you can participate, too. I've created a project on Github about it now:­

The repository currently contains two documents, the Readme and the Strategy files.

To participate, you should have attended the SICP course, or have equivalent experience.

Also, note that this is not a course, there are no exercises to be solved, but instead we'll figure out together during every meeting which part of the work everyone is going to take on. We may meet only every two weeks, and instead be expected to work several hours between the meetings. It might be possible to build some programming pairs, if necessary. I'll try to be available for help as much as possible, too, also through email and IRC. The aim is that you're going to contribute "for real". If you're willing to do this, and I'm able to make it happen by helping you where needed, I'll be happy.

There are a few things undecided yet; one is that SICP does contain the implementation of a Scheme system in the later chapters, thus obviously it would have been nice to have gone through that part already first. But SICP follows a bit a different approach (implementation in Scheme instead of bottom-up, also, less real-world concerns), and starting now would suit me better. Still something I need to figure out first. Also, we're not starting before the beginning of May. Also, organization details to be decided (like, venue still needs to be found).

If you're interested in participating, tell me tonight or send me a private message. I'll then probably set up a mailing list to add you to; I'll also publish another invitation once/if everything is settled.

If you think the project name is contra-indicated or you've got another suggestion, please tell.
Michael H.
user 93301352
London, GB
Post #: 1
As I've mentioned, sounds great, just let me know when/how you want to set up the mailing list. Just saw this today on HN (it's a book where someone goes into building a lisp in C) I'm sure their approach and ours may differ, both conceptually and in that we're using RUST but I'm gonna read it because it seems interesting: http://www.buildyouro...­
Also probably not relevant but here's some links to some of the things I was talking about:
Christian J.
user 31450652
London, GB
Post #: 2
I've skimmed the book. I'm not sure why he dislikes quote and instead invents a separate data type for unevaluated S-expressions, I think it doesn't make sense, but I haven't followed his thought train. He's using a linked environment approach which is standard for simple interpreters, but our virtual machine will instead copy environments (which will be closer to actual machines, and avoids the problem of unused environments not being garbage collected).

I'll read your other links tomorrow.

I've posted a comment about our group on the HN thread. I haven't intended to make it more public before, but this seemed too fitting. I'm hoping you're ok with potentially enlarging our group. I don't want to make it too big, but a bit shouldn't hurt.
Christian J.
user 31450652
London, GB
Post #: 4
Sorry for the late response.

> http://en.wikipedia.o...­

This is about problems arising from the assumption that functions (closures, really) are allocated on the call-stack. Stacks are an optimization technique for memory allocation that we shouldn't bother with, at least for now (we'll value correctness and safety over speed, also, because of call/cc and its dynamic nature Scheme is non-trivial[1] to optimize to make use of stack allocation). Our memory lifetimes will be determined by the garbage collector, not by dynamic scope (function application nesting) as is assumed in the above wiki page.

[1] meaning, I know there are possibilities to do so in various ways but there are trade-offs and I don't know which solution to prefer right now.

Also note that after transformation into continuation-passing style, no nesting of function calls (= nesting of continuations) is used. If the evaluator had a call stack, it wouldn't be used. Since we plan our VM language to be CPS code, there's no sense to implement continuations (a 'call stack') in it.

The above may seem like playing with words. Giving attetion to terms is important, not just to new ones, but also old terms that you think you know what they mean: you may be attaching too much (too many concepts) to them. When saying "call stack" or "stack allocation", the meaning is usually tied to how languages like C are normally being evaluated, making assumptions about their implementation. I think the correct and important realization is that continuations and also monads aren't something special (tied to Scheme or Haskell), but that those are universal concepts that every programming language has, it's just that Scheme or Haskell makes those *first-class*, or explicit in the type system.

So let's take on the term "the stack". In our context that means, the *call* stack. With, in C/Pascal or similar, an array-like representation (linear memory). It's where return addresses, and lexical environments are being kept, for resuming function bodies (outer dynamic contexts) after returns. Other terms are "execution stack", or "frame stack" (stack of "call frames" or "execution frames"). A "frame" on this stack contain a return address and a set of lexical bindings for the context to be returned to. They can be thought of as the state of the future for the calculation of the running program. The "continuation". Each frame is a "continuation frame". Thus this can also be called the "continuation stack" [2][3]. If we were to allow continuations to be accessed as first-class values (and hence referenced in any of the program's variables or data structures) with non-restricted life-times like in Scheme, then you can't use an array to implement the stack anymore the way C does, as you'd again run into memory life-time problems. You'd need to make it into some data structure that is probably using garbage-collection for life-time determination and allows to form trees, e.g. by using linked lists instead of arrays. But again, if we're CPS transforming our code before feeding it to our VM, the VM won't even need to know about continuations at all, hence we won't need to implement any call stack data structure at all in it. Our continuation stack (or tree) will be implicit in the chain of closures that the lambdas representing continuations form. The question for optimization, if we were interested in it, would become one of how to allocate/deallocate the lambdas that represent continuations efficiently (perhaps specializing them into a mechanism separate from closures).

[2] again, yes, C has continuations. They are just not first-class (meaning, accessible as a value by the program itself) in standard C. They *are* even first-class in POSIX, though, using setjmp/longjmp, although life-time issues will again show up and make it impossible or at least difficult and inefficient to store them indefinitely.

[3] to be 'fair', C compilers (usually) optimize away continuation frames that will never be needed for normal evaluation: within a basic block (function body) no new frames will be allocated, even though there may be many steps taken by the program before the next 'return'. In our CPS code, every single step will have a corresponding continuation "frame" (a lambda), unless we also optimize this later on.

If things still aren't clear, it's probably best for me to explain it again at one of the meetings (or ask questions).


I don't have anything to say about this topic. It's probably best to write a partial evaluator as one of the optimization steps later in the project (i.e. once we've got Scheme up and running). Then perhaps use the insight gained from it to revisit this.

Here's the HN link in case someone reads this thread now that the thread is off the front page: https://news.ycombina...­ . Several other small Lisp-in-C implementations are mentioned in the thread (some of them more advanced).

Powered by mvnForum

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy