5 ms·

It would be interesting to include skip[1] as it has language level memoization. There was a recent HN discussion about the language [2]. I do not think that th

It would be interesting to include skip[1] as it has language level memoization. There was a recent HN discussion about the language [2]. I do not think that the naive recursive Fibonacci is a useful benchmark in any way though, it's a way too pessimized implementation. [1] http://www.skiplang.com/ http://www.skiplang.com/ [2] https://news.ycombinator.com/item?id=18077612 https://news.ycombinator.com/item?id=18077612

ishitatsuyuki 8y ago
Memoization isn't a new thing. It's available in Haskell as a first class citizen. This benchmark explicitly targets popular languages, and it happens to include no pure functional languages.
- harpocrates 8y ago
  > It's available in Haskell as a first class citizen. Not really. Haskell's laziness makes it easier to write functions that are memoized, but it does not automagically memoize functions. And how could it without incurring a non-trivial runtime space/time cost? Haskell's purity is what makes it easier to write libraries that facilitate building memoized versions of functions in a transparent way (and that are obviously correct). For instance, I usually reach for [data-memocombinators][0], which happens to have a fibonacci example at the top of the docs: import qualified Data.MemoCombinators as Memo fib = Memo.integral fib' where fib' 0 = 0 fib' 1 = 1 fib' x = fib (x-1) + fib (x-2) [0]: http://hackage.haskell.org/package/data-memocombinators-0.5.1/docs/Data-MemoCombinators.html
  - Symmetry 8y ago
    But is there any reason the Haskell compiler couldn't decide to memoize a function call itself if it determined that it would speed things up? To me that sounds hard for the compiler to do heuristically but a Haskell compiler should still have more scope to do optimizations like that than a C compiler has.
  - vmchale 8y ago
    Haskell is call-by-need so you get guarantees you wouldn't otherwise. It's not the same as memoization but it gives you what you want in any case.
gnulinux 8y ago
Why do we need language level memorization again? In python memoizing a function is just one line `@lru_cache()` I can't see why this needs an improvement by adding yet another thing to the core language.
- thaunatos 8y ago
  Just adding a @lru_cache() to a python isn't guaranteed to be correct; for example, if you're reading from an API the response could change between calls. Skip tracks side effects, and will either (a) memoize automatically a pure function or (b) recognize that a function is impure and avoid the memoization.
- ulucs 8y ago
  Some time ago, facebook introduced a javascript compiler which pre-compiled intermediate values. I think the point was to extend the spirit to the backend apps. If memoization is first class, implementing pre-compilation should be a blast
vmchale 8y ago
> I do not think that the naive recursive Fibonacci is a useful benchmark in any way though, it's a way too pessimized implementation. probably, but I would still like to see more benchmarks that use recursion. It's a fundamental technique from functional programming and so few benchmarks bother with it at all.

ishitatsuyuki 8y ago

Memoization isn't a new thing. It's available in Haskell as a first class citizen. This benchmark explicitly targets popular languages, and it happens to include no pure functional languages.

harpocrates 8y ago
> It's available in Haskell as a first class citizen. Not really. Haskell's laziness makes it easier to write functions that are memoized, but it does not automagically memoize functions. And how could it without incurring a non-trivial runtime space/time cost? Haskell's purity is what makes it easier to write libraries that facilitate building memoized versions of functions in a transparent way (and that are obviously correct). For instance, I usually reach for [data-memocombinators][0], which happens to have a fibonacci example at the top of the docs: import qualified Data.MemoCombinators as Memo fib = Memo.integral fib' where fib' 0 = 0 fib' 1 = 1 fib' x = fib (x-1) + fib (x-2) [0]: http://hackage.haskell.org/package/data-memocombinators-0.5.1/docs/Data-MemoCombinators.html
- Symmetry 8y ago
  But is there any reason the Haskell compiler couldn't decide to memoize a function call itself if it determined that it would speed things up? To me that sounds hard for the compiler to do heuristically but a Haskell compiler should still have more scope to do optimizations like that than a C compiler has.
- vmchale 8y ago
  Haskell is call-by-need so you get guarantees you wouldn't otherwise. It's not the same as memoization but it gives you what you want in any case.

gnulinux 8y ago

Why do we need language level memorization again? In python memoizing a function is just one line `@lru_cache()` I can't see why this needs an improvement by adding yet another thing to the core language.

thaunatos 8y ago
Just adding a @lru_cache() to a python isn't guaranteed to be correct; for example, if you're reading from an API the response could change between calls. Skip tracks side effects, and will either (a) memoize automatically a pure function or (b) recognize that a function is impure and avoid the memoization.
ulucs 8y ago
Some time ago, facebook introduced a javascript compiler which pre-compiled intermediate values. I think the point was to extend the spirit to the backend apps. If memoization is first class, implementing pre-compilation should be a blast

vmchale 8y ago

> I do not think that the naive recursive Fibonacci is a useful benchmark in any way though, it's a way too pessimized implementation. probably, but I would still like to see more benchmarks that use recursion. It's a fundamental technique from functional programming and so few benchmarks bother with it at all.