Compilation Techniques for Knowledge Representation and Automated Deduction

Prof. Hassan Aït-Kaci

Université Claude Bernard Lyon 1, Villeurbanne, France

Knowledge Representation and Automated Deduction have some specificity that allows using a few particular compilation techniques that can enable substantial optimization of implementation, both in terms of space and time. While the operational semantics of fundamental operations such as property inheritance, order-sorted graph unification, and concept definitions, have been formally specified, using such semantics “as is” yields interpreters which, while providing proofs-of-concept software systems, fail to meet scalability challenges. In the same way as has been the case for more conventional programming languages, deriving a compiler optimizing an interpreter seeks to take advantage of highly recurrent aspects in structure and computation and propose a target low-level data representation and an abstract-machine architecture acting on it using a low-level assembly-like language. This is what all conventional compilers do, including those for more declarative languages such as those used in Functional Programming and Constraint Logic Programming. In this short class, some useful compilation techniques will be covered, with specific illustrations using the Order-Sorted Feature (OSF) graph constraint formalism. These form a basis to optimize knowledge manipulation and computational inference system sharing the same characteristics (i.e., all taxonomies and most attributed ontologies that can be processed as constraint specifications, including some semi-decidable kinds).


Expected work: The course will consist of 5 2-hour lectures. Due to the short time available, there will be no assignments besides readings, although longer-term independent projects for specific implementations in a popular imperative idiom (Java, Scala, C++, …) will be suggested to those interested in getting a hands-on experience on there own. The students are encouraged to read the above documents ahead of time to get some momentum, bringing questions to clarify when the material is covered in class.

Prerequisite: This course will be aimed at graduate and/or post-graduate CS majors with a bent for implementation, having some notions about what term unification is, of how the Prolog language works and aware of its techniques of compilation for unification and backtracking (namely, Warren’s Abstract Machine). It would also be good, although not necessary, if they had heard of the LIFE CLP programming language.