@techreport{R-93-02,
TITLE = {Multi-Pass Evaluation of Functional Logic Programs},
AUTHOR = {Jukka Paakki},
YEAR = {1993},
NUMBER = {R-93-02},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-93-02+abstr},
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.},
IDANR = {LiTH-IDA-R-93-02},
NOTE = {Accepted for the 21st ACM Symposium on Principles of Programming Languages (POPL), January 1994, Portland, Oregon}