August 07, 2011
Just clearing out a few links.
Got Medieval: '”[The] image is taken from the British Library’s inexhaustibly weird MS Royal 10 E IV, a manuscript illuminated – as near as I can tell – by a homicidal nutjob.” In a context where cats wield longbows and mice use catapults, this is high praise indeed.
Doctor Who geek persuades his wife to watch the entire run of the show with him, chronicles her bafflement, boredom, bon mots and occasional bouts of enthusiasm, skirts divorce (via Sarah Proud and Tall). Notable if only for introducing me to the term ‘ming-mong.’
No doubt this will earn me another chastisement from Dr Clements, but I can’t pass by this – admittedly very speculative – claim that cosmologists have found possible evidence for the ‘bubble universes’ theory, in which universes are being created all the time but never overlap because the space between them inflates faster than the universes grow. Yes, I know, ‘not statistically significant,’ and ‘wait for Planck,’ but this would be so awesome.
July 21, 2011
You could be right about the fail
Huh. If I start a sentence “If they sail…,” Word asks me to ‘correct’ sail to fail. Doesn’t happen with any other pronoun. Apparently groups only get to go sailing if they invite you or me.
July 17, 2011
Browser whose usability does not suck more with each release. Can offer part exchange on an arthritic cat.
July 13, 2011
Keeping up with the parking meters
In the annals of bad install screens, the latest Java update deserves a special mention.
The message appears to be, “Parking meters and public transportation passes run Java. You should too!” Apparently Oracle doesn’t understand that the software that runs on parking meters is completely irrelevant to whether Java is any use to me on my PC. It’s not as if I need my PC to double as a parking meter, or that there are applications built for parking meters that I’d like to run. And it’s not like having Java on my PC will equip me with skills that will save my bacon next time I need to use a parking meter.
Of the ugly design, the “I found this great 1000 Free and Shareware Fonts CD from 1994” text quality and the fact that this sales pitch appears after I have already agreed to install the product, it is not necessary to speak. The parking meters have it.
July 02, 2011
Recursive parsers in FParsec
Probably world + dog knows this already, but it didn’t jump out at me in the FParsec documentation or in Google, so I thought I’d write it down anyway.
Many languages contain recursive structures. A list in Scheme or Lisp can contain sub-lists; a JSON object can contain sub-objects.
In FParsec, a parser for a linguistic structure is represented by a variable of parser type. Here’s a simple example:
let number = many1 digit |>> Number
(FParsec does include built-in parsers for common number types – I just wanted a simple example. And the Number constructor, like List in the next fragment, is just a constructor for a hypothetical AST node.)
Now consider a parser for a Scheme list of numbers – that is, a list of numbers enclosed in brackets and separated by spaces. This is a bit more complicated:
let sepOrEnd = (spaces1 <|> (spaces >>. followedByString ")")) let listElement = parseExpr .>> sepOrEnd let series = spaces >>. many listElement |>> List let list = between (pchar '(') (pchar ')') series
(I am sure there are more elegant ways to do this, but
I don’t want to get hung up on that right now I’m trying to avoid line breaks.)
And we’ll say that an expression can be either a number or a list:
let expr = choice [ number; list ]
In reality, of course, a list should be able to contain any kind of expression. So we need to redefine listElement as follows:
let listElement = expr .>> sepOrEnd
But now disaster strikes. F# refuses to compile listElement, complaining that expr isn’t defined. And there’s no way to move things around to avoid this. expr depends on list, which depends on series, which depends on listElement, which depends on expr.
You might think we could get out of this with a let rec, making the relevant parsers mutually recursive, but let rec only works for recursive functions. FParsec parsers are values. Think of it as if you were trying to define four C# member or local variables. C# is happy to let you define four methods in terms of each other, but not for you initialise to initialise four variables in terms of each other.
To get around this, FParsec provides you with a way to effectively forward declare a parser. If I could ‘declare’ the expr parser before the listElement parser, so that listElement knew about it, but defer the implementation until after the list parser, then that would break the mutual dependency. F# doesn’t have the notion of forward declaration, but FParsec simulates it using a function.
To forward declare a parser, call the createParserForwardedToRef function. This function returns a pair. The first element of the pair is a parser you can use without having defined it. It’s the forward declaration, if you like. The second element of the pair is a reference cell you can later overwrite with the implementation of the parser. FParsec takes care of hooking up the ‘forward declaration’ parser to the eventual implementation.
This sounds more confusing than it actually is, so let’s see it in action.
let expr, exprImpl = createParserForwardedToRef()
Now expr is a parser which is hooked up to exprImpl, and exprImpl is a reference which we can overwrite later. Because expr is a proper honest-to-goodness variable as far as F# is concerned, and is now defined before listElement, the compiler is now happy for us to use it in listElement:
let listElement = expr .>> sepOrEnd
Of course, now we can no longer write let expr = … when we want to implement expr parser, because expr is already declared. And this is where exprImpl comes in. Because this is a reference, we can overwrite its contents with the parser we actually need:
do exprImpl := choice [ number ; list ]
Note the use of do and := instead of let and =. We are not rebinding exprImpl – it’s not mutable so F# wouldn’t allow that – but because it’s a reference cell, we can overwrite its contents.
Because of the way FParsec set up the expr ‘forward declaration’ – in reality, because of the implementation FParsec generated for the expr parser – all calls to expr actually end up going to exprImpl. As a result, when exprImpl invokes expr (indirectly through listElement), it ends up invoking itself. And we have a recursive parser, just as we needed.
let expr, exprImpl = createParserForwardedToRef() let number = many1 digit |>> Number let sepOrEnd = (spaces1 <|> (spaces >>. followedByString ")")) let listElement = expr .>> sepOrEnd let series = spaces >>. many listElement |>> List let list = between (pchar '(') (pchar ')') series do exprImpl := choice [ number; list ]
June 29, 2011
It has been one of those days
So to cheer myself up here is a picture of a cat ‘helping’ to install LightSpeed 4.
June 26, 2011
Sunday cats in air guitar competitions blogging
Silver medal in the ‘being a rock god while lying under a desk and stopping me getting on with my work’ category.
June 21, 2011
By way of apology to everybody who thought Partial Function Application was an experimental German rock band of the 1970s.
They don’t normally look this purposeful.
June 20, 2011
Partial function application in F#: index
This post just provides links to the various bits of the ‘partial function application’ series.
- Part 1 describes the syntax and meaning of partially applying a function.
- Part 2 shows how partial application results in code that is simpler and more readable than lambda expressions.
- Part 3 looks at another use case for partial application, precomputing partial results.
- Part 4 discusses the underlying concepts.
- Part 5 examines how the partial application idiom affects the design of your own functions.
Partial function application in F#, part 5: design considerations
I showed earlier in this series how important and idiomatic partial function application is in F#. Although you can always replace a partial application by a lambda, partial application is much more concise and readable.
So when you design a function in F#, it’s worth bearing in mind how it might be partially applied. I’ve ducked this issue throughout this series by using a very simple example which doesn’t really have any design choices about it, but real functions don’t have that luxury.
A simple predicate
Suppose we want to create a divisibleby function, which takes two arguments and returns whether one is divisible by the other. There are two ways we could write this function:
let divisibleby value factor = (value % factor = 0)
let divisibleby factor value = (value % factor = 0)
Obviously, these are the same except for whether we put the value we’re testing first or last in the argument list. Which should we prefer? You might instinctively go for the first one because the arguments appear in the same order as they do in the English sentence ‘value is divisible by factor.’ But take a look at what happens when you try to use that as a predicate in a filter expression.
let evens = List.filter (fun x –> divisibleby x 2) ints
Lambdarrific! By contrast, here’s how the predicate looks if we write divisibleby the other way around, with the factor first.
let evens = List.filter (divisibleby 2) ints
We can use partial application, and all the lambda noise goes away. The resulting expression is shorter, less noisy and more readable. Clearly if we want to use our divisibleby function in predicates, we should be writing it the second way, testee last.
A simple mapping
The List.map (LINQ Select) function provides another example. Suppose we want to subtract 1 from every member of a list:
List.map (subtract 1) ints
How should we design the subtract function? We want subtract 1 to result in subtracting 1 from its argument:
(subtract 1) y = y – 1
So, counterintuitively, we should design subtract to take its subtrahend first and its minuend second:
let subtract x y = y – x
Of course, this could be very confusing to use in a non-partial form because it reverses the order of the subtraction operator! A user writing subtract 5 2 would probably expect a result of 3, not -3. So this is a case where it might be better to stick to using a lambda in the List.map call.
The pipeline operator
F#’s pipeline operator, |>, is a nice way to make long chains of operations more readable. The pipeline operator just flips function application around:
let (|>) x f = f x
Partial application means we can use the pipeline operator even with multi-argument functions:
23 |> subtract 17;;
val it : int = 6
A more realistic example of this performs a LINQ-like query by composing List functions in a pipeline:
ints |> List.filter (divisibleby 2)
|> List.map (subtract 1)
Notice that this example depends on partial application in two ways. Not only are we partially applying the divisibleby and subtract functions to create our filter predicate and mapping function, but we are also partially applying the List.filter and List.map functions themselves.
Looking at list functions
F#’s list functions provide another case study in function design. Both List.filter and List.map take two arguments, and in both cases the filter or map function appears first, and the list to apply it to appears last. Similarly, List.fold (the equivalent to the LINQ Aggregate operator) puts the accumulator function first, the seed second and the list to aggregate over last.
This isn’t an accident. It’s precisely so that you can partially apply these functions.
The F# designers had two choices for the design of List.filter:
let filter predicate list = ... // actual
let filter list predicate = ... // hypothetical
The implementation is the same, of course, so that doesn’t help decide between them. But we can compare the meaning of the partially applied versions.
In the actual version, we can write List.filter predicate – for example, List.filter isEven – and get a function that we can apply to lists. This seems like it will give us useful functions: for example, List.filter isEven gives us a function that we can apply to a list to choose its even members.
In the hypothetical version, the partial application is List.filter list. So we can write something like List.filter ints and get a function that we can apply to predicates. In this version, List.filter ints takes a predicate, and returns all the elements of ints for which that predicate is true. This isn’t necessarily useless, but it’s kind of obscure, and more critically it is evidently a function of predicates, not of lists. If it is useful, it belongs in a Predicate module, not in a List module.
Just tell me the rules already
It’s impossible to lay down a firm set of rules on how to design F# functions. The two versions of List.filter above are functionally equivalent: the F# designers were able to choose between them because they knew that users were much more likely to be choosing a predicate and then passing different lists through it than to be choosing a list and trying different predicates against it. If you have a scenario where you have a fixed list and predicates coming in from the outside, then List.filter is the wrong design for you: you need a function which works the same as List.filter but reverses the arguments. (Needless to say, it’s trivial to write such a function: let trueIn list f = List.filter f list.) The ‘right’ design depends on how you’ll be applying the function.
Still, here’s my rule of thumb:
The thing you want to apply the function to should be the last argument.
This rule is, on the face of it, nonsense. The function takes multiple arguments, and you apply it to all of them.
But actually, a lot of the time it turns out that there’s one thing you want to apply the function to, and the other arguments are the extra information you need in order to apply the function. In the divisibleby example, I wanted to know if value was divisible by something. Of course, I had to say what that ‘something’ was; but it was the divisibility of value that I was interested in. And it turned out that putting value in the last place was the best choice. Similarly, in the subtract function, I wanted to subtract something from a minuend; I had to say what the subtrahend was, but the minuend was what it got applied to. And in List.filter, I wanted to filter things from a list; I had to say what criterion I wanted to use, but it was still the list that was being filtered.
Of course, this rule doesn’t help you to organise arguments other than the last, so what should you do if you have a function of three or more arguments? The rule of thumb is a bit more nebulous here, but here’s a stab at it:
Is there a particular argument (or set of arguments) which, if you pin it down, still gives you something useful? If so, put it at the front.
For a case study, let’s look at List.fold. This is roughly equivalent to the LINQ Aggregate operator: you give it a function, a seed and a list, and it applies the function to each member of the list in turn, starting with the seed. For example, List.fold (+) 0 list gives you the sum of the elements of list.
Obviously, the list argument is what List.fold is applied to, so that should be last. But why choose the actual List.fold (+) 0 list rather than the hypothetical List.fold 0 (+) list? Well, what is the meaning of the actual partial application List.fold (+)? It is a ‘sum from’ function – a sum operation starting with whatever seed it gets given. Contrast this with the meaning of the hypothetical partial application List.fold 0. It’s hard to find a meaning for this other than ‘aggregate using a seed of 0.’ Partially applying List.fold with the accumulation function gives us something more useful and meaningful than partially applying List.fold with the seed. So the accumulation function should go first, the list to accumulate over should go last, and by default the seed has to go in the middle.
These rules of thumb leave a lot of room for interpretation and judgment, and so they should. Design depends on context and usage. In part three we saw partial application being used to precompute a parse tree. In that example, was I applying the function to the formula text, or to the evaluation environment? Both perspectives are meaningful, and I put the formula text first and the evaluation environment last more for practical performance reasons than for conceptual reasons.
Ultimately, you’ll be guided by how you find yourself applying the function in practice. If you find yourself repeatedly writing lambda expressions that could be avoided by pushing a parameter to the front, then that’s a big hint. If you don’t, then either your design is already right, or it’s not enough of a problem to worry about. Ship it.