Prolog Language

The Prolog programming language has a long history and a bright future. - taken from this good attempt at a home site (archived): http://web.archive.org/web/20011031081230/http://www.practical-applications.co.uk/Prolog/

Programming in HornClauses with a built-in unification algorithm. If you do it right, every program can run multiple ways. For example, code that multiplies 2 numbers to give a third will, if just given the third, provide all the factors. If traditional languages are like prose, Prolog is like poetry.

Prolog is the classical LogicProgrammingLanguage.

ObligatoryQuote?s

"It was invented by BobKowalski? in 1974 and implemented by AlainColmerauer? in 1973."

1972 - Alain Colmerauer designs the logic language Prolog. His goal is to create a language with the intelligence of a two year old. He proves he has reached his goal by showing a Prolog session that says "No." to every query. -- From A Brief, Incomplete, and Mostly Wrong History of Programming Languages - http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html

I've done some Prolog for school assignments. I suppose that I could learn to love it, but it is hard to get over what I felt was a deception. I was led to believe that you didn't have to care as much about the operational model of the language. I thought it was going to be more purely declarative.

Prolog is not completely declarative because you sometimes need to control the backtracking of the unification algorithm with the "cut" operator. More modern logic programming languages, such as MercuryLanguage [and DataLog], completely separate the unification algorithm from the program code, and so are [more] declarative.

But Mercury and other languages similar to it, such as OzLanguage (as seen in the MozartProgrammingSystem environment) and Godel are committed choice languages, because they curb Prolog-style backtracking and unification in order to provide parallelism and concurrency. They're certainly similar and share Prolog's influence, and are characteristic of logic-based languages in general, but they aren't Prolog in a classical sense (not that I'm implying anyone is saying that they are, I just wanted to add that to the discussion). -- DanMoniz

Excuse me! Although MercuryLanguage indeed has CommittedChoice? (a.k.a. DontCareNondeterminism?), which is used for concurrency, (amongst other things), it also has ordinary Prolog-style nondeterminism (sometimes known as DontKnowNondeterminism?) (of which BackTracking is one possible implementation technique). Regarding unification it is true that (currently) in MercuryLanguage one can't use variable-sharing, as in, e.g., DifferenceLists. This is due to not having a way to express sharing uninstantiated terms in the (statically checked) mode/inst language. -- StefanLjungstrand

See NonDeterministic

I used Prolog in a comparative languages course. The biggest program we did was a map-coloring one (color a map with only four colors so that no bordering items have the same color, given a mapping of things that border each other). I say biggest because we were given the most time with it. I started out like most people in my class trying to hack the language into letting me code a stinking algorithm to color a stinking map. Then I wrote a test function to check if the map was colored and, in a flash of prolog, realized that that was really all I needed to code.

[...] it is hard to get over what I felt was a deception.

I think this is what most people exposed to PrologLanguage remember strongly, the initial disappointment. It takes a lot of good experiences to overcome that feeling, and few ever get that chance. -- AndersBengtsson

Here's a taste of Prolog, for those who haven't used it. Using the code below, you can get Prolog to generate all bit strings of length 3:

 2 ?- bits(3,Bits).

 Bits = [0, 0, 0] ;
 Bits = [0, 0, 1] ;
 Bits = [0, 1, 0] ;
 Bits = [0, 1, 1] ;
 Bits = [1, 0, 0] ;
 Bits = [1, 0, 1] ;
 Bits = [1, 1, 0] ;
 Bits = [1, 1, 1] ;
 No

Here's the code:

 % Non-deterministically returns a string of N bits.
 %  bits(+N,?Bit_string)
 bits(0,[]).
 bits(N, [R | Rs]) :-
N > 0,
bit(R),
N1 is N - 1,
bits(N1,Rs).

 bit(0). bit(1).

Here is another example.

 bit(0). bit(1). 
 bits(X,Y,Z) :-     
bit(X),
bit(Y),
bit(Z),
write(X),
write(Y),
write(Z),
nl,
fail.

The predicate (something like a function, though it doesn't work like a function) bits is non-deterministic, and returns multiple answers. In this example, it generates all bit strings of length 3. This is a quick and dirty tool for combinatorial computing, and you can easily use it to generate bits strings as input to other functions. You can also use bits to check if a list is a bit string, e.g.:

  3 ?- bits(5,[1,0,1,1,1]).
  Yes

  4 ?- bits(5,[1,1,1,1,0,1]).
  No

But, and this is one of the frustrating parts of Prolog, this particular predicate doesn't work if the first parameter is a variable, e.g.

  5 ?-  bits(N,[1,1,1,1,0,1]).
  ERROR: Arguments are not sufficiently instantiated

This error refers to the line N > 0, which requires that N be instantiated. ConstraintLogicProgramming is a useful extension of LogicProgramming that partially solves this sort of problem.

If you would like to have the predicate also count the length of bit strings, add a second clause that checks for an uninstantiated variable, cuts choice point for the other recursive case, checks the first element of the list for being a bit, make a recursive call and increment the count as the stack unwinds. The new predicate would be,

 % Non-deterministically returns a string of N bits or returns the length of a bit string.
 %  bits(+N,?Bit_string)
 %  bits(?N,+Bit_string)
  bits(0,[]).
  bits(N, [R | Rs]) :-
var(N), !,
bit(R),
bits(N1, Rs),
N is N1 + 1.
  bits(N, [R | Rs]) :-
 N > 0,
bit(R),
N1 is N - 1,
bits(N1,Rs).
  bit(0). bit(1).

This modified version gives the expected,

  | ?-  bits(N,[1,1,1,1,0,1]).

  N = 6 ? ;

  no

with no dangling choice points. What may be less obvious is the result of bits(X,Y) in this modified version or even what modifications would allow it to generate all combinations of bits for increasing length lists.

An operational way to understand Prolog is to say that predicates are actually what ordinary people would call procedure calls.

Regrettably, this is insufficient. Using predicates procedurally is possible with judicious use of the cut operator, but to do that removes all the advantages of using PrologLanguage. Think of a predicate instead as a search string. PrologLanguage will then become something else for you, something a lot closer to poetry than to prose.

For this reason, PrologPrograms? are typically extremely short compared with their procedural equivalents. It's a common experience that 1,000 lines of COBOL -> 100 lines of C -> 10 lines of SmallTalk -> 1 line of PrologLanguage.

So why don't professional software developments use it more? Well, it's slower than most procedural languages, and it can be extremely difficult to maintain. The last time I saw it used on any large scale was code for pacemaker/defibrillators, where it was combined with TonyHoare's program correctness-proving techniques to reduce legal liabilities. In that problem domain you understand that a fatal error is really a fatal error.

Still ... perhaps PrologLanguage might be neat for AcceptanceTesting? -- PeterMerel

Perhaps the difficulty with using the PrologLanguage is that PrologProgrammers are good and hard to find. LogicProgramming is hard to fake and does not come easy to a mind used to procedural programming. Since PrologProgrammers tend to have a logical or philosophical disposition, they are often considered hard to manage and often are hard to replace. Many folks only recall the PrologLanguage as something they never really understood from some graduate course in SymbolicProgramming. Perhaps http://www.gnu.org/software/gprolog/ will encourage a wider audience to experiment with LogicProgramming in the open and comfortable environment of the bazaar. -- VicBancroft

I like PrologLanguage very much, others might like other languages. As a tool, any languages have the possibility to solve a particular problem, and if not, probably it is just a matter to wait for a future release powerful enough that shall solve its weaknesses. I would also say, that the use of a particular language is more related with the expertise, time available to learn alternative languages, economics, former source code available, ideas.... well you name it. There is little benefit in stating if a particular language is better than other, each one will eventually fall in its place. In my case, I am so used to think in prolog terms that I found difficult to learn a new/switch back to a procedural programming -- even though I�m really interested-. I would like to encourage those who do not feel comfortable with your actual choose, to try prolog. but please keep in mind that there are different flavors of prolog, choose wisely before you get hooked.

It would indeed be nice to combine the power of Prolog with a "normal" language such as C or C++. Many "trivial" problems in, say C, are non-trivial in Prolog and vice versa. A hybrid language merging the best of both worlds would indeed be very interesting. A reason why Prolog isn't used as much among commercial developers could simply be the fact that it's difficult to grasp, or at least more difficult than procedural and even OO languages. -- Lennart Frid�n

From the days of Borland TurboProlog? and TurboC (early 90s) it was relatively easy to call one from the other. Nowadays MSWindows languages can call each other using COM (DLLs), corba, or on unix (static or dynamic) libraries. For both also object methods can be packaged as WebServices so you could have a dynamic web application using C, Java or Perl as the main "glue" that calls Prolog functors behind the scenes for special processing. Same is true for other SymbolicProcessing languages like scheme ie JayScheme embeds scheme in Java you can architect a HybridApplication to use each language for what it's best at.

A good open source Prolog implementation is SWI-Prolog (both Windows and Unix, see http://www.swi-prolog.org/). It has the ability to make GUI front ends using xpce.

There is also a PocketPc port at http://www.rainer-keuchel.de/wince/swi-prolog.html

I have a collection of resources on Prolog -- syntax, semantics, glossary, predicates, examples, etc. at http://csci.csusb.edu/dick/samples/prolog.html

--RichardBotting

Eclipse Prolog meanwhile has gone open source and comes with various constraint solvers: http://www.sourceforge.net/projects/eclipse-clp

My idea is to make Prolog easier by using if-then-else clauses.

How would that work? Prolog has implicit flow control (apart from the cut operator, which is a wart).

 if(Condition, TrueClause?, FalseClause?) :-
Condition, !, TrueClause?;
!, FalseClause?)

- I think. I don't have an implementation installed at the moment to check it, though. --DorKleiman

Prolog already has an "if_then_" operator:

Condition -> TrueClause?; !, FalseClause?

--RichardBotting

Java:

 if (x == 1) {
y = 0;
 } else {
y = 1;
 }

 Alternatively:
y = (x == 1) ? 0 : 1;

Prolog:

 if(X, Y) :-
\+ var(X),
var(Y),
X is 1,% if this fails, prolog tries the next clause of if/2
Y is 0.

 if(X, Y) :-
\+ var(X),
var(Y),
Y is 0.

 ?- if(0, A).
 A = 1.

 ?- if(1, A).
 A = 0.

moral: Prolog CAN handle if-then-else clauses but not in the conventional sense. As DorKleiman says above, flow control is implicit and much of it is handled by the implementation.

This is can be even simpler in Prolog:

 if(1, 0).
 if(_, 1).

 ?- if(0, A).
 A = 1.

 ?- if(1, A).
 A = 0.

Of course, now the word 'if' is consumed for this purpose... a rather poor choice, seriously.

The prolog program above does not reflect the Java snippet, it would translate to

public int ifx(int x) { //for lack of a better name

return  (x == 1) ? 0 : 1;

}

The -> operator reflects the if-then-else more closely, and is, as stated above a short form for (condition, ! thenClause); !, elseClause.

By the way, a constraint language could express the same thing as x#=\=y (unequal), given appropriate domain definitions.

Prolog and RDF.

A lot of people have mentioned (both positively and negatively) the similarities between Prolog and RDF (ResourceDescriptionFramework) / SemanticWeb stuff. I'm wondering, if anyone is evolving either Prolog or some derivative to be a good Semantic Web language. My limited experience with Prolog suggests that the idea is interesting, but it feels a bit bogged down and brittle. For example, does a state-of-the-art logic programming language still have to use capitalization to make the difference between variables and tokens? -- PhilJones

The SML family (SmlLanguage) seems to get along with significant case. If you want to avoid collisions, the alternative is going to be to use some kind of sigil (yuck) as overlapping the namespaces would be really quite tricky and error-prone.

There is a built in symbol that is very similar to an If-Then statement - "Condition -> Action". To make it clearer: [If] Condition -> [Then] Action ; [Else] Action.

This comes from plain old logic, where -> means "implies", in the mathematical sense. x->y is equivalent to "if x, then y" or "y if x". I would imagine (not having used the language) that the prolog way of doing things doesn't fit the if/then/else paradigm, but more that the results of an implication would be further used in a program without the need for an explicit else. -JasonEspinosa

There is a related language PARLOG which is a concurrent logic programming language - see http://www.parlog.com/en/parlog.html

There is another Windows Prolog evolving at http://dobrev.com as Strawberry Prolog in Sofia, Bulgaria. StrawberryProlog?.

See NonDeterministic

CategoryProgrammingLanguage