Prolog: as enigmatic as it is powerful, this programming language has maintained an air of mystery and interest since its inception. While it might not be as wildly popular as some of its modern counterparts, this grand master of symbolic AI offers unparalleled power and expressiveness for certain tasks. Let's step into the world of Prolog together and "grok" its genius!
Before we begin our journey, let's warm up with a brief overview of Prolog's origins.
The story starts in the early 1970s, with French computer scientists Alain Colmerauer and Philippe Roussel devising a new approach to symbolic artificial intelligence. Their objective was to create a high-level language that could handle complex formal logic problems with ease. Enter Prolog, the programming language that fused logic programming with automated theorem proving.
In 1972, the first Prolog interpreter was built at the University of Marseille. By the early 1980s, Prolog had become the weapon of choice for researchers working in AI and expert systems development. It even played a significant role in Japan's ambitious Fifth Generation Computer Systems project!
"Prolog is not just a programming language, but an elaboration of a powerful idea"—Robert Kowalski, Logic Programming Pioneer
Now that we've had our history lesson, let's explore the basic building blocks of Prolog. Unlike your run-of-the-mill imperative programming languages, Prolog is based on formal logic and has a unique set of constructs:
Facts: These are declarative statements about your problem domain, represented as predicates. For example, a fact might be
likes(jane, chocolate)., indicating that Jane likes chocolate.
Rules: Rules define relationships between predicates and consist of a head and a body separated by ':-'. The rule can be read as "head is true if body is true." An example rule would be
dessert(X) :- cake(X); ice_cream(X)., meaning something is a dessert if it’s a cake or ice cream.
Queries: Queries are questions we ask of our program using the known facts and rules. For example,
?- likes(jane, chocolate). checks whether Jane indeed likes chocolate.
Let's see these constructs in action with a simple Prolog program!
% Facts human(john). human(mary). bird(tweety). % Rules mortal(X) :- human(X). % Query ?- mortal(X).
Our program defines facts about humans and a bird. The rule
mortal(X) states that X is mortal if X is human. When we query the program with
?- mortal(X), we receive the expected output:
X = john ; X = mary.
This demonstrates that Prolog can infer that both John and Mary are mortal based on the available facts and the rule we provided.
Now, let's delve into the truly mind-bending aspects of Prolog: unification and backtracking. These mechanisms are what make Prolog so powerful (and fun!).
Unification is the process of making two terms equal by finding appropriate variable bindings. When you make a query in Prolog, it tries to unify the query with the program's facts and rules. A successful unification results in a solution.
For example, consider the following query:
?- likes(jane, X).
Here, Prolog will attempt to unify
likes(jane, X) with a matching fact or rule. If we have the fact
likes(jane, chocolate)., Prolog will bind
chocolate and the query is considered successful.
Backtracking is Prolog's method of exploring alternative solutions. If unification fails or a rule's conditions aren't satisfied, Prolog backtracks to earlier choices and attempts to find alternative matches.
Let's see backtracking in action with a Prolog program based on the Eight Queens Puzzle:
valid(). valid([Head|Tail]) :- valid(Tail), notattack(Head, Tail). notattack(_, ). notattack(X/Y, [X1/Y1 | Rest]) :- Y =\= Y1, abs(X1-X) =\= abs(Y1-Y), notattack(X/Y, Rest). eight_queens(Board) :- permutation([1,2,3,4,5,6,7,8], Board), valid(Board).
We define a set of rules to ensure that queens are placed on a chessboard without attacking each other. The
eight_queens/1 predicate finds a permutation of row numbers and checks whether it forms a valid configuration using the
notattack/2 predicates. Querying
?- eight_queens(Board). will kick off a search for valid board configurations using backtracking.
Prolog excels at tasks that involve searching large solution spaces, manipulating symbolic data, and reasoning with incomplete or uncertain information. Some of its most celebrated use cases include:
We've just scratched the surface of Prolog's immense power. As you continue your journey, don't shy away from embracing the language's unique features. Delve into its intricacies, experiment with its idiosyncrasies, and explore its myriad applications. In this wonderland of symbolic AI, Prolog awaits your mastery. Good luck, and happy programming!
Grok.foo is a collection of articles on a variety of technology and programming articles assembled by James Padolsey. Enjoy! And please share! And if you feel like you can donate here so I can create more free content for you.