A Relational/Functional Language and Its Compilation into the WAM

Abstract

The first part discusses an amalgamation of relations and functions on the basis of ‘valued clauses’, as used in RELFUN. These extend Horn clauses by ‘foot’ premises, specifying the values to be returned. Functions can succeed or fail, enumerate values non-deterministically, return multiple values, and have non-ground arguments and values. Relations act like characteristic functions, permit functionally nested call-by-value arguments, and are definable as higher-order operators. Higher-order clauses are characterized by a structure or a (free) variable in some operator position. The second part describes the WAM compilation of RELFUN. Multiple-valued functions are transformed to a ‘denotative’ form, eliminating foots that are active calls. Call-by-value nestings (possibly non-deterministic) are ‘flattened’. Higher-order clauses are reduced to ‘constant-operator’ clauses. Finally, WAM code is generated by extending the use of X-registers and ‘put’/‘get’ instructions: values are put into registers X1, ... just before a clause returns; from there, the caller can get them as arguments, as if loaded by top-level put instructions.