Libraries

Libraries are pieces of code that can be incorporated into larger programs, and especially into programs that use library code from multiple sources. The library system supports macro definitions within libraries, allows macro exports, and distinguishes the phases in which definitions and imports are needed.

Libraries address the following specific goals:

Separate compilation and analysis
No two libraries have to be compiled at the same time (i.e., the meanings of two libraries cannot depend on each other cyclically, and compilation of two different libraries cannot rely on state shared across compilations), and significant program analysis can be performed without examining a whole program.
Independent compilation/analysis of unrelated libraries
“Unrelated” means that neither depends on the other through a transitive closure of imports.
Explicit declaration of dependencies
The meaning of each identifier is clear at compile time. Hence, there is no ambiguity about whether a library needs to be executed for another library’s compile time and/or run time.
Namespace management
This helps prevent name conflicts.

This chapter defines the notation for libraries and a semantics for library expansion and execution.

6.1  Library form

A library definition must have the following form:

(library <library name>
  (export <export spec> ...)
  (import <import spec> ...)
  <library body>)

A library declaration contains the following elements:

An identifier can be imported with the same local name from two or more libraries or for two levels from the same library only if the binding exported by each library is the same (i.e., the binding is defined in one library, and it arrives through the imports only by exporting and re-exporting). Otherwise, no identifier can be imported multiple times, defined multiple times, or both defined and imported. No identifiers are visible within a library except for those explicitly imported into the library or defined within the library.

A <library name> has the following form:

(<identifier1> <identifier2... <version>)

where <version> is empty or has the following form:

(<sub-version> ...)

Each <sub-version> must be an exact nonnegative integer. An empty <version> is equivalent to ().

Each <import spec> specifies a set of bindings to be imported into the library, the levels at which they are to be available, and the local names by which they are to be known. An <import spec> must be one of the following:

<import set>
(for <import set> <import level> ...)

An <import level> is one of the following:

run
expand
(meta <level>)

where <level> is an exact integer.

As an <import level>, run is an abbreviation for (meta 0), and expand is an abbreviation for (meta 1). Levels and phases are discussed in section 6.2.

An <import set> names a set of bindings from another library and possibly specifies local names for the imported bindings. It must be one of the following:

<library reference>
(only <import set> <identifier> ...)
(except <import set> <identifier> ...)
(prefix <import set> <identifier>)
(rename <import set> (<identifier> <identifier>) ...)

A <library reference> identifies a library by its name and optionally by its version. It has the following form:

(<identifier1> <identifier2... <version reference>)

A <version reference> specifies a set of <version>s that it matches. The <library reference> identifies all libraries of the same name and whose version is matched by the <version reference>. A <version reference> is empty or has the following form:

(<sub-version reference1... <sub-version referencen>)
(and <version reference> ...)
(or <version reference> ...)
(not <version reference>)

An empty <version reference> is equivalent to (). A <version reference> of the first form matches a <version> with at least n elements, whose <sub-version reference>s match the corresponding <sub-version>s. An and <version reference> matches a version if all <version references> following the and match it. Correspondingly, an or <version reference> matches a version if one of <version references> following the or matches it, and a not <version reference> matches a version if the <version reference> following it does not match it.

A <sub-version reference> has one of the following forms:

<sub-version>
(>= <sub-version>)
(<= <sub-version>)
(and <sub-version reference> ...)
(or <sub-version reference> ...)
(not <sub-version reference>)

A <sub-version reference> of the first form matches a <sub-version> if it is equal to it. A >= <sub-version reference> of the first form matches a sub-version if it is greater or equal to the <sub-version> following it; analogously for <=. An and <sub-version reference> matches a sub-version if all of the subsequent <sub-version reference>s match it. Correspondingly, an or <sub-version reference> matches a sub-version if one of the subsequent <sub-version reference>s matches it, and a not <sub-version reference> matches a sub-version if the subsequent <sub-version reference> does not match it.

Examples:

version reference version match?
() (1) yes
(1) (1) yes
(1) (2) no
(2 3) (2) no
(2 3) (2 3) yes
(2 3) (2 3 5) yes
(or (1 (>= 1)) (2)) (2) yes
(or (1 (>= 1)) (2)) (1 1) yes
(or (1 (>= 1)) (2)) (1 0) no
((or 1 2 3)) (1) yes
((or 1 2 3)) (2) yes
((or 1 2 3)) (3) yes
((or 1 2 3)) (4) no

When more than one library is identified by a library reference, the choice of libraries is determined in some implementation-dependent manner.

To avoid problems such as incompatible types and replicated state, two libraries whose library names contain the same sequence of identifiers but whose versions do not match cannot co-exist in the same program.

By default, all of an imported library’s exported bindings are made visible within an importing library using the names given to the bindings by the imported library. The precise set of bindings to be imported and the names of those bindings can be adjusted with the only, except, prefix, and rename forms as described below.

It is a syntax violation if a constraint given above is not met.

An <export spec> names a set of imported and locally defined bindings to be exported, possibly with different external names. An <export spec> must have one of the following forms:

<identifier>
(rename (<identifier1> <identifier2>) ...)

In an <export spec>, an <identifier> names a single binding defined within or imported into the library, where the external name for the export is the same as the name of the binding within the library. A rename spec exports the binding named by the first <identifier> in each (<identifier> <identifier>) pairing, using the second <identifier> as the external name.

The <library body> of a library form consists of forms that are classified as definitionsor expressions. Which forms belong to which class depends on the imported libraries and the result of expansion—see chapter 8. Generally, forms that are not definitions (see section 9.3 for definitions available through the base library) are expressions.

A <library body> is like a <body> (see section 9.4) except that a <library body>s need not include any expressions. It must have the following form:

<definition> ... <expression> ...

When base-library begin, let-syntax, or letrec-syntax forms occur in a top-level body prior to the first expression, they are spliced into the body; see section 9.5.7. Some or all of the body, including portions wrapped in begin, let-syntax, or letrec-syntax forms, may be specified by a syntactic abstraction (see section 6.3.2).

The transformer expressions and bindings are evaluated and created from left to right, as described in chapter 8. The variable-definition right-hand-side expressions are evaluated from left to right, as if in an implicit letrec*, and the body expressions are also evaluated from left to right after the variable-definition right-hand-side expressions. A fresh location is created for each exported variable and initialized to the value of its local counterpart. The effect of returning twice to the continuation of the last body expression is unspecified.

The names library, export, import, for, run, expand, meta, import, export, only, except, prefix, rename, and, or, >=, and <= appearing in the library syntax are part of the syntax and are not reserved, i.e., the same names can be used for other purposes within the library or even exported from or imported into a library with different meanings, without affecting their use in the library form.

Bindings defined with a library are not visible in code outside of the library, unless the bindings are explicitly exported from the library. An exported macro may, however, implicitly export an otherwise unexported identifier defined within or imported into the library. That is, it may insert a reference to that identifier into the output code it produces.

All explicitly exported variables are immutable in both the exporting and importing libraries. It is thus a syntax violation if an explicitly exported variable appears on the left-hand side of a set! expression, either in the exporting or importing libraries.

All implicitly exported variables are also immutable in both the exporting and importing libraries. It is thus a syntax violation if a variable appears on the left-hand side of a set! expression in any code produced by an exported macro outside of the library in which the variable is defined. It is also a syntax violation if a reference to an assigned variable appears in any code produced by an exported macro outside of the library in which the variable is defined, where an assigned variable is one that appears on the left-hand side of a set! expression in the exporting library.

All other variables defined within a library are mutable.

Rationale:   The asymmetry in the prohibitions against assignments to explicitly and implicitly exported variables reflects the fact that the violation can be determined for implicitly exported variables only when the importing library is expanded.

6.2  Import and export levels

Every library can be characterized by expand-time information (minimally, its imported libraries, a list of the exported keywords, a list of the exported variables, and code to evaluate the transformer expressions) and run-time information (minimally, code to evaluate the variable definition right-hand-side expressions, and code to evaluate the body expressions). The expand-time information must be available to expand references to any exported binding, and the run-time information must be available to evaluate references to any exported variable binding.

Expanding a library may require run-time information from another library. For example, if a library provides procedures that are called by another library’s macros during expansion, then the former library must be run when expanding the latter. The former may not be needed when the latter is eventually run as part of a program, or it may be needed for the latter’s run time, too.

A phase is a time at which the expressions within a library are evaluated. Within a library body, top-level expressions and the right-hand sides of define forms are evaluated at run time, i.e., phase 0, and the right-hand sides of define-syntax forms are evaluated at expand time, i.e., phase 1. When define-syntax, let-syntax, or letrec-syntax forms appear within code evaluated at phase n, the right-hand sides are evaluated as phase n + 1 expressions.

These phases are relative to the phase in which the library itself is used. An instance of a library corresponds to an evaluation of its variable definitions and expressions in a particular phase relative to another library—a process called instantiation. For example, if a top-level expression in a library L1 refers to a variable export from another library L0, then it refers to the export from an instance of L0 at phase 0 (relative to the phase of L1). But if a phase 1 expression within L1 refers to the same binding from L0, then it refers to the export from an instance of L0 at phase 1 (relative to the phase of L1).

A visit of a library corresponds to the evaluation of its syntax definitions in a particular phase relative to another library—a process called visiting. Evaluating a syntax definition at phase n means that its right-hand side is evaluated at phase n + 1. For example, if a top-level expression in a library L1 refers to a macro export from another library L0, then it refers to the export from an visit of L0 at phase 0 (relative to the phase of L1), which corresponds to the evaluation of the macro’s transformer expression at phase 1.

A level is a lexical property of an identifier that determines in which phases it can be referenced. The level for each identifier bound by a definition within a library is 0; that is, the identifier can be referenced only by phase 0 expressions within the library. The level for each imported binding is determined by the enclosing for form of the import in the importing library, in addition to the levels of the identifier in the exporting library. Import and export levels are combined by pairwise addition of all level combinations. For example, references to an imported identifier exported for levels pa and pb and imported for levels qa, qb, and qc are valid at levels pa + qa, pa + qb, pa + qc, pb + qa, pb + qb, and pb + qc. An <import set> without an enclosing for is equivalent to (for <import set> run), which is the same as (for <import set> (meta 0)).

The export level of an exported binding is 0 for all bindings that are defined within the exporting library. The export levels of a reexported binding, i.e., an export imported from another library, are the same as the effective import levels of that binding within the reexporting library.

For the libraries defined in the library report, the export level is 0 for nearly all bindings. The exceptions are syntax-rules and identifier-syntax from the (rnrs base (6)) library, which are exported with level 1, and all bindings from the composite (rnrs (6)) library (see library chapter on “Composite library”), which are exported with levels 0 and 1.

Rationale:   The (rnrs (6)) library is intended as a convenient import for libraries where fine control over imported bindings is not necessary or desirable. The (rnrs (6)) library exports all bindings for expand as well as run so that it is convenient for writing syntax-case macros as well as run-time code.

Macro expansion within a library can introduce a reference to an identifier that is not explicitly imported into the library. In that case, the phase of the reference must match the identifier’s level as shifted by the difference between the phase of the source library (i.e., the library that supplied the identifier’s lexical context) and the library that encloses the reference. For example, suppose that expanding a library invokes a macro transformer, and the evaluation of the macro transformer refers to an identifier that is exported from another library (so the phase 1 instance of the library is used); suppose further that the value of the binding is a syntax object representing an identifier with only a level-n binding; then, the identifier must be used only in a phase n + 1 expression in the library being expanded. This combination of levels and phases is why negative levels on identifiers can be useful, even though libraries exist only at non-negative phases.

If any of a library’s definitions are referenced at phase 0 in the expanded form of a program, then an instance of the referenced library is created for phase 0 before the program’s definitions and expressions are evaluated. This rule applies transitively: if the expanded form of one library references at phase 0 an identifier from another library, then before the referencing library is instantiated at phase n, the referenced library must be instantiated at phase n. When an identifier is referenced at any phase n greater than 0, in contrast, then the defining library is instantiated at phase n at some unspecified time before the reference is evaluated. Similarly, when a macro keyword is referenced at phase n during the expansion of a library, then the defining library is visited at phase n at some unspecified time before the reference is evaluated.

An implementation is allowed to distinguish instances/visits of a library for different phases or to use an instance/visit at any phase as an instance/visit at any other phase. An implementation is further allowed to start each expansion of a library form by removing visits of libraries in any phase and/or instances of libraries in phases above 0. An implementation is allowed to create instances/visits of more libraries at more phases than required to satisfy references. When an identifier appears as an expression in a phase that is inconsistent with the identifier’s level, then an implementation may raise an exception either at expand time or run time, or it may allow the reference. Thus, a library is portable only when it references identifiers in phases consistent with the declared levels, and a library whose meaning depends on whether the instances of a library are distinguished or shared across phases or library expansions may be unportable.

Rationale:   Opinions vary on how libraries should be instantiated and initialized during the expansion and execution of library bodies, whether library instances should be distinguished across phases, and whether levels should be declared so that they constrain identifier uses to particular phases. This report therefore leaves considerable latitude to implementations, while attempting to provide enough guarantees to make portable libraries practical.

Note:   If a program and its libraries avoid the (rnrs (6)) and (rnrs syntax-case (6)) libraries, and if the program and libraries never use the for import form, then the program does not depend on whether instances are distinguished across phases, and the phase of an identifier’s use cannot be inconsistent with the identifier’s level.

6.3  Primitive syntax

After the import form within a library form, the forms that constitute a library body depend on the libraries that are imported. In particular, imported syntactic keywords determine most of the available forms and whether each form is a definition or expression. A few form types are always available independent of imported libraries, however, including constant literals, variable references, procedure calls, and macro uses.

6.3.1  Primitive expression types

The entries in this section all describe expressions, which may occur in the place of <expression> syntactic variables. See also section 9.5.

Constant literals

<constant>    syntax 

Numerical constants, string constants, character constants, and boolean constants evaluate “to themselves”.

"abc"              ⇒  "abc"
145932             ⇒  145932
#t           ⇒  #t

As noted in section 4.8, the value of a literal expression is immutable.

Variable references

<variable>    syntax 

An expression consisting of a variable(section 4.2) is a variable reference. The value of the variable reference is the value stored in the location to which the variable is bound. It is a syntax violation to reference an unboundvariable.

; These examples assume the base library
; has been imported.
(define x 28)
x           ⇒  28

Procedure calls

(<operator> <operand1> ...)    syntax 

A procedure call is written by simply enclosing in parentheses expressions for the procedure to be called and the arguments to be passed to it. A form in an expression context is a procedure call if <operator> is not an identifier bound as a syntactic keyword.

When a procedure call is evaluated, the operator and operand expressions are evaluated (in an unspecified order) and the resulting procedure is passed the resulting arguments.

; These examples assume the base library
; has been imported.
(+ 3 4)                                  ⇒  7
((if #f + *) 3 4)                 ⇒  12

If the value of <operator> is not a procedure, an exception with condition type &assertion is raised.

Note:   In contrast to other dialects of Lisp, the order of evaluation is unspecified, and the operator expression and the operand expressions are always evaluated with the same evaluation rules.

Note:   Although the order of evaluation is otherwise unspecified, the effect of any concurrent evaluation of the operator and operand expressions is constrained to be consistent with some sequential order of evaluation. The order of evaluation may be chosen differently for each procedure call.

Note:   In many dialects of Lisp, the form () is a legitimate expression. In Scheme, expressions written as list/pair forms must have at least one subexpression, so () is not a syntactically valid expression.

6.3.2  Macros

Scheme libraries can define and use new derived expressions and definitions called syntactic abstractions or macros.A syntactic abstraction is created by binding a keyword to a macro transformer or, simply, transformer. The transformer determines how a use of the macro is transcribed into a more primitive form.

Macro uses typically have the form:

(<keyword> <datum> ...)

where <keyword> is an identifier that uniquely determines the type of form. This identifier is called the syntactic keyword, or simply keyword, of the macro. The number of <datum>s and the syntax of each depends on the syntactic abstraction. Macro uses can also take the form of improper lists, singleton identifiers, or set! forms, where the second subform of the set! is the keyword (see library section on “make-variable-transformer”):

(<keyword> <datum> ... . <datum>)
<keyword>
(set! <keyword> <datum>)

The macro definition facility consists of two parts:

Keywords occupy the same name space as variables. That is, within the same scope, an identifier can be bound as a variable or keyword, or neither, but not both, and local bindings of either kind may shadow other bindings of either kind.

Macros defined using syntax-rules are “hygienic” and “referentially transparent” and thus preserve Scheme’s lexical scoping [282731017]:

Macros defined using the syntax-case facility are also hygienic unless datum->syntax (see library section on “Syntax-object and datum conversions”) is used.

6.4  Examples

Examples for various <import spec>s and <export spec>s:

(library (stack)
  (export make push! pop! empty!)
  (import (rnrs (6)))

  (define (make) (list ’()))
  (define (push! s v) (set-car! s (cons v (car s))))
  (define (pop! s) (let ([v (caar s)])
                     (set-car! s (cdar s))
                     v))
  (define (empty! s) (set-car! s ’())))

(library (balloons)
  (export make push pop)
  (import (rnrs (6)))

  (define (make w h) (cons w h))
  (define (push b amt)
    (cons (- (car b) amt) (+ (cdr b) amt)))
  (define (pop b) (display "Boom! ") 
                  (display (* (car b) (cdr b))) 
                  (newline)))

(library (party)
  ;; Total exports:
  ;; make, push, push!, make-party, pop!
  (export (rename (balloon:make make)
                  (balloon:push push))
          push!
          make-party
          (rename (party-pop! pop!)))
  (import (rnrs (6))
          (only (stack) make push! pop!) ; not empty!
          (prefix (balloons) balloon:))

  ;; Creates a party as a stack of balloons,
  ;; starting with two balloons
  (define (make-party)
    (let ([s (make)]) ; from stack
      (push! s (balloon:make 10 10))
      (push! s (balloon:make 12 9))
      s))
  (define (party-pop! p)
    (balloon:pop (pop! p))))


(library (main)
  (export)
  (import (rnrs (6)) (party))

  (define p (make-party))
  (pop! p)        ; displays "Boom! 108"
  (push! p (push (make 5 5) 1))
  (pop! p))       ; displays "Boom! 24"

Examples for macros and phases:

(library (my-helpers id-stuff)
  (export find-dup)
  (import (rnrs (6)))

  (define (find-dup l)
    (and (pair? l)
         (let loop ((rest (cdr l)))
           (cond
            [(null? rest) (find-dup (cdr l))]
            [(bound-identifier=? (car l) (car rest)) 
             (car rest)]
            [else (loop (cdr rest))])))))

(library (my-helpers values-stuff)
  (export mvlet)
  (import (rnrs (6)) (for (my-helpers id-stuff) expand))

  (define-syntax mvlet
    (lambda (stx)
      (syntax-case stx ()
        [(_ [(id ...) expr] body0 body ...)
         (not (find-dup (syntax (id ...))))
         (syntax
           (call-with-values
               (lambda () expr) 
             (lambda (id ...) body0 body ...)))]))))

(library (let-div)
  (export let-div)
  (import (rnrs (6))
          (my-helpers values-stuff)
          (rnrs r5rs (6)))

  (define (quotient+remainder n d)
    (let ([q (quotient n d)])
      (values q (- n (* q d)))))
  (define-syntax let-div
    (syntax-rules ()
     [(_ n d (q r) body0 body ...)
      (mvlet [(q r) (quotient+remainder n d)]
        body0 body ...)])))