While this is a cool demo, I don't really like it even as a Haskell enthusiast. Anything that relies on compiler's eta reduction/expansion rules for performance is too subtle for my taste. I'd personally argue that more explicit code could be clearer.
Eta reduction/expansion has nothing to do with performance. It's a form of point free programming that allows you to abstract out intermediate variables and use partial application instead.
f x = reverse (sort x)
Becomes:
f = reverse . sort
The compiler reaches the same conclusion either way.
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.
I might have used incorrect terminology but what I meant in my previous comment is that it should be obvious when the right hand side is evaluated.
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.
> 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.
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
Thank you for a long comment. I should've been clearer in my original comment. The crux of the matter is really that the arity of a function should be clear from its type, but those functions violate that assumption. You might think it's not a valid assumption but in practice I think it's a matter of good style to enforce it.
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 ⊥.
I have to agree that the difference is very subtle, a bit akin to as if "a -> b -> c" is not "a -> (b -> c)". On the other hand, this difference rarely matters, except in memo cases, where it can be used for a pretty cool effect.
> 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.
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.)
> Eta reduction/expansion has nothing to do with performance.
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.
Maybe you mean using lazy evaluation as a memoization hack? That is a well known trick in Haskell though I agree it is in some ways cringy, relying on the evaluation strategy like that. But there are some Hackage packages that make it fairly convenient to use. I did a naive implementation myself and benchmarked it against an explicit STRef as a cache cell. I don't remember the result but it wasn't a huge (OOM+) difference iirc. Rather than using an array as the memo cache (which means you must know its size in advance), it's nicer to use an infinite branching tree.
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.
No disrespect to the dude that I learned Haskell from, but a) he doesn’t achieve his original goal and b) the goal is much less practically useful than he implies.
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.
Memoization is also entry level DP, and too easily confused with caching (if I had a dollar for every time someone equated the two, I could buy a baseball bat to knock heads).
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.
This account is over 3000 days old so that’s less than eleven imaginary internet points per day. Which is really how it mostly goes. Three points here, six points there. Nothing much for a couple of days, then something up or down.
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”.
I've been taught DP via tabulation and struggled to get it. Then I learned the memoization trick and I am never coming back simply because memoization is much easier to reason about, and the resulting code is often much cleaner. As the result, I would only resort to tabulation if I need to match some performance goal and memoization does not cut it.
Does this technique keep the memoization table in memory while the top level function is in scope (so essentially forever?) Or does it become unreachable once the initial call to fib from somewhere else finish?
I assume this could be fixed by using a lambda instead of a top level function if you only want to occasionally call such a function, and don't need the whole memoization table around all the time?
I can't disagree more with this. Running any modern language is magic. If you don't want to use magic. You only get to write assembly or maybe C. Not that I agree with this solution.
You could probably disagree more with it, if you really tried :D
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.
The problem is that no one can define magic. The thing that you might find magic is someone else mundane code or vice versa. It's simply a catch all statement that a lazy reviewer can slap on code they don't like. Just explain why you don't like it and be done with it.
That's a fair point, what's magic and what's a good abstraction is highly subjective.
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.
I would also disagree with that, but maybe not as much as the other guy.
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.
"Wouldn’t it be cool if we could just write the recursive function, and then have some generic machinery make it fast for us by automatically generating a memo table?"
"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!"
I develop calculang, a language for calculations. It converts concise formulae into Javascript.
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.
[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/
45 comments
[ 0.21 ms ] story [ 105 ms ] threadPerhaps 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.
[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.
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.
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.
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.
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 :)
"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.
@functools.cache
def fn(x):
https://docs.python.org/3/library/functools.html#functools.c...
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/