Circular expressions: Elimination of static environments

Ravi Sethi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


Consider the connection between denotational semantics for a language with goto statements and flow diagrams for programs in such a language. The main point of interest is that the denotational semantics uses a recursively defined environment to give the meaning of labels, while a flow diagram merely has a jump to the appropriate program point. A simple reduction called “indirection elimination” strips away the environment from the denotational semantics and extracts an expression with cycles (circular expression) that is very close to the flow diagram of a program. The same idea applies to associating bodies with recursive procedures, or to any construct whose semantics is not wedded to the syntax. Circular expressions are offered as a useful data structure and conceptual device. Expressions with cycles are well defined mathematical objects — their semantics can be given by unfolding them into infinite structures that have been well studied. The practicality of the elimination of environments has been tested by constructing a trial implementation, which serves as the front end of a semantics directed compiler generator. The implementation takes a denotational semantics of a language and constructs a “black box” that maps programs in the language into an intermediate representation. The intermediate representation is a circular expression.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 8th Colloquium
EditorsShimon Even, Oded Kariv
Number of pages15
ISBN (Print)9783540108436
StatePublished - 1981
Event8th International Colloquium on Automata, Languages and Programming, ICALP 1981 - Acre, Israel
Duration: Jul 13 1981Jul 17 1981

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume115 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th International Colloquium on Automata, Languages and Programming, ICALP 1981

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Circular expressions: Elimination of static environments'. Together they form a unique fingerprint.

Cite this