# Scheme: A Interpreter for Extended Lambda Calculus

@article{Sussman1998SchemeAI, title={Scheme: A Interpreter for Extended Lambda Calculus}, author={Gerald J. Sussman and Guy L. Steele}, journal={Higher-Order and Symbolic Computation}, year={1998}, volume={11}, pages={405-439} }

Inspired by ACTORS [7, 17], we have implemented an interpreter for a LISP-like language, SCHEME, based on the lambda calculus [2], but extended for side effects, multiprocessing, and process synchronization. [...] Key Method In the fourth section we will give a general discussion of the issues facing an implementor of an interpreter for a language based on lambda calculus. Finally, we will present a completely annotated interpreter for SCHEME, written in MacLISP [13], to acquaint programmers with the tricks of… Expand

#### Topics from this paper

#### 218 Citations

Revised5 Report on the Algorithmic Language Scheme

- Computer Science
- High. Order Symb. Comput.
- 1998

The report gives a defining description of the programming language Scheme. Scheme is a statically scoped and properly tail-recursive dialect of the Lisp programming language invented by Guy Lewis… Expand

Revised6 Report on the Algorithmic Language Scheme

- Computer Science
- Journal of Functional Programming
- 2009

Scheme demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language that is flexible enough to support most of the major programming paradigms in use today. Expand

An operational semantics for Scheme 1

- 2007

This paper presents an operational semantics for the core of Scheme. Our specification improves over the denotational semantics from the Revised5 Report on Scheme specification in four ways. First,… Expand

An operational semantics for Scheme

- Computer Science
- J. Funct. Program.
- 2008

This paper presents an operational semantics for the core of Scheme, and contributes three novel modeling techniques for Felleisen Hieb-style rewriting semantics, suggesting that they would scale to complete models of other languages. Expand

Lazy evaluation and delimited control

- Computer Science
- POPL '09
- 2009

The call-by-need lambda calculus provides an equational framework for reasoning syntactically about lazy evaluation. This paper examines its operational characteristics.
By a series of reasoning… Expand

Non-Deterministic Symbolic Analysis using Free Monads for Test Data Generation

- Computer Science
- 2019

This work will be investigating how to improve constraint logic programming using the free monad and how to use this in order to perform a breadth-first search, rather than depth-first. Expand

Types and programming languages

- Computer Science
- 2002

This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages, with a variety of approaches to modeling the features of object-oriented languages. Expand

Revised Report on the Kernel Programming Language

- Computer Science
- 2005

Kernel is a statically scoped and properly tail-recursive dialect of Lisp, descended from Scheme, designed to be simpler and more general than Scheme, with an exceptionally clear, simple, and versatile semantics. Expand

PRISM revisited: Declarative implementation of a probabilistic programming language using multi-prompt delimited control

- Mathematics, Computer Science
- Int. J. Approx. Reason.
- 2018

An approach based on delimited control operators recently introduced into SWI Prolog is described, used to create a system of nested effect handlers which together implement a core functionality of PRISM—the building of explanation graphs—entirely in Prolog and using an order of magnitude less code. Expand

Extending Jason with Promises for Concurrent Computation

- Computer Science
- IDC
- 2012

This paper proposes an extension to Jason that makes concurrent programming easier with the aid of promises, and presents a non-intrusive extension that enables this style of programming and motivate its usefulness. Expand

#### References

SHOWING 1-10 OF 34 REFERENCES

Lambda calculus schemata

- Mathematics, Computer Science
- LISP Symb. Comput.
- 1993

A lambda calculus schema is an expression of the lambda calculus augmented by uninterpreted constant and function symbols and thus is an abstraction of programming languages such as LISP which permit… Expand

Definitional interpreters for higher-order programming languages

- Computer Science
- ACM '72
- 1972

The definition of a simple applicative programming language by means of an interpreter written in a similar language is considered, and the treatment of imperative features such as jumps and assignment is discussed. Expand

LISP 1.5 Programmer's Manual

- Computer Science
- 1962

The LISP language is designed primarily for symbolic data processing used for symbolic calculations in differential and integral calculus, electrical circuit theory, mathematical logic, game playing,… Expand

Semantics of communicating parallel processes

- Computer Science
- 1975

The thesis of this dissertation is that an understanding of the ordering constraints that are introduced among events of parallel process is essential to the understanding of synchronization and that… Expand

A model and stack implementation of multiple environments

- Computer Science
- CACM
- 1973

This paper presents an implementation technique using a single stack to hold procedure activation storage which allows retention of that storage for durations not necessarily tied to control flow, and applications to multitasking, coroutines, backtracking, label-valued variables, and functional arguments are discussed. Expand

The function of FUNCTION in LISP or why the FUNARG problem should be called the environment problem

- Computer Science
- SIGS
- 1970

A problem common to many powerful programming languages arises when one has to determine what values to assign to free variables in functions and the argument is tried to couch the argument in ALGOL-like terms as much as possible. Expand

Actor semantics of PLANNER-73

- Computer Science
- POPL '75
- 1975

Its value in describing programs with side-effects, parallelism, and synchronization is discussed and the implications of actor semantics for the controversy over elimination of side- effects are discussed. Expand

Thunks: a way of compiling procedure statements with some comments on procedure declarations

- Computer Science
- CACM
- 1961

This paper presents a technique for the implementation of procedure statements of ALGOL 60 with some comments on the Implementation of procedure declarations and indicates that this solution is one acceptable solution to a problem soluble in many ways. Expand

The calculi of lambda-conversion

- Physics
- 1941

The description for this book, The Calculi of Lambda Conversion. (AM-6), will be forthcoming.

Solution of a problem in concurrent programming control

- Computer Science
- CACM
- 1965

A number of mainly independent sequential-cyclic processes with restricted means of communication with each other can be made in such a way that at any moment one and only one of them is engaged in… Expand