Starbeamrainbowlabs

Stardust
Blog


Archive

Mailing List Articles Atom Feed Comments Atom Feed Twitter

Tag Cloud

3d account algorithms announcement archives arduino artificial intelligence assembly async audio bash batch blog bookmarklet booting c sharp c++ challenge chrome os code codepen coding conundrums coding conundrums evolved command line compiling css dailyprogrammer debugging demystification distributed computing downtime embedded systems encryption es6 features event experiment external first impressions future game github github gist graphics hardware meetup holiday html html5 html5 canvas interfaces internet io.js jabber javascript js bin labs learning library linux low level lua maintenance network networking node.js operating systems performance photos php pixelbot portable privacy programming problems project projects prolog protocol pseudo 3d python reddit reference release releases resource review rust secrets security series list server servers software sorting source code control svg technical terminal textures three thing game three.js tool tutorial twitter ubuntu university update upgrade version control visual web website windows windows 10 xmpp

Learning Prolog Series List

The new Learning Prolog banner!

I'm rather ill at the moment, but I had the idea of creating a banner for the Learning Prolog series I did a while ago, and at the same time I ended up realising that I never posted a full series list for it. This banner has been something to occupy my mind with while I recover, at least.

Anyway, here's the series list:

Semantic Nets in Prolog

The new learning prolog banner!

Yesterday a few friends were puzzling over a few Prolog exam questions, and I thought I'd write up a post about what we learnt before I forget :-)

The first part of the question asked us to convert a paragraph of knowledge into a semantic net (isa / hasa) diagram. Here's the paragraph in question:

Charles and Wilbert are rats which are brown coloured European animals. Charles has a brown collar. Animals are defined as having DNA and being about to move. They include African animals, European animals and Australian animals. Skippy is a kangaroo; kangaroos are brown coloured Australian animals. Wallabies are dark brown Australian animals, Willy being one of them. They have a diet of eucalyptus leaves. Gnu are antelopes and come from Africa, and they have stripes, as are Nyala. Stella is a Gnu and Madge a Nyala.

This first part wasn't too tough. It doesn't quite fit in some places, but here's what I came up with:

Semantic Net isa / hasa diagram

(Generated using mermaid by Knut Sveidqvist)

The blue nodes are the isa node, while the green nodes are the hasa nodes. The next part asked us to convert the above into prolog. Again, this wasn't particularly hard - it's just a bunch of isa/2's and hasa/2's:

isa(charles, rat).
isa(wilbert, rat).
isa(rat, european_animal).
isa(european_animal, animal).
isa(african_animal, animal).
isa(australian_animal, animal).
isa(skippy, kangaroo).
isa(kangaroo, australian_animal).
isa(wallaby, australian_animal).
isa(willy, wallaby).
isa(gnu, antelope).
isa(antelope, african_animal).
isa(stella, gnu).
isa(madge, nyala).
hasa(animal, dna).
hasa(animal, able_to_move).
hasa(rat, colour(brown)).
hasa(wallaby, colour(dark_brown)).
hasa(wallaby, diet(eucaliptus_leaves)).
hasa(gnu, stripes).
hasa(nyala, stripes).

After converting the diagram into Prolog, we were then asked to write some Prolog that interacts with the above knowledge base. Here's the first challenge:

Define a predicate called appearance which behaves as follows:


appearance(wilbert,Colour).
Colour=dark_brown
true.
appearance(skippy,Colour).
Colour=brown
true.

Upon first sight, this looks rather complicated, but it's not actually as bad as it looks. Basically, it is asking for a predicate, that, given the name of a thing, returns the colour of that thing. For example, wilbert was produce the answer brown, and wallaby would return dark_brown. The trick here is to get Prolog to recurse up the isa hasa tree if it doesn't find the answer at the current node.

When thinking about recursion, a good idea is to consider the stopping condition first. In our case, we want it to stop when it finds a thing that has a colour. Here's that in Prolog:

appearance(Name, Colour) :-
    hasa(Name, colour(Colour)).

Now we've got a stopping condition in place, we can think about the recursion itself. If it doesn't find a colour at the current node, we want Prolog to follow the appropriate isa fact and travel to the next level up. We can do that like so:

appearance(Name, Colour) :-
    isa(Name, Thing),
    appearance(Thing, Colour).

That completes the first challenge. If you put the above together this is what you'll get:

appearance(Name, Colour) :-
    hasa(Name, colour(Colour)).
appearance(Name, Colour) :-
    isa(Name, Thing),
    appearance(Thing, Colour).

The second challenge, however, was much more challenging:

Write a predicate that takes two argument and is true if both animals live on the same continent. Thus

?- same_continent(skippy,willy).

is true, whilst

?- same_continent(stella,skippy).

is not.

The problem with this challenge is that unlike the first challenge, there isn't any way (that I could think of anyway) to determine he continent that an animal comes from. I managed to hack around this by always going up 2 levels before comparing the things to see if they are the same:

same_continent(NameA, NameB) :-
    isa(NameA, AnimalTypeA),
    isa(AnimalTypeA, ContA),

    isa(NameB, AnimalTypeB),
    isa(AnimalTypeB, ContB),

    ContA = ContB.

For example, if wilfred and charles were plugged in, both ContA and ContB would be set to european_animal, and so Prolog would return true. Prolog would tell us that skippy and wilbert are not of the same continent because ContA and ContB would be set to different values (european_animal and australian_animal).

Learning Prolog: Semester 2 Lab 12

The new learning prolog banner!

You may have noticed that I've skipped a week in this series. Don't panic - I've done it on purpose. The task for lab 11 felt very close to the assessed coursework (ACW) for the Artificial Intelligence module that I'm learning Prolog in. I've decided to play it safe and hold off on posting about it for now. I might post later - it all depends on what the ACW is.

Anyway, the main task for this lab was to finish the work we started last week, but there was an additional challenge, too. It was based on the following challenge:

SEND + MORE = MONEY

Each letter stands for a digit, and the idea is to write a Prolog program that work out what each of the letters stands for. This problem is actually quite simple, and the particular way that you'd go about solving this has a special name.

In the beginning, I only knew one way to writing programs: Functional programming. Next, University introduced me to the wonderful world of Object Oriented Programming. In my second year, my AI module has been bending my mind with Symbolic Programming. Now, I have learnt of a fourth programming paradigm - Constraint based programming.

The solution for the above was provided (and explained!) in the lecture slides for this week:


% From http://clip.dia.fi.upm.es/~vocal/public_info/seminar_notes/node13.html
smm :-
    % Let X be the set of variables which I am going to assign
    X = [S,E,N,D,M,O,R,Y],
    % ...and Digits is the unique set of digits to assign
    Digits = [0,1,2,3,4,5,6,7,8,9], /* assign recursively goes through the letter variables and assigns them a digit */        
    assign_digits(X, Digits),        
    M > 0,        S > 0,    
    % multiply to corresponding 10 to the n
    1000*S + 100*E + 10*N + D + 
    1000*M + 100*O + 10*R + E    =:=        
    10000*M + 1000*O + 100*N + 10*E + Y, 
    /*
    This is then the constraint in raw Prolog. =:= checks for equality in the expression.
    */
    write(X).

myselect(X, [X|R], R). % Assign to first and hand back the rest
myselect(X, [Y|Xs], [Y|Ys]):- myselect(X, Xs, Ys). /* ...otherwise on backtracking free up the old binding Y and go get another value of X from the other Xs */

assign_digits([], _List).
assign_digits([D|Ds], List):-
    myselect(D, List, NewList),
    assign_digits(Ds, NewList).

This code works by creating an array of unknowns, an array of digit values that the array of variables can take, and then assigning each of the variables a value one by one. The expression on lines 10-12 is then tested, and if it doesn't match (which it probably won't), Prolog backtracks and tries to reassign one of the variables it assigned before. It repeats this process until it finds the solution.

Brute force isn't very efficient or clever, but it does the job quickly enough:


smm.
[9, 5, 6, 7, 1, 0, 8, 2].

Very nice. But that wasn't actually the challenge to for the lab. The real challenge was to adapt the above code in order to solve a slightly different puzzle:

DONALD + GERALD = ROBERT

Thankfully, all this new problem takes is a slight adjustment to the smm/1 rule that the above solution came with:

dgr :-
    % Let X be the set of variables which I am going to assign
    X = [D, O, N, A, L, G, E, R, B, T],
    % ...and Digits is the unique set of digits to assign
    Digits = [0,1,2,3,4,5,6,7,8,9],
    % Assign recursively goes through the letter variables and assigns them a digit       
    assign_digits(X, Digits),        
    D > 0,        G > 0,    
    % Multiply to corresponding  10 to the n
    100000*D + 10000*O + 1000*N + 100*A + 10*L + D + 
           100000*G + 10000*E + 1000*R + 100*A + 10*L + D    =:=        
    100000*R + 10000*O + 1000*B + 100*E + 10*R + T,
    /*
    This is then the constraint in raw Prolog. =:= checks for equality in the expression.
    */  
    write(X).

All I did was alter the unknown variables to match the new problem. Here's my result:


smm.
[5, 2, 6, 4, 8, 1, 9, 7, 3, 0].

This may well be the last post (Edit:) in this series until the end of the ACW. See you later!

Learning Prolog: Semester 2 Lab 10 - Eliza

The new learning prolog banner!

The lab numbering has gone a little bit strange this semester it seems (there was a lab 10 last semester), so I've added the semester number to the post title to avoid confusion.

This week's lab was all about Eliza. In case you don't know who (or what) an Eliza is, Eliza is an early attempt at building a chatbot. It isn't very clever, and relies on keywords to understand what you are saying. It's still used today though - mainly in NPCs in games, as they only have to deal with a very limited situation.

Anyway, let's begin building our very own Eliza. First of all, we need a prompt loop, to repeatedly ask the user for more input:

eliza :-
    write('Hello! My name is eliza.'), nl,
    eliza_loop.

eliza_loop :-
    write('Eliza > '),
    read(Input),
    write('You said '), write(Input), nl,
    eliza_loop.

Here I define eliza/0, which welcomes the user and then jumps into eliza_loop/0, which is the main input loop. The main loop simply writes a prompt, asks for input, echoes the input back, and goes back around all over again. Here's some example output:

eliza.
Hello! My name is eliza.
Eliza > test.
You said test
Eliza > cheese.
You said cheese
Eliza > [1,2,1,2,'testing...'].
You said [1,2,1,2,testing...]
Eliza >

This isn't very useful yet - it just echoes back what we say! Let's make it more complicated:

eliza :-
    write('Hello! My name is eliza.'), nl,
    eliza_loop.

eliza_loop :-
    write('Eliza > '),
    read(Input), respond(Input).

respond(Input) :-
    member(Term, Input),
    member(Term, [ quit, exit, leave ]),
    write('Goodbye!').
respond([my,name,is,Name | _ ]) :-
    write('Hello, '), write(Name), write('! Pleased to meet you.'), nl,
    eliza_loop.

In the above I've changed the main loop up a bit to call respond/1 instead of blindly looping back around. This lets me write rules like those starting on lines #8 and #12 that do something depending on the user's input. We can get our eliza to say goodbye and exit by not looping back around if the user mentions the words "quit", "exit", or "leave", or say hello when someone tells us their name and loop back around again.

There are also two different ways of detecting keywords in the user's input: a double member/2, or a preset list in the rule definition. Examples:

respond([my,name,is,Name | _ ]) :-
    write('You started the input with "my name is".').
respond(Input) :-
    member(Term, Input),
    member(Term, [ quit, exit, leave ]),
    write('Detected the word '), write(Term), write(' in the input.').

While detecting the items in a list is fairly straightforward, the double member isn't as obvious. It works by taking advantage of Prolog's backtracking. It provides a choice point for each word in the phrase, and then it loops over each of the keywords that we are searching for. If it finds that the current word isn't equal to any of the keywords that it is searching for, it will fail, backtrack, pick the next word, and try again. Another way of looking at it is that Prolog is trying all possible combinations of the input words and the keywords until it finds a match.

If you are following this post as a guide, at this point you can (and should!) add your own custom phrases to practice the techniques described here. Once you have done that, come back here.

Next up, we will add some 'fallback' phrases to our eliza to use when it doesn't understand what has been said. At the moment, it just fails with an impolite false., which isn't any good at all! To do this, we need a list of fallback phrases:

list_of_excuses(['I see.', 'Very interesting.', 'Tell me more.', 'Fascinating.']).

Next we need to get our eliza to loop through our list of fallback phrases in order. We can do this by making the fact that contains the list of fallback phrase dynamic, and then updating it every time we use one. To make something dynamic, you use the dynamic/1 predicate to tell Prolog that fact is dynamic and not static (this is because Prolog applies some clever optimisations to static things that don't work for dynamic things):

:- dynamic list_of_excuses/1

You can use this to tell Prolog that anything in your Prolog program is dynamic. Just change list_of_excuses to the name of the fact or rule, and change the 1 to the arity of the fact or rule that you want to make dynamic.

Next, we need to add a 'catch all' rule at the bottom of our respond/1 definition:

respond([ _ ]) :-
    retract(list_of_excuses([ Next | Rest ])),
    append(Rest, [ Next ], NewExcuseList),
    asserta(list_of_excuses(NewExcuseList)),
    write(Next), nl,
    eliza_loop.

Several things are happening here. firstly, we retract the list of fallback phrases from Prolog's knowledge database and split it up into the first item in the list, and the rest of the items in the list.

Next we create a new list that contains the phrase that we at the front at the end, and then we put this new list back into Prolog's knowledge database.

Lastly, we output the fallback phrase that was at the beginning of the list (but is now at the end) to the user as our reply, before looping back around again with exliza_loop/1.

With that, we our eliza can respond to phrase containing certain keywords, exit when asked, and reply with a fallback phrase if it doesn't understand what was said. Below I have put a small questions and answers type section containing a few of the problems that I had whilst writing this. I've also included the complete Prolog source code that this post is based on.

Common Problems

I had several problems whilst writing this program. I've included a few of them below.

My eliza fails when it doesn't understand something instead of outputting an error.

I found that I didn't get an error message if I included :- after the retract statement. Removing it made it output the error below which I was then able to solve.

I get this error when writing the fallback phrase bit:

ERROR: No permission to modify static_procedure Name/Arity

I'm certain that I put the dynamic name/arity at the top of my prolog source code, but it doesn't work.

I got this because I forgot the :- before the word dynamic. If you are getting this error, this isthe reason why.

Source Code

:- dynamic list_of_excuses/1.

list_of_excuses(['I see.', 'Very interesting.', 'Tell me more.', 'Fascinating.']).

eliza :-
    write('Hello! My name is eliza.'), nl,
    eliza_loop.

eliza_loop :-
    write('Eliza > '),
    read(Input), respond(Input).

respond(Input) :-
    member(Term, Input),
    member(Term, [ quit, exit, leave ]),
    write('Goodbye!').

respond([my,name,is,Name | _ ]) :-
    write('Hello, '), write(Name), write('! Pleased to meet you.'), nl,
    eliza_loop.

respond([my,Thing,is,called,Name | _ ]) :-
    write(Name), write(' is a nice name for a '), write(Thing), write('.'), nl,
    eliza_loop.
respond(Input) :-
    member(Animal, Input),
    member(Animal, [ cat, dog, fish, hamster, gerbil, snake, tortoise ]),
    write('You just mentioned your '), write(Animal), write('. Tell me more about your '), write(Animal), nl,
    eliza_loop.

respond(Input) :-
    member(Term, Input),
    member(Term, [ hate, dislike ]),
    member(Term2, Input),
    member(Term2, [ you ]),
    write(':('), nl,
    eliza_loop.

respond([ _ ]) :-
    retract(list_of_excuses([ Next | Rest ])),
    append(Rest, [ Next ], NewExcuseList),
    asserta(list_of_excuses(NewExcuseList)),
    write(Next), nl,
    eliza_loop.

(Try it on SWISH)

Learning Prolog: Warm up for semester 2 with the cinema

The new learning prolog banner!

Learning Prolog is back, because apparently I am totally nuts and like to write long blog posts about the hardest programming language to use in existence. To kick off semester 2, we were given an old challenge: Write a cinema program that decides whether somebody can watch a given film or not. I remember this from my very first programming lab with Rob Miles - the first ever task that we were given was to build this exact program in C♯. Because Prolog is such a nasty and difficult language to learn, it has taken until now to learn all the concepts that you would need to write such a program.

In this post, I hope to guide you through the process of writing such a program in Prolog. To start with, here's an overview of what we will be building:

A Prolog program that will state whether or not a customer can see a movie depending on their age, the movie they want to see, and whether they have an adult with them.

We will need a few films to test this with. Here are the films that I was given in the lab:

Film Name Rating
How to Lose Friends and Alienate People 15
Death Race 15
Space Chimps U
The Chaser 18
Get Smart 12A

The first job here is to convert the above table into Prolog:

film('How to Lose Friends and Alienate People', 15).
film('Death Race', 15).
film('Space Chimps', 'U').
film('The Chaser', 18).
film('Get Smart', '12A').

Now we need some way to output the above so that the customer can see which films we are currently showing. Here's what I came up with:

all_films(FilmList) :-
    findall([ Film, Rating ], film(Film, Rating), FilmList).

list_films :-
    all_films(FilmList),
    list_films(FilmList, 0).
list_films([], _).
list_films([ [ FilmName, FilmRating ] | Rest ], Counter) :-
    write(Counter), write(' - '), write(FilmName), write(' - '), write(FilmRating), nl,
    NCounter is Counter + 1,
    list_films(Rest, NCounter).

As you should have come to expect with Prolog, the solution here is recursive. Firstly I define a rule to fetch me all the films with a quick findall/3. Then I define list_films/1 which calls all_films/1 to get all the films and passes them over to list_films/2, which actually does the work. I also have a counter here to keep track of the index of each film. This is important because we want to get the user to enter the number of the film that they want to watch.

Here's some example output of the above:

?- list_films.
0 - How to Lose Friends and Alienate People - 15
1 - Death Race - 15
2 - Space Chimps - U
3 - The Chaser - 18
4 - Get Smart - 12A
true.

This works by fetching all the films and loading them each into a list that contains their name and rating. These lists are then packaged into one big list, which is then spun through and outputted one by one, whilst incrementing the counter variable.

The next part of this problem is asking the user which film they want to see. Surprisingly, this isn't too tough.

ask_film(FilmNumber) :-
    write('Enter the number of the film that you would like to see: '),
    read(FilmNumber),
    true.

cinema_loop :-
    repeat,
    write('Welcome to our multiplex.'), nl,
    write('We are presently showing:'), nl,
    list_films,
    ask_film(FilmNumber),
    write('You chose option '), write(FilmNumber), write('.').

Here I define another rule to ask the user which film they want to see, and then define the main cinema loop. The main loop displays a welcome message, lists all the films that we are presently showing using the code we devised above, asks the user which film they want ot watch, and tells them which number they selected.

We are getting there, but telling the user which option they selected is a bit pointless, if you ask me. Let's upgrade it to tell us which film we selected and it's rating.

film_rating(FilmNumber, FilmRating) :-
    all_films(FilmList),
    nthelement(FilmNumber, FilmList, [ FilmName, FilmRating ]),
    write('You want to see '), write(FilmName), write(', which is a '), write(FilmRating), nl.

cinema_loop :-
    repeat,
    write('Welcome to our multiplex.'), nl,
    write('We are presently showing:'), nl,
    list_films,
    ask_film(FilmNumber),
    film_rating(FilmNumber, FilmRating),
    check_age(FilmRating),
    write('Enjoy the film!'), nl, true.

My code starts to get a little bit messy here (sorry!), but I've taken the cinema_loop/1 that we started above and upgraded to call film_rating/2. This new rule actually has a rather misleading name now that I think about it, but it's purpose essentially is to take a given film number and to return it's rating, whilst telling the user which film they selected.

film_rating/2 calls another rule that you might find familiar - the nth_element rule that I wrote in semester 1's last lab. GO and take a look at my other post if you are confused.

Now that we have that connector in place, we can start thinking about ratings. The rating system isn't as simple as it sounds when you start to think about it:

Rating Meaning
U Universal, suitable for all ages
PG Parental Guidance, suitable for all ages at parents discretion
12 No one younger than 12 can see this film
12A No one younger than 12 can see this film unless accompanied by an adult
15 No one younger than 15 can see this film
18 No one younger than 18 can see this film

Let's brack this down into chunks. In theory, we can do this with a single rule with 2 arities one for those rating that don't require the age of the customer, and those that do. We can write one part of the rule for each rating. Let's start with U:

check_age(FilmRating) :-
    FilmRating = 'U'.

Nice and simple, right? It succeeds if the film rating is 'U'. Let's move on. We can lump PG and 12A together if the customer is under 12 years of age:

check_age(FilmRating, Age) :-
    member(FilmRating, [ 'PG', '12A' ]),
    Age < 12,
    ask_adult(Adult),
    Adult = yes.

The above simple makes sure that the rating is either 'PG' or '12A', then it make sure that the customer is under 12, then it makes sure that the customer has an adult with them usng the rule below. If all of these comditions are met, then it succeeds.

ask_adult(Adult) :-
    write('Are you accompanied by an adult?'),
    read(Answer),
    member(Answer, [y, yes, yep]),
    Adult = yes,
    true.

If the user is 12 or over and wants to see a PG or a 12A, then we should let them through without asking them about an adult.

check_age(FilmRating, Age) :-
    member(FilmRating, [ 'PG', '12A' ]),
    Age >= 12.

Next we need to deal with the regular 12, 15, and 18 ratings. There are easy:

check_age(FilmRating, Age) :-
    not(FilmRating = 'PG'), not(FilmRating = '12A'),
    Age >= FilmRating.

We then need to connect the check_age/1 with the check_age/2. This is also fairly simple:

ask_age(Age) :-
    write('What is your age? '),
    read(Age).

check_age(FilmRating) :-
    ask_age(Age),
    check_age(FilmRating, Age).

If all else fails, then the customer mustn't be allowed to see the film. We should add another quick rule to tell the customer that they can't see the film before we are done:

check_age(_, _) :-
    write('Sorry, you can\'t see that film - try picking another one.'), nl,
    fail.

That completes the cinema program. Below you can find the source code for the whole thing that I based this post on. There are some unnecessary true.s floating around, but they are just relics from when I was debugging it and couldn't figure out what the problem was.

% Current films
film('How to Lose Friends and Alienate People', 15).
film('Death Race', 15).
film('Space Chimps', 'U').
film('The Chaser', 18).
film('Get Smart', '12A').

% Main loop
cinema_loop :-
    repeat,
    write('Welcome to our multiplex.'), nl,
    write('We are presently showing:'), nl,
    list_films,
    ask_film(FilmNumber),
    film_rating(FilmNumber, FilmRating),
    check_age(FilmRating),
    write('Enjoy the film!'), nl, true.

% Get all films
all_films(FilmList) :-
    findall([ Film, Rating ], film(Film, Rating), FilmList).

% Get the film with a given number
film_rating(FilmNumber, FilmRating) :-
    all_films(FilmList),
    nthelement(FilmNumber, FilmList, [ FilmName, FilmRating ]),
    write('You want to see '), write(FilmName), write(', which is a '), write(FilmRating), nl.

% Get the nth element
% From https://starbeamrainbowlabs.com/blog/article.php?article=posts%2F134-learning-prolog-lab-10.html
nthelement(0, [ Head | _ ], Head).
nthelement(N, [ _ | Tail ], Result) :-
    N > 0,
    NRecurse is N - 1,
    nthelement(NRecurse, Tail, Result).

% Check the user's age against the given film.
check_age(FilmRating) :-
    FilmRating = 'U'.
check_age(FilmRating) :-
    ask_age(Age),
    check_age(FilmRating, Age).
check_age(FilmRating, Age) :-
    member(FilmRating, [ 'PG', '12A' ]),
    Age < 12,
    ask_adult(Adult),
    Adult = yes, true.
check_age(FilmRating, Age) :-
    member(FilmRating, [ 'PG', '12A' ]),
    Age >= 12.
check_age(FilmRating, Age) :-
    not(FilmRating = 'PG'), not(FilmRating = '12A'),
    Age >= FilmRating.
check_age(_, _) :-
    write('Sorry, you can\'t see that film - try picking another one.'), nl,
    fail.

% Gets the user's film preference
ask_film(FilmNumber) :-
    write('Enter the number of the film that you would like to see: '),
    read(FilmNumber),
    true.

% Gets the user's age
ask_age(Age) :-
    write('What is your age? '),
    read(Age), true.

ask_adult(Adult) :-
    write('Are you accompanied by an adult?'),
    read(Answer),
    member(Answer, [y, yes, yep]),
    Adult = yes,
    true.

% Lists all films
list_films :-
    all_films(FilmList),
    list_films(FilmList, 0).
list_films([], _).
list_films([ [ FilmName, FilmRating ] | Rest ], Counter) :-
    write(Counter), write(' - '), write(FilmName), write(' - '), write(FilmRating), nl,
    NCounter is Counter + 1,
    list_films(Rest, NCounter).

Learning Prolog: End of Semester 1

The new learning prolog banner!

It's nearly Christmas (I should have a small Christmas surprise ready for you soon!), which also means that we've reached the end of the first series of Prolog labs. I'll continue posting this series once the labs start up again in semester 2, which starts on the 2nd of February.

The primary reason for writing this post, however, is to provide one central list of posts in this series so far.

Learning Prolog: Lab #10

The new learning prolog banner!

We are in double figures! Welcome to my solutions for the tenth and final lab session for this semester. This lab lets you in easy, and then hits you with a really nasty problem right at the end.

The first problem asked for a rule that returned the length of a list. I found this one easy:

listlength([], 0).
listlength([ _ | Tail ], Length) :-
    length(Tail, RecursiveLength),
    Length is RecursiveLength + 1.
?- listlength([ hurricane, typhoon, cyclone ], Length).
Length = 3.

I simply recurse over the list in question and add one to a counter variable on the way out. The next one is a bit harder, but still very easy - A rule that returns the nth element in a list.

nthelement(0, [ Head | _ ], Head).
nthelement(N, [ _ | Tail ], Result) :-
    N > 0,
    NRecurse is N - 1,
    nthelement(NRecurse, Tail, Result).
?- nthelement(2, [sequoia, baobab, redwood], Item).
Item = redwood .

My solution works very similary to my listlength/2 solution, but instead counts down from the number you give it until it reaches zero ,at which point it climbs back out of the recursion again and returns the item that it got up to.

The last problem was a really tough one. It demands flattened list containing all the elements in a given list of lists of arbitrary depth (exceptempty lists). It took me a while (and some help) in order to figure this one out:

squash([[]], []).
squash([], []).
squash([ [ HeadHead | HeadTail ] | Tail ], Result) :-
    squash([ HeadHead | HeadTail ], HeadResult),
    squash(Tail, TailResult),
    append(HeadResult, TailResult, Result).
squash([ Head | Tail ], Result) :-
    squash(Tail, TailResult),
    append([Head], TailResult, Result).

Cracking particular problem requires a new brain-breaking type of recursion, called Top-and-Tail recursion. It's specific to Prolog (as far as I know), and means that instead of just recursing over the tail of the list in order to iterate over it, you iterate over the head of the list as well.

Since Prolog lets us break arguments down to any depth we like, I break the incoming list down into its head and tail, and then I break the head down into its component head and tail in order to ensure that it is actually a list.

I then recurse over the head of the list ad the tail of the list separately, and concatenate the result of the two recursive calls at the end.

If the head isn't a list, then I only recurse over the tail, and append the head to the flattened tail on the way out.

I also declare that both an empty list and an empty lsit inside an empty list should return a single empty list. This allows us to avoid any rogue empty lists that might happen to be floating around from finding their way into the solution by mistake. Here's an example:

?- squash([[[a],b],[c],[d,[e],[]]], Result).
Result = [a, b, c, d, e] .

That concludes all the AI labs for semester 1, although I have another AI lab scheduled for the coming Monday. If it turns out that there's another lab, I'll post about it here. Otherwise, I'll resume this series in sesmeter 2.

Learning Prolog: Lab #9

The new learning prolog banner!

Sorry this post is rather late! I had multiple ACW deadlies to deal with, and I now have a nasty cold as of the time of writing :(

I had a bit of trouble with this lab - I originally lost the code that I had written due to a bug in my chromebook where it doesn't resume properly when I lift the lid...! Anyway, the main point of this lab was to practice the Prolog that we have learnt already. A lot. There were 7 problems to solve, 6 of which I have a solution for. The first two aren't very interesting, so I'll just include the code and some examples below and move on.

sbrlmember(Item, [ Head | Tail ]) :-
        Item = Head ;
        sbrlmember(Item, Tail).

lastitem([ LastItem | [] ], LastItem).
lastitem([ _ | Tail ], LastItem) :-
        lastitem(Tail, LastItem).
?- sbrlmember(Item, [ apple, orange, grape ]).
Item = apple ;
Item = orange ;
Item = grape ;
false.
?- lastitem([ car, bus, truck, lorry, aeroplane ], Result).
Result = aeroplane .

The above contains definitions for two rules: sbrlmember and lastitem. sbrlmember works exactly like the member function that's built into Prolog, and lastitem, given a list, tells you what the last item in that list is.

The next one in the sequence is a rule that, given a list, returns the reverse of that list. Here's my solution, and an example:

listreverse([ Head | [] ], [Head]).
listreverse([ Head | Tail ], Result) :-
    listreverse(Tail, TailReversed),
    append(TailReversed, [Head], Result).
?- listreverse([windows, max, linux], Result).
Result = [linux, max, windows] .

Basically, it recurses over the tail of the list until there is just a single item left, at which point it returns the head on it's own in a list. When it comes back out of the recursion, it sticks everything back on the end of the list again in the reverse order.

The next problem we were given was to, given a pair of lists, return a third list containing all the items that appeared in both of the original lists. I decided to cheat a bit here and use an accumulator

intersection([], _, []).
intersection([ Head | Tail ], ListB, Result) :-
    member(Head, ListB),
    intersection(Tail, ListB, RecResult),
    append(RecResult, [Head], Result).
intersection([ _ | Tail ], ListB, Result) :-
    intersection(Tail, ListB, Result).

Complicated problems call for complicated solutions, so I decided to recurse over the first list and check to see if the current item is present in the second list. If so, then we add it to the result - if not, then we simply ignore it and carry on recursing. When it hits the end o fthe recursion, I start it off with an empty list, which it then adds to as it climbs its way back out of the recursion.

?- intersection([snow, rain, wind, flame], [snow, flame], Result).
Result = [flame, snow] .

The last problem I built a solution for asked for a rule that deleted the given atom (I think that's what you call them in Prolog?) from the given list.

deleteall(_, [], []).
deleteall(Item, [ Head | Tail ], [ Head | Result ]) :-
    not(Item = Head),
    deleteall(Item, Tail, Result).
deleteall(Item, [ _ | Tail ], Result) :-
    deleteall(Item, Tail, Result).
?- deleteall(snake, [ squirrel, bird, cat, snake ], Result).
Result = [squirrel, bird, cat] .

My solution copies everything in the list over to the result (rather like the intersection problem above actually), unless the next item along is equal to the item we are supposed to be ognoring, in which case we skip it. I do this by adding a condition on the rule that copies the item over to the result that it can't be the item that we were told to remove.

That's the last problem from this lab - I'll have the solutions for the 10th lab up soon.

Learning Prolog: Lab #8 - findall/3

The new learning prolog banner!

This week's lab was all about findall/3, and a little bit more about lists. To summarise, findall lets you, well, um, find everything that matches a given rule or set of rules. For example, if we have the following dataset:

mountain(everest).
mountain(k2).
mountain(matterhorn).
mountain(kangchenjunga).
desert(sahara).
desert(gobi).
desert(atacama).

tall(everest).
tall(k2).
tall(kangchenjunga).

We could ask Prolog to give us a list of all the mountains in it's world. It's rather like issuing a database with an SQL query, asking it to find all the records that match a set of criteria and return them.

?- findall(Mountain, mountain(Mountain), MountainList).
MountainList = [everest, k2, matterhorn, kangchenjunga] .

?- findall(Mountain, (mountain(Mountain), tall(Mountain)), List).
MountainList = [everest, k2, kangchenjunga] .

?- findall(Desert, desert(Desert), DesertList).
DesertList = [sahara, gobi, atacama].

?- findall(Place, (desert(Place); mountain(Place)), Places).

Places = [sahara, gobi, atacama, everest, k2, matterhorn, kangchenjunga] .

As I demonstrated above, you can combine multiple criteria with a set of brackets and a few commas or semi-colons.

The other thing that we looked at was a rule that would return the last item in a list. Here's what I came up with:

% Stopping condition - stop when we reach the last item
lastitem([ LastItem | [] ], LastItem).
% If we haven't reached the end of the list, recurse on the rest of the list.
lastitem([ _ | Rest ], LastItem) :-
    lastitem(Rest, LastItem).

The above keeps throwing away the first item in the given list until it finds the last item, which it then stores in the variable LastItem. It knows which the last item is because lists in Prolog are always terminated with an empty list ([]). Here's an example of the above in action:

?- findall(Place, (desert(Place); mountain(Place)), Places), lastitem(Places, LastPlace), write('The last place is '), write(LastPlace), write('.'), nl.
The last place is kangchenjunga.
Places = [sahara, gobi, atacama, everest, k2, matterhorn, kangchenjunga],
LastPlace = kangchenjunga .

That brings us to the end of the 8th Prolog lab session. This post feels a bit short, but I'm sure that there will be more to post about next time. If you're interested, here is a link to the Prolog file that I have written whilst writing this post.

Prolog Visualisation Tool

A visualisation of depth first search in Prolog.

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!

Art by Mythdael