FSM and ragel

The diagram on the right is a depiction of a state machine to parse command line arguments. I'm looking at ragel lately, because the architecture and design are genuinely compelling. The philosophy and architecture behind it are not necessarily limited to lexing input or protocols (although that is what ragel basically does). I'm looking at this from the perspective of applied research in intelligent agents knowledge base sharing and upgrading. One of the ideas I was having is whether there is a possibility to develop a common knowledge between two computer processes that is not necessarily static (like 'pre-defined'), but whether it may actually have dynamic properties such that it can reason with its internal state and knowledge base to resolve specific dead-ends and so on.

( btw, just inbetween, for an explanation how I post code on blogger without using syntax highlighter: http://kevin-berridge.blogspot.com/2007/08/posting-code-on-blogger.html ).

The above diagram was generated by specifying a sort of language for the command line arguments that the application understands. Language is to be interpreted in the broadest sense of the word. Think of it as any stream of input characters in which you can convey ideas or specifications of actions to undertake.

In the above diagram, a state is reached when the state machine can successfully pick up the next character from the stream. So, the state machine can move to a different state if it finds that the next character in the stream contains that specific symbol. It's a bit like a filter. Some states have multiple exit points (so they can go over a number of transitions), which is fine. The interesting characteristic of ragel in comparison with lexer is that you're both string matching and executing code at the same time. So when using ragel, you get the opportunity to start executing things which at a later point may not be completable because the final part of the input is missing. It takes a bit of programming to either discard the state or use it any way, it's not applicable in every context. I can imagine that if you work on transaction-based systems, you just panicked with these statements :). There, you typically wait until the full request is in, generate a response and wait for the client to actually tell you to commit and do it for real.

Another interesting part of ragel is that it doesn't use glibc or other heavier functions (possibly that much). In the above example, you'd typically use some strXXX function from glibc to find out what the user supplied. You also need to make sure your buffers are correctly set up and you don't go over them (I always use strNXXXX functions just in case I get caught out). ragel on the other hand works on your supplied buffers immediately and uses pointer arithmetic. There are two output modes: table-based, where the transition of one state to another is more of a path description and goto-based.

Goto's should probably be considered evil, but with state machines I'm starting to think that machine intelligence could greatly benefit from execution contexts that can switch very quickly from one state to another. Earlier posts made in 2007 have already rambled on about stackless python and so on. Having a stack that grows infinitely doesn't help much.

Now, in the philosophy of ragel, would there be a possibility to develop an agent language that runs in some kind of engine where the agent would continuously instruct the engine what to execute next? Maybe a thread-based context of instructions could help to make this multi-processing.

In that line of thought, consider that a state is basically an identifiable place or state of mind or state in a computer. Having an apple in your hand could be considered a state. A large problem in AI is how you make computers reason from one state to another. Generally this is done with a pre-defined knowledge base that defines all the rules before anything is executed. Such machines or robots become applicable to one thing only (that what is in the knowledge base) and not much else.

Now, a start state is known, maybe it's idle or maybe it's about being hungry or some pro-active state where the AI is trying to achieve something (possibly governed by some emotion engine?). The interaction of several state machines together would be really interesting here. The idea is to get from "start" to "goal" state. If the computer would simulate in its engine how it could get from start to goal by going over the transitions, then it may be able to find different ways of achieving its objective. If transitions have costs associated with them, then the AI could reason about the best method to achieve the objective.

Taking a transition also means using its internal resources. It isn't necessarily a trivial task. A robot could be in a start state somewhere identifiable in the current space and it may deem that it is necessary to move to another location, thus another state. The current focus is then how to get from start -> location. The transition to do that is movement and movement is concerned about finding a path from start->location, possibly using intermediate states that could be used to achieve it. If the transition finds through observation that everything is blocked, then it may decide to panic or find other ways (more costly?) to attempt.

What is described here is a design for a flexible reasoning engine depending fully on (a combination of) state machines, which execute snippets of code inbetween its reasoning processes. Combine this with a shareable language between other robots and human beings (interactive terminal?) and the computer could start asking questions...:

1. Q: "how start->goal?"
2. A: "apply movement transition"
3. ( robot downloads movement knowledgebase and code? )
   

A basic scenario involves a monkey, a box, a cage with three prescribed locations and a banana. The objective for the monkey is to grab the banana, which it can only do if the box is in the middle of the room, the monkey is standing on the box and it reaches out to grab the banana. This is a reasoning problem, as the details and specifics of actually executing those actions are of a different domain. Actually, the interesting part would be to communicate to other modules of an AI that something is an objective and leave it to sensors and other stuff to actually carry out the specific task. When those modules all agree the task has been executed, they could communicate this back to the reasoning module, which is now confirmed in the new state.

Ragel doesn't just apply actions when it's doing a transition. It can also do this when leaving states and entering them. This allows for some more flavours of interestingness. The idea is that an AI should be able to dynamically extend its knowledge base (which a couple of implementations do), ideally through communication using a simple, non-ambiguous language to communicate those knowledge gems.

In the example of the monkey above, a goal state could be to "have the banana". The computer then doesn't know how to get into that state, so it needs to understand the differences in the following:

1. how to grab a banana
   
2. how to reach out for a banana
3. how to climb on a box (and whether it is strong enough to support the monkey)
   
4. whether the monkey robot is tall enough to reach the banana without the box
5. how to move the box around the room (and that the monkey cannot be on the box to do this).
   
6. whether the box is in the middle of the room

Using these states, you can draw a state diagram of actions to be executed in a certain order. Eventually, if you leave the reasoning to the computer, it should reach a sequence of actions that is least costly to execute (the shortest way to get there) and that is what it should try.

Writing fast protocol-compliant programs quickly

I've used bison and flex for some text parsing. Another project of mine was done with ANTLR (see xssprotect), where it's basically an HTML tag filter that allows well-known tags and attributes and removes all others. Flex and Bison work together in a way, but you need to keep on your toes to understand which does what. The combination isn't suitable for all kinds of parsing and one of the reasons why programming languages are non-ambiguous by nature is so that it compiles into machine- or interpretercode exactly as intended by the programmer without unwanted side effects. Regular file parsing with flex and bison becomes more difficult once you don't have control over the format of the input file; that is, if you don't control what it should look like. This is because bison is dependent on the lexer, and the lexer should output the correct tokens such that bison can apply them properly. You could say that the lexer is more about syntax and bison is more about semantics and ordering.

So flex feeds bison and bison allows you to execute actions that should take place once things are recognized. The general tutorials all over the internet always show the same example: a calculator. Some code in flex looks like this:

%{
#include
%}
%s BRACKET
%%
[A-Za-z0-9]+            {  printf("Symbol: %s\n",yytext);  }
"("                     {  BEGIN BRACKET; }
")"             {  BEGIN INITIAL; /* Switch Back */}
[A-Za-z \t]+    {  printf("BRACKET: %s\n",yytext);  }
.|\n                    {  }
%%
int yywrap(void) { return 1;  }
int main(int arg,char *argv[])
{
  yylex();
  printf("Bye...Bye...\n");
  return 0;
}

This is input to flex. It's just printing symbols outside any context and when it encounters any brackets ( or ), it switches to different states, such that certain tokens can be disregarded, or you can start regarding them. The curly brackets are basically standard C code. Other parsers that are more advanced typically use them to return a token value (an integer), such that bison can use it. Bison would then typically attach it to a certain context.

Hence, it becomes clear why programming languages have so many magic tokens, like: { ( [ ] ) } " ' 0x * & ^ % $ # @ \ | ; : and so on. Most of these tokens are delimiters to create some kind of action. The { } tokens are probably the most interesting, as many mature languages use these to control scope of variables and instructions.

Bison scripts look like the following:

input:   /* empty */
    | input line
;
line:
      '\n'
    | exp '\n'   { printf ("\t%.10g\n", $1); }
    | error '\n' { yyerrok;                  }
;
exp:      NUM                { $$ = $1;                         }
    | VAR                { $$ = $1->value.var;              }
    | VAR '=' exp        { $$ = $3; $1->value.var = $3;     }
    | FNCT '(' exp ')'   { $$ = (*($1->value.fnctptr))($3); }
    | exp '+' exp        { $$ = $1 + $3;                    }
    | exp '-' exp        { $$ = $1 - $3;                    }
    | exp '*' exp        { $$ = $1 * $3;                    }
    | exp '/' exp        { $$ = $1 / $3;                    }
    | '-' exp  %prec NEG { $$ = -$2;                        }
    | exp '^' exp        { $$ = pow ($1, $3);               }
    | '(' exp ')'        { $$ = $2;                         }
;
/* End of grammar */
%%

You should notice how the C instructions, also in this case, permeate the general function of the processor. The processor basically has a stack of memory of tokens that were processed before, whether these are simple expressions or tokens ( a "1" is a token and an expression, a "1+1" is an expression composed of two other expressions and an operator). This calculator function above shows how bison works iteratively down your sentence and then compiles a sort of tree structure. This tree structure can be influenced to take operator precedence into account. Also, you could choose to make it contextual here.

The differences between flex and bison should become somewhat clear by these examples. Lexer doesn't know anything about the meaning of what it is processing, just that it complies with the lexing rules. An integer is a sequence of 0-9 digits without any dots or comma's. A float is a sequence of 0-9 digits with a dot or comma in the middle somewhere (followed by more digits). A char token has some alphabetic characters in them. You could easily construct your own language by prefixing or postfixing them and then making sure the rules are processed in the right order.

You could also make the parser interactive, so it becomes a command line application. Rather than verifying the exact thing was entered, you could now attempt to handle whatever was typed. So basically you could create some kind of adventure game with the above. In the adventure game, you'd probably end up recognizing verbs specifically, but maybe use a more dynamic method for dealing with nouns (objects and rooms differ from game to game). That way, the engine is reusable for entirely different contexts.

Now that you know about bison; you'll find ragel and lemon are of better use. These tools have been used to parse SQL, or geographic data (libgeom) for calculating paths and distances and so on. Without too much effort, you could script together a method for doing geometric calculations that way, such that you can invoke this from the command line.

Notice how the parser does force you to think in tree structures though. Check out this link for why state machines are quite interesting from a protocol design / implementation perspective. Often, when you parse code yourself, you find yourself knee-deep in invalid states, states that should not be reached from certain contexts, and so on. Why program that yourself? :)

State machines are also often used in Artificial Intelligence, so it makes sense in certain places to mix up these things with artificial reasoning. The problem with state machines is that it's possible to have missed some dead-end. In that case, the machine may become stuck forever and might not be able to find a sequential state to go to. Ragel though has a nice way of showing it's rules in a directed graph. That should help to make things clearer and spot those difficult places.

Linux: epoll performance and gotcha's

This is a graph of a very small test I have been running to test the performance of synchronous vs. asynchronous I/O. The previous post already showed how lighttpd is using the epoll interface. I wanted to do some testing on my own with my own implementation.
In this test, I'm using a single dual-core machine (E6850) with 4GB memory on a 1333 MHz bus with CL9. The forking server is very crude, which basically forks after accepting a connection. This could certainly be done more effectively by pooling threads and so on, but that is what the sock queue already simulates. The idea is to show the effect of creating new processes to handle new traffic and how this affects overall machine performance.

The forking server shows varying performance. At some point, the socket queue of the process within the kernel is full and the client is either waiting 3, 9 or 12 seconds to obtain a connection, probably because the kernel stalls connections (SYN flood protection?) or needs to clean up resources before it continues to accept new ones. Actually, I didn't wait for this process to finish. When you add the time required, it was running about 1 minute and did 5800 connections. So that performance is very poor. Programming wise though, things are very easy, especially using standard C available on every decent UNIX machine, since it was just an accept and a fork. (The gotcha was that you need to close the parent's file descriptor and waitpid on child's processes, otherwise it's holding on to resources).

All processes had their file descriptor limit increased to 65536 (ulimit -n 65536) and processes were run as root to prevent having to build in some setrlimit call and other complexities.

The socket queue with 8 threads is basically a round-robin fire and forget mechanism. It is implemented with glib and similarly to fork, it isn't as difficult to implement. Basically, it has one thread to continuously accept new connections as fast as it can, then it hands the socket descriptor to one of the queues in a round-robin way. The threads at the other end consume from their queue when a descriptor becomes available and process the socket until empty. Since this is all running locally, there is virtually zero latency and we know that each client connects and writes as fast as possible. Since the server doesn't create new threads or sockets, this is actually quite efficient. Problem may become when sockets actually start blocking, then you may need more threads to handle them.

The epoll() method with 8 threads is the most fancy one and actually skips a couple of other possibilities in the middle. It's strictly using asynchronous I/O, which is also the most difficult to implement. The advantage is that none of the threads ever block and are therefore always looking to do something useful. In this case, I configured eight worker threads as well. The performance is very similar to the queue one, but in different circumstances the epoll() method will certainly outperform the others. The reason is that the previous one will block waiting for something to read. Alternatives to epoll() is poll() with a self-maintained list of socket array. Eventually, those lists need maintenance and therefore they need to be processed linearly in each thread at some point. That is O(n) time, so it doesn't scale as well as epoll(), which has O(1) performance, plus the array maintenance that needs to be coded.

The simple client used in these tests is an absolute psychopath. It attempts to connect up to 125 sockets at the same time and maintain that number (that means a barrage of 125 SYN packets in a very quick succession from one thread in the beginning and as many as it can, up to 125, whenever connections get processed). This client also uses asynchronous sockets. The technique is similar to non-blocking connect() calls with select() or poll(), but in this case you feed the descriptors to epoll() to let the kernel figure everything out. The gotcha here is that the data structure used in the epoll_event structure is not a 4-attribute structure, but a union. That means that you can set only any one of the fields, but not two. For example, writing the fd field to store the socket descriptor overwrites a ptr and vice-versa.

Thus, the implementation for the client is like:

1. open socket
2. set socket to non-blocking
3. call connect(), this doesn't wait around until it completes. It almost always returns "EINPROGRESS".
   
4. store the socket + connected info in a specialized structure in epoll through the data.ptr attribute.
   
5. open another socket.

After 125 sockets are open at the same time:

1. see if any sockets have completed already, write a little bit of data and close the socket.
2. this may free up a couple of places, after which new SYN's are sent.

The quicker the server accepts new sockets, the faster it can go, especially when clients are suffering from a bit of latency. In the epoll and queued sockets structure above, I cycled through 30,000 connection requests in 4-5 seconds. That's about 6,000 processed connections per second. This is in an environment where both client and server run on the same machine. The problem that this load faces is that the machine runs out of sockets, because due to the speed, there are a lot of sockets in the "ESTABLISHED" state (that's how quick the NIC is and how relatively slow the NIC is :). Sockets in ESTABLISHED state consume file descriptors and you can only have so many open before you run out. Modern servers should be able to handle 10,000 connections at the same time however. Running this on two different computers should give twice the number of sockets available.

The idea of the above is to develop software where the system becomes network-constrained. A lot of software, due to its architecture, doesn't use all of the network's bandwidth, but it probably uses all of CPU or memory. Threads and processes require a stack space to operate, because they call functions and leave other data on the stack for reference. The 90's way of handling traffic was to add threads and processes, which increases the requirements for memory and CPU. The context switch and process management becomes a bigger bottleneck (since that's what the kernel does). The Linux kernel has a very nice scheduling system now, which is default, which also has O(1) performance. So you could have 10,000 processes hanging around quite easily, but at some point you do noticeably see performance degradation, especially once the kernel needs to traverse the process lists every x (here 1) ms. That is why having one process/thread per socket is a bad idea.

Increasing throughput on LAN's has some more considerations and options for tweaking. Most Linux distributions are pre-configured for internet use, which means that their window sizes are different from a LAN. This is because if the round trip time is high and you send a large packet, which somehow gets lost, the cost of resending that packet is high. So a smaller packet would do better. But if you only send 1 byte per packet, then you're not getting anywhere either. Linux actually seems to optimize that in the kernel now. High performance servers sometimes need a bit more local ports to deal with incoming traffic. This can be modified non-permanently in /proc/sys/net/ipv4/ip_local_port_range.

Supercharging reliable packet transfer capacity

Lighttpd is a very light, high performance web server that uses a different architecture for handling connections. It is being used for meebo and youtube, but probably with modifications. Although Apache is the best known webserver around and has been used for years as a very reliable webserver, the rise in network communications capacity is showing that the software itself is now more likely the bottleneck in communications than the hardware itself. Apache with its threaded architecture doesn't scale as well or use the hardware resources as well as lighttpd can. The reason is related to the specific use of resources on the operating system, like the number of file handles, threads, and so on. Two very important issues become copying data from socket to kernel memory and finally to user memory. This is one copy too many and people are researching how to prevent this first copy taking place, such that data arriving at the network card can be copied straight into user memory when available. The second problem is related to the overhead of thread/process context switches and the repercussions a high number of threads and processes have on overall system performance. In effect, the consequence of these systems is that the kernel spends more time figuring out which thread/process to run and housekeeping efforts become larger.

In communications where sockets are associated with threads (let's assume for the remainder of this type that threads and processes are interchangeable), the threads typically block on particular operations within the communication cycle. So, writing to a socket may succeed immediately, or it may block the sender until either the socket is disconnected or the remote end has received the data, such that the client buffer sending the data becomes free. If the thread blocks on either send or receive, the thread is put into a particular blocking state, signalling the kernel that it only needs to be woken up if some buffer becomes empty or data arrives at the socket. Having, let's say, 10,000 threads around then sounds like a lot, but in the end only a couple of those threads are actually executable on the CPU. The advantage of this approach is that programming is pretty clear and the program is easy to understand. The disadvantage is that this model is not scaleable towards the actual hardware capacity installed.

In looking at some specific problems I am facing, I also noticed that this above model doesn't scale at all for situations where clients send out notification packets. Those are characterized by clients sending a bit of data and closing the connection immediately. They can then pick up another notification to be sent, send it immediately and cycle on that. It is also possible that there are a large number of clients sending data.

For these situations, TCP state transitions look like this:

client         send ->     <-  send     server
ESTABLISHED     FIN           --        ESTABLISHED
FIN_WAIT1       --            ACK       CLOSE_WAIT
FIN_WAIT2       --            --        CLOSE_WAIT

...... server processes .......

FIN_WAIT2       --            FIN       LAST_ACK
TIME_WAIT       ACK           --        CLOSED

The "CLOSE_WAIT" state is maintained until the server has accepted the socket (which is already in CLOSE_WAIT now), reads the data, then closes the socket itself. A more serious problem arises when the number of sockets in CLOSE_WAIT equals the size of the backlog queue of the listening socket. Let's say this is 128, which is a reasonable number for Linux. The number of sockets in CLOSE_WAIT becomes 128, the server doesn't accept any more connections and it only allows more connections when the server picks up one of the pending connections by calling accept(), handles it and closes it. If the number of clients is relatively high, this server becomes a bottle-neck for any communications up-stream.

Lighttpd supports a new architecture that is available for newer kernels. Actually, it supports a couple of new constructs for handling TCP traffic, that which are given by kqueue, epoll, select, poll and so on. The ideas of these architectures is that a thread should not be created just to wait for data to come in, but the thread selects which sockets are in a state that a successful read or write can take place and the CPU will initiate those actions. The idea is that you use less threads to do the same kind of work with better use of resources, such that you become more efficient overall, such that you can handle more connections and communication overall, increasing the throughput which should easily be handled by the server.

A very good discussion on performance is here. It is also linking to a very good presentation.

Grozzr

If you want a geeky way of doing groceries, try out http://grozzr.appspot.com. It's a minimalist application to write shopping lists online on Google. Because it's hosted on AppEngine, you can return to the list later, add stuff, remove stuff, and so forth. Cool thing is that it is integrated with Android. If you have an Android phone, you can download an Android app online which syncs the online list with one of the shopping list applications you may have installed (like OI shopping list or Trolly). See the QR code below where you can download the app from:

I've written this to make this slightly easier. No pen and paper and you always have access to the shopping list. I'm trying to add as little features as possible and do the one thing really well, which is writing shopping lists. One thing I might add is the ability to send the list to an email address of another user who might have an android phone, who could then use a temporary key to access the list and sync without having to login. But nothing much beyond that.

Try it out and let me know what you think!

Tried out a new distribution: Fedora

I've used Fedora for the first time now. Like Ubuntu and Debian relationships, Fedora is a distribution that started after RedHat release 9 for home-users. RedHat sponsors Fedora heavily, but has put RedHat Enterprise Linux after the Fedora developments. So basically, the community is expected to innovate on the platform and RedHat sits around these developments, sponsoring Fedora where required and streaming those developments back into the enterprise product.

I'm now using a couple of Linux distro's actually. Some of the servers are running on CentOS, where CentOS is basically the opensource distribution of RHEL, as RedHat is required to release the software under the GPL license. So in a sense, CentOS == RHEL without the support contracts.

It's the first time I've been using SELinux as well. I can't say I'm truly happy about it, it's a bit invisible to the first-time user. I've managed to get things started ok and some nice things are coming out of Fedora, but I do think that Ubuntu support for many desktop tasks is slightly better. It's probably because of the widely visited Ubuntu forums. All-in-all, Ubuntu is slightly friendlier for using the platform, but Fedora has some great and innovative features and probably contains things I haven't even discovered yet.

From the software perspective, they seem to have more or less the same availability. RedHat systems use "yum" for package management though and Ubuntu (+Debian) use apt, that's the difference. Personally, I slightly prefer apt still. Install-wise, things are pretty easy nowadays. It all installs without a hitch.

Truth about Amsterdam

Apparently some guy called Bill O'Reilly from Fox News has painted a very untrue and wacko picture about Amsterdam. Now some people from Amsterdam set up a website to show people what it is really like. I worked right in the center of Amsterdam for the last year, my uncle and aunt lived there for their entire lives, I've studied there for five years and it's really just great. What drugs? What violence? What weapons? What crime?

Come to Amsterdam and see for yourself! I promise you'll have a great time!

Distributed Hash Tables

I've looked shortly at DHT, als called Distributed Hash Tables. DHT is not only a way to store data in some cloud of computers, it can also serve as a resilient, robust cloud of storage. It's basically a technology that has a very simple manipulation interface (get, remove, set). The differences between specific DHT's relate to geography and oriëntation of nodes, data versioning, hash generation, language of implementation and so on. If you want a clean version, look for projects like bamboo, openchord, opendht, and the likes. Other projects already put in some more functionality, like Project Voldemort.

There are some disadvantages to the use of DHT:

• It doesn't provide absolute guarantees on data consistency and integrity (but doesn't necessarily make a total mess either, check Amazon's paper on "Dynamo").
• It's not very useful for "group" queries, range queries or other kinds of data lookups.
• It doesn't natively support events or triggers very well.
• There is no authority in the network. So nodes have to cooperate between them in case certain decisions need to be made.
• Lookup of data is O(log(n)) and may take 2 or more seconds, depending on the real location, how many nodes there are and individual latencies between nodes.
  

There are clear advantages too:

• It's highly resilient to network leavers/joiners or other big changes around the network. Most implementations handle node changes very well.
• Data is automatically distributed, according to specific configuration options. The specific way how data is eventually organized depends on the chosen strategy in the design. For example, the way how nodes are organized (-ing) together is very important.
  
• Data is replicated across nodes, so it's difficult to lose it.
  
• The removal of any single node doesn't impact the network overall in any way.

Now, if you read the wikipedia page, you'll also see products that use this technology. BitTorrent is a protocol that is very effective in the distribution of file parts, but before you can start sharing a file, you need a way to find it. Finding files works by creating hash keys of them, which is basically an alternate key. By setting up a server where you can browse contents and which has an index of files that are in the network, you can find the content you're looking for and then by downloading a .torrent file, you get the hash key used to find peers in the network that can serve the content you're looking for. From that point onwards, you can communicate with the individual peers to start downloading.

Because keys allow multiple values, you can add yourself as a peer to share the file as well, so that others can negotiate with you on the file parts you may have that they don't. So, DHT in this context is used as a very effective mechanism to find peers to communicate with.

There are other uses of DHT once you start building some logic on top of this simple interface. You could create a virtual file system for example. A key with "/" can be loaded with a set of values, which are the 'subdirectories' that are valid under /. Then you just keep going until there are no more files. To get a file directly, you should be able to look for a key : "/work/myfiles/important-document", in order to get information about the location of that file.

Because projects like Hadoop have different ways for large file replication (blocks of X MB) across a huge cluster, using a DHT layer under this system could store the locations of each replicated block. Nodes themselves can manage their own files this way. This could possibly remove the need for the authoritative and centralized HDFS file directory server and make the network overall more robust and resilient (the HDFS central server is a single point of failure).

It's also possible to store files in two formats: the /x/y/z way, which is meant for finding information and the /nodeX/files way, which indicates the files located on a single machine. If each node itself manages and maintains that information, the rest of the network can react to node crashes by just looking up this information from somewhere and act on this.

The above method for storing information doesn't deviate much from Prefix Hash Trees. A complication in DHT is that you cannot access data by parts of the key (a search) because they are all hashed and unreadable, so you can only find data when you have the key in its entirety. You could create a database in this network as a kind of directory, but that introduces a single point of failure again. The schemes above make this slightly more accessible. This is also the reason why DHT's are not the right solution for every problem. It works when you access lots of data by the same primary key. Facebook uses it for showing entire user profiles, slashdot for storing and retrieving rendered comments. The only thing you need next is a method for expiring entries.

DHT's are generally stored in memory, making them really fast for lookups. Most of the times this is acceptable, but sometimes you want a bit more persistence by having individual nodes store their bits around this network. The biggest problems are faced once a node goes offline for a longer period of time and then reconnects. It is possible that the data it stores is now partly expired and you don't want those bits of information to get back on the network overall. It is also possible that certain updates have changed the information, so that it is newer, which the old keys do not contain. Amazon's Dynamo has more or less solved this by the use of "vector clocks". At some point, you need reconciliation.

Virtually, you could store everything in this network, but you need to know of course what something is as you retrieve it. If you're only looking at non-binary data, an efficient method for storing the data could be JSON. I doubt you'd need "protocol buffers", as they're designed for streaming access to large amounts of data. But possibly you could use the compiler in the project anyway to store it in the described format. That allows you at least to have the storage part covered, so that later you can create apps on top of DHT in python, C or Java.

What is so nice about DHT? The design allows you to work on top of a distributed system, if designed right of course, where you need not worry about fault tolerance within the application. Basically, once you are connected, you just write and read to your heart's content and it should work.

Android: Piggy-backing on the WebKit browser

I've been looking for ways to not store or request username/password combinations for an Android app. The application I'm developing basically needs to get some data from a Google AppEngine application that is deployed, but that app uses authenticated users for doing some queries. I am actually reluctant to request username/password for the application to login, since I don't want people to even believe the combinations can be misused.

Ideally, I want the users to log in using some login provider on the android platform, or reuse login capabilities for gmail/calendar synchronization services, but I don't think that may be possible.

The objective is to just sync some data from the web, after the user logged in with their credentials. The login is then used to perform the query with. All this without needing to have another app register precious login details in its own space, which may get lost or recovered somehow by others.

Webkit to the rescue!

WebKit on Android can be used to show HTML help pages that were bundled along with the app. Also, you can programmatically construct a browser view then use events on the webkit browser to detect when a user finished its conversation (the login process) and then recover the cookies and use that to call the actual service with. The following snippest show how this can be used in practice:

WebView webview;

private class HelloWebViewClient extends WebViewClient {
@Override
public boolean shouldOverrideUrlLoading(WebView view, String url){
view.loadUrl(url);
return true;
}
@Override
public void onPageFinished(WebView view, String url) {
super.onPageFinished(view, url);
CookieManager mgr = CookieManager.getInstance();
Log.i( "HelloAndroid", url );
Log.i( "HelloAndroid", mgr.getCookie( url ) );
}
}

@Override
public void onCreate(Bundle icicle) {
super.onCreate(icicle);
setContentView(R.layout.main);

webview = (WebView) findViewById(R.id.webview);
webview.getSettings().setJavaScriptEnabled(true);
webview.setWebViewClient(new HelloWebViewClient());
webview.loadUrl("http://yourapp.appspot.com");
}

That's a good start for temporarily using the browser to do the login. The advantage is that username/password combinations never travel through your app and the standard web mechanism is used to obtain a set of cookies to use for navigating further. The username/password remain very volatile in this entire process.

Since I am sort of running the application in a browser, there are ways for this android app to 'step out' of the browser through one of the events and call local services. As a matter of fact, there is a very nice addJavascriptInterface call, which can register a specific interface in Javascript, which can be called by downloaded HTML pages. Certainly, care must be taken security-wise not to have any other pages loaded in the same browser instance that could also call the javascript interface.

class Logger
{
public void log(String content)
{
Log.i( "HelloAndroid", url );
}
}

..... setWebViewClient(new HelloWebViewClient());
webview.addJavascriptInterface(new Logger(), "Logger");
webview.loadUrl( ........

If then your remote HTML file contains:


window.Logger.log( 'hello Android!' );


You basically have a way to let your android phone do things through the remote server app. The WebViewClient should probably contain a couple of safety controls to disallow browsing to foreign destinations.

Why is this so interesting? because you can now create a server-based GWT app and create a nice-looking browser-based interface (generated or stored server-side) and possibly avoid a good deal of code for native interfaces.

It should even be possible to finish up the browsing part if the server dictates so and continue with some intent on the handset device (and possibly return later).

My intention is to just sync some information for another app and then use that data for other purposes locally. The browser allows me to use GWT all the way, so I can use that to do the very effective GWT-RPC calls to communicate data across effectively. The GWT client code can then call the pre-meditated interfaces in the android app, and we're done!

On towards the next phases... :)

Confabulation and how it relates to SVD?

I've been reading up on this confabulation theory. It's pretty interesting work, the theory, but the practical implementation isn't as nice as the ideas behind the theory :). The use of matrices in the implementation seems to basically make this a problem of statistical analysis. The difference with Bayesian theories and other probability frameworks is that this theory assumes a "causal" relationship between one and the other, not in the way that Bayes does, but through cogency maximalization.

In the end though, and reading the word "matrices" somewhere inbetween, it all sounds a bit like singular value decomposition with a twist, rather than something entirely new. I've been looking for ways to replicate their results somehow. I came up with the following:

• Using Hadoop as an underlying platform for simple tasks (like counting words, ordering them, etc.), you take out a lot of complexity out of a program. So I'm using Hadoop to count word frequencies and the frequencies that words are seen together and at which distance.
• Hadoop provides a platform where I'm mostly using files, intermediate results stored in files and reducers to bring back some sanity. If I'd had to program that myself, I would be more concerned about stability and reliability than the core of this little research, statistical analysis (in short).
• The results are used to train a couple of SVD's á la Netflix - gradient descent. Because I've got a good 1GB file of frequencies, I don't need to process text anymore, it's all ready for learning. (text processing required 5hrs to process and get the results together. The problem in learning is that the statistical significance is only apparent after the entire lot was processed, or you'd have to heuristically make estimates).
  
• The SVD's are about 60M in size. On my machine with memory left, I could theoretically get to 33 SVD's, working together.
• The pre-processed files allow me to process the entire "frequency" file line by line, one after the other. I post-processed it to take out any words I did not recognize.
• Since I know the statistical significance of each word, how it relates to another and by what distance, I can just keep on training the features of each SVD. Not knowing that beforehand makes training slightly difficult (doh!).
  

I also thought about possible results of confabulation if it were implemented as a chat bot. Suppose that the technology were ready to produce sentences as if a chat session was going on. The Turing test is one important test, where judges need to make clear distinctions between humans and computers. Since this is a subjective test, I can't help but think that there's also an element of expectation involved. The judges know what a computer does, how it operates and what its limitations are. Now, if someone invents something really cool that breaks that barrier, the judges may temporarily be baffled and come to incorrect conclusions. But as soon as they learn about the research, they may adjust their expectations, raising the bar for the future.

In short, *can* the Turing test ever succeed? Because what if a computer OVER-performs, giving away its true nature? It seems that for a Turing test to succeed, the computer must be on the exact cognitive level of a human being, not higher or lower.

Anyway... Hadoop is really cool and useful. Having another computer in the network would half processing times. Hadoop + custom programs + post-processing scripts sound like really useful ways to pre-process huge amounts of text before you let a machine learn days on end. Since the end product are files that are in a more "edible" format, it should be a lot faster to do the research cycle.

Confabulation theory

Confabulation theory is a theory from Robert Hecht-Nielsen about the cognitive function of the brain, or in other words the working of thought. It's a theory, not an explanation. Confabulation theory basically works by processing lots of information and then from this information, find out which symbols belong together. Those symbols that are often seen together (and in cases by which distance) is information contained within the network. Confabulation can now produce new sentences by continuously generating possible phrases based on the context that is seen prior to that.



In effect, the confabulation theory uses an architecture that can produce entirely new sentences, which are plausible in the context. The interesting thing is that these sentences are also grammatically and syntactically correct. Thus, the rules of a language seem to be embedded within this network.

This does not mean that the machine 'understands' the language, or that it is conscious of the sentences it produces. I think the results should be considered the production of a thought-less brain, which only has the capacity to produce sentences without understanding what they mean. It's probably comparable to the chinese room producer, where it looks at streams of chinese symbols. At some point, the machine understands the order in which the symbols may appear and which symbols are often seen together. When asked to produce a sentence on its own, it uses this knowledge to produce a sentence.

What interested me in the theory is how this network differs from other networks that can fantasize, like the RBM. The RBM is a network that stores knowledge by looking at things and can then complete the signal it is receiving. This confabulation network is slightly different, in the sense that it can project continuations (say, a hypothesis) that are very plausible. So, if you were building a network that can produce responses to sentences, the confabulation network is likely to perform better. But if you ask a confabulation network to recognize a face, it might have good difficulty and the RBM might be better.

The RBM is a flatter network (judging the entire system) in comparison to the confabulation network. The confabulation network just competes between symbols and modules and always takes the highest value of all, but since the signals proceed from those results towards other networks, it's in a sense hierarchical.

It'd be really interesting to be able to identify specific properties of each network and then see if they can be used together. It's also possible that we're thinking about this the wrong way. The continuous processing of the confabulation network is quite different from others. We like to think from static situation to the next, perhaps the entire thing is more dynamic than that and we should focus on generating states, looping back and reprocessing the results, thus continuously adding more results to some hypothesis.

Since A.I. is also a lot about search in search spaces (think chess!), a neural network could be used to generate a hypothesis step-by-step, until it is deemed that a particular branch isn't going to produce a good result, so that it can be terminated.

Philosophy of mind and innovation

In this post I'm going to talk about a possible measure of success for creating new innovations in software. To start off, I'll put some links to put this more into context: Here's a semi-graphical timeline of the development of the GUI. Here's one of my posts made in 2007, where I'm talking about how working with computers becomes more of a conversation than it has been before. Mainframes and the likes just accepted batch jobs and you'd type the command, hit enter and that's it. In web 2.0, the computer is more or less looking over your shoulder what you type, point at and do on the screen and then if it thinks it can help you out with something, it'll pop up some helpful hint or thing next to your focal point. It is related to what we know about and how we think about our bodies and minds.

And all of this started with philosophy, thus it started with the Greek: Aristotle, Plato and Socrates. The first thoughts there however were meta-physical. What is the world made of? What does it mean to be alive? In this context, the most important thought is the separation of body and soul. The years after that, most thinking is based on the philosophy of the greeks. The middle ages turned this around a bit with the introduction of religious thought into philosophy itself. Many people tried to explain things through the use of religious ideas. And then came the others to found modern philosophy, amongst them René Descartes.

Descartes is one of the founders of modern philosophy. In his discourse about the philosophy of mind, he introduced the concept of dualism. He also considered ideas about the working of the human body. The interesting thing here... the explanation used mostly analogies and was inspired by the progress of machinery, tools and things in real life that existed at the time. In that time, the functioning of nerves and blood vessels wasn't entirely clear. For 1,500 years, people thought that "animal spirits" governed the human body. However, during the time of Descartes, certain developments were underway, like the start of hydraulics. Basic, mechanic machines could be built. Descartes knew about those and imagined the body as a kind of automaton as well. To the best of his knowledge, he tried to explain how the body worked, and used the concepts that he had available to him. After Descartes, the thinking about psychology, the mind, the brain and how it all worked together really set off. In a sense, you could also say that the way how we started thinking about things just notched downwards one level.

At this time, the thoughts about the mind didn't really go further then: "there are mechanics at work that bring sensation to a central point somewhere in the brain". This central point was imagined to be a mystic piece of the puzzle [the soul?], where thoughts occur and what can be said to be the 'I, self', when you think. So, in that time, since people observing the machines in those days clearly understood that such a machine was not alive, they didn't (perhaps not all) imagine that the machine could actually produce human thought. But, some people that did not understand its function did say that the machine can be made to do anything we ask it to do.

The function and design of the machines were still used as analogies to explain how other processes could work in the human body. Physics and mechanics research has thus certainly helped the developments in medical science to better understand the function of the heart as a pump and the fluid dynamics of blood in the vessel.

This is just a tiny grasp from everything that's happened in thinking about the mind, surely, but there's not a lot of space left on this post to continue :). It's best to read it from this excellent source I found here: Courtesty Dr. C. George Boeree.

So, philosophy started with the Greek, seeding a new science called psychology along the way and in the 20th century already at the start, we started building computers.

Why is all this "philosophy stuff" relevant?

Well, if you look at the developments in philosophical thinking and the developments in machinery, they seem to go pretty well in step. This is not because they are directly tied together, but because other developments in neuroscience, psychology, electron microscopes and imaging techniques need to be developed in order to .... start asking the right questions. And philosophy, psychology, design, artificial intelligence and sciences are the most important scientific research sources for finding those questions and hopefully the answers.

Analogous to the comparison of the mind to the technology of every age, we also see that we (re)construct our ancient tools into newer technology available. But hold on there... Shouldn't this be new tools in new technology?

Consider the desktop for example. The GUI timeline at the top is a resemblance of how we introduced the computer to the general public. The GUI works great, I don't say it should never have been developed, but there are very old concepts still present in there. Take the desktop and its applications for example:

• The trash bin is literally there and even called the same.
  
• MS Powerpoint is basically a digital slideshow projector with edit functions.
• MS Word is clearly inspired by writing on paper, thus the typewriter.
  
• The "file manager" looks like a filing cabinet in the older GUI's, but this is slowly being replaced by "explorers". The explorer still has a hierarchical view of files however.

I think one of the reasons why this was done is to make it easier for users to familiarize themselves with the environment in which they were 'operating things'. But now that everyone is accustomed to the use of a computer, more or less, there doesn't seem to be a reason to maintain this ancient set of tools in this new environment.

So, one of the problems in software innovation is related to imagination, it's certainly not about technology. A good example for starting to get rid of powerpoint is prezi. Prezi is reminiscent of the concept of mindmapping, but that is great. What is the most important difference between prezi and powerpoint?

Powerpoint is a digitalization of the slideshow projector. Mindmapping is an attempt to convey thought and their relations between them. The first is putting an old thing into a new jacket with more features. The other is understanding the mind, understanding cognition, knowing your mind and how it works, how we consume information better, what allows us to make proper distinctions, what allows us to make better judgements, communication and what allows us to easily derive the correct context and then developing a method to enable that process.

So, to finish off my post in 2007: "Conversation with the machine" with the question:

"How can/will/should user-machine conversations evolve from this point onwards?"

I think innovation should focus on following and enabling the natural flow of cognitive processes, not on the reconstruction of ancient tools of communication and processing, like mail becoming e-mail. Before you feel the urge to send out a mail to someone, there is a reason, a motivation. What if we start from there instead and just consider the computer the ultimate tool in visualization and computation? Oh yeah, and it has connectivity as well.

( footnote: There are certainly other tools like keynote+iMovie and Adobe flash that can be used to produce a prezi-like presentation. Prezi is just mentioned, because I think it is a good example of how to think "out of the box" ).

SFTP transfer scripts

I've made a set of scripts to send files from one server to another in a secure and reliable way. The idea was to use the standard UNIX/Linux tools as much as possible, because this allows admins to customize the entire process to their hearts content. A new program using libraries would certainly be more limiting.

The project is published here:

http://code.google.com/p/sftp-transfer/

It is using SFTP to transfer files from A to B and the configuration is written with Ubuntu systems in mind. The entire setup can optionally use a chrooted sftp setup. The project demonstrates full design details and a complete installation manual.

Mapping demographic data, aggregated by geographic regions

Bit of a post for the Dutch, but you may have some data that is similarly detailed and cool (AND FREE!)... Together with a colleague I've been working on mapping demographic data of Holland on Google Maps for marketing purposes. The result is here:


There is a data dump from the CBS that you should be able to find with Google called "Districts and Neighborhoods" or "Wijken en Buurten". This data contains some demographic data about a region ( municipality, district and down to neighborhood ), as counted by the CBS. As well, there is a data set called "Core figures", which translated to "kerncijfers" also supplied by the CBS.

The core figures go down to the postal code level, which does two things:

• Finer grained information than you already have (which is not very useful for marketing purposes)
• Establish a correlation between postal code and the neighborhood it is in, thus allowing you to map groups of people to neighborhood level, which is probably a good aggregation level for marketing.

The district- and neighborhood data is delivered in the form of ESRI shape files. This allows you to convert the data into Well Known Binary format (WKB) using the shp2pgsql utility. This builds a table from the data in the SHP file and outputs this into sql into a file. Then you can simply < href="http://code.google.com/eclipse/docs/getting_started.html">Google plugin) + Hibernate. To be able to query the postgis database, you need the vivid solutions extensions.

Then I use a query to get the polygons out that I need through the postgis query API:

String wktFilter = getFilter( bounds );
WKTReader fromText = new WKTReader();
Geometry filter = null;
try{
filter = fromText.read(wktFilter.toString());
filter.setSRID( -1 );
} catch(ParseException e){
throw new RuntimeException("Not a WKT String:" + wktFilter);
}

Session s = HibernateUtil.currentSession();

Criteria testCriteria = s.createCriteria(Buurt.class);
testCriteria.add(SpatialRestrictions.intersects("theGeom",filter));
List buurten = testCriteria.list();

As such, I get the neighborhoods or other regions back that I want, based on my Google maps viewport :). That's already an important step, but doesn't finish there. Since the data in the Wijken en Buurten is RijksDriehoeksmeting (RD), it needs to be converted to the Datum that Google Maps uses. They're using WGS-84, a datum, which is basically a geoïd generally used for (probably) older GPS's. I'm using this code for now to convert between the two:

public static double[] rdtowgs( double X, double Y ) {
double dX = (X - 155000) * Math.pow( 10 , -5 );
double dY = (Y - 463000) * Math.pow( 10 , -5 );
double SomN = (3235.65389 * dY) + (-32.58297d * Math.pow( dX, 2)) + (-0.2475d * Math.pow( dY, 2)) + (-0.84978d * Math.pow( dX, 2) * dY) + (-0.0655d * Math.pow( dY, 3)) + (-0.01709d * Math.pow( dX, 2) * Math.pow( dY, 2)) + (-0.00738d * dX) + (0.0053d * Math.pow( dX, 4)) + (-0.00039d * Math.pow( dX, 2) * Math.pow( dY, 3)) + (0.00033d * Math.pow( dX, 4) * dY) + (-0.00012d * dX * dY);
double SomE = (5260.52916 * dX) + (105.94684d * dX * dY) + (2.45656d * dX * Math.pow( dY, 2)) + (-0.81885d * Math.pow( dX, 3)) + (0.05594d * dX * Math.pow( dY, 3)) + (-0.05607d * Math.pow( dX, 3) * dY) + (0.01199d * dY) + (-0.00256d * Math.pow( dX, 3) * Math.pow( dY, 2)) + (0.00128d * dX * Math.pow( dY, 4)) + (0.00022d * Math.pow( dY, 2)) + (-0.00022d * Math.pow( dX, 2)) + (0.00026d * Math.pow( dX, 5 ));
double ret[] = new double[ 2 ];
ret[ 0 ] = 52.15517d + (SomN / 3600);
ret[ 1 ] = 5.387206d + (SomE / 3600);
return ret;
}
public static double[] wgstord( double Latitude, double Longitude ) {
double dF = 0.36d * (Latitude - 52.15517440d);
double dL = 0.36d * (Longitude - 5.38720621d);

double SomX= (190094.945d * dL) + (-11832.228d * dF * dL) + (-144.221d * Math.pow( dF, 2 ) * dL) + (-32.391d * Math.pow( dL, 3) ) + (-0.705d * dF) + (-2.340d * Math.pow( dF, 3 ) * dL) + (-0.608d * dF * Math.pow( dL, 3 )) + (-0.008d * Math.pow( dL, 2 ) ) + (0.148d * Math.pow( dF, 2 ) * Math.pow( dL, 3 ) );
double SomY = (309056.544d * dF) + (3638.893d * Math.pow( dL, 2 )) + (73.077d * Math.pow( dF, 2 ) ) + (-157.984d * dF * Math.pow( dL, 2 )) + (59.788d * Math.pow( dF, 3 ) ) + (0.433d * dL) + (-6.439d * Math.pow( dF, 2 ) * Math.pow( dL, 2 )) + (-0.032d * dF * dL) + (0.092d * Math.pow( dL, 4 )) + (-0.054d * dF * Math.pow( dL, 4 ) );
double ret[] = new double[ 2 ];
ret[ 0 ] = 155000 + SomX;
ret[ 1 ] = 463000 + SomY;
return ret;
}

So there goes that! Any data coming back from the UI needs to be converted into RD first (the bounds), before querying the data on the viewport.

We're still working on refining things, like encoded polygons and possibly some caching, but in compiled form the app is a lot quicker than in the GWT shell. At the moment we're simply forwarding the individual points, but that's not as efficient and probably not as precise. That shouldn't take too long to get done however. Well, the rest of the application is just using the Google Map Library and putting that little map on the screen. That means using the proper events, hooks and scriptlets, to use the old MS word inbetween.

The figures are from 2004 and have been slightly updated for 2006, but probably not too much. The real figures about inhabitants are from 2009 and are based on the GBA, but some effort has been made to change things where problems could ensue regarding privacy.

What's the use? Well, together with the postal code, which is often requested, or with the customer's IP through geo targeting, you can start data mining. Marketers can quite easily develop certain profiles of what they're selling. By the IP the region can be quickly discovered, which may then give clues about preferences if the person is not known otherwise by login for example (any preferences or login that you have is far more useful than this silly method of customer targeting).

Based on the region/IP/postal code, you can find out what kind of products are more likely to suit the visitor. Thus, it provides a way to adjust the web content to the person that's visiting. Any other smaller clues like the first three clicks could theoretically tell you the rest of what the person is trying to do, or why your site is visited.

Some other sites like funda.nl use similar databases, although I believe they've probably paid around 7,000 EUR for a postal database which is slightly more precise. The CBS borders are those borders established by the government.

This little thing that you see on the page is interactive, only loads what it needs based on the viewport bounds and was hacked together in 16 hours.

Can computers become conscious?

This is a post to contemplate about a paper I wrote, available here. When discussing the possibility whether machines can become conscious, reference is made towards the necessity to localize memory, cognition and all these other factors. In short, to have a discrete description of the system we call the Brain. Should we not understand it in full, then all hope is lost.

I'm taking a different view on things. "Emergence" for example shows that many, many small actions that are discrete in nature and often very simple, interact together to eventually become a massively complex system that no single, descriptive, general rule can describe. It is easy to describe the simple behaviour from a single agent, but it's impossible to understand the actions and consequences of the system as a whole. I reckon that we may not need to understand this entire system, but can start from the bottom by replicating certain behaviours and look at certain clusters in the detail that is still fathomable. Then attempt to replicate those clusters and move upwards in the chain.

Oh well, to prevent a rant on the same, on to the whitepaper then:

This whitepaper draws a comparison between Restricted Boltzmann Machines and human consciousness using a quantitative analysis of the capacity for the integration of information. The probability that computers can become somewhat conscious of their inputs is discussed. Consciousness of computers implies the capacity to interpret data, understand it, manipulate it and possibly to produce new data based on previous examples.

The same neurons activated by observation are also activated when dreaming or imagining. Restricted Boltzmann Machines work in a similar way; [....] This makes it plausible to construct computers that have some kind of imagination, [....] the type of consciousness isn't necessarily equal to our own [...]

Happy reading!

Pro log

No, I'm not in favor of forest logging. Prolog is a declarative language, part of the fifth generation of programming languages. I'm following the final course for this academic year, for which 2 assignments need to be created. The first assignment was a game basically with heuristics for intelligence. The other assignment is an artificial reasoning thing, where it needs to reason about the types of relations between countries. The questions and facts are written in natural language, then stored in alternative format in a more workable representation for the computer. It can be stored to and re-read from disk. It can also derive relations between two regions that have no direct relation declared, but because X has a relation with Y and Y has a relation with Z, the program can derive the possible relations (a set) between X and Z. It's coming along quite nicely at the moment, reasoning is pretty much working. There are some types of questions that are not entirely answered yet however, but it should be possible to complete them pretty quickly.

Both assignments had very interesting elements in them, whilst at the same time generating quite a bit of frustration. Prolog is a language where you're not necessarily directly in control of memory and so on. When programming a couple of years in procedural languages (most are: C/Java/PHP/C++/Python/Perl). Well, about Java and C++, opinions are divided. They don't necessarily call it procedural, since in smart cases it's about objects reacting to events. In my view though, a C++ class can be considered a whipped up C struct with a virtual table of function pointers (except that the compiler lacks other capabilities and the STL and so on).

Cool thing about prolog are the recursive abilities that usually accompany list manipulation. The interpreter does the backtracking basically, so you just tell the environment what you want to achieve. That's why it's declarative.

The main goal of prolog is: "achieve truth". Never forget that when programming in prolog. The only thing that the interpreter is ever trying to do is find paths and instantiations that, through the declared end-goal, achieve a "true" condition. Whenever a false condition occurs, the interpreter starts backtracking and will start to search for different combinations of instantiations and paths, basically other candidates.

The thing that is not very easy for beginners in prolog is branching. If you're used to the programming of 'if-trees', those if X then Y kind of structures, then prolog doesn't give you lots of tools to handle these. The good thing is that you start to think about many problems as a very generic problem, thus your approach to solving it also becomes very generic. The bad thing is that when you really need it, the amount of code may start to rise a bit.

Well, luckily the language allows modules and there are quite some internal predicates available for making programming easier, but it isn't yet as easy (for me) as programming Java or anything else.

Part of that, I think, is related to finding the correct approaches to doing things in a certain context, also called patterns. For prolog, the practice of programming prolog isn't very well documented or discussed, where the techniques that prolog allows has a lot of examples. The main examples are "knight's tour" and "sudoku".

Scheduling optimization is a topic that is more and more important for larger companies as well, or finding "a" best solution to a set of constraints and a configuration of entities. Think of DHL and timing of getting deliveries in time, think optimization of a pick-up route in logistics (travelling salesman?), think optimizing the order in which tasks need to be executed (and by whom?) across a set of resources, think developing the order in which ships may travel down a channel to take berth, having an anchorage at the outside.

These problems should not be under-estimated. With 3-4 or less constraints, procedural languages probably allow you to find a good solution within milliseconds. But when constraints are > 5 and it is possible that these increase, the procedural language solution becomes too complex, testing the solution is too complex and time-consuming and the confidence of the developers that the solution is *right* starts to decrease.

So, prolog can be pretty cool. It's pretty much crap for web development or general systems development, but once you get into that difficult problem with >4 constraints, have a look at it and see what it does, it's pretty powerful.

The wedding was yesterday, it was absolutely amazing. The people that were present were all very special to the couple and we had a great time to get to know one another. One of the ideas of the couple was to mark the poolside with a set of decadent towels with a W on it, for the last name of the family. Here's a great shot from the pool side.

So, the wedding took place on the roof of the middle building, overlooking the ocean. It was a well-timed, proper ceremony.


After the ceremony, of course there is a reception. And in Cancun, you'd typically do that on the beach at sunset.

And then the professional photographer was making shots of the couple.

The day ended in a dinner and dance more at the center of this resort.

Chichén Itzá

Yesterday we had the opportunity to see Chichen Itza. From the coast of Mexico in the Cancun resort zone, it takes about 2.5 hrs driving by car to get there. The road is very reasonable and easy to drive. Almost no traffic whatsoever. The scenery though is a bit boring, just trees, more trees and then some more. It's cutting straight through the jungle, if you could call it that. This is one of the trees that you see frequently with red blossoms / flowers:

There's a great ballcourt on this site as well. Ths is the largest in ancient mesoamerica:


And of course the most famous and visible monuments of them all, the temple of the feathered serpent:


I think it was really worth the drive over there, but since it's in the middle of the jungle, you need to bring lots of water and be able to walk a few meters in the heat and enormous humidity. Sweat keeps pouring down your forehead in general. Getting closer to the more remote areas like the market, things become a bit quieter what tourists and merchants is concerned. Sitting down in that area listening to the birds is a bit of a spiritual experience.

The other thing is getting back to the coast :). There are two roads that both have the same number 180 and it's not always clear which is which. The old 180 road goes through all little towns and takes you into the center of Cancun. I don't think you want to go there. When you exit the site, don't take the 180 road directly to Cancun, but go exactly the way you came through that little village, then take the road from there. You'll be saving yourself 2-3 hours of travel :).

So, yesterday after we got back late, we sat down for dinner and then joined into a large mojito party with the entire family, with dancing, music and talking. Great fun! Today I don't notice any of the drinking of yesterday and am just about to head off to the beach for some relaxation and possibly some more pictures.

Sunburn, easy day, dinner

Yesterday was a very beautiful, great day. It started with some easy time at the beach, then a lunch on the beach where they were serving barbeque, paella, etc. in an area with wooden benches and some protection from the sun. Then some time at the pool and near a caribbean restaurant. In the evening, the entire group went to a restaurant on this resort, which offered new-style mexican food. It means about 10 plates of little bites and tastes, where the plates change somewhat rapidly. This was great, it gave us an opportunity to meet some other people.

So, Heidi and Jorge invited family and friends from various parts of the US and from Brazil, Holland and the UK. I may have forgotten one there. Dinner was finished by going to the lounge bar, where some extravagant, really weird magic act was taking place. Today, we're going to Chichen Itza to see the temple and will be back in time for dinner and wedding rehearsals.

Arrival at Cancun

Well, we've arrived in Cancun, after an easy flight from MC to this place. We've had to wait just a little bit, but it's worth it if this is the place you're going:

King size bed, 16:9 TV, and a jacuzzi in the back there with a door that opens up to the swimming pool area right on the ground floor. Very, very nice all...

This whole trip is because we've been invited to a wedding party over here in Cancun. Jorge and Heidi are getting married in a couple of days and the entire party is slowly gathering to full strength, just under 40 people n total as I've heard today. The wedding itself will take place on the roof of the building, 5th floor. The roof has a glass railing, so standing there, the sea breeze goes through your hair and the sea greets you wave after wave with water that's probably been all over this world already. Just a couple of days away!

So, what's the beach like in Cancun? It's got what most beaches have... SAND! but of course, there are nice touches. Some thing I haven't seen are these types of chairs and complete setups:

These are really good things. It's a kind of mattress under a reed roof kind of thing with two chairs and a small table in the middle. There's about 15 of these or so around this area. Because of the swine flu, a lot of cancellations were made, so you're sure of a spot there every day. Oh, and of course, what's the view like on the other side? :)

Great huh? Water must be about 27 degrees, there are people walking around the entire time to serve food and drinks... And the room is just a stone-throw away if you prefer to get back to some airconditioning and cool off.

Tomorrow is probably jus going to be a lazy day, not sure if there will be another post then. There might just be a chance for us to see Chichen Itza some time this week, but that remains to be seen.