Bottoms Scheme implementation project
history | edit |

"Safe, S-expression based, Similar-to-C programming"

S3C is a language concept by Christian to write programs "in C", but with an S-expression based syntax, and stronger typing and syntax extension facilities, plus an implementation used during development that features complete safety at runtime (by using runtime type checking, invalidation of stack memory upon leaving a scope, and using destructors offered by the GC of the host language to verify correct memory handling). The idea is to then use extensive rules-based tests to try to make programs written in it secure (total absense of runtime errors in the safe implementation means absense of errors / security holes in the translated C code). This could be a bridge learning to go from 'plain programming' (runtime type checking, writing tests) to verifying safety statically (using static type systems and proofs).

S3C might also be a good for those who haven't used C-level programming before, for learning what gaps security-wise such programming leaves open and how to test against them thoroughly ('runtime pendant' to proofs).

It might also be interesting to actually try to add some static verification (static type system) later on, although probably after doing the rest of the project first due to time constraints.

The project repository (currently just containing a mockup) is here (example).

Reasons this may be a good idea:

Reasons this may be a bad idea:


S3C only has a mock implementation so far, thus if we are to use it to implement the VM, we'll have to implement it first. This will take 2-3 months perhaps, thus VM implementation would be delayed (we might want to implement the VM at the same time as S3C, though).

But perhaps that would actually suit the group fine: SICP studying could go along at the same time, and once S3C (and perhaps also the VM) are ready, people just interested in implementing Scheme on top could start off with the benefit of some more SICP knowledge. Especially chapter 4 should be useful. Chapter 5 is about writing a compiler: perhaps it makes sense to study this chapter as part of the workshop, we/Christian will have to think about this. Or the workshop could be followed while postponing study of chapter 5 to afterwards. -> To be decided.

The timeline would entail:

  1. meeting where Christian describes each part of the project, with room for questions and discussion to help group members to decide whether they would like to participate in the S3C and/or VM development phase.

  2. write safe implementation of S3C (in Scheme). Perhaps write VM at the same time already. (~2 months)

  3. write translator to C. (This could be done later assuming performance isn't too low without it.) (~1 month)

  4. Write VM if not already done (= implement VML). This is hopefully easier for participants to join: for those already knowing C, this will just entail learning a little different syntax, for those not knowing C, this should be easier than learning C as it has a safe evaluation environment that will point out bugs easily.

  5. Grow Scheme on top of VML, with a bigger or changed participant group. This part should be even easier for starters, nothing other than familiarity with the language to be implemented (Scheme) will be required.

    The ultimate goal is reached when the system is able not only to run the Scheme compiler (which is always self-hosted), but also the S3C compiler, i.e. fully hosting itself.


These should be done before entirely fixating the plan.