216: SICP Prerequisites

by Vladimir Nikishkin

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-216@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

This SRFI follows SRFI 203 in providing "out-of-the-box" support for hosting the exercises suggested by Structure and Interpretation of Computer Programs in portable Scheme.

Whereas SRFI 203 focused on the necessarily non-portable aspects of the problem set (the graphics), this SRFI aims to provide support for the rest of the features, which are far more widespread, often already provided, and in reality mostly need just a common vocabulary.

This SRFI provides procedures for working with time data, multi-threading, and streams, as well as SICP names for true and false.

None of these procedures is fit for production use. They are only designed for pedagogical purposes.

Students, however, are expected to be able to just write

 (include (srfi sicp))

and have the code from the book run without problems (apart from those intended by the book authors).

Rationale

Structure and Interpretation of Computer Programs (SICP) , by Harold Abelson and Gerald Jay Sussman with Julie Sussman, is one of the world's most famous programming textbooks. The code examples in the book are given in Scheme, and the exercises are mostly expected to be done in Scheme. The examples and exercises are best executed with a Scheme system that implements a reasonable subset of the Scheme language. Furthermore, the textbook assumes the existence of several primitives not included in any of the Scheme reports. Most of these primitives are already either covered by other relevant SRFIs, or can be implemented on top of those. This SRFI aims at doing precisely this. The sample implementation uses the features provided by SRFIs 18 and 27, as well as several features provided by the R7RS report, in order to implement the procedures that SICP code examples assume to exist. The picture language of Section 2.2.4 is out of scope for this SRFI. Users are encouraged to refer to the SRFI 203, or any SRFI that supersedes it, for the missing procedures. This SRFI, combined with SRFI 203, can be compared to SRFI 96, which is to SLIB as these SRFIs are to the SICP. SRFI 96 makes no attempt to document SLIB (which has over 200 modules), much less to extend it. Instead, it documents the constants, variables, procedures, and syntax forms that a Scheme must provide in order to fully host SLIB, which amount to fewer than forty.

This SRFI provides four constants, five procedures, and one syntactic construction.

Specification

Booleans

Constant: false

Must have a value that would make the if construct choose the second path. On systems that provide #f as a distinct value, it must be #f.

Even though Scheme reports as early as R4RS (Sections 3.2, 6.1) already have #f as a distinct false value, SICP continues to refer to false. See Section 1.1.6, footnote 17.

Constant: true

Must have a value that would make the if construct choose the first path. On systems that provide #t as a distinct value, it must be #t.

Even though Scheme reports as early as R4RS (Sections 3.2, 6.1) already have #t as a distinct true value, SICP continues to refer to true. See Section 1.1.6, footnote 17.

The empty list

Constant: nil
Must have a value that represents the empty list in the Scheme implementation hosting this SRFI.
Remark: even though many modern Scheme implementations only use '() to represent the empty list, SICP follows the Lisp tradition in this respect.

Time data

Procedure: (runtime)
Returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The sample implementation measures the running time in microseconds. See Section 1.2.6 of the SICP, Subsection "Probabilistic Methods", Exercise 1.22.
Example:
(display (runtime))
;; prints 1604464095599.357

Remark: it is not clear which "system" was running, and in fact, the absolute value returned by this procedure is never used by itself. The author of this SRFI, therefore, opted into assuming that the "system" is the UNIXTM operating system, and it "has been running" since the Epoch, Midnight on January 1, 1970 TAI.

Random numbers

Procedure: (random x)
Returns a nonnegative number less than its input. If random is given an exact integer, it returns an exact integer, but if it is given a decimal value, it returns a decimal value. If x is less than 0, the behaviour is unspecified. See Section 1.2.6 of the SICP, Subsection "Fermat Test", and Exercise 3.5, footnote 8.
Example:
(random 11)
;; prints 1
The sample implementation uses SRFI 27.

Multi-threading

Procedure: (parallel-execute p1 p2 ...)

Each pi must be a procedure of no arguments. parallel-execute creates a separate process for each pi, and that process applies pi to no arguments. These processes all run concurrently.


See SICP Section 3.4.2, Subsection "Serializers in Scheme".
Example: 
(define x 10)
(parallel-execute
  (lambda () (set! x (* x x))) ; P1
  (lambda () (set! x (+ x 1)))) ; P2
;; May assign to x any of the following:
;; 101 - P1 sets x to 100 and then P2 increments x to 101.
;; 121 - P2 increments x to 11 and then P1 sets x to x * x.
;; 110 - P2 changes x from 10 to 11 between the two times that P1 accesses the value of x during the evaluation of (* x x).
;; 11 - P2 accesses x, then P1 sets x to 100, then P2 sets x.
;; 100 - P1 accesses x (twice), then P2 sets x to 11, then P 1 sets x.
Procedure: (test-and-set! cell)
Tests the cell and returns the result of the test. In addition, if the test was false, test-and-set! sets the cell contents to true before returning false.
The test-and-set! operation must be performed atomically. That is, the implementation must guarantee that, once a process has tested the cell and found it to be false, the cell contents will actually be set to true before any other process can test the cell. See Section 3.4.2, Subsection "Implementing Serializers".
The sample implementation uses SRFI 18.

Streams

Syntax: (cons-stream a b)
Is equivalent to (cons a (delay b)). See SICP Section 3.5.1.
Remark: The necessity to include cons-stream is due to the fact that SICP does not introduce any syntax-altering constructs beyond writing your own metacircular interpreter. Please note that the stream-cons procedure from SRFI 41 (implementing "even" streams) would not be a drop-in replacement for cons-stream.
Constant: the-empty-stream
A distinguishable object that cannot be the result of any cons-stream operation. See SICP Section 3.5.1, footnote 54.
Remark: The implementations are encouraged to implement the-empty-stream as an empty list.
Procedure: (stream-null? x)
Returns the value of true if x is the-empty-stream, and the value of false otherwise. See SICP Section 3.5.1, footnote 54.
Example:
(stream-null? the-empty-stream)
;; => #t
(stream-null? (cons-stream 'a 'b))
;; => #f
The implementations are encouraged to implement stream-empty? as null?.

As mentioned in SRFI 41 , Philip Wadler, Walid Taha and David MacQueen describe such streams as odd because, regardless of their length, the parity of the number of constructors (delay, cons, '()) in the stream is odd.

These streams are similar to, but not equivalent to, the "even" streams of the aforementioned SRFI.

Implementation

The sample implementation has been tested on Chibi Scheme. It consists of three files attached to this document. srfi/216/216.scm provides the code that can be load-ed in a Scheme REPL, provided that SRFI 18 and SRFI 27 are available. srfi/216.sld is an R7RS library that can be import-ed in an R7RS Scheme, provided that SRFI 18 and SRFI 27 are available. srfi-216-tests.scm contains a simple conformance test, and uses SRFI 78.

References:

  1. Structure and Interpretation of Computer Programs (companion web site)
  2. Unofficial PDF of SICP, second edition (source)
  3. SRFI 27: Sources of Random Bits
  4. SRFI 18: Multithreading support
  5. Revised7 Report on Algorithmic Language Scheme (companion web site, PDF)
  6. Revised4 Report on Algorithmic Language Scheme (PDF)
  7. An internal discussion in an MIT mailing list , dedicated to solving the same problem.
  8. MIT Scheme Reference on (random x)

Acknowledgements

  1. Arthur A. Gleckler, for helping with the SRFI process.
  2. Jason Hemann, for suggesting additional references.
  3. Shiro Kawai, for spotting important missing definitions in the first draft.

© 2020 Vladimir Nikishkin.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Editor: Arthur A. Gleckler