Clauses storage in 2P-Kt

Clauses storage in 2P-Kt

advanced project



The following work approaches the recurring problem in Prolog implementations of storing the multitude of clauses that constitutes the program knowledge base. The implementation at stake is the porting of the tuProlog project to a multi-platform framework completely rewritten in Kotlin, at supporting both the JVM and JavaScript platforms. There are two simple key concepts behind the storage of clauses, especially when the theory is used in a dynamic fashion to be interacted with programmatically: a) relative order matters, since Prolog semantic can only be respected if the clauses are resoned about in the same order they were written and b) it needs to be as fast as possible, since it will be massively accessed by the Prolog solver engine in order to achieve the expected program output. The previous implementation, while being perfectly fine from a design standpoint, lacked to achieve the first point. At the moment of inspecting the database content, variables would end up clustered as the initial component of every result. This strife with the desire of programmatically interact with the clauses, since losing a common sense of the insertion order meant losing the ability to write a Prolog program, hindering the language correctness.
Spotting the source of this problematic behaviour has meant following the path of a clause since the moment it is created, to the moment it would actually be stored into the data structure, to the moment it is retrieved according to a rightful query. This eventually lead to a complete refactoring of the data structure, to both address problematics encountered or unlock strategic opportunities recognized along the path.
What the refactoring mainly addressed was the loosely coupling of the clause access interface (referred as the ClauseDatabase from now on) from the actual clause storage facility (referred as ReteTree from now on) through the creation of a collection framework that would abstract away the control over the ReteTree and allow for the reuse of the clause storage utilities it implements to fulfill other purposes.
As the refactoring was being carried out, it emerged the possibility of introducing the first parameter indexing feature, allowing for a faster retrieval where the proper set of clauses are asserted into the theory, and the proper set of query is used to retrieve them. This led to another refactoring, completely centered on the ReteTree, changing the ways it stores clauses and adding means to optimize exploration performances wherever it could be done.



— a.y.


— credits


— cycle

2nd cycle

— language



— professor

Andrea Omicini

— tutors

Giovanni Ciatto


— university

Alma Mater Studiorum-Università di Bologna

— campus


— department / faculty / school


— 2nd cycle

8614 Ingegneria e scienze informatiche 


AMS page  |  course page  |  course on IOL  |  course timetable


— course ID


Partita IVA: 01131710376 — Copyright © 2008–2023 APICe@DISI – PRIVACY