Detection of single-threading properties in combinator notations

Thumbnail Image
Date
1991
Authors
Lass, Dean
Major Professor
Advisor
David A. Schmidt
Donald Pigozzi
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
Abstract

The detection of a property called "single-threading" in functional programs or denotational language definitions can be exploited to produce a more efficient implementation of the program or language, by allowing a program variable or semantic domain to be implemented by a global data structure. Earlier work by David A. Schmidt has given sufficient criteria for the detection of the single-threading property in [lambda]-calculus expressions. We extend that work by giving criteria for single-threading detection in combinator notations;Two sets of single-threading criteria are given: one for a particular combinator language, TML, and the other for a generalized combinator notation. In both cases, proofs are given which demonstrate the soundness of the criteria. We also discuss some reasons for the differences in the two sets of criteria;In order to evaluate the usefulness of single-threading detection and the associated globalization transformation in practice, a testbed implementation of the TML criteria is being programmed, using the PSI/DAOS compiler-generation system developed at Aalborg University. Some preliminary results from this work are discussed.

Comments
Description
Keywords
Citation
Source
Subject Categories
Copyright
Tue Jan 01 00:00:00 UTC 1991