2014/12/10 by M. H. van Emden, van Emden, M. H.
Computer Science · #D.1.6 #F.3.2 #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Programming Languages (cs.PL) #Semantic Web and Ontologies #cs.LO #cs.PL
paper · pdf · doi:10.48550/arxiv.1412.3480
19 pages, 5 figures
openalex publication_date 2014/12/10 · arxiv created 2015/09/26 · arxiv updated 2015/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A logic program is an executable specification. For example, merge sort in pure Prolog is a logical formula, yet shows creditable performance on long linked lists. But such executable specifications are a compromise: the logic is distorted by algorithmic considerations, yet only indirectly executable via an abstract machine. This paper introduces relational programming, a method that solves the difficulty with logic programming by a separation of concerns. It requires three texts: (1) the axioms, a logical formula that specifies the problem and is not compromised by algorithmic considerations, (2) the theorem, a logical formula that expresses the idea of the algorithm and follows from the axioms, and (3) the code, a transcription of the theorem to a procedural language. Correctness of the code relies on the logical relationship of the theorem with the axioms and relies on an accurate transcription of the theorem to the procedural language. Sorting is an example where relational programming has the advantage of a higher degree of abstractness: the data to be sorted can be any data type in C++ (the procedural language we use in our examples) that satisfies the axioms of linear order, while the pure-Prolog version is limited to data structures in the form of linked cells. We show another advantage of relational programs: they have a model-theoretic and fixpoint semantics equivalent to each other and analogous to those of pure Prolog programs.