So I am on to the second language in Bruce Tate's Seven Languages for Seven Weeks. Prolog is likely to be the most 'different' language of all the languages featured. It is a declarative logic programming language, and in some ways is more than just a language as it comes with an engine for logical reasoning and resolution. As opposed to describing how to answer a given question; in Prolog you tell it the state of the world and then ask it for the meaning of life, leaving the system to figure out the details.

Developed in 1972 by Alain Colmerauer and Phillipe Roussel, Prolog was aimed at natural language processing (and not the statistical stuff), and has also found its way into theorem proving and expert systems. Prolog has three main building blocks: facts are basic assertions about the world, rules are inferences that relate facts and queries are questions about the world.

Lets look at some code. I decided to try to model a food web in Prolog, specifically I am using GNU Prolog, it seems different implementations can vary a fair bit in what they support. The code below represents the following food web.



/* Facts
  http://commons.wikimedia.org/wiki/File:Chesapeake_Waterbird_Food_Web.jpg
*/
eats(small_planktivorous_fish, phytoplankton).
eats(bivalves, phytoplankton).
eats(benthic_invertebrates, phytoplankton).

eats(bivalves, zooplankton).

eats(herbivorous_ducks, submerged_aquatic_vegetation).

eats(geese, vegetation).
eats(mute_swan, vegetation).
eats(tundra_swan, vegetation).

eats(sea_ducks, benthic_invertebrates).

eats(herbivorous_ducks, bivalves).
eats(sea_ducks, bivalves).
eats(tundra_swan, bivalves).

eats(large_piscivorous_fish, small_planktivorous_fish).
eats(wading_birds, small_planktivorous_fish).
eats(gulls, small_planktivorous_fish).
eats(terns, small_planktivorous_fish).

eats(bald_eagle, sea_ducks).
eats(bald_eagle, large_piscivorous_fish).
eats(osprey, large_piscivorous_fish).

/* define the extinct rule, so that Prolog doesn't complain it doesn't
   exist if there are no extinct creatures */
extinct(dodo).
extinct(small_planktivorous_fish).

/* Rules */
dinner_friends(X, Y) :- eats(X, Z), eats(Y, Z), \+(X = Y).
ally(X,Y) :- eats(Z,X), eats(Z,Y), \+(X = Y), \+(eats(X,Y)).

/* Recursion: a creature has food if there is a non extinct creature
   they eat that also has food. Add some rules at the bottom of the food
   chain to indicate that they do not 'eat' */
has_food(phytoplankton).
has_food(vegetation).
has_food(submerged_aquatic_vegetation).
has_food(X) :- eats(X,Z), \+extinct(Z), has_food(Z).

/* If a Var is passed in, this really means, does no one have food!*/
has_no_food(X) :- \+(has_food(X)).

/* Queries */

ally(bivalve, Who).
dinner_friends(sea_ducks, Who).
/* list everyone who has food */
has_food(Who).
/* no, because of the extinction of small_planktivorous_fish */
has_food(osprey).
/* yes, they can still eat sea ducks */
has_food(bald_eagle).

There are rules specifying which creatures are eaten by which. These are the direct assertions like,


eats(geese, vegetation).

Rules can build on this to define relationships between facts, for example the dinner_friends rule specifies creatures that share a particular appetite. It has three subgoals, in the first two, it establishes that the two species X and Y eat some other species Z. The third subgoal specifies that X and Y should be different creatures, the '\+' is negation in Prolog. We can then ask a question like, dinner_friends(gulls, wading_birds). or dinner_friends(sea_ducks, Who).

At this point it is useful to step back and note a few things. First, case matters in Prolog, identifiers that start with lowercase letters are atoms, that is they are actual things in the world. Identifiers that start with uppercase letters (like Who) are variables. In resolving a rule, Prolog goes through matching facts, trying to unify atoms and rules with variables to create true statements. If the unification succeeds you get the answer 'yes', or in the case of a variable passed to a query, you get the atom(s) that made the rule true (or you get 'no' if it did not succeed).



dinner_friends(gulls, wading_birds). => 'yes'
dinner_friends(sea_ducks, Who). => Who = herbivorous_ducks
                                    Who = tundra_swan


Recursion

I also tried to make a recursive rule, the has_food rule, checks to see if there is something a creature can eat that is not extinct, that in turn has food. For this I had to add a few base cases for the organisms at the bottom of the food chain. Using this rule, I am able to take an organism out of the food chain (by declaring it extinct) and see what other organisms are affected. Here is that snippet again.



/* define the extinct rule, so that prolog doesn’t complain it doesn’t
   exist if there are no extinct creatures */
extinct(dodo).
extinct(small_planktivorous_fish).
/* Recursion: a creature has food if there is a non extinct creature
   they eat that also has food. Add some rules at the bottom of the food
   chain to indicate that they do not ‘eat’ */
has_food(phytoplankton).
has_food(vegetation).
has_food(submerged_aquatic_vegetation).
has_food(X) :- eats(X,Z), \+extinct(Z), has_food(Z).

/* If a Var is passed in, this really means, does no one have food!*/
has_no_food(X) :- \+(has_food(X)).


The last line in the above snippet is a good reminder to carefully consider your formal logic when making rules. Just by negating has_food we do not always get what we be expecting, in particular that has_no_food(Who), will return a list of animals without food. If we pass in a variable we are really requiring a universal quantification (i.e. nothing should match has_food(X)) for it to return 'yes' as opposed to the existential quantification I initially desired (i.e. there is something that does not match the has_food rule).

That's it for day one! It was a fairly gentle introduction, my only gripe so far was that working with the actual Prolog interactive environment had some small annoyances. For example when reloading the file into the environment, the previously defined predicates are removed. They may be redefined in your file, but if you commented something out for example, it will still actually be there. I couldn't find a command that would clear the Prolog environment, so had to quit and restart it a bunch.

All the code is also up on github.