Theses and Dissertations Collection

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.