1 Introduction
This document is a work in progress, and is currently stronger on structure, thanks to the LAML tool which was used to generate it, than it is on content. Feel free to send comments, critiques, and suggestions to Anton van Straaten.
| Abstract. An executable implementation of the denotational semantics for the Scheme language, as defined in R5RS. The core of this implementation consists of a faithful translation of the R5RS denotational semantics into the Scheme language. A denotational semantics (DS) definition of a language can be used for a variety of purposes, including analysis, verification, compilation, and interpretation. This implementation provides a Scheme interpreter which has been built around the core DS definitions. Other applications of this DS implementation are also possible. |
| 1 Introduction This document is a work in progress, and is currently stronger on structure, thanks to the LAML tool which was used to generate it, than it is on content. Feel free to send comments, critiques, and suggestions to Anton van Straaten. |
| 1.1 Copyright 1.2 Overview 1.3 Getting Started 1.4 Motivation 1.5 What is Denotational Semantics? 1.6 References 1.7 Naming Conventions |
| 1.1 Copyright |
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1, published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and with no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License" (5.3).
The associated program code is released under the terms of the GNU General Public License, version 2, as published by the Free Software Foundation. A copy of this license is included in the section entitled "GNU General Public License" (5.4).
 1.2 Overview |
This program provides an executable implementation of the denotational semantics for the Scheme language, as defined in R5RS.
The program is written in R5RS Scheme. It has been tested on a variety of Schemes - see the section on Compatibility (5.1).
If you're unfamiliar with denotational semantics, this document may not be the best place to begin learning about the subject, since it is heavily focused on the executable implementation of a particular semantics, rather than the many broader issues which the topic encompasses. However, for a brief summary, see the section "What is Denotational Semantics?" (1.5).
The actual code translated from R5RS can be found in the two modules semantic-functions.scm (4.1) and auxiliary-functions.scm (4.2).
The implementation has been tested in various ways. One useful test was to convert the Scheme code back to a traditional denotational form, and compare the result to the original R5RS DS. This conversion was achieved using Christian Queinnec's excellent L2T tool. The results of the conversion can be seen in this PDF.
On their own, the semantic functions are not usable in executable form - they need various supporting procedures in order to run. In order to exercise them fully, a small Scheme interpreter was developed. This interpreter operates by passing expressions to a top-level dispatch procedure, expression-meaning-toplevel. The dispatch function invokes the appropriate DS procedures, resulting in a function representing the denoted meaning of an expression. The resulting meaning function is then evaluated with an appropriate environment and store, thus evaluating the original expression.
The interpreter is implemented in pure mutation-free functional style, with the exception of the global environment, which relies on mutation. Implementing a traditional global environment without mutation would be difficult without modifications to the core DS, to allow a global environment to be threaded through the computation. For more information on the operation of the interpreter, see section (2.1).
Denotational semantics, being mathematical in intent, leaves many things of relevance to an implementation unspecified. To produce an executable version, implementations of the various operations and domains must be provided. This program provides only the most minimal and simplistic mutation-free implementations of these operations. Partly as a result of this, performance for any serious tasks is unimpressive. In addition, no garbage collection is performed, so over time, performance will deteriorate. However, for typical uses of the interpreter, performance is not a significant concern.
| 1.3 Getting Started |
If you can't wait for the incomparable religious experience of interacting directly with the actual denotational semantics of the official R5RS Scheme language, all you need to know is right here.
It's very easy to get the DS interpreter up and running in any reasonably standard Scheme.
The source code for the R5RS DS and an accompanying interpreter can be downloaded from this link.
Unzip it into a new directory, change to that directory, run your favorite Scheme interpreter, and type:
(load "repl.scm")
You should get a double angle prompt, >> which indicates that the interpreter's REPL is running successfully. You can now type Scheme expressions and, if they're supported by the interpreter, they should be evaluated and the result should be displayed.
No configuration should be required. See the Compatibility section (5.1) for information about Scheme implementations known to work.
Be aware that the interpreter has a very small library, and is by no means complete. It is intended to provide a way of interacting with the executable denotational semantics, not to be a complete implementation of Scheme.
The current state of the interpreter is described beginning in Section 2, Interpreter Overview.
Error handling is currently imperfect, and many kinds of errors will dump you unceremoniously into the host Scheme. To restart the interpreter in this case, type:
(repl)
Note that all definitions from the previous session will have been lost.
The interpreter supports a procedure for examining the current store function, i.e. the interpreter's "memory". To dump the store, type:
(dump-store)
For information about the format and meaning of the store, see Section 4.12, Store Inspector.
The interpreter supports the load procedure for loading Scheme source files. Two sample source files are provided: factorial.scm and tak.scm. Here's a transcript of their use:
Note that after running tak with the above parameters, the interpreter's store has been enlarged to the point where performance is noticeably reduced. Exiting and restarting the interpreter using (repl) is suggested.>> (load "factorial.scm") Value: #t >> (factorial 12) Value: 479001600 >> (load "tak.scm") Value: #t >> (tak 12 8 4) ; takes a while Value: 5 >> (exit) ; exits to host Scheme or shell prompt
If you have any questions, feel free to email me.
| 1.4 Motivation |
I developed this program primarily out of interest and curiosity, as a learning exercise, as well as to explore and understand the possibilities presented by the practical application of denotational semantics and related techniques.
The impetus to actually begin the work arose out of an email discussion with Bill Richter, which was a spinoff from earlier discussions on comp.lang.scheme. These were long and often contentious discussions, which I'll summarize by quoting something I wrote in an email to Bill: "If nothing else, we've provoked each other into thinking!"
I hope that others might find this program useful or educational, and perhaps enhance it, extend it, and apply it in other ways. I'm interested in hearing from anyone who does anything along these lines.
Of particular interest to me is the general notion of abstracting the definition of the semantics of a language to a higher level, in order to provide leverage in the creation of tools to understand and manipulate code in a given language. Traditional interpreters and compilers tend to be primarily concerned with reaching an efficiently executable format as quickly as possible. However, as programming tools become more sophisticated, more and more operations are being performed on source code that do not lead directly to traditionally compiled or evaluated code, that are instead used to process code in other ways.
A prominent current example of this can be seen in the automatic refactoring of code, as supported for example by popular Java development environments such as Eclipse and IDEA. I believe that this sort of semi-automated processing and management of code is in its infancy, and that systems that have a better "understanding" of source code are likely to become much more common in future. (In a sense, this would be a continuation of the trend of mainstream languages eventually adopting features from LISP...)
Denotational semantics provides a well-defined mechanism for assigning meaning to code in a way that lends itself to automated processing. Even if denotational semantics itself is not the ideal vehicle for such work, the principles involved in developing applications in this area are more broadly applicable.
More generally, the interpreter provided here is a small example of interpretation by translation of source code into a minimal lambda-based language, supporting only six primary primitive operations: procedure application, evaluation of constants, variables, lambda, if, and set!. The behavior of these primitive operations is implemented by the core DS code.
At the time of development, I could not find any other publicly available implementations of the R5RS DS. This kind of work has certainly been done before - Will Clinger has mentioned on comp.lang.scheme that Jonathan Rees did such a translation as part of the development of R3RS, and that:
"Since then, several people have back-translated the denotational semantics into Scheme, usually to test some proposed change to the language or to aid in a mechanical proof of some property of Scheme or an implementation of Scheme. For example, the semantics of multiple values in R5RS was tested that way."
However, none of these translations seems to be publicly available, although my checking of this was limited primarily to searching the WWW and Usenet. At a seminar, I did ask Dr. Clinger about the code he had mentioned, but he told me that he no longer had it, and that he would have made it available otherwise.
Code of this kind has the potential to form the basis of some useful tools, both educational and practical. The actual realization of this potential seems to be another matter, however. Some examples exist of papers which describe the potential for use in practical tools. With specific reference to Scheme, two such papers are:
| 1.5 What is Denotational Semantics? |
"Denotational semantics is a formal method for defining the semantics of programming languages. It is of interest to the language designer, compiler writer and programmer. These individuals have different criteria for judging such a method - it should be concise, unambiguous, open to mathematical analysis, mechanically checkable, executable and readable depending on your point of view."
These web pages are not intended as an introduction to denotational semantics, but the following attempts to briefly place the denotational definitions in R5RS into some context, explaining a bit about denotational semantics at the same time.
It is common to define the syntax of programming languages using a grammar such as BNF (Backus Naur Form). Defining the syntax of a language using a formal meta-language such as BNF provides many benefits, for example: it communicates the syntax concisely to others; and it can be mechanically processed into programs capable of parsing the specified syntax, by the use of parser generators such as YACC.
Syntax descriptions only partly define a language, however. Generally, the semantics of a language are far more complex than the syntax, and correspondingly more important. Denotational semantics provides a formal method for assigning exact meanings to statements in a programming language, thus unambiguously specifying the semantics of a language. This is in contrast to typical natural language specifications, which may suffer from ambiguities and incompleteness.
A denotational definition of a language consists of a number of valuation functions, each of which corresponds to a particular type of language expression. Each such function maps an input expression, in the source language, to a "mathematical object" which represents the denotation, or "meaning", of that expression.
R5RS defines thirteen such semantic functions, in Section 7.2.3. These 13 functions provide denotations for the core expressions of the Scheme language, such as procedure definition and application, and variable reference and assignment.
The denotations are represented as functions written in a variation of the lambda calculus developed for the purpose. For an overview of how denotational semantics relates to lambda calculus, see this page by Lloyd Allison.
Having the denotations are written in a language which has a well-defined formal basis provides numerous benefits relating to the ability to formally analyze and manipulate expressions in a language, with the additional benefit that mechanical processing is well-supported.
From the implementation perspective, because of its lambda calculus roots, the language used for denotational definitions is quite similar to a subset of Scheme. This is not because the language is being used to define Scheme - the same denotational language is used to define the semantics of other non-Scheme-like languages, such as Pascal and Prolog.
The code documented here demonstrates the similarity between the denotational definitions and Scheme itself - for the most part, the denotational definitions have been translated, token for token, into Scheme. The close connection is further demonstrated by having successfully mechanically translated the Scheme code back into a denotational representation.
The Scheme version of the denotational semantics provides a metacircular definition of Scheme: Scheme defined in Scheme itself. This can actually be a sensible way to define a language, as noted by Henry Baker in Metacircular Semantics for Common Lisp Special Forms:
"...while a system of denotational semantics á la Scheme or ML could be developed for Common Lisp, we believe that a carefully fashioned system of metacircular definitions can achieve most of the precision of denotational semantics. Furthermore, a metacircular definition is also more readable and understandable by the average Common Lisp programmer, since it is written in terms he mostly understands."
The associated code demonstrates Baker's assertion quite convincingly, by concretely illustrating the close connection between a denotational definition of a language and a metacircular definition, at least in the case of Scheme.
The above description of denotational semantics is no doubt rather inadequate. For further information, there are some additional links in this Wikipedia entry. Additional references can be found in the following References section.
| 1.6 References |
The references which I found most directly helpful during this development were:
 1.7 Naming Conventions |
In the implementations of the R5RS semantic and auxiliary functions, the traditional DS greek characters have been mapped to Scheme identifiers as follows:
| Letter | Name | Identifier | DS Domain |
|---|---|---|---|
| α | alpha | a | Locations (mnemonic: 'a' is for Address) |
| σ | sigma | s | Stores |
| ρ | rho | r | Environments |
| κ | kappa | k | Expression continuations |
| θ | theta | theta | Command continuations |
| ν | nu | n | Natural numbers |
| ψ | psi | psi | Functions: (E | L* -> C) |
| ζ | zeta | z | Functions: (E -> K -> C) |
The naming conventions for the semantic functions themselves, curly-E, curly- C, and curly-K, are described in 4.1 Semantic Functions.
The naming conventions for the auxiliary functions from R5RS Section 7.2.4 are described in 4.2 Auxiliary Functions.
The prefix ds: is used throughout the system, a little too much in fact. In general, anything with a ds: prefix is a function defined in or required by the R5RS DS. There may be exceptions, and the prefix is used for many different kinds of functions. Better naming conventions will be instituted in a future version.
| 2 Interpreter Overview This section provides an overview of the provided interpreter, its design and limitations. |
| 2.1 Operation of the Interpreter 2.2 Supported Syntax 2.3 Interpreter Library 2.4 Datatypes 2.5 Store Function Implementation |
| 2.1 Operation of the Interpreter |
The interpreter's repl procedure invokes the core evaluator with a bootstrap expression, bootstrap-source. The bootstrap expression defines a small REPL, a load procedure, and loads a prelude file (4.13). It then commences the REPL loop.
Running the REPL within the interpreter itself serves as a good test of the interpreter. However, it has a downside in that the activity of the REPL is then visible in the DS store, so if one is interested in examining the use of the store as a result of a particular operation, the REPL may get in the way. Earlier versions of the interpreter used a more direct evaluation technique, invoking eval-expression directly with a continuation that supported display of the results. This approach may soon be resurrected as an optional capability.
The core evaluator operates by passing expressions to a top-level dispatch procedure, expression-meaning-toplevel. For derived expressions, where syntax transformation is needed, a simple source-level syntax transformation is performed, transforming the input s-exp to an output s-exp. The result is an expression containing only the primitive syntax understood by the DS: constants, variable references, lambda, if, set, and procedure application.
The transformation of derived expressions is hardcoded, and is not done via macros, since that was considered beyond the scope of this implementation. Use of a fully-fledged macro system to transform derived expressions would be likely to obscure the operation of the core DS.
Once a primitive expression is obtained, the dispatch procedures determine which DS procedure needs to be invoked, and invokes the appropriate procedure. The DS procedure executes, returning a procedure representing the denoted meaning of an expression. Note that in the current implementation, this meaning procedure is returned as an instantiated Scheme procedure, not as an s-exp. This means that operations such as lambda-calculus-style reductions cannot be performed on it, although that might be an interesting future project (essentially, a compiler).
The meaning procedure is then evaluated with an appropriate environment and store, thus evaluating the original expression. The results are then displayed by the REPL. Having the REPL implemented within the interpreter somewhat simplifies the display of results, since the interpreter's own display procedure can be used.
The interpreter is implemented in pure functional style, with the exception of the global environment, which relies on mutation. Implementing a traditional global environment without mutation would be difficult without modifications to the core DS, to allow a global environment function to be threaded through the computation.
If desired, it is possible to configure the interpreter to evaluate expressions without a global environment. Early incarnations of the interpreter did just that. In this mode, the interpreter implementation would be mutation- free. Some as yet undocumented code adjustments are required to do this, however.
| 2.2 Supported Syntax |
The provided Scheme interpreter supports the Scheme syntax specified in R5RS, with some exceptions. Macros are not supported. The following syntax is not currently supported:
| and | or | case | cond |
| do | delay | let* | quasiquote |
Most of the above would be trivial to implement, and was not done simply because it wasn't needed during development or testing.
Macro support could be added as a layer above the core interpreter, but this would simply translate code into macro-free Scheme, which would subsequently by processed via the DS functions. This would be unlikely to be of any particular interest, and would in any case be likely to obscure operation at the DS level.
The implementation of letrec currently does not conform strictly to R5RS, in that it does not strictly enforce the restriction related to referencing letrec variable values during evaluation of the initialization expressions.
| 2.3 Interpreter Library |
The interpreter's library is limited to a short list of core Scheme procedures, including all of the functions defined in the R5RS DS itself. The currently supported procedures are listed below:
| apply | boolean? | call/cc | call-with-values |
| car | cdr | cons | caar |
| cadr | cdar | cddr | char? |
| close-input-port | current-input-port | display? | eof-object? |
| eqv? | eq? | eval | interaction-environment |
| list | newline | not | negative? |
| null? | number? | open-input-file | pair? |
| port? | positive? | procedure? | read |
| set-car! | set-cdr! | string? | symbol? |
| values | write | zero? | |
| + | - | * | = |
| < | > |
Note that the operators +, -, *, =, <, > as implemented here all require exactly two operands, in contrast to the specification in R5RS section 6.2.5, Numerical Operations. This should be corrected. The two-operand restriction derives from the R5RS DS definitions of the auxiliary functions add and less, which are defined to take only two operators, presumably either to avoid needlessly complicating the semantics, or for historical reasons.
| 2.4 Datatypes |
The numeric tower is supported to some extent, largely due to snarfing of data types from the host Scheme. However, library support for numeric types is minimal, as can be seen in the list of library procedures mentioned above.
The port data type is partially supported but is not recognized by the equivalence predicates.
The vector datatype is mostly unsupported. Although it is possible to enter literal vectors, courtesy of the host Scheme, entire vectors are stored in individual DS locations as though they were scalar values. Proper support for vectors would require conversion of vector literals into the store, similar to what is done for pairs via expression-meaning-quote. It would also require a denotational-style implementation of procedures such as make-vector.
| 2.5 Store Function Implementation |
The DS domain of locations is implemented as integers. If a store function is called with an integer that represents an unallocated location, an (E x T) sequence is returned containing (*unspecified* #f), where the second value, #f, indicates that the location is unallocated.
For a location that is allocated, this second element will be #t. Simple scalar values, such as an integer, would thus be represented in the store as e.g. (42 #t).
Pairs are represented, per the DS, as pairs of locations plus a mutable flag, (L x L x T). This means that an expression evaluated in the interpreter such as (cons 'a 'b) results in location mappings in the store looking something like this:
435: (a #t) 436: (b #t) 437: ((435 436 #t) #t)The above is an excerpt from the output of the dump-store procedure, and indicates the following:
| 3 Module Overview This section provides an overview of the modular structure of the system. The term 'module' is used loosely below - the system consists of a set of Scheme source files containing global procedures. This section describes the overall organization and relationships between these files, and provides links to the entry describing each individual file. |
| 3.1 Core DS implementation 3.2 Syntactic Transformation and Semantic Dispatch 3.3 Implementation Specifics 3.4 Interpreter 3.5 Support Functions |
| 3.1 Core DS implementation |
| 3.2 Syntactic Transformation and Semantic Dispatch |
These procedures are responsible for: transforming a Scheme expression into the form supported by the semantic functions; choosing which semantic function should be used to provide a meaning for the resulting expression; invoking the appropriate semantic function; and returning the result.
The main interface for this operation is expression-meaning-toplevel, which evaluates Scheme expressions with top-level semantics, i.e. top-level define statements and top-level begin statements.
All other expressions are passed through to expression-meaning for transformation in a non-toplevel context.
In a sense, these procedures can be seen as an extension of the core DS, since their purpose is ultimately to produce a denotation function by invoking the appropriate semantic function. Accordingly, specific implementation considerations have been avoided as much as possible, to allow these procedures to support multiple purposes. However, in practice, serious applications would benefit from a more sophisticated syntactic expansion mechanism.
| 3.3 Implementation Specifics |
| 3.4 Interpreter |
| 3.5 Support Functions |
| 4 Source Files Each of the system's individual source files is described below. Each heading below corresponds to one of the source files listed in the upper right frame. |
| 4.1 Semantic Functions |
This file implements the semantic functions defined in R5RS Section 7.2.3.
Curly-E is the semantic function that assigns meaning to expressions. There is a Curly-E definition for each type of expression, e.g. one for variable references, one for procedure calls, one for assignment, etc. In this implementation, the curly-E procedures names are prefixed by expression-meaning-, followed by an indication of the type of expression they correspond to, e.g. identifier, assignment, application, etc.Similarly, Curly-C is the semantic function which assigns meaning to commands. The names of these functions are prefixed by command-meaning-.
In order to select the appropriate meaning function to determine the meaning of a given Scheme expression, dispatch procedures are required. These dispatch procedures are an implementation requirement, that are not specified by the DS. The module which defines this is described in Section 3.2. The top level dispatch procedure is expression-meaning-toplevel.
Certain expression types have specific dispatch functions. These expression types are lambda expressions, expression sequences, command sequences, and if expressions. These expression-type-specific dispatch procedures are listed in the table below, above the functions which they dispatch to.
This table thus acts as an index to all the semantic functions and related dispatch functions, found in this file as well as in semantic-dispatch (4.6) and toplevel-dispatch (4.5).
| Semantic Function | Denotes meaning of... |
|---|---|
| expression-meaning-toplevel | Dispatcher for top-level expressions, to handle top-level begin and define. All other expressions are passed down to expression-meaning. |
| expression-meaning | Dispatcher for most Scheme expressions. Invokes dispatcher or meaning function appropriate to expression being evaluated. Called recursively during evaluation, first from expression-meaning-toplevel and subsequently from within the core DS procedures. |
| constant-meaning | A constant. This is Curly-K, specified but not defined by the DS. |
| expression-meaning-quote | A quoted expression. |
| expression-meaning-constant | A constant expression. ε[[K]] = λρκ . send (κ[[K]]) κ |
| expression-meaning-identifier | A variable reference, i.e. an identifier expression. |
| expression-meaning-application | A procedure call expression |
| expression-meaning-abstraction | Dispatcher for lambda expressions |
|
expression-meaning-abstraction-fixed-arity expression-meaning-abstraction-variable-arity expression-meaning-abstraction-list-arity | A lambda expression, of the following forms, respectively:
(lambda (I...) ...) |
| expression-meaning-if | Dispatcher for conditional expression |
|
expression-meaning-if-then-else expression-meaning-if-then | Conditional expression |
| expression-meaning-assignment | Assignment expression |
| expression-sequence-meaning | Dispatcher for expression sequence |
|
expression-meaning-null expression-meaning-sequence | Expression sequence |
| command-sequence-meaning | Dispatcher for command sequence |
|
command-meaning-null command-meaning-sequence | Command sequence |
| 4.2 Auxiliary Functions |
This module contains the auxiliary functions defined in R5RS Section 7.2.4.
| ds:lookup | U -> Ide -> L | Lookup identifier in environment |
| ds:extends | U -> Ide* -> L* -> U | Extends environment with identifier/location bindings |
| ds:wrong | X -> C | Signal an error |
| ds:send | E -> K -> C | Send an expressed value to an expression continuation |
| ds:single | (E -> C) -> K | Enforce a single return value from the provided function |
| ds:new | S -> (L + error) | Return an unallocated location from a store. See also ds:update. |
| ds:hold | L -> K -> C | |
| ds:assign | L -> E -> C -> C | Assign an expressed value to a location |
| ds:update | L -> E -> S -> S | Generate new store from existing store, updating specified location with expressed value. |
| ds:tievals | (L* -> C) -> E* -> C | |
| ds:tievalsrest | (L* -> C) -> E* -> N -> C | |
| ds:dropfirst | Drop first n elements of a sequence | |
| ds:takefirst | Take first n elements of a sequence | |
| ds:truish | E -> T | Return true if argument not false |
| ds:permute | Exp* -> Exp* | Permute a sequence of expressions (implementation dependent) |
| ds:unpermute | E* -> E* | Unpermute a sequence of expressed values (inverse of permute) |
| ds:applicate | E -> E* -> K -> C | Apply argument sequence to procedure |
| ds:onearg | (E -> K -> C) -> (E* -> K -> C) | |
| ds:twoarg | (E -> E -> K -> C) -> (E* -> K -> C) | |
| ds:list | ||
| ds:cons | ||
| ds:less | ||
| ds:add | ||
| ds:car | ||
| ds:cdr | | |
| ds:setcar | ||
| ds:eqv | ||
| ds:apply | ||
| ds:valueslist | ||
| ds:cwcc | ||
| ds:values | ||
| ds:cwv | E* -> K -> C | call-with-values - Note this implementation fixes a typo in the R5RS DS, in which the final kappa was omitted. |
Note that the current naming convention for sequence handling may be confusing, since there are procedures like command-meaning-sequence and command-sequence-meaning. The curly-letter functions defined in the DS are prefixed as defined in the text above the table, e.g. command-meaning- and expression-meaning-. However, the dispatch procedures for sequences are named command-sequence-meaning and expression-sequence-meaning. There's actually some logic to the difference, but it's also confusing enough that it should probably be changed to something like command-sequence-dispatch. Originally, they were named as meaning procedures because they are called from within the core DS functions.
| 4.3 Domain Implementations |
This module provides a minimal implementation for the domains and operations specified by the DS - stores, locations, pairs, etc. These procedures are required to implement an executable DS, but are not defined by the R5RS DS. They can be replaced by other implementations.
An attempt has been made to allow for a reduced dependency on native Scheme datatypes, by providing type-specific interfaces to allow implementations to be done in terms of values other than pairs, lists, etc. However, in this module currently, these interfaces have been implemented as native Scheme datatypes. Substituting a different implementation for e.g. locations may expose some cases where the appropriate interface was not used. (A type annotation capability might have been useful...)
The procedures in this module are listed in the following table, organized by the domain, type, or operation which they implement.
| Domain, Type, or Operation | Procedure |
|---|---|
| E - Expressed values | ds:inject-value |
| Sequences | ds:append |
| ds:first | |
| ds:length | |
| ds:rest | |
| ds:second | |
| ds:sequence | |
| ds:third | |
| ds:sequence? | |
| M - Miscellaneous values | ds:false |
| ds:true | |
| ds:undefined | |
| ds:unspecified | |
| ds:misc? | |
| ds:project-misc | |
| L - Locations | ds:location? |
| ds:location-eq? | |
| ds:project-location | |
| F - Procedure values | ds:project-procedure |
| ds:procedure? | |
| R - Numbers | ds:number? |
| ds:project-number | |
| Ep - Pairs | ds:pair? |
| ds:project-pair | |
| Q - Symbols | ds:symbol? |
| ds:project-symbol | |
| Es - Strings | ds:string? |
| ds:project-string | |
| H - Characters | ds:char? |
| ds:project-char | |
| S - stores | ds:new-impl |
| ds:expand-store | |
| ds:initial-store | |
| Substitution operation - f[v/s] | ds:substitute |
| ds:substitute-location |
| 4.4 Library Procedures |
dss:eval
ds:setcdr
dss:greater
dss:numequals
dss:subtract
dss:multiply
dss:read
dss:display
display-value
dss:write
write-value
dss:open-input-file
dss:current-input-port
dss:close-input-port
dss:eof-object?
dss:newline
dss:procedure?
dss:pair?
dss:number?
dss:symbol?
dss:string?
dss:char?
dss:boolean?
dss:port?
| 4.5 Top Level Semantic Dispatch |
expression-meaning-toplevel
meaning-toplevel-command-sequence
toplevel-command-meaning-sequence
| 4.6 Semantic Dispatch |
expression-meaning
constant-meaning
expression-meaning-quote
ds:immutable-cons
expression-sequence-meaning
command-sequence-meaning
expression-meaning-if
expression-meaning-abstraction
| 4.7 Derived Expressions |
expression-meaning-begin
convert-let-variables
expression-meaning-let
expression-meaning-named-let
transform-letrec
expression-meaning-letrec
transform-internal-definitions
| 4.8 Global Environment |
dss:interaction-environment
base-environment
global-environment
initialize-global-context
global-environment-lookup
dse:initial-environment-global
expression-meaning-toplevel-definition
expression-meaning-procedure-definition
define-vars
extend-global-environment!
define-global-var
dse:initial-environment
dse:global-definer
| 4.9 Syntax Transformation Support |
split-list-at-end
malformed-expression
expression-guard
expression-guard-min
| 4.10 Interpreter REPL |
eval-expression
repl
failure-continuation-value
current-failure-continuation
ds:wrong
ds:wrong-wrong
bootstrap-source
| 4.11 Value Conversion |
ds:value->host-value
ds:pair->host-pair
ds:location-value->host-value
ds:host-value->value
| 4.12 Store Inspector |
There is also a procedure store-size, available from within the interpreter (mapped to dsi:store-size), which returns the size of the current store, i.e. the number of location/value mappings it contains.
For a description of the format of the store, see Store Implementation (2.5).
Some simple enhancements to the store inspector would improve its usability. Another useful procedure that would help the inspection capability would be a procedure which returns the location mapped to a particular identifier. TODO.
dump-store
dsi:dump-store
dsi:store-size
| 4.13 Interpreter Prelude |
not
null?
negative?
positive?
zero?
caar
cadr
cdar
cddr
call/cc
chatty-repl
| 5 Appendices |
| 5.1 Compatibility 5.2 Shortcomings 5.3 GNU Free Documentation License 5.4 GNU General Public License 5.5 The Last Word |
| 5.1 Compatibility |
This implementation is written in standard Scheme, compatible with R5RS and probably also R4RS. It has been tested and runs successfully under the following Scheme implementations, without requiring configuration or modification (in alphabetical order):
Implementations not in the above list have not been tested, but any reasonably standards-compliant implementation should work fine.
All tests were run in the host Scheme's interpreter. No pure compilers were tested.
| 5.2 Shortcomings |
Listed below are some of the more serious current shortcomings.
| 5.3 GNU Free Documentation License |
Version 1.1, March 2000
Copyright (C) 2000 Free Software Foundation, Inc. 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.
0. PREAMBLE
The purpose of this License is to make a manual, textbook, or other written document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others.
This License is a kind of "copyleft", which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software.
We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference.
1. APPLICABILITY AND DEFINITIONS
This License applies to any manual or other work that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. The "Document", below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as "you".
A "Modified Version" of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language.
A "Secondary Section" is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (For example, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them.
The "Invariant Sections" are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License.
The "Cover Texts" are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License.
A "Transparent" copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, whose contents can be viewed and edited directly and straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup has been designed to thwart or discourage subs