|
|
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 | |||||||
| >> 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 IIn 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):
- Was George I the parent of Charles I?
Query: parent(charles1, george1).- Who was Charles I's parent?
Query: parent(charles1, Parent).- Who were the children of Charles I?
Query: parent(Child, charles1).
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.htmlThe 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
|
|
Switchboard | ||||
| Latest | |||||
| Past week | |||||
| Past month | |||||
 |
 |
 |
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
|
|
|
- at http://www.let.rug.nl/~vannoord/prolog-rx/ there is a very simple straightforward interface to the ISO regular expression functions regcomp(3), regexec(3), regfree(3), regerror(3). Tested for SICStus Prolog, should work for Prologs with similar foreign language interface. GPL.
- two similar implementations are available from
- ftp://ftp.rahul.net/pub/tom/ftp/regex.tar.gz (for Quintus)
- http://fivedots.coe.psu.ac.th/~ad/re/ (uses external program which itself is a simple wrapper around regexp functions).
- similar functionality is built-in in IF-Prolog, for info consult http://www.ifcomputer.de/Products/IFProlog/home_en.html
- recent versions of YAP include a regular expression library.
- it's also present in XPCE, which is a graphical user-interface sometimes used with SWI-Prolog. http://www.swi-prolog.org
- Ciao Prolog (Gnu-copyright) has a library for regular expression matching. http://clip.dia.fi.upm.es/Software/Ciao/.
- K-Prolog has regular expressions too. http://prolog.isac.co.jp/doc/en/feature/reg_match.html
- MINERVA has regular expressions too, cf http://www.ifcomputer.co.jp/MINERVA/Manual/Reference/Predicates/regexp/ . MINERVA (proprietory, commercial, ISO-Prolog compiler in 100% Java) home is http://www.ifcomputer.co.jp/MINERVA.
- there is also a large package with finite-state utilities, all implemented in SICStus Prolog, called FSA Utilities. It contains a regular expression compiler, all kinds of operations on finite state acceptors, weighted finite-state acceptors and finite state transducers. Operations include determinization, minimization, visualization etc. There is support to add your own regular expression operators. Etc. Etc. The latest addition is a compiler of sequential (`deterministic') finite state transducers into a C program which computes the transduction (line by line). It's about 100 times faster than the built-in transduction option of FSA. Available (GPL) from http://www.let.rug.nl/~vannoord/Fsa/ there is a very small and very experimental web demo at http://www.let.rug.nl/~vannoord/fsademo/ the user manual is available as http://www.let.rug.nl/~vannoord/Fsa/Manual/
- another implementation of (extended) regular expressions in Prolog is Regi.
- XSB Prolog. There is a chapter in the XSB book on how to do automata theory in XSB.
- A page entitled Perl Style Regular Expressions (in Prolog).
- if you're looking for a lex-like tool, you might consider Elex. Elex is a lexical analyzer generator with multiple output languages. There is a version which produces Prolog lexers at http://www.let.rug.nl/~vannoord/Elex/ The original Elex homepage is at http://www.ozemail.com.au/~mpp/elex/elex.html So this is not implemented in Prolog (in C++ and Perl, rather), but can be made to produce Prolog output (tested with SICStus, SWI, BinProlog, Bprolog; should work for others).
- another lexer with Prolog output (implemented in Prolog) is part of multiplex by Peter Reintjes (for Quintus prolog). http://frege.als.com/nalp/people/Reintjes_Peter/Reintjes_Peter.html
|
|
|
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.prologFrom: 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
Newsgroups: comp.lang.prolog
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 +0200Local: 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
> and thus better to have a real general-purpose language with prolog
a Prolog in Lisp.
Prolog is a real general purpose language.
> implemented in that language so you can easily write your applicationYou 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 GMTLocal: 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.prologFrom: Peter Van Weert <Peter.VanWe...@cs.kuleuven.be>
Date: Fri, 16 May 2008 12:14:43 +0200Local: 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 GMTLocal: 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
> Duncan Patton wrote:
Peter Van Weert <Peter.VanWe...@cs.kuleuven.be> 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
|
|
|
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/
|
|
|
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
|
|
|
Contents
- Pure, declarative, and constructive binary arithmetic all-mode relations
- Soutei, a logic-based trust-management system
- Solving Dr. Ecco's puzzle "Lines of Fire"
- Minimization of a Finite Automaton
- leanTAP theorem prover in Kanren
- Universal quantification, impredicative terms, and effects
- Recursive Data Types in Prolog
- Shortest Paths in a directed graph
- Knight's tours
- N-queen problem
- KANREN: A declarative logic programming system: http://kanren.sourceforge.net
- The taste of logic programming: the distillation of Kanren to the simplest terms
- Fair backtracking monad with pruning and
bagofN
Solving ``Missionaries and cannibals'', and playing Tic-Tac-Toe with minimax search and heuristics- Representing knowledge about knowledge: ``Mr.S and Mr.P'' puzzle
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/4such thatdiv(N,M,Q,R)succeeds if and only ifN = M*Q + Rand0<=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
Mthat 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 numbersXandY-- or to find all factorizations ofZ, as the tests show. Furthermore, we can evaluateadd(X,[l],Y)and get the stream of answers, among which is[[o, _G523|_G524], [l, _G523|_G524]]. It essentially says that2*xand2*x +1are successors, for allx>0!Our
log/4predicate has the property thatlog(N,B,Q,R)succeeds if and only ifN = B^Q + Rwhere0 <= RandQis the largest such integer. We can uselog/4to 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.
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.
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:
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.
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.
- Numbers.
Ex:
1,-2,0.5,-0.776.
- Symbols, which are, for all intents and purposes, immutable strings of lower-case letters without special characters or spaces. (We'll explain why symbols must be lower-case later.)
Ex:
hello,world,this_is_a_symbol,atom3.- Linked lists of symbols or numbers. Lists are untyped.
Ex:
[hello, cruel, world],[1, 2, 3],[1, hello, 2, world],[].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. (
helloandworld, two patterns without arguments;f(hello, world), a patternfwith two arguments;g([hello, world]), a patterngwith one argument, a list; andstandard_greeting([hello, world], 2), a patternstandard_greetingwith 2 arguments, a list and a number)When several patterns are defined with the same name and the same number of arguments, Prolog will run through them, one after another in a top-to-down fashion, when trying to match them. (You can think of this as a short-circuited "OR" of pattern matching rules.)
Defining pattern-matching rules
Defining pattern-matching rules in Prolog is equally simple:
f(hello, world) :- g([hello, world]).
Whenever Prolog sees the special symbol
:-, Prolog creates a new pattern-matching rule. The basic meaning of:-is very simple: to match whatever is to left of the:-, the part to the right must be matched. This allows to "decompose" complex patterns into smaller, more manageable ones.To make the task practical, Prolog defines many operators that help us in the task of composing pattern-matching rules. Some of the more important and useful are:
,: A comma denotes sequential matching of patterns; this is equivalent to a "short-circuited AND" in many imperative programming languages. (C's&&, for example.)Ex:
f :- a, b, c.This means that to match the pattern
f, we need to match, in order, patternsa,bandc.;: A semi-colon denotes choice; this is equivalent to a "short-circuited OR" in many imperative programming languages. (C's||, for example.)Ex:
f :- p; q; r.This means that to match the pattern
f, eitherpmust be matched, or, if Prolog fails to matchp, try to matchq; if matchingqfails, finally try matchingr.
Note that the semi-colon is essentially equivalent to listing patterns on separate lines; thus,
f :- (p; q).
is equivalent to
f :- p.
f :- q.
->: An arrow denotes a conditional pattern rule, in other words, an "if-then-else" rule.Ex:
f :- (g -> h; i).This code means that Prolog first tries to match pattern
g; if the pattern can be matched, try to match the patternh. Ifgcannot be matched, try to match the patterni.
Note that the construct must be enclosed in parentheses, due to strangeness in Prolog's syntax rules.\+: This is equivalent, in a sense, to the negation operator in many programming languages. (Like theC!.)Ex:
f :- \+ g.This code means that the pattern
fmatches whenever the patterngcannot be matched.Variables
This is all very easy to understand, but is, unfortunately, useless in real-world applications. What we lack are variables. Variables in Prolog are symbols that begin with a capital letter; for example:
Var,A,Q,MATCH_ME.Whenever Prolog comes upon a variable, it starts searching in its internal database of facts and pattern-matching rules for a substitution such that substituting a value for the variable matches some fact.
A simple example will illustrate the concept better. Consider the following Prolog program:
i_know(hello).
i_know(world).is_phrase(A, B) :- i_know(A), i_know(B).
is_greeting(A, B) :- is_phrase(A, B), A = hello.
This program defines two facts (
i_know(hello)andi_know(world)) and two pattern-matching rules.
is_phrase(A, B) :- i_know(A), i_know(B).This rule, which is namedis_phraseand which accepts two arguments, tries to find substitutions for the two variables it uses (AandB) 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 variablesAandBsuch that the pattern rule matches.The new concept here is the operator
=. This operator is Prolog's equivalent of variable assignment.
P=Qmeans 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=BandB=Amean the same thing. If such a substitution cannot be found, the=operator will fail to match. For example,hello=worldwill always fail to match.Thus, after executing
i_know(A)=i_know(foo)Awill be substituted withfooeven thoughi_know(foo)does not match against Prolog's internal database. (By the way, this procedure is often called unification in Prolog jargon; thus,A=hellomeans thatAwill be unified withhello.)Finally, we can figure out what the pattern
is_greeting(A, B)does. Here, Prolog searches for substitutions forAandBsuch 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=worldAs 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.
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/
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.
We hope that the presented program will assist in the wider use of Prolog forscripting and in building demonstrative, easy-to-use wrappers around standard
Prolog code. In the future it will be interesting to evaluate the impact of Upshon 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 fromhttp://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 availabletime
Each entry is stored under its own directory, containing the following:
- A .descr file, containing a description of the package, with information about porting, size, etc, and usually with an example.
- A .pre file. Similar to the .descr file, but to be read when you need to know how to load and run the package.
- A .tar.gz file, containing the package itself. Extract the files by decompressing with gunzip, and then de-taring the resulting .tar archive.
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.
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
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.
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.
Programming Language Foundations (lecture notes)
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
npwould, 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 procedures, for recognizing sentences. An input listS0is passed into procedures, and it must setSto be the remainder of the listSafter a sentence has been removed from the beginning. To do that, it uses two subprocedures: it first callsnpto remove an NP, and then it callsvpto 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 thesprocedure 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 ans.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 forfactor; 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). Theintegerprocedure 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?).
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.).
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.
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.
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).Personunifies 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 toPerson, so we now try to unifymale(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 seesparent(bill, tom).Persongets unified with bill. Then in moving to the next rule we see that we unify withmale(bill). Now, we check the first item in the rule and see that it'sfather(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).
Lecture Notes by Serguei Krivov: Ontologies and Data Integration
prolog
Paul Brna's Prolog Programming - A First Course pspdf html (at original location)Discussion WEB Pages
Worse is BetterRichard 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]>
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.
Case Study: Implementing Perl Style Regular Expressions
A Prolog system for processing Perl style regular expressions can be implemented via the following steps.
Defining the BNF grammar of Perl-style regular expressions.
Defining a Prolog representation of Perl regular expressions.
Build a DCG parser for Perl regular expressions.
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.
Predicate names, formal:
- Lower case letters with words delimited by underscore ('_').
- Like this: ast_node, ast_node_type
- Don't use: astNode, ast_Node, ASTnode, AST_node
- Why: Consistency with standard (SWI-) Prolog notation.
Predicate names, semantic:
- Choose attributes for predicate names. yellow(B), connected(A, B)
- Verbs in singular indicative mode are also ok. follows(A, B), knows(Person, Theory). Use plural only if the predicate says something about more than one thing, e.g. about a list. include(List, Sublist) but includes(List, Element)
- Nouns that characterize relations may also be acceptable. Be aware that a noun generally sounds "symmetric" while the most predicates are not symmetric. dependency(A, B)
- Don't use: Imperative forms. (We want to think declarative!)
Predicates intended for "private" use only:
- Name ends with one underscore ('_').
- Like this: ast_node_, ast_node_type_
- Don't use: ast_node_private
- Why: Easier understanding of listings.
Dynamic Predicates
- Always declare dynamic predictes
- Like this: :- dynamic dyn_pred/1.
- Why: Undefined predicates lead to exceptions at runtime. If you query a not declared dynamic predicate and no clause/fact was added you will receive an exception instead of a silent fail.
Predicates processing lists / sets of elements:
- Name ends with 's' (or 's_' if private).
- Like this: check_statements(Pred, Statements)
- Don't use: check_statement_List(Pred, StatementList)
- Why: Says the same as the '_list' suffix but is easier (shorter) to write and read.
- Idiom: Often use a recursive predicate to process lists, which calls a predicate with the same name except for the trailing 's' to process list elements:
check_statements(Pred, []).
check_statements(Pred, [Head|Tail]) :-
check_statement(Pred,Head),
check_statements(Pred, Tail).check_statement(Pred,Head) :- ...
- Note: If possible predicate names should sound like predicates and not like commands. So maybe statements_fulfill is more appropriate than check_statments.
Variables:
- Use Java-style but start with underscore or capital letter.
- Like this: _aVeryLongVarName, AnotherVeryLongName
- Don't use: a_very_long_var_name
- Why: Shorter and easier to write than the underscore variant. The leading underscore or capital letter are required by Prolog to identify variables.
Comments:
- Use javadoc comments /** ... */ for things to include in Prologdoc and
- /* ... */ or % ... comments for commenting out code or adding implementation comments.
Line breaking:
- One predicate per line. If argument list too long, put one argument in every line with matching brackets in same column.
- Like this:
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).
- Don't use:
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).
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
Ciao is a public domain, next generation multi-paradigm programming environment with a unique set of features:
- Ciao offers a complete Prolog system, supporting ISO-Prolog, but its novel modular design allows both restricting and extending the language. As a result, it allows working with fully declarative subsets of Prolog and also to extend these subsets (or ISO-Prolog) both syntactically and semantically. Most importantly, these restrictions and extensions can be activated separately on each program module so that several extensions can coexist in the same application for different modules.
- Ciao also supports (through such extensions) programming with functions, higher-order (with predicate abstractions), constraints, and objects, as well as feature terms (records), persistence, several control rules (breadth-first search, iterative deepening, ...), concurrency (threads/engines), a good base for distributed execution (agents), and parallel execution. Libraries also support WWW programming, sockets, external interfaces (C, Java, TclTk, relational databases, etc.), etc.
- Ciao offers support for programming in the large with a robust module/object system, module-based separate/incremental compilation (automatically --no need for makefiles), an assertion language for declaring (optional) program properties (including types and modes, but also determinacy, non-failure, cost, etc.), automatic static inference and static/dynamic checking of such assertions, etc.
- Ciao also offers support for programming in the small producing small executables (including only those builtins used by the program) and support for writing scripts in Prolog.
- The Ciao programming environment includes a classical top-level and a rich emacs interface with an embeddable source-level debugger and a number of execution visualization tools.
- The Ciao compiler (which can be run outside the top level shell) generates several forms of architecture-independent and stand-alone executables, which run with speed, efficiency and executable size which are very competitive with other commercial and academic Prolog/CLP systems. Library modules can be compiled into compact bytecode or C source files, and linked statically, dynamically, or autoloaded.
- The novel modular design of Ciao enables, in addition to modular program development, effective global program analysis and static debugging and optimization via source to source program transformation. These tasks are performed by the Ciao preprocessor (ciaopp
, distributed separately).- The Ciao programming environment also includes lpdoc, an automatic documentation generator for LP/CLP programs. It processes Prolog files adorned with (Ciao) assertions and machine-readable comments and generates manuals in many formats including postscript, pdf, info HTML man, etc. , as well as on-line help, ascii README files, entries for indices of manuals (info, WWW, ...), and maintains WWW distribution sites.
Ciao is distributed under the GNU Library General Public License (LGPL).
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.
What Prolog do I Need?
- "I just want to learn Prolog" Checkout SWI-Prolog. SWI complies to the standard and it is free and stable.
- "I want do do advanced GUI stuff" Checkout SWI, Visual Prolog and LPA-Prolog. SWI has a commercial GUI on top of it, and LPA and Visual Prolog allows you to develop cute Windows apps.
- "I want to do real time robot control" Checkout BinProlog. You may even be faster than C because you have more time to concentrate on your algorithms.
- "I want to integrate a Prolog-Interpeter in my application" Checkout DGKS Prolog for a Java version or check the Prolog Resource Guide for other free Prologs.
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.
I was wondering if there are any academic or commercial visual LP languages and/or development environments.[email protected] Lindsey Spratt 25th January 1994I 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 1994We (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 1994David "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 1994I'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 1994More 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 1994Markus 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 1994XPCE 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 1994For 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/xpceXPCE 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.
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 writep :- (!), 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] ? yeswhile with an ISO-conformant system you would get| ?- name('abc\x20\def', X). X = [97,98,99,32,100,101,102] ? yesThe 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 specifieshexadecimal 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:
- Does the logic programming community want to have a standard?
- If so, is ISO Prolog the "right" standard?
- If ISO Prolog is not the "right" standard, why?
Good short tutorial that really tries to explain the language not to obscure it.
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)
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 |
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.
Google matched content |
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:
- There are three missionaries and three cannibals on the left bank of a river.
- They wish to cross over to the right bank using a boat that can only carry two at a time.
- The number of cannibals on either bank must never exceed the number of missionaries on the same bank, otherwise the missionaries will become the cannibals' dinner!
- Plan a sequence of crossings that will take everyone safely accross.
This kind of problem is often solved by a graph search method. We represent the problem as a set of
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.
- states
- which are snapshots of the world and
- operators
- which transform one state into another
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
- Write a program to find path from one node to another.
- Must avoid cycles (i.e. going around in circle).
- A template for the clause is:
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
- The search for a path terminates when we have nowhere to go.
path(Node, Node, _, [Node]).
- A path from Start to Finish starts with a node, X, connected to Start followed by a path from X to Finish.
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:
- A state is one "snapshot" in time.
- For this problem, the only information we need to fully characterise the state is:
All other information can be deduced from these three items.
- the number of missionaries on the left bank,
- the number of cannibals on the left bank,
- the side the boat is on.
- In Prolog, the state can be represented by a 3-arity term,
state(Missionaries, Cannibals, Side)Representing the Solution
- The solution consists of a list of moves, e.g.
[move(1, 1, right), move(2, 0, left)]
- We take this to mean that 1 missionary and 1 cannibal moved to the right bank, then 2 missinaries moved to the left bank.
- Like the graph search problem, we must avoid returning to a state we have visited before.
- The visited list will have the form:
[MostRecent_State | ListOfPreviousStates]Overview of Solution
- We follow a simple graph search procedure:
The search terminates whe we have found the state:
- Start from an initial state
- Find a neighbouring state
- Check that the new state has not been visited before
- Find a path from the neighbour to the goal.
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
- A move is characterised by the number of missionaries and the number of cannibals taken in the boat at one time.
- Since the boat can carry no more than two people at once, the only possible combinations are:
carry(2, 0). carry(1, 0). carry(1, 1). carry(0, 1). carry(0, 2).
- where carry(M, C) means the boat will carry M missionaries and C cannibals on one trip.
Feasible Moves
- Once we have found a possible move, we have to confirm that it is feasible.
- I.e. it is not feasible to move more missionaries or more cannibals than are present on one bank.
- When the state is state(M1, C1, left) and we try carry(M, C) then
M <= M1 and C <= C1
- must be true.
- When the state is state(M1, C1, right) and we try carry(M, C) then
M + M1 <= 3 and C + C1 <= 3
- must be true.
Legal Moves
- Once we have found a feasible move, we must check that is legal.
- I.e. no missionaries must be eaten.
legal(X, X). legal(3, X). legal(0, X).
- The only safe combinations are when there are equal numbers of missionaries and cannibals or all the missionaries are on one side.
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:
- visiting the node first, then its children (pre-order traversal):
a b d h e i j c f k g - visiting the children first, then the node (post-order traversal):
h d i j e b k f g c a - visiting some of the children, then the node, then the other children (in-order traversal)
h d b i e j a f k c g 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.
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/2relation: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 toreachback(X,Y)(one for each Y) but they all use one underlying call toreachback(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.
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] ; noThe 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?
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
Authors: Richard O'Keefe & Vitor Santos Costa
Implementation and documentation are copied from YAP 5.0.1. Thelibrary(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]
A ebook that has some coverage of Prolog usage for exploringgraph problems
- Trees: Binary Tree Operations
- UGraphs: Graph and Digraph Operations
Unweighted Graph Operations
Directed and undirected graphs are fundamental data structures representing arbitrary relationships between data objects. This package provides a Prolog implementation of directed graphs, undirected graphs being a special case of directed graphs.
An unweighted directed graph (ugraph) is represented as a list of (vertex-neighbors) pairs, where the pairs are in standard order (as produced by
keysortwith unique keys) and the neighbors of each vertex are also in standard order (as produced bysort), every neighbor appears as a vertex even if it has no neighbors itself, and no vertex is a neighbor to itself.An undirected graph is represented as a directed graph where for each edge (U,V) there is a symmetric edge (V,U).
An edge (U,V) is represented as the term U-V. U and V must be distinct.
A vertex can be any term. Two vertices are distinct iff they are not identical (
==).A path from u to v is represented as a list of vertices, beginning with u and ending with v. A vertex cannot appear twice in a path. A path is maximal in a graph if it cannot be extended.
A tree is a tree-shaped directed graph (all vertices have a single predecessor, except the root node, which has none).
A strongly connected component of a graph is a maximal set of vertices where each vertex has a path in the graph to every other vertex.
Sets are represented as ordered lists (see Ordsets).
To load the package, enter the query
| ?- use_module(library(ugraphs)).The following predicates are defined for directed graphs.
vertices_edges_to_ugraph(+Vertices, +Edges, -Graph)- Is true if Vertices is a list of vertices, Edges is a list of edges, and Graph is a graph built from Vertices and Edges. Vertices and Edges may be in any order. The vertices mentioned in Edges do not have to occur explicitly in Vertices. Vertices may be used to specify vertices that are not connected by any edges.
vertices(+Graph, -Vertices)- Unifies Vertices with the vertices in Graph.
edges(+Graph, -Edges)- Unifies Edges with the edges in Graph.
add_vertices(+Graph1, +Vertices, -Graph2)- Graph2 is Graph1 with Vertices added to it.
del_vertices(+Graph1, +Vertices, -Graph2)- Graph2 is Graph1 with Vertices and all edges to and from them removed from it.
add_edges(+Graph1, +Edges, -Graph2)- Graph2 is Graph1 with Edges and their "to" and "from" vertices added to it.
del_edges(+Graph1, +Edges, -Graph2)- Graph2 is Graph1 with Edges removed from it.
transpose(+Graph, -Transpose)- Transpose is the graph computed by replacing each edge (u,v) in Graph by its symmetric edge (v,u). Takes O(N^2) time.
neighbors(+Vertex, +Graph, -Neighbors)neighbours(+Vertex, +Graph, -Neighbors)- Vertex is a vertex in Graph and Neighbors are its neighbors.
complement(+Graph, -Complement)- Complement is the complement graph of Graph, i.e. the graph that has the same vertices as Graph but only the edges that are not in Graph.
compose(+G1, +G2, -Composition)- Computes Composition as the composition of two graphs, which need not have the same set of vertices.
transitive_closure(+Graph, -Closure)- Computes Closure as the transitive closure of Graph in O(N^3) time.
symmetric_closure(+Graph, -Closure)- Computes Closure as the symmetric closure of Graph, i.e. for each edge (u,v) in Graph, add its symmetric edge (v,u). Takes O(N^2) time. This is useful for making a directed graph undirected.
top_sort(+Graph, -Sorted)- Finds a topological ordering of a Graph and returns the ordering as a list of Sorted vertices. Fails iff no ordering exists, i.e. iff the graph contains cycles. Takes O(N^2) time.
max_path(+V1, +V2, +Graph, -Path, -Cost)- Path is a longest path of cost Cost from V1 to V2 in Graph, there being no cyclic paths from V1 to V2. Takes O(N^2) time.
min_path(+V1, +V2, +Graph, -Path, -Cost)- Path is a shortest path of cost Cost from V1 to V2 in Graph. Takes O(N^2) time.
min_paths(+Vertex, +Graph, -Tree)- Tree is a tree of all the shortest paths from Vertex to every other vertex in Graph. This is the single-source shortest paths problem.
path(+Vertex, +Graph, -Path)- Given a Graph and a Vertex of Graph, returns a maximal Path rooted at Vertex, enumerating more paths on backtracking.
reduce(+Graph, -Reduced)- Reduced is the reduced graph for Graph. The vertices of the reduced graph are the strongly connected components of Graph. There is an edge in Reduced from u to v iff there is an edge in Graph from one of the vertices in u to one of the vertices in v.
reachable(+Vertex, +Graph, -Reachable)- Given a Graph and a Vertex of Graph, returns the set of vertices that are reachable from that Vertex, including Vertex itself. Takes O(N^2) time.
random_ugraph(+P, +N, -Graph)- Where P is a probability, unifies Graph with a random graph of vertices 1..N where each possible edge is included with probability P.
The following predicates are defined for undirected graphs only.
min_tree(+Graph, -Tree, -Cost)- Tree is a spanning tree of Graph with cost Cost, if it exists.
clique(+Graph, +K, -Clique)- Clique is a maximal clique (complete subgraph) of n vertices of Graph, where n \geq K. n is not necessarily maximal.
independent_set(+Graph, +K, -Set)- Set is a maximal independent (unconnected) set of n vertices of Graph, where n \geq K. n is not necessarily maximal.
coloring(+Graph, +K, -Coloring)colouring(+Graph, +K, -Coloring)- Coloring is a mapping from vertices to colors [1,n] of Graph such that all edges have distinct end colors, where n \leq K. The mapping is represented as an ordered list of Vertex-Color pairs. n is not necessarily minimal.
- WGraphs: Weighted Graph and Digraph Operations
JSTOR: Using PROLOG in Discrete Mathematics
P-99: Ninety-Nine Prolog Problems[PS] Drawing Graphs by Example Eciently: Trees and Planar Acyclic Digraphs
Selected:
SWI-Prolog's Home high quality free implementation. Perfect for beginners. Another advantage is that it is multiplatform and can be used in Unix env. too.
Visual Prolog One of the leading implementations; too complex for beginner. See above
LPA WIN-Prolog is a commercial implementation with syntax coloring.
WIN-PROLOG shares the same underlying 32-bit inference engine and architecture as LPA DOS-PROLOG and LPA MacProlog32, and is closely compatible with both the ISO Prolog and Quintus Prolog for Unix. There is a powerful bi-directional DLL interface which allows code written in C, C++, Pascal etc to be accessed and a configurable DDE for linking with other applications (Excel, Word, Visual Basic etc). WIN-PROLOG includes full Unicode support, an attractive multi-window development environment, interactive source-level debugger, integrated editor and high-level access to Windows GUI functions.
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 quotes : Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce : Bernard 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 DOS : Programming Languages History : PL/1 : Simula 67 : C : History of GCC development : Scripting 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-Month : How 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
