# The Algebra of Logic Programming

## Silvija Seres

At present, the field of declarative programming is split
into two main areas based on different formalisms; namely,
functional programming, which is based on lambda calculus,
and logic programming, which is based on first-order logic.
There are currently several language proposals for
integrating the expressiveness of these two models of
computation. In this thesis we work towards an integration
of the methodology from the two research areas. To this end,
we propose an algebraic approach to reasoning about logic
programs, corresponding to the approach taken in functional
programming.
In the first half of the thesis we develop and discuss a
framework which forms the basis for our algebraic analysis
and transformation methods. The framework is based on an
embedding of definite logic programs into lazy
functional programs in Haskell, such that both the
declarative and the operational semantics of the logic
programs are preserved.

In spite of its conciseness and apparent simplicity, the
embedding proves to have many interesting properties and it
gives rise to an algebraic semantics of logic
programming. It also allows us to reason about logic
programs in a simple calculational style, using rewriting
and the algebraic laws of combinators. In the embedding, the
meaning of a logic program arises compositionally from the
meaning of its constituent subprograms and the combinators
that connect them.

In the second half of the thesis we explore applications of
the embedding to the algebraic transformation of logic
programs. A series of examples covers simple program
derivations, where our techniques simplify some of the
current techniques. Another set of examples explores
applications of the more advanced program development
techniques from the
Algebra of Programming by Bird and de
Moor, where we expand the techniques currently
available for logic program derivation and optimisation.