Saturday, 28 December 2013

Playing with Prolog

If you ask a number of computing science graduates (especially from the 90's) a few will have used the Prolog language at some point. Prolog is a logic language - think of it as defining a lot of facts and matching the fact with some data (like doing a database lookup). You run a "query" by matching your rules to your facts.

In my final year of my degree I worked on a project to create a "Graphical Interface for Prolog". The project represented (I think) 25% of the final score for the year and this project made me a developer. The idea for the project came from a poll of possible projects - I was told at the end that they thought the work that would be done in this project would be mainly theoretical. However, I ended up producing a "product" - in fact two products. (I also ended up winning the IBM prize that year for the best project).

We already had a Prolog interpreter for the classes we did in Artificial Intelligence - and the source code for it, which was written in C by Fernando Pereira whilst he was doing a PhD at Edinburgh University. I took his code and added some hooks into it to allow it to be extended. This gave a mechanism to add new methods working with the Prolog data types. I then wrote a set of graphical predicates (essentially functions that said whether they worked or not - can could pass back data).

For a few years I had been meaning to try and get this up and running again. I did have the source code - but on 5.25" floppy disks (which I can't read any more). But I did have the printouts.

I looked around on the internet for a Prolog interpreter and found Prolog.NET for which there was source code (written in C#). So, it being the holidays I decided on doing a bit of sofa coding - although after four or five hours, I do wish I had just sat at a desk with multiple monitors and to save all the papers thrown about the floor!

So, here are a few instructions if you want to do your own extensions. The main piece of code to add to is Library.cs which has a list of predicates and functions. I added the following code.
standard.Add("graphics", 1, new PredicateDelegate(Graphics.graphics), false);
standard.Add("axes", 2, new PredicateDelegate(Graphics.axes2), false);
standard.Add("grset", 2, new PredicateDelegate(Graphics.grset), false);
standard.Add("point", 1, new PredicateDelegate(Graphics.point), false);
standard.Add("line", 2, new PredicateDelegate(Graphics.line), false);
standard.Add("rectangle", 2, new PredicateDelegate(Graphics.rectangle), false);
standard.Add("wait", 1, new PredicateDelegate(Graphics.wait), false);
These predicates that I am defining (graphics, axes, grset, point, line, rectangle) are the same ones I did twenty years ago - just need to do an implementation. My implementation will be with Windows Forms - but without events. This makes it difficult to get mouse button presses, so I have another predicate (wait) which will wait for a period of time.

Other examples of code already written is in the folder LibraryMethods. I added a file Graphics.cs and changed the namespace and the class definition as below
namespace Prolog
{
    internal static class Graphics
    {
       // Your code
    }
}
I initially started "hacking" the code trying to keep track of an implementation of a Windows Form instance within my Graphics class. But stopped. The class was now doing more than one thing - dealing with the Prolog predicates as well as working out the Windows Forms. And was getting confusing.

Looking at my old project in C I had a set of methods called s1wg - Simple One Window Graphics. The implementation behind this was with X-Windows. Guess what - I decided to use the same "interface" - although now within a class. It was actually good to see that the implementation I did all these years ago (before getting real experience) was essentially implementing the S of SOLID (Single Responsibility Principle). I could write this code separately (in another project) and check it was working without worrying about the Prolog part (and that was giving me some problems as well). So s1wg is a simple class with methods to
  • Constructor
  • Close down (close the window)
  • Create a window (with specified position, size and title)
  • Draw a point
  • Draw a line (between two positions)
  • Draw a rectangle (with a position, width and height)
I then went back to work with the Prolog parts. The predicates we have are
  • graphics - with a parameter to initialise or close (e.g. graphics(initialise) or graphics(close)).
  • axes - to define a virtual axes (e.g. axes([-1,-8],[8,2])).
  • grset - to set something (e.g. grset(size,[400,400]) sets the window size in pixels)
  • point - to draw a point using virtual co-ordinates (e.g. point([3,3])).
  • line - to draw a line between virtual co-ordinates (e.g. line([2,5],[5,6])).
  • rectangle - to draw a rectangle a particular position with specified width and height (e.g. rectangle([1,3],[5,6])).
  • wait - taking a parameter for a delay in milliseconds (e.g. wait(100)).
I'll get the code put up somewhere in case anyone wants to try this. Here is however an example of some of the code
public static bool line(WamMachine machine, WamReferenceTarget[] arguments)
{
    Debug.Assert(arguments.Length == 2);

    WamCompoundTerm lowerLeft = arguments[0].Dereference() as WamCompoundTerm;
    WamCompoundTerm upperRight = arguments[1].Dereference() as WamCompoundTerm;

    if (lowerLeft == null || upperRight == null)
        return false;

    if (lowerLeft.Functor == Functor.ListFunctor && 
        upperRight.Functor == Functor.ListFunctor)
    {
        if (lowerLeft.Children.Length != 2 || upperRight.Children.Length != 2)
            return false;

        double? llX = GetDouble(lowerLeft.Children[0]);
        WamCompoundTerm t = lowerLeft.Children[1].Dereference() as WamCompoundTerm;
        double? llY = GetDouble(t.Children[0]);

        double? urX = GetDouble(upperRight.Children[0]);
        t = upperRight.Children[1].Dereference() as WamCompoundTerm;
        double? urY = GetDouble(t.Children[0]);

        if (llX == null || llY == null || urX == null || urY == null)
            return false;

        s1wg.DrawLine(ScaleX((double)llX), ScaleY((double)llY), 
                      ScaleX((double)urX), ScaleY((double)urY));
    }
    return true;
}
This piece of code is checking for two parameters - which are Prolog lists, e.g. line([3,4],[7,8]). From this you need to extract the values (as WamCompoundTerm) and then check that we have lists - then the lists both have two entries. I wrote a method to extract a double from each element. I had major problems with doubles, so ended up writing this bit of code
private static double? GetDouble(WamReferenceTarget argument)
{
    WamValueDouble operandDouble = argument.Dereference() as WamValueDouble;
    Double d = 0.0d;

    if (operandDouble == null)
    {
        WamValueInteger operandInteger = argument.Dereference() as WamValueInteger;
        if (operandInteger == null)
        {
            WamValueString operandString = argument.Dereference() as WamValueString;
            if (operandString != null)
            {
                if (Double.TryParse(operandString.Value, out d))
                {
                    return d;
                }
                else 
                    return null;
            }
            else
                return null;
        }
        else
            return (double)operandInteger.Value;
    }
    else
        return operandDouble.Value;
}
Ok - definitely needs cleaning up. I check if I can get a double (which I cannot ever get working), then check if we have an integer - if it isn't an integer I check for a string that can be converted into a double. Note I am using the nullable double functionality. I am pretty sure I told my apprentices that if you start using structures like this it is probably a "code smell" of a bad design!

There are some other methods (ScaleX and ScaleY) that translate between the virtual a real co-ordinates.

What was the point of this graphical interface. It allowed you to see problems solved graphically. My first one isn't really a logic problem, but shows the use of look-ups. This exercise is "chain encoded images" - for a chain of numbers I draw lines in the direction depending on each number.

Firstly, lets have some "facts"
vector(["0"],[1,0]).
vector(["1"],[1,1]).
vector(["2"],[0,-1]).
vector(["3"],[-1,1]).
vector(["4"],[-1,0]).
vector(["5"],[-1,-1]).
vector(["6"],[0,1]).
vector(["7"],[1,-1]).
These are a list of vectors - if I specify "1" I will move 1 unit on the X axis and 1 unit on the Y axis. So if you execute the command
:-vector(["0"],C).
You will get output that C is [1,0]. Next I will have a predicate newposition which will calculate a new position
newposition([X1,Y1],[DX,DY],[X2,Y2]) :-
    (X2 is (X1 + DX)),
    (Y2 is (Y1 + DY)).
Running the following command
:-newposition([3,4],[1,2],NewPosition).
Then you will get the NewPosition as [4,6]. Hooking this up to vector you can use this like
:-vector(["2"],Delta),
newposition([4,2],Delta,NewPosition).
will give the output
Delta = [0,-1]
NewPosition = [4,1]
One of my main issues with this implementation was getting lists working. Lists in Prolog are managed a the first element in the list - and the remaining items. The code to draw the chain consists of two predicates. Prolog can/is a very recursive language. The first version we have of this predicate does the main work
drawchain([H|T],S,P) :-
    vector([H],D),
    newposition(P,D,N),
    line(P,N),
    wait(100),
    drawchain(T,S,N).
Here the drawchain predicate takes a list as the first parameter[H|T] where H is the head of the list (the first element) and T is the tail (the remaining elements). The remaining parameters are S (for start position) and P (for current position). Take each line in turn
  • vector([H],D) uses the head element to get the value D (the delta/change from position)
  • newposition(P,D,N) calculates the new position N using the current position P and delta D
  • line(P,N) draws a line between P and N
  • wait(100) will wait 100 millseconds
  • drawchain(T,S,N) will call the drawchain predicate with parameters S (the start position) and N (the new position we just calculated) with T being the tail of the list.
The next predicate is the stop condition - when the list is empty. In this case we want the predicate to draw a line from the current position to the start position (the "parameters" P and S respectively).
drawchain([],S,P) :-
    line(P,S).
Now to execute this I have the predicate below
chains :-
  Chain is ["0","1","6","3","4","5","2"],
  axes([-5,-2],[11,6]),
  graphics(initialise),
  drawchain(Chain,[0,0],[0,0]).
Which is executed with
:-chains.
And you get this.

Chain Encoded Images


It's been really quite fun to play with this. Not sure if I have wasted a day of my time, but interesting to see the work I did a few years ago in operation. I have other examples to get up and running with this (Towers of Hanoi, Binary Trees and Travelling Salesman) which I implemented with this interface. As well as completing the graphics predicates (text, filled shapes etc.)

The good news is that I did in less than a day work that I did over a three month period in 1990 (albeit with a little bit of an idea now of what I am doing).

Friday, 6 December 2013

First view of parallel programming in C#

I have my current apprentice group sitting an assessment in software testing yesterday. Whilst they were doing this I thought I would investigate parallel computing in C#/.Net.

This is something I was very heavily involved with from about 1997 to 2000. At the time I was working in Schlumberger with MPP (massively parallel computers) – mainly IBM SP/2 (now IBM e-series), Silicon Graphics Origin Servers and Sun SparcStations. In the office (in 1999) we had a sixteen processor IBM SP/2 – but I also worked closely with IBM, SGI and Sun to visit them and use servers with up to 500 processors, including several weeks spent at IBM in Poughkeepsie in upstate New York and Cray Park (SGI’s HQ at the time) in Minnesota.

What I was looking at was something I could do on my own laptop, which has an Intel i5 with 4 cores. Could I get a speed-up and how easy would it be to implement. Previously I used libraries like MPI (Message Passing Interface) and PVM (Parallel Virtual Machine) to provide a common approach for all the platforms that we supported.

I looked for some reference material (see http://www.microsoft.com/en-gb/download/details.aspx?id=19222) which I could work through, but needed some examples to see it in operation. This gives an examples – however, I would strongly recommend read this to understand what some of the issues might be.

I you are reading this looking for asynchronous programming in another thread (i.e. doing some work/calculation whilst loading a page) then this is the wrong article. This will be about solving a problem – and I’ll start with a simple one, but eventually maybe use it for some mathematical puzzle.

The problem that I will look to solve will be to perform the addition of an array of numbers to get a sum. I’ll work with an array of 500,000,000 shorts – and these are initialised via a loop with the current number of milliseconds. I just needed some values in the array. Something more “real” or even “random” would be better, but I just need some numbers.

The code to do this will be

private static short[] numbers = new short[500000000];

static void InitialiseTask()
{
    for (int i = 0; i < numbers.Length; i++)
    {
        numbers[i] = (short) DateTime.Now.Millisecond;
    }
}

To perform the sum of this array the sequential code would be

static void SequentialTask()
{
    Console.WriteLine("Starting Sequential Task");
    long sum = 0;
    for (int i = 0; i < numbers.Length; i++)
    {
        sum += numbers[i];
    }
    Console.WriteLine("Sum {0}", sum);
}

I am going to package these up with a method to record start and end times

static void Task(Action task)
{
    DateTime startTime;
    Console.WriteLine("Starting {0}", task.Method);
    startTime = DateTime.Now;

    // Run the task
    task.Invoke();
    Console.WriteLine("{0}", task.Method);
    Console.WriteLine("-- START {0:hh:mm:ss.fff} FINISH {1:hh:mm:ss.fff} MS {2}",
        startTime, 
        DateTime.Now, DateTime.Now.Subtract(startTime).TotalMilliseconds);
}

So that my main program would be

static void Main(string[] args)
{
    Task(InitialiseTask);
    Task(SequentialTask);
}

And running this gave this result



So let’s turn the sequential task into a parallel task. We will split this up into two summations – the first one will sum the first 250,000,000 values and the second one the last 250,000,000 values. We will then add these two sum together to get the final sum.

We have method below which takes as parameter a task number – which will determine which part of the array we will count. The return is a long – not an int or short which will be too small.

static long ParallelSum(int taskNumber)
{
    Console.WriteLine("Starting Parallel Task {0}", taskNumber);
    long sum = 0;
    int start, end;
    if (taskNumber == 0)
    {
        start = 0;
        end = numbers.Length / 2;
    }
    else
    {
        start = numbers.Length / 2;
        end = numbers.Length;
    }

    for (int i = start; i < end; i++)
    {
        sum += numbers[i];
    }
    Console.WriteLine("Sum for task {0} is {1}", taskNumber, sum);
    return sum;
}

I know I have explicitly set the start/end points of the loop – rather than calculate them. Next for the .Net magic (I always tell my apprentices that there is no magic, but this is quite cool).

static void ParallelTask()
{
    Console.WriteLine("Starting Parallel Tasks");

    long[] sums = new long[2];
    Parallel.For(0, 2, task =>
        {
            sums[task] = ParallelSum(task);
        });

    long totalSum = 0;
    foreach (long sum in sums)
        totalSum += sum;

    Console.WriteLine("Total Sum {0}", totalSum);
}

We use the magic Parallel.For(inclusiveStart, exclusiveEnd, Action body). This will run each iteration – but in parallel. The body (delegate) is run once per iteration. So here the delegate ParallelSum will be run with arguments 0 and 1 (i.e. from and including inclusiveStart of 0 to exclusiveEnd of 2 – i.e. not 2).

I have created a local array variable to save the summations of each task and retrieved at the end of each task that summation. Once all the tasks have been completed a total sum is created. 

Modifying the main program to perform the parallel task as below

static void Main(string[] args)
{
    Task(SequentialInitialiseTask);
    Task(SequentialTask);
    Task(ParallelTask);
}

Giving output of



With the sequential task taking 1621 milliseconds and the parallel task 1296. In a further task (where I didn't do anything else on my laptop the results were 1588 ms against 844. Which is even more impressive. I am however concerned about the nearly six minutes to set the values in the array. So let’s make a parallel version of that. The main program will look at that

static void Main(string[] args)
{
    Task(ParallelInitialiseTask);
    Task(SequentialTask);
    Task(ParallelTask);
}

The task to initialise the array in parallel

static void ParallelInitialiseTask()
{
    Console.WriteLine("Starting Parallel Tasks");
    Parallel.For(0, 2, ParallelInitialise);
}

static void ParallelInitialise(int taskNumber)
{
    Console.WriteLine("Starting Parallel Task {0}", taskNumber);
    int start, end;
    if (taskNumber == 0)
    {
        start = 0;
        end = numbers.Length / 2;
    }
    else
    {
        start = numbers.Length / 2;
        end = numbers.Length;
    }

    for (int i = start; i < end; i++)
        numbers[i] = (short)DateTime.Now.Millisecond;
}

When you run this the results are



Showing a good speed up.

The splitting up of the problem (i.e. each task working with its own part of the array) is known as partitioning using domain decomposition. Here we have multiple tasks doing the same thing – each task handling a portion of the data. 

My processor has two cores and four logical processors – so the next step is to look at splitting the problem up more. I’d also like to look at the tools available to view the task running. Maybe more next time, if I get a few hours of fun!

Also need to investigate what thread safe really means, locking and a review of all the costs involved. The article mentioned earlier has a lot of detail – and hopefully I can get off the line with some simple examples. Although I need to dig out some other typical problems to solve.

Note: A server like a SP/2 was essentially multiple RS/6000 workstations networked together with a big fast networking switch – and a Silicon Graphics Origin has what could be described as a shared memory architecture, but each piece of memory will be associated with a processor – a processor accessing the memory local to that processor will get quicker access than to other memory.