LOG(F): an optimal combination of logic programming, rewriting, and lazy evaluation

by Sanjai Narain

Purchase Print Copy

 FormatList Price Price
Add to Cart Paperback86 pages $30.00 $24.00 20% Web Discount

A new approach for combining logic programming, rewriting, and lazy evaluation is described. It rests upon subsuming within logic programming--rather than extending it with--rewriting, and lazy evaluation. A non-termination, non-deterministic rewrite rule system, F*, and a reduction strategy for it, select, are defined. F* is shown to be reduction-complete in that select simplifies terms whenever possible. A class of F* programs called Deterministic F* is defined and shown to satisfy confluence, directedness, and minimality. Confluence ensures that every term can be simplified in at most one way. Directedness eliminates searching in simplification of terms. Minimality ensures that select simplifies terms in a minimum number of steps. Completeness and minimality enable select to exhibit laziness. F* can be compiled in such a way that when SLD-resolution interprets these, it directly simulates the behavior of select. Thus, SLD-resolution is made to exhibit laziness. LOG(F) is defined to be a logic programming system augmented with an F* compiler.

This report is part of the RAND Corporation paper series. The paper was a product of the RAND Corporation from 1948 to 2003 that captured speeches, memorials, and derivative research, usually prepared on authors' own time and meant to be the scholarly or scientific contribution of individual authors to their professional fields. Papers were less formal than reports and did not require rigorous peer review.

The RAND Corporation is a nonprofit institution that helps improve policy and decisionmaking through research and analysis. RAND's publications do not necessarily reflect the opinions of its research clients and sponsors.