5 ms·

I'm posting this as a top-level comment, but it's really a reply to the discussion downthread about compilers being able to work magic if we let them. Better st

I'm posting this as a top-level comment, but it's really a reply to the discussion downthread about compilers being able to work magic if we let them. Better still, why not help them? Something I took for granted for the longest time about Haskell (which remains the only language I know of with the feature) is the ability to write user-defined "rewrite rules". You can say, "okay, GHC, I know for a fact that if I use these functions in such-and-such way, you can replace it by this instead". {-# RULES foo x (bar x) = superOptimizedFooBar x #-} A rule like this would be based on the programmer's knowledge of FooBar theory, which tells her that such an equality holds. The compiler hasn't studied lax monoidal FooBaroids and cannot be expected to infer this on its own. :) Now, anywhere a user of this code writes something like foo [1,2,3] (bar [1,2,3]) the compiler will substitute superOptimizedFooBar [1,2,3] in its place. This is a nice way to bring the compiler "closer" to the programmer, and allow the library author to integrate domain-specific knowledge into the compiler's optimizations. You can also "specialize" by using faster implementations in certain cases. For example, timesFour :: Num a => a -> a timesFour = a + a + a + a timesFourInt :: Int -> Int timesFourInt x = rightShift x 2 {-# RULES timesFour :: Int -> Int = timesFourInt #-} If you call timesFour on a double, it will use addition (ha!) but using it on an Int uses bitshifting instead because this rule fires. High-performance Haskell libraries like vector, bytestring, text, pipes, or conduit capitalize on this feature, among other techniques. When compiling code written using libraries like this, this is how it goes: - rule #1 fires somewhere - it rewrites the code into something that matches rule #2, "clearing the way" for it to fire - rule #2 fires - rule #3 fires - rule #1 fires again - rule #4 fires and so on, triggering a "cascade" of optimizations. The promise of Haskell is that we already have a "sufficiently smart compiler": today, with good libraries, GHC is capable of turning clear, high-level, reusable functional code with chains of function compositions and folds and so on into tight, fast loops. -- I must add, though, that getting rewrite rules to fire in cascades to get "mad gainz" requires one to grok how the GHC inliner/specializer works. http://mpickering.github.io/posts/2017-03-20-inlining-and-specialisation.html http://mpickering.github.io/posts/2017-03-20-inlining-and-sp... Data.Vector also utilizes an internal representation that makes fusion explicit and hence predictable (inevitable, even) called a "bundle": https://www.stackage.org/haddock/lts-8.16/vector-0.11.0.0/Data-Vector-Fusion-Bundle.html https://www.stackage.org/haddock/lts-8.16/vector-0.11.0.0/Da... but this relies on rewrite rules too, e.g. the previous module contains this rule: {-# RULES "zipWithM xs xs [Vector.Stream]" forall f xs. zipWithM f xs xs = mapM (\x -> f x x) xs #-}

egeozcan 9y ago
I wonder if there will be a time we start seeing this with Javascript transpilers(JS->JS), which are normally used to bring feature parity and compatibility to runtimes but starting to get obsolete as the runtimes catch-up. For example let x = (await grabSomeIntegers()).map(double).filter(biggerThan(3)).map(substract(1)); can be optimized automatically to use a single loop but one can rewrite it to be even faster (even though insignificantly, in this trivial example) because you know they will be integers. But then you let go of the DRY. How do Haskell library authors deal with that?
- mrkgnao 9y ago
  In Haskell your example would look like x = do ints <- grabSomeIntegers return (ints & map (*2) & filter (> 3) & map (-1)) (where x & f = f x) which the compiler desugars into something like x = fmap (map (- 1) . filter (> 3) . map (* 2)) grabSomeIntegers Now the compiler can very well perform optimizations on the big composed function. Even then, as you say, this has its limits: polymorphic/DRY code still suffers a performance penalty because it has to work the same way with all allowed inputs. ... right? Nope, that doesn't have to be the case: Haskell supports more than just your $grandparent's parameterized types! The vector package uses something called data families to have different in-memory representations for vectors of different types, without "letting go of the DRY" at all. https://www.stackage.org/haddock/lts-8.15/vector-0.11.0.0/src/Data.Vector.Unboxed.Base.html#Vector https://www.stackage.org/haddock/lts-8.15/vector-0.11.0.0/sr... Here, Vector a is a data family: how a value of type Vector a "looks" in memory depends on a. So you'll notice a bunch of lines of the form newtype instance Vector Int16 = MV_Int16 (P.Vector Int16) What this means is "if we have a vector of values of type Int16, use a primitive vector (essentially a raw array) to represent it in memory". (P is an alias for the Data.Vector.Primitive module.) Now I can write code that uses the beautiful user-facing API of vector: https://www.stackage.org/haddock/lts-8.16/vector-0.11.0.0/Data-Vector-Generic.html#v:length https://www.stackage.org/haddock/lts-8.16/vector-0.11.0.0/Da... Written using vectors, code like in your example is perfectly DRY; it would look like (this is untested code!) this: combobulate :: Num a => IO (Vector a) -> IO (Vector a) combobulate = do as <- grabSomeIntegersFromNetwork return (ints & V.map (*2) & V.filter (> 3) & V.map (-1)) and under the hood, whenever I use a Vector Animal[0], it uses whatever fast general-purpose array implementation is available, but the moment I call this with a vector of Int16 or Bool or Complex Double, it switches to the fast implementations in the Primitive/Internal modules. The key is the data families: the types expose a simple, consistent API, hiding the actual guts of the memory representation from the user. The library author is free to perform whatever ugly/evil/unsafe manipulations she feels like behind the scenes on the internal representations, or not. [0] Defining numeric operations on animals is left as an exercise to the careful reader.

egeozcan 9y ago

I wonder if there will be a time we start seeing this with Javascript transpilers(JS->JS), which are normally used to bring feature parity and compatibility to runtimes but starting to get obsolete as the runtimes catch-up. For example let x = (await grabSomeIntegers()).map(double).filter(biggerThan(3)).map(substract(1)); can be optimized automatically to use a single loop but one can rewrite it to be even faster (even though insignificantly, in this trivial example) because you know they will be integers. But then you let go of the DRY. How do Haskell library authors deal with that?

mrkgnao 9y ago
In Haskell your example would look like x = do ints <- grabSomeIntegers return (ints & map (*2) & filter (> 3) & map (-1)) (where x & f = f x) which the compiler desugars into something like x = fmap (map (- 1) . filter (> 3) . map (* 2)) grabSomeIntegers Now the compiler can very well perform optimizations on the big composed function. Even then, as you say, this has its limits: polymorphic/DRY code still suffers a performance penalty because it has to work the same way with all allowed inputs. ... right? Nope, that doesn't have to be the case: Haskell supports more than just your $grandparent's parameterized types! The vector package uses something called data families to have different in-memory representations for vectors of different types, without "letting go of the DRY" at all. https://www.stackage.org/haddock/lts-8.15/vector-0.11.0.0/src/Data.Vector.Unboxed.Base.html#Vector https://www.stackage.org/haddock/lts-8.15/vector-0.11.0.0/sr... Here, Vector a is a data family: how a value of type Vector a "looks" in memory depends on a. So you'll notice a bunch of lines of the form newtype instance Vector Int16 = MV_Int16 (P.Vector Int16) What this means is "if we have a vector of values of type Int16, use a primitive vector (essentially a raw array) to represent it in memory". (P is an alias for the Data.Vector.Primitive module.) Now I can write code that uses the beautiful user-facing API of vector: https://www.stackage.org/haddock/lts-8.16/vector-0.11.0.0/Data-Vector-Generic.html#v:length https://www.stackage.org/haddock/lts-8.16/vector-0.11.0.0/Da... Written using vectors, code like in your example is perfectly DRY; it would look like (this is untested code!) this: combobulate :: Num a => IO (Vector a) -> IO (Vector a) combobulate = do as <- grabSomeIntegersFromNetwork return (ints & V.map (*2) & V.filter (> 3) & V.map (-1)) and under the hood, whenever I use a Vector Animal[0], it uses whatever fast general-purpose array implementation is available, but the moment I call this with a vector of Int16 or Bool or Complex Double, it switches to the fast implementations in the Primitive/Internal modules. The key is the data families: the types expose a simple, consistent API, hiding the actual guts of the memory representation from the user. The library author is free to perform whatever ugly/evil/unsafe manipulations she feels like behind the scenes on the internal representations, or not. [0] Defining numeric operations on animals is left as an exercise to the careful reader.