Embedding Goal-Directed Evaluation through Transformation


Mills, Peter Harper. (2016). Embedding Goal-Directed Evaluation through Transformation. Theses and Dissertations Collection, University of Idaho Library Digital Collections.

Embedding Goal-Directed Evaluation through Transformation
Mills, Peter Harper
Generators Icon Mixed-language Multi-paradigm Program transformation Unicon
Computer Science
Subject Category:
Computer science

Goal-directed evaluation is a computational paradigm that combines the power of generators with backtracking search. In goal-directed evaluation every expression is a generator that produces a sequence of values until it fails, and operations iterate over the cross-product of their operands to find successful results. Introduced in the influential dynamic language Icon and later refined in its object-oriented descendent Unicon, goal-directed evaluation is a powerful yet unconventional paradigm that can succinctly express search over a product space as well as aggregate operations amenable to parallelization. The goal of this research is to extend the benefits of this paradigm into other more familiar object-oriented languages through mixed-language embedding. However, grafting goal-directed evaluation onto other languages in a manner that provides seamless interoperability has remained an elusive challenge.

This dissertation presents a novel approach to embedding goal-directed evaluation into existing object-oriented languages based on program transformation. We first introduce annotations for mixed-language embedding that allow mixing in Unicon functionality at the level of expressions, methods, or classes. Transformations over the annotated regions then unravel the syntax of generator expressions to a conventional form by flattening nested generators and making iteration explicit, in order to enable native evaluation. The rewriting rules then translate control constructs and operations onto a stream-like calculus for composing suspendable iterators. The transformations provide a formal semantics for Unicon that enable embedding into a broad variety of object-oriented languages. To demonstrate the utility of the approach, we have implemented the transformations for Java as well as its dynamic analogue Groovy, and housed them in an interpretive harness that can function both interactively and as a translator for compilation.

We further extend the transformations to enable mixed-language embedding of concurrent generators. We present a simple model of explicit concurrency for generators based on co-expressions and multithreaded generator proxies. We demonstrate how the concurrency abstractions can express parallel pipelining, as well as build higher-order abstractions such as map-reduce. Mixed-language embedding allows the use of concurrent generators within a familiar object-oriented setting, both for high-level coordination and the prototyping and refinement of parallel programs for multi-core architectures.

doctoral, Ph.D., Computer Science -- University of Idaho - College of Graduate Studies, 2016
Major Professor:
Jeffery, Clinton
Alves-Foss, James; Donohoe, Gregory; Anderson, Michael
Defense Date:
Format Original:

Contact us about this record

In Copyright - Educational Use Permitted. For more information, please contact University of Idaho Library Special Collections and Archives Department at
Standardized Rights: