Tuesday, January 8, 2013

Logic Programming with Prolog

Logic programming uses mathematical logic to represent and execute computer programs.   This style of programming is becoming more widely used yet is quite different from that supported by many other programming languages.  In this article you'll get an introduction to logic programming and then learn how to create logic programs using Prolog, the most widely used logic programming language.

Logic Programming

Logic programming is a type of declarative programming that incorporates mathematical logic, implemented using queries and relations. When you develop a program using the logic programming approach you express an algorithm, a computation, etc. (in essence, its logic) in terms of fundamental relations (represented as facts and rules), and one or more propositions or goals. Next you load the program and ask questions (i.e. queries) using the language's interpreter. The interpreter then attempts to find the collection of fundamental relations that prove the goal(s) and thus provide answers to the questions, i.e. solutions. This programming style differs from imperative programming languages where you write programs that implement a solution by specifying a sequence of instructions. With imperative programming you are computing a result based on a specific set of instructions that implement a solution, whereas with logic programming you deduce a result based on relations that implement solutions.

With logic programming, your code describes relations (connections between one or more things), logical propositions that evaluate the truth of one or more relations, performs proof searches to prove logical propositions, combines relations through resolution, and computes values for variables through unification.  For example, the following relation

automobile(bmw)

Maps "bmw" to autombile; in other words BMW is a type of automobile.  A relation could have multiple elements, for example the relation

square(5, 25)

asserts that the square of the number 5 (i.e. 5 x 5) equals 25.  The above relations are facts; another type of relation is a rule.  Relations may include code that implements algorithms, performs computations, etc.  Relations are used to prove logical propositions; the following logical proposition

automobile(m3) < automobile(bmw), bmw(m3)

asserts that an M3 is an automobile.  To prove it's true, the relations automobile(bmw) and bmw(m3) must be proved true.  Proof search, the process of evaluating relations to find a set that proves a proposition, is conducted to perform this.

Prolog

Prolog is the most commonly used logic programming language, its name stands for Programming in Logic. It was developed in the early 1970s and initially associated with natural language processing.  Prolog is widely used for artificial intelligence and is also used in other areas such as expert systems, games, theorem proving, and control systems

A Prolog interpreter runs within the context of a database of relations consisting of Horn clauses; each clause is comprised of facts and rules (that contain your program code). Using the interpreter you run queries against these clauses to have them evaluated and hence perform computations.

There are numerous Prolog implementations available; SWI-Prolog, a free, widely used Prolog environment that runs on Mac, Windows, and Linux systems, can be downloaded here.   Below is a simple program written with Prolog that computes a number in the Fibonacci sequence.

Fibonacci Sequence Program Implemented with Prolog

There are plenty of resources online to help you get started with logic programing and Prolog, also checkout the Programming for Everyone website for a more detailed overview of the language

Programming for Everyone is designed to give the reader an introduction to computer programming. The book is written for a very general audience and focuses on providing you with a detailed understanding of the basic concepts.  It's also great for programmers who want to learn about other programming areas (e.g. logic programming, computer graphics, games, etc.) they may not have experience in.  Whatever your age or background, Programming for Everyone will help you to understand computer programming!   

No comments:

Post a Comment