Object Thinking - Objects have actions

This post follows on from Object Thinking - Objects: a neurological basis

The paper being reviewed is Micro-affordance: The potentiation of components of action by seen objects (Ellis and Tucker, 2000)[1]. 
 

The paper focuses on two experiments. The first is concerned with power and precision micro-affordance, and the second with wrist rotation micro-affordance.

In the first experiment the participants were told to memorise objects as they were shown them. They were then tested on the objects halfway through the experiment and at the end. During the memorisation phase, whenever they heard a tone, the participant was to either squeeze a cylindrical button with their whole hand, or pinch a small button between their index finger and thumb.

The type of grip response would be dependant on the type of tone; high or low. So there were two mappings known to the participants: high – large grip, low – small grip, and high – small grip, low – large grip. There were also two unknown mappings: high – large object, low – small object, and high – small object, low large object.

Each participant was assigned one mapping from each of the two groups and this was sustained throughout the experiment.

In the results from the experiment there was a statistically significant positive correlation between grip type and object type.

The second experiment was set up much the same as the first. The differences were that instead of large or small grips, the participant would make clockwise or anticlockwise wrist rotations dependant on tone, and the objects were categorised as ones more easily grasped with an anticlockwise or clockwise wrist rotation.

The results showed a statistically significant positive correlation between wrist rotation and object type.

The paper classifies micro-affordance (MA) as the state of an observer that gives rise to stimulus-response compatibility (SRC) between what the viewer sees and what actions they perform regardless of their intention. The theory is meant as a solution to the symbol grounding problem. (The reference to this problem in the paper is Harnad, 1990[2].)

The paper explains that SRC is demonstrated in many previous experiments, by various researchers, in forced choice reaction time tests. For example an advantage is gained when reaching for something on the left with the left hand, and similarly for the right. In fact an advantage is gained even in non-reaching tasks, where the location of the stimulus gives an advantage when it is on the same side as the response, this is known as the Simon Effect.

Previous experiments by Ellis and Tucker show that location is not the only action related feature encoded in this way.

This preparedness for action is thought to be a coordination of the what and where pathways in the brain.

The paper reports that the theoretical implications of the results of the study are:

1. MA are different from Gibsonian affordance in that they suggest the affordance is encoded in the viewer's nervous system (not the object being viewed), they only apply to grasping, and only grasping appropriate to the object.
2. SRC works because what is being responded to is unrelated to what is causing the compatibility effect. SRC theories suggest that stimulus → response options elicit particular mental codes, so the location of an object elicits a left or right handed response. MA, however, can be evoked without evoking a coherent action.
   This means that MA should interfere with SRC experiments.
   SRC effects have been modelled as ecological relations between visual properties and actions. They have also been modelled as effect codes that can be combined into whole actions.
   MA and these two approaches share the assumption that a compatibility effect arises from visual objects and possible, real-world actions that can be performed on them.
   MA diverges from the ecological approach by retaining representation of objects, and from effect codes by having a direct connection between vision and action. MA diverges from both because it states that actions are potentiated whenever an object is seen, regardless of the intention of the viewer.
3. Developmentally, MA fits in well with the popular theory of Neural Darwinism. Development of adaptive behaviours requires integration of sensory and motor processes. The paper proposes learning coordinated actions result from gradual adaption of the neuron groups involved. This leads to coupling of motor and sensory systems.
   The implication of the experiments is that MA reflect the involvement of the motor components of the global mapping, which have come to represent visual objects.
   
   

So what does this tell us about how natural object thinking is? Object thinking requires that you understand the objects your are working with in terms of the behaviours that they can perform. You need to be able to create your objects so that discovering what behaviours are available is intuitive — i.e. when others come to your API they aren't spending hours going through the documentation, they can just get on and use it.

Ellis and Tucker show that the brain is well suited to understanding and preparing for expected behaviours. When we see an object, we immediately know the actions that the object has available, and are primed to use them.

This implies that once we have a good understanding of a problem domain, we should be able to model the behaviours of the objects in the domain intuitively, and anyone else with a good understanding of the problem domain will be able to intuitively discover each object and its behaviours.

The behaviour driven aspects of object thinking are intrinsic to how the human mind works at the brain level.

The next section deals with anthropomorphism, why OT needs it and where it comes from: Object Thinking - Anthropomorphism.

[1] Micro-affordance: The potentiation of components of action by seen objects; Rob Ellis, Mike Tucker. British Journal of Psychology (2000), 91, 451-471
[2] Harnad, S. (1990). The symbol grounding problem. Physica D, 42, 335±346. (As sited in [1])

Object Thinking - Objects: a neurological basis

This follows on from my post Object Thinking is the natural way to think. Introduction

This post deals with how the brain perceives the world as objects.

A neurological perspective of how perception work, via studying perceptual disorders, is covered in chapter two of Neuropsychology: from theory to practice [1]. This is a review of that chapter.

Studying perceptual disorders tell us how we work by looking at damaged brains in people, or damaging brains in animals, and seeing how that affects what is perceived.

The chapter concentrates largely on visual perception, due to “the natural dominance of our visual sensory system”. It starts out by identifying two major pathways in the brain, the “what” pathway, which is responsible for identification of objects, and the “where” pathway, which is responsible for location position and motion. These were originally identified in monkeys in 1983 by Mishkin, Ungerleider and Macko. Milner and Goodale (1995) expanded on this model to explain that the “where” pathway is dedicated to the preparation of movement.

This demonstrates that humans understand the world as objects and actions. 

The chapter goes onto explain that these two pathways are linked, essentially the flow of data goes primary visual cortex → “what” pathway → “where” pathway → motor cortex. The system also gets feedback, via other pathways, from interactions with the environment to aid in learning. This of course means that we get better at performing actions the more we do them.

The next section of the chapter deals with sensation versus perception. It is not particularly relevant to this discussion. In short summary: sensation occurs before perception, and is not consciously recognised. In vision the sensation pathways are those that link the retina to the visual cortex. People with damage to these pathway will not notice that they don't see something, unless they are made aware of it appearing and disappearing from view.

Discussion of the hierarchy of the visual cortex follows on. This has quite a strong neurological focus, and describes a lot of the brain's structure in this area. The key point relevant here is that the brain is modular and parallel, which means that human thinking is modular and parallel, which is clearly analogous to separation of concerns. The parallelism is accomplished through pathways that allow feedback between modules. This could be thought of as message passing, although it might be a stretch to say it scales up to conscious thought.

Next the chapter discusses what certain disorders show us about visual perception. The two types of disorder covered are apperceptive agnosia – a condition that means the patient has a difficulty distinguishing between objects – and associative agnosia – in which the patient is unable to recognise objects or their functions.

Apperceptive agnosia, and its milder counter part; categorisation deficit, give strong evidence that the mind perceives the world as objects. People with these disorders cannot discern one object from another. This impedes problem solving, as the person with the condition does not know how to act on what they see. In fact, in the case of apperceptive agnosia, it can be equivalent to blindness, as those with the condition find it easier to navigate with their eyes shut.

Associative agnosia, prevents people from being able to recognise objects or their functions. This class of agnosia can affect any of the senses. The book focuses on vision.

People with associative agnosia can copy (e.g. by drawing) and match objects, but they cannot recognise. So it appears that primary perceptual processing is intact.

The current theory for what causes this agnosia is that the “what” pathway has become disconnected from the memory store for associative meaning. People with this condition can write something down, such as their name or address, but are completely unable to read it back. This is clear evidence that we use background knowledge to solve problems.

The chapter gives an example (p. 53) of a patient, with associative visual agnosia, who can only tell what a banana is after eating it, and even then only through logical deduction: “...and here I go right back to the stage where I say well if it's not a banana, we wouldn't have this fruit.”

The next section of the chapter discusses object and face recognition. The focus is on how this works at a neurological level, and the difference between face recognition and object recognition. The key point it makes is that the left hemisphere of the brain deals with parts of objects, and the right deals with objects as a whole. (Faces, are a special case, however, as they seem to be perceived as a whole, and not as parts, i.e. most of facial recognition is done in the right hemisphere.) The brain is set up to understand about composition.

The rest of the chapter focuses on describing top down (using past experience to influence perception) and bottom up (working from first principles) processing of visual information, and come to a conclusion about how the left and right hemispheres interact to give what we see meaning. Essentially they work together, the left hemisphere identifying objects and the meaning of objects, while the right analyses structural form, orientation and does holistic analysis of an object.

So, in conclusion, the chapter lays out clearly that human beings perceive the world as objects, even at a neurological level. This is our nature. Thus is makes sense when designing software to think of our problem space in terms of the objects in it. 

The next section will deal with why action is integral to how we think about the world, and can be found here: Object Thinking - Objects have actions.

[1] Neuropsychology: from theory to practice, David Andrewes (2001, Psychology Press)

Object Thinking is the natural way to think. Introduction

Preface
I don't know why I'm up so early on a Saturday, but I am. *yawn*. So I've been writing a paper reviewing other texts, to explain why Object Thinking is the natural way to think.
I am doing this because I do not want to lose an internet argument. I know. I've already lost. Both side have. That's how internet arguments work.
The argument is at Programmers, particularly my answer to the question "is OOP hard because it is not natural?" SK-Logic is zealously anti OO, and I am equally zealously pro OO.
Then the other day I was discussing what I'm writing with Pierre 303, in the Programmers' chat room, and he suggested that I make it into several 'blog articles, because then it would be easier to digest. I agree, so that's what I'm doing. I still don't know why I'm up so early, but at least I'm doing something.


Introduction

Object Thinking; it's been around for decades as a paradigm for software design, but what is it? When presented with a problem, someone using object thinking will start to decompose the problem into discrete sections that can interact with each other. You could, for example, be forced to change the tyre on your car. A simple task, certainly, but to do it you must understand the tools and relevant components of your car, and how they need to work together to achieve your goal.

It might take several attempts to achieve a fine grained enough understanding to effectively solve the problem. Your first pass at the above example might leave you with the idea to take the wheel off your car. A second thinking might make you realise that you need to lift the car off the floor to do that, and so on.

One thing that can give you a head start in solving a problem using object thinking is background knowledge. Knowing about your problem domain, what the objects in it are capable of, makes it easier to plan how to use them. Not knowing enough can cause issues, however, if assumptions are made based on incomplete knowledge.

For example: You are asked to stick a poster to the wall, without leaving holes in the wall. You are given a hamster, newspaper and some Blu Tack®, along with the poster. If you don't know what Blu Tack® is for then your understanding of the problem domain is incomplete and you could end up using the hamster to chew up newspaper into balls, and use those to stick the poster to the wall.

It is also important to note that not everything present in your problem domain will necessarily be used to solve the problem. So, in the previous example, you might not use the newspaper or hamster at all (or, of course, you might find the hamster solution better, as it reuses the newspaper, which is more ecological).

So how does this apply to software design? Software is just “algorithms and data structures”, right? Well, at the end maybe, but you've still got to design it. Software is the output of people's attempt to solve a problem. Solving a problem with object thinking is the natural way, as this series of posts hopes to demonstrate, because it uses people's natural problem solving techniques.

Object thinking is a core tenet of Object Oriented Design (OOD), a well known software design paradigm. The inventors of OOD set out to fix what they saw are the main problem with software design – software design was taught to make people think like computers, so that they could write software for computers.

 

A book that extensively covers the meaning and practical aspects of object thinking is Object Thinking by David West (2004, Microsoft Press). In it he likens the way that traditional programmers use OOD to writing lots of small COBOL programmes [1]. Objects in this sense have been turned into data structures with algorithms wrapped around them. While modularising code is better than having one large function, it only makes designing software a little easier. It still focuses the attention of the design on how a computer works and not how the problem should be solved.

So what makes reasoning about large systems easier? Focusing on the problem space and decomposing it into several smaller problems helps. But what is easier to think about? Is it easier to think how those problems translate into code? Perhaps in the short term, but you will end up solving the same problems over and over again, and your code will probably be inflexible.

Would it be better to think about software design the same way you think about solid world problems? That way you can use your innate problem solving skills to frame and express your design.

It turns out that the way people reason about real world problems is to break them down into smaller parts, using their background understanding of the problem space, take the parts of the problem space and treat them as objects that can do things and have things done to them, and find way for the objects to interact. [2]

This works well because people like to anthropomorphise objects, so that they can imagine the object doing things under its own agency, even if in the end it's a person causing the action.[3]

How can you be sure this is how you think, and is therefore the more sensible way to approach software design? Well it turns out that there is an oft ignored backwater science known as Cognitive Psychology, and scientists in this field have been studying people for decades, to find out how they work.

Future posts in this series will review certain cognitive psychology and neuropsychology texts and expand on how this applies to object thinking. The end goal is to demonstrate that object thinking is innate and therefore the best strategy for designing software.

Next post in the series: Object Thinking - Objects: a neurological basis

References
[1] Object Thinking, D. West (2004, Microsoft Press) p9
[2] Problem Solving from an Evolutionary Perspective visited 9th July 2011
[3] Object Thinking, D. West (2004, Microsoft Press) p101

Blu-Tack is a registered trademark of Bostik. I am not affiliated with Bostik.

Networking client / server example

At work I have been writing a lot of code relating to sending data over a TCP connection.

I have also seen a couple of questions, recently, on Stack Overflow asking about why networking code wasn't working. Unfortunately I didn't have time to answer them, but it did make me think that there must be a dearth of good samples of networking code online.

Allow me to make that dearth one sample fewer! (Does that make sense?)

For the full listing visit my Github repository: https://github.com/Mellen/Networking-Samples

One problem, that sparked my interest, was how to to keep the server running when a client disconnects. Because the server needs to know when a client disconnects, and not just choke and die. A client disconnecting is not an exceptional circumstance.

The first problem is to not let the server die when a client disconnects, the second is to keep the server looking for new connections, so that it can be a server.

Keep it alive!

My solution to the disconnection problem got generalised to both the client and the server classes, because it makes sense to not have the client die if the server disappears. The user might want to try to reconnect.

You'll find this code in the file NetworkSampleLibrary/NetworkStreamHandler.cs

protected void ReadFromStream(object worker, DoWorkEventArgs args)
{
    BackgroundWorker streamWorker = worker as BackgroundWorker;
    NetworkStream stream = args.Argument as NetworkStream;
    try
    {
        HandleStreamInput(stream);
    }
    catch (Exception ex)
    {
        if (ex is IOException || ex is ObjectDisposedException || ex is InvalidOperationException)
        {
            streamWorker.CancelAsync();
        }

        if (ex is IOException || ex is InvalidOperationException)
        {
            stream.Dispose();
        }

        if (StreamError != null)
        {
            StreamError(ex, stream);
        }
    }
}

You might have noticed that the method is an event handler. More on that below.

As you can see, there are three types of exception that can happen if a client disconnects from the server: IOException, ObjectDisposedException and InvalidOperationException. I found this out through trial and error.

The most common exception that gets thrown when a client disconnects is IOException. This is because the server will be trying to read from the client when it leaves.

Because of the threaded nature of the system, ObjectDisposedExceptions gets thrown when another exception gets thrown and the server still tries to read from the stream in the mean time.

I'm not entirely sure why InvalidOperationException gets thrown, and it doesn't happen a lot, but it is always when the client disconnects.

My strategy is to catch all exceptions, deal with the disconnection exceptions by disposing of the stream if necessary and cancelling the process that reads from the stream, then raising an event that contains the exception and the stream that threw it. I could create a custom exception here, but I settled on an event just in case something that wouldn't catch an exception wanted to know about it.

All are welcome

The next part of the puzzle is to make sure that more than one client can connect to your server.

This is achieved in the NetworkServer class. This can be found at NetworkServerSample / NetworkServer.cs

The pertinent parts are listed below:

public NetworkServer(int port)
{
    _listener = new TcpListener(IPAddress.Any, port);
    _listener.Start();
    _listener.BeginAcceptTcpClient(AcceptAClient, _listener);
    DataAvilable += SendDataToAll;

    StreamError += (ex, stream) =>
        {
            if (ex is IOException || ex is InvalidOperationException || ex is ObjectDisposedException)
            {
                _streams.Remove(stream);
                Console.WriteLine("lost connection {0}", ex.GetType().Name);
            }
            else
            {
                throw ex;
            }
        };
}

private void AcceptAClient(IAsyncResult asyncResult)
{
    TcpListener listener = asyncResult.AsyncState as TcpListener;

    try
    {
        TcpClient client = listener.EndAcceptTcpClient(asyncResult);

        Console.WriteLine("Got a connection from {0}.", client.Client.RemoteEndPoint);

        HandleNewStream(client.GetStream());
    }
    catch (ObjectDisposedException)
    {
        Console.WriteLine("Server has shutdown.");
    }

    if (!_disposed)
    {
        listener.BeginAcceptTcpClient(AcceptAClient, listener);
    }
}

private void HandleNewStream(NetworkStream networkStream)
{
    _streams.Add(networkStream);
    BackgroundWorker streamWorker = new BackgroundWorker();
    streamWorker.WorkerSupportsCancellation = true;
    streamWorker.DoWork += ReadFromStream;
    streamWorker.RunWorkerCompleted += (s, a) =>
                                        {
                                            if (_streams.Contains(networkStream) && !a.Cancelled)
                                            {
                                                streamWorker.RunWorkerAsync(networkStream);
                                            }
                                        };
    streamWorker.RunWorkerAsync(networkStream);
}

In the constructor, the server is set up to listen on a particular port for incoming connections and handle the connection requests asynchronously. It also creates an event handler for when the network stream throws an exception, as explained above. This makes sure that the stream is removed from the list of streams, so that it doesn't try to get disposed of when the server is disposed, and that no data gets broadcast down it.

The method that deals with the asynchronous requests for connection (AcceptAClient) has to make sure that the server hasn't been disposed of when the connection attempt is made, hence the try-catch block. Once the connection request has been handled then the method starts listening for another connection attempt. This is all it takes, essentially asynchronous recursion.

The HandleNewStream method also uses asynchronous recursion to read each message from the client. It sets up a BackgroundWorker instance that asynchronously calls the ReadFromStream method in the previous section, and when the work is complete, the worker will call the method again, so long as the stream is in the list of streams on the server and the worker has not been cancelled.

That's the meat of the server. Accepting and handling input from more than one client is achieved with a list and asynchronous recursion. Dealing with clients disconnecting is done with exception handling and events.

Really basic programming maths (part 1)

So I've been trying to mentally do hexadecimal addition. I've found that I'm not very good at it.

I'm going to slowly explain how I go about working stuff out, with the hope that it will stick in my head and get easier. (Binary is written with the most significant bit first, and all numbers are unsigned.)

First of all there is how to think about numbers in binary and hex.

Decimal numbers get split up into multiples of powers of ten.

For example 4181 can be broken down as:

• 4 x 10³
• 1 x 10²
• 8 x 10¹
• 1 x 10⁰

Remembering that all numbers raised to 0 are 1.

This applies to both binary and hexadecimal too.

So 0xFEED breaks down to:

• F(15) x 10(16)³
• E(14) x 10(16)²
• E(14) x 10(16)¹
• D(13) x 10(16)⁰

The numbers in parenthesis are the decimal representations of the hexadecimal numbers.

And 0b1101 breaks down to:

• 1(1) x 10(2)³
• 1(1) x 10(2)²
• 0(0) x 10(2)¹
• 1(1) x 10(2)⁰

The numbers in parenthesis are the decimal representations of the binary numbers.

Next up is the easy way to transition from hex to binary and back.

Since an individual hex digit takes up to a maximum of four bits, all hex numbers can be represented as collections of four bit numbers.

So 0x4432 can be broken down into 0b0100, 0b0100, 0b0011, 0b0010

This can be reversed. Say you have the 32bit number 0b10011100110100110101101011110011.

If you break it down into four bit chunks you get:

• 0b1001
• 0b1100
• 0b1101
• 0b0011
• 0b0101
• 0b1010
• 0b1111
• 0b0011

Each chunk can be represented as a hex digit:

• 0x9
• 0xC
• 0xD
• 0x3
• 0x5
• 0xA
• 0xF
• 0x3

Which gives us the number 0x9CD35AF3.

The difficult part comes in getting that number as decimal.

To do it from hex, you need to add up all the powers of sixteen that there are:

• 9 x 16⁷
• 12 x 16⁶
• 13 x 16⁵
• 3 x 16⁴
• 5 x 16³
• 10 x 16²
• 15 x 16¹
• 3 x 16⁰

Which turns out to be: 2631097075. Not easy to calculate in your head. To do it from binary would take even longer as you would need to add up all the powers of two from 31 to 0.

Thus endeth part one.

Addresses in databases

Whenever I see something like this:

• Address Line 1:
• Address Line 2:
• Address Line 3:
• City:
• Country:
• Post Code:

I want to find the database designer and smack them.

What is it about addresses that make people think that they don't need normalising?

No! Of course! The solution to storing addresses is to create a table and force all addresses to fit into five lines plus a postal code. Brilliant. Really smart.

There is one mandatory field in the address: country. That's the only one. Everyone lives in a country. I don't want to get into stupid arguments like "Wales isn't a country it's a principality", etc., when you put it in an address it's a country.

You know something people know? How many lines there are in their address. So don't force them to have 3, 4, 5, xty mumble-jillion, or however many you think is sufficient.

This is what I want to see from now on:

Address

If you do the post / zip / whatever code search thing, then great, but be sure to store the address lines in a sensible manner.

address_id	line_id	text
1	1	My House Name
1	2	My Street Name
1	3	My City Name
1	4	My Post Code
1	5	My Country

Re: quick idea

It's not trivial. There is no easy way to convert a file like jpg/png/gif into icon format. Arbitraried!

No coding Sundays

I've decided that I'm going to not code on Sundays.

I'll try and cut out Stack Overflow too, except for next Sunday because that is my 99th consecutive day. I NEED MY BADGE.

Sundays will be given over to something else. Anything else.

It's not that I've stopped loving coding. I think I love it too much. I'm going to see what else there is.

Quick idea

I think it should be trivial to make an png/jpeg/gif/bmp -> icon creator

I'm going to work to one.

Solving Sudoku

I was chatting with my manager the other day, just shooting the breeze, and we got on to how he knocked together a python script to prove to his girlfriend that programmatically solving sudoku puzzles is easy.

I disagreed for a moment and then realised I was thinking of generating sudoku puzzles, which we agreed isn't easy.

I had tried to make a sudoku helper app before, to practice MVVM and WPF, but had messed up in some calculation or other. Probably at the point where I was calculating which block a square was in. Anyway I had deleted that one, but my boss had spurred my interest in doing it again.

I'm a better programmer than I was that first time - I understand both WPF and MVVM better now, so this little solver is pretty sweet. (Unless you look at the code.)

It has all the features I need. I can fill in the known numbers, delete mistakes, and click a button to solve the unknowns (once the knowns are in place).
Sometimes you don't even need the button, since the programme eliminates possibilities as you type. One puzzle I tried was solved before I typed in all the known numbers!

So my amazing solver has two simple algorithms doing the solving:

1. Each square has an event that fires when its number of possible values reaches 1, either programmatically or by user intervention. This event is subscribed to by all the squares related to it (row, column, block), and so each related square will remove this value from their possible values list. This can cause a chain reaction of updates, solving the sudoku puzzle when enough knowns are typed in.
2. If elimination alone doesn't do the job then the second algorithm is just a button click away. I might have over thought this one:
1. Create a list of squares that have at least 2 possible values, sorted in ascending order of number of possible values
2. Take the first square and find all the squares in the same block
3. Add theses squares to a checked block list
4. Flatten the lists of potential values into one list
5. Find any unique values in that list
6. If there are any unique values then these represent solved squares so break out of the loop and update the squares related to those values.
7. If there isn't a unique value then repeat 3, 4 and 5 for the row, then the column of the current square.
8. If after that there still isn't a unique value, move onto the next square that hasn't been checked yet.

If at the end of the second algorithm a number hasn't been updated then the programme lets the user know that it needs more knowns, otherwise it starts the second algorithm again until all the squares are filled.

I know what you're thinking. You're thinking that if a user makes a mistake inputting a value, then when they delete it and input a new value the possible values list for the related squares will be wrong. Fear not! Deleting a value fires an event that does the opposite of inserting a value, so things go back to the way they were. Phew!

If you want to look at the code it's on github here: http://github.com/Mellen/SudokuSolver

The code is c#. The project is a Visual Studio 10 project, that runs on the .NET 4.0 framework. It even has a couple of unit tests. Yes, I'm that guy. I unit test toy projects.

The executable is available from github: SudokuSolver1.0.2.zip. It requires .NET version 4.0.

Anyway! This was a fun little diversion. I makes me happy that I got it right the second time.

Thinking about learning

So, my lack knowledge needs to take a bit of a beating.

If I'm to get significantly better at writing C#, I need to understand the specification.

It seems like a daunting task, but I think if I try and tackle a point at a time, writing small programmes to demostrate my understanding, I'll get a much deeper understanding of how my programmes hang together and how to write them better.

Wish me luck!

Learning to see patterns in my own behaviour

So, a week and a half ago I was looking at a question on Stack Overflow (Algorithm to calculate the number of combinations to form 100 ). I set about solving it in Haskell, and came up against a block to my success:

Given a list of numbers xs and another number n, generate a list of all the possible combinations lists of length n that contain the numbers from xs.

So, given the list [1,2] and the number 3, the function should generate this list of lists: [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]

I was pretty sure that this had been done before, but because I'm trying to get better at deducing algorithms, I'm stubborn, and I'm doing this for fun I decided to figure out the algorithm for myself.

It wasn't as easy as it seemed.

I sat down and wrote out the outputs for a few different sets of inputs, I looked at them, I looked some more. I could see a couple of patterns, namely that (length of xs)ⁿ is the length of the final output and that you could create a rectangle of answers with width length of xs and height (length of xs - 1)ⁿ. Neither of these were helpful.

I left the problem alone for a while, hoping that time would give me perspective. I was surprised how hard I was finding it to find the pattern.

Today I came back to it with a fresh brain and time to kill. I took a walk to the park, sat down, started to write out the output where the input is a list of length 3, and n as 3. As I was writing, I had the realisation that the way to solve this was to figure out the algorithm of how to write it down. The problem in my previous examples of output was that I hadn't written it in a good enough pattern. I started writing out the output for a different input a list of length 4, with n of 4 (256 items, for those keeping count). This time I was very systematic about how I wrote out the output. I got to the 44th list in the list and stopped to see if I could see it yet. I could: the last element in the individual lists was repeating every 4 items.

I stood up and, as is my wont when I am thinking, I started pacing. I must have looked a little unhinged, as I was pacing in a small circle around my bag.

It took me a few minutes, but eventually I figured out how to represent what I was seeing in my written output as an algorithm: the first time through, each item of xs is appended to an empty list, for each subsequent time through, each item in xs is appended to each list in the list of lists.

In Haskell, I came up with this function to do the work:

makeallsets :: Integral a => [a] -> a -> [[a]] makeallsets xs n = mas (addtoonelist [] xs) xs (n - 1) where mas yss _ 0 = yss mas yss xs (n + 1) = mas (addtoeachlist yss xs) xs n where addtoeachlist [] xs = [] addtoeachlist (ys:yss) xs = (addtoonelist ys xs) ++ (addtoeachlist yss xs) addtoonelist ys [] = [] addtoonelist ys (x:xs) = (x : ys) : (addtoonelist ys xs)

This allowed me to create an answer to the Stack Overflow problem. (Although there's no point posting it for 3 very good reasons: 1. it's not in the target language (which is Scala); 2. It uses the brute force approach; 3. There is already a better answer.)

Score 1 for perseverance!

P.s. if anyone would like to show me a better way, I'd be very glad to hear it.

Update to ToDoList

I have made an update to the ToDoList WPF application I wrote some time ago.

ToDoList version 1.2.0.0

Changes:

• Created a ViewModel for the To Do List object and To Do List items.
• Setup templates in the MainWindow XAML that display the ViewModel.
• Added in an edit window.
• Added in a context menu for items that allows for editing, deletion and marking as done.
• Added in edit and delete functionality.

I think the final addition will be to allow users to view done items. I'll get around to this at some point :D

Memoizing functions in c++

I was thinking about memoization, and how I'd not yet used it. I thought this was a bad thing simply because not using it might lead to me forget about it. So I'm putting together this blog post to help me solidify the concept.

A long while a go I realised a simple fact about square numbers: x² = (x-1)² + (x-1) + x, x ∈ N. I.e. for any positive integer its square is the square of the previous integer plus the previous integer plus itself. (e.g. 17*17 = 16*16 + 16 + 17)

This is something that is unlikely to be interesting or useful, except that I can use it to demonstrate memoization.

From the above formula you can write a recursive function:

int square(int n)
{
    if(1 == n)
    {
        return 1;
    }
    return (square(n - 1) + (n - 1) + n);
}

As you can see this is a very long winded way to get the square of a number, and not a function that would ever be used in reality, but it is a good candidate for memoization.

Memoization in this instance is very easy. Simply add in a static map<int, int> and update it for each number you haven't calculated yet:

int square(int n)
{
 static std::map<int, int> results;
 if(1==n)
 {
  return 1;
 }
 if(0 == results[n])
 {
  results[n] = square(n-1) + n-1 + n;
 }
 return results[n];
}

It might be that you'll want to make the results variable on the heap with some sort of smart pointer, so that it automatically deletes itself, but other than that this second version should give a performance increase over the original.

I carried out some simple timing tests with std:clock(). The programme had to calculate the squares from 1 to 32767 using the memoized and non memoized functions, in a loop:

toggle test code

#include <map>
#include <ostream>
#include <ctime>

int calcSqr(int);
int calcSqrSlow(int);

int main()
{
 clock_t start1 = std::clock();
 for(int i = 1; i <= 32767; ++i)
 {
  calcSqrSlow(i);
 }
 clock_t start2 = std::clock();
 std::cout << "Ticks taken (slow): " << start2 - start1 << std::endl;
 clock_t start3 = std::clock();
 for(int i = 1; i <= 32767; ++i)
 {
  calcSqr(i);
 }
 clock_t start4 = std::clock();
 std::cout << "Ticks taken (memo): " << start4 - start3 << std::endl;
 return 0;
}

int calcSqrSlow(int n)
{
 if(1 == n)
 {
  return 1;
 }
 
 return (calcSqrSlow(n - 1) + (n - 1) + n);
}

int calcSqr(int n)
{
 static std::map<int, int> results;
 
 if(1==n)
 {
  return 1;
 }
 
 if(0 == results[n])
 {
  results[n] = calcSqr(n-1) + n-1 + n;
 }
 
 return results[n];
}

Ticks taken for the normal function: 3120
Ticks taken for the memoized function: 78

Obviously this test was biased towards the memoized function, but I really did it to show the potential benefits of memoizing a function where the results can be reused.

SVG + Javascript drag and zoom

Recently I've been working on a project that uses SVG (Scalable Vector Graphics).

I have been using SVGWeb (http://code.google.com/p/svgweb/) so that the SVG will work in all the major browsers.

It is a fantastic library and I am so grateful to the people who work on it.

The things I found difficult were figuring out how to get zooming with the mouse wheel and dragging to work. I had it working in Firefox, using its native SVG renderer, however SVGWeb does things differently. It took me a while to work out how. I'm going to share what I found here. (Hooking the mouse wheel is actually explained on the SVGWeb mailing list: Mouse Wheel Events.)

With dragging, I knew I needed to store the old X and Y values of the position of the mouse and take the difference between them and the new mouse position. For some reason setting global variables for the old X and Y values didn't quite work - the delta was very small, approximatley 7.5 times too small.

With zooming, the SVGWeb library doesn't pick up the mouse wheel event. The way to get around this is to attach the mouse wheel event to the container tag (e.g. div) that is surrounding the object tag that is holding the SVG on the HTML page.

On to the code!

I did not come up with the Javascript - I took it from various places; mostly the SVGWeb mailing list entry above and the "photos" demo that comes with SVGWeb.

This is the main HTML and Javascript for the page that is holding the SVG:

toggle code

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
        <title>SVG Example</title>
        <meta name="svg.render.forceflash" content="true" />
        <link rel="SHORTCUT ICON" href="favicon.ico" />
    </head>
    <body onload="loaded()">
        <div id="svgContainer">
            <!--[if IE]>
            <object id="svgImage" src="example.svg" classid="image/svg+xml" width="100%" height="768px">
            <![endif]-->
            <!--[if !IE]>-->
            <object id="svgImage" data="example.svg" type="image/svg+xml" width="100%" height="768px">
            <!--<![endif]-->
            </object>
        </div>
        <script type="text/javascript" src="svg/src/svg.js" data-path="svg/src/" ></script>
        <script type="text/javascript">
            function loaded()
            {
                hookEvent("svgContainer", "mousewheel", onMouseWheel);
            }
            function hookEvent(element, eventName, callback)
            {
              if(typeof(element) == "string")
                element = document.getElementById(element);
              if(element == null)
                return;
              if(element.addEventListener)
              {
                if(eventName == 'mousewheel')
                  element.addEventListener('DOMMouseScroll', callback, false); 
                element.addEventListener(eventName, callback, false);
              }
              else if(element.attachEvent)
                element.attachEvent("on" + eventName, callback);
            }
            function cancelEvent(e)
            {
                e = e ? e : window.event;
                if(e.stopPropagation)
                    e.stopPropagation();
                if(e.preventDefault)
                    e.preventDefault();
                e.cancelBubble = true;
                e.cancel = true;
                e.returnValue = false;
                return false;
            }
            function onMouseWheel(e)
            {
                var doc = document.getElementById("svgImage").contentDocument;   
                e = e ? e : window.event;
                doc.defaultView.onMouseWheel(e);
                return cancelEvent(e);
            }
        </script>
    </body>
</html>

This is the SVG and Javascript:

toggle code

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<svg version="1.0" xmlns="http://www.w3.org/2000/svg" onload="loaded()" id="svgMain" >
    <script type="text/javascript" language="javascript">
    <![CDATA[
        var isDragging = false;
        var mouseCoords = { x: 0, y: 0 };
        var gMain = 0;
        
        function loaded()
        {
            var onloadFunc = doload;

            if (top.svgweb) 
            {
                top.svgweb.addOnLoad(onloadFunc, true, window);
            }
            else 
            {
                onloadFunc();
            }
        }
        
        function doload()
        {
            hookEvent('mover', 'mousedown', onMouseDown);
            hookEvent('mover', 'mouseup', onMouseUp);
            hookEvent('mover', 'mousemove', onMouseMove);
            hookEvent('mover', 'mouseover', onMouseOver);
            gMain = document.getElementById('gMain');
            gMain.vScale = 1.0;
            gMover = document.getElementById('mover');
            gMover.vTranslate = [50,50];
            setupTransform();
        }
        
        function onMouseDown(e)
        {
            isDragging = true;
        }
        
        function onMouseUp(e)
        {
            isDragging = false;
        }
        
        function onMouseOver(e)
        {
            mouseCoords = {x: e.clientX, y: e.clientY};
        }
        
        function onMouseMove(e)
        {
            if(isDragging == true)
            {
                var g = e.currentTarget;
                var pos = g.vTranslate;
                var xd = (e.clientX - mouseCoords.x)/gMain.vScale;
                var yd = (e.clientY - mouseCoords.y)/gMain.vScale;
                g.vTranslate = [ pos[0] + xd, pos[1] + yd ];
                g.setAttribute("transform", "translate(" + g.vTranslate[0] + "," + g.vTranslate[1] + ")");
            }
            
            mouseCoords = {x: e.clientX, y: e.clientY};
            
            return cancelEvent(e);
        }
        
        function setupTransform() 
        {
            gMain.setAttribute("transform", "scale(" + gMain.vScale + "," + gMain.vScale + ")");
        }
        
        function hookEvent(element, eventName, callback)
        {
            if(typeof(element) == "string")
                element = document.getElementById(element);
            if(element == null)
                return;
            if(eventName == 'mousewheel')
            {
                element.addEventListener('DOMMouseScroll', callback, false); 
            }
            else
            {
                element.addEventListener(eventName, callback, false);
            }
        }
        
        function cancelEvent(e)
        {
            e = e ? e : window.event;
            if(e.stopPropagation)
                e.stopPropagation();
            if(e.preventDefault)
                e.preventDefault();
            e.cancelBubble = true;
            e.cancel = true;
            e.returnValue = false;
            return false;
        }
        
        function onMouseWheel(e)
        {
            e = e ? e : window.event;
            var wheelData = e.detail ? e.detail * -1 : e.wheelDelta / 40;
            
            if((gMain.vScale > 0.1) || (wheelData > 0))
            {
                gMain.vScale += (0.02 * wheelData);
            }
            
            setupTransform();
            
            return cancelEvent(e);
        }
    ]]>
    </script>
    <g id="gMain">
        <g transform="translate(50,50)" id="mover">
            <circle stroke-width="2" stroke="black" cx="0" cy="0"  r="20" fill="red"/>
            <text font-family="verdana" text-anchor="middle" transform="translate(0,40)" fill="black" stroke-width="1" font-size="12" >Drag me!</text>
        </g>
    </g>
</svg>

There is some overlap in the Javascript presented there, this is just to keep things simple if you're copy/pasting this to test for your self.

This Javascript in the main file passes the mouse wheel event info to the SVG document:

function onMouseWheel(e)
{
   var doc = document.getElementById("svgImage").contentDocument;    
   e = e ? e : window.event;
   doc.defaultView.onMouseWheel(e);
   return cancelEvent(e);
}

The rest of the important Javascript is in the SVG document.
To get dragging to work, first define a global object to hold position information:

var mouseCoords = { x: 0, y: 0 };

When the mouse moves over the desired element, update the object:

function onMouseOver(e)
{
    mouseCoords = {x: e.clientX, y: e.clientY};
}

There also needs to be a global boolean to switch dragging on and off. I called mine isDragging. Toggle dragging when the mouse is up or down on the element.

function onMouseDown(e)
{
    isDragging = true;
}
       
function onMouseUp(e)
{
    isDragging = false;
}

When moving the mouse with dragging on, change the position of the element and update the object. Notice that the delta is being divided by the scale. This prevents the movement from becoming erratic.

function onMouseMove(e)
{
    if(isDragging == true)
    {
        var g = e.currentTarget;
        var pos = g.vTranslate;
        var xd = (e.clientX - mouseCoords.x)/gMain.vScale;
        var yd = (e.clientY - mouseCoords.y)/gMain.vScale;
        g.vTranslate = [ pos[0] + xd, pos[1] + yd ];
        g.setAttribute("transform", "translate(" + g.vTranslate[0] + "," + g.vTranslate[1] + ")");
    }
   
    mouseCoords = {x: e.clientX, y: e.clientY};
   
    return cancelEvent(e);
}

And that's how it works.

Pomodoro!

I've been feverishly subscribing to blogs recently after I realised I'm only really reading channel9.

I've got so much reading to do it's unreal. I've got through about 50 .NET posts so far and I've got 50 more to go, before I'm caught up. I've also got about 50 PHP posts to read too.

In my .NET blogs I came across this entry: You say tomato i say pomodoro at the developing for .NET blog. The post outlines a simple way to help manage your time effectively. It has inspired me to create a little timer app and a todo list app.

The timer app is really simple: it's a picture of a tomato with a button on it that minimises the app to the notification area and sets a timeout period. Once the period is reached (the length is set in the config file) then the app pops back up and plays a sound at you. I've put the code over at GitHub: code for Pomodoro timer.

The todo list app is equally simple, just a list view and list item entry controls. On close it writes to a file. The source is also at GitHub: code for To Do List.

update

I've uploaded the binaries for each, so you don't have to compile them!

To Do List executable
Pomodoro executable

dec2int and foldl

So, I'm trying to learn Haskell (as well as about functional programming) and I have a book I'm using: Programming in Haskell by Graham Hutton.

At the end of each chapter there are exercises.

Chapter 7 is about higher-order functions and one of the exercises is to create a function dec2int which is of the type dec2int :: [Int] -> Int and takes a list of decimal numbers (i.e. numbers 0 to 9); so given the input [1,2,5,7] dec2int would output 1257. The other stipulation is that the function must use foldl.

Step 1 - define dec2int recursively

My first thought in solving this problem was that I wanted to have a working dec2int function.

dec2int [] = 0 dec2int (x:xs) = x*10^(length xs) + dec2int xs

Not very efficient, obviously, as it has to call length for each call to the function, but it works and gives a general idea as to how to write the function.

Step 2 - define dec2int to the letter but not the spirit of the problem

I spent quite some time trying to understand foldl as it's described in the book. foldl's type is foldl :: (a->b->a)->a->[b]->a. A recursive definition looks like this (taken from the book)

foldl f v [] = v foldl f v (x:xs) = foldl f(f v x) xs

So the function f that's passed into foldl has to take a default value, a current value, and return a value that can be used in the function in place of the default value.

My first successful attempt at this does not seem to me to be in keeping with the spirit of the problem:

xANDpos :: [a] -> [(a,Int)] xANDpos [] = [] xANDpos (x:xs) = (x,len):xNp len xs where len = length xs xNp _ [] = [] xNp (pos + 1) (x:xs) = (x,pos):xNp pos xs dec2int :: [Int] -> Int dec2int xs = foldl dec2int' 0 (xANDpos xs) where dec2int' n (x,pow) = n + x*10^pow

f in this instance is dec2int'. xANDpos is a function that takes a list of something and returns a list of tuples of something and its position in the list, if the list were reversed. Not the best name for the function.

I don't think this is in the spirit of the problem because, while it does accomplish the goal, it adds an extra section of recursion when recursion is meant to be being handled by foldl.

Step 3 - this time with spirit

It took some time, but I finally realised that my first function wasn't the only way to get to the answer. The final version is a lot simpler than the second, and therefore more beautiful.

dec2int :: [Integer] -> Integer dec2int = foldl d2i 0 where d2i n x = n*10 + x

This is also a lot quicker - it doesn't traverse the list multiple times. As you can see, I've changed the type of the function, slightly, to allow for bigger numbers to be produced.

Here is a worked example of how the function functions:

dec2int [3,7,0,4,2] = foldl d2i 0 [3,7,0,4,2] = foldl d2i(d2i 0 3 = 0*10 + 3) [7,0,4,2] = foldl d2i(d2i 3 7 = 3*10 + 7) [0,4,2] = foldl d2i(d2i 37 0 = 37*10 + 0) [4,2] = foldl d2i(d2i 370 4 = 370*10 + 4) [2] = foldl d2i(d2i 3704 2 = 3704*10 + 2) [] = foldl d2i 37042 [] = 37042

The function can also be written as a one liner, using lambda: dec2int = foldl(\n x -> n * 10 + x) 0 however I think the other version is more readable.

The problem I encountered here was that my first assumption was incorrect, i.e. the function I came up with in step 1 was not the only way to solve the problem using recursion.

Lesson learned!

Neural Network failure

I have deleted the posts regarding the neural network class as the class didn't work - I couldn't solve the XOR problem.

Adaptive Protection

One thing that has fascinated me for the last few years has been the thought that instead of these centralised, hub like antivirus (and anti-malware, anti-spyware, etc.) systems and firewalls that work on a per computer/network basis, we could have an adaptive peer to peer system.

At this point in time I think there are three major uses for the internet. Number one is business, number two is socialising and number three is sharing data. Although I suppose three encapsulates both one and two.

The only downsides to the internet are crime and government. I'm not about to try and fix governance of the internet except to say that peer to peer trumps centralised control, and I'll hopefully convince you of that in this blog, if not this post.

There are two types of crime on the internet; mostly on the web and in email, but they also feature in other applications. The first is digital crime like trojans, spyware, etc. The second type is confidence tricks, like when on ebay someone sells you a DVD allegedly signed by Ron Jeremy and it's just a blank DVD with a squiggle on it, and there's nothing to prove it is what it is. The latter type of crime is rife in a walks of life. Digital crime, however, can only happen on computers.

So now we get to the point of my post: adaptive protection from digital crime.

Our current model for protection is one where we install some software, be it a firewall, script blocker, antivirus programme or whatever and allow it to run. Every so often the software will call home, either automatically, or because we tell it too, and it will update how it works. This is what we do and it means that we are always one step behind the attackers.

Let me throw some crazy, metaphorical idealism at you.

The internet is like fertiliser. It's not a living thing its self, it doesn't change as such. Its purpose is always to be the place where ideas can grow and evolve. The applications of the internet: bit torrent, web, ftp, usenet, gopher, finger, etc., are all lifeforms that evolve, or become endangered or extinct (to over extend the metaphor). Essentially we (users) behave like seed carriers; we increase the population of an application by spreading it around, getting others to use it, a lot like corn or carrots.

The other applications, the ones that are less than favourable for most users, are also able to flourish in this fertiliser. Like weeds, I suppose, or maybe bacteria or fungi. So like sensible farmers we deploy pesticides to kill them off, which work fine until they evolve and we have to make a better pesticide, and so on and so on.

We have one advantage over bio-technologists, though. If we start doing mad scientist type experiments to try and create programmes that can behave in a way that is adaptive and can help wipe out the undesirable programmes, we can't cause ecological disaster, like DDT or engineering resistant plants might.

My basic premise is that the best way to beat the viruses et al. is through co-operation and on the fly adaptation, via implementing a new internet application. Rather than an application that considers the internet as a place to guard against, create an internet application that wants to defend its turf.

It would have to be an application that runs in the background of your computer, and is able to understand what should be happening and what shouldn't, and how to prevent these things. Once recognition of a problem takes place and action is taken then the programme would need to propagate that information to neighbours to help them identify similar problems.

You cannot define all the rules up front. You can, however, define how to define rules, and let evolution take its course. This is one area I think that evolutionary computing will excel in. It is perfectly suited to coming up with solutions that involve iterative design over many generations.

I haven't done enough reading around operating systems to be able to implement such a system, but the idea is most intriguing. I also haven't read around in the adaptive protection literature, so I don't know how far along this research is. It is definitely something I will be getting involved in.

It seems I'm not very good at keeping on track.

I keep getting distracted by things and don't do enough work on my AI stuff.

It's not that I haven't done any work, but I've started a new project and I haven't progressed at all on the mini project. This is partly due to not having unpacked my Linux box after moving house, but also because my social life has improved after moving.

The new project isn't getting much work done on it either, but I don't want to discuss it yet, as it in the really really early stages. It's currently being developed on Windows XP, but it should be easy enough to port it to Linux when the time comes.

Merry Christmas to anyone reading this!