Abstract
An operational semantics for logic programming languages with external
functions (procedures) is presented. The external procedures stand
for arbitrary functions, implemented in any programming language.
In addition to ordinary constructor terms, a program written in a
functional logic language includes special functional terms that
represent calls to external functions. The central dynamic requirement
is that external functions can be called only with ground constructor
terms as arguments. Methods are presented for statically analyzing
the groundness of functional terms, and for arranging the corresponding
external function calls into a proper execution order. The methods
are based on techniques developed for attribute grammars. Consequently,
execution of a functional logic program is divided into two phases:
first an incomplete skeleton of a proof tree is constructed in conjunction
with a modified SLD-resolution scheme, and then the skeleton is completed
into a proof tree by traversing its labels and executing the associated
function calls. The analysis guarantees that whenever a term is subject
to functional evaluation, all its arguments are ground. The completing
traversal phase can consist of multiple passes over the skeleton.
The execution scheme is generated from an annotated version of the
program, based on dividing the arguments of predicates into inherited
and synthesized ones and on analyzing the data dependencies between
them in the spirit of attribute grammars. Algorithms are given for
automatically inferring a proper (partial) annotation. Several special
program classes are defined. One-pass programs, such as L-annotated
and one-sweep programs, can be executed during the modified SLD-resolution
phase without building and traversing an explicit skeleton. This
is not possible for general multi-pass programs, such as absolutely
non-circular programs, that always require an explicit skeleton to
be constructed due to complex mutual data dependencies between different
atoms of the program.Finally, implementation and optimization methods
in terms of the operatio- nal semantics are discussed
Users
Please
log in to take part in the discussion (add own reviews or comments).