June 08, 2011
Partial function application in F#, part 3: precomputing partial results
In previous parts we saw that partially applying a function was a bit like creating a lambda to call that function. So far we’ve mostly used this as a convenience for calling LINQ-like functions. In this part we’ll look at it in a different context – precomputing partial results.
The expression engine
Suppose you’re writing a simple data analysis or reporting tool which operates over a data set. Users can enter formulae and the tool evaluates these formulae for each record in the data set – a bit like computed columns in a database. For example, maybe the input data contains a field named Age. Then the user could write 65 – Age and assign this to a field named YearsUntilRetirement.
Using the F# tools fslex and fsyacc, it’s fairly easy to build a parser that translates the user text to an abstract syntax tree (AST), and a set of evaluation functions to walk such a tree and perform the calculations. You can then put this behind a handy evaluate function which hides all the implementation from the caller.
The one wrinkle – and it’s an important one – is that evaluating an AST requires not only the AST itself, but also the values of the fields to which the user formula refers. In the 65 – Age example, the evaluator needs to be able to get the Age value for the record being processed. We’ll call this an evaluation environment. So the evaluate function looks something like this:
let evaluate text environment =
let ast = parse text // parse is private
evalAst ast environment // evalAst is private
That is, evaluate and evalAst takes two arguments, the formula string and the evaluation environment object.
The evaluate function works fine for small data sets. But if you feed it a lot of records, you’ll notice that it feels a bit… well… sluggish.
It’s not hard to see why. For every record, evaluate is taking the string expression, parsing it, and then evaluating the parsed AST in the provided environment. And it turns out that parsing formulae is hard work.
Let them eat AST
Parsing the same formulae for every record is redundant. The only thing that varies from record to record is the environment: the same formula always results in the same AST.
This suggests one way to solve the performance problem: make the parse and evalAst functions public. Then the consumer can run parse once, store the resulting AST, and feed it back into evalAst as required. Sorted, right?
A functional solution
This works, but at the expense of requiring the consumer to know about parsers and ASTs. The consumer isn’t really interested in the parsing process and its intermediate results. The consumer just wants a way to get the result of a formula for a particular environment.
A way to get one value from another? That sounds like a function! Specifically, it sounds like a function from environments to results.
Without further ado, let’s write that function:
let makeEval text =
let ast = parse text
makeEval starts out the same as evaluate, but because it doesn’t have an environment argument, it can’t finish the job. Instead, it partially applies the evalAst function. Partial application leaves us with something still waiting for an environment, and ready to return a result when it gets one – that is, a function from environments to results, just as we needed.
let f = makeEval "65 - Age" // can cache this for reuse
let result = f env
Like the previous fix, this solves the performance problem. When you call makeEval, F# precomputes the AST, doing all the hard work of parsing, and returns you a function with that precomputed AST all tucked up inside. When you apply that function, it uses the precomputed AST, so it doesn’t pay the parsing overhead again.
Spelling it out
This may be confusing, so I’ll rewrite makeEval in a more C#-like idiom:
let makeEval text =
let ast = parse text
fun env –> evalAst ast env
This makes it clearer that makeEval returns a function, and exactly what that function does, at the expense of some noise.
Finding the right partial results to precompute
What if we didn’t control the expression engine? Could we still take advantage of precomputing by partially applying evaluate?
let f = evaluate "65 – Age"
let result = f env
evaluate "65 – Age" does return a function from environments to results, so this superficially seems attractive. Alas, it is fools’ gold. The only thing precomputed by evaluate "65 – Age" is the string "65 – Age", which is no saving at all! Partial application doesn’t look inside evaluate to see if there’s anything it could precompute – all it does is bundle up the arguments it has in the form of a lambda. The above is equivalent to:
let f = fun env –> evaluate "65 – Age" env
It’s now obvious that the full evaluate function, including the repetitive parsing, would run each time the lambda was called. The makeEval function works only because it precomputes the AST: it relies on partially applying evalAst rather than partially applying evaluate.
Precomputing partial results is a handy technique in any language, and will work in any language where you can capture those partial results and provide an easy way to reuse them. Lambdas are a particularly convenient way to provide a function with precomputed state, and what we’ve seen here is basically partial application as a shorthand for lambdas.
I hope that after this part and the previous one, partial application doesn’t seem quite as intimidating or obscure as it seemed after the first part. In the next part, I’ll return to the underlying concepts and implementation.
TrackBack URL for this entry:
Listed below are links to weblogs that reference Partial function application in F#, part 3: precomputing partial results: