boot2

Playing with the boostrap
git clone https://git.ryansepassi.com/git/boot2.git
Log | Files | Refs | README

R7RS micro

R7RS micro is a deliberately small profile of R7RS-small for bootstrap interpreters and other environments where implementation complexity carries more weight than language breadth.

The intended use is the one in this repository: bring up a compact Scheme interpreter early, then use it to host a substantially more capable program such as a C compiler. Micro keeps the lexical scope, evaluation rules, data model, proper tail calls, and useful procedural core of Scheme while omitting features that are expensive to implement and are not needed by the hosted program.

This document defines two layers:

The reference language is R7RS-small. Unless this document narrows a form's syntax, call shape, value domain, or resource range, the R7RS-small semantics apply.

Compatibility claim

Micro is a source profile, not an implementation-conformance claim.

A micro translation unit is a sequence of definitions and expressions. It does not contain library declarations or imports. A translation unit that uses only the micro layer can be placed after suitable imports in an R7RS-small program without changing the meaning of its supported operations.

A micro program obeys all of the following:

Every micro program is intended to have the same observable behavior when its translation unit is evaluated by micro or by an R7RS-small implementation, apart from resource exhaustion, diagnostics, and other behavior the report leaves unspecified.

Micro does not provide a library named (scheme base). That R7RS library has a fixed, substantially larger export set. A micro implementation must not accept (import (scheme base)) as a no-op or otherwise imply that it provides the complete library.

A micro+boot2 program is not necessarily an R7RS-small program. Boot2 extensions are specified separately so that a reader can identify each portability boundary.

Design rules

Micro implementations follow four rules.

  1. Standard spellings keep standard meaning. If micro accepts an R7RS form or procedure call, it has the R7RS result and effects on the supported domain.
  2. Unsupported cases fail closed. A valid R7RS construct outside the micro profile is rejected or left unbound. It must not silently produce a different result.
  3. Error-domain extensions are permitted. Boot2 may accept extra argument types or call shapes where R7RS already says the call is an error. This cannot change the result of a valid R7RS program and is useful for keeping a bootstrap host compact.
  4. Portability boundaries are visible. An extension must either have a clearly nonstandard name or be called out explicitly in the boot2 section. A private facility must not occupy an R7RS name with an unrelated contract.

These rules are more important than maximizing the number of recognized R7RS identifiers.

Goals

Non-goals

Micro does not require:

An implementation may provide additional R7RS-compatible features. They are not part of the micro portability contract unless added to this document.

Lexical and datum syntax

Micro source is case-sensitive and uses an ASCII source encoding. The character and string repertoire is implementation-defined but must include ASCII. Boot2 uses the byte values 0..255 as its repertoire and encodes each character as one byte.

Whitespace and comments

A semicolon, string quote, vertical bar, abbreviation prefix (', `, or ,), opening or closing parenthesis, or end of input terminates an adjacent token where R7RS requires it to be a delimiter, even when the delimited construct itself is outside micro.

Identifiers

Micro identifiers use the ASCII letters, digits, and these characters:

! $ % & * + - . / : < = > ? @ ^ _ ~

The first character must satisfy the R7RS rules for an ordinary or peculiar identifier. +, -, and ... are valid identifiers. A lone . is reserved for dotted-list syntax.

Vertical-bar identifiers, identifier escapes, and case-folding directives are not in micro.

The identifiers used by micro syntax are reserved within a micro program. A program that lexically rebinds one of them is outside the profile. This removes the need for syntax-binding identity in the bootstrap evaluator.

Booleans

Micro recognizes #t and #f. The long forms #true and #false and case variants are outside the profile.

Exact integers

Micro recognizes:

Binary, octal, explicit decimal, exactness, inexactness, rational, decimal point, exponent, and complex-number syntax are outside the profile.

The supported exact-integer range is implementation-defined. Boot2 uses one machine word with three tag bits: -2^60 through 2^60-1 inclusive on P1-64, and -2^28 through 2^28-1 inclusive on P1-32.

Characters

Micro recognizes:

Characters form a type disjoint from exact integers. Character/integer conversion is performed only by char->integer and integer->char.

Strings

Micro strings are mutable sequences of characters and form a type disjoint from bytevectors. A string has an explicit logical length; embedded null characters do not terminate it.

Strings created by string and make-string are mutable. Mutating a string literal is outside the micro profile, as it is an error in R7RS-small.

String literals support these escapes:

\n  \t  \r  \\  \"  \xNN...;

Other R7RS string escapes and escaped line continuations are outside the profile.

Bytevectors

Bytevectors are mutable sequences of exact integers in 0..255 and are disjoint from strings. Micro recognizes R7RS bytevector literals:

#u8(0 1 2 254 255)

Mutating a bytevector literal is outside the micro profile.

Symbols, pairs, and abbreviations

Mutating a pair, string, bytevector, or other mutable object reached through a literal datum is outside the micro profile.

Backquote, comma, comma-at, vector literals, datum labels, and shared or cyclic external representations are outside micro. Comma has a boot2-specific use inside pmatch patterns described below.

Data model

Micro has these disjoint categories:

An implementation may also have unobservable internal values for unspecified results and multiple-value packs. Boot2 additionally has private runtime types for its extensions.

boolean?, integer?, char?, symbol?, string?, bytevector?, pair?, null?, and procedure? report the corresponding disjoint categories. Because micro has only exact integers, number? is equivalent to integer?.

Evaluation model

Definitions are accepted only at the top level. A definition in a procedure, binding-form body, conditional body, or explicit begin is outside micro and must be rejected.

Core syntax

This section is exhaustive for micro syntax.

Primitive expressions

variable
literal
(quote datum)
(if test consequent)
(if test consequent alternate)
(lambda formals body ...)
(set! variable expression)
(begin expression ...)
(procedure argument ...)

Lambda formals may be a proper list, an improper list with a rest identifier, or a single rest identifier.

Boolean and conditional forms

(and expression ...)
(or expression ...)

(cond
  (test expression ...)
  (test)
  (test => procedure-expression)
  ...
  (else expression ...))

and and or return their deciding value. A successful one-element cond clause returns the value of its test. else must be the final clause.

case, when, unless, and do are not required by micro.

Binding forms

(let ((variable init) ...) body ...)
(let name ((variable init) ...) body ...)
(let* ((variable init) ...) body ...)

(let-values (((formals init) ...) ...) body ...)
(let*-values (((formals init) ...) ...) body ...)

Named let supplies the recursive binding needed by most micro loops. letrec and letrec* are deliberately omitted.

Definitions

(define variable expression)
(define (variable formal ...) body ...)
(define (variable formal ... . rest) body ...)
(define (variable . rest) body ...)

All definitions are top-level.

Records

Micro supports the R7RS define-record-type shape with a restricted constructor specification:

(define-record-type name
  (constructor field ...)
  predicate
  (field accessor)
  (field accessor mutator)
  ...)

The constructor field list must name every declared field exactly once and in the same order as the field specifications. Partial or reordered constructor lists are outside micro and must be rejected.

Record definitions are top-level. Each evaluation of a record definition creates a generative type disjoint from every other type. The constructor, predicate, accessors, and mutators otherwise have their R7RS meanings.

Core procedures

The signatures below are the call shapes guaranteed by micro. Optional or variadic R7RS call shapes not shown are outside the profile.

Equivalence and predicates

(eq? a b)
(eqv? a b)
(equal? a b)
(not obj)

(boolean? obj)       (number? obj)
(integer? obj)       (char? obj)
(symbol? obj)        (string? obj)
(bytevector? obj)    (pair? obj)
(null? obj)          (procedure? obj)

equal? is guaranteed for acyclic values. Passing a cyclic value to equal? is outside the micro profile.

Pairs and lists

(cons a b)                 (car pair)
(cdr pair)                 (set-car! pair obj)
(set-cdr! pair obj)

(list obj ...)
(list? obj)
(length list)
(append obj ...)
(reverse list)
(make-list k)
(make-list k fill)
(list-ref list k)
(list-tail list k)
(list-set! list k obj)
(list-copy obj)

Every argument to append except the last must be a finite proper list. With no arguments it returns the empty list; with one argument it returns that argument.

Micro also provides the R7RS c[ad]+r compositions containing two through four selector letters, implemented as ordinary Scheme procedures.

List walkers require finite lists. list? is guaranteed for acyclic input; passing it a circular list is outside micro.

Membership and association calls are restricted to the two-argument forms:

(memq obj list)             (memv obj list)
(member obj list)
(assq obj alist)            (assv obj alist)
(assoc obj alist)

The optional comparison-procedure arguments of member and assoc are not part of micro.

Exact integers

(+ integer ...)
(* integer ...)
(- integer integer ...)

(= integer integer ...)
(< integer integer ...)
(> integer integer ...)
(<= integer integer)
(>= integer integer)

(zero? integer)
(positive? integer)
(negative? integer)
(abs integer)
(min integer integer)
(max integer integer)

(quotient integer nonzero-integer)
(remainder integer nonzero-integer)
(modulo integer nonzero-integer)

The identities and unary behavior of +, *, and - are those of R7RS. quotient truncates toward zero, remainder has the sign of the dividend, and modulo has the sign of the divisor.

Every exact result must be representable in the implementation's advertised range. An implementation that cannot represent a result must terminate the evaluation with an implementation-restriction diagnostic; it must not silently wrap or invoke host undefined behavior.

There is no / procedure and no non-integer numeric tower in micro.

Characters

(char? obj)
(char->integer char)
(integer->char integer)

integer->char is defined only for integers corresponding to a character in the implementation's advertised repertoire.

Strings and symbols

(make-string k)
(make-string k char)
(string char ...)
(string? obj)
(string-length string)
(string-ref string k)
(string-set! string k char)
(string=? string1 string2 string ...)

(symbol? obj)
(symbol=? symbol1 symbol2 symbol ...)
(symbol->string symbol)
(string->symbol string)

(number->string integer)
(number->string integer radix)
(string->number string)
(string->number string radix)

Micro guarantees radix 10 and 16 for number/string conversion. A different radix is outside the profile and must be rejected, not treated as radix 10.

symbol->string and number->string return strings, not bytevectors.

Other string operations, character ordering and classification, Unicode case mapping, and case-insensitive string operations are not required by micro.

Bytevectors

(bytevector byte ...)
(make-bytevector k)
(make-bytevector k byte)
(bytevector? obj)
(bytevector-length bytevector)
(bytevector-u8-ref bytevector k)
(bytevector-u8-set! bytevector k byte)
(bytevector-copy bytevector start end)
(bytevector-copy! to at from start end)
(bytevector-append bytevector ...)
(bytevector=? bytevector bytevector)

Micro requires explicit bounds for both copy procedures. Copies behave as if the source range were first copied to temporary storage, so overlapping source and destination ranges work.

The omitted optional start/end call shapes are outside micro.

Procedures and iteration

(procedure? obj)
(apply procedure argument ... final-list)
(map procedure list1 list ...)
(for-each procedure list1 list ...)
(values obj ...)
(call-with-values producer consumer)

map and for-each stop at the shortest list. All calls made by these procedures preserve the R7RS tail/non-tail relationships.

Errors and output

(error message irritant ...)

Micro has no exception system. error is a non-returning operation that emits an implementation-defined diagnostic and terminates evaluation. Because a micro program cannot install an exception handler, it cannot distinguish this from an uncaught R7RS error except through unspecified diagnostic and process details.

General datum output is not required by micro. Boot2 supplies output and formatting extensions for diagnostics and generated files.

Failure and resource model

The following terminate evaluation with a diagnostic:

Micro does not require these failures to be catchable. A diagnostic should identify the failed implementation restriction when practical.

Fixed limits are expected in bootstrap implementations. They are compatible with micro when they fail explicitly rather than corrupting memory, silently changing a result, or relying on host undefined behavior.

Boot2 extensions

The boot2 extensions exist to host cc.scm, drive bootstrap subprocesses, and make a small freestanding interpreter observable. They are not part of micro and are not promised by another micro implementation.

Because micro has no library system, boot2 extensions live in the same initial environment. Their status is established by this section rather than an import name.

Byte-oriented string bridge

The C compiler is byte-oriented but contains many convenient string literals. Boot2 therefore extends several bytevector operations to accept a string in a position where R7RS requires a bytevector:

(bytes? obj)                         ; string or bytevector
(bytes=? bytes bytes)
(bytevector-length string)
(bytevector-u8-ref string k)
(bytevector-u8-set! string k byte)
(bytevector-copy string start end)
(bytevector-copy! to at from start end)
(bytevector-append bytes ...)
(bytevector=? bytes bytes)

Here bytes means a string or bytevector. A mixed or string source is observed as the implementation repertoire's byte encoding, and constructors/copies that produce byte storage return a bytevector.

bytes=? compares two byte sequences without requiring them to have the same string/bytevector type. Standard equal?, member, and assoc retain their R7RS type distinctions; boot2 code that intentionally mixes strings and bytevectors must opt into bytes=? or another byte-aware extension.

This extension does not make the types identical:

(string? "abc")                  ; #t
(bytevector? "abc")              ; #f
(bytes? "abc")                   ; #t
(string? #u8(97 98 99))          ; #f
(bytevector? #u8(97 98 99))      ; #t
(bytes=? "abc" #u8(97 98 99))   ; #t
(equal? "abc" #u8(97 98 99))    ; #f

Boot2 also permits a bytevector as the input to string->number and string->symbol, and permits strings where a syscall expects pathname or output bytes. These are extensions of R7RS error domains, not changes to valid R7RS calls.

Pattern matching

pmatch is a boot2 special form used heavily by the C compiler:

(pmatch expression
  (pattern body ...)
  (pattern (guard guard-expression ...) body ...)
  ...
  (else body ...))

The subject is evaluated once. Clauses are attempted from first to last. A matched clause evaluates its body in an environment extended by its pattern bindings. Every guard expression must produce a true value. Failure to match a clause terminates evaluation unless an else clause is present.

Patterns are:

()                         empty list
literal                    equal? literal match; byte literals use bytes=?
symbol                     that exact symbol; symbols are not binders
,identifier                bind the matched value
,_                         wildcard without a binding
(pattern ...)              proper-list pattern
(pattern ... . pattern)    improper-list pattern
($ predicate
   (accessor pattern) ...) record predicate/accessor pattern

Comma is recognized as binding syntax only in a pmatch pattern. It is not micro unquote, and boot2 does not provide quasiquotation.

The byte-aware literal rule lets a string-literal pattern match a bytevector token with the same bytes. This behavior belongs to pmatch; it does not widen the micro equal? procedure.

guard and $ in this grammar are pmatch syntax, not R7RS bindings.

Bit operations

Boot2 provides exact-machine-integer operations used by the C compiler:

(bit-and integer ...)
(bit-or integer ...)
(bit-xor integer ...)
(bit-not integer)
(arithmetic-shift integer count)

Their domain is the boot2 tagged machine integer representation. The logical model is an infinite two's-complement exact integer: negative shift counts shift right with sign extension and nonnegative counts shift left. A result outside the advertised exact-integer range is an implementation restriction and must fail explicitly. Bit patterns and shifts are boot2 extensions rather than R7RS-small operations.

Compiler utility procedures

Boot2 supplies these ordinary Scheme helpers:

(filter predicate list)
(fold procedure initial list)
(format template argument ...)

fold is a left fold. format recognizes:

~a  display-style value
~s  write-style value
~d  decimal integer
~x  lowercase hexadecimal integer
~%  newline
~~  literal tilde

format accepts a string or bytevector template and returns a bytevector so that compiler output can be appended and written without conversion.

Boot2 may also provide display and write for diagnostics. They accept a single value, write to file descriptor 1, and support the acyclic value types available to boot2. They are conveniences corresponding to the R7RS writer where their domains overlap, but they are not part of micro.

Compiler hash tables

Boot2 provides a private mutable map for compiler-wide namespaces whose alist representation would otherwise make repeated lookup and insertion quadratic:

(%make-hash-table capacity-hint)
(%hash-ref table key)             ; value, or #f when absent
(%hash-set! table key value)      ; unspecified
(%hash-delete! table key)         ; #t when removed, otherwise #f
(%hash-size table)                ; number of live entries

The % prefix is intentional: these are representation-oriented boot2 operations, not an implementation of an SRFI or another Scheme hash-table API. The capacity hint is a nonnegative exact integer; the implementation may round it and grows the table automatically.

String and bytevector keys hash and compare by byte content, including mixed string/bytevector keys, following the byte-oriented bridge above. All other keys compare by eq?. A byte key must not be mutated while it is present in a table. %hash-ref uses #f as its missing sentinel, so callers that need to distinguish a stored #f from absence must use another representation.

Tables and their entries are managed and traced by the garbage collector. Resizing or collection does not change the identity of the table object.

EOF value

Boot2 has a singleton EOF value bound as eof and recognized by:

(eof? obj)

These names are boot2 extensions. Micro does not define a standard port or EOF interface.

Raw syscalls

Boot2 exposes the freestanding operations needed by the bootstrap environment:

(sys-read fd bytevector offset count)
(sys-write fd bytes offset count)
(sys-close fd)
(sys-openat dirfd path flags mode)
(sys-clone)
(sys-execve path argv)
(sys-spawn path argv)
(sys-waitid idtype id info-bytevector options)
(sys-argv)
(sys-exit status)

Except for sys-exit, each syscall wrapper returns:

(#t . value)       ; success
(#f . errno)       ; failure

sys-exit does not return. sys-spawn is available only on bootstrap targets whose kernel supplies it; the boot2 process layer probes it and otherwise uses sys-clone plus sys-execve.

sys-argv and its argv convenience wrapper return the boot2 argument vector as a list of bytevectors. The elements may be compared with string literals through the byte-oriented string bridge.

File-descriptor ports

Boot2's buffered file handles are not R7RS ports. Operations whose historical names collide with the standard port API use fd-specific names.

The target names are:

(fd-port? obj)
(port-fd port)

(open-input path)                 ; result pair containing fd-port
(open-output path)                ; result pair containing fd-port
(open-append path)                ; result pair containing fd-port
(close port)                      ; result pair

(read-bytes port count)           ; result pair containing bv or eof
(fd-read-line/result port)        ; result pair containing bv or eof
(read-all port)                   ; result pair containing bv

(write-bytes port bytevector)     ; result pair
(fd-write-string/result port bytes)
(write-line port bytes)           ; result pair

The preconstructed handles stdin, stdout, and stderr are fd ports.

The historical boot2 names port?, read-line, and write-string conflict with R7RS names and are not part of the target extension API. Implementations should migrate callers to the names above and remove the historical bindings.

Process helpers

The boot2 prelude builds these procedures on the syscall and fd layers:

(spawn program argument ...)
(run program argument ...)
(wait pid)
(decode-wait-status raw-status)
(file-exists? path)

spawn, run, and wait return the boot2 result-pair convention. run waits for the child and returns its decoded status on success.

For a string pathname, file-exists? has the behavior of the corresponding R7RS optional-library procedure. Boot2 additionally accepts a bytevector pathname through the byte-oriented bridge.

The R7RS optional-library names command-line and exit are not required by micro+boot2. Bootstrap code should use argv and sys-exit unless those standard names are separately implemented with their R7RS contracts.

Record and heap introspection

Boot2 exposes low-level operations used for diagnostics and generic copying:

(record? obj)
(record-td record)
(record-ref record index)
(record-set! record index value)
(make-record/td type-descriptor)
(td-nfields type-descriptor)
(td-name type-descriptor)

(make-deep-copy-context)
(deep-copy context obj)

(heap-usage)
(collect-garbage)
(target-word-bytes)
(target-word-bits)

These procedures expose representation details and are not portable Scheme. The indexed record operations require a record and a valid field index. The target-word procedures return 4/32 on P1-32 and 8/64 on P1-64; they let bootstrap tools such as cc.scm choose target-sized layouts.

Unsafe memory inspection

Boot2 may provide:

(tagged-value obj)
(peek-memory-u8 address)

tagged-value exposes the raw tagged representation of an object. peek-memory-u8 reads a byte from a raw address and is intended only for runtime debugging. Invalid addresses have unrestricted consequences.

The historical name peek-u8 conflicts with the R7RS port procedure and must not be used for this operation.

Deliberately omitted R7RS-small areas

The following remain out of scope unless a bootstrap workload demonstrates a need for them:

Area Reason
Library/import system Concatenation supplies the fixed bootstrap environment.
syntax-rules and local syntax The compiler uses pmatch, ordinary procedures, and records instead.
Internal definitions and letrec Named let and top-level mutually recursive procedures cover the workload.
Exceptions Fatal diagnostics and explicit result pairs cover compiler and syscall failures.
Continuations and dynamic extent No bootstrap workload requires them; implementation cost is high.
Parameters Explicit state is simpler and already used by the compiler.
Vectors Lists, records, and bytevectors cover current data structures.
Standard ports and read The compiler consumes files as bytevectors through a small fd layer.
Numeric tower Exact machine integers are sufficient for parsing and code generation.
Full string/character libraries The compiler is byte-oriented and uses only character conversion.
Shared/cyclic datum I/O Source and generated output do not require it.
Optional libraries None is needed to reach the next bootstrap stage.

Implementation work should be justified by a concrete micro program or bootstrap workload rather than by the size of the remaining R7RS export list.

Conformance and regression testing

Tests are divided by layer.

Micro tests

A micro test:

Where practical, the same test body should be run under boot2 and a reference R7RS-small system after adding the reference system's imports and a minimal result harness.

Boot2 tests

Boot2 tests cover:

The C compiler and full bootstrap acceptance tests are the primary integration tests for micro+boot2.

Boot2 implementation migration

The existing scheme1 implementation predates this profile. Reaching the target requires these changes, in order:

  1. Correct the silent divergences: one-expression cond, unsupported radix fallback, overlapping copies, unbound set!, and record constructor validation.
  2. Rename the private port?, read-line, write-string, and raw-memory peek-u8 bindings.
  3. Introduce a character representation disjoint from exact integers.
  4. Introduce a length-bearing string representation disjoint from bytevectors.
  5. Add the byte-oriented string bridge, bytes?, and bytes=?; update the compiler's mixed-type predicates and alist comparisons to use them. Make pmatch byte-literal matching use bytes=?.
  6. Make datum output correct for supported characters, strings, symbols, and acyclic compound values.
  7. Detect and report unrepresentable exact-integer results.
  8. Split or clearly label the portable micro prelude and boot2 extension prelude.

The repository's scheme1 interpreter, prelude, compiler, bootstrap drivers, and conformance fixtures implement this migration. Future changes should keep the micro and boot2 layers visibly separated and preserve the negative tests for rejected syntax, call shapes, radices, constructor forms, and exact-range overflow.