A fully abstract semantics for concurrent graph reduction
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper presents a fully abstract semantics for a variant of the untyped /spl lambda/-calculus with recursive [Bdeclarations. We first present a summary of existing work on full abstraction for the untyped /spl lambda/-calculus, concentrating on S. Abramsky (1989) and C.H.L. Ong (1988) work on the lazy /spl lambda/-calculus. Abramsky and Ong's work is based on leftmost outermost reduction without sharing. This is notably inefficient, and many implementations model share by reducing syntax graphs rather than syntax trees. Here we present a concurrent graph reduction algorithm for the /spl lambda/-calculus with recursive declarations, in a style similar to G. Berry and G. Boudol's chemical abstract machine. We adapt Abramsky and Ong's techniques, and present a program logic and denotational semantics for the /spl lambda/-calculus with recursive declarations, and show that the three semantics are equivalent.Keywords
This publication has 12 references indexed in Scilit:
- A chemical abstract machine for graph reduction extended abstractPublished by Springer Nature ,1994
- A natural semantics for lazy evaluationPublished by Association for Computing Machinery (ACM) ,1993
- Report on the programming language HaskellACM SIGPLAN Notices, 1992
- An adequate operational semantics of sharing in lazy evaluationPublished by Springer Nature ,1992
- The chemical abstract machinePublished by Association for Computing Machinery (ACM) ,1990
- An algorithm for optimal lambda calculus reductionPublished by Association for Computing Machinery (ACM) ,1990
- A compiler for lazy MLPublished by Association for Computing Machinery (ACM) ,1984
- A filter lambda model and the completeness of type assignmentThe Journal of Symbolic Logic, 1983
- Fully abstract models of typed λ-calculiTheoretical Computer Science, 1977
- PAL---a language designed for teaching programming linguisticsPublished by Association for Computing Machinery (ACM) ,1968