Starbeamrainbowlabs

Stardust
Blog


Archive


Mailing List Articles Atom Feed Comments Atom Feed Twitter Reddit Facebook

Tag Cloud

3d 3d printing account algorithms android announcement architecture archives arduino artificial intelligence artix assembly async audio automation backups bash batch blender blog bookmarklet booting bug hunting c sharp c++ challenge chrome os cluster code codepen coding conundrums coding conundrums evolved command line compilers compiling compression conference conferences containerisation css dailyprogrammer data analysis debugging defining ai demystification distributed computing dns docker documentation downtime electronics email embedded systems encryption es6 features ethics event experiment external first impressions freeside future game github github gist gitlab graphics guide hardware hardware meetup holiday holidays html html5 html5 canvas infrastructure interfaces internet interoperability io.js jabber jam javascript js bin labs latex learning library linux lora low level lua maintenance manjaro minetest network networking nibriboard node.js open source operating systems optimisation outreach own your code pepperminty wiki performance phd photos php pixelbot portable privacy problem solving programming problems project projects prolog protocol protocols pseudo 3d python reddit redis reference release releases rendering research resource review rust searching secrets security series list server software sorting source code control statistics storage svg systemquery talks technical terminal textures thoughts three thing game three.js tool tutorial twitter ubuntu university update updates upgrade version control virtual reality virtualisation visual web website windows windows 10 worldeditadditions xmpp xslt

Creating a HTTP Server in C♯

An image looks cool.

(Image from here.)

I discovered the HttpListener class in .NET the other day, and decided to take a look. It turns out that it's way easier to use than doing it all by hand as I had to do in my 08241 Networking module a few months ago. I thought I'd write a post about it so that you can see how easy it is and use the same technique yourself. You might want to add a HTTP status reporting system to your program, or use it to serve a front-end GUI. You could even build a real-time app with WebSockets.

As with all my tutorials - this post is a starting point, not an ending point. Refactor it to your heart's content!

To start off, let's create a new C♯ console project and create an instance of it:

using System;
using System.Net;

class MainClass
{
    public static void Main(string[] args)
    {
        HttpListener listener = new HttpListener();
    }
}

This should look pretty familiar to you. If not, then I can recommend the C♯ yellow book by Rob Miles. This is all rather boring so far, so let's move on quickly.

listener.Prefixes.Add("http://*:3333/");
listener.Start();

C♯'s HttpListener works on prefixes. It parses the prefix to work out what it should listen on and for what. The above listens for HTTP requests from anyone on port 3333. Apparently you can listen for HTTPS requests using this class too, but I'd recommend putting it behind some kind of proxy like NginX instead and let that handle the TLS certificates instead.

We also start the listener listening for requests too, because it doesn't listen for requests by default.


while(true)
{
    HttpListenerContext cycle = listener.GetContext();
    Console.WriteLine("Got request for {0} from {1}.", cycle.Request.RawUrl, cycle.Request.RemoteEndPoint);
    StreamWriter outgoing = new StreamWriter(cycle.Response.OutputStream);
}

This next part is the beginning of the main request / response loop. The highlighted line is the important one - it retrieves the next pending request, waiting for it if necessary. The following lines log to the console about the latest request, and set up a StreamWriter to make it easier to send the response to the requester.

The final piece of the puzzle actually sending the request and moving onto the next one.

outgoing.WriteLine("It works!");
outgoing.Close();
cycle.Response.Close();

Actually writing the response is easy - all you have to do is write it to the StreamWriter. Then all you have to do is call Close() on the stream writer and the Response object, and you're done! Here's the whole thing:

using System;
using System.Net;
using System.IO;

namespace HttpServerTest
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            HttpListener listener = new HttpListener();
            listener.Prefixes.Add("http://*:3333/");
            listener.Start();

            while(true)
            {
                HttpListenerContext cycle = listener.GetContext();
                Console.WriteLine("Got request for {0} from {1}.", cycle.Request.RawUrl, cycle.Request.RemoteEndPoint);
                StreamWriter outgoing = new StreamWriter(cycle.Response.OutputStream);
                cycle.Response.ContentType = "text/plain";
                outgoing.WriteLine("It works!");
                outgoing.Close();
                cycle.Response.Close();
            }
        }
    }
}

(Hastebin, Raw)

That's all you really need to create a simple HTTP server in C♯. You should extend this by putting everything that could go wrong in a try..catch statement to prevent the server from crashing. You could also write a simple find / replace templating system to make it easier to serve files from your new HTTP server. Refactoring the above to make it asynchronous wouldn't be a bad idea either.

Have you been building anything interesting recently? Post about in the comments below!

Getting started with arduino

An arduino and a simple circuit.

Since I've been playing around with the Arduino a bit recently (thank you Rob!) I thought I'd write a quick post on how you can get started with the arudino and it's many variants.

If you're into creating electronics and creating circuits, then the arduino is for you. The arduino is a small electronic board that you might find some variant thereof in your thermostat at home, or Rob's thing-o-matic for example. You'll probably find something akin to an arduino in most embedded systems.

To get started, you'll need to buy an Arduino Uno (you can probably find it cheaper elsewhere). Some LEDs, resistors, and jumper cables wouldn't hurt either.

Once you've got all that, you can start to have some fun. To compile and send programs to your new arudino, you'll need to download and install the Arduino IDE from the official arduino website (direct link for debian / ubuntu users). Once installed, connect your arduino to your computer using the supplied cable and open the IDE.

The menu options that need changing in the IDE

Next, we need to set the IDE up to send correctly compiled programs to our new board. Firstly, we need to tell the IDE what kind of board we have. Go to Tools->Board and select Arduino Uno. We also need to tell the IDE which programmer to use. Go to Tools->Programmer and select AVRISP mkII. Finally, we need to tell the IDE which serial port the arduino is connected on. Go to Tools->Serial Port and select the last item in the list. If the next steps don't work, try selecting a different option in this list until it works.

With that out of the way, we can start to test out our arduino! Arduinos are programmed using a variant of C, which is similar to GSGL. To get started quickly, let's send some example code to our arduino to start with. In the file menu, go to Examples->01. Basics and select Blink.

Selecting the example code in the file menu.

A new window will pop up containing the example code. To compile and send the code to your arduino, click the second button in from the left, with the right facing arrow on it. This will send the code to your arduino. Once it's done, you should see a flashing light on your arduino board!

The Arduino IDE interface.

The other buttons are also useful. Here's an explanation:

  1. Verify - Compiles and checks your code for syntax errors, but doesn't write it to the arduino.
  2. Upload - Compiles your code and sends it to your arduino.
  3. New - Creates a new document. This clears your existing tab! Use the down arrow below the 6 in the picture and select New Tab instead.
  4. Open - Opens an existing document. Again, this clears your existing tab.
  5. Save - This should be obvious.
  6. Opens the serial monitor. The serial monitor is like a very basic console which allows you to see what your arduino is saying and lets you send messages to it.

That just about covers my very basic getting started tutorial for the arduino. If you've got any questions or comments, please leave them down below.

Sources and Further Reading

TeleConsole: A simple remote debugging solution for awkward situations

Header image (Header image from here.)

Several times in the last few months I've found myself in some kind of awkward situation where I need to debug a C♯ program, but the program in question either doesn't have a console, or is on a remote machine. In an ideal world, I'd like to have all my debugging message sent to my development machine for inspection. That way I don't have to check the console of multiple different machines just to get an idea as to what has gone wrong.

C♯ already has System.Diagnostics.Debug, which functions similarly to the Console class, except that it sends data to the Application output window. This is brilliant for things running on your local machine through Visual Studio or MonoDevelop, but not so great when you've got a program that utilises the network and has to run on separate computers. Visual Studio for one starts to freeze up if you open the exact same repository on a network drive that's already open somewhere else.

It is for these reasons that I finally decided to sit down and write TeleConsole. It's a simple remote console that you can use in any project you like. It's split into 2 parts: the client library and the server binary. The server runs on your development machine, and listens for connections from the client library, which you reference in your latest and greatest project and use to send messages to the server.

Take a look here: sbrl/TeleConsole (GitLab) (Direct link to the releases page)

The client API is fully documented with intellisense comments, so I assume it should be very easy to work out how to use it (if there's something I need to do to let you use the intellisense comments when writing your own programs, let me know!). If you need some code to look at, I've created an example whilst testing it.

Although it's certainly not done yet, I'll be definitely be building upon it in the future to improve it and add additional features.

Pushing Git Commits to an SVN Repository

Yesterday I found myself in the awkward position in which I needed to push some commits in a git repository to an existing SVN repository. This came about because as soon as my 3D module was finished at University, I copied my code over to a private git repository and started working from there instead. As luck would have it, I ended up running into a few nasty issues and needed to push my extra commits to the original SVN repository.

Since it took me a while to work out how to accomplish this, I thought I'd write a blog post on it. Credit for this method goes to Pete Goodliffe for figuring out how to do it.

The first thing you need to do is to install git svn, if you haven't already. If you're on Windows, then you probably already have it if you've got git (which you'll need too). If you're not sure, simply type git svn into a command line (or terminal), and if you don't get a 'svn' is not a git command message, you've got it installed.

Next, you need to use git svn to clone your SVN repository. Even if you've got a clone sitting somewhere already, you should create a fresh one, just in case. This process may take a long time, depending on how many commits you've made to the SVN repository. Use the following command:


git svn clone {svnRepositoryUrl}

Replace {svnRepositoryUrl} with the URL of your remote SVN repository. Now that you've done that, cd into the created directory.

Next, we need to add the git repository as a new remote. To do this, type something like this:


git remote add -f remote-repo {gitRepoUrl}

Replace {gitRepoUrl}with the url of your remote git URL. Now we've set everything up, we can replay the remote git repository's commits overtop the commits in the SVN repository:


git rebase --onto remotes/git-svn --root remote-repo/master

Again, this may take a while. Once this command has completed, all you have to do is a quick git svn dcommit to push the new commits up to the SVN repository.

Alternatively you can push the SVN commits to the remote git repository by entering the following commands instead of the rebase command above:


git pull remote-repo master # Make sure that the local workspace is in sync with the remote git repo
git push remote-repo # Push the SVN commits to the remote git repo

That's about all I wanted to include in this post. If you found this post useful (and even if you didn't!), please leave a comment down below.

The Hull Pixelbot Meetup

Rob's Hull Pixelbot (Above: Rob's WiFi-enabled Pixelbot.)

Today Rob Miles was kind enough to give me a lift to the monthly hardware (or hull pixel bot) meetup. It was different to what I'm used to, but it was rather fun actually!

Rob Miles has built a kit that gives you the parts to build your very own Arduino-powered robot that trundles around on the floor. He's also managed to add a WiFi chip to it too - so you can (provided you write the code) connect to your pixel bot and control it remotely!

You can build your own by going to hullpixelbot.com.

I'll certainly be playing around with it and attending the next meetup (meetups are on the first Thursday of every month at 6:00pm at C4DI).

ES6 Features 13: Classes

Almost a year ago I finished a series on the new features of Ecmascript 6, the next version of Javascript. At the time there were one or two features remaining that I hadn't covered, but I didn't feel that today's browsers supported them well enough for me to write a blog post on them. Today, however, that has changed, for classes at least. In this blog post I'll explain by example how classes work in ES6.

Originally, I was against the idea of having classes in javascript. After using them for a while, I've decided to change my mind. They can bring organisation to an otherwise rather cluttered project, especially since the modules syntax hasn't yet landed.

If you've you're familiar C♯, then ES6 classes will feel a little bit familiar. Here's a simple example:


"use strict";
class Bicycle
{
    constructor(inPosition, inColour)
    {
        this.pos = inPosition;
        this.colour = inColour;
        this.wheelCount = 2;
        this.setup();
    }

    setup()
    {

    }

    update(dt)
    {
    }

    render(context)
    {
        // Do rendering stuff
    }
}

Very familiar (I hope). Classes in ES6 are defined using the class Tree { } syntax, with everything belonging to that class inside a set of curly braces, just like in C♯. Because javascript isn't a typesafe language, method declarations look a bit different. Essentially they are the same as a C♯ method declaration, just with the type names taken out.

The "use strict"; at the top is important - today's browsers don't let you use classes without it. I'll omit it in later examples for sake of simplicity, but you'll always need to remember to include it when using ES6 classes.

The constructor() method is, as you've probably guessed, the constructor of your class. Strange way of doing things, I know, but that's how it's declared. Note also that all variable initialisation is done in the constructor and not in the class body. Apparently class definitions are supposed to define an object's capabilities and not its members.

Calling a method from inside is an ES6 is easy too (see highlighted line #8), but it's important to understand what the this variable is in this context first (I could write a whole separate blog post about this). this is a special variable in javascript that holds the current context. In the case of an ES6 class, it holds the current instance of the current class. This is identical to C♯, but the difference is that you'd normally never need to use this in C♯ and it's required in ES6 - for both method access and variable access.

class Tree
{
    grow(dt, rate)
    {
        this.classMethodA(4, dt, this.someVariable);
    }

    // ...
}

White noise

Update: It turns out that ES6 does indeed support static methods (but not variables I don't think) natively via the static keyword. Here's an example:


class Tree
{
    constructor()
    {
        this.something = Tree.doComplicatedStuff();
        this.somethingElse = this.constructor.doComplicatedStuff();
    }

    static doComplicatedStuff()
    {
        // ...!
    }
}

Native static methods can be called in two ways (highlighted above). One is practically the same as the C♯ way of doing things, and the other is useful if for whatever reason you don't have the name of your own class handy.

Original sectional text

You can define static variables and methods too, although it's a little bit of a hack. Imagine I have this class:

class NoiseGenerator
{
    constructor()
    {
        // ...!
    }

    GetNoise(amount)
    {
        // ...!
    }
}
Let's pretend that we want all our noise generated with our class to use the same seedable random number generator. How about rand = new MyPRNG();? Or window.rand = new MyPRNG();? Or even this.rand = new MyPRNG()? Unfortunately, all of these methods have at least one problem with them (if you know what's wrong with them, comment down below!). Don't despair though, because we can exploit the fact that classes themselves are objects - and aren't read-only. With this knowledge, we can do something like this:

NoiseGenerator.rand = new MyPRNG(someSeed);
Remember to put the above _after_ the class definition - ES6 classes are a little bit like C++ classes in that they don't exist until the interpreter has executed them (unlike regular old functions). Then in the body of a method, you can access it with something like `NoiseGenerator.rand.nextInt(0, 10);`.

Too many classes

ES6 classes do infact support inheritance under the guise of sub classing. A good example is worth a thousand words I think:

class Vehicle
{
    constructor()
    {
        // ...
    }

    move()
    {
        console.log("Moving vehicle...");
    }

    start() { console.log("Starting..."); }
    stop() { console.log("Stopping."); }
}

class Train extends Vehicle
{
    move()
    {
        super.move();
        console.log("Moving train...");
    }
}

As demonstrated in the example above, classes can inherit from one another with the extends keyword instead of C♯'s colon. The super word replaces the functionality of C♯'s base keyword too. Other than that, there really isn't a lot more to say about inheritance in ES6 besides the fact that almost everything not described works as you'd expect it to in C♯.

That concludes my whirlwind tour of classes in ES6. If I explained in detail every little feature, you'd be here all week reading about it (and I'd be here for the better part of a month writing this post!). ES6 classes also support getters and setters, overriding the default constructor, and more.

Sources and further reading

Demystifying traceroute

A map of undersea cables. (Image from labnol. View the full map at submarinecablemap.com.)

A little while ago someone I know seemed a little bit confused as to how a traceroute interacts with a firewall, so I decided to properly look into and write this post.

Traceroute is the practice of sending particular packets across a network in order to discover all the different hops between the source computer and the destination. For example, here's a traceroute between starbeamrainbowlabs.com and bbc.co.uk:

traceroute to bbc.co.uk (212.58.244.23), 30 hops max, 60 byte packets
 1  125.ip-37-187-66.eu (37.187.66.125)  0.100 ms  0.015 ms  0.011 ms
 2  be10-147.rbx-g1-a9.fr.eu (37.187.231.169)  0.922 ms  0.912 ms  0.957 ms
 3  be100-1187.ldn-1-a9.uk.eu (91.121.128.87)  7.536 ms  7.538 ms  7.535 ms
 4  * * *
 5  ae-1-3104.ear2.London2.Level3.net (4.69.143.190)  18.481 ms  18.676 ms  18.903 ms
 6  unknown.Level3.net (212.187.139.230)  10.725 ms  10.434 ms  10.415 ms
 7  * * *
 8  ae0.er01.telhc.bbc.co.uk (132.185.254.109)  10.565 ms  10.666 ms  10.603 ms
 9  132.185.255.148 (132.185.255.148)  12.123 ms  11.781 ms  11.529 ms
10  212.58.244.23 (212.58.244.23)  10.596 ms  10.587 ms  65.243 ms

As you can see, there are quite a number of hops between us and the BBC, not all of which responded to attempts to probe them. Before we can speculate as to why, it's important to understand how a traceroute is performed.

There are actually a number of different methods to perform a traceroute, but they all have a few things in common. The basic idea exploits something called time to live (TTL). This is a special value that all IP packets have (located 16 bytes into an ipv4 header, and 7 bytes into an ipv6 header for those who are curious) that determines the maximum number of hops that a packet is allowed to go through before it is dropped. Every hop along a packet's route decreases this value by 1. When it reaches 0, an ICMP TTL Exceeded message is returned to the source of the packet. This message can be used to discover the hops between a given source and destination.

With that out of the way, we can move on to the different methods of generating this response from every hop along a given route. Linux comes with a traceroute utility built-in, and this is the tool that I'm going to be investigating. If you're on Windows, you can use tracert, but it doesn't have as many options as the Linux version.

Linux's traceroute utility defaults to using UDP packets on an uncommon port. It defaults to this because it's the best method that unprivileged users can use if they have a kernel older than 3.0 (check your kernel version with uname -r). It isn't ideal though, because many hosts don't expect incoming UDP packets and silently drop them.

Adding the -I flag causes traceroute to use ICMP ping requests instead. Thankfully most hosts will respond to ICMP pings, making it a much better probing tool. Some networks, however, don't allow ping requests to pass through their gateways (usually large institutions and schools), rendering this method useless in certain situations.

To combat the above, a new method was developed that uses TCP SYN packets instead of UDP or ICMP ping. If you send a TCP SYN packet (manipulating the TTL as above), practically all hosts will return some kind of message. This is commonly referred to as the TCP half-open technique, and defaults to port 80 - this allows the traceroute to bypass nearly all firewalls. If you're behind a proxy though I suspect it'll snag on it - theoretically speaking using port 443 instead should rectify this problem in most cases (i.e. traceroute -T -p 443 hostname.tld).

Traceroute has a bunch of other less reliable methods, which I'll explain quickly below.

  • -U causes traceroute to use UDP on port 53. This method usually only elicits responses from DNS servers along the route.
  • -UL makes traceroute use udplite in a similar fashion to UDP in the bullet point above. This is only available to administrators.
  • DCCP can also be used with the -D. It works similar to the TCP method described earlier.
  • A raw IP packet can also be used, but I can't think of any reasons you'd use this.

That just about covers all the different traceroute methods. If you have any questions, please leave a comment below.

SnoozeSquad.js - Finally a decent lazy image loader

It's been on my todo list for positively ages, but I've finally gotten around to replacing the existing lazy image loading on this website (not on the blog yet, sorry!) with a new one of my own devising.

Lazy image loading is a technique in which you only load images no a given webpage if they are near the user's field of view. This saves bandwidth by preventing images that are never seen from being downloaded.

Since I've been unable to find a good, solid, reliable lazy image loading script on the web, I thought it best to post about it here so that you can use it too.

Link: SnoozeSquad (Direct download)

The Graphics Pipeline

Since the demonstration for my 3D work is tomorrow and I keep forgetting the details of the OpenGL graphics pipeline, I thought I'd write a blog post about it in the hopes that I'll remember it.

In case you didn't know, OpenGL uses a pipeline system to render graphics. Basically, your vertices and other stuff go in one end, and a video stream gets displayed at the other. This pipeline is made up of number of stages. Each stage has it's own shader, too:

The OpenGL pipeline.

There are rather a lot of stages here, so I've made this table that lists all the different shaders along with what they do:

Stage Programmable? Function
Vertex Shader Yes Raw vertex manipulation.
Hull Shader No Aka the Tessellation Control Shader. Determines control points for the tessellator. Although it's fixed function, it's highly configurable.
Tessellator No Subdivides surfaces and adds vertices using the control points specified in the hull shader.
Domain Shader Yes Aka the Tessellation Evaluation Shader. Adds details to vertices. Example uses include simplifying models that are far away from the camera. Has access to the control points outputted by the hull shader.
Geometry Shader Yes Superseded by the tessellator (see above). Very slow.
Rasterisation No Fixed function. Converts the models etc. into fragments ready for the fragment shader.
Fragment Shader Yes Insanely flexible. This is the shader that is used to add most, if not all, special effects. Lighting and shadows are done here too. Oddly enough, Microsoft decided that they would call it the "Pixel Shader" in DirectX and not the fragment shader.
Compute Shader Yes Not part of the graphics pipeline. Lets you utilise the power of the matrix calculator graphics card to do arbitrary calculations.

The tessellator is very interesting. It replaces the geometry shader (which, although you can technically use, you really shouldn't), and allows you to add details to your model on the GPU, thereby reducing the number of vertices you send to graphics card. It also allows you to customize your models before they hit rasterisation and the fragment shader, so you could simplify those models that are further away, for instance.

As an example in our lecture, we were shown the Haven Benchmark. Our lecturer turned the tessellator on and off to show us what it actually does. Since you can't see what I saw, here's an animation I made showing you the difference:

The other pipeline to be aware of is the coordinate pipeline. This pipeline specifies how coordinates are transformed from one space to another. Here's another diagram:

The coordinate pipeline.

Again, this looks complicated, but it isn't really. A similar process would be followed for 2D graphics as well as 3D ones. If you take it one step at a time, it doesn't seem so bad.

  • Model Space - This refers to coordinates relative to any given model. Each model will have the coordinates of each of its vertices stored relative to its central point.
  • World Space - Multiplying all of a model's coordinates by the model matrix brings it into World Space. World space is relative to the centre of your scene.
  • View Space - Multiplying all the coordinates in a world by the view matrix brings everything into into View Space. View Space is relative to the camera. It is for this reason that people say that you cheat and move everything around the camera - instead of moving the camera around a scene.
  • Normalised Device Space - Multiplying everything in view space by the projection matrix brings it into Normalised Device Coordinates. Graphics cards these days apparently like to consider points between $(-1, -1, -1)$ and $(1, 1, 1)$ (if you're OpenGL, that is. DirectX is different - it prefers $(-1, -1, 0)$ to $(1, 1, 1)$ instead). Points in this space are called Normalised Device Coordinates and anything outside of the aforementioned ranges will be cut off. No exceptions.
  • Image Space - When your scene has been through the entirety of the Graphics pipeline described above, it will find itself in Image Space. Image space is 2D (most of the time) and references the actual pixels in the resulting image.

Converting between all these different coordinate spaces is best left up to the vertex shader - it's much easier to shove a bunch of transformation matrices at it and get it to do all the calculations for you. It's so easy, you can do it in just 11 lines of vertex shader code:

#version 330
uniform mat4 uModel; // The model matrix
uniform mat4 uView; // The view matrix
uniform mat4 uProjection; // The projection matrix

in vec3 vPosition; // The position of the current vertex

void main() 
{ 
    gl_Position = vec4(vPosition, 1) * uModel * uView * uProjection;
}

If you made it this far, congratulations! That concludes our (rather long) journey through the graphics pipeline and its associated coordinate spaces. We looked at each of the various shaders and what they do, and learnt about each of the different coordinate spaces involved and why they are important.

I hope that someone besides myself found it both useful and educational! If you did, or you have any questions, please post a comment below. If you have spotted a mistake - please correct me in the comments below too! I try to make sure that posts like this one can be used by both myself and others as a reference in the future.

Sources

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).

Art by Mythdael