Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I've been recently studying inline caching as a technique to optimize method dispatch in object oriented languages. Basically, the idea is that one can remember what was previously dispatched and predict that things will go on in the same way.
My question is whether this technique has been used in pure functional languages (I'm a native of Scala which mixes both paradigms thus the uncertainty).
As Gilles points out, it's not immediately obvious what the analogue of this would be in a non-object-oriented language. Below is one suggestion.
Let's say you have a function h :: (A -> B) -> C (this is using Haskell syntax). h is a higher order function and particularly it takes a function of type A -> B. The definition of h will be something like:
h f = ... (f a) ...
h doesn't know what f will be so it must emit code for a call to an unknown function. Of course, if (h g) occurs in the code where g is a known function, the compiler may choose to inline h and then further optimize the inlined body of h with f now known. This is just normal inlining. We could also imagine a similar variation where we make specialized versions of h for some finite collection of functions A -> B and call the appropriate specialized version rather than inlining. (For GHC Haskell, this occurs with type classes via the SPECIALIZE pragma.) Neither of these are inline caching, though you could imagine a "static" version of inline caching that adds the appropriate guards and branches to specialized code if possible and otherwise falls back to generic code. I don't believe this is a particularly common optimization whether a language is functional or not. It's similar to rearranging branches to improve branch prediction though.
On the other hand, this optimization and inline caching in OO languages will both happen automatically with a trace-based JIT compiler. If you view a first-class function as an object with a single method as many OO languages with higher order functions do, then inline caching will do this optimization. That said, there aren't that many functional languages with a JIT compiler (tracing or otherwise) based implementation, particularly for a JIT compiler specifically geared to the functional language. Two trace-based systems for functional languages described in the literature are Pycket for Racket, which is not a purely function language, and Lambdachine for Haskell. I'm not aware of any JIT compiler for a functional language that explicitly and specifically targeted this particular optimization.
