Detection of single-threading properties in combinator notations
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
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.