Author: imccoy

Well, that was fun

It appears that if

  • you’re using Android’s HttpURLConnection (2.3 is the specific source of the grievance), and you’re talking to certain web servers (ahem, in this case nginx with varnish in front of it, if the headers are to be believed).
  • you call setDoOutput(true)
  • you call setChunkedStreamingMode()

then calling getOutputStream() will cause your later call to getResponseCode() to return a 503 HTTP_UNAVAILABLE.

Isn’t that nice? My fix was to precompute the POST data so I could call setFixedLengthStreamingMode() with its length instead.

PS. You know how I said it was fun? I lied.

Do The Shuffle

My grand purely-functional web application architecture project continues, and today I’d like to talk about a dictionary webapp. It’s very simple, having only two types of inputs, one of which creates words and one of which creates definitions.

type Word = String
type Definition = String
data Input = NewWord Word | NewDefinition Word Definition

The system state is a list of words, where each word is accompanied by a list of definitions (using some unsurprising helper functions, defined at the bottom of this post):

state :: [Input] -> [(Word, [Definition])]
state inputs = map word (filter isNewWord inputs)
  where word w = (w, definitions w)
        definitions w = definitionsFor w inputs
definitionsFor w = (map definitonFrom) .
                     (filter $ (==w) . wordFrom) .
                     (filter isNewDefinition)

That is, for each word-creating input, make a word entry. Gather all of the relevant definition entries into that word entry.

And from this I want to produce an implementation that does the minimum necessary to update the state when the inputs change. For an implementation to be practical, a NewDefinition input for a word should only impact on values that are directly related to that word. From that perspective, our state function is trouble. In particular, that list of (Word, [Definition]) is trouble.

Here’s why: The simplest thing that I can think of to produce a state-updating version of the function is to use a nice simple top-down algorithm. So from a regular map function,

map f [] = []
map f (x:xs) = (f x):(map f xs)

We produce something like this (where f’ is a state-updating version of f):

map' f' [] = []
map' f' (x:xs) = (f' x):(map' f' xs)

This implementation has an unpleasant implication. For any (f x) to change, every value in the initial x:xs has to be looked at. This is bad news from a practical-implementation point of view, because it means that adding a definition for word w actually has to touch the list elements for all of the words created prior to (or after, which one it is doesn’t matter all that much) w. It is quite possible to make an implementation like this that actually works [1], if you are not worried about the inevitable failure to scale.

At the same time, this bad news is no news at all, since immutable-everything value semantics demand that changing a value within a list also changes all of the lists that contain that value. That is, if we have a list (1:(2:(3:[]))), an update to 3 can only be made by making an update to the cons cell with value 2, and that update in turn can only be made by making an update to the cons cell with value 1. Those are the rules of the game.

Changing the Game

Why do implementations of the map-reduce framework not have this problem? After all, they are all about having a huge pile of input and generating some number – possibly a similarly huge pile – of outputs. How do the inputs find their way into the relevant outputs? When we say map-reduce, we are omitting the middle step, that of shuffling. The result of the computation is not `reduce (map input)’ but rather `reduce (shuffle (map input))’. The Map stage produces a pile of (key, value) pairs, the shuffle stage arranges those by key so you have a pile of (key, [value]) pairs, then each of those (key, [value]) pairs is reduced. The shuffle stage is all about sending values off to where they will have an effect. So inspired, we can introduce a function shuffle:

shuffle :: (Ord k) -> [a] -> (a -> k) -> ([a] -> v) -> Map k v
-- the type signature kind of says it all for me, but 
-- here's an implementation anyway
shuffle is fk fv = foldr (\i m -> addAtKey i (fk i) m) Map.empty is
  where addAtKey i = Map.alter (Just . maybe [i] (i:))

That is, for some collection of things `[a]’ we have a function that says which bucket they should go in, and a function that says how to produce a value from the members of a bucket, and from all those things we produce a map of buckets to values. This idea is so simple and so obvious that it took me a month to think of it.

The point of all that is of course that we can implement shuffle’:

shuffle' (\is -> i:is) fk fv fv' = Map.alter f (fk i) v
  where f Nothing = Just $ fv [i]
        f (Just v) = Just $ fv' (\is -> i:is) v

So when we have an as-yet empty bucket (the `f Nothing’) case we just compute fv on the single element. When we have a bucket with something in it, we compute the effect of the bucket input’s change on the bucket’s output, apply that change to the bucket’s output, and just like that your uncle’s name is Robert. Probably. This is implementable too, and we can rework our dictionary app to use it quite readily:

definitions inputs = Map.mapWithKey definitionsFromInputsFor
                                    (shuffle wordFrom inputs)
  where definitionsFromInputsFor w inputs
            = map definitionFrom (definitionInputsFor w inputs)

We have lost something on the way, though. At the start of this post, we could write any function we liked to express our program’s state. Now, the set of functions we can write to do that is severely curtailed. On the other hand, they are efficiently implementable[2]. Will that severe curtailment turn out to be a problem?

It raises another question. Is `shuffle’ actually giving us much, or is the win coming from some special privileges being given to the Map data structure? Maybe representing system state as a list is just a stupid thing to do (exhibit A, the vastly simpler shuffleized implementation).

On both of these questions, further work (as the academics like to say) is required.


Oh, right. Here’s those unsurprising helpers I was talking about. They’re, like, totes boredom:

isNewWord (NewWord _) = True
isNewWord _ = False
isNewDefinition (NewDefinition _ _) = True
isNewDefinition _ = False
wordFrom (NewWord w) = w
wordFrom (NewDefinition w _) = w
definitionFrom (NewDefinition _ d) = d
definitionFrom _ = undefined

[1] Beware, the README is something of an unreliable narrator.
[2] Unverified claim.[3]
[3] STFU.

Android and Predexed Clojure

This is a continuation of Android and clojure, 2 apks and a proxy.

I finally managed to get acceptable build times by pre-dexing the clojure jar. You can see the good sauce over at github, in DexterActivity.java. It turns out there are 3 goats to sacrifice.

Firstly, the DexClassLoader takes a filesystem path, but the pre-dexed jar is a resource in the APK. The pathForApk method copies the apk out of the resource and into a cache directory that the DexClassLoader can get at.

Next, you need to make sure that Clojure uses the right class loader. The way I made this happen is by building the Clojure runtime into one apk, my clojure code into another apk, then using a single DexClassLoader for both apks. Then, tell the Clojure runtime to use that DexClassLoader. That juju starts at line 36.

Finally, you need to use reflection to load up the clojure classes. Line 43 is the responsible party.

And it all works. This drags down the build time to within reasonable limits. Alas, the startup time is still too expensive. If I tilt again at this windmill, it will be to break up the clojure jar into a bunch of smaller APKs, and write a class loader that loads those smaller APKs lazily.

Wine Theorem

We define a glass of wine W as containing sips w0, w1, w2, …, wn. For two sips wn and wm, n < m if the drinker consumed wn earlier than wm. Note that is <, strictly less than, because if n = m the same sip is being consumed twice. While not unknown, this phenomenon usually does not appear until after more than one glass, and in any case is irrelevant to this study.

We further define a function f, which denotes the flavour of the wine. The better the wine tastes, the larger the value of f. Negative values are regrettably possible.

The Wine Theorem

The Wine Theorem is simply: f(wn) > f(w0)

The proof is left as an exercise to the reader[1].

Further Conjecture

Conjecture: as n approaches infinity, f(w0) ÷ f(wn) approaches zero.

Attempts to prove this conjecture are not encouraged.

Conclusion

The last sip of the glass tastes an awful lot better than the first.

[1] the proof is notably simpler when attempted with a glass of cheap wine in hand.

Testing is pooched

What’s the point of an automated test? I humbly submit that it is to prove that your program does what it’s supposed to.

The things we want to say are incredibly simple. When some data goes in here, it comes back out over there. When it comes out over there, it’s been processed in a particular way.

And yet, in our practice we say neither of these things. We declare things about particular methods[1], and hope that the aggregate effect of the methods is correct. We declare that taking particular actions elicits a particular reaction, and then we have an infinitude of minor variations that mostly take the same paths over and over again[2].

So where is the ambition? Why do we not say what we mean? This data goes from hither to thither; and on its way, it gets processed in such-and-such a way. One might object: the data goes not merely from A to B; it comes from A, then goes to B, C, and D. To which I say, Then we can say that! And Two might object: the data gets processed in one way if it’s going to B, another way if it’s going to C; but there’s this other processing that happens to it, no matter where it’s going. To which I reply, That, too, we can say.

I wish we said these things.

[1] rspec

[2] cucumber

Stopping at the border

For the last few years I’ve been building rails apps for a living. On some level, they look like this:

A request comes in, and gets picked up by some request handler. A bunch of mutation happens in memory, then a bit of mutation in the database, then some more mutation in memory, then a response gets made. Any of those mutations can potentially interact with almost anything in any other handler. You can reduce the risk of interaction by following various disciplines, but most people don’t, and so I’ve spent too many hours debugging IO happening at surprising times, or data changing in surprising places, or things appearing with the wrong type.

An immutable-everything, pure, strongly-typed language like Haskell offers a potent guarantee. Between those three properties, we are assured: no surprises. Feeling the bloody wounds of that debugging time, I would love that no-surprises guarantee to apply during office hours. Which means I want to get that guarantee in web-land, and so I’ve spent time with Yesod, Ur/Web, Opa; enough time, I hope, to grok the philosophies thereof. I’ve spent time reading about lift and noir and django. I’ve read of the many-flowered garden of academic approaches to web programming and the whole menagerie of java frameworks for same.

Those first three go really hard on the no-surprises properties. They provide a lovely little strongly typed and pure and immutable-everything bubble for you to send a response out and twiddle the data store when a request comes in. The guarantee makes me happy, but the experience leaves me a little confused. We’ve eliminated surprising interactions between mutations within different handlers. Interactions between a handler’s mutators are limited by the language’s immutable-everything style. But all the handlers are still interacting with the database in a wild mutation frenzy, and there is a strange and lurking sense that the process is not that different to that of a rails app. A request comes in, so we change stuff in the data store, and now we have all the potential surprises of mutability. Wha?

The problem is that in choosing to make the request handler strongly typed and pure and immutable-everything, we choose to allow those guarantees to stop at the borders of the request handler. Can we model the application in such a way as to extend these boundaries right out to the border of the application?

Here’s a statement that is always true: the state of the application is a function of the inputs it has received. Historically, that state is maintained by continuously making small incremental updates, but that is in some sense an optimisation. We can define the state as a function of the inputs, and then recompute the state every time we need it. Or, we can use techniques from FRP and incremental computing to keep the state current as the inputs list changes.

If it’s a short-lived application, then you could use incremental computing to define the state function in memory on the inputs, and let that machinery keep the state up to date as you add inputs. It should be possible to implement the same machinery[1] so that it works over data that lives somewhere more permanent, too. Going even further may be an option: we can write a compiler that takes a function from inputs to state, and produces a function that tells you how to update the state for any given change to the input.

If we can do that, then we can write a pure function over the inputs, and get an efficient program. Then, the next time the question presents itself, “how the hell did that happen?”, the possibility space to be explored will be that much smaller. Prevention of bugs, rather than cure.

[1] for each value, you keep track of values that depend on it and may have to change when it does. When a value changes, you recompute the dependent values and see if they change. Recurse if necessary.

How To Program

 

  1. Have an idea: I’ll make the computer do…. that!
  2. Sit down at the keyboard. Stare blankly. Start typing. Stop typing. Walk away.
  3. Have an idea: I’ll make the computer do that…. like this!
  4. Sit down at the keyboard. Stare blankly. Start typing. Stop typing. Walk away.
  5. Have an idea: I’ll make the computer do that like this… producing this output!
  6. Sit down at the keyboard. Start typing. Stop typing. See that you’ve got the output you wanted.
  7. Have an idea: Now I’ll just generalise from that output!
  8. Repeat.