unitsig.ss: Units with Signatures

To load: (require (lib "unitsig.ss"))

The unit syntax presented in section 51 poses a serious notational problem: each variable that is imported or exported must be separately enumerated in many import, export, and link clauses. Consider the phone book program example from section 51.3: a realistic graphics@ unit would contain many more procedures than make-window and make-button, and it would be unreasonable to enumerate the entire graphics toolbox in every client module. Future extensions to the graphics library are likely, and while the program must certainly be re-compiled to take advantage of the changes, the programmer should not be required to change the program text in every place that the graphics library is used.

This problem is solved by separating the specification of a unit's signature (or ``interface'') from its implementation. A unit signature is essentially a list of variable names. A signature can be used in an import clause, an export clause, a link clause, or an invocation expression to import or link a set of variables at once. Signatures clarify the connections between units, prevent mis-orderings in the specification of imported variables, and provide better error messages when an illegal linkage is specified.

Signatures are used to create units with signatures, a.k.a. signed units. Signatures and signed units are used together to create signed compound units. As in the core system, a signed compound unit is itself a signed unit.

Signed units are first-class values, just like their counterparts in the core system. A signature is not a value. However, signature information is bundled into each signed unit value so that signature-based checks can be performed at run time (when signed units are linked and invoked).

Along with its signature information, a signed unit includes a primitive unit from the core system that implements the signed unit. This underlying unit can be extracted for mixed-mode programs using both signed and unsigned units. More importantly, the semantics of signed units is the same as the semantics for regular units; the additional syntax only serves to specify signatures and to check signatures for linking.

52.1  Importing and Exporting with Signatures

The unit/sig form creates a signed unit in the same way that the unit form creates a unit in the core system. The only difference between these forms is that signatures are used to specify the imports and exports of a signed unit.

In the primitive unit form, the import clause only determines the number of variables that will be imported when the unit is linked; there are no explicitly declared connections between the import variables. In contrast, a unit/sig form's import clause does not specify individual variables; instead, it specifies the signatures of units that will provide its imported variables, and all of the variables in each signature are imported. The ordered collection of signatures used for importing in a signed unit is the signed unit's import signature.

Although the collection of variables to be exported from a unit/sig expression is specified by a signature rather than an immediate sequence of variables,13 variables are exported in a unit/sig form in the same way as in the unit form. The export signature of a signed unit is the collection of names exported by the unit.


(define-signature arithmetic^ (add subtract multiply divide power))
(define-signature calculus^ (integrate))
(define-signature graphics^ (add-pixel remove-pixel))
(define-signature gravity^ (go))
(define gravity@
  (unit/sig gravity^ (import arithmetic^ calculus^ graphics^)
    (define go (lambda (start-pos) ... subtract ... add-pixel ...))))

In this program fragment, the signed unit gravity@ imports a collection of arithmetic procedures, a collection of calculus procedures, and a collection of graphics procedures. The arithmetic collection will be provided through a signed unit that matches the arithmetic^ (export) signature, while the graphics collection will be provided through a signed unit that matches the graphics^ (export) signature. The gravity@ signed unit itself has the export signature gravity^.

Suppose that the procedures in graphics^ were named add and remove rather than add-pixel and remove-pixel. In this case, the gravity@ unit cannot import both the arithmetic^ and graphics^ signatures as above, because the name add would be ambiguous in the unit body. To solve this naming problem, the imports of a signed unit can be distinguished by providing prefix tags:

(define-signature graphics^ (add remove))
(define gravity@
  (unit/sig gravity^ (import (a : arithmetic^) (c : calculus^) (g : graphics^))
    (define go (lambda (start-pos) ... a:subtract ... g:add ...))))

Details for the syntax of signatures are in section 52.2. The full unit/sig syntax is described in section 52.3.

52.2  Signatures

A signature is either a signature description or a bound signature identifier:

(sig-element ···) 

sig-element is one of
  (struct base-identifier (field-identifier ···) omission ···) 
  (open signature) 
  (unit identifier : signature)

omission is one of
  (- variable)

Together, the element descriptions determine the set of elements that compose the signature:

The names of all elements in a signature must be distinct.14 Two signatures match when they contain the same element names, and when a name in both signatures is either a variable name in both signatures or a sub-signature name in both signatures such that the sub-signatures match. The order of elements within a signature is not important. A source signature satisfies a destination signature when the source signature has all of the elements of the destination signature, but the source signature may have additional elements.

The define-signature form binds a signature to an identifier:

(define-signature signature-identifier signature)

The let-signature form binds a signature to an identifier within a body of expressions:

(let-signature identifier signature body-expr ···1)

For various purposes, signatures must be flattened into a linear sequence of variables. The flattening operation is defined as follows:

52.3  Signed Units

The unit/sig form creates a signed unit:

(unit/sig signature 
  (import import-element ···) 

import-element is one of
  (identifier : signature) 

renames is either empty or
  (rename (internal-variable signature-variable) ···)

The signature immediately following unit/sig specifies the export signature of the signed unit. This signature cannot contain sub-signatures. Each element of the signature must have a corresponding variable definition in one of the unit-body-exprs, modulo the optional rename clause. If the rename clause is present, it maps internal-variables defined in the unit-body-exprs to signature-variables in the export signature.

The import-elements specify imports for the signed unit. The names bound within the signed-unit-body-exprs to imported bindings are constructed by flattening the signatures according to the algorithm in section 52.2:

52.4  Linking with Signatures

The compound-unit/sig form links signed units into a signed compound unit in the same way that the compound-unit form links primitive units. In the compound-unit/sig form, signatures are used for importing just as in unit/sig (except that all import signatures must have a tag), but the use of signatures for linking and exporting is more complex.

Within a compound-unit/sig expression, each unit to be linked is represented by a tag. Each tag is followed by a signature and an expression. A tag's expression evaluates (at link-time) to a signed unit for linking. The export signature of this unit must satisfy the tag's signature. ``Satisfy'' does not mean ``match exactly''; satisfaction requires that the unit exports at least the variables specified in the tag's signature, but the unit may actually export additional variables. Those additional variables are ignored for linking and are effectively hidden by the compound unit.

To specify the compound unit's linkage, an entire unit is provided (via its tag) for each import of each linked unit. The number of units provided by a linkage must match the number of signatures imported by the linked unit, and the tag signature for each provided unit must match (exactly) the corresponding imported signature.

The following example shows the linking of an arithmetic unit, a calculus unit, a graphics unit, and a gravity modeling unit:

(define-signature arithmetic^ (add subtract multiply divide power))
(define-signature calculus^ (integrate))
(define-signature graphics^ (add-pixel remove-pixel))
(define-signature gravity^ (go))
(define arithmetic@ (unit/sig arithmetic^ (import) ...))
(define calculus@ (unit/sig calculus^ (import arithmetic^) ...))
(define graphics@ (unit/sig graphics^ (import) ...))
(define gravity@ (unit/sig gravity^ (import arithmetic^ calculus^ graphics^) ...))
(define model@
    (link (ARITHMETIC : arithmetic^ (arithmetic@))
          (CALCULUS : calculus^ (calculus@ ARITHMETIC))
          (GRAPHICS : graphics^ (graphics@))
          (GRAVITY : gravity^ (gravity@ ARITHMETIC CALCULUS GRAPHICS)))
    (export (var (GRAVITY go)))))

In the compound-unit/sig expression for model@, all link-time signature checks succeed since, for example, arithmetic@ does indeed implement arithmetic^ and gravity@ does indeed import units with the arithmetic^, calculus^, and graphics^ signatures.

The export signature of a signed compound unit is implicitly specified by the export clause. In the above example, the model@ compound unit exports a go variable, so its export signature is the same as gravity^. More forms for exporting are described in section 52.6.

52.5  Restricting Signatures

As explained in section 52.4, the signature checking for a linkage requires that a provided signature exactly matches the corresponding import signature. At first glance, this requirement appears to be overly strict; it might seem that the provided signature need only satisfy the imported signature. The reason for requiring an exact match at linkages is that a compound-unit/sig expression is expanded into a compound-unit expression. Thus, the number and order of the variables used for linking must be fully known at compile time.

The exact-match requirement does not pose any obstacle as long as a unit is linked into only one other unit. In this case, the signature specified with the unit's tag can be contrived to match the importing signature. However, a single unit may need to be linked into different units, each of which may use different importing signatures. In this case, the tag's signature must be ``bigger'' than both of the uses, and a restricting signature is explicitly provided at each linkage. The tag must satisfy every restricting signature (this is a syntactic check), and each restricting signature must exactly match the importing signature (this is a run-time check).

In the example from section 52.4, both calculus@ and gravity@ import numerical procedures, so both import the arithmetic^ signature. However, calculus@ does not actually need the power procedure to implement integrate; therefore, calculus@ could be as effectively implemented in the following way:

(define-signature simple-arithmetic^ (add subtract multiply divide))
(define calculus@ (unit/sig calculus^ (import simple-arithmetic^) ...))

Now, the old compound-unit/sig expression for model@ no longer works. Although the old expression is still syntactically correct, link-time signature checking will discover that calculus@ expects an import matching the signature simple-arithmetic^ but it was provided a linkage with the signature arithmetic^. On the other hand, changing the signature associated with ARITHMETIC to simple-arithmetic^ would cause a link-time error for the linkage to gravity@, since it imports the arithmetic^ signature.

The solution is to restrict the signature of ARITHMETIC in the linkage for CALCULUS:

(define model@
    (link (ARITHMETIC : arithmetic^ (arithmetic@))
          (CALCULUS : calculus^ (calculus@ (ARITHMETIC : simple-arithmetic^)))
          (GRAPHICS : graphics^ (graphics@))
          (GRAVITY : gravity^ (gravity@ ARITHMETIC CALCULUS GRAPHICS)))
    (export (var (GRAVITY go)))))

A syntactic check will ensure that arithmetic^ satisfies simple-arithmetic^ (i.e., arithmetic^ contains at least the variables of simple-arithmetic^). Now, all link-time signature checks will succeed, as well.

52.6  Embedded Units

Signed compound units can re-export variables from linked units in the same way that core compound units can re-export variables. The difference in this case is that the collection of variables that are re-exported determines an export signature for the compound unit. Using certain export forms, such as the open form instead of the var form (see section 52.7), makes it easier to export a number of variables at once, but these are simply shorthand notations.

Signed compound units can also export entire units as well as variables. Such an exported unit is an embedded unit of the compound unit. Extending the example from section 52.5, the entire gravity@ unit can be exported from model@ using the unit export form:

(define model@
    (link (ARITHMETIC : arithmetic^ (arithmetic@))
          (CALCULUS : calculus^ (calculus@ (ARITHMETIC : simple-arithmetic^)))
          (GRAPHICS : graphics^ (graphics@))
          (GRAVITY : gravity^ (gravity@ ARITHMETIC CALCULUS GRAPHICS)))
    (export (unit GRAVITY))))

The export signature of model@ no longer matches gravity^. When a compound unit exports an embedded unit, the export signature of the compound unit has a sub-signature that corresponds to the full export signature of the embedded unit. The following signature, model^, is the export signature for the revised model@:

(define-signature model^ ((unit GRAVITY : gravity^)))

The signature model^ matches the (implicit) export signature of model@ since it contains a sub-signature named GRAVITY -- matching the tag used to export the gravity@ unit -- that matches the export signature of gravity@.

The export form (unit GRAVITY) does not export any variable other than gravity@'s go, but the ``unitness'' of gravity@ is intact. The embedded GRAVITY unit is now available for linking when model@ is linked to other units.


(define tester@ (unit/sig () (import gravity^) (go 0)))
(define test-program@
     (link (MODEL : model^ (model@))
           (TESTER : () (tester@ (MODEL GRAVITY))))

The embedded GRAVITY unit is linked as an import into the tester@ unit by using the path (MODEL GRAVITY).

52.7  Signed Compound Units

The compound-unit/sig form links multiple signed units into a new signed compound unit:

  (import (tag : signature) ···) 
  (link (tag : signature (expr linkage ···)) ···) 
  (export export-element ···)) 

linkage is

unit-path is one of
  (simple-unit-path : signature) 

simple-unit-path is one of
  (tag identifier ···) 

export-element is one of
  (var (simple-unit-path variable)) 
  (var (simple-unit-path variable) external-variable) 
  (open unit-path) 
  (unit unit-path) 
  (unit unit-path variable)

tag is

The import clause is similar to the import clause of a unit/sig expression, except that all imported signatures must be given a tag identifier.

The link clause of a compound-unit/sig expression is different from the link clause of a compound-unit expression in two important aspects:

The export clause determines which variables in the sub-units are re-exported and implicitly determines the export signature of the new compound unit. A signed compound unit can export both individual variables and entire signed units. When an entire signed unit is exported, it becomes an embedded unit of the resulting compound unit.

There are five different forms for specifying exports:

The collection of names exported by a compound unit must form a legal signature. This means that all exported names must be distinct.

Run-time checks insure that all link clause exprs evaluate to a signed unit, and that all linkages match according to the specified signatures:

52.8  Invoking Signed Units

Signed units are invoked using the invoke-unit/sig form:

  (invoke-unit/sig expr invoke-linkage ···)

invoke-linkage is one of
  (identifier : signature)

If the invoked unit requires no imports, the invoke-unit/sig form is used in the same way as invoke-unit. Otherwise, the invoke-linkage signatures must match the import signatures of the signed unit to be invoked. If the signatures match, then variables in the environment of the invoke-unit/sig expression are used for immediate linking; the variables used for linking are the ones with names corresponding to the flattened signatures. The signature flattening algorithm is specified in section 52.2; when the (identifier : signature) form is used, identifier: is prefixed onto each variable name in the flattened signature and the prefixed name is used.

(define-values/invoke-unit/sig signature unit/sig-expr [prefix invoke-linkage ···])      SYNTAX

This form is the signed-unit version of define-values/invoke-unit. The names defined by the expansion of define-values/invoke-unit/sig are determined by flattening the signature specified before unit-expr, then adding the prefix (if any). See section 52.2 for more information about signature flattening.

Each invoke-linkage is either signature or (identifier : signature), as in invoke-unit/sig.

(namespace-variable-bind/invoke-unit/sig signature unit/sig-expr [prefix invoke-linkage ···])      SYNTAX

This form is the signed-unit version of namespace-variable-bind/invoke-unit. See also define-values/invoke-unit/sig.

(provide-signature-elements signature)      SYNTAX

Exports from a module every name in the flattened form of signature.

52.9  Extracting a Primitive Unit from a Signed Unit

The procedure unit/sig->unit extracts and returns the primitive unit from a signed unit.

The names exported by the primitive unit correspond to the flattened export signature of the signed unit; see section 52.2 for the flattening algorithm.

The number of import variables for the primitive unit matches the total number of variables in the flattened forms of the signed unit's import signatures. The order of import variables is as follows:

52.10  Adding a Signature to Primitive Units

The unit->unit/sig syntactic form wraps a primitive unit with import and export signatures:

(unit->unit/sig expr (signature ···) signature)

The last signature is used for the export signature and the other signatures specify the import signatures. If expr does not evaluate to a unit or the unit does not match the signature, no error is reported until the primitive linker discovers the problem.

52.11  Expanding Signed Unit Expressions

The unit/sig, compound-unit/sig, and invoke-unit/sig forms expand into expressions using the unit, compound-unit, and invoke-unit forms, respectively.

A signed unit value is represented by a signed-unit structure with the following fields:

To perform the signature checking needed by compound-unit/sig, MzScheme provides two procedures:

(signature->symbols name)      SYNTAX

Expands to the ``exploded'' version (see section 52.11) of the signature bound to name (where name is an unevaluated identifier).

13 Of course, a signature can be specified as an immediate signature.

14 Element names are compared using the printed form of the name. This is different from any other syntactic form, where variable names are compared as symbols. This distinction is relevant only when source code is generated within Scheme rather than read from a text source.