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!

Thoughts on GitHub's new theme

The other day, I got a notification on GitHub asking me to try their new website redesign. Now that I've had time to think about it, I thought that I'd make a post on what I think about it.

To start with, the design as a whole feels more modern and a little bit more 'flat'. I'm not sure if this is a good thing or not yet, though it does make the interface feel less cluttered. This makes the content that the interface is presenting easier to digest.

The only exception to this is the top of the repository page, especially the code view (the view that you see by default). Having the different sections of the repository along the top rather than down the side makes it feel like there is more going on than there was before - and it can feel a little bit overwhelming at times. Add to this the new "Add file" and "Find file" buttons, and it really starts to feel rather crowded.

Having said that, cutting the design down to use a single column makes the interface a bit more consistent with the mobile view. This is a good thing - although I found that reducing the width of the page caused a horizontal scrollbar to appear - perhaps it would be better to allow the new design to resize to fit smaller screens? It also opens up more space that can be used to display other things - like the list of a repository's issues, or the network graph in the "Graphs" section (there's a bug with the network graph by the way - it appears to be cut off just before the edge of the box).

Having a single wide column also makes a repository's README (and other markdown documents) easier to, um, read. It makes them feel more like a webpage and less like a file that someone's uploaded, though this wasn't a huge issue for me before.

All in all, GitHub's new interface is an improvement. It's an improvement overall, which makes the interface feel more modern. The top of the repository view feels rather cluttered and definitely needs rethinking.

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

The Atom Editor is Awesome

Recently a friend of mine (who you can find on GitHub here) reintroduced me to the atom editor, which is built by GitHub. I looked at it a while back, but it was too unstable and lacked too many features for me to consider using it as my main editor. Fast forward a few years, and it's much more stable. It even comes with batteries included - it has an awesome files panel (in which you can open multiple folders), a GUI for the settings (which brackets doesn't have), and a package ecosystem which can be utilised without leaving atom. It shows you the readme for packages too, so you always know how to use packages that you've got installed (or are considering installing).

If you've heard of atom before, give it another go! You might be surprised. If you haven't, you don't know what you're missing out on.

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!

On CPU Registers in Assembly

I've been given some directed reading from the Intel Software Developer's Manual recently, and I found it complicated enough that I had to make about 2 1/2 pages of notes on what I read. This post is an attempt to explain to you what I learnt, in the hopes that I don't forget it! There will probably be mistakes in here - please point them out in the comments below!

The x86 instruction set contains a number of registers, each of which can be accessed in a number of different ways depending on the number of bits you wish to get or set.

Description	8 bit (byte)	16 bit (word)	32 bit (dword)	64 bit (qword)
General purpose	AL	AX	EAX	RAX +
General purpose	BL	BX	EBX	RBX +
General purpose	CL	CX	ECX	RCX +
General purpose	DL	DX	EDX	RDX +
General purpose (high byte)	AH *	-	-	-
General purpose (high byte)	BH *	-	-	-
General purpose (high byte)	CH *	-	-	-
General purpose (high byte)	DH *	-	-	-
?	DIL +	DI	EDI	RDI +
?	SIL +	SI	ESI	RSI +
Base Pointer	BPL +	SP	ESP	RSP +
Stack Pointer	SPL +	BP	EBP	RBP +
General Purpose	R8L +	R8W +	R8D +	R8 +
General Purpose	R9L +	R9W +	R9D +	R9 +
General Purpose	R10L +	R10W +	R10D +	R10 +
General Purpose	R11L +	R11W +	R11D +	R11 +
General Purpose	R12L +	R12W +	R12D +	R12 +
General Purpose	R13L +	R13W +	R13D +	R13 +
General Purpose	R14L +	R14W +	R14D +	R14 +
General Purpose	R15L +	R15W +	R15D +	R15 +

This table requires some explanation. Registers suffixed with * may only be utilised in 32 bit assembly. Similarly, registers suffixed with + may be utilised in 64 bit assembly only. Each row is a register, and each column represents a different number of bits. For example, the EAX register can be accessed as an 8 bit register with AL, 16 bit as AX, 32 bit as EAX, and 64 bit as RAX.

The exception here is the AL, BL, CL, DL, AH, BH, CH and DH registers. These actually refer to the same register. Let's take AL and AH for example. The AL register refers to the first 8 bits of the AX register, and the AH register refers to the second 8 bits. This is called the Low byte and the High byte.

In addition to the registers above, there are two others which can also be accessed as 8, 16, 32 and 64 bit registers:

Description	16 bit	32 bit	64 bit
Instruction Pointer	IP	EIP	RIP
CPU Flags	FLAGS	EFLAGS	RFLAGS

These registers should not be written to under normal usage though, as the CPU uses these to maintain its internal state. The instruction pointer points to the instruction that the CPU is currently executing, whereas the CPU Flags register holds all of the current flags, such as the result of a cmp (comparison).

That concludes this post on CPU registers. I don't think I can quite believe I'm posting this actually.... a year ago I would never have suspected I'd be learning about how to program the CPU itself in assembly.

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!

The Big Wheel in HTML5

Just in time for Hull Fair to leave (yes I know they left last week), I've finished recreating the big wheel using the HTML5 Canvas. It's even got search lights and gradients.

Here's a link to the Big Wheel - Make sure that you use a recent browser (I'm using ES6 classes).

The basic pattern I used to create it was to break the scene down into different things, create a different class for each thing (except the background), and then break each thing down into its component parts. Each component part then got its own drawing function, which are then all called by the master renderer function for that class.

In order to position everything correctly, I abused context.save(), context.restore(), context.translate() and context.rotate(). Since the saving / restoring of the canvas state works like a stack, you can push as many drawing states to the stack as you like, and then pop them all off when you're done.

If anyone is interested in proper 'making of' post, please comment down below and I'll write one up!.

Static Variable Memory Allocation

Recently we were asked in an Advanced Programming lecture to write a program that proves that static variables in C++ are located in a different area of memory to normal variables. This post is about the program I came up with.

But first I should probably explain a little bit about memory allocation in C++. I'm by no means an expert (I'm just learning!), but I'll do my best.

There are two main areas of memory in C++ - the stack and the heap. The stack is an ordered collection of data that contains all the local variables that you define. It grows downward from a given address in memory. The stack is split up into frames, too, with each frame being a specific context of execution. You can find more information about this in the Intel Software Developer's Manual, Section 6.2.

The second area of memory is the heap. The heap is a large portion of memory that can be used for storing large lumps of unordered data. I haven't taken a look at this yet, so I don't know much more about it.

Apparently variables that are declared to be static are not located in the stack (where they are located I'm not entirely sure), and we were asked to prove it. Here's what I came up with:

#include <iostream>
#include <string>

using namespace std;

void staticTest()
{
    static int staticD = 0;
    cout << "staticD: " << &staticD << endl;
}

int main()
{
    int a = 50;
    int b = 200;
    int c = 23495;

    cout << "a: " << &a << endl;
    cout << "b: " << &b << endl;
    cout << "c: " << &c << endl;

    staticTest();

    int e = 23487;
    cout << "e: " << &e << endl;

    //cin.get();

    return 0;
}

The above simply creates 3 normal variables, outputs their addresses, calls the staticTest() function to create a static variable and output it's memory address, and then creates a 4th normal variable and outputs its address too. The above program should output something like this:

a: 0091F8C4 b: 0091F8B8 c: 0091F8AC staticD: 00080320 e: 0091F8A0

In the above output, the normal variables a, b, c, and e are all located next to each other in memory between the adresses 0091F8C4 and 0091F8A0 (note how the memory address is decreasing - the stack grows downward, like a stalactite). The static variable staticD, however, is located in an entirely different area of memory over at 00080320. Since it's located in an entirely different area of memory, it's safe to assume, I think, that static variables are not stored in the stack, but somewhere else (I'm not sure where - the heap maybe?).

If you know where they are stored, please leave a comment below!