Functional-logic integration via minimal reciprocal extensions

AbstractRELFUN reciprocally extends Horn RELations and call-by-value FUNctions just enough to yield a unified operator concept. Relations acquire application nesting and higher-order notation; functions acquire non-groundness and non-determinism. Relations are defined by Horn-like clauses implicitly returning true; functions are defined by rules with an additional returned-value premise. This minimal relational-functional kernel permits common extensions without duplicate features in logic and functional languages. Procedural and model-theoretic semantics are developed for kernel RELFUN, transferring the Herbrand models of (Horn-clause) relational programming to (first-order) functional programming. The compiler system reuses the register X1 of the Warren Abstract Machine for value returning, statically flattening general nestings while optimizing first-argument nestings. Applications include a (hyper)graph library, a CAD-to-NC transformer, and sharable knowledge bases