Introduction to Programming with Prolog
Introduction to this Tutorial
A bit ago, I ranted about tail call recursion and talked a bit about Prolog- a programming language that relies heavily on recursion, and hence benefits from tail call recursion. Buried in the CompSci complexities, I promised a tutorial on Prolog targeted towards non-programmers.
This is that tutorial. Whether you've programmed or not before, I am going to do everything I can to make this tutorial accessible to the average person. I strongly believe that everyone can write programs, and that everyone would benefit from learning a little about it. Between the technical skills, the problem solving-skills, and the general "cool" factor1, it's a good skill for everyone to pick up.
background(programming)
To be overly literal. programming is the skill of being able to write programs. In common understanding, a program is a pile of code that tells a computer what to do. At a very low level, we're told, this all translates to ones and zeros and the computer does "stuff" with them.
This is all well and good, but it doesn't give us the clearest possible picture. What would be clearer? Try this on for size:Program: a collection of expressions, rules, or directions; given a certain input, this collection instructs the executing agent to generate a certain output.
There's a lot in there. As someone that's using programs, I hope that this definition is clear to you. You're reading this article in a web browser. The input, in this case, is an HTML file (your View->Source menu option will show you the contents). The output is an on-screen rendering of that HTML source that you can read and interact with. Your web browser is a set of instructions that tells your computer (the "executing agent") how to turn the HTML input into the on-screen output.
Input -> Program -> Output
Expressions, Rules and Directions
Programming languages are how we specify what a program does. There are a few major schools of thought on how a programming language should do this. Each of these different approaches is suited to different kinds of problems, but they're all capable of solving any problem2. The most instinctive approach is what we call an imperative language.
Go to Google Maps. Search for directions from your location to Pittsburgh, PA. Read those directions. That's what an imperative program looks like. "Do this, then do this, now do this." An imperative programming language uses directives as its main element. Examples of imperative languages:C,Pascal,Cobol
. These sorts of languages will often group a collection of directives into a procedure (For example, the results you get from Google Maps could be called the procedure, "Drive to Pittsburgh").
For the more mathematically minded, there exist a collection of languages that use an expression or a function. The idea of a function is a mathematical one, and we're all familiar with a few common mathematical functions. Function AreaOfACircle(radius) is 2π*radius2
Function ConvertTemperature(C) is 9/5 * C + 32
A program written in a functional language would try to break a problem down into a series of expressions, and then group those expressions into a function. Examples of functional languages: LISP, JavaScript, ErLang
The other major category of language is the logical language. Our choice of language, Prolog, is this kind of language. Prolog uses facts and rules to describe how to turn input into output. Logical reasoning:
LogicProlog
Socrates is a manman(socrates).
All men are mortalmortal(X) :- man(X).
∴Socrates is mortalmortal(socrates).
In a logical language, like Prolog, we're going to specify facts and rules for how to combine facts and how those facts relate to each other.
Objectified
I would be remiss if I didn't include the other major family of programming languages, Object Oriented Languages. In an object based language, our main language construct is the object- a thing. If I wanted to make a programming about driving, I would define a type of object called a "car". I would define the attributes and behaviors of a thing called a car, and I'd define them using procedures and functions. In reality, OO languages are generally imperative languages with object modeling. Object Oriented Programming is very much focused on model building- you make an abstract model of a real-world problem in programming code. Examples of Object Oriented Languages: C++,Java (no relation to JavaScript),C#,VB.Net,Python,Ruby
OOP is extremely popular for enterprise and business programming, in part because it makes it easy to build highly modular code that can be reused and worked on by large teams.
One more thing...
It's also a bit misleading for me to have split these languages up as neatly as I did. Most imperative languages have functions in them as well. LISP and JavaScript, both functional languages, have the idea of objects. The latest version of C# has something called "closures", which are generally a concept from functional programming. For the time being, we don't really need to worry about these details. I just want to make it clear that I am oversimplifying things a bit.
To be more explicit about how MUCH I'm simplifying, skim this list of programming paradigms and their relationships. I have some complaints about the way that hierarchy is put together, but there's a lot more going on here than we need to worry about for our exercises.
background(prolog)
As I said before, we're focusing on Prolog as our tool for learning how to program. This means we'll be building our programs out of facts and rules. But there's a few more things to keep in mind about programming in Prolog. Prolog is a little different than most other languages because a Prolog program, left to its own devices doesn't do anything. When building a Prolog program, you're going to write a file known as a "Logicbase". This is your collection of facts and rules. To "run" this program, you tell Prolog to consult the file (which loads those rules into your Prolog interpreter), and then you issue queries. Prolog looks at your query, looks at your rules and facts, applies its own internal logic (which we'll look at in detail later) and generates a response. This means that all execution in Prolog is interactive.
Getting Set Up
To start programming in Prolog, you're going to need a Prolog interpreter. This will be the the software that executes your Prolog code. I'm going to be building my examples around SWI-Prolog, which you can download and install from here. They'll have versions for each different operating system. Actually launching SWI-Prolog is going to require that you know where you installed it. Some vague directions are here. On Windows, it'll install where it tells you to, on OSX it installed into /opt/local/bin, and on Linux I imagine it goes someplace similar. Where ever it installed, you need to configure your PATH to include it.
For Windows, you should be able to find Prolog in your start menu (in a folder "Pl" by default). Keep in mind, on Vista, you must use the "Run As Administrator" feature to install it properly. On Linux, it varies depending what shell you're using. Here are some instructions for Bash, the most common shell. Those instructions should also work for OSX.
I'm sorry that there's no easy way for me to give you these instructions. This is the one section of getting started that requires some semi-obscure technical knowledge. Do your best to truck through, and if you need any help, reply in the comments. I'll do my best to help get you set up. Google is your friend.
Another Option
Thanks to danbri, I now know of another option without any install issues. This web based Prolog interpreter provides a no-install-issue way of doing things. I haven't played with it much, and I don't know if everything we cover will be 100% compliant (some of it probably won't, actually), but this provides a way to get started without dealing with annoying install crap.
Running Prolog
If you've got everything set up properly in the last step, this part should be easy.
Windows
Go Start->Programs->Accessories->Command Prompt. Type plcon.exe and hit enter.
OSX
In /Applications/Utilities you'll see a program called Terminal. Double click on this and type swipl and hit enter.
Linux
Bring up a terminal. Type swipl and hit enter.
Running your first Prolog program
At this point, you should be looking at a prompt with a ?-. This is the interactive terminal for querying your Prolog logicbase, but we don't have one just yet. We're going to build one using SWI-Prolog's built in text editor. Type the following and hit enter: emacs. (include the period! every command in Prolog ends with a period).
A window will appear after a moment. This is a Prolog-based version of a popular programmer's text editor called Emacs. This program is very powerful, but we're going to focus on just the parts we need. Go up to the file menu and create a new file. You'll need to tell Emacs where to save it, and name the file: "Lesson1.pl". Now, let's switch to "Prolog Mode", go: File->Mode->Prolog. This tells the editor to treat it as a Prolog file. This will enable a few features we need and color-code your code to make it easy to read.
Simple Prolog
Now, I'm going to give you a program. We're not going to discuss exactly what's happening here just yet. Just type the following into the editor window:
man(socrates).
man(aristotle).
woman(hypatia).
mortal(Person) :- man(Person).
mortal(Person) :- woman(Person).
Capitalization matters!
The first three lines are facts. The last two lines are rules that tell Prolog how to put those facts together. This says a Person is mortal if that Person is a woman or a man (a variation on the syllogism above). Now, we need to give this program to Prolog. Go up to your "Compile" menu and select "Compile Buffer".
Switch back to your console window (where you typed emacs.). You may see some text has printed out about compiling Lesson1. At the ?- prompt, type this and hit enter: mortal(socrates). (again, include the period and capitalization matters!).
Prolog should print out "true". Based on the facts and rules we supplied, Socrates is a man, all men are mortal, and therefore Socrates is mortal. Try this query: man(hypatia).. This returns false: there is no fact or rule that says Hypatia is a man. But mortal(hypatia). returns true. This is a very simple example, but there's some really powerful bits to even this simple program. Try this code:
man(X).
After you hit enter, it prints "X = socrates". Hit the ";" key, and it then prints out "X = aristotle". That semicolon told Prolog you weren't happy with its first answer, and you wanted it to find another. So it prints out everyone who is a man.
Now try: mortal(X). and use the semicolon key again. You'll have to hit it twice, as it prints out:
?- mortal(X).
X = socrates ;
X = aristotle ;
X = hypatia.
Summary
This is a big lesson. There's a lot in here, and my future lessons probably won't be this long. My goal for this lesson was to give you some background on programming and demonstrate a simple Prolog logicbase. I blasted through the bits of code very quickly, because our goal here was just to give you a taste. In our next lesson, we'll study this simple program and experiment with a few others. We'll define exactly how rules and facts behave in Prolog, and start talking a little bit about the "magic" of Prolog.
In this lesson, we discussed what a program is, and mentioned a few of the different varieties of programming languages. We set up our computer to run Prolog, and now we've looked at a simple Prolog program.
1Programmers are cool, right? I think so, but my opinion has a bit of bias.
2There's a hypothetical computer known as a Turing Machine. Alan Turing proved, mathematically, that his hypothetical computer could solve a certain broad class of mathematical problem. Any programming language that can solve those problems is known as "Turing Complete". Nearly all languages in common use are "Turing Complete". This means they can all do the same things, in a general sense. But they may be better at one task than another language.
A bit ago, I ranted about tail call recursion and talked a bit about Prolog- a programming language that relies heavily on recursion, and hence benefits from tail call recursion. Buried in the CompSci complexities, I promised a tutorial on Prolog targeted towards non-programmers.
This is that tutorial. Whether you've programmed or not before, I am going to do everything I can to make this tutorial accessible to the average person. I strongly believe that everyone can write programs, and that everyone would benefit from learning a little about it. Between the technical skills, the problem solving-skills, and the general "cool" factor1, it's a good skill for everyone to pick up.
background(programming)
To be overly literal. programming is the skill of being able to write programs. In common understanding, a program is a pile of code that tells a computer what to do. At a very low level, we're told, this all translates to ones and zeros and the computer does "stuff" with them.
This is all well and good, but it doesn't give us the clearest possible picture. What would be clearer? Try this on for size:Program: a collection of expressions, rules, or directions; given a certain input, this collection instructs the executing agent to generate a certain output.
There's a lot in there. As someone that's using programs, I hope that this definition is clear to you. You're reading this article in a web browser. The input, in this case, is an HTML file (your View->Source menu option will show you the contents). The output is an on-screen rendering of that HTML source that you can read and interact with. Your web browser is a set of instructions that tells your computer (the "executing agent") how to turn the HTML input into the on-screen output.
Input -> Program -> Output
Expressions, Rules and Directions
Programming languages are how we specify what a program does. There are a few major schools of thought on how a programming language should do this. Each of these different approaches is suited to different kinds of problems, but they're all capable of solving any problem2. The most instinctive approach is what we call an imperative language.
Go to Google Maps. Search for directions from your location to Pittsburgh, PA. Read those directions. That's what an imperative program looks like. "Do this, then do this, now do this." An imperative programming language uses directives as its main element. Examples of imperative languages:C,Pascal,Cobol
. These sorts of languages will often group a collection of directives into a procedure (For example, the results you get from Google Maps could be called the procedure, "Drive to Pittsburgh").
For the more mathematically minded, there exist a collection of languages that use an expression or a function. The idea of a function is a mathematical one, and we're all familiar with a few common mathematical functions. Function AreaOfACircle(radius) is 2π*radius2
Function ConvertTemperature(C) is 9/5 * C + 32
A program written in a functional language would try to break a problem down into a series of expressions, and then group those expressions into a function. Examples of functional languages: LISP, JavaScript, ErLang
The other major category of language is the logical language. Our choice of language, Prolog, is this kind of language. Prolog uses facts and rules to describe how to turn input into output. Logical reasoning:
LogicProlog
Socrates is a manman(socrates).
All men are mortalmortal(X) :- man(X).
∴Socrates is mortalmortal(socrates).
In a logical language, like Prolog, we're going to specify facts and rules for how to combine facts and how those facts relate to each other.
Objectified
I would be remiss if I didn't include the other major family of programming languages, Object Oriented Languages. In an object based language, our main language construct is the object- a thing. If I wanted to make a programming about driving, I would define a type of object called a "car". I would define the attributes and behaviors of a thing called a car, and I'd define them using procedures and functions. In reality, OO languages are generally imperative languages with object modeling. Object Oriented Programming is very much focused on model building- you make an abstract model of a real-world problem in programming code. Examples of Object Oriented Languages: C++,Java (no relation to JavaScript),C#,VB.Net,Python,Ruby
OOP is extremely popular for enterprise and business programming, in part because it makes it easy to build highly modular code that can be reused and worked on by large teams.
One more thing...
It's also a bit misleading for me to have split these languages up as neatly as I did. Most imperative languages have functions in them as well. LISP and JavaScript, both functional languages, have the idea of objects. The latest version of C# has something called "closures", which are generally a concept from functional programming. For the time being, we don't really need to worry about these details. I just want to make it clear that I am oversimplifying things a bit.
To be more explicit about how MUCH I'm simplifying, skim this list of programming paradigms and their relationships. I have some complaints about the way that hierarchy is put together, but there's a lot more going on here than we need to worry about for our exercises.
background(prolog)
As I said before, we're focusing on Prolog as our tool for learning how to program. This means we'll be building our programs out of facts and rules. But there's a few more things to keep in mind about programming in Prolog. Prolog is a little different than most other languages because a Prolog program, left to its own devices doesn't do anything. When building a Prolog program, you're going to write a file known as a "Logicbase". This is your collection of facts and rules. To "run" this program, you tell Prolog to consult the file (which loads those rules into your Prolog interpreter), and then you issue queries. Prolog looks at your query, looks at your rules and facts, applies its own internal logic (which we'll look at in detail later) and generates a response. This means that all execution in Prolog is interactive.
Getting Set Up
To start programming in Prolog, you're going to need a Prolog interpreter. This will be the the software that executes your Prolog code. I'm going to be building my examples around SWI-Prolog, which you can download and install from here. They'll have versions for each different operating system. Actually launching SWI-Prolog is going to require that you know where you installed it. Some vague directions are here. On Windows, it'll install where it tells you to, on OSX it installed into /opt/local/bin, and on Linux I imagine it goes someplace similar. Where ever it installed, you need to configure your PATH to include it.
For Windows, you should be able to find Prolog in your start menu (in a folder "Pl" by default). Keep in mind, on Vista, you must use the "Run As Administrator" feature to install it properly. On Linux, it varies depending what shell you're using. Here are some instructions for Bash, the most common shell. Those instructions should also work for OSX.
I'm sorry that there's no easy way for me to give you these instructions. This is the one section of getting started that requires some semi-obscure technical knowledge. Do your best to truck through, and if you need any help, reply in the comments. I'll do my best to help get you set up. Google is your friend.
Another Option
Thanks to danbri, I now know of another option without any install issues. This web based Prolog interpreter provides a no-install-issue way of doing things. I haven't played with it much, and I don't know if everything we cover will be 100% compliant (some of it probably won't, actually), but this provides a way to get started without dealing with annoying install crap.
Running Prolog
If you've got everything set up properly in the last step, this part should be easy.
Windows
Go Start->Programs->Accessories->Command Prompt. Type plcon.exe and hit enter.
OSX
In /Applications/Utilities you'll see a program called Terminal. Double click on this and type swipl and hit enter.
Linux
Bring up a terminal. Type swipl and hit enter.
Running your first Prolog program
At this point, you should be looking at a prompt with a ?-. This is the interactive terminal for querying your Prolog logicbase, but we don't have one just yet. We're going to build one using SWI-Prolog's built in text editor. Type the following and hit enter: emacs. (include the period! every command in Prolog ends with a period).
A window will appear after a moment. This is a Prolog-based version of a popular programmer's text editor called Emacs. This program is very powerful, but we're going to focus on just the parts we need. Go up to the file menu and create a new file. You'll need to tell Emacs where to save it, and name the file: "Lesson1.pl". Now, let's switch to "Prolog Mode", go: File->Mode->Prolog. This tells the editor to treat it as a Prolog file. This will enable a few features we need and color-code your code to make it easy to read.
Simple Prolog
Now, I'm going to give you a program. We're not going to discuss exactly what's happening here just yet. Just type the following into the editor window:
man(socrates).
man(aristotle).
woman(hypatia).
mortal(Person) :- man(Person).
mortal(Person) :- woman(Person).
Capitalization matters!
The first three lines are facts. The last two lines are rules that tell Prolog how to put those facts together. This says a Person is mortal if that Person is a woman or a man (a variation on the syllogism above). Now, we need to give this program to Prolog. Go up to your "Compile" menu and select "Compile Buffer".
Switch back to your console window (where you typed emacs.). You may see some text has printed out about compiling Lesson1. At the ?- prompt, type this and hit enter: mortal(socrates). (again, include the period and capitalization matters!).
Prolog should print out "true". Based on the facts and rules we supplied, Socrates is a man, all men are mortal, and therefore Socrates is mortal. Try this query: man(hypatia).. This returns false: there is no fact or rule that says Hypatia is a man. But mortal(hypatia). returns true. This is a very simple example, but there's some really powerful bits to even this simple program. Try this code:
man(X).
After you hit enter, it prints "X = socrates". Hit the ";" key, and it then prints out "X = aristotle". That semicolon told Prolog you weren't happy with its first answer, and you wanted it to find another. So it prints out everyone who is a man.
Now try: mortal(X). and use the semicolon key again. You'll have to hit it twice, as it prints out:
?- mortal(X).
X = socrates ;
X = aristotle ;
X = hypatia.
Summary
This is a big lesson. There's a lot in here, and my future lessons probably won't be this long. My goal for this lesson was to give you some background on programming and demonstrate a simple Prolog logicbase. I blasted through the bits of code very quickly, because our goal here was just to give you a taste. In our next lesson, we'll study this simple program and experiment with a few others. We'll define exactly how rules and facts behave in Prolog, and start talking a little bit about the "magic" of Prolog.
In this lesson, we discussed what a program is, and mentioned a few of the different varieties of programming languages. We set up our computer to run Prolog, and now we've looked at a simple Prolog program.
1Programmers are cool, right? I think so, but my opinion has a bit of bias.
2There's a hypothetical computer known as a Turing Machine. Alan Turing proved, mathematically, that his hypothetical computer could solve a certain broad class of mathematical problem. Any programming language that can solve those problems is known as "Turing Complete". Nearly all languages in common use are "Turing Complete". This means they can all do the same things, in a general sense. But they may be better at one task than another language.