New (To Me) Languages – Prolog

It’s been awhile since I’ve posted; part of the reason is that I’ve devoted some of my off hours to becoming more familiar with a couple of programming languages, Prolog and Haskell. However, the most of the reason is laziness.

I did start a post on what is wrong with the infrastructure of the web that turned into a rant. Turns out rants are draining to write and therefore it may remain unfinished. A post on my dual monitor setup is pending behind a clean desk, which should happen Any Day Now (wink).

Anyways, a few words about Prolog. (I was going to make one post with both Prolog and Haskell, but Prolog kinda grew out of control). I’m attempting to keep this fairly non-technical, let me know how I do.

Prolog

Prolog is a declarative logic language. In a nutshell, this means that it probably shares little in common with languages that you use at work or for play. Unless you use SQL, which I suppose is also a declarative logic language; however, the similarities pretty much end at the designation. The core concepts are quite different.

One axis used to classify programming languages is declarative v. procedural. The typical language is procedural. The programmer specifies the steps needed (a.k.a. an algorithm, or the ‘how’) to perform a particular computation (the ‘what’). In a declarative language, the programmer specifies the ‘what’ and the computer determines the ‘how’.

Prolog as a logic language makes heavy use of predicates (statements of fact in this context), horn clauses (if these N things are all true than it is implied that P is true), and backward chaining (can I prove P based on the predicates I know?).

Prolog’s core machinery is composed of non-determinism (or what is effectively non-determinism) and unification.

Non-determinism

Non-determinism is a funny word to attach to programming as it would seem to imply that things behave in a random way. However, what is meant is not random behavior, but that the steps needed to arrive at a result are not known ahead of time.

Imagine that you’re in a maze and presented with the choice to go left or right. Having never been in this maze before, you have no idea with choice will eventually lead to the end. Non-determinism proposes that since you cannot determine which choice to make, you make them both. So, you create a copy of your current universe, giving you two universes. In one universe you turn left and in the other you turn right. Repeating this process will eventually lead to a universe in which you make it out. By discarding all universes where you weren’t successful, you give the magical illusion of knowing the correct path all along.

Obviously, you can’t actually create copies of the universe, but you can fake it by hiring a scribe and suffering memory loss. The scribe keeps track of where you’ve been and where you’ve run into dead ends. The scribe will tell you which choice to make based on their record of previously unsuccessful choices. When you get out of the maze, the scribe presents to you the successful route. You assume that copies of the universe must have been made, because you can’t remember not making copies (I know it’s a stretch and also a double negative). However, the reality is that scribe guided the back tracking. The scribe in this analogy is Prolog.

Unification

If you have a two stacks of colored blocks, it’s easy to see if they match:

Stack 1: Red Green Blue Yellow
Stack 2: Red Green Blue Yellow

Stack 3: Red Green Yellow Blue
Stack 4: Red Green Blue Yellow

Obviously, stacks 1 & 2 match while stacks 3 & 4 don’t. If you were to add blank blocks that could assume any color, unification is the deductive process that you’d use to determine if the stacks could be made the same. If they can be made the same, unification produces the needed colors for the blank blocks. (No adding, subtracting, or rearranging of blocks is allowed.)

For example:

Stack 5: Blank Green Blue Blank
Stack 6: Blank Blank Blue Yellow

Stack 7: Red Blank Green
Stack 8: Blue Yellow Green

Stacks 5 & 6 can be unified by observing that the first blocks can be made any color as long as they are both the same color, that the second block of stack 6 must be green, and that the last block of stack 5 must be yellow.

Stacks 7 & 8 cannot be made the same, no matter what color is given to the blank block in stack 7. They cannot be unified.

Unification is pervasive in Prolog, used to assign values to variables (blank blocks) and to compose and decompose structures.

Quick and Dirty Example

At this point, I was initially tempted to walk through an example that illustrates how a non-determinism and unification are used in a program. After deciding that would be a bit too heavy, I decided to highlight how different Prolog is from a procedural language via an example, using lots of hand waving.

Consider a program that joins two lists. For example, the list [1,2] can be joined with [3,4] to form the list [1,2,3,4]. Waving my hands, I’ll claim that the procedural approach will involve iterating over (at least one of) the lists while constructing a ‘new’ list with all of the elements in order. (This is assuming that the list is represented as a singly linked list or an array.) The procedural program has one purpose and one capability, two lists in, one list out.

Here’s the Prolog version of the above:


join([],ListB,ListB).
join([Head|TailOfListA],ListB,[Head|TailOfListC]) :- join(TailOfListA,ListB,TailOfListC).

It can join two lists just like the procedural version:


?- join([1,2],[3,4],C).
C = [1, 2, 3, 4].

But, because of non-determinism and unification, this one two line program has additional abilities. And this is the magic of Prolog, as the above program can:

Tell you if a list is the result of joining two given lists:

?- join([1,2],[3,4],[1,2,3,4]).
true.


?- join([1,2],[3,4],[1,2,3]).
false.

Let you take a apart lists:

?- join([1,2],B,[1,2,3,4]).
B = [3, 4].


?- join(A,[3,4],[1,2,3,4]).
A = [1, 2]

And even tell you all of the different lists that can be joined to form a given list:

?- join(A,B,[1,2,3,4]).
A = [],
B = [1, 2, 3, 4] ;


A = [1],
B = [2, 3, 4] ;


A = [1, 2],
B = [3, 4] ;


A = [1, 2, 3],
B = [4] ;


A = [1, 2, 3, 4],
B = []

If you want to get underneath all of the hand waving, learnprolognow.org has a solid online book.

2 Comments

  1. Kevin Smith
    Posted February 3, 2010 at 10:29 pm | Permalink

    Great work professor. Are you adding this to your Programming Languages lesson plan? How about posting a more technical follow-up with a real life use for Prolog. That’s from the engineer in me.

    Obviously looking forward to the next lesson in Haskell.

  2. jachrispens
    Posted February 4, 2010 at 10:15 am | Permalink

    Prolog would’ve been a better language than Snobol!

    Real world uses… hmm… Even after spending a bit of time with it, I’m at the level where it still takes effort to read and write even fairly trivial things. Not yet saying, “I know, I’ll use Prolog!”.

    My motivation was to be able to understand the Java 1.6 class file byte code verification, which happens to be specified in Prolog. I haven’t yet returned to it to see if I can make sense of it after spending time with Prolog

Post a Comment

Your email is never shared.