Let us discuss SRFI-216: SICP Prerequisites

1. Abstract

001-Sicp_js.png

This post is a not-so-technical introduction to the Scheme Request for Implementation 216: SICP Prerequisites, that I have written and made available for discussion. (Please, contribute!)

SICP stands for the "Structure and Interpretation of Computer Programs", a world-famous introductory programming textbook.

It's aim is to make the exercises and examples from the book be available for any Scheme system bothering to provide it, and not just MIT/GNU Scheme and Racket (which doesn't even consider itself a Scheme any more). Before this SRFI an issue tracker request asking for SICP support would have been looking vaguely. Now you can just write "Could you consider providing SRFI-216 (and 203)" in your implementation.

In order to write this SRFI, I went through the whole book and solved all the exercises. However, my experience is just mine, and to make a truly good common vocabulary, community feedback is required.

For technical detail and more background, I am inviting you to read the whole article.

2. What is SICP and why is it good?

002-800px-Massachusetts_Institute_of_Technology_logo.svg.png

SICP used to be an introductory course in programming in the Massachusetts Institute of Technology.

Its aims are twofold.

On one hand, it aims to provide sort of a bridge between the level of programming at which programmers reason about basic computational units, such as half-adders and XOR gates, and the level at we can reason about everyday things, such as "please highlight all misspelled words".

On the other hand it tries to expose the students to as many software design/architectural patterns (that are actually thought out to add value rather than overcome the limitations of a language) as possible.

Both of these goals are enormous, and the course is itself enormous in size.

Still, passing it gives that (false) feeling of almightiness that is just so seductive that trying it once, the student is almost bound to pursuing it later on.

And apart from the sheer difficulty of the course, there are technical problems too.

3. Which technical problems?

003-800px-MIT_GNU_Scheme_Logo.svg.png

To keep the long story short, the Scheme world is not a place for the weak.

SICP challenges the student extra hard in both the questions it asks, and in the questions it does not ask. In particular, it speaks almost nothing about any particular implementation of Scheme, apart from a few words about MIT/GNU Scheme. Recalling that MIT Scheme was initially conceived as a software simulator for a hardware chip will already give you a sketch of an emotion that a serious student tackling SICP is experiencing all the time.

Implementations matter a lot for a language as high-level as Scheme. In C you can get by with a lot of things, because the language itself has direct memory access, so you are allowed to bend the rules for your own benefit pretty much in an unlimited fashion.

However, Scheme is a high level language, and the developers paid a lot of effort to make sure that it remains as abstractly formulated, as possible, to avoid "designing themselves in the corner" from which it would be very hard to escape.

But a side-effect of this is that a lot of features that modern programmers take for granted, such as random numbers or time and date query are unavailable to pure Scheme programmers.

SICP uses several of those, as its aim as a programming language textbook is to introduce the student to as many programming concepts, as possible, even if they have not yet been as cleanly and abstractly formulated, as is desirable to be included into the Scheme standard.

4. Why would I even want to solve SICP in some other Scheme?

One of the main benefits of the SICP is that it teaches the readers how to build an "artificial intelligence system" (in this case, a high-level programming system) on almost any Turing-complete substrate.

But the more frustrating then is to realise that completing it entirely is only possible on two systems, one of which is highly peculiar and does not support Windows (MIT, officially), and the other one doesn't even call itself Scheme.

Moreover, nowadays the main strength of the SICP is not the strength of a general-purpose language (even though writing standalone programs is still completely possible, and Cisco still maintains its own implementation), but as an extension language that can be built into almost any software product imaginable, written in any language.

There are Schemes working on top of JVM, CLR, Fortran, JavaScript. Scheme is an extension language for GNU Debugger, GNU GIMP and GNU Guix.

For an interested programmer, it's the most reasonable to choose the programming system for mastering SICP that is most like to fit well into the daily workflow.

This is one of the main goals of this SRFI.

5. My contribution

Since may years has passed since the release of SICP, Second Ed., the language has evolved, and several widely accepted libraries have emerged, that now make it possible to pass the course without digging into the gory details of interpreter implementation, as was required years ago, if you wanted to use any Scheme other than MIT/GNU.

Some of the features still remain a no man's land in the sense that no overwhelmingly acceptable abstraction has emerged to be included into the Scheme. The most noticeable missing jigsaw bit is the graphics output. Frankly speaking, in the age of extra powerful HTML, it is unlikely that it will ever emerge.

The author of this text, therefore, had to deal with the graphics separately, as described in https://lockywolf.wordpress.com/2020/07/18/proposing-programming-language-features/ and the SRFI-203.

This work, however, speaks about the features that either have been included into the standard, of have widely accepted abstractions.

6. The artefact

004-srfi.png

The result of my work is a Scheme Request For Implementation, a non-normative Scheme community standard.

It includes two constants, five functions, and one syntactic extension to the core language.

6.1. Boolean values.

Many people would remember that it took quite a while until the C language got a dedicated logical type. Well, for Scheme it took even longer, and therefore SICP has to refer to the two variables true and false, that are an abstraction over some (unknown) logical types.

Now that Scheme standard has #t and #f, it makes a lot of sense to bridge this gap by equating SICP values and standard values.

6.2. Time queries.

Scheme hasn't had a standard function to find current time for quite a while. Now it does have one, it is possible to implement the most basic tool for performance profiling (timer) portably. This way the runtime function was implemented.

6.3. Random numbers.

How would you implement random numbers on a machine that has not access to a clock, an entropy source, or a decaying atom? It's actually a non-trivial question! Therefore, the Scheme standard still does not have a way to generate (pseudo-)random numbers.

Luckily, the need in random numbers is so large that a widely accepted abstraction has appeared ages ago, and for me it was necessary to just repackage the code.

This way the random procedure was born.

6.4. Multi-threading.

005-1200px-Multithreaded_process.svg.png

Multi-threading was a hot topic about ten years ago, when I was still at a university. It has not yet been fully researched, deadlocks and race conditions still arise quite a lot, despite several languages that claim to be very fit for multi-threaded programming being available on the market.

The two most basic tools that are required for properly understanding multi-threading are something that "allows programs to run in parallel" and something that "allows one program to make sure that it is not interfering with the some other one".

Of course, there are numerous other tools, but the parallel-execute, and test-and-set! (also known as atomic-compare-and-swap) are the basic foundation on which everything else can be built.

I implemented them on top of the "SRFI-18", which itself borrows inspiration from Java. It is funny to implement mutexes on top of other mutexes, but that's the price of two models not being completely corresponding.

6.5. Streams.

Streams are infinite lists. They would not have appeared here at all, if SICP had spoken at least a tiny bit about native mechanisms for syntactic extension.

Alas! SICP was written in the years when Scheme had so-called "non-hygienic" macros, but still says nothing about them.

The most useful cons-stream syntactic structure is, therefore, impossible to implement without writing your own Scheme, which by the Chapter 3 is still not possible.

I had, therefore, implement it myself, on top of the last (R7RS) standard's syntax-rules.

7. How can I help?

Firstly, no good standards appear unless a lot of people examine them. Code and document review are extremely needed.

Secondly, if you have a "favourite" Scheme implementation, you could try lobbying the provision of this SRFI, in order to both make the implementation more attractive to the users, and to promote SICP.

Tell your friends, students, professors, and enthusiasts, that studying SICP does not have to be a process full of pain.

If you are teaching programming, functional programming, or informatics (or your friends do), suggest that they have a look at the proposal, their feedback would be the most useful.

8. Conclusion

The SRFI-216, and the SRFI-203, combined, provide all the features that are required from a Scheme implementation to host the book.

I'm hoping that this work may extend the period of relevance for Scheme, SICP, and help popularise such an in-depth and unorthodox course.

The discussion is done through the mailing list. For details, please, consult https://srfi.schemers.org/srfi-216/.

9. Contacts and Donations

This post was not funded by anyone, so if you liked it and/or find it useful, please consider donating or subscribing.

Donate

Subscribe