Bottoms Scheme implementation project
history | edit |

Format

(Unlike the other pages, this is written in first-person perspective by Christian, as he's organizing this.)

This is about the formation of a group that regularly meets to work on a project, a compiler for the programming language Scheme. The ultimate goal is for the result to be worthwhile for us to use, although the primary aim is to learn how to do this. Scheme is a good choice because although in some ways it's a simple language to implement, in other ways it's also an interesting (demanding) one, and it's a general and clean language usable for real work if one wishes to use the result. Also, it will be a good basis on which to later implement type systems, should we wish to do a followup project.

I'm hoping to satisfy participants with a somewhat wide experience spectrum. I'm not looking for contributors for this project because I'm thinking that this will get it done faster, but because I'm hoping to learn from you just as I'm hoping that you'll learn something. And enjoy ourselves while doing it. I'm limited in the amount of help I can provide by the time and attention I can invest before it interferes with working with the rest of the group. I'm asking for everybody to be courteous and helping out where they see fit and communicating in a way that all involved can understand.

You should not mistake this for a course or classes because:

Participation is free except if there are costs for location or infrastructure that need to be shared (currently not expected).

Workshop?

In the search for a term to describe this format, "workshop" came to my mind. I think of a workshop as a location where one can actively and efficiently work on a (common) object, and where tools or knowledge are available. I do see the term being used for events with a predefined program (talks or poster presentations) with passive participation, though, so perhaps I should use a different term? (Also, these events are usually not free.)

Requirements

This is for people who are already familiar with Scheme or another Lisp, or have experience with functional programming from another environment. You should either have worked through the SICP course materials, chapters 1-2, or should check whether you're able to solve the exercises there. If in doubt, I suggest you contact me or us early on if possible (before the start of the stage of the project for which you want to contribute), then we can find out what knowledge you're missing if any and suggest preparatory studying before the start of the work (I'll try to support you with it) if necessary.

Consider joining the London SICP Study Group (see below) if that could be beneficial for you.

Don't hesitate to contact me to see whether I think you'll fit. You can also subscribe to the bottoms-public mailing list to stay current about our planning before deciding to join.

Activities

The workshop will consist of meetings and activity between the meetings. The meetings will be used for:

Between workshop meetings, participants will work individually on their choosen task (coding, perhaps reading), possibly using email or IRC for communication.

Stages

There are multiple relatively independent stages and hence possible points in time when participants can join:

  1. implement S3C if we want to use that to implement the VM. This includes getting familiar with C if not already, getting to know Scheme more intimately, writing a simple compiler/translator (top-down instead of bottom-up), writing rules-based tests and possibly testing framework. More advanced than part 3.

  2. implement the VM (VML). This includes learning S3C or whichever other language we're using as implementation language, plus writing rules-based tests (or dealing with an advanced type system (and possibly proof assistant)). S3C should make it easy to contribute, the language is pretty simple and the safe implementation will point out errors dynamically (i.e. easy to understand). Advanced debugging techniques are only used when needed and can be explained when situations that require them turn up. Writing tests smartly will require some clear thinking, but doesn't require special knowledge. Rust or ATS may require quite a steep investment first before knowing enough to write the VM (and contributors adding complex types in an attempt at encoding security requirements might make things more difficult for the others to understand).

  3. write a language on top of VML, by growing it towards Scheme step by step. This should be easy to follow or teach as the steps are mostly incremental.

It will be best if you participate during the whole time of a stage, as otherwise you'll not be up to date about what we're doing and will need help to catch up. If you'd like to join (or rejoin after missing several meetings) after the start of a stage, ask and we'll see what we can do. If you can't come for a meeting, please give note about what the others should know about the project part that you're working on, and afterwards read and ask about what we've been doing. If you often can't come for a meeting, you may need to find someone else to work in a pair.

Time investment

Currently planned are meetings of 2.5 hours (6:30 pm - 9 pm) every fortnight, plus a personal investment of about the same amount of time between the meetings (perhaps a bit more for those who can and would like to work on more involved parts).

It's difficult to say how long it will take us to reach the goals. Due to the bottom-up approach, part 3 is going to be slower than projects using existing programming languages to bootstrap from. We're also aiming for something a bit more complete than many toy implementations aspire to, thus the effort can't be compared. Also, it will depend on how effective we will be as a group (will we be faster or slower than a single person working on the project alone?), and how much attention to detail we give and how much time we spend reflecting. I may be tempted or happy to follow sidetracks too if I find them interesting, and if it doesn't mean that others are disappointed for boredom or because it's not what they expected...

I suspect that implementing S3C and writing the VM will together probably take about 4 months when following this schedule (with me likely investing additional time). If that's too long (i.e. the parallel SICP studying takes less time than that), we may be able to hurry up a bit or it could be shortened down much by implementing the VM in plain Scheme instead, or even radically so by using Scheme's objects for guest language objects instead of writing our own memory allocator; that would of course eliminate some of the aims and learning opportunities, too.

For the rest (part 3 above, writing the actual language on top of the VM), when I'm looking at the steps in Languages, I can see getting through it in about 10 meeting/working periods (i.e. about 5 months) if things are going smoothly and work can progress in parallel. Estimates are always a mix between generous time allocations and underestimating the amount of detail required to get things done, though. Probably all in all this amount of time is rather too optimistic than pessimistic. But this is also quite a bit flexible: in case we loose our energy before reaching the end, since we're going to implement it in steps / layers, we could stop or participants could leave before reaching the full goals and will still have something interesting running. Of course we could also decide at some point that the bottom-up approach is too time-consuming and relent, and use an existing Scheme environment to run new code before our own system supports it. That would betray the name of the project and be somewhat of a pity, though. In case we're too quick, there will be lots of additional challenges and work to improve the system.

Let's discuss the plans at a first meeting, and then see how it goes and re-evaluate from time to time (every other month).

An idea may be to invest a weekend or a couple and go camping with laptops (and batteries [and 230 V inverter] provided by Christian for offline power outside the campsite) or rent a cabin?

Co-organization with the London SICP Study Group

There are plans to continue having SICP study sessions, and we'll try to make it so that when reaching the SICP chapters about compilers we'll be ready to start stage 3 as listed above.

During stages 1 and 2, we'll have to see whether the participants of this workshop also want to follow SICP. One possible arrangement might be to have weekly meetings at the same time for both groups, one week the workshop group will work on the project while part of the SICP group will read the new SICP chapters together?, and the other week everyone will do the SICP exercises together. Or perhaps we can get enough room to have SICP and workshop meetings at different times. It might not be possible to get room in the same location or on the same day every time, we may have to be flexible.