schemeDS.html

An Executable Denotational Semantics for Scheme
Anton van Straaten ©    anton@appsolutions.com    AppSolutions    

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.

 

  Interpreter Overview 
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
 

Introduction  Overview
1.1  Copyright
These web pages (referred to below as "this document") and the associated program code are copyright (c) 2002 by Anton van Straaten.

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).  

 

Introduction Copyright Getting Started
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.  

 

Introduction Overview Motivation
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:

    >> (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

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.

If you have any questions, feel free to email me.  

 

Introduction Getting Started What is Denotational Semantics?
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:

    The Scheme 311 Compiler - An Exercise in Denotational Semantics. William Clinger. Proceedings of the 1984 ACM Symposium on LISP and functional programming.
    Realistic Compilation by Program Transformation. Richard Kelsey, Paul Hudak. Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, 1989. 

For the final word on the subject, see section 5.5.  

 

Introduction Motivation References
1.5  What is Denotational Semantics?
Lloyd Allison provides the following summary in the opening paragraph of his book, "A Practical Introduction to 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.  

 

Introduction What is Denotational Semantics? Naming Conventions
1.6  References

The references which I found most directly helpful during this development were:

    R5RS - The Revised^5 Report on the Algorithmic Language Scheme. Richard Kelsey, William Clinger, and Jonathan Rees (editors).
    Lisp in Small Pieces. Christian Queinnec. Cambridge University Press, 1996. ISBN 0-521-56247-3. Contains a useful chapter on denotational semantics, including a number of examples of denotational definitions for a variety of Scheme-like languages.
    comp.lang.scheme - in particular, numerous messages by William D. Clinger and Matthias Blume.
    A Practical Introduction to Denotational Semantics. Lloyd Allison. (Cambridge Computer Science Texts #23), Cambridge University Press 1986. ISBN 0-521-31423-2. 

Tools

    LAML  Scheme Elucidator - used to produce these web pages.
    L2T literate programming utility - used to generate a denotational representation from the DS Scheme code, for comparison to the original R5RS DS. The end result is available in this PDF. 

 

 

Introduction References 
1.7  Naming Conventions
Variable names

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)
Procedure names

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.  

 

 Introduction Module Overview 
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
 

Interpreter Overview  Supported Syntax
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.  

 

Interpreter Overview Operation of the Interpreter Interpreter Library
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.  

 

Interpreter Overview Supported Syntax Datatypes
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.  

 

Interpreter Overview Interpreter Library Store Function Implementation
2.4  Datatypes
The basic Scheme data types are supported. Support for the numeric tower, ports, and vectors are subject to some caveats, below.

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.  

 

Interpreter Overview Datatypes 
2.5  Store Function Implementation
The Scheme semantics rely on store functions which map locations to values. These store functions thus serve the purpose of "memory" for the DS interpreter. In order to support inspection of the mappings represented by these store functions, a primitive Store Inspector has been provided (see also 4.12.)

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:

    location 435 is allocated and mapped to the value 'a
    location 436 is allocated and mapped to to the value 'b,
    location 437 is allocated (the final #t) and mapped to a mutable pair of locations, 435 and 436. Mutability is indicated by the first #t. In the case of pairs, this means that the set-car! and set-cdr! procedures are allowed to change the values mapped by the locations specified in the pair. 

 

 

 Interpreter Overview Source Files 
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
 

Module Overview  Syntactic Transformation and Semantic Dispatch
3.1  Core DS implementation
The following two files implement the Scheme denotational semantics as specified in R5RS sections 7.2.3 and 7.2.4.

    4.1 Semantic Functions from R5RS sec. 7.2.3
    4.2 Auxiliary Functions from R5RS sec. 7.2.4 

 

 

Module Overview Core DS implementation  Implementation Specifics
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.

    Top Level Dispatch - 4.5
    Semantic Dispatch - 4.6
    Derived Expressions - 4.7
    Supporting Procedures - 4.9

 

 

Module Overview Syntactic Transformation and Semantic Dispatch Interpreter
3.3  Implementation Specifics
These modules provide necessary implementation details not specified by the denotational semantics. These modules can be replaced with alternative implementations, without affecting the core DS modules.

    Domain Implementations - 4.3
    Value Conversion - 4.11
    Global Environment - 4.8

 

 

Module Overview Implementation Specifics Support Functions
3.4  Interpreter
These procedures implement the REPL of a Scheme interpreter, using the above modules to evaluate Scheme expressions. The Interpreter Prelude is loaded and evaluated by the DS interpreter itself, not by the host Scheme.

    Interpreter REPL - 4.10
    Interpreter Prelude - 4.13

 

 

Module Overview Interpreter 
3.5  Support Functions

    Library Procedures - 4.4 : provides wrappers for various host Scheme library procedures.
    Store Inspector - 4.12 : procedures for inspecting DS store functions.

 

 

 Module Overview Appendices 
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
4.2  Auxiliary Functions
4.3  Domain Implementations
4.4  Library Procedures
4.5  Top Level Semantic Dispatch
4.6  Semantic Dispatch
4.7  Derived Expressions
4.8  Global Environment
4.9  Syntax Transformation Support
4.10  Interpreter REPL
4.11  Value Conversion
4.12  Store Inspector
4.13  Interpreter Prelude
 

Source Files  Auxiliary Functions
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...) ...)
(lambda (I* . I) ...)
(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
 

 

Source Files Semantic Functions Domain Implementations
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 	
TODO.
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.  

 

Source Files Auxiliary Functions Library Procedures
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
 

 

Source Files Domain Implementations Top Level Semantic Dispatch
4.4  Library Procedures
This file contains a number of procedures to wrap library procedures from the host Scheme. The procedures listed below are not the entire library available to the interpreter - other library procedures are defined in various places. For a full list of library procedures, see Interpreter Library (2.3).

    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?

 

 

Source Files Library Procedures Semantic Dispatch
4.5  Top Level Semantic Dispatch
Implements the top level behavior of a Scheme interpreter, specifically support for the required top level behavior of define and begin. The interpreter's REPL invokes expression-meaning-toplevel as the primary interface to the denotational interpreter. All expressions other than define and begin are passed through to expression-meaning.

    expression-meaning-toplevel
    meaning-toplevel-command-sequence
    toplevel-command-meaning-sequence

 

 

Source Files Top Level Semantic Dispatch Derived Expressions
4.6  Semantic Dispatch
This file defines one of the main semantic dispatch procedures, expression-meaning, along with related dispatch procedures which it invokes. For a description of how this fits into the bigger picture, see Semantic Functions (4.1) and Syntax Transformation & Dispatch (3.2).

    expression-meaning
    constant-meaning
    expression-meaning-quote
    ds:immutable-cons
    expression-sequence-meaning
    command-sequence-meaning
    expression-meaning-if
    expression-meaning-abstraction

 

 

Source Files Semantic Dispatch Global Environment
4.7  Derived Expressions
These procedures implement source-level syntactic transformations of the derived expression types as defined in R5RS Section 4.2. They are invoked from the dispatch procedures in 4.6 and 4.5.

    expression-meaning-begin
    convert-let-variables
    expression-meaning-let
    expression-meaning-named-let
    transform-letrec
    expression-meaning-letrec
    transform-internal-definitions

 

 

Source Files Derived Expressions Syntax Transformation Support
4.8  Global Environment
Procedures to manage the global environment, including the procedures which handle definition of variables in the global environment, which are invoked from expression-meaning-toplevel.

    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

 

 

Source Files Global Environment Interpreter REPL
4.9  Syntax Transformation Support
Support procedures for the syntactic transformation procedures defined in 4.5, 4.6, and 4.7.

    split-list-at-end
    malformed-expression
    expression-guard
    expression-guard-min

 

 

Source Files Syntax Transformation Support Value Conversion
4.10  Interpreter REPL
Implements a simple REPL for the DS-based Scheme interpreter. For a description of the operation of the interpreter, see 2.1.

    eval-expression
    repl
    failure-continuation-value
    current-failure-continuation
    ds:wrong
    ds:wrong-wrong
    bootstrap-source

 

 

Source Files Interpreter REPL Store Inspector
4.11  Value Conversion
Procedures for converting values between the host Scheme and the DS interpreter's store.

    ds:value->host-value
    ds:pair->host-pair
    ds:location-value->host-value
    ds:host-value->value

 

 

Source Files Value Conversion Interpreter Prelude
4.12  Store Inspector
The dump-store procedure, executed from within the interpreter, provides a way to inspect the current DS store function. If called without parameters, it will dump the entire current store (400-odd locations when the interpreter is first loaded). Alternatively, a positive integer can be provided as a parameter to dump-store, and the store from that location on will be dumped.

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

 

 

Source Files Store Inspector 
4.13  Interpreter Prelude
This file is loaded by the DS interpreter on initialization. It is not executed by the host Scheme. For a description of the operation of the interpreter, see 2.1.

    not
    null?
    negative?
    positive?
    zero?
    caar
    cadr
    cdar
    cddr
    call/cc
    chatty-repl

 

 

 Source Files  
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
 

Appendices  Shortcomings
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):

    Chicken
    Guile [1]
    JScheme
    Kawa [2]
    MIT Scheme
    PLT Scheme (DrScheme and MzScheme, v103 & v202)
    Scheme 48
    SISC
    UMB Scheme 

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.
Notes:

    Guile exhibited a display anomaly in which the DS interpreter's REPL prompt did not display until after read had returned - perhaps due to line buffering, but this was not investigated. All other functionality worked correctly.
    By default, Kawa displays its own REPL prompt when read is used. One way to disable this is to start the DS program from the command line using the -f option, e.g. java kawa.repl -f repl.scm. 

 

 

Appendices Compatibility GNU Free Documentation License
5.2  Shortcomings
There are many things that could be done to improve this program as it currently stands. However, the need for many of them depends on what it is one wishes to do with the program. For example, if one were interested in using the DS for compilation purposes, then the limitations of the interpreter are irrelevant.

Listed below are some of the more serious current shortcomings.

    Procedure naming conventions - these developed (or not!) as the system "just growed". The ds: prefix is overused and doesn't have much specific meaning at this point.
    The simplistic implementation of the DS domains, particularly the way datatypes have been snarfed from the host Scheme. This allows leakage of capabilities from the host Scheme, such as the ability to insert vectors into the store, even though the implementation has no support for vectors. Another example is the occasional return of a "void" or "undefined" type from the host Scheme (as opposed to *undefined* and *unspecified* used by the DS interpreter).
    Error handling needs work - particularly syntax errors, and certain invocations of ds:wrong. The latter needs to be called in an appropriate context, since it is one of the DS support functions. Some of the calls to it in modules other than the core DS may not be correct, and can result in crashing the interpreter (although the original error is still reported, which is helpful).
    Store inspection capabilities, and other reflective capabilities, are very limited, but could be improved quite easily.
    Having the REPL running within the DS interpreter has advantages and disadvantages. The disadvantage is that if you are interested in examining the use of the store, it can become cluttered with bits of source expressions read in by the REPL. One way to correct this would be to enhance the ability to evaluate expressions from outside the REPL.
    The syntax and library supported by the interpreter could be improved quite easily, particularly by the use of snarfing macros (see comments in the source file associated with 4.4.) 

 

 

Appendices Shortcomings GNU General Public License
5.3  GNU Free Documentation License
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 subsequent modification by readers is not Transparent. A copy that is not "Transparent" is called "Opaque".

Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML designed for human modification. Opaque formats include PostScript, PDF, proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML produced by some word processors for output purposes only.

The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text.

2. VERBATIM COPYING

You may copy and distribute the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compensation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3.

You may also lend copies, under the same conditions stated above, and you may publicly display copies.

3. COPYING IN QUANTITY

If you publish printed copies of the Document numbering more than 100, and the Document's license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects.

If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages.

If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a publicly-accessible computer-network location containing a complete Transparent copy of the Document, free of added material, which the general network-using public has access to download anonymously at no charge using public-standard network protocols. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public.

It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document.

4. MODIFICATIONS

You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you release the Modified Version under precisely this License, with the Modified Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version:

    A. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous versions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission.
    B. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has less than five).
    C. State on the Title page the name of the publisher of the Modified Version, as the publisher.
    D. Preserve all the copyright notices of the Document.
    E. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices.
    F. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Addendum below.
    G. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Document's license notice.
    H. Include an unaltered copy of this License.
    I. Preserve the section entitled "History", and its title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section entitled "History" in the Document, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sentence.
    J. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for previous versions it was based on. These may be placed in the "History" section. You may omit a network location for a work that was published at least four years before the Document itself, or if the original publisher of the version it refers to gives permission.
    K. In any section entitled "Acknowledgements" or "Dedications", preserve the section's title, and preserve in the section all the substance and tone of each of the contributor acknowledgements and/or dedications given therein.
    L. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equivalent are not considered part of the section titles.
    M. Delete any section entitled "Endorsements". Such a section may not be included in the Modified Version.
    N. Do not retitle any existing section as "Endorsements" or to conflict in title with any Invariant Section. 

If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles.

You may add a section entitled "Endorsements", provided it contains nothing but endorsements of your Modified Version by various parties--for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard.

You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one.

The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version.

5. COMBINING DOCUMENTS

You may combine the Document with other documents released under this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invariant Sections of all of the original documents, unmodified, and list them all as Invariant Sections of your combined work in its license notice.

The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work.

In the combination, you must combine any sections entitled "History" in the various original documents, forming one section entitled "History"; likewise combine any sections entitled "Acknowledgements", and any sections entitled "Dedications". You must delete all sections entitled "Endorsements."

6. COLLECTIONS OF DOCUMENTS

You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects.

You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document.

7. AGGREGATION WITH INDEPENDENT WORKS

A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of a storage or distribution medium, does not as a whole count as a Modified Version of the Document, provided no compilation copyright is claimed for the compilation. Such a compilation is called an "aggregate", and this License does not apply to the other self-contained works thus compiled with the Document, on account of their being thus compiled, if they are not themselves derivative works of the Document.

If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one quarter of the entire aggregate, the Document's Cover Texts may be placed on covers that surround only the Document within the aggregate. Otherwise they must appear on covers around the whole aggregate.

8. TRANSLATION

Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License provided that you also include the original English version of this License. In case of a disagreement between the translation and the original English version of this License, the original English version will prevail.

9. TERMINATION

You may not copy, modify, sublicense, or distribute the Document except as expressly provided for under this License. Any other attempt to copy, modify, sublicense or distribute the Document is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.

10. FUTURE REVISIONS OF THIS LICENSE

The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. See http://www.gnu.org/copyleft/.

Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation.

 

 

Appendices GNU Free Documentation License The Last Word
5.4  GNU General Public License
Table of Contents

    GNU GENERAL PUBLIC LICENSE
        Preamble
        TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION 

GNU GENERAL PUBLIC LICENSE

Version 2, June 1991

Copyright (C) 1989, 1991 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.

Preamble

The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation's software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too.

When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things.

To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it.

For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights.

We protect your rights with two steps: (1) copyright the software, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the software.

Also, for each author's protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors' reputations.

Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary. To prevent this, we have made it clear that any patent must be licensed for everyone's free use or not licensed at all.

The precise terms and conditions for copying, distribution and modification follow.
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

0. This License applies to any program or other work which contains a notice placed by the copyright holder saying it may be distributed under the terms of this General Public License. The "Program", below, refers to any such program or work, and a "work based on the Program" means either the Program or any derivative work under copyright law: that is to say, a work containing the Program or a portion of it, either verbatim or with modifications and/or translated into another language. (Hereinafter, translation is included without limitation in the term "modification".) Each licensee is addressed as "you".

Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the Program is covered only if its contents constitute a work based on the Program (independent of having been made by running the Program). Whether that is true depends on what the Program does.

1. You may copy and distribute verbatim copies of the Program's source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and disclaimer of warranty; keep intact all the notices that refer to this License and to the absence of any warranty; and give any other recipients of the Program a copy of this License along with the Program.

You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee.

2. You may modify your copy or copies of the Program or any portion of it, thus forming a work based on the Program, and copy and distribute such modifications or work under the terms of Section 1 above, provided that you also meet all of these conditions:

    a) You must cause the modified files to carry prominent notices stating that you changed the files and the date of any change.

    b) You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License.

    c) If the modified program normally reads commands interactively when run, you must cause it, when started running for such interactive use in the most ordinary way, to print or display an announcement including an appropriate copyright notice and a notice that there is no warranty (or else, saying that you provide a warranty) and that users may redistribute the program under these conditions, and telling the user how to view a copy of this License. (Exception: if the Program itself is interactive but does not normally print such an announcement, your work based on the Program is not required to print an announcement.) 

These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Program, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it.

Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Program.

In addition, mere aggregation of another work not based on the Program with the Program (or with a work based on the Program) on a volume of a storage or distribution medium does not bring the other work under the scope of this License.

3. You may copy and distribute the Program (or a work based on it, under Section 2) in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following:

    a) Accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or,

    b) Accompany it with a written offer, valid for at least three years, to give any third party, for a charge no more than your cost of physically performing source distribution, a complete machine-readable copy of the corresponding source code, to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or,

    c) Accompany it with the information you received as to the offer to distribute corresponding source code. (This alternative is allowed only for noncommercial distribution and only if you received the program in object code or executable form with such an offer, in accord with Subsection b above.) 

The source code for a work means the preferred form of the work for making modifications to it. For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the executable. However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable.

If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code.

4. You may not copy, modify, sublicense, or distribute the Program except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense or distribute the Program is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.

5. You are not required to accept this License, since you have not signed it. However, nothing else grants you permission to modify or distribute the Program or its derivative works. These actions are prohibited by law if you do not accept this License. Therefore, by modifying or distributing the Program (or any work based on the Program), you indicate your acceptance of this License to do so, and all its terms and conditions for copying, distributing or modifying the Program or works based on it.

6. Each time you redistribute the Program (or any work based on the Program), the recipient automatically receives a license from the original licensor to copy, distribute or modify the Program subject to these terms and conditions. You may not impose any further restrictions on the recipients' exercise of the rights granted herein. You are not responsible for enforcing compliance by third parties to this License.

7. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program.

If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances.

It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose of protecting the integrity of the free software distribution system, which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice.

This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License.

8. If the distribution and/or use of the Program is restricted in certain countries either by patents or by copyrighted interfaces, the original copyright holder who places the Program under this License may add an explicit geographical distribution limitation excluding those countries, so that distribution is permitted only in or among countries not thus excluded. In such case, this License incorporates the limitation as if written in the body of this License.

9. The Free Software Foundation may publish revised and/or new versions of the General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns.

Each version is given a distinguishing version number. If the Program specifies a version number of this License which applies to it and "any later version", you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of this License, you may choose any version ever published by the Free Software Foundation.

10. If you wish to incorporate parts of the Program into other free programs whose distribution conditions are different, write to the author to ask for permission. For software which is copyrighted by the Free Software Foundation, write to the Free Software Foundation; we sometimes make exceptions for this. Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally.

NO WARRANTY

11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.

12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.

END OF TERMS AND CONDITIONS
 

 

Appendices GNU General Public License 
5.5  The Last Word

    "Denotational semantics is just a very peculiar language with poor syntax."

        -- Matthias Blume on comp.lang.scheme