We have developed a prototype implementation (approx. 2000 lines of code) of a partial deduction system for Prolog programs which follows the offline approach. Basically, we apply a quasi-termination analysis (based on size-change graphs) and, then, annotate the source program so that potential loops are avoided by generalizing dangerous arguments of selected atoms at partial evaluation time.
We have also developed a prototype tool, PEPE for predicting the effectiveness of partial evaluation. It reuses several techniques from offline partial evaluation (size-change analysis, BTA) but introduces a new trace analysis for easing the interpretation of the results.
More information can be found here
Narrowing extends rewriting with logic capabilities by allowing logic variables in terms and replacing matching with unification. Narrowing has been widely used in different contexts, ranging from theorem proving (e.g., protocol verification) to language design (e.g., it forms the basis of so called functional logic languages).
We have developed a new tool, TNT, that can be used to analyze the termination of narrowing computations (and, thus, the termination of functional logic programs). This tool accepts left-linear constructor systems, a widely accepted class of systems in functional and functional logic programming, and returns a transformed system such that it it terminates w.r.t. rewriting, the the original system terminates w.r.t. narrowing.
More information can be found in this paper.
We have developed several partial evaluation systems. Firstly, we developed the
for functional logic programs. It is implemented in Prolog and considers an
abstract syntax based on simple rewrite rules. It follows the
narrowing-driven approach to partial evaluation as presented in
We have also developed an online partial evaluator for the multi-paradigm language Curry (indeed, this is the first purely declarative partial evaluator for functional logic programs). The partial evaluator is written in Curry itself and considers arbitrary Curry programs (including higher-order, several built-in functions, concurrent constraints, etc). This partial evaluation tool has been integrated into the PAKCS compiler for Curry. The partial evaluator follows the ideas presented in [AHV00, AHV01, AHV02].
Recently, we have implemented an offline version of the previous partial evaluator. The new system, together with a description of several benchmarks, is available here. A more technical description appears in [RSV05].
We have developed an automatic technique for the partial inversion of first-order functions. Here, "partial" means that not all input parameters become output parameters after inversion, but some of the inputs may remain as such. This is useful in some cases because the original function needs not be injective in order to produce a confluent inverse function.
In order to asses the effectiveness of the partial evaluation process, we have developed a source-level abstract profiler for Curry programs. It is "abstract" in the sense that it measures the number of basic operations performed during a computation rather than actual execution times (e.g., the number of function unfoldings, pattern matchings, or applications). A complete description of the profiler can be found in [AV01].
Following a similar purpose, we have developed a cost-augmented partial evaluator. It is available here. This system is an extended version of the partial evaluator for the multi-paradigm language Curry. The original narrowing-driven partial evaluator is enhanced with the computation of abstract costs (similarly to the profiler above). In order to ease the analysis of the results, we also incorporate a simple speedup analysis which allows us to determine the improvement achieved by the specialization process. The original ideas about measuring the effectiveness of partial evaluation can be found in [AAV00]. The formalization of the cost-augmented partial evaluator for programs in the flat representation is here: [Vid02, Vid04].
By exploting the similarities between (forward) slicing and (online) partial evaluation, we developed a forward slicing tool for the multi-paradigm language Curry. The (forward) slicing tool has been implemented by adapting an existing partial evaluator for Curry programs. It required a small implementation effort, i.e., only the underlying meta-interpreter needed significant changes.