×
all 24 comments

[–]edwardkmett 21 points22 points  (9 children)

Let's take your suggestion:

If you implement a number type like

newtype Mod = Mod { runMod :: Int -> Int }

instance Num Mod where
  Mod f + Mod g = Mod $ \m -> (f m + g m) `mod` m
  Mod f * Mod g = Mod $ \m -> (f m * g m) `mod` m      
...

then you get a problem if you go to call a function like

 (^) :: Mod -> Int -> Mod

Why?

Internally it calls * with the same arguments recursively to square its way toward its goal.

So you get

 x2 = x*x
 x4 = x2*x2
 x8 = x4*x4
 x16 = x8*x8
 ...
 x256 = x128*x128

That involves 8 multiplications right?

Well, in the "reader-like" version it involves 256!

Each * is sharing 'functions' but that doesn't share the answer to the functions for m!

  x2 m = x m * x m
  x4 m = x2 m * x2 m
  ...

It doesn't have any opportunity to spot the common sub-expressions there, because (^) was written polymorphically in the number type a decade or two ago by Lennart -- it knows nothing about Mod -- so even if it was smart enough to CSE, which generally isn't a good idea in Haskell, it is robbed of the opportunity by separate compilation.

We need a way to tell GHC 'we're always going to pass you the same m, so its safe for you to lift m out of all the lambdas, and share all the results.

 newtype Mod s = Mod Int 

is clearly a concrete value, not a function.

instance Reifies s Int => Num (Mod s) where
   Mod n + Mod n = (m + n) `mod` reflect (Proxy :: Proxy s)

is going out into the environment to grab the instance, but that instance will lift out as far as it can from lambdas and the like.

GHC can know that every time it 'calls a function'

 Reifies s Int => y

that it will get the same dictionary for Reifies s Int, this makes it sound for it to move that out a far as it wants.

Really, anything that takes a constraint is really a function from that constraint, but GHC has a great deal more freedom in moving those around in your code than it does actual function arguments.

[–]gridaphobe 2 points3 points  (8 children)

Why is is not a good idea to perform CSE in Haskell?

I'm guessing the answer has something to do with laziness, but that doesn't quite make sense. In fact, you could think of call-by-need as call-by-name + CSE.

[–]edwardkmett 14 points15 points  (5 children)

Lifting things out of lambdas can drastically increase their lifetimes compared to what you expect.

Sometimes things in memory are cheaper to recompute than to hold onto. Sometimes holding onto something (like a function) doesn't actually let you compute the answer to the function at specific arguments any faster, so the reference to the particular variant of a function closure is just wasting space.

When I have multiple uses of a thing I lose fusion opportunities that may have exceeded the gain from the shared structure, etc.

There are several different problems that all add up to it being a dicey proposition.

As a result I just write all my code as CSE'd as I can by hand, that way I can remove as much potential for things to go wrong as possible. and can -fno-cse whenever the compiler starts going wrong.

CSE also can do strange things to NOINLINEd chunks of code.

I'm somewhat saddened by all of this because it is part of what I think makes a sufficiently smart compiler sufficiently smart.

[–]NiftyIon[S] 7 points8 points  (2 children)

Thanks a ton for the replies. Incredibly helpful.

Could a sufficiently smart compiler generate both CSE'd and non-CSE'd versions of code and decide dynamically based on runtime properties (size of the data structure?) which one to use?

[–]edwardkmett 8 points9 points  (0 children)

No idea. Sounds like you have a research project. ;)

[–]willIEverGraduate 1 point2 points  (0 children)

Profile-guided optimization might be applicable here.

[–]gridaphobe 1 point2 points  (1 child)

Thanks!

These are all reasonable objections to CSE, but none of them seem particularly specific to Haskell. They do, however, seem to be (somewhat) connected to higher-order functions, which makes me wonder if the ML-style languages do CSE.

[–]edwardkmett 1 point2 points  (0 children)

I think the main issue is that thunks can be a lot harder to reason about in terms of lifespan than the usual strict values. e.g. Region based collection works pretty well in strict languages, but is more or less useless for a call-by-need language.

[–]htebalaka 5 points6 points  (0 children)

You can cause space leaks. If you have some expression ... f a ... f a ... and replace it with let x = f a in ... x ... x ... then you have to hold onto x until it's been used in all occurences in ... x ... x ..., which might not be wise if x is very large.

[–]fridofrido 4 points5 points  (0 children)

A very simple example is the following two implementations of the power set (well, power list) function.

No CSE (unless GHC accidentally gets too clever, which can happen sometimes...):

powerSet :: [a] -> [[a]]
powerSet []     = [[]]
powerSet (x:xs) = powerSet xs ++ map (x:) (powerSet xs)

versus manual CSE:

powerSet' :: [a] -> [[a]]
powerSet' []     = [[]]
powerSet' (x:xs) = let tmp = powerSet' xs in tmp ++ map (x:) tmp

Now length . powerSet runs in constant memory, while length . powerSet' blows up, even though it's much faster.

[–]htebalaka 9 points10 points  (2 children)

I found reflection easier to understand by looking at the Given typeclass rather than the Refies class (Given is simpler, but I think occasionally less well behaved). Then we can implement the following:

implicit :: (a -> b) -> (Given a => b)
implicit f = f given
explicit :: (Given a => b) -> a -> b
explicit a b = give b a

Aside from the performance issues edward mentions there are some interfaces that you simply can't implement with Reader that you can with reflection. For instance, try to implement Eq for a Reader-based modulo number. The best you could do is liftA2 (==), but that would return a -> Bool, while you need Bool. But with reflection you can move the fact that you're returning a function out of the type signature into the instance context, so you have:

newtype Mod a = Mod a
instance (Given a, Integral a) => Eq (Mod a) where
    Mod a == Mod b = normalize a == normalize b
      where normalize a = a `mod` given

You don't even really need a Given constraint for Eq; if you move the Given constraint into the various Num methods you can make sure that you can't construct an un-normalized modulo number, in which case we already know it's normalized when we try to equate two Mod values.

With the actual Reifies class we can also guarantee that we can't equate a modulo 8 number with a modulo 16 number; the extra phantom type parameter makes numbers in different modulos have different types. We can also provide an Ord instance similarly, which means we can construct Maps which use modulo-numbers as keys, which we can't do with Reader (I think this is only safe with Reifies, not Given).

A while back I was experimenting with aping imperative syntax with lenses to write code that's polymorphic over whether or not you're in a monad, so you could do things like:

while ((!x) < 10) $ do
    y =: foo (!x) + (!y)
    x =: (!x) + 1

Where anything to the right of (=:), or in the while-loops condition were given read-only access to the state monad's state. Without reflection the best I would have managed would be something like:

while (fmap (<10) (view x)) $ do
    y =: ((+) <$> fmap foo (view x) <*> view y)
    x =: ((+) <$> view x <*> pure 1)

Even adding instance (Num a) => Num (Reader r a) would only help for code that's polymorphic over Num. In the general case you have to constantly liftA2/pure/fmappure functions to work over the Reader monad, whereas the reflection-based interface does so automatically.

http://lpaste.net/139394 has the implementation if anyone's curious.

[–]tel 6 points7 points  (1 child)

Given provides a cute, direct interpretation of reflection: it lets you turn (->) into (=>) and visa versa.

[–]htebalaka 2 points3 points  (0 children)

Yeah, GHC will rewrite implicit :: Given a => (a -> b) -> b, but I think putting the constraint to the right of the function argument makes it clearer.

[–]Tekmo 10 points11 points  (9 children)

I think you can also use the reflection package to dynamically generate localized type class instances parametrized on runtime values. See this example

[–]edwardkmett 6 points7 points  (4 children)

This was exactly why I wrote the package.

I had a DFA lying around as a value in Haskell.

I wanted a monoid that represented tabulations of that DFA: where it took values as you applied it to certain inputs. This is representable as an array of n items given a DFA with n states.

But I wanted the type system to prevent me from wiring up tabulations from two different DFAs.

With reflection this was easy.

[–]rpglover64 1 point2 points  (3 children)

Do you have this as example code somewhere?

[–]edwardkmett 0 points1 point  (2 children)

Not really.

[–]rpglover64 0 points1 point  (1 child)

That's a shame.

[–]edwardkmett 3 points4 points  (0 children)

It was rather peculiar to the problem I was solving.

http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html

is an implementation of the idea without reflection.

Just take your DFA, reflect it, and use arrays of size equal to the number of elements instead of the 'Table' that Dan uses there.

[–]deltaSquee 2 points3 points  (3 children)

Yup, that's what I used it for. It's amazing for that.

[–]sambocyn 0 points1 point  (2 children)

can you go in to more detail about how you used it?

[–]aaronlevin 5 points6 points  (0 children)

I accidentally stumbled on some of the design ideas behind reflection when I was trying to store types in JSON strings, which I wrote up in this blog post: Using Data.Proxy to Encode Types in Your JSON.

I found writing that blog post helpful to understand reflection. Perhaps it'll be helpful reading it.