The monomorphism restriction and mhs

[arossato]

The practical advantages of the monomorphism restriction can be illustrated, I believe, by the following example:

import Debug.Trace (trace)

fib :: (Eq t, Num t, Num a) => t -> a
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

tb = trace "eval tb" $ fib 27

test_lb :: Int
test_lb = let x = trace "eval x" (fib 27) in x + x + x + x

main = do
  print (tb + tb + tb + tb)
  print test_lb

Running this will produce:

$ runghc -XMonomorphismRestriction mr.test.hs
eval tb
785672
eval x
785672

$ runghc -XNoMonomorphismRestriction mr.test.hs
eval tb
eval tb
eval tb
eval tb
785672
eval x
eval x
eval x
eval x
785672

This default behavior can be changed with annotations: so tb :: forall a . Num a => a will lead to multiple evaluations with MR (which is on by default in ghc), while let (x :: Int) = ... will allow the sharing of x when MR is off (like in ghci). Even though I must confess I find more aesthetically pleasing the second approach, Haskell 2010 decided to go with the first one, apparently because, according to § 6.2 of "Being Lazy With Class", «Hughes argued strongly that it was unacceptable to silently duplicate computation in this way. His argument was motivated by a program he had written that ran exponentially slower than he expected»

mhs behaves differently:

mhs -r mr.test.hs
eval tb
eval tb
eval tb
eval tb
785672
eval x
785672

It generalizes function, pattern and simple top-level binds. I have reasons to believe this is driven by its architectural design: binds are grouped into strongly connected components, each group is independently type-checked, while the substitution map is reset at each iteration. This way all unification variables for each group can be garbage collected and the memory footprint limited.

One consequence of this design is that, if binds were not generalized, they would have to be immediately defaulted before tcResetis called, and that would lead to problems, as illustrated by this example:

constant = 1

f :: Int -> Int
f x = x + constant

This is a simplified version of what can be found in the package colour (Data.Colour.CIE.Chromaticity): constant, if not generalized, must be immediately defaulted to Integer (to allow for the SCC memory reset) before checking it at call site in f, which would lead to an unsatisfied constraint Int ~ Integer.

Lacking a module-wide substitution map Rule 2 of MR cannot be applied, and the generalization of top-level binds becomes a requirement. This is a concrete illustration:

import Data.Typeable

default Show (String)

myshow = show

main :: IO ()
main = print (typeOf myshow)

This will produce:

runghc-9.14 -XNamedDefaults -XExtendedDefaultRules test.hs
[Char] -> [Char]

But if we change the last line to:

main = print (typeOf myshow) >> putStrLn (myshow 42)

it would produce:

runghc-9.14 -XNamedDefaults -XExtendedDefaultRules test.hs
Integer -> [Char]
42

mhs instead produces:

mhs -r test.hs
[Char] -> [Char]
42

mhs generalizes myshow and instantiates it with different meta variables at each call site, defaulting the type at each occurrence.

I doubt that implementing a module-wide substitution map in order to avoid multiple evaluation of top-level binds would make sense given the spirit of `mhs. But still I thought it could be useful to point the problem.

Simple non-overloaded local binds

Locally, instead, mhs, after dropping MonoLocalBinds, generalizes only function binds.

So this works:

main =
  let f x = id x
  in print (f 5, f True)

and this does not:

main =
  let f = id
  in print (f 5, f True)

I created a branch for implementing the generalization of non-overloaded binds:

https://github.com/arossato/MicroHs/tree/monomorphism_restriction

And here the modifications can be seen

I think there are good reasons why this should be allowed:

data PolyBox = PolyBox
  { runPoly :: forall a. a -> a
  }

polyBox :: PolyBox
polyBox = PolyBox { runPoly = id }

testPoly :: (Int, Bool)
testPoly = let f = runPoly polyBox
           in (f 5, f True)

main = print testPoly

This seems (or seemed?) to introduce some confusion, though, since it may be difficult to immediately grasp why let f = id works while let forM = flip mapM, which is overloaded, is rejected. But, I believe, this would be coherent with the Haskell report and possibly complete the "allow generalization for local bindings" entry in the TODO.

[augustss]

Thanks! I will look at this when I have some time.

[augustss]

I've (finally) merged your PR. Thank you!