This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home. For a version of this page that may be more recent, see BottomScheme in WG2's repo for R7RS-large.

Bottom­Scheme

cowan
2015-04-17 03:24:58
2history
source

This is not an R7RS page; it's just John Cowan's notes on an idea that used to live on a scrap of paper.

Bottom Scheme is a tiny subset of R7RS-small. It is not really a Scheme at all, because it omits assignment, macros, modules, proper tail calls except in named let, multiple values, call/cc, dynamic-wind, mutable pairs and strings, I/O (except for read-char and write-char), and essentially all non-primitive procedures.

Specification

This list is organized according to the R7RS-small report.

  1. 1 Identifiers

No case-folding directives.

  1. 2 Whitespace

Only ; comments.

  1. 3 Other notations

Parens, apostrophe, quoted strings, #t and #f, and number, vector, and bytevector constants. No backquoting, character constants, number bases, or labels.

  1. 1 Primitive expression types

Variables, constants, procedure calls, lambda without improper formals, if.

  1. 2 Derived expression types

Only cond without =>, and, or, let, letrec, begin, and named let (with the restriction that the bound procedure can only be invoked in tail positions within the lexical scope of the let).

  1. 5 Record-type definitions

Full support for define-record-type.

  1. 1 Equivalence predicates

Only eqv? (for which eq? is a synonym). Programmers are encouraged to provide their own definition of equal?.

  1. 2.1 Numerical types

All types are supported.

  1. 2.2 Exactness

The only exact numbers are integers within a fixed range.

  1. 2.4 Implementation extensions

Inexact real numbers are IEEE doubles; inexact complex numbers are pairs of IEEE doubles in the rectangular representation.

  1. 2.5 Syntax of numerical constants

/ is not supported, because all exact numbers are integers. Base and exactness prefixes are not supported. The notations -0.0, +inf.0, -inf.0, and +nan.0 are supported.

  1. 2.6 Numerical operations

Predicates: number?, real?, exact?, inexact?. Arithmetic: +, -, *, / with two arguments only; / always returns an inexact value. Transcendental functions: exp, log (one argument), sin, cos, tan, asin, acos, atan (one argument), sqrt, expt always return complex numbers. Complex: make-rectangular, real-part, imag-part. Conversion: exact, inexact.

As an enhancement to R7RS-small, the non-generic arithmetic functions fx+, fx-, fx*, fl+, fl-, fl*, fl/, cx+, cx-, cx*, cx/ are provided.

  1. 3 Booleans

Only #t and #f notations, not, boolean?.

  1. 4 Pairs and lists

Pairs are immutable. Only pair?, cons, car, cdr, null?

  1. 5 Symbols

Only symbol?, symbol->string, string->symbol.

  1. 6 Characters

Not supported; use single-character strings instead.

  1. 7 Strings

Full support for string literals. Strings are immutable. All Unicode characters are supported except U+0000 (NUL). Only string?, string-length, string=?, string<?, string>?, substring, list->string.

  1. 8 Vectors

Full support for vector literals. Only vector?, make-vector (one argument), vector-length, vector-ref, vector-set!.

  1. 9 Bytevectors

Full support for bytevector literals. Only bytevector?, make-bytevector (one argument), bytevector-length, bytevector-u8-ref, bytevector-u8-set!.

  1. 10 Control features

Only procedure?, apply.

  1. 11 Exceptions

Only error.

  1. 13 Input and output

Only read-char (no arguments), eof-object, eof-object?, write-char (no arguments), display (mostly for debugging).

Implementation

These notes assume a 64-bit system.

With the basic object 64 bits in size, NaN-boxing is a plausible technique. In this scheme, IEEE doubles are represented as immediates, and all other objects are stuffed into the signaling NaN space (high-order bit is 0, next 11 bits are 1, next bit is 1). This limits them to 52 bits in size, which is enough to hold 64-bit pointers in current architectures, since they are only 47 bits in size (excluding the kernel area). Because a pointer to a 64-bit value always has the low-order three bits zero, they can be used for the following tagging scheme: