Prolog Visualisation Tool

Recently, I've been finding that Prolog is getting rather more complicated, and that the traces that I keep doing are getting longer and longer. This is making it rather difficult to understand what's going on, and so in response to this I am building the Prolog Visualisation Tool(kit).

Basically, the Prolog Visualisation Tool(kit) is a tool that, given a Prolog trace, produces a diagram of the trace in question. The image at the top of this post is diagram produced by the tool for a depth first search.

You can find it live now on GitHub Pages.

It is built with mermaid, a really cool diagramming library by knsv, which converts some custom graph syntax to an svg.

The next step will be to animate it, but I haven't got that far yet. Expect an update soon!

Learning Prolog: Lab #7

Today's lab introduced lists, and they are a lot harder to comprehend than the other things that we have done so far. You can define a list in Prolog with square brackets, like so:

?- Sandwiches = [ cheese, chicken, cucumber, lettuce_and_tomato ].

This isn't particularly useful, but the real fun comes later on after you've written a bunch of utility rules. Before I get into that though, I should explain a little bit about heads and tails. In Prolog, you can split a list up into its head and its tail with a bar character (|), like so:

printhead([ Head | Tail ]) :-
    write(head).

Here's a quick example of the above in action:

?- printhead([ apple, orange, grape ]).
apple
true.

This is especially useful for recursion, as we shall see in a moment. With that out of the way, here are few utility rules that I put together. There's one that writes out all the items in a list, one that counts up all the numbers in a list, one to concatenate two lists together, and one to calculate the length of a list. They all use loops, so if you don't understand those you should go back and read my previous blog post before continuing.

writelist([]). % Stopping condition.
writelist([ Head | Tail ]) :-
    % Write out the head of the list.
    write(' - '), write(Head), nl,
    % Recursively write out the rest of the list.
    writelist(Tail).

concat([], List, List). % Stopping condition - The 2nd list and the result should be one and the same
% Add the head of the first list onto the result
concat([ Head | Tail ], List2, [ Head | Result ]) :-
    % Recursively add the next item in the first list to the result
    concat(Tail, List2, Result).

countlist([ LastItem | [] ], LastItem). % Stopping condition - Don't continue if we reach the end of the list.
countlist([ Head | Rest ], Result) :-
    % Recursively count the rest of the list
    countlist(Rest, RecursiveResult),
    % Add the head to the result from recursively counting the rest of the list.
    Result is RecursiveResult + Head.

listlength([ _ | [] ], 1).
listlength([ _ | Tail ], Result) :-
    listlength(Tail, RecursiveResult),
    Result is RecursiveResult + 1.

All of the above use a similar loop structure. They recursively sort out the tail, and then deal with the tail when we coming back out again. Here are some examples of the above rules (virtual cookie for whoever works out what all the things in each of the lists below have in common). Don't forget to ask questions in the comments if you don't understand something.

?- writelist([ cat, dog, parrot, elephant, whale]).
- cat
- dog
- parrot
- elephant
- whale
true
?- countlist([ 4, 7, 2, 18, 48, 364 ], Result).
Result = 443 .
?- listlength([ alpha_centauri, sirius, barnards_star, epsilon_eridani, tau_ceti], Length).
Length = 5 .
?- concat([elysium_mons, arsia_mons, aeolis_mons], [skadi_mons, maat_mons], Result).
Result = [elysium_mons, arsia_mons, aeolis_mons, skadi_mons, maat_mons].

Find all the things!

The other thing we looked at this week was the findall/3 predicate. In a nutshell, findall will find everything that matches the given criteria and put them in a list. Here's a simple example:

loves(cat, milk).
loves(dog, bone).
loves(mouse, cheese).
loves(mouse, seeds).
loves(cat, cheese). % Yes, my cat does love cheese...!
loves(parrot, seeds).

?- findall(Who, loves(Who, cheese), Result), writelist(Result).
 - mouse
 - cat
true.

In the above example, we ask Prolog to find us everyone who loves cheese, and then print out the result. The second argument is the criteria we want Prolog to use when searching, the first argument is the variable from the criteria that we want to store, and the third argument is the list we want populating.

As an exercise, try to work out how to ask Prolog who likes seeds, given the above dataset. If you find that easy, try asking Prolog to list everyone who likes both seeds and cheese. The answers will be in the comments.

findall can be used to search many different datasets. Here's another more complicated example:

isa(polly, parrot).
isa(parrot, bird).
isa(bird, living_thing).
hasa(parrot, wings(2)).
hasa(polly, perch).
hasa(polly, colour(green)).

?- findall(green_birds(Who), hasa(Who, colour(green)), Result).
Result = [green_birds(polly)] .

That concludes this blog post on the 7th Prolog lab. If you are interested, here are some links to the source code for the examples found in this post, along with a few extras.

• Pastebin
• Raw

Learning Prolog: Lab Session #6 - More Looping

Before I get into today's post, I wanted to include a picture of some firework that I managed to photograph a few days ago on my phone. A heard them outside and when I took a look out of the window, this is what I saw!

Anyway, Today's Prolog lab session was about more loops. These loops are different to the failure driven loops that we did last time though in that they are recursive instead. Here's an example:

loopa :-
    write('Enter \'end.\' to exit.'), nl,
    read(Input), (Input = end ; loopa).

The above is a simple rule that keeps asking for user input until the user enters 'end'.

?- loopa.
Enter 'end.' to exit.
|: hello.
Enter 'end.' to exit.
|: cheese.
Enter 'end.' to exit.
|: end.
true.

This is done through the semi colon, which acts as an or operator. Although this works, it isn't very readable. Let's try something else.

% Stopping condition
loopb(end).
% Main loop
loopb(Input) :-
    write('Enter \'end.\' to exit.'),
    read(Input2),
    loopb(Input2).

% Starter rule
go :-
    loopb(something).

Much better. The above is divided up into the stopping condition (i.e. when the user types end), the main loop, and a rule that kicks the rest of the program off. When go is called, we call loopb with something as a parameter immediately. Since this doesn't match the fact loob(end), Prolog looks at the rule we defined, loopb(Input). Then it asks the user for input, and starts the process over again until the user inputs end.

Here's an example of the above in action:

?- go.
Enter 'end.' to exit.gdsfgdrt.
Enter 'end.' to exit.sdfgsdgf.
Enter 'end.' to exit.sdfgsdfgertr.
Enter 'end.' to exit.cheese.
Enter 'end.' to exit.end.
true.

Having learnt this, one of the challenges was to write a rule in Prolog. A factorial is where you multiply an integer by all the integers greater than 0 but less than the integer. For example, 4! (4 factorial) is 4x3x2x1, which is 24). Here's what I came up with:

factorial(1, 1).
factorial(N, Factorial) :-
    N2 is N - 1,
    factorial(N2, Ans),
    Factorial is N * Ans.

And here's an example of the above in action:

?- factorial(6, Answer).
Answer = 720 .

That concludes this post on the 6th Prolog lab session. If you don't understand something (or I've made a mistake!) please post a comment below and I'll do my best to help you. Also, if you have any, post your firework pictures below. I'd be interested to see them!

Learning Prolog: Lab Session #5 - Backtracking

The next lab in the series introduces the idea of backtracking. Apparently Prolog is somewhat persistent in its attempts to prove things that you ask it, leading it to go back to where it last had a choice and try a different route when faced with failure.

Let's take this dataset (or knowledge base) for example:

food(apple,fruit).
food(tomato,fruit).
food(lettuce,salad).
food(beef,meat).
food(cucumber,salad).

This is a simple set of foods, along with their types.

What if we were lazy and wanted to get Prolog to output all the different salad foods in the above dataset? It's too much work for us to us (there might be thousands of lines to search in future), so let's insert the following lines:

display_salad_food :- food(Food,salad),
    write(Food), write(' is a salad'), nl, fail.

(Pastebin, Raw)

The above is a rule that can be satisfied by fetching a food of type salad. It then writes out the food to the console, then a new line, and then hits fail - a brick wall that tells Prolog that it, well, erm... failed. This causes Prolog to backtrack to the last choice it made (in this case food(Food,salad)) and try finding a different route. Here's some example output from the above:

?- display_salad_food.
lettuce is a salad
cucumber is a salad
false

This construct is called a failure driven loop. This is because it gets Prolog to try all possibilities by backtracking - causing it to fail over and over again while it searches out alternative routes.

The other thing this lab introduced was repeat predicate. This acts as a 'checkpoint', so to speak, which lets Prolog continue from this point, even if it doesn't find any path to take. Here's an example, though I should warn you that running it will crash Prolog! (unless you are using the web based editor or course - then you can just hit the abort button)

hello_world :- write('Hello '), repeat, write('World'), nl, fail.

And here's some example output:

Hello World
World
World
World
World
World
World
World
World
World
...

The reason it crashes is because it contains an infinite loop. Prolog writes out Hello,, and writes out World and a new line, and then hits fail. Going back, it spots a repeat statement, which allows it to continue. It then writes out World again, hits the fail, and so on and on and on.....

That concludes this post about lab #5. If you found it helpful, please comment (I love reading comments)! Suggestions and constructive criticism are always welcome too!

Learning Prolog: Lab Session #4 - Reading and Writing

This week we were asked to do another 2 labs in one session - this blog post will cover lab #4, and there will be another one coming out on Thursday for lab #5.

Before we start though, I want to mention Swish. It's an online editor for Prolog that runs in the browser. It apparently doesn't support all the features that the desktop version does, but the editor itself is so much better than the desktop version. It's actually bearable! If at all possible, I'll be using it from now on.

This week's (first) lab was all about reading and writing from the console. You would have thought that this would be the first thing you'd learn as a hello world, but apparently that isn't the case. 3 weeks into the course, and we finally know enough to write our first hello world in Prolog!

Anyway, reading and writing are quite simple actually - once you've learnt rules. Here's an example:

go :-
    write('Hello, world!').

If you query go. on the above, you should get an output something like this:

?- go.
Hello, world!
true

The write/1 (write arrity 1) statement lets us write out a message to the console. Note that the string we want to output is enclosed in single quotes. This is important, because apparently some Prolog environments interpret double quotes to mean "output the ASCII character codes of the characters in this string", and not "output the characters themselves in this string". Personally I haven't found that to be the case, but it's best to be aware of it.

Writing messages to the console is neat, but not particularly useful in itself. Let's upgrade it to ask the user's name, and then say hello to them:

go :-
    write('Enter name: '), read(Name),
    write('Hello, '), write(Name), write('!'), nl.

Here's an example output:

?- go.
Enter name:
|: starbeamrainbowlabs.
Hello, starbeamrainbowlabs!
true.

When you ask Prolog go., it then asks you what your name is - and then says hello to you. There are several things to note here. Firstly, nl/0 is a special predicate that simply write a newline character to the console. Secondly, read/1 is a special predicate to read in a string from the console and drop it into the given variable.

read/1 can be rather weird when it comes to actually getting input from the user. The string the user enters must be terminated by a full stop (.), otherwise it will continue to ask for input. It must also start with a lower case letter, otherwise strange stuff starts to happen. I theorise that this is probably related to the fact that variables in Prolog start with an uppercase letter.

Thankfully, we can get around the second issue by enclosing strings in double quotes:

?- go.
Enter name:
|: 'Starbeamrainbowlabs'.
Hello, Starbeamrainbowlabs!

Much better. Let's actually use these new functions to do something (kind of) useful. Here's the first excercise:

Write a Prolog program using facts in the form month/1 that displays the month depending on the integer entered by the user, e.g. if the user enters 3 the program will display The Month is March.

Initially I was started with a program beginning like this:

month(January) :-
    % ...

But soon found that it didn't work. The solution here is to invert it, so that Prolog gets to choose which path it takes based on the input it gets. It makes sense, I suppose, considering Prolog is a language for writing artificial intelligences.

Here's some example output:

?- month(1).
January
true.
?- go.
Enter month code:
|: 4.
April
true.

In the above, we can either call query month/1 directly, or query go., which will ask us for the month code directly and call month/1 for us.

That concludes the 4th lab. I'll write up another post for lab #5, which should hopefully be out on Thursday. As an aside, I used the embed code from PasteBin in this post instead of embedding the code directly and then linking to the PasteBin. Which would you prefer? Why? Do you have another idea? Let me know in the comments!

Learning Prolog: Lab Session #3

I'm back with the third post in this (rather unexpected) series! I think I might be getting the hang of this. It's rather abstract and difficult to visualise though. Perhaps there's a tool out there that lets you visualise your Prolog programs to better understand them (If you know of one, please leave a comment down below!) This week's lab introduced the idea of rules. A rule in Prolog is basically if this then at. For example, if the temperature is low and there are lots of clouds in the sky, the weather can be considered bad.

Here's an example:

weather(bad) :-
    temperature(low),
    cloud(high),
    visibility(low).

weather(good) :-
    temperature(high),
    cloud(low),
    visibility(high).

weather(unsure).

temperature(low).
cloud(high).
visibility(low).

(Pastebin, Raw)

The last 3 lines of the above describe the weather at the moment - feel free to change them. The :- bit is simply the equivalent of the IF syntax in Prolog (rather odd if you ask me). Anyway, using the above we can now ask Prolog what the weather is like so:

?- weather(What).
What = bad .

Note that you nad to press enter in order to tell Prolog that it got the correct answer. This is because it has detected that there are other possible answers that it hasn't evaluated yet. You can press space to tell Prolog that it hasn't found the correct answer, but more on this later.

The above, in english, says something like this:

The weather is bad if the temperature is low, there's lots of cloud cover and visibility is low. The weather is good if the temperature is high, there aren't many clouds about and visibility is high. If the weather is neither of the above, then we are unsure about whether the weather good or bad.

We can also use rules in Prolog to categorise something based on a set of rules. Here's an example that works out what category a test score would fall into.

grade(distinction, Mark) :-
    Mark >= 70.
grade(pass, Mark) :-
    Mark >= 40,
    Mark < 70.
grade(fail, Mark) :-
    Mark < 40.

(Pastebin, Raw)

Using the above, we can ask Prolog questions like this:

What grade would I get if I got a mark of 86?

What grade would a mark of 52 be?

And so on. Here's how you would ask Prolog the above questions:

?- grade(Category, 87).
Category = distinction .

?- grade(Category, 52).
Category = pass .

?- grade(Category, 11).
Category = fail.

verything was all going rather well, until I got to the final excersize. It was based on getting Prolog to tell you whether a car fault was electrical or not. Here's a description of what we were asked to do:

A car fault is electrical if the car won't start or the lights are broken. A car fault is also electrical if the car won't start and the lights won't work, or the battery is flat.

After some thought, I came up with the following:

car_fault(electrical) :- % colon-if represents IF in Prolog.
    wont_start; % Semi-colons represent OR in Prolog.
    lights_broken. % Full stops terminate rules.
car_fault(electrical) :-
    (wont_start, % Commas represent AND in Prolog.
    lights_broken);
    flat_battery.

wont_start.
lights_broken.

Where you define any combination of wont_start., lights_broken. or flat_battery beneath the rules, depending in your situation. However, I got a nasty error when I tried to run it, complaining that I hadn't defined something. After sone looking into it (and some help from my lecturer), we found that you need to explicitly tell Prolog that it's OK if lights_broken., wont_start., or flat_battery. aren't defined, and that it shouldn't throw an error. You can do this like so:

:- dynamic wont_start/0.
:- dynamic flat_battery/0.
:- dynamic lights_broken/0.

(Full version: Pastebin, Raw)

Then you can ask Prolog whether your car has an electrical fault like so:

?- car_fault(What).
What = electrical .

...and Prolog will reply that yes, it is an electrical fault if the above rules are met. Otherwise, it will reply false. To practice, try extending the above to include the following:

A car fault is mechanical if the windows have been smashed.

A car fault is also mechanical if the engine is smoking, or if the engine is making a loud noise.

Just ask in the comments for the answer to the above, or if you need help. Also note that I can't tell who's reading this blog if you don't comment! I don't have any analytics set up at all.

Update 16th Jan 2016: An anonymous commenter (please leave your name next time!) alerted me to a mistake in the test grading example. I've fixed it now, thank you!

Learning Prolog: Lab Session #2

Apparently we are supposed to complete the second and third set of lab instructions before the next lab. This post is about what I've learnt from the second lab session, and my thoughts along the way.

Now that I've played around with Prolog for a bit, I've discovered that it isn't really as bad as I thought it was to start with, although the inbuilt editor is absolutely terrible (and there's no real replacement :/).

Last time I learnt that Prolog is rather like a detective in that you tell it about the world, and it can then answer simple questions based on what it's learnt. It's also capable of working things out that you don't explicitly tell it, for example that cats don't like bones - they like milk instead.

Today's lab session started off with some simple Maths. Prolog, apparently, isn't particularly good at Maths - and I'm inclined to agree. Maths in Prolog is done through the use of the symbol comparison system. For example, you can ask Prolog is 2 is equal to itself:

?- 2 = 2.
true.

Prolog replies that yes, 2 is equal to itself. This is relieving, as something would be very wrong otherwise. You can ask Prolog whether other things are equal to each other:

?- two = two.
true.
?- carrots = carrots.
true.

This is mildly interesting, but not really useful. Let's ask it something a bit harder.

?- 4 = 2 + 2.
false.

Erm right. That's not the answer we were expecting...! The reason for this is that Prolog sees the above in terms of the literal symbols that we gave it. So Prolog sees this instead:

Is four equal to "two plus two"?

The equals operator in Prolog actually means unify (are these things the same?), and Prolog is a bit stupid and takes this more literally than we intended. Thankfully, there's another operator we can use:

?- 4 is 2 + 2.
true.

That's much better. The is operator can be used to check if two things are equal as well, but the difference here is that Prolog will perform any mathematical operations that it comes across on the right hand side. In addition, it can be used to set variables (more on that later). The is operator supports brackets, too, allowing you to do this:

?- 40 is ((2 * 10) / 4) * 8.
true.

Variables

Variables in Prolog always start with a capital letter, and are useful when you want to ask Prolog questions like "What does a cat like?" or "What is purple?". Here's an example knowledge base:

purple(flower).
purple(elephant).
animal(elephant).
animal(cat).

Given the above information, we know we can ask Prolog questions like these:

?- purple(elephant).
true.
?- purple(cat).
false.

Those are nice, but rather obvious. Let's step it up a bit, and ask it what is purple:

?- purple(What).
What = flower .

Note that you have to hit enter after entering the command to confirm that the answer is correct. In the above it has correctly identified that a flower is purple and put this information into the variable What. Let's see if we can retrieve the contents of the variable later on:

?- What.
% ... 1,000,000 ............ 10,000,000 years later
% 
%       >> 42 << (last release gives the question)

What's going on here?! This is certainly a rather odd response. The problem here is that variables in Prolog are scoped to the command that's executing. This seems rather useless for now, but at least we use them to ask Prolog a different sort of question. This also works with multiple predicate parameters:

food(cheese, dairy).
food(milk, dairy).
food(cabbage, vegetable).
food(orange, fruit).

Given the above knowledge, we ask things like:

?- food(What, vegetable).
What = cabbage.
?- food(What, dairy).
What = cheese .

Prolog correctly identifies that a cabbage is a vegetable, and that cheese is a dairy product. Note that it picked cheese over milk, as cheese is the first thing it came across. I have a feeling this might be important later on.

That concludes this post on Prolog. If you found it useful, please comment below! I don't run any sort of analytics on here at the moment, so I can't who's reading (or not). If you found a mistake (which is likely) or just want to say hello, please also leave a comment below.

Prolog: First Impressions (or a basic tutorial on the first lab session)

Yesterday I had my first artificial intelligence lab session on Prolog. It didn't start off very well. The instructions we were given didn't seem to have been tested and were largely useless. Thankfully one of the demonstrators came over to help and showed me the basics.

This blog post is part review, part first impressions, and part tutorial. It's purpose is to consolidate the things that I have learnt. Hopefully it will be useful to someone else out there :) Also note, if you haven't figured it out by now, I am a complete beginner with Prolog. There will be mistakes! If you spot one, please comment below so that I can fix it :)

My first impression of Prolog is that it is hard. It is very hard to learn. This isn't helped by the fact that the tools available to the new Prolog programmer are very out of date and feel exceptionally clunky. Perhaps a redesign is in order?

Anyway, I discovered at first that Prolog is very much like a detective. You give it facts and relationships, and then question it on the information you've given it (much like comprehension) using things called queries. Here's an example of a fact:

cat.

In the above, we are telling prolog that something called a cat exists. In it's world now, a cat is the only thing in existence. We can then ask it whether a cat exists in the world in the query window by running the prolog file. If you are using the default editor that comes with Prolog, simply press CTRL+C and then CTRL+B. If you aren't, type prolog filename.pl to launch a query window based on filename.

?- cat.
true.

Prolog is telling us that a cat exists, but we knew that already. Let's try asking it whether a dog exists:

?- dog.
ERROR: toplevel: Undefined procedure: dog/0 (DWIM could not correct goal)

Oh dear! We get a nasty (over)complicated error! Thankfully, this error (in this case) is a really simple one. Prolog is basically telling us that it doesn't know what a dog is, because a dog doesn't exist in Prolog's world at the moment.

Getting Prolog to tell us whether something exists in it's world is nice, but it isn't terribly useful. Let's try something a little bit more complicated.

animal(cat).

The above tells prolog that a cat is an animal. For reference, the bit before the opening bracket is called a predicate I think. After executing the above, Prolog's world jsut got a bit more complicated. It now knows that there is something called a cat, and that a cat is an animal. We can then ask Prolog if a cat is an animal like so:

?- animal(cat).
true.

Prolog tells us that yes, a cat is an animal. This is also nice, but still not amazingly clever. Let's write some more Prolog.

animal(cat).
animal(dog).
animal(cow).

pet(cat).
pet(dog).

food(milk).
food(bone).

likes(cat, milk).
likes(dog, bone).

The above looks much more complicated, but it's not as bad you might first think. In the above, we tell Prolog that a cat, a dog, and a cow are animals. We also tell it that only a cat and dog are pets. In addition, we say that both milk and a bone are forms of food, and that a cat likes milk, and a dog likes a bone. We can then ask Prolog a bunch of questions on the above:

?- animal(cow).
true.
?- pet(cow).
false.
?- likes(cat, milk).
true.
?- likes(cat, bone).
false.

In the above, we ask prolog 4 questions:

1. Is a cow an animal? Prolog answers that yes, a cow is in fact an animal (we told it so).
2. Is a cow a pet? Prolog answers that no, a cow isn't a pet. It knows that because we told it that a cow is an animal, but we didn't tell it that a cow is a pet.
3. Does a cat like milk? Prolog answers that yes, cats do like milk - because we told it so.
4. Does a cat like a bone? Prolog answers that no, cats don't like bones, as we told it that cats like milk instead.

Prolog is starting to show how powerful it is, but I have a feeling that I haven't even scratched the surfaced yet. Next week, assuming I understand the next lab, I'll make another post about what I've learnt.