A "memoized" modifier for function caching proposal

[Nikita Volkov]

Memoization is an optimization technique when function evaluation results get cached by the set of passed parameters. This allows to evaluate the function only at the first time it is called with a specific set of arguments and return the cached results on all the consecutive calls with the same set of arguments.

You can think of it as of a more general lazy that also distinguishes the parameters. Thus memoization on functions with no arguments, such as memoized def functionWithNoParameters: String will have absolutely the same effect as lazy val functionWithNoParameters: String.

Some Use Cases

1. Functions with heavy calculations

    memoized def calculateSomething(a: Int, b: Int): String = {
      // some heavy calculations take place here
    }

    calculateSomething(1, 2)    // since it's the first time the function is called with 
                                // parameters `(1, 2)` it will actually evaluate, then
                                // it will store the result in cache and return this result

    calculateSomething(1, 2)    // since the function has already been called with this
                                // set of parameters it will quickly just fetch a result 
                                // from the underlying cache, and no actual evaluation will
                                // take place

    calculateSomething(1, 3)    // will calculate again, since yet there's no record for 
                                // a `(1, 3)` arguments set in cache yet

2. Implicits keeping context or state

    //  the following will always return the same instance of `ListWrapper` per each list
    memoized implicit def listWrapper[T](list: List[T]) = new ListWrapper(list)

    class ListWrapper(source: list) {
      lazy val cachedPermutations = list.permutations
    }

    List(1, 3, 4, 4, 4, 3, 3).cachedPermutations  // will calculate
    List(1, 3, 4, 4, 4, 3, 3).cachedPermutations  // will fetch the result from cache

A sample implementation

memoized def resolveSomething(a: Int, b: Int): String =
  a.toString + b.toString

This would generate a code similar to the following:

private val resolveSomethingCache = collection.mutable.Map[(Int, Int), String]()
def resolveSomething(a: Int, b: Int) =
  try resolveSomethingCache((a, b))
  catch {
    case _ => {
      val result = {
        //  actual implementation relies here:
        a.toString + b.toString
      }
      resolveSomethingCache.update((a, b), result)
      result
    }
  }

Please note that in the implementation above I didn't take multithreading into account.

I'm not sure about the correct procedure to make it go into the actual proposal. On the SIP documentation I've seen a recommendation to discuss it here. Just in case, I've also posted an appropriate issue on the tracker: https://issues.scala-lang.org/browse/SI-5741

[Tony Morris]

On 04/05/12 21:45, Nikita Volkov wrote:
>
> Memoization is an optimization technique when function evaluation results
> get cached by the set of passed parameters. This allows to evaluate the
> function only at the first time it is called with a specific set of
> arguments and return the cached results on all the consecutive calls with
> the same set of arguments.
>
> You can think of it as of a more general lazy that also distinguishes the
> parameters. Thus memoization on functions with no arguments, such as memoized
> def functionWithNoParameters: String will have absolutely the same effect
> as lazy val functionWithNoParameters: String.

> Some Use Cases1. Functions with heavy calculations

However, a Map is not always optimal to implement memoisation. You'd
want the user to define the cache, among other things. Also useful
(mandatory?), you'd want a guarantee that the function is indeed a
function -- we've all seen what happens when we equivocate here right?.

--
Tony Morris
http://tmorris.net/

[missingfaktor]

I do not see why this needs to be supported at a language level. It is possible to provide memoization facilities as a library:  http://michid.wordpress.com/2009/02/23/function_mem/.

--

Cheers,

missingfaktor.

[Justin du coeur]

I find the suggested syntax cleaner and more obvious.  But I do wonder if it could be implemented with a macro -- it seems like an obvious use case, and that seems cleaner than trying to bake it into the language.  (Can a macro work as an annotation to a function like that?)

[Eugene Burmako]

Currently macro cannot be applied to defs. However, we plan to explore macro annotations in the future - they will enable this technique.

So, roughly speaking, if we find macro annotations good enough to include them in Scala, you would be able to write:

@memoized def calculateSomething...

[Alex Repain]

2012/5/4 Nikita Volkov <nikita....@gmail.com>

2. Implicits keeping context or state

    //  the following will always return the same instance of `ListWrapper` per each list
    memoized implicit def listWrapper[T](list: List[T]) = new ListWrapper(list)

    class ListWrapper(source: list) {
      lazy val cachedPermutations = list.permutations
    }

    List(1, 3, 4, 4, 4, 3, 3).cachedPermutations  // will calculate
    List(1, 3, 4, 4, 4, 3, 3).cachedPermutations  // will fetch the result from cache

In this example, I wouldn't like the last 2 lines to work like hinted in the comments. You are producing 2 different instances of a List, so unless you use List case matching to check if a SIMILAR list has already recorded a cachedPermutations result, the memoization here won't work. And case matching is not enough to guarantee a strong functional equivalence between objects, so this option is to be ruled out. Therefore, you probably meant to write :
 

val l = List(1, 3, 4, 4, 4, 3, 3)


l.cachedPermutations  // will calculate
l.cachedPermutations  // will fetch the result from cache

[Stefan Zeiger]

On 2012-05-04 15:28, Justin du coeur wrote:

memoized def resolveSomething(a: Int, b: Int): String =
  a.toString + b.toString

A purely library-based implementation doesn't have to be that much more verbose:

val resolveSomething = memoized[(Int, Int), String] { _ => { case (a, b) =>
  a.toString + b.toString
}}

(Using https://github.com/typesafehub/slick/blob/a2774ab174ee5b48b0b96d3c32934d45ecf7184c/src/main/scala/scala/slick/ast/OptimizerUtil.scala#L24)

[Justin du coeur]

It's not a matter of verbosity, so much as clarity.  It's very subjective, but I find that having memoized as more or less an annotation is a nice separation of concerns: it treats the memoization as a separate notation, visually and logically apart from the algorithm that you're memoizing.  Not a huge deal, but it does feel cleaner and more consistent to me.

Of course, there's a part of me that *really* wants an annotation that says, "This is a pure but complex function", and have the memoization simply fall out from that as an optimization.  Or better yet, in the long run, simply have the compiler decide based on static code analysis.  Do folks use memoization for anything *other* than optimization, in practice?  I've mostly lived in the procedural world, so I don't have a sense of the state of the art here, but I've always thought of memoization as a concise way of saying "optimize this sucker in this specific way"...

[Daniel Sobral]

Why a new keyword? Why not just "lazy def"?

Personally, I'd wait for further developments on the macro side of
things, and implement it as a library. In fact, some libraries already
implement it, though not as seamlessly as it would be possible with
macro annotations.

--
Daniel C. Sobral

I travel to the future all the time.

[Dave Griffith]

I would favor this as a library as well. Indeed, I could see value in
putting it as a method on Function, similar to tupled/untupled/curried/
uncurried, or on each of the FunctionN, like compose and andThen.
It's obviously not as fundamental as those, but would still be a
reasonable small addition to the standard library.

--Dave

[Jori Jovanovich]

> On May 4, 10:56 am, Daniel Sobral <dcsob...@gmail.com> wrote:
>> Why a new keyword? Why not just "lazy def"?

I like this a lot … it adds a nice feature and makes the language more intuitive. When I was first starting with Scala that I tried to write a "lazy def" expecting this behavior and was surprised that it gave me an error message.

[Simon Ochsenreither]

I think the hard/impossible part is to figure out sane settings which work for everyone.

E.g.:

Can the Map grow indefinitely?
Will it start discarding values? If yes, which ones? Oldest? Last-used? Least-used?
What's the life-time of those values? SoftReferences/WeakReferences/StrongReferences?

Imho a single keyword doesn't suffice here. I guess at least some macro annotation with a LOT of options is necessary here. If that would be worthwhile is a separate question...

[Jori Jovanovich]

You could also use regular annotations or an implicit to provide options if it was a "lazy def" keyword.

[ARKBAN]

I agree, and I'd go further to say I don't think its possible to find
single set of settings will work for everyone. Look at the array of
options for caching in Google's Guava libraries
http://code.google.com/p/guava-libraries/wiki/CachesExplained

ARKBAN

[Nikita Volkov]

On foreign libraries and the reasoning behind the special keyword

The only decent argument against this feature being implemented as a keyword IMO was expressed by Simon Ochsenreither, saying that there may arise some situations when this feature will need to be customized and it's impossible to do on a keyword. That I'll address in the section about the memory issues. All the other arguments are just as applicable to the `lazy` keyword, yet it exists, and no one has to say anything against it. 

In fact I see the current proposal as a direct sister of `lazy`. It has so much in common with it that the newcomers even expect it to be already implemented, as Jori Jovanovich did and I did too. It just fits organically. Besides, nowadays the `lazy` feature is so frequently used that some people even call it idiomatic Scala. The memoization feature has all the chances to become just as popular if easy to use, which brings us to the libraries approach issue.

As Justin du coeur pointed out the library approach makes memoization a part of an algorithm, which it has nothing to do with. The library approach piles up your code with repitative redundant symbols which distract you from the actual problem. It closely couples your code with that lib. It adds a one extra serious obstacle in readability of your code for the ones not acquainted with such a lib.  

Finally I want to emphasize that a feature of memoization at hand is not just about caching the "heavy" functions, but the introduction of new concepts, changing your approach to the problem. Just take another look at the example with implicit. I strongly believe that there are much more horizons for us to explore with it than with `lazy` and that it has at least as much rights to be.

On `lazy def`

Actually I've considered that for this proposal but after some analysis I've put that away. 

You see, the `lazy` keyword implies "initialized lazily" in the case of a `val`, which means that a value's initialization is somehow deferred. What will it imply in case of a `def`? The functions don't initialize, nor do we want to defer anything about their evaluation, if anything we want to cache them or memoize them. Besides "memoization" is a very common and correct term describing exactly the case of the current proposal, but above all "a lazy function" syntactically just doesn't make sense.

On memory and setup issues

As far as I see the only need for customization of memoization behaviour is custom memory management. But I see no need for that. 

The actual cache of the function gets held on the context object on which the function gets called as a method. So as soon as this object loses all pointers to, it should get garbage collected with all the cache of the memoization. The issue will preserve for the static singleton objects though, but anyway I believe that memoization must be used with care.

Please correct me if I'm wrong.

I strongly vote for keeping it as simple as possible. 

On the argument of Alex Repain

Scala compares lists by their contents. Even when they are used for keys in maps. Please consider the following:

scala> val cache = collection.mutable.Map[(List[Int]), String]()

cache: scala.collection.mutable.Map[List[Int],String] = Map()

scala> cache.update((List(1,2,3)), "abc")

scala> cache

res4: scala.collection.mutable.Map[List[Int],String] = Map(List(1, 2, 3) -> abc)

scala> cache.update((List(1,2,3)), "cba")

scala> cache

res6: scala.collection.mutable.Map[List[Int],String] = Map(List(1, 2, 3) -> cba)

2012/5/4 ARKBAN <ark...@arkban.net>

[Rex Kerr]

On Fri, May 4, 2012 at 2:03 PM, Nikita Volkov <nikita....@gmail.com> wrote:

On memory and setup issues

As far as I see the only need for customization of memoization behaviour is custom memory management. But I see no need for that. 

The actual cache of the function gets held on the context object on which the function gets called as a method. So as soon as this object loses all pointers to, it should get garbage collected with all the cache of the memoization. The issue will preserve for the static singleton objects though, but anyway I believe that memoization must be used with care.

Please correct me if I'm wrong.

I strongly vote for keeping it as simple as possible. 

This only covers a small fraction of use-cases, however.

I have all sorts of memoization in various image processing code that I run, ranging from data fetching to analysis to other things.  Of the 20-odd uses of the memoizing code that I use in that code, only twice do I memoize only the last result and only once do I memoize everything.  All others have some different scale appropriate to the memory usage and context of the task.

"As simple as possible" would require, I think, 80% of the work for 20% of the benefit.  Not a good investment of time.

  --Rex

[Daniel Sobral]

On Fri, May 4, 2012 at 3:03 PM, Nikita Volkov <nikita....@gmail.com> wrote:
>
> On `lazy def`
>
> Actually I've considered that for this proposal but after some analysis I've
> put that away.
>
> You see, the `lazy` keyword implies "initialized lazily" in the case of a
> `val`, which means that a value's initialization is somehow deferred. What
> will it imply in case of a `def`? The functions don't initialize, nor do we
> want to defer anything about their evaluation, if anything we want to cache
> them or memoize them. Besides "memoization" is a very common and correct
> term describing exactly the case of the current proposal, but above all "a
> lazy function" syntactically just doesn't make sense.

A "lazy function" is a non-strict function which caches its value once
evaluated.

[Alex Cruise]

On Fri, May 4, 2012 at 12:35 PM, Daniel Sobral <dcso...@gmail.com> wrote:

A "lazy function" is a non-strict function which caches its value once

evaluated.

...but, *which* value?  For Function0, sure.  But if it's a Function2[Int,Int,Int] there are an awful lot of possible values you might want to cache.

-0xe1a

[Lars Hupel]

> All the other arguments are just as applicable to the `lazy` keyword,
> yet it exists, and no one has to say anything against it.

Well, I guess I speak up against it, then. With macros in place and
research about macro annotations going on, there is absolutely no need
for a dedicated `lazy` syntax any more. Apart from that, the `lazy val`
feature isn't even very orthogonal right now (no support in method (and
function) parameters).

[Nikita Volkov]

I'd like to point out that I wasn't arguing against macros. I think it's fine if this feature gets realized with macros, as long as it comes bundled into the core Scala distribution and as long as there are no barriers to applying it. 

2012/5/5 Lars Hupel <hu...@in.tum.de>

[Bernd Johannes]

Am Freitag, 4. Mai 2012, 21:31:55 schrieb Rex Kerr:
> On Fri, May 4, 2012 at 2:03 PM, Nikita Volkov
<nikita....@gmail.com>wrote:

> > *On memory and setup issues*

+1 to that...

Deterministic caching is only useful when the caching behaviour is plugable.

A fixed/naive caching behaviour would be limited to rather trivial caching
problems. So I vote for some kind of library approach for caching
implementations (if there is to be some kind of "lazy def" in scala's
future...).

Greetings
Bernd