Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: A Fully Abstract Semantics for a Functional Language with Logic Variables
Authors: Pingali, Keshav
Panangaden, Prakash
Jagadeesan, Radhakrishnan
Keywords: computer science
technical report
Issue Date: Feb-1989
Publisher: Cornell University
Abstract: We present a novel denotational semantics for a functional language with logic variables intended for parallel execution. The intuition behind this semantics is that equations represent equational constraints on data. Thus, a system of equations can be viewed as defining a set of possibly inconsistent constraints. The semantics is couched in terms of closure operators on a Scott domain. This allows one to abstract away from all the complexities associated with operational reasoning expressed in terms of concurrent threads of execution. We define a structural operational semantics for the language that expresses precisely the concurrent execution model that we have in mind. We show that the abstract denotational semantics is fully abstract with respect to the operational semantics. This is surprising, given how very different the two semantic descriptions are. It also shows that thinking in terms of constraints is an accurate substitute for thinking in terms of explicit parallel execution. The proof of full abstraction is complicated by the fact that there are potentially infinite objects in the domain.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
89-969.pdf3.93 MBAdobe PDFView/Open
89-969.ps748.79 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us