TY - GEN
T1 - Circular expressions
T2 - 8th International Colloquium on Automata, Languages and Programming, ICALP 1981
AU - Sethi, Ravi
N1 - Publisher Copyright:
© 1981, Springer-Verlag.
PY - 1981
Y1 - 1981
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84976730695&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84976730695&partnerID=8YFLogxK
U2 - 10.1007/3-540-10843-2_31
DO - 10.1007/3-540-10843-2_31
M3 - Conference contribution
AN - SCOPUS:84976730695
SN - 9783540108436
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 378
EP - 392
BT - Automata, Languages and Programming - 8th Colloquium
A2 - Even, Shimon
A2 - Kariv, Oded
PB - Springer-Verlag
Y2 - 13 July 1981 through 17 July 1981
ER -