|
In the early 1970's, at the University of Marseille-Aix, Alan Colmerauer created a theorem prover, Colmerauer intended for use in natural processing systems. It was based on the work of Kowalski and Colmerauer, on the subject of explicit goal-directed linear resolution procedures. The first Prolog engines were not very fast and efficient. A few years later David H.D. Warren and his peers created the Warren Abstract Machine, a compiler that translated Prolog clauses in to machine instructions and was fast enough for industrial use.
Prolog stands for "Programming in Logic". It is a vastly different style of programming than the more common languages such as C, Java, Fortran, and many others, which are known as procedural languages. Prolog is known as a declarative language. In a procedural language you give exact programming instructions detailing each step the program should take. The programmer enters these instructions in a linear sequence. Even though parts of a procedural program may not execute in a linear sequence, the component subroutines and functions almost always are, unless interrupted by a program fault. In a declarative language, you describe the logical interrelationships of your program instead, and let the logic engine determine the exact the flow of execution. In Prolog, these declarative statements are known as Horn clauses. In reality, the programmer does influence the behavior of a Prolog program by the order that he or she writes the Horn clauses in, but the effect of that ordering is much less than in a procedural program.
Prolog is also known by it's extensive use of unification, backtracking, and recursion. You can find the techniques of backtracking and recursion in procedural languages as well, but there is a vast difference. In a procedural language you have to explicitly create code to implement these techniques every time you need them. In Prolog you get them for "free". The Prolog engine examines the structure of your declarative program, and automatically determines the choice points. A choice point is any place where different branches of execution can take place, due to different values a variable might take, or different flow paths through a predicate. You can loosely think of a Prolog predicate as a subroutine or function call in a procedural language.
Backtracking - As stated above, Prolog knows every possible choice point in your program. Without any effort on the part of the programmer, it will try every combination and permutation that can be made from the set of choice points; offering each solution to the programmer as they are found. Therefore, instead of having to write code to examine every possible variant of a solution set, Prolog finds them for you automatically. In a procedural program, you have to work to write code that examines a solution set. In Prolog you usually have to prune the set of solutions to keep a Prolog program from taking too long to compute.
Unification - Unification can be loosely thought of being akin to the overloading of a function call like in C++ or Java. In C++ for example, you can have a function that is defined with three different function headers or call signatures, each handling different argument types. When you call the function with a particular argument type or types, the compiler will select the correct function based on the argument type you called it with. In Prolog, when you call a predicate, the engine will select the first Horn clause whose Head can be unified with the arguments you passed. However, the effect is much more powerful and subtle with Prolog, because unification can take place in very intricate ways, and can be partial. Partial unification happens when a predicate instantiates parts of a complex object while leaving other parts undefined or uninstantiated; allowing other parts of the program to try and unify those parts.
Recursion - Recursion can be found in almost any language, procedural or not. In Prolog it is used far more heavily than in a procedural language, frequently taking the place of iterative loops. Prolog programmers learn early to use recursion to break a problem into smaller pieces and pass those pieces down in recursive calls until a solution can be found. The pieces of the solution are then assembled into a full solution as the recursive calls terminate and exit up to the top level of the program. The assembly into the full solution is a natural side effect of recursive programming in Prolog, and does not require the programmer’s involvement. (Note: In Prolog, the term Goal is more commonly used as the top level starting point of a program).
Editor's note: It is important to understand a critical difference between a language like Prolog which has built-in inferencing engine and a typical procedural language. With a typical procederal language such as C, C++, Java, Basic, etc., execution of your program is strictly controlled by the code you enter. In other words, nothing happens unless you explicitly program it. In contrast, there are a ton of useful side effects that occur with a Prolog program due to the voracious appetite of the inference engine. The inference engine will explore every possible choice pathway your Prolog program creates. In fact, restricting the range of solutions found by the Prolog inference engine is an art that requires substantial experience.
|