Posted on 04 October 2011
The latest clojure dojo was on a subject suggested by Robert Rees: write a program to play 20 Questions, such that the program starts with a small dataset of known celebrities, but each time it fails to guess someone, you teach it a new question. So, for example, if it had guessed Barack Obama but I was thinking of Abraham Lincoln, I could teach it to ask “Are you alive?” to distinguish between these two people later.
I decided to take the idea and extend it by writing a shared server which everyone could use. They would download the initial dataset, play a game locally, then when they were finished, upload their dataset back to the server to share with everyone else.
The code for the server is on my github. It operates via simple HTTP — there is one URL at /20-questions/latest which accepts either a GET request to pull down the data, or a PUT to push it back up.
Once again, I learned a number of lessons — last time, they were about participating in a dojo, this time, they were about organizing a dojo.
It’s upsetting that I hadn’t thought about this beforehand, but just like in every other language, user input in Clojure is painful, and difficult to get anything done with in the time constraints of a dojo. Although one or two of the dojo teams managed to wrestle with read-line enough to get it working, the rest of the teams ended up writing internal DSLs (or, less grandiosely, functions) to play the game without having to solve some accidental complexity. In hindsight, I might have thought more deeply about how to deal with user input.
A number of the teams had problems uploading to the server. Uploading is always going to be harder than downloading, because you have to generate the data in the correct format, and there’s more ways for that to go wrong than for parsing the downloaded data.
The server had actually been set up to issue useful responses to problems: if it thought a request was not well formatted, or that it didn’t resemble a tree of questions, it would return a 400 (Bad request) code. If, on the other hand, it received a valid question tree, but one which was based on out of date data, it would return a 409 (Conflict) response. An example of the latter situation is where you try to upload a tree, but somebody else adds a new celebrity and beats you to it. In order to prevent people from wiping out each other’s progress, the server would reject the request and issue a 409.
Two problems prevented this from being useful feedback. The first was that I just didn’t explain this at all; I felt that it might be too much detail to go in before people had gotten their teeth into it. But I could have at least mentioned that the error codes were meaningful and that they could have asked me for help once they had reached the point of trying to upload.
The second problem was that clj-http, the library we were using, did not show very much feedback when the error responses were received. The server had, in fact, filled in a full request body, explaining the situation in plain english; but clj-http just threw an exception which said “400” or “409” – not even a “Bad request” or “Conflict”! This made the fact that there was more information available very undiscoverable.
So all in all, as I could see these problems happening, people struggling with user input or seemingly random HTTP response codes, I was getting more and more nervous that nobody would be able to upload anything to the central server — whose data, by the way, was being projected onto a big screen for everyone to see. Thankfully, after a while, one of the teams successfully uploaded, and shortly thereafter, a number of the other teams did too. By the time we were ready for show and tell, we had built up quite a question tree:
{:no
{:no
{:no "Elizabeth I",
:question "Did you find Nemo?",
:yes "Nemo's Mum"},
:question "Are you a king?",
:yes
{:no "Richard the 3rd",
:question "Do you have blue suede shoes",
:yes "Elvis"}},
:question "Are you alive?",
:yes
{:no
{:no
{:no
{:no
{:no "Chuck Norris",
:question "Are you in the building?",
:yes "Elvis"},
:question "Who's the Daddy?",
:yes "The Daddy"},
:question "Are you a panda?",
:yes
{:no "Kung fu Panda",
:question "Are you ling ling",
:yes "Ling Ling"}},
:question "Are you a kung fu expert?",
:yes
{:no "Bruce Durling",
:question "Are you (not Bruce Durling)?",
:yes "Not Bruce Durling"}},
:question "are you a newsreader?",
:yes
{:no "Trevor McDonald",
:question "Are you the Irish newsreader (the only one)?",
:yes "Sharon Ni Bheolan"}}}I think I’ve never seen such a great example of the GIGO principle.
If you want to see some of the client code, team 4 and team 5 uploaded theirs. Also, after the dojo, Uday created a zipper-based client.
The London clojure dojo happens on the last Tuesday of every month. During the dojo, we split into groups of four or five around a single computer, and each person takes a turn at the keyboard. This ensures that even if you have zero clojure experience, you will get the opportunity to write some code at the event.
Entry to the dojo is free, but advance booking is required. Listen for announcements on the London clojurians mailing list.
Posted on 08 September 2011
Prologue: I’m going to start blogging every month’s London clojure dojo here. For more details, see epilogue.
August’s dojo, like most of them, was a bit of an experiment. The wonderful Dale Thatcher had prepared a tournament environment for all of our clojure programs to compete in.
The format was this: every ten minutes, we had to upload a working clojure program to a tournament server. The server would then play each team’s program against every other program and determine the winner each time. Points would be scored and added to a running leaderboard.
After settling in with a few rounds of rock, paper, scissors, we started the main feature: noughts and crosses! Your program is given a command line argument of the form
xx0-0----
representing a noughts and crosses grid. You have to output a number from the range 0-8 indicating your next move. One snag is that you are not told whether you are noughts or crosses, and have to determine this fact with the knowledge that noughts go first.
So for example, in the above board layout, you would instantly win if you output 6, because you are noughts, and you would have formed a line top-right-to-bottom-left.
I was on team 4 — you can grab the code and follow on from github.
Since we were to be uploading a new contender every 10 minutes, the first thing we did was write a script called gen-zip which did just that. This script bundled our app into a zip file and uploaded our entry to the tournament server in one step. Hey presto, continuous delivery! Furthermore, this script also automatically committed to git, keeping a history of every single program we uploaded to the tournament server (from the second round onwards, at least).
Our first entry for noughts and crosses was simply (println 5). It was basically the fastest thing we could write which wasn’t simply guaranteed to lose. Since deployment is cheap, we uploaded it, although it wasn’t captured in the git history. Our second entry (aed257) simply searched for the first free space and went there:
(defn choice [board] (inc (.indexOf board "-")))
The simplicity of this is astonishing:
Instead, we just use Java’s native String.indexOf() method to find the first free space and output the index corresponding to that space.
Our next contender (2db1fc1) was only slightly more complex:
(defn choice [board] (cond (= \- (nth board 4)) 5 (= \- (nth board 0)) 0 (= \- (nth board 6)) 6 (= \- (nth board 2)) 2 (= \- (nth board 8)) 8 :else (inc (.indexOf board "-"))))
Here we use the fact that clojure strings are sequences and can have nth called on them just like anything else. Once more, we don’t need to parse the string into a board; we work only with the flattened string, and we add a bunch of special cases to make a brute-force strategy of getting the middle and then each corner in turn. If all are taken, we revert to our original strategy of the first available space.
You may have noticed some oddities in the above code. What is that inc doing there before .indexOf? Why do we say (cond (= \- (nth board 4)) 5 ...) not (cond (= \- (nth board 4)) 4 ...)? This is because we made the faulty assumption that the grid indexing was 1-based, not 0-based. As a result, we were often going one square to the right of where we actually had intended to go!
We only discovered this because one member of our team was checking each tournament result to see which other teams we lost to and why. He noticed that we were making invalid moves — something we thought we had avoided by always aiming for an empty space.
Our next version (d83b9a6c) fixed this problem. It also started work on a significant new effort — parsing the board and detecting if it was possible to win outright from the current position.
By this time our work on instant-win to determine if there was an instant winner was the most significant part of our efforts. The next step was a function to determine which player we were. This was deemed a challenging enough task that we wrote a test for the function. Next we wrote a test for our instant win function, and aimed towards putting together the pieces which could make that function pass. However, all of this was a waste, because we simply didn’t have the time or phenomenal brains required to solve the problem in the half hour we had remaining.
By contrast, the only significant refinements we made to our program in these rounds were based on feedback from tournament results:
8e4e524, grabbing square 2 earlier, to stop us losing to those enemy programs who just filled the grid in order (as our example in aed257 had done).244c97c, changing from 4-2-0-6-8 to 4-2-6-0-8 to fill the 2-4-6 line one move faster.Our final version had reams of abortive attempts at sophistication, all commented out using the #_ reader macro. But the real reward had come from those old tactics, rapid feedback and gradual evolution.
Epilogue : the London clojure dojo happens on the last Tuesday of every month. During the dojo, we split into groups of four or five around a single computer, and each person takes a turn at the keyboard. This ensures that even if you have zero clojure experience, you will get the opportunity to write some code at the event.
Entry to the dojo is free, but advance booking is required. Listen for announcements on the London clojurians mailing list.
Posted on 08 May 2011
In the spirit of define-measure-improve, here is a list of open source projects I have contributed to, and the largest individual contribution to each project.
Hopefully maintaining this list will encourage me to improve my open source contributions.
"If you can not measure it, you can not improve it." -- Lord Kelvin
Posted on 14 April 2011
HTTP has four standard-usage verbs: POST, GET, PUT, and DELETE. They do not correspond to CRUD (Create, Read, Update, Delete). Forget about the distinction between create and update; it won't help you here. Both POST and PUT can be used for create and update operations in different situations. So what exactly is the difference between PUT and POST?
In a nutshell: use PUT if and only if you know both the URL where the resource will live, and the entirety of the contents of the resource. Otherwise, use POST.
POST is an incredibly general verb. Because it promises neither safety nor idempotence, and it has a relatively loosely-worded description in the RFC, you can use it for pretty much anything. In fact, you could make all of your requests POST requests because POST makes very few promises; it can behave like a GET, a PUT, or a DELETE if it wants to. It also can do some things that no other verb can do - it can create a new resource at a URL different from the URL in the HTTP request; and it can modify part of a resource without changing the whole thing (although the proposed but not widely-accepted PATCH method can do something similar).
PUT is a much more restrictive verb. It takes a complete resource and stores it at the given URL. If there was a resource there previously, it is replaced; if not, a new one is created. These properties support idempotence, which a naive create or update operation might not. I suspect this may be why PUT is defined the way it is; it's an idempotent operation which allows the client to send information to the server.
Very often, POST is used for creation because the server is responsible for assigning URLs to resources. As an example, a forum post is likely to be POSTed because the server must assign it a unique URL. If PUT were used, it would force clients to choose URLs for forum posts, and there would be no arbiter to prevent collisions when two clients chose the same URL.
Very often, PUT is used for update because the resource already has a URL which the client knows about. The client just has to supply a modified version of the resource.
Sometimes, PUT is used for creation. Generally this will be in a level 2 richardson maturity model situation, where the client knows about the structure of URLs and how to create them. For example, if I know a server has a URL scheme where users live at http://example.com/users/username, I could create myself a user account by doing a PUT to http://example.com/users/rhebus, because I already know what my desired username is, and therefore, which URL my user account will live at. [In theory, PUT could also be used for creation at level 3 richardson, where the server tells the client about URLs where resources may be created. If anyone has experienced this situation, I would love to hear about it.]
Sometimes, POST is used for update because only part of the resource is being updated. PUT requires a complete resource; but the client may not know the full contents of the resource or the client may not wish to send the full contents of the resource down the wire. (This is the use-case that PATCH would cover.) For example, a client may wish to append to a log file on the server, without caring about the existing contents of the file.
References:
Posted on 07 September 2010
So I decided to take the plunge and see what Rakudo* has to offer and what Perl 6 is like as a language. I’ve always found the best way to learn programming is through examples and by doing tasks, so when I found the perl6-examples collection, I started to go through the 99-problems one by one.
Although I started out writing “baby” perl 6, I quickly found that other people’s solutions to the problems were shorter – and clearer – than my own. It’s quickly become clear that the menagerie of perl 6 operators is more expressive than I ever imagined possible. I’ve never complained that a language lacked a particular operator, or that a language should be extended by adding more operators. Perl 6 may be changing my mind.
Today all this was made clear by a silly example in #perl6: noughts and crosses! (or tic-tac-toe, if you prefer.) The problem: given a noughts-and-crosses grid, where the players are 1,-1 and the empty squares 0, determine who, if anyone, has won. Here’s the first example that masak made:
He uses a slicel function to create cross-cutting slices of
multidimensional arrays, and uses his list of lines to go through all
possibilities, finding a winner. He also takes advantage of the [==]
reduction metaoperator: [==] results in a == b && b == c. The
reduction metaoperator can also create such useful functions as [+]
sum and [*] product, which in other languages would require a
separate function call. In Perl 5, for example, product is reduce {
$a * $b } using reduce from List::Util.
Here’s my improvement:
By flattening the board array, I avoided the need for a slicel
function; I also used the X+ cross metaoperator to shorten creating
the lines. Xop <1 2 3> gives a op 1, a op 2, a op 3, b op 1, b op
2, b op 3, c op 1, c op 2, c op 3. Then
moritz_ pointed out that 0,1,2 can be
written using the upto operator: ^3:
Further refinements are possible: 0,3,6 is ^3 »*» 3, using the
hyper operator to multiply each of 0,1,2 by 3. But by this point,
we’re just using different Perl 6 operators for the sake of it, not
because it makes the code clearer. Like code golf, this is hackers at
play; and while the product is not something necessarily useful, the
learning I’ve gained from it is invaluable.