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.

Performance sucks

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
  evalAst ast

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.

Conclusion

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.