Prolog: A Complete Guide to How to Use It

In an era dominated by new programming languages, it’s easy to overlook the foundational technologies that set the stage for today’s innovations. Among these, the programming language Prolog holds a unique place. Developed in the 1970s, Prolog was engineered with the ambitious goal of mimicking human reasoning and problem-solving capabilities. This design ethos makes Prolog not just a tool of the past, but a continuing influence in the field of artificial intelligence and logic programming.

But what is it about Prolog that has allowed it to remain relevant in a rapidly evolving tech landscape? This exploration into Prolog’s history, design principles, and its subtle role in modern AI will answer just that. We’ll also look at some examples of Prolog in use today. Prolog is an example of a fourth generation programming language.

A Brief History of Prolog

Let’s begin by tracing the history of Prolog, including why it was developed and what it was created to achieve.

Origins and Evolution

The story of the programming language Prolog (Programming in Logic) began in the early 1970s at the University of Marseille, where Alain Colmerauer and Philippe Roussel developed it as a part of their artificial intelligence research. It was later advanced by logician Robert Kowalski, working with the AI group at the University of Edinburgh.

The language was primarily intended to facilitate the programming of AI applications by using logic, a radical departure from the procedural programming paradigms of the time. Prolog encodes a set of logical relationships between linguistic elements, allowing a computer to “understand” the logical relationships that underlie language.

An example would be grandparent = parent of parent. This method mimics the way humans learn language, building up complex logical structures from simple ones. Kowalski’s phrase “Algorithm = Logic + Control” distinguishes two parts of an algorithmic process: the logical description of a problem and the control strategy used to solve it.

This is key to how Prolog operates. It allows Prolog to focus on the “what” (logic) rather than the “how” (control), which is instrumental in AI applications where decision-making based on complex rulesets is required.

Purpose and Design Goals

The primary goal behind the development of Prolog was to create a language that could efficiently handle and process symbolic information and not just numerical data. This was particularly aimed at applications in AI, such as natural language understanding, where the ability to work with abstract, symbolic relationships is crucial.

Two aspects of Prolog were key to the early development of natural language processing:

Declarative Nature: Prolog’s design allows programmers to express problems in terms of relations, represented as facts and rules. A Prolog program essentially consists of a database of facts and rules about objects and their relationships, and queries are made to infer information from these facts and rules.

Automatic Backtracking: Prolog includes this powerful feature that enables the language to explore multiple paths to find solutions to a problem, which is particularly useful in search problems and non-deterministic computations often found in AI.

Achievements and Milestones

Prolog’s capabilities in natural language processing and its pivotal role in the development of expert systems marked its early success stories. The language was instrumental in projects like the Japanese Fifth Generation Computer Systems project, which aimed to revolutionize computing with AI.

Although the Japanese project did not achieve its ambitious aims, it did help train a generation of AI developers and create prototypes for computer reasoning that paved the way for future LLMs.

Prolog helped formalize the representation of knowledge as rule-based logic, which is central to all LLMs. This is particularly true in LLMs that combine symbolic reasoning with statistical learning.

Furthermore, Prolog’s strengths in pattern matching and symbolic processing made it an excellent tool for early NLP applications. The declarative nature of Prolog allowed developers to focus on describing the grammar and semantics of languages without delving into the control flow of the application. These early advances in NLP contributed to the evolution of more sophisticated NLP techniques, which are core to the functioning of LLMs.

Lastly, Prolog’s ability to automatically infer new knowledge from a given set of facts and rules by using logical deduction (through backward chaining and resolution) showcased a powerful method of automated reasoning.

This aspect of logical inference laid the groundwork for later AI systems to incorporate reasoning capabilities. In LLMs, while the inference is statistical rather than logical, the underlying need to derive conclusions from known data is a shared goal.

Key Features and Design of Prolog

Let’s look at little closer at how Prolog works and why it’s helpful as a foundation of LLM programming.

Logical Foundations

Prolog stands out as an example of a fourth-generation programming language, emphasizing declarative programming over procedural. In Prolog, the programmer specifies what the problem is, rather than detailing how to solve it. The system then tries various solutions, following a set of logical rules.

This approach aligns closely with human logical reasoning, making Prolog especially powerful for tasks involving complex rule-based logic and inference.

Prolog Programming Language Syntax

Consider a simple family relationship problem where one needs to determine familial relations based on a set of given facts. Prolog allows these relationships to be expressed and queried directly, illustrating the natural, intuitive style of programming that Prolog facilitates.

Once a full set of rules is written in Prolog, a potentially unlimited set of problems can be solved. A simple Prolog program can be written to solve any Rubik’s Cube, for instance, once provided with a list of rules a human expert would use to solve the puzzle.

Here are some simple examples of how facts, rules and queries are encoded in Prolog:

As you can see, if Prolog is supplied with a long list of snacks and fruit, then the second query in the above example could have multiple solutions. Modern LLMs apply statistical means to select between possible solutions to provide the best next token in the linguistic sequence.

Prolog in Modern AI and LLMs

Now that we have a basic understanding of what Prolog is, and how it developed, let’s look at how it became foundational in the development of modern AIs and LLMs.

Continued Relevance of Prolog

Although the advent of more versatile programming languages has overshadowed Prolog in some areas of AI, it remains a valuable tool in specific domains such as expert systems and advanced knowledge bases. Prolog’s ability to handle complex rule-based data and infer new knowledge from existing facts aligns well with certain aspects of modern AI research.

Prolog’s direct role in the architecture and implementation of modern LLMs like GPT (Generative Pre-trained Transformer) or BERT (Bidirectional Encoder Representations from Transformers) is minimal because these models are based on neural network architectures that fundamentally differ from the logic-based programming environment of Prolog.

However, the foundational concepts in Prolog have indirectly influenced the broader field of AI, including aspects that are critical to the development and functionality of LLMs. Here’s how Prolog’s principles and methodologies have contributed conceptually and theoretically to the environment from which modern LLMs have emerged:

1. Emphasis on Formal Logic and Automated Reasoning

Prolog is based on formal logic, specifically predicate logic, which is fundamental to understanding and formulating rules about relations and functions in intelligent systems.

While LLMs use statistical methods to process and generate language, the influence of logical structuring in AI has helped develop methods for reasoning and understanding in AI systems. Prolog’s focus on formal logic has spurred further research into how these logical frameworks can be integrated with or inspire statistical models to enhance reasoning capabilities.

2. Knowledge Representation and Reasoning

Prolog was designed for knowledge representation and reasoning, allowing developers to define relationships and rules that the system uses to infer new knowledge. In the context of LLMs, while the representation is learned from data rather than explicitly defined, the goal of deriving new, coherent pieces of information from known data is a shared objective.

Prolog’s influence is evident in hybrid AI systems where rule-based logic programming is combined with statistical models to improve the LLMs’ understanding and generation of language, particularly in domain-specific applications.

3. Natural Language Processing (NLP) Techniques

Prolog’s capabilities in pattern matching and syntactic analysis have historically benefited NLP applications. Early Prolog systems contributed to parsing and understanding natural language through rule-based methods, which evolved into the more advanced, data-driven approach used in LLMs.

The development of NLP from rule-based to statistical methods builds upon the foundational ideas seen in Prolog.

4. Exploratory and Incremental Development

Prolog supports an exploratory style of programming that is highly conducive to AI development, where hypotheses about knowledge and logic can be incrementally tested and refined.

This approach mirrors the development cycle of LLMs, where models are iteratively trained, tested, and fine-tuned based on performance metrics and outputs.

5. Declarative Problem Solving

The declarative nature of Prolog, where the programmer specifies what the program should accomplish without dictating how to do it, shares philosophical underpinnings with the way LLMs are trained to generate language.

In LLMs, the model learns to predict or generate text based on input examples alone, without explicit programming of the steps involved in the generation process.

Application of Prolog to Large Language Models

In the context of modern large language models (LLMs), Prolog’s influence is subtle. While LLMs primarily leverage neural networks, the logical and structured thinking that Prolog embodies can be seen in how these models handle rule-based tasks and logical reasoning.

Now that we understand how Prolog became a steppingstone on the road to natural language processing and LLMs, let’s enumerate the essential differences between the two:

You can see that, in many aspects, Prolog bears little resemblance to a modern LLM. However, hybrid forms do exist, using a combination of both methodologies to improve outputs. In such systems the logical processing power of Prolog (or similar systems) acts as a corrective to the statistical methods used by LLMs.

For example, developers arXiv, based at Cornell University have proposed a framework called HalluVault, which applies logic programming methods to correct the tendencies of LLMs to “hallucinate” (make false “factual” statements).

Prolog Programming Online

For those interested in exploring Prolog, numerous resources and platforms offer online environments to learn and test Prolog code. These platforms provide a great starting point for both novices and seasoned programmers to experiment with logic programming.

Programmer Markus Triska has both an online Prolog Course and a YouTube channel with a very detailed and strangely poetic approach. This might not be the best resource for the complete beginner, however.

A more structured, simplified approach is offered on Learn Prolog Now! created by Patrick Blackburn, Johan Bos, and Kristina Stieglitz. This course is divided into twelve chapters, each with exercises and a practical session, which leads you through the various steps of an operation so you can see, in real time, how various parts of Prolog work.

The classic text Art of Prolog (second edition, 1994) by Leon Sterling and Ehud Shapiro, and published by MIT Press, can be downloaded in PDF for free here. Over 500 pages long, this book is one of the most detailed guides to the language, with many helpful examples and a comprehensive index.

Another helpful tour of the basics of Prolog is provided by Ryan Schnacte on his YouTube channel The Simple Engineer. The first part of his Prolog playlist is here. He recommends downloading two free pieces of open source software to be able to write in Prolog: the text editor Sublime and SWI–Prolog to compile and run your programs.

Another great textbook is Prolog Programming for Artificial Intelligence (4th Edition, 2011) by Ivan Bratko and published by Pearson Education Canada. The first 200 pages provide a great introduction to the semantics and syntax of the language. The remaining 13 chapters demonstrate how Prolog can be applied to the basics of AI. At 678 pages, it’s an even more in-depth guide than the Sterling and Shapiro book.

Online skills platform Udemy has a popular course, The Complete Prolog Programming Course: From Zero to Expert! The course was created by Lucas Bazillo, has been taken by over 830 students and has earned a 4.7-star rating. Best of all, the whole course costs less than $20.

Prolog Programming Examples

To further illustrate Prolog’s capabilities, consider exploring common examples like graph traversal, sorting algorithms, and decision-making processes in AI simulations. These examples demonstrate how Prolog’s logic can be applied to solve diverse problems efficiently.

Example 1: Prolog in Graph Traversal

Graph traversal refers to the process of visiting, checking, and updating nodes (vertices) and edges in a graph, whether it be a directed or an undirected graph. The two most common methods of graph traversal are Breadth-First Search (BFS) and Depth-First Search (DFS).

BFS explores the graph layer by layer, starting from a given node and moving outward, typically using a queue to manage the nodes that need to be visited. DFS, on the other hand, explores as far along a branch as possible before backtracking, usually employing a stack (either explicitly with a stack data structure or implicitly through recursion).

Prolog is especially useful in graph traversal due to its inherent recursive nature and its declarative approach to problem-solving. Here’s why Prolog is beneficial for graph traversal:

Recursive Programming: Prolog’s strength in recursion simplifies the process of writing DFS algorithms. Since DFS naturally fits into a recursive framework (where you visit a node and then recursively visit all its unvisited neighbors), Prolog can express this pattern succinctly and clearly.

Backtracking: Prolog automatically handles backtracking. When a path leads to a dead end (i.e., all nodes are visited or a condition is not met), Prolog can automatically backtrack to explore other unvisited paths. This feature is particularly useful in implementing DFS where backtracking is a necessary component.

Pattern Matching: Prolog’s pattern matching capabilities allow it to easily manage the traversal’s conditions and rules. You can specify patterns to match specific nodes or structures within a graph, making it straightforward to deal with complex graph queries and constraints.

Declarative Nature: Unlike imperative programming languages where you describe how to perform a task, in Prolog you describe what you want as a set of rules and relationships. This high-level approach is well-suited for expressing problems like graph traversal, where you can define the graph and its query properties (e.g., connectivity, paths, cycles) in a declarative manner.

Here’s a simple example of how Prolog might be used to perform a depth-first search on a graph:

% Define edges in the graph

edge(a, b).

edge(a, c).

edge(b, d).

edge(c, d).

edge(d, e).

% Define the recursive DFS rule

dfs(Node, Visited, [Node|Path]) :-

edge(Node, Next),

\+ member(Next, Visited), % Ensure the node has not been visited

dfs(Next, [Next|Visited], Path).

% Query to start DFS from node ‘a’

query_dfs(Path) :-

dfs(a, [a], Path).

In this Prolog code, dfs/3 is a rule that performs DFS from a given node, maintaining a list of visited nodes to prevent cycles. The \+ member(Next, Visited) ensures that the next node to visit has not been previously visited.

Example 2: Creating a Sorting Algorithm in Prolog

Sorting algorithms are fundamental to computer science, and implementing one in Prolog provides a great example of using Prolog’s declarative style and logical reasoning capabilities.

Unlike more conventional programming languages where you would explicitly describe the steps to sort elements, in Prolog, you define what conditions a sorted list must satisfy and let the language’s inference engine figure out how to achieve those conditions.

Concept of Sorting in Prolog

Sorting in Prolog can be implemented in various ways, but one elegant method is to use the concept of permutations and order checking. Essentially, you define what a sorted list looks like, and then generate permutations of the input list until you find one that is sorted.

Example: Insertion Sort in Prolog

Here’s a straightforward implementation of the Insertion Sort algorithm in Prolog. This algorithm works by building up a sorted list one element at a time, inserting each new element into its correct position in the already-sorted list.

% Insert an element into a sorted list at the correct position

insert(X, [], [X]).

insert(X, [Y|Ys], [X,Y|Ys]) :- X =< Y.

insert(X, [Y|Ys], [Y|Zs]) :- X > Y, insert(X, Ys, Zs).

% Insertion sort algorithm using the insert predicate

insertion_sort([], []).

insertion_sort([X|Xs], Sorted) :-

insertion_sort(Xs, SortedTail),

insert(X, SortedTail, Sorted).

In this code:

insert/3 is a predicate that inserts an element X into the correct position in a sorted list. The first rule handles the base case where the list is empty. The second rule inserts X before the first element Y of the list if X is less than or equal to Y. The third rule continues to traverse the list if X is greater than Y.

insertion_sort/2 sorts a list by recursively sorting the tail of the list and then inserting the head of the list into the sorted tail.

Further Exploration: Permutation Sort

Another way to implement sorting in Prolog is through permutation sort, which is more aligned with Prolog’s strengths but less efficient in practice:

% Check if a list is sorted

sorted([]).

sorted([_]).

sorted([X,Y|Rest]) :- X =< Y, sorted([Y|Rest]).

% Permutation sort uses the permutation predicate and checks for sortedness

permutation_sort(List, Sorted) :-

permutation(List, Sorted),

sorted(Sorted).

This approach checks every permutation of the input list until it finds one that is sorted. While this is computationally expensive (O(n!)), it demonstrates Prolog’s power in handling combinatorial problems with ease.

The Legacy of Prolog

It’s clear that Prolog’s legacy is twofold. On one hand, Prolog has directly contributed tools and methodologies to AI that are still in use.

On the other, it has influenced the design and development of subsequent programming languages and AI systems. The programming language Prolog exemplifies how foundational technologies can continually influence new generations of technology and innovation, even within the cutting-edge realm of AI. Rayobyte is one of the best proxy providers and the proxy is useful to collect data through programming languages. You can do all that and more with Rayobyte proxies today.

The information contained within this article, including information posted by official staff, guest-submitted material, message board postings, or other third-party material is presented solely for the purposes of education and furtherance of the knowledge of the reader. All trademarks used in this publication are hereby acknowledged as the property of their respective owners.