Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. A Fully Abstract Semantics for a Functional Language with Logic Variables

A Fully Abstract Semantics for a Functional Language with Logic Variables

File(s)
89-969.ps (748.79 KB)
89-969.pdf (3.84 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6885
Collections
Computer Science Technical Reports
Author
Pingali, Keshav
Panangaden, Prakash
Jagadeesan, Radhakrishnan
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.

Date Issued
1989-02
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-969
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance