We started with logic programming, in particular Prolog.

And before we kind of start reviewing this, you will need to install Prolog on your computer,

because there will be, quite soon actually, homeworks, starting with, well you've

guessed it, Prolog. The usual things, take two lists, reverse them, all these

kind of things, to get you going. You will have to look at them, remember what

recursive programming is like, and just keep doing it until the pain goes away.

Yes, it's painful at the beginning, but that's for any new programming

paradigm, because you have to unlearn a couple of bad habits.

Oh, let's take a variable, let's stick 15 into it, and then increase it by one, and blah blah blah.

That's not gonna work, okay. You cannot do C programming or Java programming in Prolog.

It is different, which is why we're not giving you problems that require a lot of code,

but just a little bit of code. Of course, there are lots of problems, which you can

write down in a little bit of code, where in Java you would need lots of stuff.

Okay, so we are going to use something called SWI. Prolog, that's a very mature

implementation of Prolog, runs on everything that takes electricity, and

just Google it. It has an installer for Windows, it has a Mac installer,

you can do it with AppsKit, install blah-de-blah, or on a Mac I would use

homebrew or something like this. You can get it any way you want, and any

version is good enough. Prolog hasn't changed significantly over 20 years.

Which is a good thing. There are typically special modes for your

favorite editor. It's probably a good idea to install them as well. If you're

using Emacs, there's something how you do that is explained in the course

notes, only for the reason because I know how to do it. If you want to do it in

Sublime, I know there are ways of doing it. There's even a VI mode, and there is

a couple of web prologs around, so just do something, but don't use WordPad,

because that's not going to be fun. My main concern with Prolog is that it's a

different programming paradigm. It is not like imperative programming, where you

give a cooking recipe. First do this, then do that, put the noodles into the pot, add

water and heat, stir until done. That's typical imperative programming.

That's not what Prolog does. What Prolog does is, this is true about the world,

I've seen that, and so on. You write down knowledge about the world, and then

rather than just letting your program run, you actually ask it questions.

I think we can all agree it's different. The surprising fact about this, and

that's what I want to show you today, is that this is actually Turing complete.

You can actually program everything, and people have programmed everything in

Prolog. At first you think, oh come on, that's not programming, that's AI.

Well, AI and programming, they're the same. The rule, Prolog has exactly

one rule, no two, two actually, two rules, which is sufficient to understand the

language. We went through an example, we have a knowledge base,

which is about natural numbers, that basically says, well zero is a natural

number, dot, and the successor of S, S is a function, the successor of X is a

natural number, if X is a natural number. Very simple knowledge base.

Most people know more than this, but it's all beautiful. We can actually start a

query and apply the so-called back chaining rule. Now back chaining is very

simple. It takes the first term in the query, remember the query can be longer

than one term, takes the first term in its hand, keeps a good hold of this, and

goes into the knowledge base and compares the query term with the

knowledge base term. And if it can make them equal, possibly changing variables

in a consistent way, then it acts, it does something, otherwise it goes on.

That's the rule, that's the so-called back chaining rule. So if we do this, we