Dynamic programming in Haskell: automatic memoization
byorgey.wordpress.com
byorgey.wordpress.com
f x = reverse (sort x)
f = reverse . sort
Perhaps you are thinking of RULES pragmas? Which honestly you wouldn't usually reach for unless you really need to force the compiler to optimize in a particular way that is non-trivial.
If a function has type declaration `f :: A -> B -> C` you would expect that its body only gets evaluated when two arguments are actually supplied. So evaluating the function itself using `seq` doesn't do anything. Nor does partial application of a single argument.
To be absolutely clear, the expressions `seq f (putStrLn "hello")` and `seq (f undefined) (putStrLn "hello")` should both not evaluate anything and cause the string hello to be printed rather than raising an exception.
However you can make it otherwise. That breaks the user's intuition about evaluation. Most of the time it's not a problem at all; I just personally don't like it and prefer to be more explicit.
This often occurs in cases where the above hypothetical function `f` requires an intermediate value that's expensive to compute but only relies on the first of its two arguments. Then do you evaluate that expensive intermediate with a partial application of a single argument, or do you not? Neither is satisfactory and so this problem is best avoided.
In your trivial example `reverse . sort` the compiler will inline the dot operator and make it `\x -> reverse (sort x)` and I have no issue there.
That’s not correct, regardless of η expansion. The core of the issue is that this function really takes one argument, regardless of how in practice it is used as if it had two.
> the expressions `seq f (putStrLn "hello")` and `seq (f undefined) (putStrLn "hello")` should both not evaluate anything and cause the string hello to be printed rather than raising an exception.
That’s not how `seq` works, as per language report. The definition is very simple, and does not take into account any kinds of types (such as treating functions differently). The report demands that `seq ⊥ x = ⊥` [1], so if the first argument is ⊥, you get a crash. Whether `x` is also evaluated in this context is up to the compiler actually, but what certainly cannot happen is that a "hello" is printed, because that would require a non-⊥ value to be passed to the surrounding IO context, but the whole `seq` is ⊥, so that’s not possible.
In GHC, seq is essentially a tag that helps the strictness analyzer, and hence the optimizer.
There is one subtlety in GHC that makes it not respect η expansion, and that is strictness properties, namely that `seq ⊥ () = ⊥`, but `seq (\x -> ⊥ x) () = ()`, were you referring to that? (In my opinion this is a violation of the Haskell Report.)
> This often occurs in cases where the above hypothetical function `f` requires an intermediate value that's expensive to compute but only relies on the first of its two arguments.
Lookup tables work that way, yes! I’m using this technique for walking a certain distance on a Bezier curve for example (Code at [2], result picture at [3]) Call that academic and I’ll show you the DIN A1 sized CNC machine I control using that logic ;-P
[1]: https://www.haskell.org/onlinereport/haskell2010/haskellch6.... [2]: https://github.com/quchen/generative-art/blob/master/src/Geo... [3]: https://quchen.github.io/generative-art/generative-art-0.1.0...
My point about seq is really about arity. If a function has arity 2 then partial application of ⊥ cannot cause any part of the function to be executed and therefore the function cannot inspect its argument and find that it is ⊥.
This does actually work here, because the array is created lazily.
> This often occurs in cases where the above hypothetical function `f` requires an intermediate value that's expensive to compute but only relies on the first of its two arguments. Then do you evaluate that expensive intermediate with a partial application of a single argument, or do you not? Neither is satisfactory and so this problem is best avoided.
Computing the intermediate value with a partial application does not actually take away laziness, it only adds sharing. (At least it can be done this way.)
It affects inlining. GHC only inlines fully applied functions, where "fully applied" means applied to as many arguments as it was declared with. So in something like `g = fmap f` your first definition of `f` would never get inlined into g whereas your second definition might.
In practice an awful lot of the functions you want to memoize a) involve continuations and b) want some way of evicting things from the cache.
Haskell has no end of cute tricks for doing deterministic functions, it’s just that deterministic functions are programming’s easy mode.
If you want the power of dynamic programming you need to get at least as far as tabulation.
I’ve just gone through removing “memoization” from two parts of our code that were difficult to understand even without the caching layer. The reason I did the second one is because the first one went so well I wanted to see if it was a fluke.
In doing the first, what I did was replace depth first execution with a tree scan. At the end I had a set of actions that needed to happen, and why. Essentially a plan for the execution. That’s a great spot for a breakpoint if the code or a test are failing, but it also yields you a set with all of the duplicates removed, instead of a graph. And in this case the number of data operations to combine all of the data is n+1 instead of > nlog(n) based on the number of duplicates. It also pointed out other optimizations that were possible.
In the second case it also surfaces a potential ordering problem, and the added wrinkle was that some warning messages were being repeated, quite confusing to other developers. Those could be reduced from eight to three.
In both cases memory usage was reduced (and in the one case the code was a bottleneck for starting short lived processes) because you don’t cache anything that is used once. There is no clever trick you need to work out. It just works, and the mechanism is perfectly readable and reason-able.
I was among those who down voted your earlier comment, and I did so because of the talk about knocking heads with a baseball bat.
It’s not the points it’s the conversation. One of the few times this year I scored highly, I said virtually the same thing in two parts of the same post. Nothing sarcastic, no dark humor, something like +40 points and responses for one, no responses and oblivion for the other. I only know they former because the latter made me curious.
Popularity is weird, not that I’m probably telling you anything new. There are some ideas that are only popular here for a certain crowd, and if they see it first you’re good, if they don’t it’s either gone, or you come back a few hours later to see you’ve swung from -2 to +5. It’s a nice vindication but your flow is gone and so I never feel like those conversations get as far. Maybe that person is a kook, or maybe you’ve had a narrow experience. Or they have. Maybe if you talk about it you’ll learn which.
One of those topics, based on previous experience (here, elsewhere, and I’m person”, seems to be, “DP is much more than caching”.
Anyway, thanks for replying.
"In other words, we’d like a magic memoization function . . . Then we could just define our slow, recursive function normally, wave our magic memo wand over it, and get a fast version for free!"
Perl has this exact functionality with Memoize:
https://perldoc.perl.org/Memoize
More programming languages should have this functionality built in.
Since calculation formulae are usually inherently pure, a `--memo` flag to the compiler memoizes the lot.
Many of my models are written in this recursive style and only work because of memoization. Sometimes other tricks are needed e.g. careful ordering of the calls, so that the memo is available before the stack breaks.
My first calculang example is a bouncing ball: the position at t depends on speed and the position at previous t. With loops we'll usually discover the same thing, but it can be so much harder to follow.
First-class memoization to proliferate this style is a really neat thing.
[0] https://github.com/calculang/calculang
[1] bouncing ball code: https://github.com/declann/calculang-miscellaneous-models/bl...
[2] bouncing ball initial post: https://observablehq.com/@declann/calculang-bouncing-ball?co...
[3] if you can tolerate my slow-load WIP devtools and are on a Desktop, this is better, with buttons to navigate through the model development (only some of which are working now!): https://models-on-a-plane.pages.dev/stories/bounce/
@functools.cache
def fn(x):
https://docs.python.org/3/library/functools.html#functools.c...
[0]: https://www.swi-prolog.org/pldoc/man?section=tabling-memoize [1]: http://retina.inf.ufsc.br/picat_guide/#x1-210001.5
You may want a new control operator. In case of, say, Java, you go and ask language developers. In case of Haskell, you write a function or a bunch of functions. "if-then-else" can be implemented in Haskell as a function, for one example. Myself, I created a lot of these control operators when I worked with Haskell. I also used a lot of operators defined by others.
Any code you describe with "Magically" is going to bite you in the arse in about two months. Maybe three.
Leave magic to the guy who also does balloon animals at kids parties.
I had the pleasure of being able to use Haskell "in anger" for about a year. Still my favorite language to toy around with, but would not want to use it for work again.
One take away is that half of the time Haskell code "just works". You write algorithms as you think they should be and often the resulting binary is "good enough™".
The other half you spend in the trenches hunting down memory leaks because some thunk was not evaluated and your program is amassing unevaluater expressions until it dies :-)
And I'm not picking on Haskell here, I've lost countless hours to weird Spring failures when multiple annotations on one class or method interact poorly and produce a stack-trace deep in the bowels of Spring's annotation processors.
Or, well, gestures at Hibernate in general
Likewise, Django classes that defy type annotations because they override __new__ and inject nested classes into types, or queries over joins where the join logic between attribute A and type B is magically parsed from an undeclared keyword argument like "A__B__filter" that includes attributes, types and actions in one convenient keyword that no IDE can predict.
Like your unevaluated thunks, trying to figure out why "Foo__Bar__bomb_baghdad" didn't actually bomb Baghdad takes a large amount of time.
The magic is convenient until it breaks :)
But it's a bit early in the evening for reductio ad absurdum.
After all, we can take it further into absurdity, why aren't we all just programming in hex via a keypad in the front of the computer?
Abstraction != magic.
The one bit of SICP that really stuck in my brain was:
"Programs must be written for people to read, and only incidentally for machines to execute"
Magic makes the first part far harder. If I need to understand your deep magic to understand your code, well, that's making my life harder, and don't you want people to understand what you're doing and why?
I apply this critique to every kind of magic in code.
Annotations in Java frameworks (I've had so much fun with Spring proxy invocations over RPC via Camel), monkey patching and metaprogramming in dynamic languages (or as Zed Shaw referred to it in Ruby, chainsaw infanticide) ...looking at you Django...
Oh, and of course weak type coercion hacks and Perl's (< 6) DWMI. I mean, once you decode the sigils, it's a good feeling because you "get it", but if I want to feel clever for "getting it", I'll do cryptic crosswords.
I'd far rather workaday code be boring and obvious when I have to make a mental model of it in order to fix it.
I like it when I can read your code after you've moved onto another company, and understand what the code is doing and why without having to inveigle you into an awkward Zoom call or having to rewrite the magic step by painful step after the magician left, just so it's accessible to others.
I've used "memoizing intermediate steps" often in the past, but it doesn't need to be magic.
I guess I'm a fan of the principle of least surprise.
I'd far rather explicitly define a configuration property in some file than "if you create an environment variable called FOO_CONFIG_X=5, the Foo framework will populate your settings for you!"
Because when the Foo framework doesn't respond to your incantations the way the docs say it should, then you're going to spend the rest of the day reading code to figure out why.
Shit, the Spring annotation magic made me miss XML context files for that reason, the XML made wiring explicit, as opposed to auto wiring annotations that failed deep in the bowels of the beast.
It's a continual problem across languages and frameworks, the (admittedly very) convenient magic is great until it isn't.
I've lost enough time on it in my career that these days the only dependency injection libraries I'll consider for a new project have to be compile time.
Still as much magic, possibly even more (trying to understand Quarkus' compile time DI library ArC is... something), but at least it breaks before you can deploy it.