« Partial function application in F#, part 2: a technique for simplicity | Main | Partial function application in F#, part 4: underlying concepts »

## 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.

**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.

June 8, 2011 in Software | Permalink

## TrackBack

TrackBack URL for this entry:

https://www.typepad.com/services/trackback/6a00d8341c5c9b53ef015432d8a3ac970c

Listed below are links to weblogs that reference Partial function application in F#, part 3: precomputing partial results: