schemeds


SchemeDS

SchemeDS is an executable implementation of the formal semantics of Scheme, as defined by R5RS.

What does that mean? R5RS Chapter 7 defines the semantics of the core elements of the Scheme language, using denotational semantics, a formal method for defining the semantics of programming languages.

Denotational semantics tends to be quite impenetrable to the casual reader. It relies on a mathematical syntax heavy in greek characters. However, in many respects, it is simpler than it looks. The language used to express denotational semantics is a variation of the lambda calculus, and it can be expressed quite directly in Scheme itself. A definition in denotational semantics can be treated as a program — as though it were a reference implementation of the language it defines.

SchemeDS exploits this by expressing Scheme's denotational semantics in Scheme itself, and building a simple interpreter around this definition. The formal mathematical semantics which appear in R5RS Chapter 7 have been translated into Scheme code, in two files: Semantic functions and Auxiliary functions.

The above files represent a very direct translation, or transliteration, of the R5RS semantics into Scheme, so much so that it is possible to generate a copy of the formal semantics from this Scheme code.

To make this code do something useful, a minimal Scheme interpreter has been built around it. This interpreter should run under any R5RS Scheme. For more details, see the SchemeDS page, and in particular, the hypertext explanation of the code.


category-software