In my TestNess project I have decided to try to rewrite certain parts in F# to see if the code can benefit from functional programming. It is also a learning thing as I’m definitively not well versed in functional programming - yet :-). One of the specific problems I try to address is to create sub structures given a root structure. The root structure is typically a method, and a sub structure can be a call graph for that method. Creating a call graph is non-trivial, so preferably I want to do this only once for each method, and I therefore need to cache the graph.
This is in itself not a problem at all, but my colleague Jimmy told me he was pretty sure that functional languages have some sort of build-in caching in general. This lead me to investigate a bit, and I ended up on this page.
To test return value caching, I created a tiny Visual Studio 2010 project which can be fetched from GitHub.
To begin with, I need a type from which I can create instances (this type corresponds to the aforementioned call graph):
type AType(i:int) = class end
(You gotta love the conciseness!) Next, a function that creates an instance of the type given some input:
let produceWithArg i = new AType(i) let produce = produceWithArg
For the sake of unit testing this, I’ll create an “alias” function
produce. I’ve created two really simple unit tests, one that
verifies that the function produces the same value if given the same
input repeatedly, and one that verifies that the return values are not
the same for different inputs. Here they are in all their glory (I chose
NUnit simply because I had it on my machine):
[<TestFixture>] type cachingFixture() = class [<Test>] member self.cacheWithSameInputTest() = Assert.AreSame (produce 1, produce 1) [<Test>] member self.dontCacheWithDifferentInputsTest() = Assert.AreNotSame (produce 1, produce 2) end
produce function as defined above, the first test fails while
the second passes. This is quite expected, as the function obviously
creates a new instance each time it is called.
The first attempt at a caching solution, then, is to remove the argument. According to the link mentioned previously: “When F# comes across a function with no parameters, F# will only evaluate the function once and reuse its value everytime the function is accessed.” Let’s try it:
let produceNoArg = fun i -> new AType(i) let produce = produceNoArg
Unfortunately, the test result is the same as before. The reason? Well, what’s being cached in this case is indeed the return value, which happens to be the (anonymous) function! But if the returned function is called twice, it will of course create two instances of the type! It’s return value cannot be cached since it takes a parameter.
Lesson learned: This type of caching is only interesting if the evaluation of the function is expensive but the execution is trivial. My situation is directly orthogonal to this!
The next attempt is to use lazy evaluation. Using the
lazy keyword, we
can create a
Lazy<AType> instance that caches its value:
let produceLazy i = lazy(new AType(i)) let produce i = (produceLazy i).Force()
Note that this is not as transparent as before; we need to call the
Force() method to retrieve the value. And sadly, our tests are still
in the same state - the first fails and second passes. What happened is
Lazy<AType> were created, and they won’t cache values between
each other for obvious reasons.
Would it be better to combine a parameter-less function with lazy evaluation? No, because at some point we must introduce a function that takes a parameter, and then everything is lost.
So the third attempt is to use memoization, which in this context means
explicit return value caching. But we can do a bit better than having to
be explicit in every function that needs caching. I use the
function copied from the link above like so:
let produceMem = memoize(fun i -> new AType(i)) let produce = produceMem
And finally both tests pass!