The semantics of Scheme control-flow analysis

Published 1 January 1991Open access

Olin Shivers

Citations75

TL;DR

The method of abstract semantic interpretations is used to explicate the control-flow analysis technique presented in "Control-How Analysis in Scheme", using a denotational semantics for CPS Scheme and presenting an alternate semantics that precisely expresses the control -flow analysis problem.

Abstract

Abstract: "This is a follow-up to my 1988 PLDI paper, 'Control-Flow Analysis in Scheme' [9]. I use the method of abstract semantic interpretations to explicate the control-flow analysis technique presented in that paper. I begin with a denotational semantics for CPS Scheme. I then present an alternate semantics that precisely expresses the control-flow analysis problem. I abstract this semantics in a natural way, arriving at two different semantic interpretations giving approximate solutions to the flow analysis problem, each computable at compile time.The development of the final abstract semantics provides a clear, formal description of the analysis technique presented in 'Control- Flow Analysis in Scheme.'"

Keywords

Computer Science

Abstract interpretation

6,131 Citations1977Patrick Cousot, Radhia Cousot

DSpace@MIT (Massachusetts Institute of Technology)Rabbit: A Compiler for Scheme

402 Citations1978Jr. Guy L. Steele

A compiler for the lexically-scoped dialect of LISP known as SCHEME, which handles only a small basis set which reflects the semantics of lambda-calculus, and serves to produce code as good as that produced by more traditional compilers.

View PDF

Modern healthcareControl-flow analysis of higher-order languages of taming lambda

343 Citations1991Olin Shivers

ACM SIGPLAN NoticesControl flow analysis in scheme

279 Citations1988Olin Shivers

ACM SIGPLAN NoticesOrbit

259 Citations2004David Kranz, Richard Kelsey +4 more

Orbit was an optimizing compiler for T, a dialect of Scheme, that directly spawned six PhD theses and one Masters thesis, and influenced many other projects as well, including SML of New Jersey.

Continuation-passing, closure-passing style

168 Citations1989Andrew W. Appel, Trevor Jim

This work implemented a continuation-passing style (CPS) code generator for ML that separates the code generation into phases that rewrite this representation of the language into ever-simpler forms.

View PDF

A semantic model of reference counting and its abstraction (detailed summary)

140 Citations1986Paul Hudak

Most interpreters for functional languages (as well as Lisp) employ at some level in the implementation a notion of sharing, whether manifested indirectly through an environment or directly via pointers, which is essential to an efficient implementation.

Science of Computer ProgrammingAutomatic autoprojection of higher order recursive equations

139 Citations1991Anders Bondorf

This paper describes an approach to treat a higher order subset of the Scheme language as an extension to the existing autoprojector Similix that treats a first order Scheme subset.

Replacing function parameters by global variables

119 Citations1989Peter Sestoft

Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Data-flow analysis and type recovery in Scheme

38 Citations2018Olin Shivers

This paper presents a technique for recovering type information from Scheme programs using flow analysis, which is semantically based, and is novel in that it correctly handles the "environment flow'* problem.

View PDF