advisor(X,Z),
ancestor(Z,Y).
Read the ‘,’ as “and”, while the multiple definitions for ancestor combine with “or” (i.e., each represents
a valid way to be an ancestor, so to be in the ancestor relation it’s enough to satisfy one rule or the other).
All Prolog rules are written in this “or of and’s” form (Disjunctive Normal Form). Notice the use of Z twice
on the right-hand side. This is intentional: this is what captures the fact that the same person must be both
the immediate advisor and herself a descendant.
Armed with this extended rule, we can ask more interesting queries of Prolog:
2(Careful with those capital letters!)
33.1. EXAMPLE: ACADEMIC FAMILY TREES
297
:- advisor(barwise,tarski).
yes
so we can confirm that Barwise was advised by a legend. But it’s always a good idea to write tests that
ensure we didn’t write a faulty rule that made the relation too large:
:- advisor(tarski,barwise).
no
By the way, here’s an easy kind of mistake to make in Prolog: suppose you write
advisor(tawrdowski,brentano).
instead of
advisor(twardowski,brentano).
Then you get
:- advisor(barwise,clemens).
no
Prolog doesn’t have any way of knowing about slight misspellings of Polish names. It accepts your facts
as truth; garbage in, garbage out. This is another important pitfall (along with capitalization and making a
relation too large) to keep in mind.
Now let’s expand the relation with a few more facts. Franz Brentano actually had two advisors, of whom
we’ve given credit to only one above. So we should add the fact
advisor(brentano,trendelenburg).
We can now ask Prolog
:- advisor(barwise,clemens).
yes
:- ancestor(barwise,trendelenburg).
yes
and it shows that the relationships Prolog tracks really are relations, not functions: the mapping truly can
be one-to-many. (We could already have guessed this from the rule for ancestor, where we provided
multiple ways of determining whether or not a pair of constants was in that relation.)
Now let’s add some more rules. The simplest is to ask questions in the other direction:
descendant(X,Y):-ancestor(Y,X).
As of now, each person has only one immediate descendant. But most of these people produced many
students. Tarski, one of the great logicians and mathematicians, not only generated a rich corpus of material,
but also trained a string of remarkable students. We already know of one, Feferman. Let’s add a few more:
298
CHAPTER 33. PROGRAMMING IN PROLOG
advisee(tarski,montague).
advisee(tarski,mostowski).
advisee(tarski,robinson).
Now, clearly, there are more ways of being one’s descendant. There are two ways of fixing the descendant
relation. One, which involves a lot of work, is to add more facts and rules. A much easier fix is to note that
every advisee relationship subscribes a corresponding advisor relationship:
advisor(X,Y):-advisee(Y,X).
And sure enough,
:- descendant(clemens,montague).
yes
:- descendant(trendelenburg,montague).
yes
:- descendant(feferman,montague).
no
:- descendant(barwise,montague).
no
We haven’t at all explained how Prolog evaluates, and that’s largely because it seems so very intuitive
(though once we have multiple clauses, as in descendant, it may be a little less than obvious). But then,
we also haven’t seen Prolog do anything truly superlative. Let’s explore some more.
Let’s first assume we’ve removed Trendelenburg from the database, so Brentano has only one advisor.
(We can do this in a source file by using C-style comments, delimiting text in /* and */.) Then let’s ask
Prolog the following query:
:- ancestor(barwise,X).
What does this mean? We know all the parts: advisor is a relation we’ve defined (by both facts and rules);
barwise is a constant; and X is a variable. We should interpret this as a query, asking Prolog whether there
is a value for X that would satisfy (make true) this query. In fact, we know there is (clemens). But Prolog’s
response is worth studying. This particular Prolog system3 prints
SOLUTION:
X=feferman
So not only did Prolog establish that the query was valid, it also found a solution for X! Now this isn’t the
solution we expected above, but if you think about it for a moment, it’s clear that the query has multiple
solutions, and Prolog has picked one of them. In fact, at the bottom of the window (in this interface), Prolog
says Press cancel to stop, or continue for more solutions. Clicking on the Continue button provides one
more solution, then another, then another, and so on until there are no more, so the final output is
3Trinc-Prolog R3. In many textual Prolog systems, it’s conventional to print a caret to indicate that another solution is available.
The user types a semi-colon to ask Prolog to present it.
33.1. EXAMPLE: ACADEMIC FAMILY TREES
299
SOLUTION:
X=feferman
SOLUTION:
X=tarski
SOLUTION:
X=lesniewski
SOLUTION:
X=twardowski
SOLUTION:
X=brentano
SOLUTION:
X=clemens
no
Wow! Prolog actually “filled in the blank”. In fact, if we put Trendelenburg back into the picture, Prolog
prints one more solution:
SOLUTION:
X=trendelenburg
We can ask a similar query with the variable in the first position instead:
:- ancestor(X,clemens).
SOLUTION:
X=brentano
SOLUTION:
X=barwise
SOLUTION:
X=feferman
SOLUTION:
X=tarski
SOLUTION:
X=lesniewski
SOLUTION:
X=twardowski
This shows that Prolog isn’t just working as a functional program might, where the last position in the
relation is like a “return” location. Prolog really doesn’t discriminate between different positions where you
might put variables.
Maybe this isn’t so surprising. After all, Prolog is merely listing the same chain of relationship that we
entered as facts at the top of the program. Actually, this isn’t quite true: it had to apply the transitive rule of
ancestor to find all the solutions (and these are indeed all of them). But perhaps a more impressive test
would be to ask a query that runs counter to the facts we entered. For this, we should employ the advisee
relation.
300
CHAPTER 33. PROGRAMMING IN PROLOG
:- descendant(tarski,X).
SOLUTION:
X=feferman
SOLUTION:
X=montague
SOLUTION:
X=mostowski
SOLUTION:
X=robinson
SOLUTION:
X=barwise
Sure enough, Prolog produces the entire part of Alfred Tarski’s family tree that we’ve taught it. Notice that
to get to Barwise it had to recur through Feferman using advisor, and to get to Robinson it had to employ
advisee.
This is pretty impressive already. But we can take this a step further. Why stop with only one variable?
We could in fact ask
:- ancestor(X,Y).
In response, Prolog will actually compute all pairs in the ancestor relation and present them sequentially:
SOLUTION:
X=barwise
Y=feferman
SOLUTION:
X=feferman
Y=tarski
SOLUTION:
X=tarski
Y=lesniewski
SOLUTION:
X=lesniewski
Y=twardowski
and so on and on.
Now let’s explore another relation: academic siblings. We can define a sibling pretty easily: they must
have a common advisor.
sibling(X,Y):-
advisor(X,Z),
advisor(Y,Z).
We can either ask Prolog to confirm relationships (and just to be sure, try them both ways):
33.2. INTERMISSION
301
:- sibling(robinson,montague).
yes
:- sibling(montague,robinson).
yes
or to generate their instances:
:- sibling(robinson,X).
SOLUTION:
X=feferman
SOLUTION:
X=montague
SOLUTION:
X=mostowski
SOLUTION:
X=robinson
How’s that? When Robinson comes along to find out who her academic siblings are, she finds. . . herself!
It’s not very surprising that we got this output. What we meant to say was that different people, X and Y,
are academic siblings if. . . and so on. While we may have mentally made a note that we expect X and Y to be
different people, we didn’t tell Prolog that. And indeed, because Prolog programs can be “run backwards”,
it’s dangerous to not encode such assumptions. Making this assumption explicit is quite easy:4
sibling(X,Y):-
advisor(X,Z),
advisor(Y,Z),
X \== Y.
Now, sure enough, we get the right number of siblings.
33.2
Intermission
At this point, we have seen most of the elements of (the core of) Prolog. We’ve seen fact declarations
and the expression of rules over them to create extended relations. We’ve also seen that Prolog evaluates
programs as simple rule-lookups or as queries (where the former are a special case of the latter). We’ve seen
Prolog’s variables, known as logic variables, which can take on multiple values over time as Prolog boldly
and tirelessly seeks out new solutions until it has exhausted the space of possibilities. And finally, related to
this last step, Prolog backtracks as necessary to find solutions, in accordance with the non-determinism of
the rules.
4For a very subtle reason, we cannot move the last line earlier. We will understand why better once we’ve implemented Prolog.
302
CHAPTER 33. PROGRAMMING IN PROLOG
33.3
Example: Encoding Type Judgments
Let’s look at another use for Prolog: to encode type judgments. Recall that we had rules of the form
Γ e : τ
where some were axioms and the others were conditionally-defined judgments. The former we will turn into
facts, the latter into rules.
First, we must determine a representation for abstract syntax in Prolog. We don’t want to deal with
parsing, and we don’t actually distinguish between individual values of a type, so we’ll assume constants
have been turned into an abstract node that hides the actual value. Thus, we use the constant numConst to
represent all syntactically numeric expressions (i.e., those abstract syntax terms of type numE), boolConst
to represent true and false, and so on.
Given this, we will define a three-place relation, type. The first place will be the type environment,
represented as a list; the second will be the expression; and the third the type of the expression. (When
writing this as a function in a traditional language, we might define it as a two-argument function that
computes the expression’s type. But because Prolog can “run backward”, it doesn’t have a distinguished
“return”. Instead, what we normally think of as the “result” is just another tuple in the relation.) Our axioms
therefore become:
type(_,numConst,num).
type(_,boolConst,bool).
The _ represents that we don’t care what goes in that position. (We could as well have used a fresh logic
variable, but the underscore makes our intent clearer.) That is, no matter what the type environment, numeric
constants will always have type num.
The easiest judgment to tackle is probably that for conditional. It translates very naturally into:
type(TEnv,if(Test,Then,Else),Tau) :-
type(TEnv,Test,bool),
type(TEnv,Then,Tau),
type(TEnv,Else,Tau).
Pay close attention to lower- and upper-case initials! Both type and if are in lower-case: the former
represents the type relation, while the latter is the abstract syntax term’s constructor (the choice of name is
arbitrary). Everything else is a type variable. (Notice, by the way, that Prolog performs pattern-matching on
its input, just as we saw for Haskell.)
Given these two facts and one rule for type, we can ask Prolog to type-check some programs (where
[] denotes the empty list):
:- type([],boolConst,bool).
yes
:- type([],if(boolConst,numConst,numConst),num).
yes
:- type([],if(boolConst,numConst,boolConst),num).
no
33.3. EXAMPLE: ENCODING TYPE JUDGMENTS
303
The implementation of this rule in your type checkers reflected exactly the semantics we gave: if the three
conditions in the antecedent were met, then the consequent holds. In contrast, because Prolog lets us query
relations in any way we please, we can instead use the same implementation to ask what the type of an
expression is (i.e., make Prolog perform type inference):
:- type([],boolConst,T).
T=bool
no
:- type([],if(boolConst,numConst,numConst),T).
T=num
no
:- type([],if(boolConst,numConst,boolConst),T).
no
It should be no surprise that Prolog “inferred” a type in the first case, since the use precisely matches the
axiom/fact. In the second case, however, Prolog used the rule for conditionals to determine solutions to the
type of the first expression and matched these against those for the second, finding the only result. In the
third case, since the program does not have a type, Prolog fails to find any solutions.
We can now turn evaluation around by asking Prolog strage questions, such as “What expression have
type num?”
:- type([],T,num).
Amazingly enough, Prolog responds with:5
SOLUTION:
T=numConst
SOLUTION:
T=if(boolConst, numConst, numConst)
SOLUTION:
T=if(boolConst, numConst, if(boolConst, numConst, numConst))
SOLUTION:
T=if(boolConst, numConst,
if(boolConst, numConst,
if(boolConst, numConst, numConst)))
The output here actually gives us a glimpse into the search order being employed by this implementation
(notice that it depth-first expands the else-clause of the conditional).
Next let’s deal with identifiers. We’ve said that the type environment is a list; we’ll use a two-place
bind relation to track what type each identifier is bound to.6 To look up the type of an identifier in the type environment, therefore:
5The output has been indented for readability.
6We’ll make the simplifying assumption that all bound identifiers in the program are consistently renamed to be distinct.
304
CHAPTER 33. PROGRAMMING IN PROLOG
type([bind(V,T)|_],var(V),T).
type([bind(_,_)|TEnvRest],var(V),T):-
type(TEnvRest,var(V),T).
A quick test:
:- type([bind(w,bool),bind(v,num)],var(v),T).
T=num
Next we’ll specify the rule for functions:
type(TEnv,fun(Var,Body),arrow(T1,T2)) :-
type([bind(Var,T1)|TEnv],Body,T2).
Testing this:
:- type([],fun(x,if(var(x),numConst,boolConst)),T).
no
:- type([],fun(x,if(var(x),numConst,numConst)),T).
T=arrow(bool,num)
Notice that in the second example, Prolog has determined that the bound identifier must be a boolean, since
it’s used in the test expression of a conditional.
Finally, the rule for applications holds no surprises:
type(TEnv,app(Fun,Arg),T2) :-
type(TEnv,Fun,arrow(T1,T2)),
type(TEnv,Arg,T1).
Running it:
:- type([],
app(fun(x,if(var(x),
numConst,
numConst)),
boolConst),
T).
T=num
Now let’s try some more interesting functions:
:- type([],fun(x,var(x)),T).
T=arrow(__2823020, __2823020)
This is Prolog’s way of saying that parts of the answer are indeterminate, i.e., there are no constraints on it.
In short, Prolog is inferring parameterized types!
33.4. FINAL CREDITS
305
:- type([],
app(fun(id,
if(app(var(id),boolConst),
app(var(id),boolConst),
app(var(id),boolConst))),
fun(x,var(x))),
T).
T=bool
:- type([],
app(fun(id,
if(app(var(id),boolConst),
app(var(id),numConst),
app(var(id),numConst))),
fun(x,var(x))),
T).
no
Finally, we have to try:
:- type([], fun(x, app(var(x), var(x))), num).
no
:- type([], fun(x, app(var(x), var(x))), T).
T=arrow(arrow(arrow...
Exercise 33.3.1 Are Prolog’s types truly polymorphic? Do they automatically exhibit let-based polymor-
phism (Section 31)? Write appropriate test expressions and present Prolog’s output to justify your case.
33.4
Final Credits
We’ve now seen even more of Prolog. We’ve encountered the “don’t care” notation. Prolog computes the
most general response it can, so if there are no constraints on some part of the answer, it leaves them unde-
fined (using the same symbol to show sharing constraints, as in the inferred type of the identity function).
Prolog will match patterns as deep as they are nested, and programmers can use the same variable twice
in a rule to indicate that they intend for the values of both to be the same. (Having already seen this with
genealogical trees, we made much more extensive use of it to encode type judgments, mimicking the use of
meta-variables when we wrote the judgments on paper.)
Putting together the pieces, we found that Prolog was a very convenient encoding of the rules of a type
checker. Indeed, for free, we were able to turn our type checker into a type inference engine. Thinking about
how we implemented type inference manually may give us some clues as to how to implement Prolog!
306
CHAPTER 33. PROGRAMMING IN PROLOG
Chapter 34
Implementing Prolog
A Prolog program is a collection of facts and rules. Against these, we ask Prolog a query, also known as
providing a goal that it must satisfy. If a goal contains logic variables, Prolog must find assignments (if
necessary) for those variables consistent with the facts and rules.
It is easy to see that in the typical case, a collection of Prolog facts subscribes a flat relational database.
Searching such a database is not especially hard (there are obviously challenges to doing so efficiently, but
these concerns are handled well by database management systems; they’re outside the scope of our study).
Prolog evaluation becomes interesting with the introduction of rules.
34.1
Implementation
As we have seen, Prolog rules are in disjunctive normal form, i.e., an “or of and’s”. Such formulas naturally
subscribe a tree, where the individual nodes in the tree are labeled by a Boolean connective. Given a goal,
Prolog can construct a disjunctive tree of the facts and rules that match the head term in the goal. For
instance, if the query is
:- ancestor(barwise,feferman).
Prolog can construct an or-labeled tree of all the ways of being an ancestor (there are two ways, correspond-
ing to two rules and no facts). Prolog then explores each node in turn: each of these is, reasonably enough,
called a sub-goal. If the sub-goal is a fact, there is nothing further to explore; otherwise it can expand into
further sub-goals that must, in turn, each be satisfied. In short, Prolog naturally constructs and then explores
a classical search tree. Thus we say that programming in Prolog is “programming by searching”. More
precisely, Prolog’s search is non-deterministic: it permits rules to have multiple definitions and searches
them all, looking for any—and, indeed, every—way to satisfy it.
Armed with this background, we can now delve into the pieces. To clarify the execution of Prolog, we
must provide an account of (at least) the following:
• How does Prolog search the space of relations?
• What exactly constitutes satisfaction?
307
308
CHAPTER 34. IMPLEMENTING PROLOG
• What are logic variables? How do logic variables take on a value, and how does this value change
over the course of a search?
• What causes computation to terminate?
34.1.1
Searching
In what order should Prolog search the tree? Both of the canonical answers make sense:
breadth-first search This has the benefit of never getting “stuck” in an infinite expansion exploring one
sub-goal while a different one is satisfiable and might have led to an answer. Unfortunately, it is also
rather expensive to maintain the queue necessary for breadth-first search.
depth-first search This has the disadvantage that it may get “stuck” exploring one non-satisfying disjunct
while another can satisfy the query. It has the advantage of executing relatively efficiency because it
corresponds well to a stack-based execution, which modern systems are tuned well to implement.
Though breadth-first search will therefore produce satisfying answers in situations when depth-first search
will not, Prolog chooses the latter, sacrificing some purity at the altar of efficiency.
Exercise 34.1.1 Write a Prolog program that would yield responses under a breadth-first order but that
fails to terminate in a traditional implementation.
Hint: Even when choosing depth-first search, a Prolog system has the choice of choosing sub-goals left-
to-right, right-to-left, etc. You can glean insight into the order chosen by the Prolog implementation you’re
using by examining the order in which it prints output for queries that have many satisfying answers.
Exercise 34.1.2 Rewrite your example from the previous exercise to retain as much of its structure as pos-
sible, but to provide as many answers as possible in the Prolog system you’re using. Discuss what you had
to change and its implications for programming by searching.
34.1.2
Satisfaction
The example we saw in Section 33.1 helps illustrate numerous concepts:
sibling(X,Y):-
advisor(X,Z),
advisor(Y,Z),
X \== Y.
Given the query
sibling(robinson,feferman}.
34.1. IMPLEMENTATION
309
we can pretend Prolog “binds” X to robinson and Y to feferman; this therefore appears to make two
“recursive calls” to advisor. However, these cannot be function invocations in the traditional sense,
because Z is not bound. In fact, Z is—as we have said—a logic variable.
Prolog searches every pair in the advisor relation to find values that it can associate with Z. None
of the facts about advisor yield a match, but we also have a rule relating advisor to advisee. This
spawns a fresh goal, trying to satisfy advisee(Z,robinson). This eventually finds a satisfying match,
with Z bound to tarski. Now that Prolog has a value of Z, it can proceed with the second clause (recall
that , should be read as “and”, so there is no point proceeding until the first clause has been satisfied).
Now we understand why logic variables are called variables: they change their value. Initially Z had no
value at all, whereas now it holds the value tarski. To satisfy the next goal, Prolog must therefore attempt
to satisfy advisor(feferman,tarski). This is, of course, a fact about advisor, so Prolog imme-
diately satisfies it. Now it proceeds to successfully discharge the inequality test, and return an affirmative
answer—that is, Robinson and Feferman are indeed academic siblings.
This account does not yet explain two things:
• How many times can a logic variable vary? Does it change its value just once (going from unbound
to bound), or does it change more than once?
• Why did we have to place the inequality test at the end of the rule?
To study these questions, let us consider the more general query,
sibling(mostowski,B).
Initially, X is bound to mostowski and Y to the logic variable B. This yields the sub-goal
advisor(mostowski,Z).
which e