This is an informal account of the evolution of the Bousi~Prolog language written by Pascual Julián-Iranzo.
The low level approach
The first implementation of Bousi~Prolog (circa 2005-06) was due to Clemente Rubio-Manzano (now at the Bío-Bío University -Chile-) when he was a doctorate student and I his doctoral advisor. This implementation was based on an adaptation of the Warren Abstract Machine (WAM) that we called Similarity WAM Machine.
The Similarity WAM machine (SWAM) is a virtual machine for executing BPL programs coping with similarity relations (not with proximity relations yet). It was implemented using the Java programming language. Roughly speaking, it is an adaptation of the classical WAM, able to execute a Prolog program in the context of a similarity relation defined on the first order alphabet induced by that program. The SWAM uses an operational mechanism that conforms with the weak SLD principle. We dealt with the problem of adapting the WAM to incorporate fuzzy unification in a conservative way, without forcing its main structure. The SWAM is based in a pre-compilation phase, called the Adapter, which introduces some adaptations into the source code to facilitate the translation task. Also, the Adapter translates the original program into a transformed program, with explicit information about the similarity degree of predicates, that helps us to manage similarity relations properly. The similarity relation is stored into the Similarity Matrix memory area and its information is used: during the pre-compilation phase, by the Adapter; at execution time, when it is necessary during the unification process.
The implementation of Bousi~Prolog based on the SWAM was called the “low level” implementation. Although it had advanced features like a GUI interface, the main problem with that implementation was that it only cover the essential features of a standard Prolog system: (weak) unification; (weak) resolution and basic I/O predicates. Moreover, weak unification were not appropriated for working with proximity relations.
Clemente did a great job, but it was very difficult to overcome these aforementioned limitations. At that time I was focused on the theory and he was the only implementer. A larger team was needed to address that task.
The high level approach
Long ago we abandoned the idea of implementing the BPL system using the Similarity WAM. As it has been pointed out, the reason was that we should have had to replicate the entire features of a standard Prolog system and this was a goal above our limited possibilities. Therefore, we decided to build what we called a “high level” implementation based on Prolog its self. This way we could trap nearly all features of a Prolog system easily. I implemented the core of the system (it was circa 2008) and lately Juan Gallardo-Casero (now working at INDRA) completed the task.
A) BPL versions 1 to 1.07
The BPL system (versions 1 to 1.07) was a prototype, written on top of SWI-Prolog. The complete implementation consisted of about 900 lines of Prolog code. The parser and translator module translated (compiled) rules and facts of the source BPL code into an intermediate Prolog code representation which was called “TPL code” (Translated BPL code). Then, following standard techniques, a meta-interpreter executed the TPL code according to the weak SLD resolution principle.
For that versions BPL essentially implemented Sessas’ weak unification algorithm which operates on the basis of a similarity relation (a fuzzy binary relation holding the reflexive, symmetric and transitive properties) on a syntactic domain. So it was important to generate automatically the similarity relation starting from an ordinary fuzzy binary relation on a set of first order symbols of a BPL program. As it was commented, proximity equations of the form
symbol ~ symbol = degree
were used to represent an arbitrary fuzzy binary relation R. A proximity equation “a ~ b = degree” is representing the entry “R(a,b)=degree” of the relation R. The user supplies an initial subset of similarity equations and then, the system automatically generates a reflexive, symmetric, transitive closure to obtain a similarity relation. The transitivity/1 directive can alter this default behavior. A foreign module, written in the C programming language, implemented the algorithm for the construction of the similarity relation. See ‘A procedure for the construction of a similarity relation’ for more details about that algorithm. The foreign library was implemented by Juan Gallardo-Casero. It was his first contribution to the system when he was yet a student.
We gave great importance to this feature because it frees the programmer from the need to build the similarity relation by hand.
B) BPL version 2.0
Between 2010 and 2011, Juan took over the implementation and completely renewed the system.
I asked him to improve the parser that I was implemented using very ad-hoc techniques (it did not even have syntactic error control). Also I suggested a method to translate/compile BPL programs to Prolog in order to eliminate the necessity of a meta-interpreter. The translations was inspired in techniques used for the Adapter module of the SWAM. However, He did much more than that. He improved the structure of the system and every corner of it. He even implemented a GUI interface. When he ended the system was a mature one.
Then, the complete implementation consisted of about 6193 lines of Prolog code (in 10 modules), 1879 lines of C code (in 6 files, excluding the header files) and a number of shell script files to facilitate the installation of the BPL system. After that, the system was more reliable, safe and efficient.
C) The crossing of the desert
In 2012 we were on the deep of the economic crisis and a regional project I was leading conclude and it was impossible to keep going. Money stopped and people had to emigrate. It was a difficult time.
Because similarity relations have expressive limitations, I dedicated my time to define a proximity-based unification algorithm which was sound and complete and could be implemented efficiently.
D) BPL version 3.0
In 2016, I met Fernando Sáenz-Pérez at the annual Spanish conference on Programming Languages (PROLE). I admired Fernando for all the work he was doing on the Datalog Educational System (DES). After my talk, at lunch, we had the opportunity to talk about our work. He was interested in the work we did on BPL (although it had not been the main topic of my talk) and proposed to work to make a fuzzy version of his DES system. That gave rise to him knowing the BPL system and an advantageous collaboration for both began.
In 2017 I knew how to implement a proximity-based unification algorithm efficiently and we started working in that direction.
The proximity-based unification algorithm is based on a new notion of proximity over syntactic symbols. Given a proximity relation R on the symbols of an alphabet and two symbols a and b, they approximate if they belong to the same proximity block and they are always assigned to only a proximity block (note that, it is not sufficient that R(a,b) with a certain degree). If we represent R as a graph, a proximity block is a maximal clique.
Roughly speaking, two terms weakly unify if the symbols at the root position belong to the same proximity block, the arguments of the terms pairwise weakly unify and there are no inconsistencies in the block assignments.
The main novelties of BPL version 3.0 have been the implementation of the new proximity-based unification algorithm and its incorporation to the resolution procedure. Also we introduced other improvements, like the possibility of working with different t-norms distinct than the minimum t-norm. At the present time, the BPL system implements three different weak unification algorithms, including the similarity-based unification algorithm proposed by Maria Sessa, which is only adequate for similarity relations. You can choose which one to use using the weak_unification/1 directive.
We had to modify a number of modules of the BPL system to complete the task and the experience of Fernando was very valuable. Clearly, he played a decisive role in the success of the project.
E) BPL version 3.1
This version integrates WordNet into Bousi~Prolog. Because WordNet relates words but does not give graded information of the relation between them, we have implemented standard similarity measures and new directives that allow us to generate the proximity equations linking two words with an approximation degree.
F) BPL version 3.2
This version has reached a new degree of maturity. The system is more stable and a number of small errors have been eliminated. However, the main novelty of this version has been the incorporation of filtering techniques that optimize the TPL code generated after the parsing phase. Also, fuzzy modifiers can be applied on predicate symbols.
G) BPL version 3.3 and 3.4
Both versions incorporates improvements in the operational mechanism and full access to WordNet through a wide repertoire of built-in predicates. Now all public predicates of the WN-CONNECT modules are accesible through the command line of the BPL shell. Version 4.3 provides a better compilation method which optimices TPL code. Also incorporates an explicit weak unification operator ~~, which can be used in goals and the body of rules.
H) BPL version 3.5
Starting with this version, Bousi~Prolog incorporates “graded rules“. That is, fuzzy rules can be annotated with an approximation degree. During a resolution step, this degree is composed with the resulting approximation degree obtained when weakly unifying a rule head and the current goal. The t-norm used when composing unification degrees can be other than the minimum t-norm (min). Just selecting one of the following constants: product, luka, drastic, nilpotent, and hamacher.
I) BPL version 3.6 (a step further)
It can be considered a step further because the integration of important implementation techniques that improve the efficiency of the BPL system: tail recursion and indexing. These techniques, jointly with the filtering techniques introduced in an earlier version, produce computation speedups four times higher than other comparable systems when it comes to solving a problem that involves weak unification tasks. In terms of functionality, the major contribution of version 3.6 has been the introduction of Definite Clause Grammars (DCG).