Categorical Modelling of Logic Programming: Coalgebra, Functorial Semantics, String Diagrams
Logic programming (LP) is driven by the idea that logic subsumes computation. Over the
past 50 years, along with the emergence of numerous logic systems, LP has also grown into a
large family, the members of which are designed to deal with various computation scenarios.
Among them, we focus on two of the most influential quantitative variants are probabilistic
logic programming (PLP) and weighted logic programming (WLP).
In this thesis, we investigate a uniform understanding of logic programming and its quan-
titative variants from the perspective of category theory. In particular, we explore both a
coalgebraic and an algebraic understanding of LP, PLP and WLP.
On the coalgebraic side, we propose a goal-directed strategy for calculating the probabilities
and weights of atoms in PLP and WLP programs, respectively. We then develop a coalgebraic
semantics for PLP and WLP, built on existing coalgebraic semantics for LP. By choosing
the appropriate functors representing probabilistic and weighted computation, such coalgeraic
semantics characterise exactly the goal-directed behaviour of PLP and WLP programs.
On the algebraic side, we define a functorial semantics of LP, PLP, and WLP, such that they
three share the same syntactic categories of string diagrams, and differ regarding to the semantic
categories according to their data/computation type. This allows for a uniform diagrammatic
expression for certain semantic constructs. Moreover, based on similar approaches to Bayesian
networks, this provides a framework to formalise the connection between PLP and Bayesian
networks. Furthermore, we prove a sound and complete aximatization of the semantic category
for LP, in terms of string diagrams. Together with the diagrammatic presentation of the
fixed point semantics, one obtain a decidable calculus for proving the equivalence between
propositional definite logic programs.
https://discovery.ucl.ac.uk/id/eprint/10168183/1/tao-thesis.pdf