Solving SICP

This report is written as a post-mortem of a project that has, perhaps, been the author’s most extensive personal project: creating a complete and comprehensive solution to one of the most famous programming problem sets in the modern computer science curriculum “Structure and Interpretation of Computer Programs”, by Abelson, Sussman, and Sussman (\cite{Abelson1996}).

It measures exactly:

  • How much effort SICP requires (729 hours 19 minutes (over eight months), 292 sessions).
  • How many computer languages it involves (6).
  • How many pieces of software are required (9).
  • How much communication with peers is needed.

It suggests:

  • A practical software-supported task management procedure for solving coursework.
  • Several improvements, on the technical side, to any hard skills teaching process.
  • Several improvements, on the social side, to any kind of teaching process.

The solution is published online (the source code and pdf file):

This report (and the data in the appendix) can be applied immediately as:

  • A single-point estimate of the SICP problem set difficulty.
  • A class handout aimed at increasing students’ motivation to study.
  • A data source for a study of learning patterns among adult professionals aiming for continuing education.
  • An “almost ready” protocol for a convenient problem-set solution procedure, which produces artefacts that can be later used as a student portfolio.
  • An “almost ready”, and “almost convenient” protocol for measuring time consumption of almost any problem set expressible in a digital form.

Additionally, a time-tracking data analysis can be reproduced interactively in the org-mode version of this report. (See: Appendix: Emacs Lisp code for data analysis)

Read full paper

Let us discuss SRFI-216: SICP Prerequisites

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.

Read the whole story

Proposing programming language features

This blog hasn’t had enough attention for quite a while. This is not, however, because I have abandoned it, but rather because the original purpose of this blog, that is dumping essays regarding books I read, is still valid. It’s just that the most recent book has taken an order of magnitude more time than I had expected it to take.

Okay, I’m going to write a bigger and better review on the “Structure and Interpretation of Computer Programs”, but the book altogether took so much time, effort and emotions, that even writing the review is going to take a while.

Meanwhile, one of the by-products of my reading happened to be a proposal of a feature to be included into the Scheme Language, that is needed in order to support all the code examples in the book.

(Yes-yes, you’re not misreading it. The book published in 1996 is _still_ not covered by the existing language standard in full. Otoh, it means that there is a chance of achieving things.)

Now that the proposal has an official number, there is going to be a public discussion among the potential Language System providers, and maybe (if it passes the review), we will have this feature officially recognised.

Watching discussions of experts on what they may actually work themselves is a fascinating experience, and a chance to improve own skills too. In this case the discussion is not expected to be too heated, however, but anyway.

https://srfi.schemers.org/srfi-203/ — this is the link to my recent proposal.

It speaks about quite an interesting approach to generating computer images, that builds on top of the classical features present in most drawing languages, such as PostScript, TikZ, MetaPost or SVG. While the expressive power is largely the same, the degree of abstractness is greater, which leaves gives greater code reusability and flexibility.

Scheme is by not means the only language that has a community feature review process.

  • Python has Python Enhancement Proposals (PEP)
  • Java has Java Community Process (JCP)
  • Scheme has Scheme Requests For Implementation

The image in the header is a digital copy of a work of M. Escher, whose works have inspired the original author of the “Picture Language” Peter Henderson. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.1503