Softpanorama
(slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-)

Google   

Prolog Programming

 
News See also Recommended books Recommended Links Implementations Tutorials References
Tools and Libraries Free Implementations Production systems TEC prolog Usage of Prolog for exploring graph problems FAQ Regular expressions
Prettyprining Debugging Coroutines Tips Humor History Etc
 

If I may intrude a personal element here, one of the things which distinguishes imperative programming in C, Pascal, Fortran or whatever from declarative programming in Prolog, Scheme, ML or whatever for me is a big difference in feeling. When I code in C, I feel I'm on a knife-edge of “state” — I focus on statements and what they do. I'm worried about the behaviour of a machine. But when I'm writing Prolog, the predicates feel like geometric objects and the data flow between goals feels like lines of tension holding the goals together into an integrated whole, as if the program fragment I was working were a large Rubik's cube that I could handle and move from one configuration to another without destroying it. When I fix mistakes in a Prolog program, I look for flaws in the “spatial” configuration of the program; a mistake feels like a snapped thread in a cobweb, and I feel regret for wounding the form. When I'm coding C, I worry about `register' declarations and pointer arithmetic. When I'm coding Prolog, I worry about getting the interface of each predicate just right so that it means something and has the visible perfection of a new leaf.

Richard A. O'Keefe:
The Craft of Prolog.
MIT Press,
Cambridge MA, 1990

 

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 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 and rather narrow applicability of recursive decent parsing is one of the reason is 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 in many cases failed, was to created a programming language with powerful pattern matching capabilities similar to recursive decent parsing.  Being non-procedural language it is only the second such language that achieved significant success (older and the most successful non-procedural language is 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 that 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 link to a pure procedural language. That probably one of the reasons that doomed the language 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 of factorial calculation is trivial for anybody who read Knuth (And I can say, that calculation of factorial in Prolog is a pure sadistic perversion ;-). Here is one of more suitable for the language primary domain examples borrowed from Prolog Tutorial by James Power):

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

Take the following family tree as an example:

 

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

In Prolog we represent this as: 

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

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

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

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

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

You should probably think about this example as an elegant way for expressing grammars (which is not context free). 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 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.

While syntax based approach is a very powerful paradigm 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. In this sense 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" ;-).  Essentially if pattern matches then certain variables are populated with values resulting from this match much like in Perl regular expressions. There are of course some differences (for example "lock-in" property in Prolog -- first value assigned to variable that has no value is "final").

As a language Prolog is a compromise between powerful, but very specialized, declarative programming notation and the complex realities of real world programming. An operational way to understand Prolog is to say that predicates are actually what ordinary people would call procedure calls with side effects that operate with the facts database.  Unlike relational databases, Prolog facts database can contain both regular (passive) records/structures and rules. There is also a built-in  method of creating a predicate from a list (the "=.." operator):


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

is equivalent to:

    F = function(arg1, arg2).
 

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

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

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

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

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

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

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

A good current open source Prolog implementation is SWI-Prolog (both Windows and Unix, see http://www.swi-prolog.org/). It has the ability to make GUI front ends using xpce. There is also a PocketPc port at http://www.rainer-keuchel.de/wince/swi-prolog.html

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

Good luck !

Dr. Nikolai Bezroukov
Notes:
  • Those pages are written by people for whom English is not a native language. Some amount of grammar and spelling errors should be expected.
  • This is a Spartan WHYFF (We Help You For Free) site. It cannot replace the best teachers and the best books.
  • The site contain some obsolete pages as it develops like a living tree... Some links on older pages are broken. Please try to use Google, Open directory, etc. to find a replacement link (see HOWTO search the WEB for details). We would appreciate if you can mail us a correct link.

Search Amazon by keywords:

 Google   
Open directory
Research Index
 

Old News ;-)

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

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

Release focus: Major feature enhancements

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

[Dec 4, 2007] Prolog and Logic Programming

Contents

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

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

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

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

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

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

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

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

 

Universal quantification, impredicative terms, and effects

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

 

leanTAP theorem prover in Kanren

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

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

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

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

 

Soutei, a logic-based trust-management system

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

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

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

This is a joint work with Andrew Pimlott.
 

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

Minimization of a Finite Automaton

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

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

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

 

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

PySWIP 0.2.0 Jun 28th 2007 04:49 PDT

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

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

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

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

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

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

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

Ah, my head spins!

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

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

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

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

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

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

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

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

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

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

Prolog facts

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

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

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

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

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

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

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

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

Example of a Prolog program that defines several facts:

hello.
world.

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

 

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

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

Defining pattern-matching rules

Defining pattern-matching rules in Prolog is equally simple:

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

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

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

Variables

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

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

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

i_know(hello).
i_know(world).

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

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

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

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

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

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

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

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

Thus, after executing i_know(A)=i_know(foo) A will be substituted with foo even though i_know(foo) does not match against Prolog's internal database. (By the way, this procedure is often called unification in Prolog jargon; thus, A=hello means that A will be unified with hello.)

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

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

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

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

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

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

From: Djamé Seddah <djame.seddah@free.fr>
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 majordomo@science.uva.nl
>
>

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

Good luck
 

Djamé

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

[May 7, 2007] BSF engine for Prolog

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

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

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

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

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

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

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

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

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

on systems that provide drag and drop interaction.

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

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

GNU Prolog. Upsh is available from

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

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

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

time

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

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

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

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

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

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

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

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

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

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

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

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

[May 6, 2007] Prolog Interpreter

[May 6, 2007] Syntax-Driven Semantic Analysis

Acknowledgement: This exercise was heavily inspired by Joakim Nivre.

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

[May 6, 2007] FSSPL How to Order

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

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

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

$S~ \longrightarrow ~NP ~VP$
$NP~ \longrightarrow ~Det~ N$
$VP~ \longrightarrow ~TV~ NP$
$VP~ \longrightarrow ~V$
$Det~ \longrightarrow ~the$
$Det~ \longrightarrow ~a$
$Det~ \longrightarrow ~every$
$N~ \longrightarrow ~man$
$N~ \longrightarrow ~woman$
$N~ \longrightarrow ~park$
$TV~ \longrightarrow ~loves$
$TV~ \longrightarrow ~likes$
$V~ \longrightarrow ~walks$
 

In this grammar we can derive such simple sentences as:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Consider some example executions of this grammar: 

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

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

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

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

no
| ?-

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

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

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

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

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

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

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

A Bit About Prolog

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

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

The Problem

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

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

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

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

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

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

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

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

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

[May 5, 2007] Prolog and Regular Expressions

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

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

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

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

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

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

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

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

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

 ( 1, 2, 3, 4, 5 )

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

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

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

 ( 1, 2, 3, 4, undef )

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

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

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

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

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

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

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

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

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

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

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

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

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

CS 251 Syllabus by Week by Xindong Wu

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

Lecture Notes by Serguei Krivov: Ontologies and Data Integration

Programming Language Concepts by Sidney Marshall

prolog

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

Discussion WEB Pages

Worse is Better

Richard P. Gabriel

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

My Programming Language Crisis
Keith Waclena <k-waclena@uchicago.edu>

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

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

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

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

Case Study: Implementing Perl Style Regular Expressions

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

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

  2. Defining a Prolog representation of Perl regular expressions.

  3. Build a DCG parser for Perl regular expressions.

  4. Building a regular expression matcher in Prolog.

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

XP-Projektgruppe 2004 Coding Conventions Prolog

Predicate names, formal:

Predicate names, semantic:

Predicates intended for "private" use only:

Dynamic Predicates

Predicates processing lists / sets of elements:

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

          check_statement(Pred,Head) :-         ...

Variables:

Comments:

Line breaking:

        mortal(X) :-
           alive(X).

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

        mortal(X):-alive(X).

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

Untitled Document

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

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

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

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

[May 25, 2005] Prolog Parsers

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

Prolog Comparison

What Prolog do I Need?

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

Mixtus, an automatic partial evaluator for full Prolog Dan Sahlin  

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

[Jan 24 1994] Visual Prolog Appeared in Volume 7/2, May 1994 joerg@iolo.harvard.edu David "S." Joerg

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

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

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

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

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

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

Bibliography

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

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

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

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

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

[6] "Mpl - a