Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
A Prolog Introduction for Hackers

By tkatchev in Technology
Thu Feb 26, 2004 at 05:03:23 PM EST
Tags: Software (all tags)
Software

Strange, but true: Prolog is, without a doubt, currently the simplest and the most straightforward programming language of all mainstream programming languages; however, the special interests of academia and inept teaching have given it a horrible, pariah-like reputation. (After all, you cannot write a PhD thesis explaining obvious, practical things.) This article aims to ameliorate the situation; to introduce the practical simplicity of Prolog to those that might normally sneer at what they consider a horrible, convoluted playing field of doctorate theory.


The Prolog approach

Prolog is, essentially, a query language for databases, like SQL. However, unlike SQL, which is a limited query language for relational databases, (tables of rows and columns, much like a spreadsheet) Prolog is a query language for matching complicated patterns against a database of simple facts.

Thus, all Prolog programs consist of three parts: a list of facts, a list of pattern matching rules (sometimes also called predicates in Prolog jargon) and a list of queries. (Also sometimes called goals in Prolog jargon.)

Prolog facts

Facts, in Prolog, are pre-defined patterns that get stored in Prolog's internal database, usually in a manner to make searching them more efficient.

There are, essentially, three types of values in Prolog:

  • Numbers.

    Ex: 1, -2, 0.5, -0.776.

  • Symbols, which are, for all intents and purposes, immutable strings of lower-case letters without special characters or spaces. (We'll explain why symbols must be lower-case later.)

    Ex: hello, world, this_is_a_symbol, atom3.

  • Linked lists of symbols or numbers. Lists are untyped.

    Ex: [hello, cruel, world], [1, 2, 3], [1, hello, 2, world], [].

Modern, practical Prolog implementations define many more useful datatypes; however, this is implementation-dependent and doesn't really matter as far as this article is concerned. Look up your Prolog implementation's manual if you are interested.

Facts, or pre-defined patterns, are written using the standard notation of functions or procedures in other programming languages. The symbol before the opening parenthesis is the pattern's name, with a list of comma-separated values inside the parentheses.

Ex: f(hello), greeting_message(hello, world), g([hello, world]), fac(3, 6).

Note that the following is illegal in Prolog: f(). Patterns without arguments are written without parentheses, like this: f.

Also note that pattern arguments can have any of Prolog's datatypes, thus symbol, number and list arguments are allowed.

Thus, to define a fact in Prolog, all you need to do is to write a Prolog program that lists pre-defined patterns with a period (full-stop) after each entry.

Example of a Prolog program that defines several facts:

hello.
world.

f(hello, world).
g([hello, world]).
standard_greeting([hello, world], 2).

This simple program inserts five pre-defined patterns into Prolog's internal database. (hello and world, two patterns without arguments; f(hello, world), a pattern f with two arguments; g([hello, world]), a pattern g with one argument, a list; and standard_greeting([hello, world], 2), a pattern standard_greeting with 2 arguments, a list and a number)

When several patterns are defined with the same name and the same number of arguments, Prolog will run through them, one after another in a top-to-down fashion, when trying to match them. (You can think of this as a short-circuited "OR" of pattern matching rules.)

Defining pattern-matching rules

Defining pattern-matching rules in Prolog is equally simple:

f(hello, world) :- g([hello, world]).

Whenever Prolog sees the special symbol :-, Prolog creates a new pattern-matching rule. The basic meaning of :- is very simple: to match whatever is to left of the :-, the part to the right must be matched. This allows to "decompose" complex patterns into smaller, more manageable ones.

To make the task practical, Prolog defines many operators that help us in the task of composing pattern-matching rules. Some of the more important and useful are:

  • ,: A comma denotes sequential matching of patterns; this is equivalent to a "short-circuited AND" in many imperative programming languages. (C's &&, for example.)

    Ex:f :- a, b, c.

    This means that to match the pattern f, we need to match, in order, patterns a, b and c.

  • ;: A semi-colon denotes choice; this is equivalent to a "short-circuited OR" in many imperative programming languages. (C's ||, for example.)

    Ex:f :- p; q; r.

    This means that to match the pattern f, either p must be matched, or, if Prolog fails to match p, try to match q; if matching q fails, finally try matching r.
    Note that the semi-colon is essentially equivalent to listing patterns on separate lines; thus,
    f :- (p; q).
    is equivalent to
    f :- p.
    f :- q.

  • ->: An arrow denotes a conditional pattern rule, in other words, an "if-then-else" rule.

    Ex:f :- (g -> h; i).

    This code means that Prolog first tries to match pattern g; if the pattern can be matched, try to match the pattern h. If g cannot be matched, try to match the pattern i.
    Note that the construct must be enclosed in parentheses, due to strangeness in Prolog's syntax rules.

  • \+: This is equivalent, in a sense, to the negation operator in many programming languages. (Like the C !.)

    Ex:f :- \+ g.

    This code means that the pattern f matches whenever the pattern g cannot be matched.

Variables

This is all very easy to understand, but is, unfortunately, useless in real-world applications. What we lack are variables. Variables in Prolog are symbols that begin with a capital letter; for example: Var, A, Q, MATCH_ME.

Whenever Prolog comes upon a variable, it starts searching in its internal database of facts and pattern-matching rules for a substitution such that substituting a value for the variable matches some fact.

A simple example will illustrate the concept better. Consider the following Prolog program:

i_know(hello).
i_know(world).

is_phrase(A, B) :- i_know(A), i_know(B).

is_greeting(A, B) :- is_phrase(A, B), A = hello.

This program defines two facts (i_know(hello) and i_know(world)) and two pattern-matching rules.

is_phrase(A, B) :- i_know(A), i_know(B). This rule, which is named is_phrase and which accepts two arguments, tries to find substitutions for the two variables it uses (A and B) such that the pattern on the right side of the :- matches against Prolog's internal fact database.

In this particular case, Prolog will find the following substitutions:

A=hello, B=hello
A=hello, B=world
A=world, B=world
A=world, B=hello

is_greeting(A, B) :- is_phrase(A, B), A = hello. Again, a pattern of two arguments. As before, Prolog will try to find substitutions for the two variables A and B such that the pattern rule matches.

The new concept here is the operator =. This operator is Prolog's equivalent of variable assignment.
P=Q means that Prolog will find substitutions for variables such that the two arbitrary patterns to the left and to the right of the = are exactly equal. Note that in this operator Prolog doesn't care whether or not the two patterns can be matched against its internal database; what matters is that the two patterns become equal after = finished its work. The = operator is commutative; thus, A=B and B=A mean the same thing. If such a substitution cannot be found, the = operator will fail to match. For example, hello=world will always fail to match.
Thus, after executing i_know(A)=i_know(foo) A will be substituted with foo even though i_know(foo) does not match against Prolog's internal database. (By the way, this procedure is often called unification in Prolog jargon; thus, A=hello means that A will be unified with hello.)

Finally, we can figure out what the pattern is_greeting(A, B) does. Here, Prolog searches for substitutions for A and B such that a match against the known facts is found.
Expanding all the pattern-matching rules, Prolog will find the following substitutions:

A=hello, B=hello
A=hello, B=world

As you can see, using just a few basic Prolog operators and Prolog's advanced search engine, we can build pattern-matching rules of arbitrary complexity. It is here that Prolog's power really shines though: Prolog allows to build very complicated matching rules very easily. Thus, Prolog is designed for use in applications where we have just a few very simple facts, but a lot of very complex search rules.

Contrast this with SQL, which has been designed for the opposite situation: a great amount of very complex data with very simple, very basic search rules.

Programming in Prolog

While the basic Prolog engine is enough to perform arbitrarily complex searches, it is not enough to use Prolog as a general-purpose programming language.

At the very least, what we miss is a way to do basic input/output, a way for handling arithmetic and a way for doing loops.
In true Prolog spirit, the designers of the language decided to not complicate the language with unnecessary constructs and unnecessary syntax, but instead to write simple, basic hacks that integrate very well with the basic Prolog query language. (Contrast this with Oracle's PL/SQL, for those that know it.)

Input and output in Prolog is done with special pattern rules that always match, and produce output or return input as a side effect. Since there are a great number of implementation-specific input and output functions, I will describe two of the most basic, to give the general idea. If you want to learn more, consult the manual of your Prolog implementation.

Outputting a value is very simple: the pattern-matching rule write(A) will output its argument. This pattern-matching rule always matches. For example, write_greeting(A, B) :- is_greeting(A, B), write(A), nl, write(B), nl. will output two words on the screen, provided that the two words are a greeting. (The nl pattern simply outputs a newline character.)

Basic input is equally simple: the pattern-matching rule read(A) will ask the user to input a value, using Prolog syntax, substitute the typed value for A and match successfully. For example, this simple pattern-matching rule of zero arguments will simply output whatever value the user typed: echo :- read(A), write(A), nl.

For arithmetic, Prolog uses a special operator called is. This operator is just like the = operator, except that on the right side must be an arithmetic expression, not a pattern. For example, A is B + 1 will substitute a value for A that is equal to B + 1. Due to the special syntax of the is command, it is not commutative. Thus, B + 1 is A will give an error. This means that there is always a variable to the left of the is.

Note, however, that the is operator is still nothing but a special pattern-matching rule; so, for example, A is A + 1 is an invalid expression that will likely give an error, since no number can be substituted such that the number becomes equal to itself incremented by one. If this makes little sense, try making some simple substitutions in your head: 5 is 5 + 1 violates the basic rules of arithmetic.

Loops in Prolog are very simple; like other well-known programming languages, looping is done by writing recursive pattern-matching rules.

An example: infinite_loop(A) :- write(A), nl, infinite_loop(A). This rule will run an infinite loop that prints its argument infinitely many times. Using recursive applications of pattern-matching rules, any looping construct can be expressed. Recursion is equivalent to looping, as any programmer of functional languages knows.

Prolog queries

Queries, or goals, are a way for the user to interact with Prolog's internal database and pattern-matching rules. Almost all Prolog implementations include an interactive shell where the user can type arbitrary patterns; Prolog then tries to match the given pattern, outputting whatever variable substitutions are needed to match the pattern. This provides an easy and powerful way to interact with Prolog in real-time, typing in search queries and getting back results immediately.

Note, however, that the majority of Prolog implementations do not allow defining new patterns interactively; a Prolog program must be written using a separate editor and loaded into the interactive Prolog shell.

Query syntax, like almost everything in Prolog, is elegantly simple. Here is an example of an interaction, based on the previously shown program:

Ciao-Prolog 1.9 #44: Mon Dec 30 16:47:15 2002
?- ensure_loaded('i:/ivan/foo.pl').

yes
?- f(hello).

yes
?- f(foo).

no
?- is_phrase(hello, world).

yes
?- is_phrase(hello, _).

yes
?- is_greeting(A, B).

A = hello,
B = hello ? ;

A = hello,
B = world ? ;

no
?- is_greeting(_, B).

B = hello ? ;

B = world ? ;

no
?- hello.

yes
?- foo.
{ERROR: user:foo/0 - undefined predicate}

no
?-

The ?- is the standard Prolog prompt; it means that the user is invited to type in a Prolog pattern, ending with a period, as all Prolog statements. Note, also, that Prolog returns either a yes or a no after each query; a yes means that Prolog was able to match the query against its internal database; a no means, respectively, that Prolog was unable to find a match. (Notice that trying to use an undefined pattern foo caused a Prolog error.) When Prolog encounters variables in the query (like A and B in this example) Prolog prompts us before returning each found value for the variable, one by one. Finally, there is a special variable called _, which means that we do not care about the values of this variable and do not want them printed.

An extended example

To solidify your understanding of the abstract underpinnings of Prolog, here are a few very simple programs in Prolog. (In Prolog, the % character denotes comments.)

Calculating the factorial:

% fac(N,R) : R is the factorial of N.

fac(0,1).
fac(N,R) :- P is N-1, fac(P,Q), R is N*Q.

Using this pattern is simple: typing the query fac(5,R)., for example, gives the result: R = 120. When playing around a little, though, many deficiencies start becoming apparent, including unwanted infinite loops and the fact that fac(N,120) doesn't give the expected result. The reason for this is the fact that Prolog is very ill-suited for numerical computation; arithmetic in Prolog is a hack, and doesn't integrate well into the Prolog search engine too well.

Addendum: Here is a tail-recursive version of the factorial pattern.

% fac2(N,A,R) : R is the factorial of N; A is the "accumulator" value.

fac2(0,R,R).
fac2(N,Acc,R) :- P is N-1, Q is N*Acc, fac2(P,Q,R).

Usage: fac2(5,1,R).

Reversing a list:

% cat(A, B, C) : C is the concatenation of lists A and B.

cat([], R, R).
cat([H|T1], Z, [H|T2]) :- cat(T1, Z, T2).

% rev(A, B) : B is the list A when reversed.

rev([], []).
rev([H|T], Q) :- rev(T,P), cat(P,[H],Q).

(Here we first encounter the special Prolog syntax for handling lists; the special system pattern [H|T] matches any list whose first element is H with T being the rest of the list without the first element.)
Using this pattern is simple: rev([1, 2, 3],R). In other words, find all such R that rev([1, 2, 3],R) matches the Prolog pattern-match rule database. Notice, however, that rev(R,[1,2,3]) gives us the same result! This is obvious if you think a little bit about the nature of Prolog's pattern-matching engine.

As an example, here is a second, simpler version of rev that doesn't rely on concatenating lists:

% rev2(A, B, C) : C is the reversal of the list A, C is the "accumulator"
% for growing lists.

rev2([], R, R).
rev2([H|T], Z, R) :- rev2(T, [H|Z], R).

Here, the second parameter of the pattern-matching rule is used as an "accumulator" for holding intermediate values. Using this rule is simple: rev2([1, 2, 3], [], R). Look at how smart the Prolog pattern-matching is when it processes lists and other symbolic data: not only does rev2(A, [], [1, 2, 3]) produce the expected results, but rev2([1, 2, 3], B, [3, 2, 1]) produces B = [], and rev2([1, 2, 3], A, [3, 2]) returns us a pattern-match failure.

Addendum

Wait one second, Prolog is a logic-based language!

No, it is not. Prolog has several system patterns that were (very) loosely inspired by formal logic; these were designed to ease the use of Prolog for those people that are already familiar with formal logic. However, if you persist with your delusion that Prolog is a language for "handling logic predicates", you will get bitten sooner or later! (And probably sooner than later.)

Standard Prolog

Prolog is a very established, industrial-strength, popular language. As such, there is a very clear and formal ISO standard for Prolog interpreters and compilers. You can view the standard for ISO Prolog here, for example.

Strange language

Prolog programmers and implementors simply love using non-standard, confusing and sometimes plain wrong language. Do not be afraid of this peculiar trait; when encountering strange or confusing terms, be aware that 90% of the time a very simple and down-to-earth concept is hiding behind it.

The "cut" operator

The so-called "cut" operator (written as !) is a pre-defined operator in Prolog that allows the programmer to subtly tweak the search strategy used by the Prolog matching engine; while this operator allows some neat programming tricks and optimisation techniques, I do not advise anyone ever to use this operator. It is a dirty, very confusing and dangerous hack that will inevitably make your program impossible to read and introduce subtle bugs. In short, avoid the "cut" like the plague.

Open-Source Prolog

Prolog is a programming language with a great deal of choice as far as implementations are concerned; there are lots and lots of good, high-quality implementations of Prolog that are Open-Source.

Try it yourself

You can try interacting with a Prolog shell without installing a Prolog implementation here. (The link points to tuProlog, an Open-Source Prolog written on top of the JVM and embeddable into standard Java applications.)

For fun

Just in case you are wondering how Prolog can be used in the "real world", take a look at this simple rouguelike game written entirely in Prolog: Caves of Golorp.

Though of course, Prolog is very useful for non-toy applications as well. Browsing through the site of any commercial Prolog vendor, (and there are lots of them) you will inevitably stumble upon a page listing many serious, industrial-grade applications in Prolog.

Warning to Americans

Prolog is decidedly a European language; not only was it originally invented by a Frenchman, the majority of Prolog implementations are developed and used in Europe; and even in a purely academic setting, Prolog is much more popular as a teaching language in European universities when compared to higher education in the U.S.

Despite this, do not be afraid; Prolog is a very useful tool in its own right. Good luck.

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Poll
Programming Language:
o C 9%
o C++ 9%
o Lisp-derivative. 12%
o Pascal-derivative. 3%
o Java 14%
o .NET 3%
o Prolog 1%
o ML-derivative. 5%
o Python 17%
o Perl 9%
o Something "visual". 1%
o Other, procedural. 4%
o Other, functional. 2%
o Other. 2%
o No reply. 1%

Votes: 219
Results | Other Polls

Related Links
o here
o here [2]
o tuProlog
o Caves of Golorp
o and there are lots of them
o Also by tkatchev


Display: Sort:
A Prolog Introduction for Hackers | 127 comments (96 topical, 31 editorial, 5 hidden)
General purpose? (2.00 / 5) (#13)
by jongleur on Wed Feb 25, 2004 at 04:27:06 PM EST

Prolog lacks functions.  I haven't tried to do too much normal programming with Prolog but, it seems to me that some other language like mercury or some other language might make normal programming that much easier (but I'm guessing).  

Also, I found that Prolog lacks good string handling - I wanted to do something like sprintf once; there is the nice format, but it only works with streams.  So, I ended up format()ing to file and reading it into a string.  So, I'm not convinced it truly is general-purpose.
--
"If you can't imagine a better way let silence bury you" - Midnight Oil

Of course. (2.33 / 6) (#15)
by tkatchev on Wed Feb 25, 2004 at 04:54:48 PM EST

Prolog is nothing more than a fancy database search engine.

(Imagine an SQL implmentation where queries can modify themselves on the fly; this is the idea behind Prolog, except that Prolog is much simpler than SQL.)

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

SQL vs. Prolog (none / 2) (#37)
by bob6 on Thu Feb 26, 2004 at 07:29:01 AM EST

The other main difference is that Prolog is a complete language, whereas some things are just impossible to express in SQL.

Cheers.
[ Parent ]
Yes. (none / 2) (#43)
by tkatchev on Thu Feb 26, 2004 at 11:38:56 AM EST

Loops, for example. You cannot write an infinite loop using pure SQL.

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

Mercury (none / 2) (#38)
by bob6 on Thu Feb 26, 2004 at 07:51:10 AM EST

It's a WOW! language: very expressive, very smart compiler. Unfortunately the syntax is actually awful and it lacks an interpreter (there's only a compier). I was willing to find some spare time (that was funny) to try out Curry, an extension to Haskell where functions can be non-deterministic. There are also other marginal logic functional languages like Oz or Relfun...
Otherwise, you may write a functional preprocessor to the prolog comiler in order to simulate functions... It is a good classic Prolog exercise.

Cheers.
[ Parent ]
You can hack it (none / 1) (#49)
by duffbeer703 on Thu Feb 26, 2004 at 02:14:58 PM EST

You can do lots of unconventional stuff...I know of people who use oracle as a backend for prolog rule engines.

It's pretty arcane stuff, but you could certainly shoehorn a perl interpreter or regex engine into prolog.

[ Parent ]

DB Backend (none / 0) (#87)
by bob6 on Fri Feb 27, 2004 at 05:33:37 AM EST

It's pretty straightforward to write a Prolog2SQL program in Prolog. You just have to assign a predicate to each table and a position in the predicate argument list to each field (or column). Et voilą.
It's bit trickier (not that hard, though) if you want it to generate SQL with joins.

Cheers.
[ Parent ]
A Frenchman? (2.94 / 18) (#14)
by it certainly is on Wed Feb 25, 2004 at 04:39:16 PM EST

I thought it was invented at Edinburgh University.

I like your article a lot, but you seem to have picked examples that aren't exactly meaningful. Yes, it is a query-based pattern matching language, but that's not very helpful itself. Something more lucid and classical, like:

male(kevin). % kevin is male
female(jane).% jane is female
male(bob).
female(lisa).

parent(lisa, jane). % lisa is parent of jane
parent(lisa, kevin).
parent(bob, jane).
parent(bob, kevin).

father(X,Y) :- male(X), parent(X, Y). % X is the father of Y if X is male and X is the parent of Y
mother(X,Y) :- female(X), parent(X, Y).
son(X,Y) :- male(X), parent(Y, X).
daughter(X,Y) :- female(X), parent(Y, X).
sibling(X,Y) :- parent(Z, X), parent(Z, Y).
sister(X,Y) :- female(X), sibling(X, Y).
brother(X,Y) :- male(X), sibling(X, Y).
You see what I'm getting at? Various orders of "hello" and "world" are no way to teach abstract concepts.

kur0shin.org -- it certainly is

Godwin's law [...] is impossible to violate except with an infinitely long thread that doesn't mention nazis.

Origins of Prolog (2.60 / 5) (#16)
by tkatchev on Wed Feb 25, 2004 at 05:00:28 PM EST

See here, for example.


   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

It was invented by an academic.... (1.25 / 3) (#61)
by Beechmere on Thu Feb 26, 2004 at 07:35:38 PM EST

I'm fairly sure Prolog was invented by a self-serving academic in the 1970s, better known for his obscure philosophical theories than his ability to pass on useful IT knowledge. I won't mention his name for fear of defamation. Prolog is a truly useless language with no practical applications whatsoever. Its only purpose seems to be to waste the time of students when they could be learning more useful languages like COBOL, C, Visual Basic, Java, Assembler, etc.

[ Parent ]
Whatever, you meaningless cog. [n/t] (none / 2) (#64)
by it certainly is on Thu Feb 26, 2004 at 07:40:53 PM EST



kur0shin.org -- it certainly is

Godwin's law [...] is impossible to violate except with an infinitely long thread that doesn't mention nazis.
[ Parent ]

My favourite Prolog joke (2.89 / 28) (#21)
by stuaart on Wed Feb 25, 2004 at 08:15:47 PM EST

Q: How many Prolog programmers does it take to screw in a lightbulb?
A: no

Linkwhore: [Hidden stories.] Baldrtainment: Corporate concubines and Baldrson: An Introspective


My thoughts on Prolog (2.62 / 8) (#24)
by stuaart on Wed Feb 25, 2004 at 08:29:14 PM EST

I would like to add my admittedly uninformed account of my brief experience of Prolog (feel free to point out my misunderstandings in this rant):

I have developed a distinct hatred for the programming language known as Prolog. Prolog stands for (Programming Logic); code written in the language consists of lines of predicates (or clauses) which are then queried by the interpreter. It is this interpreter that finds solutions to the predicates, that is in Prolog-speak, it satisfies the goals generated by the code.

As one might guess, this makes for obfuscated, foul code that is declarative in a truly hideous way (cf. the functional language Haskell which is declarative and lovely). Whilst I like the declarative ideals and the way of thinking involved with such methods, I can't help but feel that the designers of Prolog intentionally chose the most non-standard syntax for the language as they could muster.

Perhaps the most unforgivable bit of syntax is the "cut" (indicated with a "!" character). The cut basically bodges procedural methods into an otherwise ok implementation. When the cut is used, the programmer intends to instruct the interpreter to cease its "backtracking" (the depth first search algorithm that finds the various solutions), and thus renders the code deterministic, successfully ruining the whole concept of "programming in logic".

And there's more. Stupid design choices about what should be an inbuilt procedure and what shouldn't abound. For instance, Prolog has a special inbuilt method of creating a predicate from a list (the "=.." operator):


F =.. [function, arg1, arg2].

gives:

F = function(arg1, arg2).

This kind of operator is very useful if you're reading something from a file (e.g. some kind of command database), but exactly why other essential operators have been excluded from the basic language is beyond me (such as an operator to append lists - Prolog is based on lists!).

And if that weren't dumb enough, the system for deciding what is a variable and what is a constant is merely based on whether the first letter of said text is capitalised or not! This results in hard-to-read lines of code like:


function(Variable, constant, variable, Constant).

Without syntax highlighting, you're screwed, to put it bluntly.

I sincerely hope that Prolog is consigned to language hell where it shall burn for all eternity for its inherent design flaws.

Linkwhore: [Hidden stories.] Baldrtainment: Corporate concubines and Baldrson: An Introspective


Consider Mercury (none / 2) (#45)
by discoflamingo13 on Thu Feb 26, 2004 at 01:05:55 PM EST

Mercury seeks to overcome many of the limitations and kludges of Prolog. Just FYI.

The more I watch, the more I learn ---
If you set yourself on fire, the world will pay to watch you burn.
--- Course of Empire

[ Parent ]
Appending Lists (none / 0) (#118)
by robmyers on Mon Mar 01, 2004 at 01:10:02 PM EST

[] appends items to lists. And you can concatenate lists with the standard library. You can't destructively update lists because that isn't how Prolog works. If you want destructive updating, you haven't learnt the language properly.

[ Parent ]
anyone make prolog persistent yet? (3.00 / 4) (#26)
by khallow on Thu Feb 26, 2004 at 01:32:16 AM EST

As I recall, that was the prime obstacle to using prolog in a project I worked on once. If we had to restart the system, then the embedded prolog matching engine had to be fed the data from the start. We were looking at a lot of data (on the order of a few megabytes to hundreds of megabytes) that would have to be reloaded from scratch.

Stating the obvious since 1969.

Ciao has it I believe (none / 3) (#29)
by jongleur on Thu Feb 26, 2004 at 02:08:41 AM EST

Ciao Prolog

But there are a million prologs all messing with all kinds of features - shouldn't be hard to find one.

--
"If you can't imagine a better way let silence bury you" - Midnight Oil
[ Parent ]

I agree. (none / 2) (#33)
by tkatchev on Thu Feb 26, 2004 at 04:43:01 AM EST

The next standard needs to do something about this problem.

Basically, there is still this 1970's view that anything can be stored as a plain-text "config file". Obviously, for real projets this is not always true.


   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

There is a Java Prolog, XProlog... (none / 2) (#39)
by claes on Thu Feb 26, 2004 at 08:48:08 AM EST

out there somewhere. The knowledge base is just a hash table so you could serialize it or (gaak) xml-ize it and persist it.

Some prologs are hooked up to databases so the rows in the database work like rules. (I've never used that feature).

-- claes

[ Parent ]

Yup (none / 2) (#48)
by duffbeer703 on Thu Feb 26, 2004 at 02:11:18 PM EST

The IBM/Tivoli Enterprise Console uses prolog as a rule engine to correlate events.

I know that a guy named I.V. Blankenship who a popular contributor to the tivoli listserv managed to figure out how to call link apps from external libraries into prolog predicates.

He gave a presentation about it a year or two ago...

Try googling for "tec and blankenship" or "tivoli iv blankenship" and you should be able to find it. Otherwise try searching the Tivoli listserv archive http://tme10.uio.no

[ Parent ]

Prolog can suck (2.75 / 4) (#28)
by falsedan on Thu Feb 26, 2004 at 01:59:04 AM EST

..but so can any language. I was taught declarative programming by a Russian researcher. The course certainly had room for improvement, but I don't think Prolog sucks.

I can't beleive you're disparaging 'cut'! It's so useful, and is essential in preventing inefficient backtracking. It can also be hard to understand, but that doesn't mean it's bad.



PROLOG:SQL::ALGOL:FORTRAN (none / 2) (#34)
by Lode Runner on Thu Feb 26, 2004 at 05:18:52 AM EST

nuff said

+1 Just what I need... (none / 2) (#35)
by melia on Thu Feb 26, 2004 at 06:54:48 AM EST

I looked (briefly) for a prolog tutorial the other day and didn't find many. I need one. Cheers.
Disclaimer: All of the above is probably wrong
Talk about RDF! (2.60 / 5) (#46)
by snowlion on Thu Feb 26, 2004 at 01:28:37 PM EST

I'm voting +1 FP. When I saw the title, I thought, "How timely!"

RDF is basically Prolog assertions. The idea is that we're going to put these assertions all over the web, and network them together, and use something like Prolog to get our computers to reason about stuff.

This is so important right now, that an article on Prolog is the perfect thing.

The only thing is: Nobody's mentioned RDF here!

So, if you get voted out: Rewrite it in terms of how this helps us explain RDF and what's happening on the web right now. Take some tripples from web RDF explanations, rewrite them as prolog assertions, and then have a prolog program make some conclusions.

Then, people will say, "Oh! I see! Now I understand what RDF will do for me!"

--
Map Your Thoughts

Go for it - what's RDF? nt (none / 1) (#50)
by jongleur on Thu Feb 26, 2004 at 02:52:29 PM EST


--
"If you can't imagine a better way let silence bury you" - Midnight Oil
[ Parent ]
snowlion, 'mapping your thoughts' (none / 2) (#52)
by jongleur on Thu Feb 26, 2004 at 03:50:38 PM EST

Have you tried a wiki as a first approximation to your idea?  By the way I haven't read it all but man, it looks exciting.  A wiki does decently for me, though once it grows to a certain size it gets unwieldy.  And, it sorely needs a way to represent different types of links.  

But your ideas look great - too bad I'm so lazy.  I really do love the wiki, so, I wonder, if yours were better, whether there could be money in it.  Really.  Or open-source fame at least..  

--
"If you can't imagine a better way let silence bury you" - Midnight Oil
[ Parent ]

I dig wiki Deep. (none / 1) (#97)
by snowlion on Fri Feb 27, 2004 at 01:00:01 PM EST

If you see my blog, you'll see that most of my recent activity has centered on Wiki.

I run a bunch of wiki, but my main activity occurs on CommunityWiki.

My primary issue right now is proliferating wiki. Wiki, and wiki-like technologies, are going to rock the world.

AS FOR my notebook system- I have a new system, that is MUCH simpler, and much better. Not nearly as complicated. The system I documented in that book has a number of flaws. I intend to make a wiki on notebook systems, and document my new system there.

E-mail me if you are interested in working on wiki, or working on notebook systems. I can find your interest, and put you into loops.

No, there isn't money in wiki. At least, I don't think there is. The primary value in wiki, it seems to me, is making things cost far less, and riding the public. There is ''zero'' scarcity here, but ''a lot'' of fun.

--
Map Your Thoughts
[ Parent ]

To my shame... (none / 1) (#55)
by tkatchev on Thu Feb 26, 2004 at 04:09:36 PM EST

...I don't know what RDF is.

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

It's the little button at the bottom of the page, (none / 0) (#63)
by it certainly is on Thu Feb 26, 2004 at 07:38:48 PM EST

the blue one with "XML" in white letters. That's RDF, unless snowlion has stopped studying neurotic, insular web-wankery and has moved on to Radio Direction Finding.

kur0shin.org -- it certainly is

Godwin's law [...] is impossible to violate except with an infinitely long thread that doesn't mention nazis.
[ Parent ]

Close, but not quite. (none / 1) (#99)
by snowlion on Fri Feb 27, 2004 at 01:18:45 PM EST

While K5's RSS feed is in RDF, RSS is not RDF.

You can express a lot of things in RDF. For example, you can describe yourself with RDF, as well. To see what the results are like, you can see mine.

Some people's comment blogs now allow you to just point to your friend-of-a-friend RDF file, rather than typing in your name, email, and homepage URL. I haven't seen it, but they should be able to download your depiction, and place it next to your comment as well; All based on info contained in the RDF file.

What's really cool about RDF, is not the syntax (which is ugly,) but that it's a standard graph-based system for giving Prolog-like assertions. Like XML, this is "no big deal-" it's technically trivial. But also like XML, it's a "big deal," in that it's a standard, and there is wide buy-in, and everyone's going to be implementing things with it, for all languages.

Read up on FOAF, if you want to see the kind of thing this is for.

Web wankery. It's good for you. :)
--
Map Your Thoughts
[ Parent ]

Holey Moley... (RDF) (none / 0) (#98)
by snowlion on Fri Feb 27, 2004 at 01:01:42 PM EST

Okay, well, this is easily cured.

You've got google. You know how to use it. :)

Go to!

If you like Prolog, RDF is going to blow your mind.

Just imagine hoards of prolog assertions, scattered all over the globe. That'll get you started. :)
--
Map Your Thoughts
[ Parent ]

Yeah, yeah, I know. (none / 0) (#103)
by tkatchev on Fri Feb 27, 2004 at 06:46:35 PM EST

It's so wordy and confusing, though. Reminds me of COBOL for some reason.

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

Write in: (2.25 / 4) (#53)
by guyjin on Thu Feb 26, 2004 at 03:52:21 PM EST

Forth. I picked "other" because Forth isn't really procedural or functional.
-- 散弾銃でおうがいして ください
anything beside the sun prom (none / 0) (#59)
by asad on Thu Feb 26, 2004 at 05:42:16 PM EST

use forth ?

[ Parent ]
FreeBSD scripts (none / 0) (#90)
by MyDyingDuck on Fri Feb 27, 2004 at 09:11:56 AM EST

In the /boot directory of FreeBSD there's several Forth scripts.
--
They're seeding the clouds today.
Watch nothing's gonna go your way.

[ Parent ]
There's this cool microcontroller (none / 0) (#104)
by zrail on Fri Feb 27, 2004 at 07:20:12 PM EST

called the IsoPod (www.newmicros.com) that uses a resident version of Forth that they call IsoMax for programming. They also have versions of SmallC and pure assembler for it, but Forth is way cooler. They also have about five different versions of the board for different applications. Very cool stuff.

[ Parent ]
Not another buffer overflow language please! NT (none / 0) (#126)
by Anonymous Hiro on Wed Mar 17, 2004 at 12:02:13 PM EST



[ Parent ]
mutli-lingual compilers (none / 2) (#58)
by cronian on Thu Feb 26, 2004 at 05:26:37 PM EST

I think compilers should support multiple programming languages in the same block of code. The code should then be automatically convertible between programming languages. Then, when you debug if something looks confusing you could convert it to a different programming language, and it would make more sense. Also, you could code inefficiently in one language, and then hit the convert, and code make it more efficent.

We perfect it; Congress kills it; They make it; We Import it; It must be anti-Americanism
Compiling is lossy... (none / 0) (#65)
by claes on Thu Feb 26, 2004 at 07:49:16 PM EST

So you really can't go backwards.

Plus, with prolog, you're talking about an interpreter.

wait, is this a troll.

[ Parent ]

good compiler (none / 0) (#68)
by cronian on Thu Feb 26, 2004 at 08:30:47 PM EST

I'm not sure you would need to go backwords too much. The comiler would save the old code, and somehow reintegrate it, when you converted back. At least the variable would be able to remain basically the same. The AI might be a bit difficult, but, although the halting may be formally undecidable, I think it should at least be conceivable. Is there any reason prolog couldn't be made into a compiler, or C couldn't be run with an interpreter? Some of the code could even compiled, with other parts interpreted.

The whole point of a compiler is that you can code in a language other than binary. So, I ask why be so limiting that you only have one language? Why not allow multiple languages?

We perfect it; Congress kills it; They make it; We Import it; It must be anti-Americanism
[ Parent ]
Prolog is usually compiled. (none / 0) (#78)
by tkatchev on Fri Feb 27, 2004 at 03:36:20 AM EST

Prolog is simple enough that writing a compiler is trivial. (Though compiled Prolog usually doesn't run much faster than interpreted Prolog.)

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

Will probably not work with Prolog (none / 1) (#85)
by Highlander on Fri Feb 27, 2004 at 04:52:32 AM EST

This will probably not work with Prolog, since Prolog actually will do a lot more than a normal programmming language does: Prolog searches the facts and rules backwards and forwards for a match.

Expressing something done in Prolog looking arcane would probably still look arcane in the matching C code.

Moderation in moderation is a good thing.
[ Parent ]

You forgot to mention: (none / 2) (#60)
by i on Thu Feb 26, 2004 at 06:39:26 PM EST

Prolog has no logical negation. Not without the cut anyway.

and we have a contradicton according to our assumptions and the factor theorem

No kidding. (none / 1) (#79)
by tkatchev on Fri Feb 27, 2004 at 03:37:00 AM EST

That's because Prolog isn't designed for handling formal logic. It's a fancy pattern matching engine, nothing more.

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

Logical negation (none / 1) (#102)
by Pseudonym on Fri Feb 27, 2004 at 06:08:02 PM EST

The cut actually makes things less logical.

What you actually need for logical negation is a guarantee that all variables used inside under the "not" will not be further instantiated. This, for example, is unsound:

foo :- \+ (X = 2), X = 3.

This, however, is safe:

foo :- X = 3, \+ (X = 2).

There are several attempts "out there" to fix this. NU-Prolog, for example, suspends the negation until X is ground. Mercury, on the other hand, has strong checked modes (analogous to strong types) so the compiler can reorder this conjunction at compile time.


sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
[ Parent ]
The problem is, its not procedural enough. (none / 0) (#62)
by Phillip Asheo on Thu Feb 26, 2004 at 07:36:32 PM EST

Most people try to solve problems in a step by step "do this and then do that" style. The declarative approach of the prolog gurus is alien to joe sixpack.

Combine this fact with the fact that to solve any real-world problems in prolog involves interfacing with third party C and C++ libraries in a non-declarative fashion, is it any wonder that most programming gurus (Kent Beck for example) recommend Smalltalk-80 ?

--
"Never say what you can grunt. Never grunt what you can wink. Never wink what you can nod, never nod what you can shrug, and don't shrug when it ain't necessary"
-Earl Long

Hey, it's my favorite consultant! (none / 2) (#67)
by it certainly is on Thu Feb 26, 2004 at 08:22:52 PM EST

Rob Enderle, you are my favourite consultant. Whenever you have anything to say about technology, the world takes notice. I wish all people were as well-informed as you.

kur0shin.org -- it certainly is

Godwin's law [...] is impossible to violate except with an infinitely long thread that doesn't mention nazis.
[ Parent ]

"joe sixpack"? (none / 0) (#124)
by fizbin on Fri Mar 05, 2004 at 10:53:43 AM EST

Most people try to solve problems in a step by step "do this and then do that" style. The declarative approach of the prolog gurus is alien to joe sixpack.
Most programmers I know try to solve things step by step in a "do this and then do that" style. Most non-programmers try to solve things by telling people who can solve them what they want done. When they give procedural-style directions, they're micromanaging.

Seriously, though, I think that most instructions given to someone use the procedural style overall, and the declarative style for the small stuff. (e.g. you might tell someone "stack the wood into those two pickups over there, and make sure that the piles are even. Then go get Joe - Bob will know what hole he's working in - and have him drive one pickup with you following out to where they're building that new home, and help the guys there unload the wood.") Also, declarative style instructions are often given as a supplement to procedural style instructions, specifying global constraints. ("As you carry the water from here to there, be careful never to touch this blue thing, because it gets very, very hot" or "As you change the baby's diaper, try to keep some small pressure on her chest - say, with a small beanie-baby - to keep her from freaking out")

This would seem to point to a multi-paradigm language as the way to go; say, Oz or a standard procedural language with a small inference engine implemented to take care of specific parts of the program. (Such as amb shown in Teach Yourself Scheme in Fixnum Days)



[ Parent ]
small world (none / 2) (#66)
by gdanjo on Thu Feb 26, 2004 at 08:14:48 PM EST

The so-called "cut" operator (written as !) is a pre-defined operator in Prolog that allows the programmer to subtly tweak the search strategy used by the Prolog matching engine; while this operator allows some neat programming tricks and optimisation techniques, I do not advise anyone ever to use this operator. It is a dirty, very confusing and dangerous hack that will inevitably make your program impossible to read and introduce subtle bugs. In short, avoid the "cut" like the plague.
Heh. I was taught Prolog at University of Canberra by a guy who wrote a book on Prolog - T. Van Lee? The book was called "Techniques in Prolog Programming." I may be wrong, but the thrust of the book seemed to indicate that it was "introducing" the cut operator, and I always thought that it was Van Lee himself that "invented" it due to the book's main thesis and that he liked it so.

Anyway, I think your suggestion to "avoid it like the plague" will likely have the opposite effect - the curious mind (the most likely to take up Prolog) will inevitable want to know why one should avoid it. My suggestion would be "learn it, know it, live it, and if you're still not convinced that you should avoid it, you don't yet understand it." Reverse psychology, if you will :-).

My memory of the cut was the opposite to your experience - I found it to be interesting and useful, though I can imagine how it may wreak havoc for long-term Prolog-ers, especially wrt maintenance.

Dan ...
"Death - oh! fair and `guiling copesmate Death!
Be not a malais'd beggar; claim this bloody jester!"
-ToT

The purpose of prolog? (none / 0) (#69)
by Julian Morrison on Thu Feb 26, 2004 at 09:01:10 PM EST

What's it for? Besides academia, that is, and proving the point. Do people write real commercial programs in it?

Real commercial programs? (none / 1) (#73)
by it certainly is on Thu Feb 26, 2004 at 11:03:12 PM EST

Why not? People certainly can't write them in Perl.

kur0shin.org -- it certainly is

Godwin's law [...] is impossible to violate except with an infinitely long thread that doesn't mention nazis.
[ Parent ]

Yes (none / 2) (#84)
by wastl on Fri Feb 27, 2004 at 04:11:17 AM EST

Prolog is e.g. heavily used in expert systems (e.g. for diagnosis in medicine or for broken cars), scheduling problems (e.g. generating timetables) and theorem provers (admittedly, this is a rather academic application) and has long been used as a tool for creating prototypes that are implemented in other languages later.

An exercise that I find very interesting and entertaining is to take a book with little mathematical puzzles and try to express and solve them in Prolog. In many cases, the solution in Prolog is very concise.

BTW: I have the theory that while you might be able to express a many-1000-lines C program in 7 lines of Prolog, you actually often need the same amount of time to program, you just have to think more in the latter case.

Sebastian

[ Parent ]

Fun with cut (none / 0) (#70)
by Repton on Thu Feb 26, 2004 at 09:19:28 PM EST

Loop for reading user input and doing something with it:

repeat.
repeat :- repeat.
loop :-
      repeat,
      write('Enter a term: '), nl,
      read(X),
      ((X = stop, !, fail);
        do_something(X), fail).

--
Repton.
They say that only an experienced wizard can do the tengu shuffle..

Ouch. (none / 0) (#82)
by tkatchev on Fri Feb 27, 2004 at 03:42:38 AM EST

That's arcane.

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

Pfft. (2.60 / 5) (#71)
by SIGNOR SPAGHETTI on Thu Feb 26, 2004 at 09:25:29 PM EST

Implementing Prolog is exercise 7.3 in "LISP for Dummies."

--
Stop dreaming and finish your spaghetti.

It's funny cuz it's TRUE [nt] (none / 2) (#76)
by warrax on Fri Feb 27, 2004 at 02:51:17 AM EST

.

-- "Guns don't kill people. I kill people."
[ Parent ]
:- huh (1.00 / 7) (#72)
by br14n on Thu Feb 26, 2004 at 10:31:01 PM EST

if it just had 8==D we would be in business

Prolog could be so great... but... (none / 2) (#74)
by Baldrson on Fri Feb 27, 2004 at 12:58:27 AM EST

Fundamentally the world doesn't allow us depth-first search. It's understandable why implementers would want to pursue that sort of search strategy but they make such a mess of things that Prolog becomes virtually unusable. Even with a breadth-first search, where it isn't fatal, you should _never_ get stuck in an infinite recursion just because you have redundant rules. In depth-first search its just fatal.

Nix.

Prolog was originally implemented for systems like the DEC-10 where resources were so scarce compared to today's systems, it may have been understandable to some limited degree. Nowadays there's no excuse.

A pretender to the predicate calculus should serve that tradition more nobly.

-------- Empty the Cities --------


Depth first for speed (none / 0) (#77)
by jongleur on Fri Feb 27, 2004 at 03:09:11 AM EST

I believe.  It's some reason anyway, I've forgotten.  Iterative deepening is hybrid between depth-first and breadth-first that tries to give the best of both.
--
"If you can't imagine a better way let silence bury you" - Midnight Oil
[ Parent ]
Yes that's vastly superior, but... (none / 0) (#95)
by Baldrson on Fri Feb 27, 2004 at 12:27:53 PM EST

Even with iterative deepening (which is basically just limited-depth depth-first that retries at a deeper depth-limit each iteration) you still run into really nasty exponentiation problems that have to be addressed somehow. The choice of which alternative hypothesis is the most promising to explore at each depth is a classic problem - extending well beyond the domain of machine learning to science in general. You really have to have your phenomenology straight when you do this stuff and that means you have to be willing to place bets on outcomes and then ruthlessly invest in the 'winning model' even though, as the sophomoric never tire of chanting: "correlation doesn't imply causation". Logic without proportion just doesn't work when trying to solve the problems people need solving.

-------- Empty the Cities --------


[ Parent ]

Errata: "model" -> "models" (none / 0) (#96)
by Baldrson on Fri Feb 27, 2004 at 12:35:00 PM EST

That sentence should have read more as:

"...invest in models in proportion to their projected outcomes...".

-------- Empty the Cities --------


[ Parent ]

What are you talking about? (none / 1) (#89)
by it certainly is on Fri Feb 27, 2004 at 08:28:20 AM EST

Prolog easily supports all known search strategies, as long as you program them explicitly.

And no, I wouldn't like to use a programming language based on traversal that could change the traversal order at a whim. That would make it almost impossible to program for.

kur0shin.org -- it certainly is

Godwin's law [...] is impossible to violate except with an infinitely long thread that doesn't mention nazis.
[ Parent ]

Excuse me ... ? (2.75 / 12) (#75)
by levsen on Fri Feb 27, 2004 at 02:41:20 AM EST

Didn't you just prove that Prolog is a "horrible, pariah-like" language? In the usual professor-manner you have given a very precise, complete and useless explanation of Prolog. No one, I repeat no one curious about Prolog cares about syntax first.

What'd be interesting, if indeed Prolog is not a horrible, pariah-like language, is how you had a problem the other day that you were trying to solve in Java/Haskell/... and it was so much clearer and simpler in Prolog. Or you had a problem (real world, not sorting algorithms ma'am) that you never figured out until Prolog made it possible in the first place.

Show to us how you compiled a vast knowledge base for your research project that you can now tame and profit from using Prolog, show some sample rules or all of them actually, tell us about the inspirations that led you to Prolog ('cause it was not university, was it) and what led the French guy to make it in the first place.

Show us. Your silence will be proof that Prolog is, after all, a horrible, pariah-like language.

P.S.: After you're done doing that can you do the same for Lisp please, which in spite of Paul Graham I haven't 'gotten' yet, and I can assure you I am not stupid.


This comment is printed on 100% recycled electrons.

Lisp sucks. (1.25 / 4) (#81)
by tkatchev on Fri Feb 27, 2004 at 03:40:47 AM EST

Scheme is a real programming language, while Lisp is mostly used for writting buggy editor macros.

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

Scheme sucks. (2.25 / 4) (#93)
by JyZude on Fri Feb 27, 2004 at 10:20:34 AM EST

Just as much as Lisp.

If you're a human being and you want to get something done, the easiest way to do it is to break it into steps like A, B, C, define an order to them, use conditionals for unexpected situations, and write a plan. If your task involves things, you can use "objects" and interact with them.

This is how the human mind normally gets things done. All these bizarro languages like Scheme, Lisp, and Prolog go counter to natural most thinking processes and natural human languages. Though these languages are theoretically interesting, most people don't want to think like a mathematician. They just want to get things done.

-----
k5 is not the new Adequacy k thnx bye


[ Parent ]
Hello, Sir. (3.00 / 8) (#94)
by tkatchev on Fri Feb 27, 2004 at 11:00:56 AM EST

Both Lisp and Scheme are algorithmic languages that break up problems into "steps" and "objects".

Whereas something as common as SQL is a declarative language.

In short, you lose.


   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

lisp and scheme (none / 0) (#120)
by JyZude on Mon Mar 01, 2004 at 02:09:47 PM EST

Aren't they Functional languages? Yes, they do break stuff into algorithms, but the thing I recall about Scheme is that it's always using recursion. If you want to get something done to a list, you deal with the head and assume that the tail has already been done. It's much easier to say "do this to the head and repeat for the tail" instead of "do this with the head and append it to the already-done tail." Or maybe I'm just too stupid.

Agreed, SQL is declarative. But SQL usually just gets you data, or moves it about. If you want to do something more interesing, you use PL/SQL, which is procedural, isn't it?

-----
k5 is not the new Adequacy k thnx bye


[ Parent ]
Functional != declarative. (none / 1) (#121)
by tkatchev on Mon Mar 01, 2004 at 03:52:25 PM EST

"Functional" languages are simply languages with a subset of the functionality found in "normal" imperative algorithmic languages; the idea is to remove all the unneeded stuff that makes programming complicated and allows for bugs and segmentation faults and whatnot.

So in fact learning "functional" programming is simple -- you just need to forget about all the "extra" stuff you learned and re-learn to do more with less.

Declarative programming is totally different and isn't really related at all to functional programming. (Though adding declarative elements to functional languages is easier because functional languages are, in general, simpler to reason about and have less "stuff" at the core.)

Though nothing at all prohibits you from adding declarative features to C or Java or COBOL or whatnot; in fact, C's type system and inheritance in Java are declarative features. So if you know a little C or a little Java, you already know a little bit of declarative programming.

P.S. Recursion isn't declarative; recursion is simply a way of doing loops in a simple and consistent way. (i.e. You just use recursion instead of having to define fifty-nine different "for", "while", "until" and "do" operators with different syntax and different semantics.) In fact, nothing prohibits you from using recursion in C or Java. (Except for really dumb non-optimising compilers.)


   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

rebol (none / 0) (#100)
by davros4269 on Fri Feb 27, 2004 at 04:45:27 PM EST

Rebol is a cool and usable Lisp variant. It's easier to 'get', and you aren't forced into doing everything via recursion.

It's too bad it's not Open Source, if so, I predict it would take off.
Will you squirm when you are pecked? Quack.
[ Parent ]

LISP really does work (2.75 / 4) (#101)
by tamills on Fri Feb 27, 2004 at 05:26:29 PM EST

At school (20 years ago) I was taught languages in this order: Basic, COBOL, PASCAL, Assembler, Fortran.

On my first real job with DoD, my boss gave me a Symbolics LISP workstation and a set of manuals. Within only two weeks, I was producing working code and began delivering. And I am not necessarily such a smart man.

I'm not some MIT graduate. I attended Western Kentucky Univ. I never saw LISP in the classroom. But I got LISP right away. 'Getting' LISP has far more to do with when and how you are introduced to it.

I am convinced that LISP's lack of popularity began in the world of the first assemblers as people tried to do programs like shopping lists. And it continued as high-level languages were pushed more and more towards English. So people aren't required to learn to think in a LISP way.

I understand that people don't 'get' LISP. But I'll bet that if your paycheck depended on it you too could pick it up in a couple of weeks and be productive.

We (DoD) produced large working systems in a short time. Take it from this hillbilly. LISP ain't that strange.

Drew

[ Parent ]
Lisp Me (none / 0) (#105)
by levsen on Sat Feb 28, 2004 at 07:38:41 AM EST

Just to make sure there's no misunderstanding here, I didn't doubt that Lisp or Prolog work, that they are undeservedly unpopular or anything else you said, especially that it just takes the 'right' introduction. I just doubt that was "tkatchev" wrote, was the right introduction.

Especially sample problems (real world, don't forget!) do wonders in this respect. Now if you could share some of the DoD's projects with us ...

Please ....


This comment is printed on 100% recycled electrons.
[ Parent ]

well (none / 1) (#108)
by pantagruel on Sat Feb 28, 2004 at 12:38:26 PM EST

two points: 1. he pointed to some links at the end of his article to cover those points. 2. When I'm interested in something one of the first things I look at is the syntax, the syntax tells me how the designer(s) think, cruddy syntax, muddy thinking. Another thing I look at is a technical description of the language, what type of language is it, declarative, logic, procedural, OO, functional, etc. this tells me some of what to expect, as well as telling me what kinds of problems I will think it most likely to be good for.

[ Parent ]
Real-world Problem (none / 0) (#119)
by robmyers on Mon Mar 01, 2004 at 01:13:32 PM EST

I've prototyped geometry/graphics problems in Prolog. It's so much easier to search a network of nodes or a scenegraph with Prolog than anything else that it's not funny. And then I hit that 300-line limit and I have to re-code it in something else... :-)

[ Parent ]
Learn Prolog Now! (book) (none / 2) (#80)
by The Shrubber on Fri Feb 27, 2004 at 03:38:17 AM EST

Learn Prolog Now! is a free (beer) book online and is quite friendly:

http://www.coli.uni-sb.de/~kris/learn-prolog-now/

Prolog in Lisp (none / 1) (#83)
by cpghost on Fri Feb 27, 2004 at 04:07:38 AM EST

One of my customers needed help in maintaining a Prolog application. The programs were very difficult to read, because they kept adding and removing facts _and_ rules dynamically. The easiest way to solve this maintenance nightmare was to write a prolog inference engine in scheme, and then port the whole application to a lisp-like syntax. Unlike Prolog, the resulting program was much easier to parse and extend.

Now Prolog isn't a bad language. It has just a horrible syntax.


cpghost at Cordula's Web
Oz (none / 2) (#86)
by Wildgoose on Fri Feb 27, 2004 at 05:31:06 AM EST

Anyone interested in Prolog should also take a look at Oz, a modern multi-paradigm language that attempts to incorporate all the main strands of computing: imperative, functional and constraint programming.

Its creators come from a Prolog background, and have attempted to address all its deficiencies.

Recommended.

SWI Prolog (none / 0) (#127)
by Elektro Schock on Wed Apr 07, 2004 at 01:05:29 PM EST

Ma favourite implementation is SWI prolog from the Netherlands

[ Parent ]
I tried to use Prolog at work once... (none / 2) (#88)
by skyknight on Fri Feb 27, 2004 at 06:12:59 AM EST

but ended up abandoning the project. I wanted to use it to specify permission relationships for users to view and edit documents. It would have been the perfect language for representing the kind of things that were needed, but I could not for the life of me find a robust and well supported way to tie Prolog to a MySQL database.

Our code base was in Perl, and I found a couple of different libraries for interfacing Perl and Prolog, but it seemed that I would have been stuck with the odious task of keeping the Prolog engine synced up with the mammoth database. What I really needed was some way for Prolog to use the MySQL database transparently as its set of facts. Alas I could find no evidence of the existence of such a thing.

If anyone has successfully managed to use Prolog in an industry project, then I would be very interested to hear about it.



It's not much fun at the top. I envy the common people, their hearty meals and Bruce Springsteen and voting. --SIGNOR SPAGHETTI
look at xsb (none / 1) (#107)
by pantagruel on Sat Feb 28, 2004 at 12:33:20 PM EST

xsb a tabled prolog.

[ Parent ]
O.b. poll. (none / 0) (#91)
by tkatchev on Fri Feb 27, 2004 at 09:36:17 AM EST

Interesting, Lisp is about equal with C and C++.

   -- Signed, Lev Andropoff, cosmonaut.

lisp (none / 1) (#106)
by DGolden on Sat Feb 28, 2004 at 11:27:27 AM EST

Not sure about the wording "lisp derived", though - I mean, my language of choice is Common Lisp, it IS Lisp.  I guess you could say it's lisp derived, but it's like saying C is C derived because it's based on earlier versions of C...

 My attitude to prolog is basically similar to another posters - syntax sucks, write an inference engine in Lisp instead (takes a few minutes if you've got a lisp book to hand, a prologish interpreter is one of those "hello world" examples lisp book writers seem to always use...).
Don't eat yellow snow
[ Parent ]

Down with Prolog (1.06 / 16) (#92)
by Cro Magnon on Fri Feb 27, 2004 at 10:12:18 AM EST

COBOL rUleZ!
Information wants to be beer.
Um... (none / 0) (#109)
by trhurler on Sat Feb 28, 2004 at 06:25:36 PM EST

.NET is not a programming language, unless you call the JVM a programming language. Also, some(myself included) would argue that Lisp is actually a tool for making hippies out of programmers rather than a programming tool...

--
'God dammit, your posts make me hard.' --LilDebbie

Benefits of the Prolog mindset... (3.00 / 4) (#110)
by knickknack on Sat Feb 28, 2004 at 09:45:44 PM EST

Thanks tkatchev, I was very happy to see an accessible introduction to Prolog (one of my favourite languages); but, I just had to comment, and respectfully disagree on some aspects ;-).

It took me a few courses (and curses ;-) using Prolog before it really sunk in. The first time I used Prolog, I was locked in the Object-Oriented mindset, and judged Prolog unfavourably on this metric. It was 'interesting', but I thought I would never have a use, or need to bother with that language again -- and good riddance. Fortunately, the university curriculum was persistent ;-)

I'll comment more on Prolog's practical shortcomings later, but I will say it is a very useful prototyping language. More importantly, it encourages a very, very valuable mindset to problem solving that is its greater value -- even if you don't program in Prolog, this mindset can help you write programs in any language.

This article takes the traditional problem solving mindsets and applies them to Prolog (and this is all fine and good); but it is the opposite mapping that is more needed, since the programmer at large is likely well versed with the OOP mindset.

Problems, programming, and their languages have a natural duality between the goals of a problem and the plan that achieves it. Typically, programmers focus on the plan (which is the sequence of instructions that achieve the goal) which they must generate themselves. Still, this plan much achieve the program goals (usually verified by testing). The declarative style of programming is focussed on what is true in the world (and on capturing these in the program model). Goals are things which we hope are true in the world, and plans are the proofs to achieve them (a plan can still be seen as a sequence of instructions). In the declarative style the plan is not the focus of the programmer, but plans are still required to achieve the goals. In Prolog, constructing the plan is taken care of for us.

Prolog can be viewed as a procedural-type language (to make it more accessible to experienced programmers) just as it can be viewed declaratively (all part of that duality). For example, take the rules:

a([],B,B).
a([A|As],B,[A|Cs]) :- a(As,B,Cs).

In the procedural view, 'procedures' are call-by-reference (kind of), and 'procedure' a/3 (the name is 'a' and takes 3 arguments) has two implementations (think of this like a type of operator-overloading, where the failure of one operator invokes another one). The first implementation is run if arg 1 is the empty list ([]), and arg 2 equals arg 3. The second implementation requires arg 1 to be a list with at least one element, and calls 'procedure' a/3. The values returned by this 'call' are used to created the returned value for arg 3.

In the declarative view, predicate a/3 is true if arg 1 equals [], and arg 2 equals arg 3; or, a/3 is true if a/3 (with slightly modified arguments) is also true.

Some of this duality can be seen in the way that we comment our predicates. We can comment a/3 above either procedurally:

% a(A,B,C) appends list B to the end of list A, to produce list C.

Or declaratively:

% a(A,B,C) is true if C is a list containing all elements of A, then all elements
% of B, in the order they appear in A and B.

The second comment better captures that a/3 can serve multiple purposes -- one, to create the appended list C, and the other to test if the pre-existing list C satisfies the append properties. Additionally it indicates that a/3 will also construct B if only A and C are given...

it_certainly_is gave a nice family relations example in post #14. The procedural view of mother/2 is that calling mother/2, then calls female/1 followed by parent/2. The declarative view is that a mother is a female parent.

In the declarative view, the body of the rule is just another query.

And now to the relevant bit... You can apply the declarative perspective to imperative style languages too. Basically, when I program, I hold both perspectives in mind at the same time, and they help to create the imperative plan, verifying in my mind that it has the properties I'd expect. Essentially, this is just internalizing the use of pre and post-conditions without explicitly asserting them. It is also easier to do mini inductive-proofs in one's head that a program actually works, if we know what properties the functions (are supposed to) have. I find that being at home with both perspectives simultaneously makes programming even imperative languages much faster, more fun, and less error prone.

If you only view Prolog through the perspective of your familiar mindset (e.g., 'SQL', pattern matching, or procedural approaches), I think you are short changing yourself. Sorry.

And now for some other smaller points...

I wonder if we will see a paper, "Cut (!) Considered Harmful" ;-) I disagree on the dangers of cut -- it is in fact very useful, although it is extra-logical. I have not seen an elegant explanation of cut, even in the comments, so I'll try:

Cut (!) is a commitment to the current rule.

So, if the current rule cannot be satisfied after the cut, then no other version of the rule is tried. This is an extra-logical operator that diminishes the 'declarative perspective' of the program since it relies on the order in which rules are evaluated (the order they appear in the source file). However, outside of this, it is quite safe and useful to eliminate duplicate work.

In the purely logical declarative perspective, we don't need to even think about how the 'plan' construction is done (something which cut interferes with). If a Prolog program doesn't use any extra-logical operators, then the order of the rules, and the order of predicates in the rule bodies does not matter from a logical perspective (the truth remains the same), but different orderings do affect 'plan' finding efficiency. One great thing about Prolog is how easy it is to write a meta-interpreter (a program which interprets Prolog programs). Here are two examples (the simplest version is only 3 rules!):

A very simple meta-interpreter:

pprove((A,B)) :- !, pprove(A) , pprove(B).
pprove(X) :- predicate_property(X,built_in), !, call(X).
pprove(H) :- clause(H,B), pprove(B).

A more advanced meta-interpreter supporting or (;) and cut (!):

pprove((A;B)) :- !, pprove(A) ; pprove(B).
pprove((A,B)) :- !, pprove(A) , pprove(B).
pprove(!) :- !, pprove_cut.
pprove(X) :- predicate_property(X,built_in), !, call(X).
pprove(H) :- catch((clause(H,B), pprove(B)), pprove_cut_exception, fail).

pprove_cut.
pprove_cut :- throw(pprove_cut_exception).

You could try the query:

?- pprove(a([a,b,c],[1,2,3],C)).

to evaluate the a/3 predicate given above.

These meta-interpreters do not change the order in which predicates are evaluated (that's left as an exercise for the reader ;-), but it is fairly easy to do. Even with some small extensions to the above code we can get useful capabilities added to our interpreter, such as depth bounding, the entire proof tree, or iterative deepening (to simulate breadth first search). In this way, our code is also a data...

Prolog does lack as a practical language, I'll admit. There is a dearth of built-in predicates and routines compared to other languages, and Prolog code can be difficult to maintain (data structures represented as function constants are particularly fragile when changed). The supporting tools also feel less mature for Prolog than for other languages. Still, I like working in it, and I'm very grateful for the 'declarative' perspective it's given me.

SWI-Prolog is a very decent Prolog implementation. It is fast enough, handles large data-sets very well, comes with a graphical debugger, and a good collection of useful predicates.

**plug** For those wanting a Java based Prolog to try in a browser, there is JLog. It can work as either an applet or application, and is Free software. There is a nifty little robot simulator example you can try out that uses the graphic display capabilities of JLog -- you can see from the source for the robot example that it is using meta-interpreter for a Prolog-like language. There are some other examples available to try out too.

Thanks again for introducing Prolog to K5ers, I hope the curious will eventually come to appreciate the logical declarative perspective!



Mindset, excellent (none / 0) (#111)
by levsen on Sun Feb 29, 2004 at 05:08:17 AM EST

I am glad you are separating the two aspects of a programming language, the aspect of being an interface to the computer (syntax, essentially) and the aspect of communicating ideas between software developers and to oneself (mindset).

No speaking of the mindset, I wonder if you can distill the Prolog mindset down to what's actually the difference between Prolog and an inference engine.

Although I am very curious about Prolog, the mindset, I am 100% sure I will never use Prolog the syntax, all there will be is an inference engine in Java or Scheme or whoknowswhat. Now an inference engine is a simple backtracking algo implemented in 10 lines essentially. What more is there to Prolog?


This comment is printed on 100% recycled electrons.
[ Parent ]

You missed the key (none / 0) (#116)
by Baldrson on Sun Feb 29, 2004 at 02:53:27 PM EST

To reduce relations to computations you have to have a good discipline for translating relations to functions. The use of predicate calculus to express things at a high level is crucial for the start of any specification process. The real issues arise when you are translating the resulting relations to functions. "order by" functions are a good example of the general technique used in SQL relations as they take an indeterminate result and by ordering it make it determinate. However when you're trying to be coherent about solving a problem you really need some sort of _global_ ordering which can guide the entire computation. The best example of such an ordering arises during the specification of business processes and business rules where there is a single ordering function for all rules and processes: The (risk adjusted) net present value of the business. Now if you are a human immunodeficiency virus, your global ordering function may be a bit different from that -- but the principle holds regardless.

-------- Empty the Cities --------


[ Parent ]

graphical IDE? splitting? debugging? (none / 0) (#112)
by levsen on Sun Feb 29, 2004 at 05:17:32 AM EST

Can anyone say something about what "slicing" means when referring to Prolog. Has anyone used a graphical environment to program Prolog. In particular, I am interested what this is, further information from the authors is not available.


This comment is printed on 100% recycled electrons.

RE: graphical IDE? splitting? debugging? (none / 0) (#117)
by kardamon on Mon Mar 01, 2004 at 08:27:32 AM EST

You could try Visual Prolog, they have a free personal version to try out.

[ Parent ]
graphical environment (none / 0) (#125)
by tarantino on Wed Mar 10, 2004 at 11:13:39 AM EST

Amzi prolog provides a graphical IDE in which to develop it, though it still runs text-based. It doesn't seem there is a free version. http://www.amzi.com/products/prolog_products.htm http://www.amzi.com/download/index.htm

[ Parent ]
Best Prolog book I know of (none / 0) (#113)
by gpig on Sun Feb 29, 2004 at 06:23:31 AM EST

For those who need to ritualistically slaughter some fraction of a tree when they learn a new language:

PROLOG Programming for Artificial Intelligence by Ivan Bratko

It's not heavily into theoretical AI stuff & so should be ok for industrial use too.

(reposted from editorial comment)

Art of Prolog (none / 1) (#114)
by jsykari on Sun Feb 29, 2004 at 09:19:26 AM EST

I strongly recommend Art of Prolog by Sterling & Shapiro. It's a classic that has not aged a bit.

I can only say it left me with the feeling of enlightenment that no other book than SICP has been able to produce.

[ Parent ]

I have heard good things about Art of Prolog (none / 0) (#115)
by gpig on Sun Feb 29, 2004 at 11:06:31 AM EST

also the cover art is superior.

[ Parent ]
Oh, wow. (none / 2) (#122)
by James A C Joyce on Wed Mar 03, 2004 at 03:21:46 PM EST

Prolog sounds like a shittified version of m4.

I bought this account on eBay

Mainstream? Easy? (none / 0) (#123)
by suquux on Thu Mar 04, 2004 at 12:43:43 PM EST

... currently the simplest and the most straightforward programming language of all mainstream programming languages ...

Prolog mainstream ? I rather doubt that.

Easy ? I recall I once did linear algebra in (Turbo :) PROLOG. Big fun, many !!! . I rather would think that LOGO would be a candidate to consider.

Interesting though that PROLOG is revived when it comes to the semantic web.

CC.

P.S.: Some Goodies here!


All that we C or Scheme ...
A Prolog Introduction for Hackers | 127 comments (96 topical, 31 editorial, 5 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest © 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!