narain@randvax.UUCP (Sanjai Narain) (09/17/88)
=============================================================================
LOG(F) is a system for doing lazy, non-terminating, non-deterministic
rewriting within Prolog, without changing Prolog. Thus, full advantage is
taken of the very efficient implementations of Prolog available today.
Except in the last, optional, optimization phase, rewrite rules are
compiled into pure Prolog clauses. The theory of LOG(F) is described in
a report whose abstract appears below.
For problems for which lazy evaluation does not reduce lengths of
computation, LOG(F) is, on an average, five times slower than Prolog.
Otherwise, LOG(F) is faster than Prolog by unbounded, even infinite
amounts.
Logic programming, and lazy rewriting can be freely mixed in LOG(F). In
particular, infinite structures, such as streams, can be easily
manipulated. Thus, new possibilities emerge, within Prolog, for reasoning
about concurrent computation, implementing intelligent backtracking,
manipulating relational databases, doing arbitrary precision arithmetic,
parsing with functional grammars, or computing with the rule of
substitution of equals for equals.
The compiler for F*, the rewrite rule system underlying LOG(F), has been
developed in Quintus Prolog. However, it should run satisfactorily in
SB-Prolog, SICSTUS-Prolog, and C-Prolog. Both the compiler and the report
are available for experimental, academic, non-commercial use only, by
emailing a request to the author, or writing to:
Sanjai Narain
Rand Corporation
1700 Main Street
Santa Monica, CA 90406
USA
(213) 393 0411 (ext 6336)
The F* compiler will be emailed. Please be sure to include your physical
address especially if you request the report.
=============================================================================
LOG(F): An Optimal Combination of Logic Programming,
Rewriting, and Lazy Evaluation
ABSTRACT
A new approach for combining logic programming, rewriting, and lazy
evaluation is described. It rests upon subsuming within logic
programming, instead of upon extending it with, rewriting, and lazy
evaluation.
A non-terminating, 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, respectively, weak and strong forms
of laziness.
F* can be compiled into Horn clauses 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.
LOG(F) can be used to do lazy functional programming in logic, implement
useful cases of the rule of substitution of equals for equals, and obtain
a new proof of confluence for combinatory logic.
=============================================================================
PLEASE NOTE
=============================================================================
If you request, or use the F* compiler (hereinafter referred to as
"software"), it is assumed that you have read, and agree to the following
conditions:
The software will be provided without charge. The purpose of distributing
it is to obtain feedback regarding its design, and the theoretical issues
surrounding it. It may be used for academic, non-commercial purposes
only. It will be provided "as is", with no warranty of any kind, express
or implied, including, but not limited to, the implied warranties of
merchantability and fitness for a particular purpose. The entire risk as
to the quality and performance of the software is with you. Should this
software prove defective, you assume the cost of all necessary servicing,
repair, or correction. In no event, is RAND Corporation, or Sanjai
Narain, liable for any damages, direct, or consequential, arising out of
use of the software.