Programming in Prolog

Early Preview – just wanted to post this to force myself to update it for Monday – pretty much complete, except for a few examples

This is not going to be a book review of the classic by Clocksin & Mellish (which the image at the left is from), but if you want a review: It’s a CLASSIC – if you’re interested in Prolog programming – BUY IT!

A recent post by Bob Marshall (@flowchainsensei) about Nonviolent Programming got me thinking… Most programming languages are Imperative, i.e. you tell the computer what to do. There is however another paradigm – Declarative, where you tell it what you want (need?). There is a subtle but significant difference here – I can say “I want to go to the shops” (which is a query) and if there are enough facts and rules (aka transformations) then the computer just gives me a result!

In case you think declarative programming is some theoretical concept from academia – it is. But it’s widely used, and probably by you unless you’ve been under a programming rock for the last 20+ years… Some examples? SQL, HTML, XML, XSLT and “configuration files” from frameworks such as Spring and J(2)EE. If you’re lucky and have used a rules engine, then you’ve been doing declarative programming with what is probably a subset of Prolog.

Overall, the above are restricted in their capabilities as they’re essentially domain specific languages, whereas Prolog is a fully generic language. So how do you “program” in Prolog, and what’s the difference between it and a declarative program? Let’s clarify this with an example – I want to work out what type of transport to get around – let’s start with going from home to the local shop.

I know the distance from my home to the shop, and that’s a fact:

distance(home, shop, 0.5).

furthermore, I know the range of various types of transport and they’re also facts:

range(walking, 0, 1).
range(car, 2, 100).
range(plane, 101, 10000).

Now, all I have to do is work out the best way to get from my place to the shop, which is a query where Prolog will try and solve for the unbound variable METHOD:

transport_method(home, shop, METHOD).

There’s only one thing missing now, and that’s the program! Well, it’s not really a program in Prolog, it’s actually a rule:

1: transport_method(FROM, TO, METHOD) :-
2:   distance(FROM, TO, DISTANCE),
3:   range(METHOD, MIN_DISTANCE, MAX_DISTANCE),
4:   DISTANCE >= MIN_DISTANCE, DISTANCE =< MAX_DISTANCE.

Which is pretty much common sense, i.e.

1: In order to get FROM one place TO another I need a METHOD
2: I'll need to know the DISTANCE
3: Each METHOD has a MIN & MAX DISTANCE it's best suited for
4: The DISTANCE I want to go is between those MIN & MAX DISTANCES

So if I run the query I get:

transport_method(home,shop,METHOD).
METHOD = walking
yes
done.

The interesting thing is that there were no “commands” I didn’t have to tell the computer how to do it step-by-step. All I had to do was tell it what I “knew” (in the form of facts and rules) and what I “needed” as a query.

Anyone who knows an Imperative language will know that to do this would require all sorts of arrays / lists / maps and some loops. I’m not going to illustrate what this would look like in Java, but it wouldn’t be pretty.

“Ah,” you may say “there must be a price!?” Of course there is, as there’s no such thing as free lack of code. The price is the fact that the query is being satisfied by an Inference Engine which gives us all sorts of advantages…

>>> to come – more queries & examples…

In the past, there have been some concerns with Prolog, the major one being performance. Given that most modern implementations only have an ~25% overhead over Imperative languages, does that argument really hold any more when we have so much bandwidth and memory? When the major cost to building software is people?

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s