Solving Logical Business Problems Using Prolog: Part One

Software development problems in business frequently involve some form of data management. At a basic level, that might be tracking simple things like sales or inventory quantities. At a more complex level, business needs may include effective scheduling, resource distribution, delivery routing, metrics gathering and analysis, and simulation. These can be highly logical problems, necessitating a highly logical coding solution.

Most programmers are accustomed to trying to solve those problems with imperative paradigms, as seen in the most popular languages like Java, Javascript, C++, C#, etc. An imperative language concerns itself primarily with how a program operates. It is command-oriented, changing a program’s state through the use of (usually) volatile variables that can be assigned and reassigned values. In contrast, a declarative language defines what a program should accomplish and leaves the how to the compiler itself. Declarative programs tend to conform more to the mathematical definition of a task than to its implementation. They consciously avoid side effects, most noticeably in that variables can only ever be assigned values once during execution.

Prolog is the primary representative of logic programming, a type of declarative programming. In logic programming, we engage in controlled deduction, meaning that we rely on the run-time engine to infer a problem’s solution for us. This requires the programmer to have a distinct mindset: We are not calculating results directly, but rather we are describing a search space to be explored by the logic engine.

As Prolog lends itself to logically complex tasks and theorem proving, it remains popular in academic research. It is less well known in industry circles, though it is popular in specific fields such as artificial intelligence and natural language processing.

But Prolog is useful for more than theoretical work! It is well suited to any relational, data-driven problem that can be logically defined. Also, there are tools available to call Prolog code from other languages like Java, allowing developers to perform specific tasks with Prolog before processing its results in another language. We can therefore leverage its problem-solving strengths without sacrificing the more extensive libraries and legacy code built with other platforms.

In this introduction to a four-part series, we will explain the basic elements of the Prolog language. In part two, we will discuss constraint logic programming (CLP), a powerful tool for solving satisfiability problems. In part three we will use CLP in a small but powerful program for scheduling task assignments. Finally, in part four, we will explain how to integrate Prolog and Java code through cross-language function calls.

Note that all code examples may be run using SWI-Prolog, a powerful and freely available Prolog distribution.

Facts and Rules

Prolog is designed around evaluation of predicates, which are similar to functions that evaluate either to true or false. The two basic types of predicates in this language are facts and rules.

A fact defines basic data. For example, to create persons named Blake and Jonathan, write:

person(blake).

person(jonathan).

As predicates, facts always return true. To see this, you can go to the SWI-Prolog console and load a .pl source file containing the two facts above, using consult(filename). Then type:

?- person(blake).

true.

By executing that code, you are implicitly calling a rule of the following form:

person(blake) :- true.

We can define a relationship between a person and what he likes using tuple-like facts (that is, predicates with a higher arity):

likes(blake,hamburgers).

likes(blake,smashbros).

likes(jonathan,dolphins).

We can create a predicate to see if someone is a person and likes something using the following rule:

person_likes(Name,Thing) :- person(Name),likes(Name,Thing).

The comma (,) may be thought of as an and operator. That is, if person(Name) evaluates to true and likes(Name,Thing) evaluates to true, then the entire rule returns true. Prolog evaluates predicates in order from left to right, which allows us to feed the output from one call as input to the next.

If you’re editing a source file, you can reload it by typing consult(filename) again. Test our new rule with:

?- person_likes(blake,hamburgers).

true.

Variables and Non-Determinism

Much of Prolog’s power comes from its process of binding values to variables. When Prolog needs to use a variable, it looks to see if it can infer anything concrete to assign to it. This is called unifying the variable with a value.

If Prolog sees there are multiple candidate values to unify with a variable, it doesn’t just pick one. It uses them all.

We can see this by writing a call in the Prolog console to obtain all defined persons. Note that a string starting with a lower-case letter (like blake above) is treated as a constant atom, whereas a string starting with an upper-case letter is treated as a variable.

?- person(Person).

Person = blake ;

Person = jonathan.

In executing this call, Prolog sees there are two existing person predicates. It unifies Person with the first value it sees (blake), returns the result, and then backtracks to unify Person with the second value it sees (jonathan). That is, it non-deterministically computes the result of using every possible variable binding. It will even do this for more complex functions, with any number of variables:

?- person_likes(Person,Thing).

Person = blake,

Thing = hamburgers ;

Person = blake,

Thing = smashbros ;

Person = jonathan,

Thing = dolphins.

If we wanted to aggregate all the results Prolog finds into a list, we can use the built-in predicate findall:

?- findall(Thing,person_likes(_,Thing),Things).                                    

Things = [hamburgers, smashbros, dolphins].

The first parameter tells findall what variable’s bindings to pull from the predicate in the second parameter (person_likes(_,Thing)), to be unified with the variable in the third parameter (Things). Note that we used an underscore (_) in place of Person here; Prolog still binds all available persons as part of its solution-finding process, but we use an underscore to indicate that we don’t care what they are.

Lists and Recursion

Like many other declarative languages, Prolog does not have traditional loop structures like for and while. Therefore, any iterative operation requires recursion. Frequently we use lists in recursive predicates. They are typically used like a stack, popping off elements for each recursive call until we end up with a base case of an empty list.

For example, we could take the list of Things above and determine who likes each thing in the list:

% which_people_like(+Things,+PeopleLikeAcc,-PeopleLike)

which_people_like([],PersonLike,PersonLike).

which_people_like([Thing|Things],PeopleLikeAcc,PeopleLike) :-

    findall(Person,likes(Person,Thing),People),

    append(PeopleLikeAcc,[people_like(People,Thing)],PeopleLikeAcc2),

    which_people_like(Things,PeopleLikeAcc2,PeopleLike).

This code contains many of the elements commonly found in recursive Prolog functions. The comment at the top (indicated by %) describes the expected parameters: in traditional notation, a “+” designates input, a “–” designates output, and a “?” designates either. Here, Things is the list of things to check against the fact database and PeopleLike is an output list of people_like terms. PeopleLikeAcc is an accumulator, meaning that it temporarily stores the list of terms as it is being constructed on each recursive call, before its final result is unified with PeopleLike once the base case is reached. The original call should initialize it to an empty list:

?- which_people_like([hamburgers,dolphins,smashbros,football],

       [],PeopleLike).

PeopleLike = [people_like([blake], hamburgers), people_like([jonathan], dolphins), people_like([blake], smashbros), people_like([], football)].

As you can see, no one likes football.

There are two predicates defined for which_person_likes. Prolog will try to call both, but they are constructed in such a way that only one signature can be matched at a time. When Things is empty ([]), the first base predicate will be called, which will unify PeopleLikeAcc with PeopleLike and return that as the result. When Things has content, it will match the second predicate.

The list split construction [Thing|Things] can be read as [head|tail], where head is the first element of the list and tail is the list of elements after the head. We use findall to obtain all People who like Thing, then append a new term people_like(People,Thing) to our accumulator PeopleLikeAcc. Prolog doesn’t permit us to modify the existing accumulator list, so we create a new one, creatively called PeopleLikeAcc2. We then recursively call which_people_like again. Note that the recursive call happens last, which makes the function tail-recursive, allowing Prolog to optimize its execution.

Conclusion

Programming in Prolog feels very different from programming in an imperative language like Java. In my personal experience, the two most difficult things to adapt to are recursive programming and non-deterministic variable binding.

I first felt like I truly grasped the language when I began to think of my code as defining a search space. Much of Prolog programming can be thought of as defining the boundaries of that space, and then letting Prolog explore it fully. It is important to remember that Prolog does not simply return one solution to a problem, but rather all solutions. You can then consider those solutions and select the best choice for your needs.

In part two, we will discuss constraint logic programming (CLP), before using it in part three to create an employee scheduling system. Finally, in part four, we will show how to call that scheduler from within a Java application.

• Prolog