Pre-SchemePre-Scheme is a statically typed dialect of the Scheme<br>programming language, combining the flexibility of Scheme with the<br>efficiency and low-level machine access of C. The compiler uses type<br>inference, partial evaluation, and other correctness-preserving<br>transformations to compile a subset of Scheme into C with no additional<br>runtime overhead. This makes Pre-Scheme a viable alternative to C for<br>programming virtual machines, operating systems, and embedded<br>systems where the runtime overhead of a complete Scheme implementation<br>is not desirable.<br>Status<br>Thanks to an NGI Zero grant facilitated by the NLnet<br>Foundation, the Pre-Scheme Restoration project is now underway!<br>A high-level overview of the project is available in the announcement<br>post, and the latest progress is detailed in the first<br>progress report.<br>History<br>Pre-Scheme was originally developed by Richard Kelsey and Jonathan Rees<br>in 1986 as the implementation language for the Scheme 48<br>virtual machine. In the following years, Richard developed the compiler<br>for Pre-Scheme based on his dissertation work on the "Transformational<br>Compiler". The compiler remains part of the Scheme 48 project and is<br>used to compile its virtual machine and garbage collector(s) to native<br>code.<br>Features<br>Compared to C, Pre-Scheme offers the following features:<br>Scheme semantics: Pre-Scheme code is Scheme code. With a small<br>compatibility library, Pre-Scheme code can run directly in a Scheme<br>interpreter, allowing for interactive development and debugging using<br>the same tools used for Scheme.<br>Scheme macros: Scheme's powerful macro system allows language<br>extension by writing procedures which manipulate source-code as a<br>data structure. These can be used to write new control-flow<br>operators, implement domain-specific languages, and eliminate<br>boilerplate.<br>Compile-time evaluation: The top-level of a Pre-Scheme program is<br>evaluated at compile time, allowing complex data-structures and<br>procedures to be built up incrementally, and then treated as static<br>during the rest of the compilation process.<br>Type inference and polymorphism: Pre-Scheme uses type inference<br>to model Scheme's dynamic typing as accurately as possible. The<br>compiler uses a modified Hindley/Milner algorithm to choose a<br>specific machine representation for every variable, and can make<br>copies of procedures to support polymorphism.<br>Efficient tail recursion: Pre-Scheme guarantees that local<br>tail-recursive procedures run in constant space, so iterative<br>processes can be safely implemented with recursion. In C, this kind<br>of optimization is not guaranteed, so it's normal to use constructs<br>like for loops or while loops which fundamentally depend on mutation.<br>Compared to Scheme, Pre-Scheme has the following restrictions:<br>No garbage collector: As with C, Pre-Scheme requires the<br>programmer to manually manage memory. Calls like make-vector and<br>make-string are compiled down to a malloc, and that memory will<br>be leaked unless it's explicitly deallocated at some point in the<br>future.<br>No runtime closures: Lambda expressions which capture<br>locally-bound variables in a way that would require dynamic<br>allocation of a closure are not supported, and will result in a<br>compilation error. This restriction doesn't apply to code which is<br>evaluated at compile-time.<br>Limited tail recursion: Pre-Scheme doesn't provide Scheme's<br>universal guarantees for tail-call optimization. Only cases which<br>can be handled efficiently, such as local recursion using let or<br>letrec, are optimized automatically.<br>Strict static typing: Type information is fully resolved at<br>compile-time, so there's no built-in support for Scheme's runtime<br>type-checking predicates like number? and string?. As in C, any<br>runtime type systems need to be implemented in application code.<br>Limited first-class data types: Pre-Scheme only supports<br>data-types which are supported natively by C. There are no lists, no<br>first-class continuations, and only fixed-size numeric types. As in<br>C, more complex data-types need to be implemented using record types<br>in application code.