Softpanorama

May the source be with you, but remember the KISS principle ;-)
Home Switchboard Unix Administration Red Hat TCP/IP Networks Neoliberalism Toxic Managers
(slightly skeptical) Educational society promoting "Back to basics" movement against IT overcomplexity and  bastardization of classic Unix

Prolog Programming

 
News See also Recommended books Recommended Links Implementations Tutorials References
TEC prolog Free Implementations Tools and Libraries Production systems Usage of Prolog for exploring graph problems FAQ Regular expressions
Prettyprining  Softpanorama Debugging Recommendations  Coroutines Quotes Random Findings Programming Language Humor Etc
>> XSLT? Just a bastardized spawn of Prolog.

>
> As is any kind of pattern matching, including everyone's favourite  regular expressions. Prolog did it all.
>
I'm assuming you're kidding--there is a lot of difference between an RE that produces a highly optimized finite state machine to quickly match a string, and a language that uses brute-force depth-first recursion, plus some nonobvious tricks, to do the same thing. Like many orders of
magnitude in execution time :-)

That said, it'd be nice if there were some easy way to access a Prolog engine from Python. When Prolog is appropriate, it's _really_ appropriate.

[OT] Prolog and Regular Expressions, Was Re perspective on ruby Python Python

First  let' review the  history  of the language:

Prolog was invented by Alain Colmerauer and Phillipe Roussel at the University of Aix-Marseille in 1971. It was first implemented 1972 in ALGOL-W. It was designed originally for natural-language processing but has become one of the most widely used languages for artificial intelligence.

It is based on LUSH (or SLD) resolution theorem proving and unification. The first versions had no user-defined functions and no control structure other than the built-in depth-first search with backtracking. Early collaboration between Marseille and Robert Kowalski at University of Edinburgh continued until about 1975.

Early implementations included C-Prolog, ESLPDPRO, Frolic, LM-Prolog, Open Prolog, SB-Prolog, UPMAIL Tricia Prolog. In 1998, the most common Prologs in use are Quintus Prolog, SICSTUS Prolog, LPA Prolog, SWI Prolog, AMZI Prolog, SNI Prolog.

It came into prominence in early 80th due to long forgotten (and failed) Japanese  "Fifth Generation Computer Systems" project. As Wikipedia states:

The Fifth Generation Computer Systems project (FGCS) was an initiative by Japan's Ministry of International Trade and Industry, begun in 1982, to create a "fifth generation computer" (see history of computing hardware) which was supposed to perform much calculation utilizing massive parallelism. It was to be the end result of a massive government/industry research project in Japan during the 1980s. It aimed to create an "epoch-making computer" with supercomputer-like performance and usable artificial intelligence capabilities.

Pattern matching is a powerful computational tool. It can make programs shorter and easier to understand due to its declarative nature. Like Snobol4  Prolog uses pattern matching as a primary mean of expressing computations. That helps to understand its main application area -- transformation of text consisting of words into another text or proving some properties of the text.

It faded with the demise of the project with the golden decade of Prolog limited to probably 1980-1990.

Prolog is an interesting and rather strange specialized language for patterns recognition with good backtracking capabilities similar but more complex that those used in regular expressions.  A good introduction can be found  at Prolog Tutorial  by James Power (see also An introduction to Prolog - A short introduction to Prolog by Michel Loiseleur and Nicolas Vigier. ).

It is declarative language in a way similar to RPG, spreadsheets (Excel is the most popular non-procedural software system/language in existence) and, especially, regular expressions. Due to incorporation of recursive decent parser it is well suited for pattern matching or, in more general terms, for "goal oriented programming" like top-down syntax analysis.  It is more complex and much less understood then regular expressions.

It might be that complexity, rather narrow applicability of recursive decent parsing and absence of standard interface to scripting languages were the reasons that the language linger in relative obscurity. It never managed to make it into mainstream although it did achieved some level of success in  80th. 

The key questions about Prolog can be formulated in a following way:

For people who are interested in programming language design the first impression about Prolog is dominated by really bizarre, outdated syntax without clean separation between lexical and syntax level (strange and backward even for 1974). On lexical level the decision of what is a variable and what is a constant is based on whether the first letter is capitalized or not.   At the same time Prolog has some interesting and non-orthodox lexical properties (it is the only language that makes use of trigrams like <->, =/=, @<=, =.. etc). In this sense it does remind me some scripting languages (for example, Perl), but historically it is a much earlier language (1974). 

Those idiosyncrasies might be connected with its origin.  It originated outside the mainstream language design circles from work carried out in the early 1970's by Robert.A. Kowalski at Edinburgh University (and later at Imperial College, London) and Alain Colmerauer at the University of Aix-Marseille. The idea, that proved to be attractive (but which in case of Prolog failed) was to created a programming language with powerful pattern matching capabilities similar to recursive decent parsing.  Being non-procedural pattern recognition language it is only the second such language that achieved significant success (older and the most successful non-procedural language for patterns recognition is the regular expressions language popularized by Unix).

Colmerauer and Roussel built the first Prolog interpreter and David Warren at the AI Department, University of Edinburgh, the first Prolog compiler.  But actually in PC world Prolog was brought to prominence in the 1980's by Borland's Turbo-Prolog implementation (which has since reverted to it's developer, Prolog Development Center).

Anyway it is easy to criticize the over-exaggeration of pattern matching (goal oriented programming) in Prolog but all-in all it one of oldest (RPG is older) and reasonably successful  (both regular expressions and spreadsheets are vastly more successful; they are actually mainstream technologies -- in no stretch of imagination Prolog is a mainstream technology) among many non-procedural languages .

As it incorporates unique goal oriented  or "top-down syntax parsing" programming paradigm it is far from complete flop: for certain class of problems, the problems which can benefit from backtracking Prolog programs are shorter compared with their procedural equivalents (let's say for suitable problems, for each 100 lines of C we will need only 10-20 lines of Perl and 3-6 lines of Prolog).

But for hammer everything is a nail for Prolog everything is a theorem to prove (or goal to achieve) and this approach sucks for many real world problems. At the same time the language designers failed to provide clean "escape" path and interface with a scripting language. That probably one of the reasons that doomed Prolog in the first place.

I think that most people exposed to Prolog remember strongly the initial disappointment. Language was/is so hyped but all you can see initially are pretty trivial examples that are solved by complex, obscure notation that lacks real expressive power: some of simple examples can be expressed no less concisely is many other languages. All this junk like family tree example or factorial calculation are trivial for anybody who read Knuth (And I can say, that calculation of factorial in Prolog is a pure sadistic perversion ;-). Here is one of more suitable for the language primary domain examples borrowed from Prolog Tutorial by James Power):

The basic entities will be people; the properties we will want to look at will be father, mother, brother, sister, ..... We choose three basic predicates, male, female and parent, which will describe a family by a series of facts.

Take the following family tree as an example:

                              James I
                                 |
                                 |
                +----------------+-----------------+
                |                                  |
             Charles I                          Elizabeth
                |                                  |
                |                                  |
     +----------+------------+                     |
     |          |            |                     |
 Catherine   Charles II   James II               Sophia
                                                   |
                                                   |
                                                   |
                                                George I

In Prolog we represent this as:

  % male(P) is true when P is male
  male(james1).
  male(charles1).
  male(charles2).
  male(james2).
  male(george1).

  % female(P) is true when P is female
  female(catherine).
  female(elizabeth).
  female(sophia).

  % parent(C,P) is true when C has a parent called P
  parent(charles1, james1).
  parent(elizabeth, james1).
  parent(charles2, charles1).
  parent(catherine, charles1).
  parent(james2, charles1).
  parent(sophia, elizabeth).
  parent(george1, sophia).

Start a new file in your text editor (call it "family.pl"), and copy and paste the above program into it.

We can now formulate some queries (try entering these yourself):

You should probably think about this example as an elegant way for expressing grammars (which BTW is not  a context free grammar). In this case queries are just questions about whether particular sentence belongs to this grammar (the sentence may consist of pure final language tokens (facts) and in this case the answer is yes or no or can contain higher level grammar construct (be semi-parsed); in the latter case the answer is also consists with the value of high level syntax contracts that are present in the question and the whole activity resembles tree-based pattern matching. 

We can specify something similar in BNF but BNF being context-free does not provide the concise way to specify transitive relationship  (parent-child):

male := james1 | charles1 | charles2 | james2 | george1

female :=   catherine | elizabeth | sophia

james :=  charles1 | elizabeth 

charles1 :=  catherine |  charles2 |  james2

elizabeth := sophia

sophia :=  george1

parent := james | charles | elisabeth | sophia

Generally it takes a lot of time and experiences with the language and its implementation to overcome feeling that Prolog is an overhyped junk. Few ever get that chance. In industrial application tivoli TEC administrators are probably the most "realistically oriented" subclass of Prolog users.  In most cases people quickly switch to the other language that provides a more productive environment.  But you should not throw out the child with the bath-water. Syntax parsing based approach to programming is a powerful paradigm and Prolog is the one of the few surviving languages that incorporates this paradigm in a rather elegant way.

But even in this area we can saw limitations of Prolog. The parser provided by Prolog "for free'' is a recursive descent parser with backtracking. If you need something more complex you had to go to some lengths to program around these limitations, and even then the results were not completely satisfying.

Probably the most constructive way to view Prolog is to view it as a failed attempt to create yet another very higher level language similar to scripting languages.  Forget for minute about all this mathematic logic junk. In a sense "theorem proving" can be understood as "pattern matching" or more precisely grammar matching/parsing (again, I would like to stress that this aspect of Prolog has some resemblance to BNF).

BTW the initial design goal was analysis of natural languages: Prolog actually originated from attempts to use mathematical logic to express grammar rules and to formalize the process of parsing.  See Prolog Parsers/Parsing techniques in Prolog for more information.  The "grammar matching/theorem proving machine" approach helps to understand that you do not explicitly specify the algorithm in Prolog, but provide something like a grammar for the data (called facts) similar to BNF. After that you can answer question similar to the key question that is answered by syntax parsers: whether a particular text belongs to the particular language as specified by the grammar.   How this query is performed is controlled by ordering of facts and rules as well as by internal Prolog "theorem proving" logic which can be viewed as recursive decent based pattern matching with few tweaks.

Actually viewing Prolog as a grammar-based goal oriented formalism might save you from some headache by helping to see some logic in the design of the language. The idea of top down syntax analysis for a given grammar in many cases provides better understanding of internal mechanics then all blah-blah about "theorem proving" ;-).  And if the pattern match accurs, then certain variables are populated with values resulting from this match much like in Perl regular expressions. There are of course some differences (for example "lock-in" property in Prolog -- first value assigned to variable that has no value is "final").

As a language Prolog is a compromise between powerful, but very specialized, declarative programming notation and the complex realities of real world programming. An operational way to understand Prolog is to say that predicates are actually what ordinary people would call procedure calls with side effects that operate with the facts database. 

Unlike relational databases, Prolog facts database can contain both regular (passive) records/structures and rules. There is also a built-in  method of creating a predicate from a list (the "=.." operator):

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

is equivalent to:

    F = function(arg1, arg2).
 

Therefore the third way to view Prolog is to view it as a specialized database query language like SQL.  In a way in TEC Prolog is used in this function and it is not accidental that SQL-based "correlation engines" represent the main threat to the survival of Prolog in TEC.

The view of  Prolog as higher level language helps to understand that even simple Prolog statements like in:

bit(0).
bit(1).
bit(A),bit(B).

provides for implicit search which is the clear sign of higher level languages (in this case the program will give all six possibilities of values of A and B one by one.). You can try to generalize this program to any number of bits.

All-in-all it looks like Prolog makes sense as a part of the system that deals with the problems that are perfect for its capabilities and other parts of the system need to be programmed in a different language. Thus one of the most promising uses is a imbedded interpreter or by communicating with other parts of the system via pipes or files.

That's explain why don't professional software developments use it more? Well, area where it is efficient is very narrow and outside of this narrow area programs are very difficult to write and debug, they are slower than most scripting language to say nothing about compiled languages, and they can be extremely difficult to maintain. That means that as soon as you leave the area of text transformation the language is more of the burden then help. Borland made important step forward solving this problem by providing a good link to C language: in the days of Borland TurboProlog and TurboC (early 90s) it was relatively easy to call one from the other.  But that was not enough...

Despite being semi-forgotten Prolog was successfully standardized in late nineties.  The ISO standard enables users to write programs in ISO Prolog and then run them on any ISO compatible Prolog system on whatever platform that is.

A good current 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

The main production level application of Prolog that I know of is Tivoli Enterprise Console (TEC).  Actually TEC uses macro language that is translated into Prolog by special preprocessor, not plain-vanilla Prolog :-)

Good luck !

Dr. Nikolai Bezroukov


Top Visited
Switchboard
Latest
Past week
Past month

NEWS CONTENTS

Old News ;-)

[Mar 27, 2011] AI-Prolog 0.741

freshmeat.net
AI::Prolog is a predicate logic engine implemented in pure Perl. In predicate logic, instead of telling the computer how to do something, you tell the computer what something is and let it figure out how to do it. Conceptually, this is similar to regular expressions. The AI::Prolog distribution contains a Prolog shell called aiprolog and two short adventure games, spider.pro and sleepy.pro.
Tags CPAN Perl Modules Interpreters logic programming
Licenses Perl
Operating Systems OS Independent
Implementation Perl

Prolog and Regular Expressions

[Nov 22, 2008] why not use LISP-imp of Prolog as opposed to Prolog itself - comp.lang.prolog Google Groups

7 messages - Collapse all

/groups/adfetch?adid=1T2F7xEAAAAV2-9fyNifVZocRokHUFSTi_s2p3x1d9mB7p8AMaL9cQ

The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.

Newsgroups: comp.lang.prolog

From: globalrev <skanem...@yahoo.se>

Date: Tue, 13 May 2008 13:51:14 -0700 (PDT)

Local: Tues, May 13 2008 3:51 pm

Subject: why not use LISP-imp of Prolog as opposed to Prolog itself?

is there an actual reason to use swi-prolog or the like as opposed to
just use an implementation of Prolog in Lisp?

it seems Prolog is a special-purpose language and the
turingcompleteness is fairly pointless and just there for the cause of
being turingcomplete.
and thus better to have a real general-purpose language with prolog
implemented in that language so you can easily write your application
and then dont have to run code between 2 different languages.

or how big of a fool am i? this is just my quick/first impression of
prolog.

Newsgroups: comp.lang.prolog

From: globalrev <skanem...@yahoo.se>

Date: Tue, 13 May 2008 21:44:30 -0700 (PDT)

Local: Tues, May 13 2008 11:44 pm

Subject: Re: why not use LISP-imp of Prolog as opposed to Prolog itself?

Reply to author | Forward | Print | Individual message | Show original | Report this message | Find messages by this author

http://www.amazon.com/gp/product/1558601910/002-6413815-3000828?v=gla...

Lisp has been getting a higher profile lately because of essayists
like Paul Graham and Philip Greenspun; in particular, Greenspun's
Tenth Rule of Programming which states: "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." So, should this book be read as an exhortation to return to Lisp as the preferred programming language?

Paradoxically, I think not. One third of the way through the book,
Norvig shows us how to implement Prolog in Lisp. From then on out,
most of the AI techniques he presents either directly use Prolog
instead of Lisp (such as his excellent discussion of natural language processing using Prolog) or use Prolog as a base to build on (such as his discussions on knowledge representation).

From this we can abstract what I'd like to call Norvig's Corollary to Greenspun's Tenth Law of Programming: "Any sufficiently complicated LISP program is going to contain a slow implementation of half of Prolog". I'm leaving out the "ad hoc", "bug-ridden" part of Greenspuns's law, because Norvig's programs are neither. But it is quite remarkable the degree to which, once having absorbed Prolog, Norvig uses Prolog as the basis for further development, rather than Lisp.

Is this a book about Prolog then? Again, no. What is the take-away
message? It is this: as our world becomes more and more complex, and as the problems which programmers are facing become more and more complex, we have to program at a higher and higher level.

Newsgroups: comp.lang.prolog

From: Alessio Stalla <alessiosta...@gmail.com>

Date: Wed, 14 May 2008 02:36:05 -0700 (PDT)

Local: Wed, May 14 2008 4:36 am

Subject: Re: why not use LISP-imp of Prolog as opposed to Prolog itself?

globalrev ha scritto:

> http://www.amazon.com/gp/product/1558601910/002-6413815-3000828?v=gla...

> Lisp has been getting a higher profile lately because of essayists
> like Paul Graham and Philip Greenspun; in particular, Greenspun's
> Tenth Rule of Programming which states: "Any sufficiently complicated
> C or Fortran program contains an ad hoc, informally-specified, bug-
> ridden, slow implementation of half of Common Lisp." So, should this
> book be read as an exhortation to return to Lisp as the preferred
> programming language?

> Paradoxically, I think not. One third of the way through the book,
> Norvig shows us how to implement Prolog in Lisp. From then on out,
> most of the AI techniques he presents either directly use Prolog
> instead of Lisp (such as his excellent discussion of natural language
> processing using Prolog) or use Prolog as a base to build on (such as
> his discussions on knowledge representation).

> From this we can abstract what I'd like to call Norvig's Corollary to
> Greenspun's Tenth Law of Programming: "Any sufficiently complicated
> LISP program is going to contain a slow implementation of half of
> Prolog". I'm leaving out the "ad hoc", "bug-ridden" part of
> Greenspuns's law, because Norvig's programs are neither. But it is
> quite remarkable the degree to which, once having absorbed Prolog,
> Norvig uses Prolog as the basis for further development, rather than
> Lisp.

> Is this a book about Prolog then? Again, no. What is the take-away
> message? It is this: as our world becomes more and more complex, and
> as the problems which programmers are facing become more and more
> complex, we have to program at a higher and higher level.

It's not a book about Prolog, but it's a book about a field of
computer science where Prolog really shines (well, it was invented
precisely for that ;), so it's only natural to use Prolog-like
features everywhere. To my eyes and mental model, though, Lisp feels
more "general purpose" than Prolog, and the very fact Norvig shows how
to "add" Prolog to Lisp with limited effort is a confirmation in that
direction IMHO. Keep in mind that Norvig's Prolog implementation is
"slow" and "half" because it is code included in a book.
AllegroProlog, which was developed starting from PAIP Prolog, is
supposedly very fast (see http://bc.tech.coop/blog/040919.html and
http://bc.tech.coop/blog/040920.html), and probably more feature-
complete too. That said, which language to use depends both on the
task AND on the programmer's tastes (and sadly on other more mundane
factors as availabilty of libraries, which tend to give advantage to
already popular languages). If you feel Prolog is the right tool for
the problem you want to solve, use it all the way.

Cheers
Alessio Stalla

Newsgroups: comp.lang.prolog

From: bart demoen <b...@cs.kuleuven.be>

Date: Thu, 15 May 2008 22:03:11 +0200

Local: Thurs, May 15 2008 3:03 pm

Subject: Re: why not use LISP-imp of Prolog as opposed to Prolog itself?

On Tue, 13 May 2008 14:51:14 -0700, globalrev wrote:
> is there an actual reason to use swi-prolog or the like as opposed to
> just use an implementation of Prolog in Lisp?

Yes there is: Lisp can be (and was) implemented in Prolog (search for
Lisprolog in Google for one example). The point is: you never really want
Lisp; what you want is Prolog. So why not go for the real thing instead of
the embedded interpreter ?

> it seems Prolog is a special-purpose language and the

No, Prolog is general purpose.

> turingcompleteness is fairly pointless

No it isn't, it is essential in almost anything one wants to program.

> and just there for the cause of being turingcomplete.

BTW, Lisp is Turing Complete - otherwise it would not be possible to write
a Prolog in Lisp.

> and thus better to have a real general-purpose language with prolog

Prolog is a real general purpose language.

> implemented in that language so you can easily write your application

You can easily write your application in Prolog.

> and then dont have to run code between 2 different languages.

And that wouldn't even be a bad thing, so why worry about it.

> or how big of a fool am i?

I pass on this one.

Cheers

Bart Demoen

Newsgroups: comp.lang.prolog

From: Duncan Patton <campb...@neotext.ca>

Date: Fri, 16 May 2008 07:38:35 GMT

Local: Fri, May 16 2008 2:38 am

Subject: Re: why not use LISP-imp of Prolog as opposed to Prolog itself?

Reply to author | Forwa=8039e1ecddef8925">...@cs.kuleuven.be> wrote:
> On Tue, 13 May 2008 14:51:14 -0700, globalrev wrote:

> > is there an actual reason to use swi-prolog or the like as opposed to
> > just use an implementation of Prolog in Lisp?

> Yes there is: Lisp can be (and was) implemented in Prolog (search for
> Lisprolog in Google for one example). The point is: you never really want
> Lisp; what you want is Prolog. So why not go for the real thing instead of
> the embedded interpreter ?

> > it seems Prolog is a special-purpose language and the

> No, Prolog is general purpose.

> > turingcompleteness is fairly pointless

> No it isn't, it is essential in almost anything one wants to program.

There are non-Turing complete languages. They are just fairly useless.

Dhu

> > and just there for the cause of
> > being turingcomplete.

> BTW, Lisp is Turing Complete - otherwise it would not be possible to write
> a Prolog in Lisp.

> > and thus better to have a real general-purpose language with prolog

> Prolog is a real general purpose language.

> > implemented in that language so you can easily write your application

> You can easily write your application in Prolog.

> > and then dont have to run code between 2 different languages.

> And that wouldn't even be a bad thing, so why worry about it.

> > or how big of a fool am i?

> I pass on this one.

> Cheers

> Bart Demoen
Newsgroups: comp.lang.prolog

From: Peter Van Weert <Peter.VanWe...@cs.kuleuven.be>

Date: Fri, 16 May 2008 12:14:43 +0200

Local: Fri, May 16 2008 5:14 am

Subject: Re: why not use LISP-imp of Prolog as opposed to Prolog itself? Duncan Patton wrote:
> There are non-Turing complete languages. They are just fairly useless.

That is most definitely not true. Are Petri Nets useless? Is SQL useless? No. There are several examples of very useful domain-specific languages that aren't Turing powerful.

Peter

Newsgroups: comp.lang.prolog

From: Duncan Patton <campb...@neotext.ca>

Date: Fri, 16 May 2008 17:39:18 GMT

Local: Fri, May 16 2008 12:39 pm

Subject: Re: why not use LISP-imp of Prolog as opposed to Prolog itself?

On Fri, 16 May 2008 12:14:43 +0200
Peter Van Weert <Peter.VanWe...@cs.kuleuven.be> wrote:

> Duncan Patton wrote:
> > There are non-Turing complete languages. They are just fairly useless.

> That is most definitely not true. Are Petri Nets useless? Is SQL
> useless? No. There are several examples of very useful domain-specific
> languages that aren't Turing powerful.

Just try any non-trivial programming without access to a Turing-complete language sometime and you will
know what I mean. Non-Turing languages are, at the very best, language extensions. Usually they are
an excuse to waste money and blow smoke: like our Canadian Gun Control Registry that was written in
MS Access.

Dhu

[May 1, 2008] freshmeat.net Project details for YAP Prolog System

About:
Yap is a high-performance Prolog compiler developed at LIACC, Universidade do Porto. Its Prolog engine is based on the WAM (Warren Abstract Machine), with several optimizations for better performance, and achieves performance comparable or exceeding that of commercial Prolog systems. Yap is largely compatible with the major Edinburgh Prolog systems, and has been ported to most 32-bit and 64-bit Unix based platforms. A Windows port is also available.

Release focus: Major feature enhancements

Homepage: http://www.ncc.up.pt/~vsc/Yap/

[Mar 10, 2008] Gulf Breeze Blog SCEProlog - Prolog for the State Based Correlation Engine

A new release of OpenESM for Prolog (V1.1) is now available at Sourceforge. This new release includes a Prolog engine for the TEC 3.9 State Based Correlation Engine (SCE).

You can download the new release at:

http://sourceforge.net/projects/gulfsoft

Here are some notes from the Readme:

SCEProlog - Prolog for the State Based Correlation Engine

This library implements a Prolog environment as a State Based Correlation Engine custom action. Why would you want to use Prolog at the TEC Gateway or adapter level? Firstly, a Prolog environment would allow you to leverage most of your existing Prolog facts and logic that enrich events before true event correlation. Secondly, the Prolog language provides a flexible and powerful language to manipulate event objects. Finally, since Prolog is the base language for the TEC rule language, it is familiar to every seasoned TEC rule writers.

The underlying Prolog implementation for SCEProlog is GNU Prolog for Java (http://gnuprologjava.sourceforge.net/) by Constantine A. Plotnikov. While this project seems stagnant, I found it the simplest to integrate with the State Based Correlation Engine. Included with this distribution is the gnuprolog.jar file. If you desire to see the source of the GNU Prolog for Java library it is available for download from the original project website.

The SCEProlog environment implements the most of the ISO standard with the following additional predicates:

BIM Prolog compatability:
lowertoupper(LowerAtom,UpperAtom)
inttoatom(Integer,Atom)
realtoatom(Real,Atom)
atomconcat(Atom1,Atom2,Concat)
atomconcat(AtomList,Concat)
append(List1,List2,ApendedList)
member(Element,List)
memberchk(Element,List)
erase(Key)
erase(Key1,Key2)
record(Key,Term)
record(Key1,Key2,Term)
recorded(Key,Term)
recorded(Key1,Key2,Term)
rerecord(Key,Term)
rerecord(Key1,Key2,Term)

State based Correlation Engine:
set_event_class(ClassName)
get_event_class(ClassName)
set_event_slot(SlotName,SlotValue)
get_event_slot(SlotName,SlotValue)
get_event_slot(SlotName,SlotValue,DefualtValueIfNotSet)
delete_event_slots(SlotNameList)
discard_event
forward_event(SCE_RuleName_List)
get_rule_id(SCE_RuleId)
get_rule_variable(SCE_VariableName,VariabeValue)

IP Address Name Resolution:
get_hostname(IPAddress_or_Name,Hostname)
get_ipaddress(Hostname,IPAddress)
get_local_hostname(LocalHostname)
get_local_ipaddress(LocalIPAddress)
get_canonical_hostname(IPAddress_or_Name,CanonicalHostname)

Regular Expressions:
regex_create(RegexID,Pattern)
regex_create(RegexID,Pattern,RegexFlagList)
valid RegexFlag values:
canon_eq,
case_insensitive,
comments,
dotall,
multiline,
unicode_case,
unix_lines
regex_exists(RegexID)
regex_match(RegexID,Atom)
regex_match(RegexID,Atom,GroupMatchList)
regex_replace(RegexID,Atom,Replacement,Result)

Misc. Utilities:
get_system_property(JavaSystemProperty,PropertyValue)

You can see the rest of the notes in the readme that is part of the gb_08MAR2006.zip file

[Dec 4, 2007] Prolog and Logic Programming

Contents

Pure, declarative, and constructive binary arithmetic all-mode relations

This Prolog code shows Addition, Multiplication, Division with the remainder and Discrete Logarithm as sound and complete, pure and declarative relations that can be used in any mode whatsoever. The relations define arithmetic over base-2 non-negative numerals of arbitrary size.

In particular, we define the predicate div/4 such that div(N,M,Q,R) succeeds if and only if N = M*Q + R and 0<=R<M. We run the following queries:

1 isb N1, 0 isb N0, div(N1,N0,Q,_).
It fails instantly and does not try to enumerate all natural numbers.
1 isb N1, 5 isb N5, div(N5,M,N1,_).
It finds all such M that divide (perhaps unevenly) 5 with the quotient of 1. The answer is the set (5 4 3).
div(N5,M,N7,_)
simply fails and does not loop forever.

We can use our mul(X,Y,Z) either to multiply two numbers X and Y -- or to find all factorizations of Z, as the tests show. Furthermore, we can evaluate add(X,[l],Y) and get the stream of answers, among which is [[o, _G523|_G524], [l, _G523|_G524]]. It essentially says that 2*x and 2*x +1 are successors, for all x>0!

Our log/4 predicate has the property that log(N,B,Q,R) succeeds if and only if N = B^Q + R where 0 <= R and Q is the largest such integer. We can use log/4 to exponentiate, to find discrete logarithms or roots.

Version
The current version is 1.11, March 4, 2005.
References
pure-bin-arithm.prl [41K]
Very commented source code, with termination proofs.

The same example in Kanren
Thanks to the fair scheduling primitives of Kanren, Kanren arithmetic relations enumerate their whole domains without any restrictions; moreover, they do so in the natural order, despite being the implementations of binary arithmetic.

Universal quantification, impredicative terms, and effects

This note discusses universal quantification of variables in the body of a clause, given open- and closed-world assumptions. We also discuss two ways of expressing impredicative terms like (exists U. [U,U]), and `common subexpression elimination' in logical programs. We draw parallels with effects, of creating logical variables.
Version
The current version is 1.3, March 5, 2005.
References
quantification.txt [8K]

leanTAP theorem prover in Kanren

leanTAP (Beckert and Posegga, 1995) is a simple, elegant and efficient theorem prover for the full classical first-order predicate logic. The prover is based on semantic tableaux.

The miniKanren implementation uses higher-order syntax (to avoid copy_term) and an advanced evaluator that removes the need for explicit iterative deepening.

Version
The current version is 1.5, Aug 30, 2005.
References
< http://cvs.sourceforge.net/viewcvs.py/kanren/kanren/mini/leanTAP.scm >

Bernhard Beckert and Joachim Posegga. leanTAP: Lean Tableau-based Deduction. Journal of Automated Reasoning, 15(3), 339-358 (1995).
< http://citeseer.ist.psu.edu/beckert95leantap.html>

Soutei, a logic-based trust-management system

We describe the design and implementation of a trust-management system Soutei, a dialect of Binder, for access control in distributed systems. Soutei policies and credentials are written in a declarative logic-based security language and thus constitute distributed logic programs. Soutei policies are modular, concise, and readable. They support policy verification, and, despite the simplicity of the language, express role- and attribute-based access control lists, and conditional delegation.

We describe the real-world deployment of Soutei into a publish-subscribe web service with distributed and compartmentalized administration, emphasizing the often overlooked aspect of authorizing the creation of resources and the corresponding policies.

Soutei brings Binder from a research prototype into the real world. Supporting large, truly distributed policies required non-trivial changes to Binder, in particular mode-restriction and goal-directed top-down evaluation. To improve the robustness of our evaluator, we describe a fair and terminating backtracking algorithm.

This is a joint work with Andrew Pimlott.

Version
The current version is April 2006.
References
Soutei, a logic-based trust-management system (system description) [PDF]
The paper presented at FLOPS 2006, 8th International Symposium on Functional and Logic Programming. Fuji-Susono, Japan, April 24-26, 2006. The paper is published in Springer's Lecture Notes in Computer Science 3945/2006, pp. 130-145.
Soutei: syntax, semantics, and use cases [external link]
soutei-1.tar.gz [62K]
The first implementation of Soutei, in Scheme. Its particular feature is the compilation of Soutei assertions into Kanren code. The code relies on Bigloo-specific module system and the built-in parser and lexer. The code can be compiled with Bigloo v2.4. It includes many built-in tests.
This source code is given here for information only. It is no longer used; it served as a model for the current, version 2 implementation, which is written in Haskell.

Minimization of a Finite Automaton

A Prolog code that implements a Hopcroft-Ullman Algorithm 2.6 to minimize a Finite Automaton.

Given a set of states, an initial and the final state(s), the alphabet and the transition function, the code returns a list of equivalent states. The equivalent states can then be merged, resulting in a smaller Finite State Machine.

Version
The current version is 1.0, October 1991.
References
minimizer.prl [7K]
A very commented source code.

[Jun 28, 2007] freshmeat.net PySWIP a Python/SWI-Prolog bridge

PySWIP 0.2.0 Jun 28th 2007 04:49 PDT

About: PySWIP is a Python/SWI-Prolog bridge that enables you to query in prolog using SWI-Prolog in your Python programs. It includes both a SWI-Prolog foreign language interface and a utility class that makes it easy to query with SWI-Python. Since it uses SWI-Prolog as a shared library and ctypes to access it, it doesn't require compilation to be installed.

Changes: This release introduces a new 'Pythonic' interface. Prolog.query now returns real Python data types and foreign functions get values as Python data types. A Sudoku Solver was included.

[May 16, 2007] Prolog as a Ruby DSL www.kdedevelopers.org

Prolog in Ruby
I just read Pat Eyler's blog Reading Ola Bini writing about some interesting discussions on Ruby metaprogramming and how it compared with Lisp macros for writing Domain Specific Languages. In one of the references Why Ruby is an acceptable LISP, amongst other things people discuss how to implement prolog as a DSL in Ruby or Lisp. A long time ago some of my 'hobby programming' projects were writing prolog interpreters in various languages; I started off with a Pascal one and added things to it, translated it into Modula-2, and I did a Object Oriented one in Objective-C. I've started translating the Objective-C one into Ruby, and it's quite fun seeing how the code compares in the two languages.

In the Objective-C prolog I didn't attempt to use the language as a DSL, I used lex and yacc to tokenise and parse the prolog code. That allowed me to do a pretty complete implementation, apart from the 'op' predicate which allows you to define new operators with precedences to implement DSLs in prolog (although they weren't called DSLs then). With Ruby I think the language is just about powerful enough to implement a simple prolog in Ruby itself. Here's my idea of what it could look like:

[May 16, 2007] the { buckblogs here } D&D, Knowledge bases, and Prolog (oh, my!)

Game programming connection
It's one thing to evaluate this chain when the parameter is known. If I want to know if a character is eligible for Greater Weapon Specialization (Longsword), then I know that they have to have the requisite feats with the longsword as well. However, sometimes I need to ask "what feats is the character eligible for right now?" In that case, I can see that the character has weapon proficiency with a particular set of weapons, which implies that the character may be eligible for Weapon Focus in any of those weapons as well. Even trickier is the case of a prestige class that simply says "must have the Greater Weapon Specialization feat", but doesn't require a specific weapon. In that case, when I ask whether or not the character is eligibile for the prestige class, I basically have to use a variable for the feat's parameter and then bind it, at the end, to the set of all weapons that the character might be able to use to eventually meet that requirement.

Ah, my head spins!

However, as I was pondering all of this, I kept getting a little ping from my university memories. Something I studied (and promptly forgot) 10 years ago was trying to tell me it was now relevant…

Enter automated theorem proving. As I begin researching and remembering the hours I spent on my homework and programming assignments, the concepts of Resolution and Unification came flooding home. I actually really enjoyed that class (which is probably why I remembered anything at all about it), even though I was sure I would never ever be doing anything with that knowledge.

For about 10 years, I was right. It was useless data stored in my brain.

But suddenly, it was relevant. How? Well, what my NPC generator needs to be is a knowledge base of all the facts and relationships between the various data in the system. Generating a character is (essentially) a query against the knowledge base-"has this character met this goal?" The knowledge base then needs to come back and either say "yes" (in which case the goal is met), or "no" (in which case the response includes the actions that need to be taken to help the character achieve the goal). Revelation!

With that in mind, I finally decided it was time to learn Prolog. It's been one of those languages on my "huh, maybe I ought to look at that someday" list, but now it actually has relevance to something I want to accomplish. Mostly, I only want to use Prolog to test my ideas, and to prototype the NPC generator. I still love Ruby and think I could make a killer DSL for this in Ruby, but we'll see what happens.

So far, all I've managed to do in Prolog is hard code a bunch of assertions that define a genealogy database, along with some rules that I can use to ask things like "who are the grandparents of this person". It's fun, and I'm looking forward to delving further in. I'm especially excited to see how far I can apply this to my original problem domain: random generation of gaming characters with some (potentially arbitrary) set of constraints.

[May 10, 2007] A Prolog Introduction for Hackers kuro5hin.org by tkatchev

What he writes is not true, but still helps to understand the language ;-)

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:

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:

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.

[May 7, 2007] [PDF] CGI Scripting in SWI-Prolog Under Windows 2003 Server (IIS 6.0)

[May 7, 2007] stdin Re [SWIPL] Perl launch script for Prolog

From: Djamé Seddah <[email protected]>
Date: Wed Apr 20 2005 - 11:21:08 CEST

Steve Prior a écrit :
> I've been using the following "PrologScript" for launching SWI-Prolog to
> a Prolog command prompt after consulting some files:
>
> ------------------------ snip ---------------------------------------------
> #!/usr/local/prolog.5.3.14/bin/pl -q -g main -f
>
> main :-
> working_directory(_,'/home/sp/smarthome/smarthome2/brain/rules'),
> consult('brain.pl'),
> brain_commandmode,
> write('Smarthome command mode\n').
> ------------------------ end snip -----------------------------------------
>
>
> There are couple of things I'd like to improve on this.
>
> 1. I use an environment variable PROLOG_HOME to point to the most
> recent installed version of Prolog and I don't believe environment
> variable substitution is supported on the first line.
>
> 2. I'd like to add the ability to pass a custom directory to chdir
> to (leaving the above path as a default).
>
> I'm actually more comfortable with Perl as a scripting language in
> terms of fancy command line args parsing, but haven't figured out
> how to write a perl script which can invoke prolog, define the
> main predicate above, execute it, and keep me at a Prolog prompt.
> I'd actually take the change of working directory out of the Prolog
> part and do that in the perl before Prolog is launched. I'd like to
> keep the definition of the main predicate in the perl script itself
> and not need another file to store it in.
>
> Has anyone done something similar and can get me started?
>
> Steve
>
> ------------
> For further info, please visit http://www.swi-prolog.org/
>
> To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
> in its body to [email protected]
>
>

you can use in perl the command system
system("$PL_HOME/bin/pl",$arg1,$arg2) (perldoc -f system for the details)
to call prolog
If I was you I'll put the definition of your goal predicate in one huge
string and then I'll pass it as an argument of the system command using "-g"

Good luck

Djamé

------------
For further info, please visit http://www.swi-prolog.org/

[May 7, 2007] BSF engine for Prolog

This page describes a BSF (Bean Scripting Framework) engine for JLog, a Prolog-in-Java system. JLog is a full-featured Prolog interpreter that can be run as an applet, an application or embedded through an API. You can download the full package, which includes JLog-1.3.5, here: JLog-1.3.5-ulf.zip. It's licensed under the GPL.

BSF enables a Java host program to call scripts or programs written in other languages in a language-neutral way. That means that a BSF-enabled application can

a) call scripts and programs written in other languages without knowing in advance in which language they might be (embedding), and

b) that any language for which a BSF engine is available can be used to script a BSF-enabled Java application (scripting).

Currently, BSF integration is available for JavaScript, XSLT, Jython, Python, Ruby, ObjectScript, NetRexx, TCL, Groovy and now for Prolog. BSF has been released under the Apache License and can be found at http://jakarta.apache.org/bsf/. It's also included in the download above.

[May 7, 2007] Upsh A Unix to Prolog Shell

We hope that the presented program will assist in the wider use of Prolog for

scripting and in building demonstrative, easy-to-use wrappers around standard

Prolog code. In the future it will be interesting to evaluate the impact of Upsh

on systems that provide drag and drop interaction.

Upsh runs on three dierent engines: SICStus, SWI and Yap. Its core func-

tionality should be easy to implement in other Prolog systems, such as CIAOand

GNU Prolog. Upsh is available from

http://www.cs.york.ac.uk/nicos/sware/upsh/

It is distributed in source form which experts in other engines can adopt.

Our reasons for not supporting more engines is lack of expertise and of available

time

[May 6, 2007] Public-domain Prolog library by Jocelyn Paine

Contains not only programs but also examples from several books including Source from Jocelyn's book "The Logic Programming Tutor"

Each entry is stored under its own directory, containing the following:

Note that the .descr files are usually based on comments and writeups supplied by the contributors. I have annotated them in some cases, e.g. where I've changed the code, but I have not rewritten them from scratch. Note also that some of the entries are quite old, and assumptions about user interfaces (e.g. use of windowing predicates), good programming practice, etc, may have changed in the meantime.

For some entries, I've also made a subdirectory called "files", and stored some or all of the source files there. I've done this where I think it's particularly convenient or educational to be able to pick and choose individual files via WWW; where the .descr file doesn't give a good example of the entry in use and the source files may help; or just where I think the files are interesting in their own right.

The rest of this page lists the contents of the library by topic. The listing for each entry contains links to the .descr and .tar.gz files, to the entry's FTP directory itself, and to the individual files if these exist.

[May 6, 2007] Artificial Intelligence through Prolog by Neil C. Rowe

E-book. Prentice-Hall, 1988, ISBN 0-13-048679-5

Table of Contents
Preface
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 12
Chapter 13
Chapter 14
Chapter 15
Appendix A
Appendix B
Appendix C
Appendix D
Appendix E
Appendix F
Appendix G
Some figures in crude form
Instructor's Manual, containing additional answers and exercises
Errata on the book as published

[May 6, 2007] [PDF] Prolog as description and implementation language in computer science teaching

Prolog is a powerful pedagogical instrument for theoretical elements of computer science when used as combined description language and experimentation tool. A teaching methodology based on this principle has been developed and successfully applied in a context with a heterogeneous student population with uneven mathematical backgrounds. Definitional interpreters, compilers, and other models of computation are defined in a systematic way as Prolog programs, and as a result, formal descriptions become running prototypes that can be tested and modified by the students.

These programs can be extended in straightforward ways into tools such as analyzers, tracers and debuggers. Experience shows a high learning curve, especially when the principles are complemented with a learning-by-doing approach having the students to develop such descriptions themselves from an informal introduction.

[May 6, 2007] Prolog Interpreter

[May 6, 2007] Syntax-Driven Semantic Analysis

Acknowledgement: This exercise was heavily inspired by Joakim Nivre.

The task for this assignment is to develop a simple grammar (essentially context-free) augmented with rules for compositional semantic interpretation. For the assignment we will use Prolog and the built-in grammar formalism DCG. The program handling semantic analysis will be given from the start, together with a grammar for a tiny fragment of English. Your task will be to add new grammar rules with semantic augmentations in order to handle more complex grammatical constructions in a semantically adequate fashion.

[May 6, 2007] FSSPL How to Order

[May 6, 2007] Grammars in Prolog by David Warren

Next we turn to more complex examples of Prolog programming. Prolog was originally invented as a programming language in which to write natural language applications, and thus Prolog is a very elegant language for expressing grammars. Prolog even has a builtin syntax especially created for writing grammars. It is often said that with Prolog one gets a builtin parser for free. In this section we will see why this claim is made (and sometimes contested).

Consider the following simple context-free grammar for a small fragment of English.

In this grammar we can derive such simple sentences as:

a man loves the woman
every woman walks
a woman likes the park

We can write a simple Prolog program to recognize this language, by writing a recursive descent parser. We first must decide how to handle the input string. We will use a list in Prolog. For each nonterminal we will construct a Prolog procedure to recognize strings generated by that nonterminal. Each procedure will have two arguments. The first will be an input parameter consisting of the list representing the input string. The second will be an output argument, and will be set by the procedure to the remainder of the input string after an initial segment matched by the nonterminal has been removed. An example will help clarify how this works. The procedure for np would, for example, take as its first argument a list [a,woman,loves,a,man] and would return in its second argument the list [loves,a,man]. The segment removed by the procedure, [a,woman], is an NP. The Prolog program is:

    s(S0,S) :- np(S0,S1), vp(S1,S).
    np(S0,S) :- det(S0,S1), n(S1,S).
    vp(S0,S) :- tv(S0,S1), np(S1,S).
    vp(S0,S) :- v(S0,S).
    det(S0,S) :- S0=[the|S].
    det(S0,S) :- S0=[a|S].
    det(S0,S) :- S0=[every|S].
    n(S0,S) :- S0=[man|S].
    n(S0,S) :- S0=[woman|S].
    n(S0,S) :- S0=[park|S].
    tv(S0,S) :- S0=[loves|S].
    tv(S0,S) :- S0=[likes|S].
    v(S0,S) :- S0=[walks|S].
The first clause defines procedure s, for recognizing sentences. An input list S0 is passed into procedure s, and it must set S to be the remainder of the list S after a sentence has been removed from the beginning. To do that, it uses two subprocedures: it first calls np to remove an NP, and then it calls vp to remove a VP from that. Since the grammar says that an S is an NP followed by a VP, this will do the right thing. The other rules are exactly analogous.

Having put this program in a file called grammar.P, we can load and execute it on our example sentences as follows:

% xsb
XSB Version 1.4.1 (94/11/21)
[sequential, single word, optimal mode]
| ?- [grammar].
[Compiling ./grammar]
[grammar compiled, cpu time used: 1.14 seconds]
[grammar loaded]

yes
| ?- s([a,man,loves,the,woman],[]).

yes
| ?- s([every,woman,walks],[]).

yes
| ?- s([a,woman,likes,the,park],[]).

yes
| ?- s([a,woman,likes,the,prak],[]).

no
| ?-
When the string is in the language of the grammar, the program will execute successfully through to the end, and the system produces `yes'. If the string is not in the language, as in the final example where `park' was misspelled, the system answers `no'. We called the s procedure with the input string as first argument and we gave it the empty list as second argument, because we want it to match the entire input string, wiht nothing left over after seeing an s.

The grammar above is called a Definite Clause Grammar (DCG) and Prolog supports a special rule syntax for writing DCGs. The syntax is simpler, much closer to the syntax one uses in writing context-free grammar rules. When using the DCG syntax, the programmer doesn't have to write all the string variables threaded through the nonterminal procedure calls; the compiler will do it. Here following is the same Prolog program as above, but witten as a DCG:

    s --> np, vp.
    np --> det, n.
    vp --> tv, np.
    vp --> v.
    det --> [the].
    det --> [a].
    det --> [every].
    n --> [man].
    n --> [woman].
    n --> [park].
    tv --> [loves].
    tv --> [likes].
    v --> [walks].
Notice that these ``procedure definitions'' use the symbol --> instead of :- to separate the procedure head from the procedure body. The Prolog compiler converts such rules to (almost) exactly the program above, by adding the extra arguments to the predicate symbols and treating the lists as terminals. The ``almost'' is because it really translates, for example, a single word list [loves] above to the procedure call 'C'(S0,loves,S), and includes the definition of this new predicate as:
    'C'([Word|String],Word,String).
This gives exactly the same effect as the Prolog program for the grammar given above.

Consider another example grammar, this one for simple arithmetic expressions over integers with operators + and *:

expr --> term, addterm.
addterm --> [].
addterm --> [+], expr.
term --> factor, multfactor.
multfactor --> [].
multfactor --> [*], term.
factor --> [I], {integer(I)}.
factor --> ['('], expr, [')'].
There are several things to note about this DCG. Notice that the list entries, representing terminals, need not appear alone on right-hand-sides of DCG rules, but may accompany nonterminals. Also notice the first rule for factor; it has a variable (I) in a list, which will cause it to be matched with, and thus set to, the next input symbol. The following procedure call is enclosed in braces. This means that it matches no input symbols and so its translation to Prolog does NOT result in the string variables being added. It remains just a call to the Prolog procedure with one argument: integer(I). The integer procedure is a Prolog builtin which tests whether its argument is an integer. Note also that we must quote the parentheses in the final rule. Otherwise, Prolog's reader would not be able to parse them correctly as atoms.

Consider some example executions of this grammar:

% xsb
XSB Version 1.4.1 (94/11/21)
[sequential, single word, optimal mode]
| ?- [grammar].
[Compiling ./grammar]
[grammar compiled, cpu time used: 1.309 seconds]
[grammar loaded]

yes
| ?- expr([4,*,5,+,1],[]).

yes
| ?- expr([1,+,3,*,'(',2,+,4,')'],[]).

yes
| ?- expr([4,5,*],[]).

no
| ?-

This grammar is not the most obvious one to write down for this expression language. It is specially constructed to avoid being left recursive. We mentioned above that we were writing a recursive descent parser for the grammar, and that is what one gets for a DCG from Prolog's execution strategy. Prolog execution of the underlying deterministic machines and its use of a stack to schedule them naturally yields a recursive descent parser. And it is well known that a recursive descent parser cannot handle left-recursive grammars; it will go into an infinite loop on them. So in Prolog we must avoid left-recursive grammars.

Also a recursive descent parser can be quite inefficient on some grammars, because it may re-parse the same substring many times. In fact, there are grammars for which recursive descent parsers take time exponential in the length of the input string. When using DCGs in Prolog, the programmer must be aware of these limitations and program around them. It is for this reason that some people respond to the claim that ``You get a parser for free with Prolog'' with ``Maybe, but it's not a parser I want to use.''

(Another example for adding arguments and using word/3 instead of strings?).

[May 6, 2007] perl.com Logic Programming with Perl and Prolog by Robert Pratte

See also a nice introduction to Prolog-in-Perl
Computing languages can be addictive; developers sometimes blame themselves for perceived inadequacies, making apologies for them. That is the case, at least, when one defends his or her language of choice against the criticism of another language's devotee. Regardless, many programmers prefer one language, and typically ground that preference in a respect for that language's strengths.

Perl has many strengths, but two most often cited are its adaptability and propensity to work as a "glue" between applications and/or data. However, Perl isn't the only advantageous language: programmers have used C or even assembly to gain speed for years, and intelligent use of SQL allows the keen coder to offload difficult data manipulations onto a database, for example.

Prolog is an often overlooked gem that, when combined with the flexibility of Perl, affords the coder powerful ways to address logical relationships and rules. In this article, I hope to provide a glimpse of the benefits that embedded Prolog offers to Perl programmers. Moreover, I hope that my example implementation demonstrates the ease with which one can address complex logical relationships.

A Bit About Prolog

For the sake of demonstration, I would like to frame a simple problem and solution that illustrate the individual strengths of Perl and Prolog, respectively. However, while I anticipate that the average reader will be familiar with the former, he or she may not be as familiar with the latter. Prolog is a logic programming language often used in AI work, based upon predicate calculus and first developed in 1972. There are several excellent, free versions of Prolog available today, including GNU Prolog and the popular SWI Prolog. For the Prolog initiate, I recommend checking out some of the free Prolog tutorials, either those linked from Wikipedia or from OOPWeb.

Prolog and Perl aren't exactly strangers, however. There are several excellent Perl modules available to allow the coder to access the power of Prolog quite easily, including the SWI module developed by Robert Barta, the Interpreter module by Lee Goddard, the Yaswi modules developed by Salvador Fandino Garcia, and the AI::Prolog module written by Curtis "Ovid" Poe. Poe has also recently provided a rather nice introduction to Prolog-in-Perl in an online-accessible format.

The Problem

There are many advantages to using Prolog within Perl. In the general sense, each language has its own advantages, and can thus complement the other. Suppose that I am building a testing harness or a logic-based query engine for a web application, where neither language easily provides all of the features I need. In cases such as these, I could use Prolog to provide the logic "muscle," and Perl to "glue" things together with its flexibility and varied, readily available modules on CPAN.

In my simple demonstration, I am going to posit the requirement that I take genealogical information built by another application and test relationships based upon a set of rules. In this case, the rules are defined in a Prolog file (an interesting intersection here is that both Perl and Prolog typically use the suffix .pl), while the genealogical information is contained in a Dot file readable by Graphviz. As such, I am going to make certain assumptions about the format of the data. Next, I am going to assume that I will have a query (web-based, or from yet another application) that will allow users to identify relationships (such as brothers, cousins, etc.).

[May 6, 2007] An Introduction to Language Processing with Perl and Prolog

Contains 54 pages intro to Prolog as Appendix A which is available online.

[May 6, 2007] Dr. Dobb's AI Expert Newsletter - October 2005 October 6, 2005

By coincidence, considering the previous feature on Gawk, I found a Prolog implementation of regular expressions. It's by Robert Cameron and makes a nice example of symbolic computing in Prolog and a clear specification of regular expression semantics. There are two stages: the first uses Definite Clause Grammars to parse regular expressions into trees, and the second matches strings against the trees. This example combines both stages

www.cs.sfu.ca/people/Faculty/cameron/Teaching/384/99-3/regexp-plg.html - Perl Style Regular Expressions in Prolog, by Robert Cameron, Simon Fraser University.

www.let.rug.nl/~vannoord/prolog-rx/PrologAndRegex.html - Prolog and Regular Expressions, by Gertjan van Noord. Ten or so links to regular expression software for various Prolog systems. Amongst them is a link to van Noord's Elex scanner generator, which generates lexical analysers in various languages, including Prolog. The page also links to his Finite-State Automata Utilities, of interest because transforming regular expressions into finite-state automata is a standard implementation technique - see James Power's Notes on Formal Language Theory and Parsing at www.cs.may.ie/~jpower/Courses/parsing/node8.html. Van Noord's utilities include some powerful software for displaying automata as graphs, and an extension which allows arcs in the automata to be labelled with predicates.

en.wikipedia.org/wiki/Regular_expression - Wikipedia entry for regular expressions.

[May 5, 2007] Prolog and Regular Expressions

[May 4, 2007] Learn Prolog Now! Argh! at Holy Shmoly!

Learn Prolog Now! is an introductory course to programming in Prolog. The online version has been available since 2001, and now there is also a throughly revised version available in book form.

[May 3, 2007] Logic Programming in Perl - search.cpan.org

At this point, it's worth having a bit of a digression to explain how this works.

Many deductive systems in artificial intelligence are based on two algorithms: backtracking and unification. You're probably already familiar with backtracking from regular expressions. In fact, regular expressions are very similar to Prolog in that you specify a pattern for your data and let the regex engine worry about how to do the matching.

In a regular expression, if a partial match is made, the regex engine remembers where the end of that match occurred and tries to match more of the string. If it fails, it backtracks to the last place a successful match was made and sees if there are alternative matches it can try. If that fails, it keeps backtracking to the last successful match and repeats that process until it either finds a match or fails completely.

Unification, described in a fit of wild hand-waving, attempts to take two logical terms and "unify" them. Imagine you have the following two lists:

 ( 1, 2, undef, undef,     5 )
 ( 1, 2,     3,     4, undef )

Imagine that undef means "unknown". We can unify those two lists because every element that is known corresponds in the two lists. This leaves us with a list of the integers one through five.

 ( 1, 2, 3, 4, 5 )

However, what happens if the last element of the first list is unknown?

 ( 1, 2, undef, undef, undef )
 ( 1, 2,     3,     4, undef )

We can still unify the two lists. In this case, we get the same five element list, but the last item is unknown.

 ( 1, 2, 3, 4, undef )

If corresponding terms of the two lists are both bound (has a value) but not equal, the lists will not unify:

 ( 1, 23, undef, undef, undef )
 ( 1,  2,     3,     4, undef )

Logic programming works by pushing these lists onto a stack and walking through the stack and seeing if you can unify everything (sort of). But how to unify from one item to the next? We assign names to the unknown values and see if we can unify them. When we get to the next item in the stack, we check to see if any named variables have been unified. If so, the engine will try to unify them along with the other known variables.

That's a bad explanation, so here's how it works in Prolog. Imagine the following knowledge base:

 parent(sally, tom)
 parent(bill, tom)
 parent(tom, sue)
 parent(alice, sue)
 parent(sarah, tim)
 
 male(bill)
 male(tom)
 male(tim)

Now let's assume we have a rule that states that someone is a father if they are a parent and they are male.

 father(Person) :-
   parent(Person, _),
   male(Person).

In the above rule, the underscore is called an "anonymous vairable" and means "I don't care what this value is." Prolog may still bind the variable internally (though this behavior is not guaranteed), but its value will not be taken into account when trying to determine if terms unify.

Taking the first term in the rule, the logic engine might try to unify this with the first fact in the knowledge base, parent(sally, tom). Person unifies with sally. The underscore, _, unifies with tom but since we stated this unification is unimportant, we can ignore that.

We now have a fact which unifies with the first term in the rule, so we push this information onto a stack. Since there are still additional facts we can try, we set a "choice point" in the stack telling us which fact we last tried. If we have to backtrack to see a choice point, we move on to the next fact and try again.

Moving on to the next term in the rule, male(Person), we know that "sally" is unified to Person, so we now try to unify male(sally) with all of the corresponding rules in the knowledge base. Since we can't, the logic engine backs up to the last item where we could make a new choice and sees parent(bill, tom). Person gets unified with bill. Then in moving to the next rule we see that we unify with male(bill). Now, we check the first item in the rule and see that it's father(Person). and the logic engine reports that bill is a father.

Note that we can then force the engine to backtrack and by continuously following this procedure, we can determine who all the fathers are.

And that's how logic programming works. Simple, eh? (Well, individual items can be lists or other rules, but you get the idea).

CS 251 Syllabus by Week by Xindong Wu

Artificial Intelligence: A Modern Approach, Second Edition, by Stuart Russell and Peter Norvig, Prentice-Hall, 2003, ISBN: 0-13-790395-2.

Lecture Notes by Serguei Krivov: Ontologies and Data Integration

Programming Language Concepts by Sidney Marshall

prolog

Paul Brna's Prolog Programming - A First Course pspdf html (at original location)

Discussion WEB Pages

Worse is Better

Richard P. Gabriel

http://www.dreamsongs.com/
http://www.dreamsongs.com/WorseIsBetter.html
http://www.dreamsongs.com/WIB.html

My Programming Language Crisis
Keith Waclena <[email protected]>

http://www.lib.uchicago.edu/keith/crisis/

[Oct 30, 2006] Open Source Rule Engines Written In Java - Manageability

JLog - JLog is an implementation of a Prolog interpreter, written in Java. JLog is a BSF-compatible language. It includes built-in source editor, query panels, online help, animation primitives, and a GUI debugger.

Perl Style Regular Expressions in Prolog CMPT 384 Lecture Notes. Robert D. Cameron. November 29 - December 1, 1999

Case Study: Implementing Perl Style Regular Expressions

A Prolog system for processing Perl style regular expressions can be implemented via the following steps.

  1. Defining the BNF grammar of Perl-style regular expressions.

  2. Defining a Prolog representation of Perl regular expressions.

  3. Build a DCG parser for Perl regular expressions.

  4. Building a regular expression matcher in Prolog.

This is a useful case study of symbolic computing in Prolog and also an exploration of the semantics of regular expressions.

XP-Projektgruppe 2004 Coding Conventions Prolog

Predicate names, formal:

Predicate names, semantic:

Predicates intended for "private" use only:

Dynamic Predicates

Predicates processing lists / sets of elements:

check_statements(Pred, []).
check_statements(Pred, [Head|Tail]) :-
check_statement(Pred,Head),
check_statements(Pred, Tail).

check_statement(Pred,Head) :- ...

Variables:

Comments:

Line breaking:

mortal(X) :-
alive(X).

example_with_long_parameter_list :-
findall( X,
(long(Z,X), conjunction(X), of(X,Y), predicates(X)),
Result
),
next_predicate(Result).

mortal(X):-alive(X).

example_with_long_parameter_list :-
findall( X, (long(Z,X), conjunction(X), of(X,Y),
predicates(X)),Result),
next_predicate(Result).

Untitled Document

The birth of Prolog, with Philippe Roussel, draft of a paper in History of Programming Languages, édited by Thomas J. Bergin and Richard G. Gibson, ACM Press/Addison-Wesley, 1996. Abstract. The programming language, Prolog, was born of a project aimed not at producing a programming language but at processing natural languages; in this case, French. The project gave rise to a preliminary version of Prolog at the end of 1971 and a more definitive version at the end of 1972. This article gives the history of this project and describes in detail the preliminary and then the final versions of Prolog. The authors also felt it appropriate to describe the Q-systems since it was a language which played a prominent part in Prolog's genesis.19november92.pdf

[May 29, 2005] The Ciao Prolog Development System WWW Site

Ciao is a public domain, next generation multi-paradigm programming environment with a unique set of features:

Ciao is distributed under the GNU Library General Public License (LGPL).

[May 25, 2005] Prolog Parsers

A study of the efficiency of various parsing techniques in Prolog, e.g. top-down, bottom-up, oracles, prediction, left-corner, chart. Also a comparison with Lisp. Examples in Prolog and Lisp.

Prolog Comparison

What Prolog do I Need?

Simple Text Parser - An implementation of a parser in LPA Prolog as well as a report about this parser.

Mixtus, an automatic partial evaluator for full Prolog Dan Sahlin

My thesis named An Automatic Partial Evaluator for Full Prolog is also available free of charge. The manual page for Mixtus is now also available on-line.

[Jan 24 1994] Visual Prolog Appeared in Volume 7/2, May 1994 [email protected] David "S." Joerg

I was wondering if there are any academic or commercial visual LP languages and/or development environments.
[email protected]
Lindsey Spratt
25th January 1994 
I am working on a visual LP language based on sets and partitioning constraints (which I currently call SPARCL) for my PhD research. I presented a brief paper on this, "A Visual Logic Programming Language Based on Sets and Partitioning Constraints." by Lindsey Spratt (myself) and Allen Ambler (my advisor), at the IEEE Symp. on Visual Languages in Bergen, Norway, in June of 1993.

Below is the visual LP languages discussion in the "related work" section of my dissertation proposal, which gives my understanding of the state of the art. (One additional note, someone told me that the CUBE language is now being implemented using LDL. Since LDL handles sets explicitly, does this mean that CUBE will handle sets visually?)

Visual programming languages that have logic programming paradigm semantics include: "Predicates and Pixels" [1], CUBE [2], Pictorial Janus [3], VLP [4], VPP [5], Mpl [6] (which is actually a constraint logic language, based on CLP(R) [7]), and picture LP [8].

Of the various kinds of visual languages, the visual logic languages are of most interest to the SPARCL project. They differ importantly from SPARCL in that none of them make use of sets (or partitions of sets). Also, they have very limited or nonexistent meta-programming capabilities. Only CUBE and Pictorial Janus are completely visual environments; the others rely on linear textual presentations of code in certain situations. Mpl is a combination of a straight linear textual Prolog plus a two- dimensional presentation of matrices, intermingled in the linear presentation. Mpl introduces novel pattern matching techniques for matrices which may have some analog in SPARCL.

There has been some work in visualizing logic programs, which is distinct from a visual programming language. The Transparent Logic Machine (TLM) [9] and the AND/OR graph-based system of Senay and Lazzeri [10] are examples of this. TLM offers another approach to representing logic graphically which may be useful to SPARCL.

In a somewhat different vein, Peirce presented a diagrammatic representation of logic. He proposed this as an alternative to linear textual representation of first order logic. John Sowa proposed a diagrammatic representation for higher order logic, conceptual graphs, in [11]. There is a current effort to implement a system which uses Peirce's diagrammatic logic in conjunction with Sowa's. This system is more of a theorem proving environment than a programming language environment.

Bibliography

[1] Ringwood 1989 "Predicates and Pixels" by G. Ringwood in New Generation Computing, 7, 1989, pp. 59-70.

[2] "The CUBE Language" by Marc A. Najork and Simon M. Kaplan. Pages 218 to 224 in Proceedings of the 1991 IEEE Workshop on Visual Languages, October 8-11, 1991, Kobe, Japan. IEEE Computer Society Press:Los Alamitos, CA. 1991.

[3] "Complete Visualizations of Concurrent Programs and their Executions" by Kenneth M. Kahn and Vijay A. Saraswat. Pages 7 to 15 in Proceedings of the 1990 IEEE Workshop on Visual Languages, October 4-6, 1990, Skokie, Illinois. IEEE Computer Society Press: Los Alamitos, CA. 1990.

[4] "VLP: A Visual Logic Programming Language" by Dider Ladret and Michel Rueher in Journal of Visual Languages and Computing (1991) 2, 163-188.

[5] "Visual Logic Programming" by L. F. Pau and H. Olason in Journal of Visual Languages and Computing (1991) 2, 3-15.

[6] "Mpl - a graphical programming environment for matrix processing based on logic and constraints" by Ricky Yeung, in IEEE Workshop of Visual Languages, pages 137- 143. IEEE Computer Society Press, October 1988.

[7] "The CLP(R) Programmer's Manual", Version 1.2 by Nevin C. Heintze, Joxan Jaffar, Spiro Michaylov, Peter J. Stuckey, and Roland H. C. Yap. This manual is distributed with version 1.2 of CLP(R) by Joxan Jaffar at the IBM Thomas J. Watson Research Center. This manual is dated September 1992.

[8] "Pictures Depicting Pictures: On the Specification of Visual Languages by Visual Grammars" by Bernd Meyer. Pages 41-47 in Proceedings of the 1992 IEEE Workshop on Visual Languages September 15-18, 1992, Seattle, Washington. IEEE Computer Society Press:Los Alamitos, CA. 1992.

[9] "The Transparent Prolog Machine (TPM): an execution model and graphical debugger for LP" by M. Eisenstadt and M. Brayshaw. In Journal of Logic Programming, 5 (4), 1988.

[10] "Graphical Representation of Logic Programs and Their Behavior" by Hikmet Senay and Santos G. Lazzeri. Pages 25 to 31 in Proceedings of the 1991 IEEE Workshop on Visual Languages, October 8-11, 1991, Kobe, Japan. IEEE Computer Society Press:Los Alamitos, CA. 1991.

[11] "Conceptual Structures - Information Processing in Mind and Machine" by John A. Sowa. Reading MA: Addison-Wesley. 1984.

[email protected] 
Alan Westwood
25th January 1994 
We (LPA) have a visual programming tool called MacObject that runs under MacProlog and enables the graphical design of Prolog++ (Object Oriented Prolog extension) programs. For more information, contact: Clive Spenser Marketing Director Email [email protected]
[email protected]
Jocelyn Paine
25th January 1994  
David "S." Joerg writes:

I was wondering if there are ANY academic or commercial projects

Yes, it was described in a volume of 1993 LP proceedings, near the end, in a one-page reprint of one of the posters in the conference's poster session. The title was something like 'A visual logic for spatial reasoning'.

The idea is that you write standard Prolog code, but you can have 'picture terms' as well as ordinary terms.

The researchers had been investigating various classes of pictures. The first class they tried was too general to allow efficient unification, because the unification mechanism had to do an exhaustive search for subgraph isomorphism between components of the pictures being unified. However, they've since defined a more restricted class of pictures which avoid this problem.

[email protected]
Paul Holmes-Higgin
25th January 1994 
I'm aware of visual programming languages, but what I'd really like is a Prolog version of MS's Visual Basic as a development environment, not just a tool for designing GUIs and simply linking to Prolog. Is anyone doing this?
[email protected] 
Jan Wielemaker
27th January 1994 
More of less. I'm working on an environment that lets you graphically build a GUI and define the behaviour of this GUI. This is running on top of XPCE (ProWindows-3). While defining the behaviour, the behaviour-diagram is interpreted to generate the behaviour of the GUI. (Graphical) links can be made to Prolog predicates to be called by the interface. The environment will define a clause-skeleton (including arguments) which you may then further refine.

When completed, you simply drag the interface to the source-editor and it will insert the Prolog code to generate the interface.

[email protected]
Norbert E. Fuchs
27th January 1994  
Markus Fromherz, a PhD student of mine, developed graphical editors for designing finite state machines and window-oriented user interfaces that were translated to and from an object-oriented extension of Prolog.
[email protected]
Paul Holmes-Higgin
10th February 1994 
XPCE has just gained a new tool, still under beta test, for defining dialog boxes. It has drag and drop drawing of buttons, menus, edit items etc., with popup refinements on each dialog item; drag the dialog window name to an editor and it dumps the specification in Prolog source. The tool is called Visual Prolog.

What makes it really interesting is its behaviour editor. Drag the dialog items to this and you can define the functional interaction of the dialog boxes and their callbacks to Prolog. "Run" the behaviour model, do something in the dialog box - then watch the process run visually.

[email protected]
Jan Wielemaker
11th February 1994 
For those unfamiliar with XPCE, here is a short description.

XPCE is a generic GUI library for symbolic languages and C++ (although the Prolog environment is superior to the Lisp and C++ ones). It provides support for dialog windows, graphics (notably support for graphical diagramming languages and direct- manipulation graphics), text manipulation (there is PceEmacs written in XPCE/Prolog that can be extended in Prolog), interprocess and network communication, etc.

Most of the documentation is available under anonymous FTP from:
ftp://swi.psy.uva.nl/pub/xpce

XPCE runs on a number of Unix machines: SunOs 4.1.x and 5.[23], AIX 3.2, IRIX and Linux are well maintained, Ultrix and HP-UX may be a bit rusty.

XPCE was connected to SWI-Prolog originally, and later to SICStus and Quintus Prolog. The latter version is commercially distributed as ProWindows-3 and supported. It is available from AIIL (uk), who can be contacted at: [email protected]

Unsupported academic versions are available from SWI. The licence form and ordering info is on the ftp server. If you don't have ftp, contact: [email protected].

A free (binary only) demo version is available for the PC/Linux platform from the ftp server (pub/xpce/linux). To be of any use, you need at least 8 MB on your Linux box and 33Mhz 486 or up. Using a 66DX2 and 16 MB it runs like a dream.

The Visual Prolog beta code is integrated in the academic and demo distribution. It will be distributed as a demonstration-tool in the next ProWindows-3 release.

Is the ISO Prolog standard taken seriously

I read comp.lang.prolog regularly, I subscribed the "users" mailing list for several major Prolog programming systems, and I regularly visit the WWW sites dedicated to logic programming. But I have never seen somebody complaining because some Prolog vendor/provider was ignoring the standard. So, unless something important has escaped my attention, the above question is legitimate. After all, a standard that nobody cares about, in practice, does not exist.

With this note I intend to solicit opinions from everybody in the community: a question like this must not pass under silence and an answer, any answer, can save the time of many people.

Syntax: SICStus Prolog versus ISO Prolog

The following is quoted from the "SICStus Prolog User's Manual", release 3.7, October 1988:
SICStus Prolog complies in spirit, if not in detail, with the Draft International Standard ISO/IEC 13211-1 (PROLOG: Part 1--General Core). In particular, SICStus Prolog does not offer a strictly conforming mode which rejects uses of implementation specific features. Minor deviations also concern e.g. the syntax, the arithmetic functions, and the error system. To aid programmers who wish to write standard compliant programs, built-in predicates that have a counterpart in the ISO Prolog Standard are annotated with [ISO] in this manual, where appropriate with a comment clarifying the difference between the SICStus and the prescribed ISO Prolog versions.
This is all what is said about the ISO standard. The user is not told what the minor syntactic deviations from ISO Prolog are (and similarly for the arithmetic functions).

A deviation that is all but minor is due to the following: in ISO Prolog an operator cannot immediately follow another operator. Thus a goal of the form X = '>' is not ISO Prolog (I have found similar goals in several real programs). In ISO Prolog one has to write X = (>) instead (bracketing allows an operator to be treated like an ordinary atom). Looking at this simple example the problem would not seem so serious. Consider the following one. SICStus CLP(FD) defines '!' as an operator. Namely, in SICStus CLP(FD) the declaration

:- op(600, xf, '!').
is in effect. This implies that a SICStus CLP(FD) clause of the form, say,
p :- !, q.
is not valid in ISO Prolog, standing the declaration of '!' as an operator ('!' and ',' are both operators, and thus one cannot immediately follow the other). In order to make it conformant one would have to write
p :- (!), q.
but does people want to write cuts this way? So the choice (and confirmation even in the last release) of '!' as an operator was an unfortunate one, from the point of view of standard conformance.

Up to now we have seen a couple of examples whereby, syntactically speaking, a SICStus Prolog program is not an ISO Prolog program. However, the reverse statement also holds. Consider escape sequences. In SICStus Prolog 3.7.1, you have:

| ?- name('abc\x20\def', X).

X = [97,98,99,32,127,101,102] ? 

yes
while with an ISO-conformant system you would get
| ?- name('abc\x20\def', X).

X = [97,98,99,32,100,101,102] ? 

yes
The problem stems from the fact that, in SICStus, an hexadecimal escape sequence is defined (on page 402 of the manual) by (+)
\xCD the character code CD (two hexadecimal digits)
while ISO specifies
  hexadecimal escape sequence (* 6.4.2.1 *) = 
    backslash char (* 6.5.5 *),
    symbolic hexadecimal char (* 6.4.2.1 *),
    hexadecimal digit char (* 6.5.2 *),
    { hexadecimal digit char (* 6.5.2 *) },
    backslash char (* 6.5.5 *) ;
Note the trailing backslash required by ISO: SICStus will not accept it as part of the hexadecimal escape sequence, and will interpret "\d" as a (non standard) control escape sequence for delete (ASCII 127). It is clear that the above definitions of hexadecimal escape sequence are not compatible. In other words, a SICStus user may have surprises when switching to an ISO-conformant system. Similarly, a program written for ISO Prolog can be interpreted by SICStus as a different program.

(Indeed, SICStus 3.7.1, the latest version, will accept just anything. For example, the query X = '\xzz' gives the answer X = 'S'. This is the kind of "feature" that is able to transform a simple typing mistake in a week of frustrating debugging work.)

Things LP users should take into account

No Prolog vendor/provider can guarantee that his system will continue to be supported forever, or that it will be able to take advantage of future processing devices, or that it will be conveniently ported to other platforms, or anything like that. Usage of non-standard features of the implemented systems is thus a risky operation. A standard that is not only on paper is on the interest of users. It allows them not to be tied to any particular vendor/provider, it provides a whole lot of good, complete documentation (the lack of complete documentation is one of the problems of most LP systems), it greatly improves portability, it enables the use of tools coming from different sources, it brings to the development of better software environments, and, ultimately, it secures the investments done in software development.

It may well be the case that ISO Prolog is not the best possible standard: no standard I know enjoys this property. Indeed, there are several things that I do not like in ISO Prolog. But I believe that it is a reasonable compromise. Moreover, I do believe that following ISO Prolog is much, much better than following no standard at all.

These considerations seem to be part of the common knowledge of other communities. I follow quite closely the C++ standardization process and the development of g++ (the GNU C++ compiler). I must say that the entire C++ community (users and providers) really strive for standard conformance. As far as I can see, providers do not hesitate to break backward compatibility (even though this is done in two or more steps), and users are more than willing to catch up by modifying their programs for the sake of standardization.

I apologize to those who, like myself, regard the above sentences as overwhelmingly obvious. I really do hope that the discussion will prove they were superfluous.

Conclusion

In my opinion, the bottom line is:
  1. Does the logic programming community want to have a standard?
  2. If so, is ISO Prolog the "right" standard?
  3. If ISO Prolog is not the "right" standard, why?

Tutorials

An Introduction to PROLOG - Prolog tutorials by James Power. Revised Alex Monaghan.

Good short tutorial that really tries to explain the language not to obscure it.

An introduction to Prolog - A short introduction to Prolog by Michel Loiseleur and Nicolas Vigier.

Prolog Tutorial -- Contents by J.R.Fisher

Programming in Tabled Prolog (very) DRAFT 1 by David S. Warren

Prolog Programming: A First Course, an on-line book for a short Prolog course by Paul Brna.

Adventure in Prolog
Prolog book is aimed at programmers who wish to add it as a tool for games programming.

Prolog Guide - Contents by Roman Barták

An Introduction to Prolog (PDF format)

ProgrammingProlog - Wikibooks

James Power - Prolog Tutorials The tutorials were prepared by James Power in 1995, and enhanced and modified by Alex Monaghan in 1996, but are released under the GNU Free Documentation License. If you'd like to copy the tutorials, a zip file of all of them might be useful.

Prolog Tutorial very short mini-tutorial

IC Prolog II on-line manual.

The Prolog Language -- small tutorial

Prolog Tutorials and Visual Prolog Tutorials

LPA Win-Prolog documentation Files

File Name File Size File Date Contents
AGT_REF.PDF 1,334,417 20-JUL-2004 Agent Toolkit
CBR_REF.PDF 1,359,078 20-JUL-2004 Case Based Reasoning Toolkit
DTM_API.PDF 1,804,322 20-JUL-2004 Data Mining Toolkit
FLN_REF.PDF 3,986,351 20-JUL-2004 Flint Fuzzy Logic Toolkit
FLX_EGS.PDF 976,658 20-JUL-2004 flex Examples
FLX_REF.PDF 1,746,677 20-JUL-2004 flex Reference
FLX_TUT.PDF 1,135,482 20-JUL-2004 flex Tutorial
INT_REF.PDF 1,335,189 20-JUL-2004 Intelligence Server
PDI_REF.PDF 1,071,267 20-JUL-2004 ProData Database Interface
PPP_REF.PDF 1,463,910 20-JUL-2004 Prolog++ Reference
PWS_REF.PDF 2,848,891 20-JUL-2004 ProWeb Server Reference
TCP_REF.PDF 1,461,151 20-JUL-2004 TCP/IP Reference
VSR_REF.PDF 1,546,769 02-MAR-2005 VisiRule Reference
WELCOME.PDF 873,653 20-JUL-2004 Welcome Document
WFS_REF.PDF 2,000,637 20-JUL-2004 WebFlex Server Reference
WIN_EGS.PDF 2,399,442 20-JUL-2004 WIN-PROLOG Examples
WIN_PRG.PDF 1,503,109 20-JUL-2004 WIN-PROLOG Programming Guide
WIN_REF.PDF 12,904,100 20-JUL-2004 WIN-PROLOG Reference
WIN_TUT1.PDF 971,341 04-FEB-2005 WIN-PROLOG Tutorial 1
WIN_TUT2.PDF 1,090,795 04-FEB-2005 WIN-PROLOG Tutorial 2
WIN_TUT3.PDF 1,087,401 04-FEB-2005 WIN-PROLOG Tutorial 3
WIN_TUT4.PDF 1,069,106 04-FEB-2005 WIN-PROLOG Tutorial 4
WIN_UPD.PDF 1,364,575 20-JUL-2004 WIN-PROLOG Update Notes
WIN_USR.PDF 4,001,215 20-JUL-2004 WIN-PROLOG User Guide

References

SICStus Prolog Homepage

Amzi! Prolog User's Guide and Reference

This document serves as a User's Guide and Reference Manual for Amzi! Prolog + Logic Server on all supported platforms. Any differences between the supported platforms are noted in the text.

The Amzi! Prolog implementation is ISO compliant which is based on the older, de-facto "Edinburgh Standard". The latter is described in the widely available text Programming in Prolog by William Clocksin and Christopher Mellish, published by Springer-Verlag, hereafter referred to as Clocksin & Mellish).

This document is not an introduction or tutorial for the Prolog programming language. For that, we offer Adventure in Prolog. For an advanced tutorial on expert systems, we offer Building Expert Systems in Prolog.

Recommended Links

Google matched content

Softpanorama Recommended

Top articles

Sites

Prolog - Wikipedia, the free encyclopedia

Open Directory - Computers Programming Languages Prolog

Logic Programming in Perl - search.cpan.org

Prolog and Regular Expressions

Programming Languages Prolog in the Yahoo! Directory

The Association of Logic Programming (ALP)

***** CMU Prolog Repository (large).

**** SWI-Prolog's Home

SICS Intelligent Systems Laboratory

techref - Prolog Alexei Morozov's page. See also Actor Prolog. Programming language definition.

comp.lang.prolog (also via Google) provides a forum for discussion.

Frequently Asked Questions -- old, largly outdated

See also:

The following may be of interest:

Usage of Prolog for exploring graph problems

Problem Solving and Search in AI

This kind of problem is often solved by a graph search method. We represent the problem as a set of

states
which are snapshots of the world and
operators
which transform one state into another
States can be mapped to nodes of a graph and operators are the edges of the graph. Before studying the missionaries and cannibals problem, we look at a simple graph search algorithm in Prolog. the missionaries and cannibals program will have the same basic structure.

Graph Representation

A graph may be represented by a set of edge predicates and a list of vertices.

	edge(1, 5).	edge(1, 7).
	edge(2, 1).	edge(2, 7).
	edge(3, 1).	edge(3, 6).
	edge(4, 3).	edge(4, 5).
	edge(5, 8).
	edge(6, 4).	edge(6, 5).
	edge(7, 5).
	edge(8, 6).	edge(8, 7).

	vertices([1, 2, 3, 4, 5, 6, 7, 8]).

Finding a path

	path(Start, Finish, Visited, Path).
Start
is the name of the starting node
Finish
is the name of the finishing node
Visited
is the list of nodes already visited.
Path
is the list of nodes on the path, including Start and Finish.

The Path Program

	path(Node, Node, _, [Node]).
	path(Start, Finish, Visited, [Start | Path]) :-
		edge(Start, X),
		not(member(X, Visited)),
		path(X, Finish, [X | Visited], Path).
Here is an example of the path algorithm in action.
Representing the state
Now we return to the problem of representing the missionaries anc cannibals problem:
	state(Missionaries, Cannibals, Side)
Representing the Solution
	[move(1, 1, right), move(2, 0, left)]
	[MostRecent_State | ListOfPreviousStates]
Overview of Solution
	state(0, 0, right).
Top-level Prolog Code
% mandc(CurrentState, Visited, Path)

mandc(state(0, 0, right), _, []).
mandc(CurrentState, Visited, [Move | RestOfMoves]) :-
	newstate(CurrentState, NextState),
	not(member(NextState, Visited)),
	make_move(CurrentState, NextState, Move),
	mandc(NextState, [NextState | Visited], RestOfMoves]).

make_move(state(M1, C1, left), state(M2, C2, right), move(M, C, right)) :-
	M is M1 - M2,
	C is C1 - C2.
make_move(state(M1, C1, right), state(M2, C2, left), move(M, C, left)) :-
	M is M2 - M1,
	C is C2 - C1.
Possible Moves
	carry(2, 0).
	carry(1, 0).
	carry(1, 1).
	carry(0, 1).
	carry(0, 2).
Feasible Moves
	M <= M1 and C <= C1
	M + M1 <= 3 and C + C1 <= 3
Legal Moves
	legal(X, X).
	legal(3, X).
	legal(0, X).
Generating the next state
newstate(state(M1, C1, left), state(M2, C2, right)) :-
	carry(M, C),
	M <= M1,
	C <= C1,
	M2 is M1 - M,
	C2 is C1 - C,
	legal(M2, C2).
newstate(state(M1, C1, right), state(M2, C2, left)) :-
	carry(M, C),
	M2 is M1 + M,
	C2 is C1 + C,
	M2 <= 3,
	C2 <= 3,
	legal(M2, C2).

The complete code, with instructions for use, is available at http://www.cse.unsw.edu.au/~billw/cs9414/notes/mandc/mandc.pro

Methods of Search

In the preceding example, the state space is explored in an order determined by Prolog. In some situations, it might be necessary to alter that order of search in order to make search more efficient. To see what this might mean, here are two alternative methods of searching a tree.

Depth first search begins by diving down as quickly as possible to the leaf nodes of the tree. Traversal can be done by:

There are many other search methods and variants on search methods. We do not have time to cover these in COMP9414, but you can find out about some of them in the text by Bratko. For example, chapter 12 deals with best-first search.

Some Simple Graph Problems

Consider the problem of finding connected components in a directed graph. Assume we have a node and we want to find all the nodes that are in the same connected component as the given node.

The first thought that comes to mind is: given a node X, find those nodes Y that are reachable from X and from which you can get back to X. So we will assume that edges are given by an edge/2 relation:

sameSCC(X,Y) :- reach(X,Z), reach(Z,Y).

:- table reach/2.
reach(X,X).
reach(X,Y) :- reach(X,Z), edge(Z,Y).

Indeed given a node X, this will find all nodes in the same strongly connected component as X, however it will in general take O(n*e) time, where n is the number of nodes and e is the number of edges. The reason is that given an X, there are n possible Z values and for each of them, we will find everything reachable from them, and each search can take O(e) time.

However, we can do better. It is known that this problem can be solved in O(e) time. The idea is, given a node X, to find all nodes reachable from X following edges forward. Then find all nodes reachable from X following edges backward (i.e., follow edges against the arrow.) Then intersect the two sets. That will be the set of nodes in X's SCC, because if Y is in both these sets, you can follow the edges forward from X to Y and then since there is also a backwards path from X to Y, there is forward path from Y to X, so you can get from X to Y and back to X following edges forward. So the program that does this is:

% sameSCC(+X,-Y)
sameSCC(X,Y) :- reachfor(X,Y), reachback(X,Y).

:- table reachfor/2, reachback/2.
reachfor(X,X).
reachfor(X,Y) :- reachfor(X,Z),edge(Z,Y).

reachback(X,X).
reachback(X,Y) :- reachback(X,Z),edge(Y,Z).

Let's now consider its complexity to see why it is O(e). For a fixed value X, the computation of the query reachfor(X,Y) takes O(e) time. Then we may have O(n) calls to reachback(X,Y) (one for each Y) but they all use one underlying call to reachback(X,_) which takes O(e) and is done only once. So when we add all that up (assuming a connected graph), we get O(e) time.

Prolog Tutorial -- 2.15

As an example, consider the following connected graph:


Fig. 2.15

The edges can be represented in Prolog as facts:

edge(1,2).
edge(1,4).
edge(1,3).
edge(2,3).
edge(2,5).
edge(3,4).
edge(3,5).
edge(4,5).

To represent the fact that the edges are bi-directional we could either add eight more 'edge' clauses (edge(2,1),etc.) or we could try a rule like:

 (*)      edge(X,Y) :- edge(Y,X).

This is not a good idea, however. To see why it is not a good idea, try the following goal.

?- edge(5,1).

Notice that the rule (*) will be tried over and over in an infinite loop, so the goal will not terminate. Try it! A better way to handle this is to use a rule such as the following.

connected(X,Y) :- edge(X,Y) ; edge(Y,X).

Note the use of disjunction ';' in this rule. This rule could have been written as two rules:

connected(X,Y) :- edge(X,Y).
connected(X,Y) :- edge(Y,X).

We wish to develop a Prolog definition which generates paths between any two nodes of the graph. More specifically, we require the following (kind of) behavior for the predicate 'paths'.

?- path(1,5,P).
P = [1,2,5] ;
P = [1,2,3,5] ;
P = [1,2,3,4,5] ;
P = [1,4,5] ;
P = [1,4,3,5] ;
P = [1,4,3,2,5] ;
P = [1,3,5] ;
P = [1,3,4,5] ;
P = [1,3,2,5] ;
no

The paths are represented by the list of nodes through which one must travel to get from node 1 to node 5. Here is a definition for paths:

path(A,B,Path) :-
       travel(A,B,[A],Q), 
       reverse(Q,Path).

travel(A,B,P,[B|P]) :- 
       connected(A,B).
travel(A,B,Visited,Path) :-
       connected(A,C),           
       C \== B,
       \+member(C,Visited),
       travel(C,B,[C|Visited],Path).  

A declarative reading for the first clause amounts to "A path from A to B is obtained if A and B are connected". A declarative reading for the second clause amounts to "A path from A to B is obtained provided that A is connected to a node C different from B that is not on the previously visited part of the path, and one continues finding a path from C to B". Avoiding repeated nodes ensures that the program will not cycle endlessly.

Exercise 2.15 Suppose that edges have lengths. How does one calculate shortest paths between points in Prolog?

Package lang-prolog-code-math-graph-

lang/prolog/code/math/graph/
This package contains two programs: one for decomposing a non-weighted directed graph into strongly connected components; and the other for finding simple and elementary cycles in a strongly connected component.
Origin:   

   src.doc.ic.ac.uk:packages/prolog-pd-software/ (146.169.2.1)
   as graph.tar.Z

SWI-Prolog 5.6.32 Reference Manual Section A.4

Authors: Richard O'Keefe & Vitor Santos Costa

Implementation and documentation are copied from YAP 5.0.1. The library(ugraph) library is based on code originally written by Richard O'Keefe. The code was then extended to be compatible with the SICStus Prolog ugraphs library. Code and documentation have been cleaned and style has been changed to be more in line with the rest of SWI-Prolog.

The ugraphs library was originally released in the public domain. YAP is convered by the Perl artistic license, which does not imply further restrictions on the SWI-Prolog LGPL license.

The routines assume directed graphs, undirected graphs may be implemented by using two edges.

Originally graphs where represented in two formats. The SICStus library and this version of library(ugraphs.pl) only uses the S-representation. The S-representation of a graph is a list of (vertex-neighbors) pairs, where the pairs are in standard order (as produced by keysort) and the neighbors of each vertex are also in standard order (as produced by sort). This form is convenient for many calculations. Each vertex appears in the S-representation, also if it has no neighbors.

vertices_edges_to_ugraph(+Vertices, +Edges, -Graph)
Given a graph with a set of Vertices and a set of Edges, Graph must unify with the corresponding S-representation. Note that the vertices without edges will appear in Vertices but not in Edges. Moreover, it is sufficient for a vertice to appear in Edges.
?- vertices_edges_to_ugraph([],[1-3,2-4,4-5,1-5], L).
L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[]]

In this case all vertices are defined implicitly. The next example shows three unconnected vertices:

?- vertices_edges_to_ugraph([6,7,8],[1-3,2-4,4-5,1-5], L).
L = [1-[3,5], 2-[4], 3-[], 4-[5], 5-[], 6-[], 7-[], 8-[]] ? 
vertices(+Graph, -Vertices)
Unify Vertices with all vertices appearing in graph Graph. Example:
?- vertices([1-[3,5],2-[4],3-[],4-[5],5-[]], L).
L = [1, 2, 3, 4, 5]
edges(+Graph, -Edges)
Unify Edges with all edges appearing in Graph. In the next example:
?- edges([1-[3,5],2-[4],3-[],4-[5],5-[]], L).
L = [1-3, 1-5, 2-4, 4-5]
add_vertices(+Graph, +Vertices, -NewGraph)
Unify NewGraph with a new graph obtained by adding the list of Vertices to the Graph. Example:
?- add_vertices([1-[3,5],2-[]], [0,1,2,9], NG).
NG = [0-[], 1-[3,5], 2-[], 9-[]]
del_vertices(+Vertices, +Graph, -NewGraph)
Unify NewGraph with a new graph obtained by deleting the list of Vertices and all the edges that start from or go to a vertex in Vertices to the Graph. Example:
?- del_vertices([2,1],
                [1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[2,6],8-[]],
                NL).
NL = [3-[],4-[5],5-[],6-[],7-[6],8-[]]
add_edges(+Graph, +Edges, -NewGraph)
Unify NewGraph with a new graph obtained by adding the list of edges Edges to the graph Graph. Example:
?- add_edges([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[],8-[]],
             [1-6,2-3,3-2,5-7,3-2,4-5],
             NL).
NL = [1-[3,5,6], 2-[3,4], 3-[2], 4-[5], 5-[7], 6-[], 7-[], 8-[]]
del_edges(+Graph, +Edges, -NewGraph)
Unify NewGraph with a new graph obtained by removing the list of Edges from the Graph. Notice that no vertices are deleted. In the next example:
?- del_edges([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[],8-[]],
             [1-6,2-3,3-2,5-7,3-2,4-5,1-3],
             NL).
NL = [1-[5],2-[4],3-[],4-[],5-[],6-[],7-[],8-[]]
transpose(+Graph, -NewGraph)
Unify NewGraph with a new graph obtained from Graph by replacing all edges of the form V1-V2 by edges of the form V2-V1. The cost is O(|V|^2). Notice that an undirected graph is its own transpose. Example:
?- transpose([1-[3,5],2-[4],3-[],4-[5],5-[],6-[],7-[],8-[]], NL).
NL = [1-[],2-[],3-[1],4-[2],5-[1,4],6-[],7-[],8-[]]
neighbours(+Vertex, +Graph, -Vertices)
Unify Vertices with the list of neighbours of vertex Vertex in Graph. Example:
?- neighbours(4,[1-[3,5],2-[4],3-[],
                 4-[1,2,7,5],5-[],6-[],7-[],8-[]], NL).
NL = [1,2,7,5]
neighbors(+Vertex, +Graph, -Vertices)
American version of neighbours/3.
complement(+Graph, -NewGraph)
Unify NewGraph with the graph complementary to Graph. Example:
?- complement([1-[3,5],2-[4],3-[],
               4-[1,2,7,5],5-[],6-[],7-[],8-[]], NL).
NL = [1-[2,4,6,7,8],2-[1,3,5,6,7,8],3-[1,2,4,5,6,7,8],
      4-[3,5,6,8],5-[1,2,3,4,6,7,8],6-[1,2,3,4,5,7,8],
      7-[1,2,3,4,5,6,8],8-[1,2,3,4,5,6,7]]
compose(+LeftGraph, +RightGraph, -NewGraph)
Compose, by connecting the drains of LeftGraph to the sources of RightGraph. Example:
?- compose([1-[2],2-[3]],[2-[4],3-[1,2,4]],L).
L = [1-[4], 2-[1,2,4], 3-[]]
ugraph_union(+Graph1, +Graph2, -NewGraph)
NewGraph is the union of Graph1 and Graph2. Example:
?- ugraph_union([1-[2],2-[3]],[2-[4],3-[1,2,4]],L).
L = [1-[2], 2-[3,4], 3-[1,2,4]]
top_sort(+Graph, -Sort)
Generate the set of nodes Sort as a topological sorting of graph Graph, if one is possible. A toplogical sort is possible if the graph is connected and acyclic. In the example we show how topological sorting works for a linear graph:
?- top_sort([1-[2], 2-[3], 3-[]], L).
L = [1, 2, 3]
top_sort(+Graph, -Sort0, -Sort)
Generate the difference list Sort-Sort0 as a topological sorting of graph Graph, if one is possible.
transitive_closure(+Graph, -Closure)
Generate the graph Closure as the transitive closure of graph Graph. Example:
 ?- transitive_closure([1-[2,3],2-[4,5],4-[6]],L).
L = [1-[2,3,4,5,6], 2-[4,5,6], 4-[6]]
reachable(+Vertex, +Graph, -Vertices)
Unify Vertices with the set of all vertices in graph Graph that are reachable from Vertex. Example:
?- reachable(1,[1-[3,5],2-[4],3-[],4-[5],5-[]],V).
V = [1, 3, 5]

Simply Logical - Table of Contents by Peter Flach

A ebook that has some coverage of Prolog usage for exploringgraph problems

SICStus Prolog

JSTOR: Using PROLOG in Discrete Mathematics

P-99: Ninety-Nine Prolog Problems

[PS] Drawing Graphs by Example Eciently: Trees and Planar Acyclic Digraphs

Implementations

Selected:

Multiplatform:

Commercial

Windows:

Java based:

Random Findings



Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotesSomerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose BierceBernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOSProgramming Languages History : PL/1 : Simula 67 : C : History of GCC developmentScripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-MonthHow to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D


Copyright © 1996-2021 by Softpanorama Society. www.softpanorama.org was initially created as a service to the (now defunct) UN Sustainable Development Networking Programme (SDNP) without any remuneration. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.

FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available to advance understanding of computer science, IT technology, economic, scientific, and social issues. We believe this constitutes a 'fair use' of any such copyrighted material as provided by section 107 of the US Copyright Law according to which such material can be distributed without profit exclusively for research and educational purposes.

This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...

You can use PayPal to to buy a cup of coffee for authors of this site

Disclaimer:

The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Created: November 1, 1996; Last modified: March 12, 2019