5 ms·

> has poor support for numerical computing. The issue comes from being lazy by default. When you are writing lazy functional code, you essentially build up a

by spott 9y ago

> has poor support for numerical computing. The issue comes from being lazy by default. When you are writing lazy functional code, you essentially build up a system of thunks[0] that collapse to a value when you need it. This works great for abstractions like infinite lists, or essentially only paying for the value you need. Unfortunately, they are kind of expensive (I believe they are usually implemented as a tagged union, where they are either a value that is returned immediately or a pointer to another function or thunk) when you don't need the laziness. In any sort of numerical computing, you are usually dealing with enough values that you lose a lot of performance when dealing with these thunks. Working around this is doable with a bunch of strict annotations (so that these thunks are immediately collapsed to values), but that is only half the battle: you still need to reduce the immutable function applications to a mutable version so you don't lose out by copying your values back and forth in memory, and you don't do a bunch of unnecessary calculations. All this requires "a sufficiently intelligent compiler" or a lot of compiler hints and peering into Core: the intermediate language of GHC. It isn't for the faint of heart. There have been a bunch of work on avoiding some of this: hmatrix[1] is a lapack and blas library for finally doing the calculations once you have reduced the graph, "subhask"[2] is a standard library for Haskell that attempts to add some support for basic numerical work and "numerical"[3] is a library that I believe is trying to make a well typed linear algebra library (I'm not sure if it is going to call into hmatrix/blas/lapack or not). The issue with a lot of this is that until there are good tools for this kind of thing, no-one does serious numerical programming in Haskell, and there are only a few people working on the tooling because there aren't that many people trying to do serious numerical programming in Haskell. (note: I'm not an expert in this, so don't depend on any of this for love or money. I'm sure someone will come along and tell me how I'm wrong.) [0] https://en.wikipedia.org/wiki/Thunk https://en.wikipedia.org/wiki/Thunk, https://wiki.haskell.org/Thunk https://wiki.haskell.org/Thunk [1] http://hackage.haskell.org/package/hmatrix http://hackage.haskell.org/package/hmatrix [2] https://github.com/mikeizbicki/subhask https://github.com/mikeizbicki/subhask [3] https://github.com/wellposed/numerical https://github.com/wellposed/numerical

aseipp 9y ago
I think the problem the author of HLearn and SubHask faced isn't really so much of a problem with thunking or whatever. Compiler optimizations and whatnot are always great and avoiding indirection is good (it's also not super hard either to do it manually for 99% of cases). But rather, I believe the problem they were hinting at is that the current Haskell numeric hierarchy is insufficient to capture the patterns we want for the vast kinds of numerical computing we do today. But even then, the tools we need to design the hierarchy we do want are also a bit out of reach, and implementing them will take time. SubHask for example uses hmatrix and other LAPACK/BLAS libraries under the hood, which is good of course -- but almost all of the actual work in SubHask, then, is around designing a reusable hierarchy that works for all the 'weird' cases you find with this domain. Even 'non weird' things like rank/dimension polymorphic products, etc, require a lot of type-level infrastructure to accomplish today, and the features to support that are constantly evolving. (An example of APL-style rank-polymorphic stuff I typed up recently can give you an idea of how much work it is to do some 'seemingly trivial' things, though the examples at the end are rather nice[1]) SubHask also has an extremely fine grained hierarchy, with lots of little classes to handle cases like "weird containers" with appropriate laws -- and figuring that out is a lot of work too. Haskell's type system is getting more expressive all the time, so hopefully this will become less tiresome in the future, and iterating and honing the design will be far simpler. But getting the design right is much more important and the other stuff (better underlying numeric libraries, improved performance, etc) can come after. I think you're spot on that the lack of attention here creatives a negative feedback loop, as well. Another example of this I think that was bad was that very little code took into account things like numerical stability of algorithms. The SubHask/HLearn author also tried tackling this in an interesting way, too[2]. [1] https://gist.github.com/thoughtpolice/c408773f43972e48f93377ce3e4f441f https://gist.github.com/thoughtpolice/c408773f43972e48f93377... [2] https://github.com/mikeizbicki/HerbiePlugin https://github.com/mikeizbicki/HerbiePlugin
- spott 9y ago
  >But rather, I believe the problem they were hinting at is that the current Haskell numeric hierarchy is insufficient to capture the patterns we want for the vast kinds of numerical computing we do today. But even then, the tools we need to design the hierarchy we do want are also a bit out of reach, and implementing them will take time. I think part of this issue boils down to avoiding the laziness and immutability of the language. The "patterns we want for [...] numerical computing" not infrequently boil down to (a) build a matrix, (b) modify that matrix, (c) apply that matrix, or parts of that matrix, on vectors, (d) modify vectors, (e) partition matrices into submatrices to do work on, etc. Notice the "modify" part of so many of these. These aren't really hard problems in imperative languages. The naive algorithm for Arnoldi iteration[0] is inherently iterative and really isn't that hard to write with ok performance in an imperative language... but try writing it naively in a functional language! So, tools and abstractions need to be built to make these kinds of algorithms more natural to write functionally without costing too much in performance. In other words: the tools and abstractions are only necessary because of the limitations of a language that leans so hard on the compiler for performance. I think this is one of the underlying things that differentiate Haskell and other languages: In Haskell, abstractions can be absurdly reusable, allowing for really elegant code to do things... if you know what abstraction to use. If you don't, then things can get difficult to do. In imperative languages, abstractions can't quite reach the level of reusability that they can in Haskell... but you don't have to rely on the abstractions as much to solve the problems that you want to solve. Think about the Arnoldi iteration. The iterative version in a number of languages is 10 lines, but the functional version needs some way of drilling down into an array in a mutable way (a monad) in order to make it match the iterative in performance... [0]https://en.wikipedia.org/wiki/Arnoldi_iteration#The_Arnoldi_iteration https://en.wikipedia.org/wiki/Arnoldi_iteration#The_Arnoldi_...
w4rh4wk5 9y ago
May I ask, do you have any useful references on how to write strict, efficient Haskell code. Or at least some Do/Don'ts?
- spott 9y ago
  I don't. I learned all this while trying my own hand[0] at writing a sparse matrix library in Haskell and running into some of these issues. Unfortunately, I mostly gave up. [0]https://xkcd.com/1831/ https://xkcd.com/1831/
zygomega 9y ago
The author addresses the potential benefits of immutability and laziness in a note on cover trees[0]. Last time I checked, this is still the world's fastest NN algorithm. Haskell could shine in numerical computing. I think the key is polymorphism: a vector is a matrix is a tensor is a number, and they can all be multiplied in the same way, once you define what multiply is. Poor support is more about the lack of haskell coders doing ML. It's hard to compete without the numbers that other platforms enjoy. [0] https://izbicki.me/blog/fast-nearest-neighbor-queries-in-haskell.html https://izbicki.me/blog/fast-nearest-neighbor-queries-in-has...
- eli_gottlieb 9y ago
  I think it's more about ML experts not learning Haskell. "Haskell programmers" and "PL experts" are tightly overlapping groups, but almost no other major cluster of experts overlaps with those.
willtim 9y ago
Laziness never prevented high-performance array libraries like Vector being implemented. GHC Haskell also now has a module-level pragma that turns on strict-by-default. Python typically doesn't implement any high-performance primitives anyway, it simply delegates to C/Fortran. Something Haskell could do equally well.

by spott 9y ago

aseipp 9y ago

I think the problem the author of HLearn and SubHask faced isn't really so much of a problem with thunking or whatever. Compiler optimizations and whatnot are always great and avoiding indirection is good (it's also not super hard either to do it manually for 99% of cases). But rather, I believe the problem they were hinting at is that the current Haskell numeric hierarchy is insufficient to capture the patterns we want for the vast kinds of numerical computing we do today. But even then, the tools we need to design the hierarchy we do want are also a bit out of reach, and implementing them will take time. SubHask for example uses hmatrix and other LAPACK/BLAS libraries under the hood, which is good of course -- but almost all of the actual work in SubHask, then, is around designing a reusable hierarchy that works for all the 'weird' cases you find with this domain. Even 'non weird' things like rank/dimension polymorphic products, etc, require a lot of type-level infrastructure to accomplish today, and the features to support that are constantly evolving. (An example of APL-style rank-polymorphic stuff I typed up recently can give you an idea of how much work it is to do some 'seemingly trivial' things, though the examples at the end are rather nice[1]) SubHask also has an extremely fine grained hierarchy, with lots of little classes to handle cases like "weird containers" with appropriate laws -- and figuring that out is a lot of work too. Haskell's type system is getting more expressive all the time, so hopefully this will become less tiresome in the future, and iterating and honing the design will be far simpler. But getting the design right is much more important and the other stuff (better underlying numeric libraries, improved performance, etc) can come after. I think you're spot on that the lack of attention here creatives a negative feedback loop, as well. Another example of this I think that was bad was that very little code took into account things like numerical stability of algorithms. The SubHask/HLearn author also tried tackling this in an interesting way, too[2]. [1] https://gist.github.com/thoughtpolice/c408773f43972e48f93377ce3e4f441f https://gist.github.com/thoughtpolice/c408773f43972e48f93377... [2] https://github.com/mikeizbicki/HerbiePlugin https://github.com/mikeizbicki/HerbiePlugin

spott 9y ago
>But rather, I believe the problem they were hinting at is that the current Haskell numeric hierarchy is insufficient to capture the patterns we want for the vast kinds of numerical computing we do today. But even then, the tools we need to design the hierarchy we do want are also a bit out of reach, and implementing them will take time. I think part of this issue boils down to avoiding the laziness and immutability of the language. The "patterns we want for [...] numerical computing" not infrequently boil down to (a) build a matrix, (b) modify that matrix, (c) apply that matrix, or parts of that matrix, on vectors, (d) modify vectors, (e) partition matrices into submatrices to do work on, etc. Notice the "modify" part of so many of these. These aren't really hard problems in imperative languages. The naive algorithm for Arnoldi iteration[0] is inherently iterative and really isn't that hard to write with ok performance in an imperative language... but try writing it naively in a functional language! So, tools and abstractions need to be built to make these kinds of algorithms more natural to write functionally without costing too much in performance. In other words: the tools and abstractions are only necessary because of the limitations of a language that leans so hard on the compiler for performance. I think this is one of the underlying things that differentiate Haskell and other languages: In Haskell, abstractions can be absurdly reusable, allowing for really elegant code to do things... if you know what abstraction to use. If you don't, then things can get difficult to do. In imperative languages, abstractions can't quite reach the level of reusability that they can in Haskell... but you don't have to rely on the abstractions as much to solve the problems that you want to solve. Think about the Arnoldi iteration. The iterative version in a number of languages is 10 lines, but the functional version needs some way of drilling down into an array in a mutable way (a monad) in order to make it match the iterative in performance... [0]https://en.wikipedia.org/wiki/Arnoldi_iteration#The_Arnoldi_iteration https://en.wikipedia.org/wiki/Arnoldi_iteration#The_Arnoldi_...

w4rh4wk5 9y ago

May I ask, do you have any useful references on how to write strict, efficient Haskell code. Or at least some Do/Don'ts?

spott 9y ago
I don't. I learned all this while trying my own hand[0] at writing a sparse matrix library in Haskell and running into some of these issues. Unfortunately, I mostly gave up. [0]https://xkcd.com/1831/ https://xkcd.com/1831/

zygomega 9y ago

The author addresses the potential benefits of immutability and laziness in a note on cover trees[0]. Last time I checked, this is still the world's fastest NN algorithm. Haskell could shine in numerical computing. I think the key is polymorphism: a vector is a matrix is a tensor is a number, and they can all be multiplied in the same way, once you define what multiply is. Poor support is more about the lack of haskell coders doing ML. It's hard to compete without the numbers that other platforms enjoy. [0] https://izbicki.me/blog/fast-nearest-neighbor-queries-in-haskell.html https://izbicki.me/blog/fast-nearest-neighbor-queries-in-has...

eli_gottlieb 9y ago
I think it's more about ML experts not learning Haskell. "Haskell programmers" and "PL experts" are tightly overlapping groups, but almost no other major cluster of experts overlaps with those.

willtim 9y ago

Laziness never prevented high-performance array libraries like Vector being implemented. GHC Haskell also now has a module-level pragma that turns on strict-by-default. Python typically doesn't implement any high-performance primitives anyway, it simply delegates to C/Fortran. Something Haskell could do equally well.