A Tight, Practical Integration of Relations and Functions
Harold Boley, Stanford, CA, USA
Lecture Notes in Artificial Intelligence. VOL. 1712, 1999. XI + 169 pp.
Springer-Verlag. ISBN 3-540-66644-3
(http://www.springer.de/cgi-bin/search_book.pl?isbn=3-540-66644-3)
The issue of synthesizing the relational and functional paradigms has
long been a leading topic in declarative language design. Several
'relational-functional' or 'functional-logic' integrations have been
attempted via various conceptual, formal, and implementation bridges.
However, there remains the challenge of establishing an integrated
declarative language in main-stream programming practice. Thus, RELFUN
takes the approach of a synthesis based on the principle of minimal
cross-extension. The RELFUN kernel contains just those extensions to
relational and functional notions that are necessary for their tight
integration. These are logic variables plus non-determinism from
relations and nested plus higher-order operations from functions. It
is only this integrated kernel which is then uniformly enriched by a
shell of features such as finite domains and exclusions, types/sorts,
and built-ins. The 'kernel+shell' approach has made RELFUN a suitable
language for teaching and practicing declarative programming.
HOW RELFUN INTEGRATES RELATIONS AND FUNCTIONS
This separate text illustrates RELFUN's kernel notions in an easy way
(http://smi-web.stanford.edu/people/boley/integrelfun.txt).
FROM THE PREFACE
Part of the unique attraction of computer science stems from the fact
that most of its notions permit a multitude of simultaneous
perspectives, connecting form and content, theory and practice, etc.
Thus, the study of programming involves syntax, semantics, and
pragmatics: Syntactically, a program can be specified by grammar
formalisms on several levels. Semantically, a program can be
characterized as a static entity such as a mathematical model and by
dynamic computations such as derivation traces. Pragmatically, a
program can be run by an interpreter, in an abstract machine, and as
native code of a real computer. In order to obtain insights into new
programming paradigms one can start off from either of these ends or
from somewhere in the middle. The texts treats most of these
perspectives for the RELFUN integration, whose development started at
the practical ends, later tailored theoretical ones for them, and now
is proceeding in both directions: In chapter 2.6. the PROLOG-like user
syntax is specified by an EBNF grammar. In chapter 3 the semantics is
founded equivalently on Herbrand models and on SLD-resolution. In
chapter 5 the pragmatics is implemented via the Warren Abstract
Machine. For further summaries we refer to the reader's guide at the
end of the overview chapter 1 and to the synopses at the beginning of
all five chapters.
Here we summarize our contributions to the theory and practice of
tight relational-functional integration:
* The relational notions of non-ground terms and (don't-know)
non-determinism were integrated with the functional notions of
application values and higher-order functions into a minimal kernel
system (chapter 1).
* This was extended by `first-class' finite domains and exclusions
(chapter 4), sort hierarchies, `single-cut' determinism specification
(chapter 2), etc.
* Encapsulated partial (non-ground) data structures were transferred
to the functional paradigm even for computations with ground I/O
(chapter 2).
* The semantics of first-order functions was founded on the same
model-theoretic level as that of relations (chapter 3).
* Relational-functional transformers, compilers, and abstract machines
were developed in LISP (chapter 5).
* Using these, application studies were conducted about declarative
programming in engineering domains (chapter 1).
* The reusability of concepts, techniques, and source programs was shown
with the languages COLAB (BMBF project ARC-TEC) and DRL (BMBF project
VEGA).
C O N T E N T S
*{ }Preface{V}
*{1}An Overview of the Relational-Functional Language RELFUN}{1}
-{1.1}Declarative Merger via Minimal Extensions}{1}
-{1.2}From Relations and Functions to Operators}{5}
-{1.3}PROLOG-LISP-RELFUN Comparison}{8}
-{1.4}Semantics and Implementation}{11}
-{1.5}Applications}{14}
-{1.6}Related Work}{16}
-{1.7}Reader's Guide}{19}
*{2}Extended Logic-plus-Functional Programming}{21}
-{2.1}Introduction}{21}
-{2.2}Relations Defined by Hornish Clauses}{23}
-{2.2.1}Open-world DATALOG}{23}
-{2.2.2}PROLOG-like Structures and Lists}{25}
-{2.2.3}Varying-arity Structures}{26}
-{2.2.4}Varying-arity Relationships}{28}
-{2.2.5}Higher-order Constructors and Relations}{29}
-{2.3}Functions Defined by Footed Clauses}{31}
-{2.3.1}DATAFUN as a Functional Database Language}{31}
-{2.3.1.1}Molecular Rules and Non-ground Functions}{31}
-{2.3.1.2}Footed Rules and the {\tt density} Example}{33}
-{2.3.1.3}Non-determinism, DATALOG Relationalizing, and WAM Compilation}{35}
-{2.3.2}Full RELFUN Exemplified by ``Self''-Functions}{36}
-{2.3.3}Higher-order Constructors and Functions}{39}
-{2.4}The Logic/Functional Style in Use}{42}
-{2.4.1}{\tt serialise}: Inplace Specialization of Structures}{42}
-{2.4.2}{\tt wang}: On-the-fly Construction of Proof Trees}{45}
-{2.4.3}{\tt eval}: Interpreting a LISP Subset in RELFUN}{48}
-{2.5}Conclusions}{50}
-{2.6}Appendix: The RELFUN Syntax}{52}
*{3}A Direct Semantic Characterization of RELFUN}{55}
-{3.1}Introduction}{55}
-{3.2}Extending First-order Theories to First-order Relational-Functional{} Theories}{61}
-{3.3}Relational-Functional{} Interpretations and Models}{65}
-{3.4}SLV{}-Resolution}{72}
-{3.5}Soundness of SLV{}-Resolution}{78}
-{3.6}Least Herbrand Crossbase Models as Fixpoints}{80}
-{3.7}Completeness of SLV{}-Resolution}{85}
-{3.8}Conclusions}{87}
*{4}Finite Domains and Exclusions as First-class Citizens}{89}
-{4.1}Introduction}{89}
-{4.2}Domain Terms}{91}
-{4.3}Exclusion Terms}{93}
-{4.4}Occurrence Bindings}{95}
-{4.5}Domains/Exclusions in Relation Definitions}{97}
-{4.5.1}Facts and {\tt dom}/{\tt exc} Reductions}{97}
-{4.5.2}Clauses and {\tt bnd}-to-``{\tt .=}'' Reductions}{99}
-{4.6}Finite-Domain/Exclusion Functional Programming}{101}
-{4.6.1}Domains/Exclusions as Function Arguments}{102}
-{4.6.2}Functions with Domain/Exclusion Values}{103}
-{4.7}Domain and Exclusion Anti-unification}{105}
-{4.8}Operational Semantics}{109}
-{4.9}Conclusions}{111}
-{4.10}Appendix: The RELFUN Meta-{\tt unify}}{114}
*{5}Multiple-valued Horn Clauses and Their WAM Compilation}{117}
-{5.1}Introduction}{117}
-{5.2}A Multiple-valued Relational/Functional Language}{120}
-{5.2.1}Amalgamating Relations and Functions}{120}
-{5.2.2}Single-valued and Multiple-valued Clauses}{123}
-{5.2.3}An Example: Refining the {\tt palindrome} Operator}{128}
-{5.2.4}Higher-order Functions and Relations}{134}
-{5.3}Relational/Functional WAM Compilation}{137}
-{5.3.1}A Compilation Strategy}{137}
-{5.3.2}Evaluative Foots and Denotative Normalization}{140}
-{5.3.3}Non-deterministic, Multiple-valued Nestings and Static Flattening}{143}
-{5.3.4}Higher-order Clauses and Constant-operator Reduction}{148}
-{5.3.5}Translation to WAM Instructions}{151}
-{5.4}Conclusions}{157}
*{ }{Bibliography}{161}
------------------------------------------------------------------------------
Note: This press release has been made URL-accessible as an HTML file
(http://smi-web.stanford.edu/people/boley/lnai1712.html).