This post provides manuals and information about the BPL system as well as a history with the different versions of the BPL system that can be downloaded.

Bousi~Prolog: Design and Implementation

Bousi~Prolog Manual

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).

The BPL syntax is mainly the Prolog syntax but enriched with a built-in symbol “~” used for describing proximity relations (actually, fuzzy binary relations which are automatically converted into proximity or similarity relations) by means of what we call a proximity equation. Proximity equations are expressions of the form:

<symbol> ~ <symbol> = <proximity degree> 

Although, a proximity equation represents an arbitrary fuzzy binary relation, its intuitive reading is that two constants, n-ary function symbols or n-ary predicate symbols are approximate or similar with a certain degree. That is, a proximity equation

a~b = α

can be understood in both directions: a is approximate/similar to b and b is approximate/similar to a with degree α. Therefore, a BPL program is a sequence of Prolog facts and rules followed by a sequence of proximity equations. 

Example 1. Suppose a fragment of a database that stores a semantic network with information about people’s names and hair color, as well as the approximate relation between black, brown and blond hair. 

% BPL directive                % FACTS
 :- transitivity(no).           is_a(john, person).
                                is_a(peter, person).
% SIMILARITY EQUATIONS          is_a(mary, person).
  black~brown=0.6.              hair_color(john,black).
  black~blond=0.3.              hair_color(peter,brown).
  blond~brown=0.6.              hair_color(mary,blond).

In a standard Prolog system, if we ask about whether peter’s hair is blond, “?- hair color(peter, blond)”, the system fails. However BPL allows us to obtain the answer “Yes with 0.6”. 

To obtain this answer, the BPL system operates as follows: i) First it gen- erates the reflexive, symmetric closure of the fuzzy relation {R(black, brown) = 0.6, R(black,blond) = 0.3, R(blond,brown) = 0.6}, constructing a proxim- ity relation. ii) Then it tries to unify the goal hair color(peter, blond) and (eventually) the fact hair color(peter,brown). Because there exists the en- try R(brown, blond) = 0.6 in the constructed proximity relation (that is, brown is approximate to blond), the unification process succeeds with approximation degree 0.6. 

The above example serves to illustrate both the syntax and the operational se- mantics of the language. Also, it is important to note that, in the last example, to inhibit the construction of the transitive closure (and therefore the construc- tion of a similarity relation) has been crucial to model the information properly and to obtain a convenient result. This effect is obtained by the BPL directive transitivity which disables or enables the construction of the transitive closure of a fuzzy relation during the compilation process. If a similarity relation would be generated, the system would constructed the entries R(brown, blond) = 0.3 and R(blond,brown) = 0.3, overlapping the initial approximation degree pro- vided by the user and leading to a wrong information modeling 

Unification and term comparison. 
BPL implements a weak unification operator, also denoted by ‘~’. It can be used, in the source language, to construct expressions like ‘Term1 ~ Term2 =:= Degree’ which is interpreted as follows: The expression is true if Term1 and Term2 are unifiable by proximity with approximation degree equal to Degree. In general, we can construct expressions ‘Term1 ~ Term2 <op> Degree’ where “<op>” is a comparison arithmetic operator or the symbol “=”. In the last case, the construction “Term1 ~ Term2 = Degree” success if Term1 and Term2 are weak unifiable with approximation degree Degree.  Note that these are crisp expressions which are evaluated to the approximation degree 1.0.

Starting with BPL version 3.4, an explicit weak unification operator ‘~~’ was implemented, which is the fuzzy counterpart of the syntactical unification operator ‘=’ of standard Prolog. The expression ‘Term1 ~~ Term2’  success with degree D if  Term1 and Term2 are unifiable by proximity with approximation degree D. Note that contrary to the last operator  ‘~’, this is a fuzzy operator that returns approximation degrees between 0 and 1.0.

The expressions built with these operators may be introduced in a query as well as in the body of a clause.

Fuzzy sets. 
BPL makes use of two directives to define and declare the structure of a linguistic variable: domain and fuzzy_set. 

The domain directive allows to declare and define the universe of discourse or domain associated to a linguistic variable.  The fuzzy_set directive allows to declare and define a list of fuzzy subsets (which are associated to the primary terms of a linguistic variable) on a predefined domain. At this time, it is possible to define two types of membership functions: either a trapezoidal function or a triangular function. 

BPL provides modifiers that can be applied to fuzzy subsets. Additionally, a BPL program may include what we call “domain points” and “domain ranges”. 

Example 2. BPL models the following fuzzy inference in a very natural way: “if $x$  is young then $x$ is fast” and “Robert is middle” then “Robert is somewhat fast”.

% DIRECTIVES
 :-domain(age, 0, 100, years).
 :-fuzzy_set(age,[young(0,0,30,50), middle(20,40,60,80),
                  old(50,80,100,100)]).
 :-domain(speed, 0, 40, km/h).
 :-fuzzy_set(speed,[slow(0,0,15,20), normal(15,20,25,40),
                    fast(25,30,40,40)]).

% FACTS AND RULES
 speed(X, fast) :- age(X, young).        
 age(robert, middle).

Now, if we launch the goal: “?- speed(robert,somewhat#fast). The BPL system answers “Yes with 0.375”.

Definite Clause Grammars.
Version 3.6 has introduced the ability to work with Definite Clause Grammars (DCG) natively.  DCGs were initially a notation for writing production rules for defining grammars, but now they can be used to parse, generate and check lists. In addition, they form a comfortable interface to difference lists.

WordNet and BPL. 
In Bousi∼Prolog, the wn-connect subsystem must be made visible before using the built-ins (public predicates) defined in its modules. This can be done interactively, without the requirement of loading a BPL program first, by launching the following goal:

BPL> ensure_loaded(wn(wn_connect)).
         Yes
         With approximation degree: 1 .

or loading a program, with the directive  :- wn connect. in the first line of the program.

Remember that BPL directives must be used within a program. BPL directives  to access the WordNet database and all the ancillary stuff for related predicates are the following:

:- wn_connect.
This directive performs the necessary actions to connect BPL to the WordNet resources. It must occur before any other access to WordNet, and it assumes that the environment variable WNDB has been set to the OS directory in which the WordNet database is stored.

There is an alternative to this directive if the environment variable cannot be set or the user simply does not want to:

:- wn_connect(Directory).
Where Directory is the directory where the WordNet database is located.

Next directives are responsible for generating proximity equations building an ontology:

:- wn_gen_prox_equations(Msr, LL_of_Pats).
Where Msr is the similarity measure which can have any of the following constant values:  path,  wup (Wu & Palmer, 1994), lch (Leacock & Chodorow, 1998), res (Resnik, 1995), jcn (Jiang & Conrath, 1997) and lin (Lin, 1998). The second argument LL_of_Pats is a list for which each element is another list containing the patterns that must be related by proximity equations.
The pattern can be either a word or the structure Word:Type:Sense, where Word is the word, Type is its type (either n for noun or v for verb) and Sense is the sense number in its synset.
If the pattern is simply a word, then a sense number of 1 is assumed, and its type is made to match to all other words in the same list.

Filtering techniques.
The BPL code can be optimized using filtering techniques. The idea is that the proximity equations in the program files and ontology can be filtered according to the lambda cut, so that the proximity equations that relate the terms with a degree lower than the lambda cut are discarded. Also, this technique prevents the generation of certain rules after the parsing phase, which greatly reduces non-determinism and, therefore, the search tree for a given goal.

Filtering can be activated or deactivated inside a BPL program, using a directive, or from the the BPL shell, using the command fl:
– Filtering directive:    :-filtering(+Boolean).   If the parameter Boolean is true, activates filtering, if it is false, disables filtering.
– Command fl:    fl +Boolean.   Same behaviour as the directive.

On the other hand, the lambda-cut can be modified using the BPL shell command lc.

Tail recursion and Indexing.
Bousi~Prolog implements WSLD-resolution by translating BPL code into Prolog code. The translation process is called BPL expansion and the translated code, TPL code. BPL expansion has two drawbacks: first, expanded rules breaks tail recursion and, second, it avoids the benefits of clause indexing techniques available in current implementations of Prolog.

Tail recursion is lost because when the rules of the BPL source program are expanded, partial degrees are composed by means of a last call to the internal predicate degree_composition/2. So, if a predicate in the source program is defined by tail recursion, when expanding the rule to obtain the TPL program, the last call is not anymore a call to the recursive predicate, and Prolog cannot perform last call optimization when the TPL program is consulted. This problem can be solved by computing the partial degrees first (by means of a call to the predicate degree_composition/2) and passing them, on the fly, through an accumulator parameter of each call in the body of a rule, keeping the last call as the recursive call.

A new directive  :-degree accumulator(+Boolean) is provided for either enabling or disabling degree accumulator translation. Enabling this translation implies not breaking tail recursion optimization in BPL programs. By default, it is enabled (Boolean=true).

Problems with indexing arise because, for accomplishing a proximity based semantics with a crisp syntactic unification, it is necessary to flatten and linearise the rules of the BPL source program. In this way, two drawbacks occur: first, head unification is delayed up to the clause body, which avoids some Prolog compiler optimisations; and, second, the indexation on head arguments in the rules is lost. We have introduced some techniques to remedy some aspects of these indexing problems.

A new directive  :-indexing(+Boolean) is at disposal of a BPL system user for either enabling or disabling indexing optimization. By default, it is enabled (Boolean=true).

Logic Programming is founded on the idea that logic, or at least substantial subsets of it, can be used as a programming language. Although logic programming has been used in a wide range of applications such as problem solving and knowledge representation, deductive database systems, expert systems or natural language processing, it has not direct tools to deal with the essential vagueness or uncertainty of some problems.

Fuzzy Logic Programming amalgamates fuzzy logic and pure logic programming, in order to provide these languages with the ability of dealing with uncertainty and approximated reasoning. One of the main advantages of this combination is the construction of programming languages that allow us to deal with imprecise information by using declarative techniques. 

Bousi~Prolog (BPL) is a fuzzy logic programming language that replaces the syntactic unification mechanism of classical SLD-resolution by a fuzzy unification algorithm. This algorithm provides a weak most general unifier as well as a numerical value, called the unification degree. Intuitively, the unification degree represents the truth degree associated with the (query) computed instance. Then, the core of BPL operational semantics is a fuzzy unification algorithm based on proximity relations (that is reflexive and symmetric, but not necessarily transitive, binary fuzzy relations on a set). Hence, generalizing the operational mechanism of Maria I. Sessa, based on similarity relations, and increasing the expressive power of the resulting language. Proximity relations allow us to model problems where the transitivity restriction of a similarity relation is an obstacle.

Also we use proximity relations to implement  fuzzy sets (linguistic variables),  obtaining an elegant, simple, natural and efficient fuzzy Prolog system based on weak unification.

Starting with version 3.1 of the BPL system, it integrates WordNet. New versions, such as version 3.3, has increased the connection with WordNet.

Since version 3.5 the BPL system incorporates “graded rules“, that is, fuzzy rules can be annotated with an approximation degree. Now, the degree of a computation has two sources: the approximation degree provided by the weak unification algorithm and the annotation of the rule used to perform the step. The BPL user can choose the t-norm used to combine these degrees among a wide set of t-norms: product, luka, drastic, nilpotent, and hamacher.

Version 3.6 has introduced the ability to work with Definite Clause Grammars (DCG) natively.  DCGs were initially a notation for writing production rules for defining grammars, but now they can be used to parse, generate and check lists. In addition, they form a comfortable interface to difference lists.

Bousi~Prolog and efficiency 
From the beginning we had a great concern with efficiency. For instance, key proceses for the weak unification algorithm such as the generation of closures or proximity blocks of fuzzy relations, have been moved and confined to the compilation phase, avoiding its computation at runtime.

Version 3.2 was a step ahead for efficiency by means of the implementation of novel filtering techniques that optimize the TPL code generated after the parsing and translating into Prolog phase. Also in version 3.6 we have developed new techniques that allow us to preserve the Prolog tail recursion optimization and even recover certain aspects of its indexing techniques in the framework of high-level implementation. Now, thanks to these optimization techniques, Bousi~Prolog can process larger programs.

Experiments confirm that Bousi~Prolog, equipped with these optimization techniques, is more than four times faster than other comparable systems when it comes to solving a problem that involves weak unification tasks.

Bousi~Prolog Aplications 
There are several practical applications for a language with the aforementioned characteristics: flexible query answering; advanced pattern matching; information retrieval where textual information is selected or analyzed using an ontology; text cataloging and analysis; etc. 

This is the official website of the Bousi~Prolog system.

Bousi~Prolog is a fuzzy logic programming system. This software is for research and educational purposes only and it is distributed with NO WARRANTY.

This site maintains the high level implementation of the Bousi~Prolog system developed, using SWI-Prolog and the C programming language, by:

Juan Gallardo-Casero (University of Castilla-La Mancha — now at INDRA Sistemas), Fernando Sáenz-Pérez (Complutense University of Madrid) and Pascual Julián-Iranzo (University of Castilla-La Mancha).