language: en

Constructing Logic Programs with Higher-Order Predicates 1

Jorgen Fischer Nilsson
Department of Computer Science Technical University of Denmark
Andreas Hamfelt
Computing Science Department Uppsala University

Abstract: This paper proposes a logic programming approach based on the application of a system of higher-order predicates put at disposal within ordinary logic programming languages such as prolog. These higher-order predicates parallel the higher-order functionals or combinators which form an established part of contemporary functional programming methodology. The suggested toolbox of higher-order predicates for composing logic programs is derived from one universal higher-order predicate. They take the form of recursion operators (in particular for expressing recursion along lists) intended to cover all commonly occurring recursion schemes in logic programming practice. Their theoretical sufficiency is proved and their practical adequacy is argued through examples. The recursion operators, denoting higher-order relations rather than functions, are brought about straightforwardly through a well-known metalogic programming technique, rendering superfluous the need for special higher-order unification mechanisms.

Keywords: Relational higher-order and metalogic programming. Logic program recursion schemes. Declarative logic programming methodology.

[Perche nessuna cosa si puo amare ne odiare, se prima no si a cognitio di quella. - Leonardo da Vinci, Notebooks]

1 Introduction: Background and Ob jectives