Theory of Programming Languages/Logic Programming

This is a lesson in in the course, Theory of Programming Languages, which is a part of The School of Computer Science

Objective

In this lesson, students will learn about the how logic programming is unique among programming languages. This will involve learning the simple structure of commands in Prolog.

Students will be able to answer these questions:

What is logic programming, and how is it different than other programming paradigms?
What is the structure of a logical program?
How can programmers communicate with the computer to compute information?

Logic Programming

Logic Programming is fundamentally different from the other programming paradigms we've seen in previous lessons. Rather than giving commands to a computer, programmers state the relationships between objects. The computer can then consider these relationships and arrive at logical conclusions. Generally within a logic program there are two main sets of code - there are facts and rules. Rules are applied to facts to gain knowledge about the environment. Consider this example:

Fact: Rudy is a dog.
Rule: All dogs have teeth.

Query: Does Rudy have teeth?
Conclusion: Yes.

The rule "all dogs have teeth" can be applied to Rudy because there is a fact stating "Rudy is a dog". This example isn't written in any real syntax. Let's look at an example written in Prolog, one of the more well known logic programming languages:

female(alice).
male(bob).
male(clyde).
female(dora).

child_of(dora, clyde).
child_of(clyde, bob).
child_of(dora, alice).

father_of(F, P) :- male(F), child_of(P, F).

Were you able to read this program? Prolog is remarkably different than other languages. A section of code which resembles "female(alice)." is a fact. "father_of(F, P) :- male(F), child_of(P, F)." is a rule, ":-" can be read as "is true if". The capital letters signify a variable which can be applied to any object - so F could mean clyde, dora, alice, or bob. We can translate this code as:

alice is female.
bob is male.
clyde is male.
dora is female.

dora is the child of clyde.
clyde is the child of bob.
dora is the child of alice.

"F is the father of P" is true if F is male, and if P is the child of F.

What if we wanted to query this program to derive more knowledge? Let's try and find the father of bob:

?- father_of(bob, X).

The system will respond with the following answer:
X = clyde

We passed in a relationship where one of the values was a variable, Prolog applied different objects to this relationship until one was logically sound. The only parent of clyde was bob, and bob is male. This satisfied our rule "father_of(F, P) :- male(F), child_of(P, F).". When X is equal to "clyde" the logic is sound. We can pass in more general queries to Prolog which will cause the system to generate multiple results:

?- father_of(Father, Child).

Father = bob
Child = clyde ;

Father = clyde
Child = dora

As we have seen in these examples, logic programming does not need the information that alice or bob are people in order to derive knowledge about them - indeed, it need not even be told that there is a concept called person. In most non-logical programming languages, such concepts (or types) would have to be defined before one could write programs processing information about persons.

Assignments

Write a prolog program which uses these definitions: All animals have cells. If an animal is a bird it has a beak. If an animal is a mammal it has a mouth. If an animal is a fish it has fins.
Write queries we can make this program, and the results the system would produce.
Write two other programs which have at least 5 facts and 5 rules.
List three problems that are best solved by logical programming, and three problems ill suited for logical programming. How did you come to this conclusion?

Completion status: this resource is just getting off the ground. Please feel welcome to help!