Grok all the things

grok (v): to understand (something) intuitively.


πŸ‘·β€β™€οΈ Β Professionals

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!

A Glimpse into History πŸ“œ

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

The Building Blocks of Prolog πŸ”¨

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:

  1. 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.

  2. 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.

  3. 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

% 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.

Unification and Backtracking: Prolog's Secret Sauce πŸ§ͺ

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 🀝

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 X to chocolate and the query is considered successful.

Backtracking πŸ”™

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([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 valid/1 and notattack/2 predicates. Querying ?- eight_queens(Board). will kick off a search for valid board configurations using backtracking.

Applications: Where Prolog Shines ✨

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:

  • Expert systems and knowledge representation
  • AI planning and problem-solving
  • Natural language processing
  • Constraint logic programming and operations research
  • Graph algorithms and pathfinding

Ready to "Grok" Prolog? 🎯

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! 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.