From [the docs][1] for GHC 7.6:

&gt; [Y]ou often don&#39;t even need the SPECIALIZE pragma in the first place. When compiling a module M, GHC&#39;s optimiser (with -O) automatically considers each top-level overloaded function declared in M, and specialises it for the different types at which it is called in M. The optimiser also considers each imported INLINABLE overloaded function, and specialises it for the different types at which it is called in M.

and

&gt; Moreover, given a SPECIALIZE pragma for a function f, GHC will automatically create specialisations for any type-class-overloaded functions called by f, if they are in the same module as the SPECIALIZE pragma, or if they are INLINABLE; and so on, transitively.

So GHC should automatically specialize [some/most/all(?)][2] functions marked `INLINABLE` *without* a pragma, and if I use an explicit pragma, the specialization is transitive. My question is: 
is the *auto*-specialization transitive?

Specifically, here&#39;s a small example:

Main.hs:

    import Data.Vector.Unboxed as U
    import Foo
    
    main =
        let y = Bar $ Qux $ U.replicate 11221184 0 :: Foo (Qux Int)
            (Bar (Qux ans)) = iterate (plus y) y !! 100
        in putStr $ show $ foldl1&#39; (*) ans

Foo.hs:

    module Foo (Qux(..), Foo(..), plus) where
    
    import Data.Vector.Unboxed as U
    
    newtype Qux r = Qux (Vector r)
    -- GHC inlines `plus` if I remove the bangs or the Baz constructor
    data Foo t = Bar !t
               | Baz !t
    
    instance (Num r, Unbox r) =&gt; Num (Qux r) where
        {-# INLINABLE (+) #-}
        (Qux x) + (Qux y) = Qux $ U.zipWith (+) x y
    
    {-# INLINABLE plus #-}
    plus :: (Num t) =&gt; (Foo t) -&gt; (Foo t) -&gt; (Foo t)
    plus (Bar v1) (Bar v2) = Bar $ v1 + v2

GHC specializes the call to `plus`, but does *not* specialize `(+)` in the `Qux` `Num` instance which kills performance. 

However, an explicit pragma 
 
    {-# SPECIALIZE plus :: Foo (Qux Int) -&gt; Foo (Qux Int) -&gt; Foo (Qux Int) #-}

results in *transitive* specialization as the docs indicate, so `(+)` is specialized and the code is 30x faster (both compiled with `-O2`). Is this expected behavior? Should I only expect `(+)` to be specialized transitively with an explicit pragma?

----
**UPDATE**

The docs for 7.8.2 haven&#39;t changed, and the behavior is the same, so this question is still relevant.


  [1]: http://www.haskell.org/ghc/docs/7.6.3/html/users_guide/pragmas.html#idp49866112
  [2]: https://stackoverflow.com/questions/21071706/specialization-with-constraints

Transitivity of Auto-Specialization in GHC

I&#39;m beginning to understand how the `forall` keyword is used in so-called &quot;existential types&quot; like this:

    data ShowBox = forall s. Show s =&gt; SB s

This is only a subset, however, of how `forall` is used and I simply cannot wrap my mind around its use in things like this:

    runST :: forall a. (forall s. ST s a) -&gt; a

Or explaining why these are different:

    foo :: (forall a. a -&gt; a) -&gt; (Char, Bool)
    bar :: forall a. ((a -&gt; a) -&gt; (Char, Bool))

Or the whole `RankNTypes` stuff...

I tend to prefer clear, jargon-free English rather than the kinds of language which are normal in academic environments.  Most of the explanations I attempt to read on this (the ones I can find through search engines) have these problems:

 1. They&#39;re incomplete.  They explain one part of the use of this keyword (like &quot;existential types&quot;) which makes me feel happy until I read code that uses it in a completely different way (like `runST`, `foo` and `bar` above).
 2. They&#39;re densely packed with assumptions that I&#39;ve read the latest in whatever branch of discrete math, category theory or abstract algebra is popular this week.  (If I never read the words &quot;consult the paper *whatever* for details of implementation&quot; again, it will be too soon.)
 3. They&#39;re written in ways that frequently turn even simple concepts into tortuously twisted and fractured grammar and semantics.

So...

On to the actual question.  Can anybody completely explain the `forall` keyword in clear, plain English (or, if it exists somewhere, point to such a clear explanation which I&#39;ve missed) that doesn&#39;t assume I&#39;m a mathematician steeped in the jargon?

-----

*Edited to add:*

There were two stand-out answers from the higher-quality ones below, but unfortunately I can only choose one as best.  [Norman&#39;s answer](https://stackoverflow.com/questions/3071136/what-does-the-forall-keyword-in-haskell-ghc-do/3071365#3071365) was detailed and useful, explaining things in a way that showed some of the theoretical underpinnings of `forall` and at the same time showing me some of the practical implications of it.  [yairchu&#39;s answer](https://stackoverflow.com/questions/3071136/what-does-the-forall-keyword-in-haskell-ghc-do/3071932#3071932) covered an area nobody else mentioned (scoped type variables) and illustrated all of the concepts with code and a GHCi session.  Were it possible to select both as best, I would.  Unfortunately I can&#39;t and, after looking over both answers closely, I&#39;ve decided that yairchu&#39;s slightly edges out Norman&#39;s because of the illustrative code and attached explanation.  This is a bit unfair, however, because really I needed both answers to understand this to the point that `forall` doesn&#39;t leave me with a faint sense of dread when I see it in a type signature.

What does the `forall` keyword in Haskell/GHC do?

Here&#39;s the scenario: I&#39;ve written some code with a type signature and GHC complains could not deduce x ~ y for some `x` and `y`. You can usually throw GHC a bone and simply add the isomorphism to the function constraints, but this is a bad idea for several reasons:

  1. It does not emphasize understanding the code.
  2. You can end up with 5 constraints where one would have sufficed (for example, if the 5 are implied by one more specific constraint)
  3. You can end up with bogus constraints if you&#39;ve done something wrong or if GHC is being unhelpful

I just spent several hours battling case 3. I&#39;m playing with [`syntactic-2.0`][1], and I was trying to define a domain-independent version of `share`, similar to the version defined in [`NanoFeldspar.hs`][2].

I had this:

    {-# LANGUAGE GADTs, FlexibleContexts, TypeOperators #-}
    import Data.Syntactic
    
    -- Based on NanoFeldspar.hs
    data Let a where
        Let :: Let (a :-&gt; (a -&gt; b) :-&gt; Full b)

    share :: (Let :&lt;: sup,
              Domain a ~ sup,
              Domain b ~ sup,
              SyntacticN (a -&gt; (a -&gt; b) -&gt; b) fi) 
          =&gt; a -&gt; (a -&gt; b) -&gt; a
    share = sugarSym Let

and GHC `could not deduce (Internal a) ~ (Internal b)`, which is certainly not what I was going for. So either I had written some code I didn&#39;t intend to (which required the constraint), or GHC wanted that constraint due to some other constraints I had written.

It turns out I needed to add `(Syntactic a, Syntactic b, Syntactic (a-&gt;b))` to the constraint list, none of which imply `(Internal a) ~ (Internal b)`. I basically stumbled upon the correct constraints; I still don&#39;t have a systematic way to find them.

My questions are:

  1. Why did GHC propose that constraint? Nowhere in syntactic is there a constraint `Internal a ~ Internal b`, so where did GHC pull that from?
  2. In general, what techniques can be used to trace the origin of a constraint which GHC believes it needs? Even for constraints that I *can* discover myself, my approach is essentially brute forcing the offending path by physically writing down recursive constraints. This approach is basically going down an infinite rabbit hole of constraints and is about the least efficient method I can imagine.

  [1]: https://hackage.haskell.org/package/syntactic-2.0
  [2]: https://github.com/emilaxelsson/syntactic/blob/2.0/examples/NanoFeldspar.hs

Techniques for Tracing Constraints

Haskell (with the `GHC` compiler) is a [lot faster than you&#39;d expect][1]. Used correctly, it can get close-ish to low-level languages. (A favorite thing for Haskellers to do is to try and get within 5% of C (or even beat it, but that means you are using an inefficient C program, since GHC compiles Haskell to C).) My question is, why?

Haskell is declarative and based on lambda calculus. Machine architectures are clearly imperative, being based on turing machines, roughly. Indeed, Haskell doesn&#39;t even have a specific evaluation order. Also, instead of dealing with machine data types, you make algebraic data types all the time.

Weirdest of all though is higher order functions. You would think that creating functions on the fly, and throwing them around, would make a program slower. [But using higher order functions actually makes Haskell faster.][2] Indeed, it seems that, to optimize Haskell code, you need to make it more elegant and abstract instead of more machine-like. None of Haskell&#39;s more advanced features seem to even *affect* its performance, if they don&#39;t improve it.

Sorry if this is sounding ranty, but here is my question: **Why is Haskell (compiled with GHC) so fast, considering its abstract nature and differences from physical machines?**

Note: The reason I say C and other imperative languages are somewhat similar to Turing Machines (but not to the extent that Haskell is similar to Lambda Calculus) is that in an imperative language, you have a finite number of states (a.k.a. line number), along with a Tape (the ram), such that the state and the current tape determine what to do to the tape. See the Wikipedia entry, [Turing machine equivalents][0], for the transition from Turing Machines to computers.

  [0]: https://en.wikipedia.org/wiki/Turing_machine_equivalents
  [1]: https://wiki.haskell.org/Why_Haskell_matters#The_speed_of_Haskell
  [2]: https://hbtvl.wordpress.com/2015/12/14/efficient-parsing-of-large-text-files-part-4-and-conclusion/

Why is Haskell (GHC) so darn fast?

I&#39;ve recently posted a [question][1] about [syntactic-2.0][2] regarding the definition of `share`. I&#39;ve had this working in **GHC 7.6**:

    {-# LANGUAGE GADTs, TypeOperators, FlexibleContexts #-}
    
    import Data.Syntactic
    import Data.Syntactic.Sugar.BindingT
    
    data Let a where
        Let :: Let (a :-&gt; (a -&gt; b) :-&gt; Full b)
    
    share :: (Let :&lt;: sup,
              sup ~ Domain b, sup ~ Domain a,
              Syntactic a, Syntactic b,
              Syntactic (a -&gt; b),
              SyntacticN (a -&gt; (a -&gt; b) -&gt; b) 
                         fi)
               =&gt; a -&gt; (a -&gt; b) -&gt; b
    share = sugarSym Let

However, GHC 7.8 wants `-XAllowAmbiguousTypes` to compile with that signature. Alternatively, I can replace the `fi` with 

    (ASTF sup (Internal a) -&gt; AST sup ((Internal a) :-&gt; Full (Internal b)) -&gt; ASTF sup (Internal b))

which is the type implied by the fundep on `SyntacticN`. This allows me to avoid the extension. Of course this is 

 - a very long type to add to an already-large signature
 - tiresome to manually derive
 - unnecessary due to the fundep

My questions are:

  1. Is this an acceptable use of `-XAllowAmbiguousTypes`?
  2. In general, when should this extension be used? An answer [here][3] suggests &quot;it is almost never a good idea&quot;.
  3. Though I&#39;ve read [the docs][4], I&#39;m still having trouble deciding if a constraint is ambiguous or not. Specifically, consider this function from Data.Syntactic.Sugar:

        sugarSym :: (sub :&lt;: AST sup, ApplySym sig fi sup, SyntacticN f fi) 
                 =&gt; sub sig -&gt; f
        sugarSym = sugarN . appSym
    
   It appears to me that `fi` (and possibly `sup`) should be ambiguous here, but it compiles without the extension. Why is `sugarSym` unambiguous while `share` is? Since `share` is an application of `sugarSym`, the `share` constraints all come straight from `sugarSym`.


  [1]: https://stackoverflow.com/questions/23448150/techniques-for-tracing-constraints
  [2]: https://github.com/emilaxelsson/syntactic
  [3]: https://stackoverflow.com/questions/23461560/how-can-i-extract-this-polymorphic-recursion-function/23462397#23462397
  [4]: http://www.haskell.org/ghc/docs/7.8.2/html/users_guide/other-type-extensions.html#ambiguity

When is -XAllowAmbiguousTypes appropriate?

Core is GHC&#39;s intermediate language. Reading Core can help you better understand the performance of your program. Someone asked me for documentation or tutorials on reading Core, but I couldn&#39;t find much.

What documentation is available for reading GHC Core?

Here&#39;s what I&#39;ve found so far:

* [Write Haskell as fast as C: exploiting strictness, laziness and recursion][1]
* [Haskell as fast as C: working at a high altitude for low level performance][2]
* [RWH: Chapter 25. Profiling and optimization][3]
* [High-Performance Haskell talk at CUFP][4] (slide 65-80)

  [1]: http://donsbot.wordpress.com/2008/05/06/write-haskell-as-fast-as-c-exploiting-strictness-laziness-and-recursion/
  [2]: http://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-high-altitude-for-low-level-performance/
  [3]: http://book.realworldhaskell.org/read/profiling-and-optimization.html
  [4]: http://blog.johantibell.com/2010/09/slides-from-my-high-performance-haskell.html


Reading GHC Core

GHC has a lot of optimizations that it can perform, but I don&#39;t know what they all are, nor how likely they are to be performed and under what circumstances.

My question is: what transformations can I expect it to apply every time, or nearly so? If I look at a piece of code that&#39;s going to be executed (evaluated) frequently and my first thought is &quot;hmm, maybe I should optimize that&quot;, in which cases should my second thought be, &quot;don&#39;t even think about it, GHC got this&quot;?

I was reading the paper [Stream Fusion: From Lists to Streams to Nothing at All][1], and the technique they used of rewriting list processing into a different form which GHC&#39;s normal optimizations would then reliably optimize down into simple loops was novel to me. How can I tell when my own programs are eligible for that kind of optimization?

There&#39;s [some information][2] in the GHC manual, but it only goes part of the way towards answering the question.

EDIT: I&#39;m starting a bounty. What I would like is a list of lower-level transformations like lambda/let/case-floating, type/constructor/function argument specialization, strictness analysis and unboxing, worker/wrapper, and whatever else significant GHC does that I&#39;ve left out, along with explanations and examples of input and output code, and ideally illustrations of situations when the total effect is more than the sum of its parts. And ideally some mention of when transformations *won&#39;t* happen. I&#39;m not expecting novel-length explanations of every transformation, a couple of sentences and inline one-liner code examples could be enough (or a link, if it&#39;s not to twenty pages of scientific paper), as long as the big picture is clear by the end of it. I want to be able to look at a piece of code and be able to make a good guess about whether it will compile down to a tight loop, or why not, or what I would have to change to make it. (I&#39;m not interested so much here in the big optimization frameworks like stream fusion (I just read a paper about that); more in the kind of knowledge that people who *write* these frameworks have.)

[1]: http://metagraph.org/papers/stream_fusion.pdf
[2]: http://www.haskell.org/ghc/docs/latest/html/users_guide/options-optimise.html

What optimizations can GHC be expected to perform reliably?

I&#39;m having problems getting GHC to specialize a function with a class constraint. I have a minimal example of my problem here: [Foo.hs][1] and  [Main.hs][2]. The two files compile (GHC 7.6.2, `ghc -O3 Main`) and run.

**NOTE:**
`Foo.hs` is really stripped down. If you want to see why the constraint is needed, you can see a little more code [here][3]. If I put the code in a single file or make many other minor changes, GHC simply inlines the call to `plusFastCyc`. This will not happen in the real code because `plusFastCyc` is too large for GHC to inline, even when marked `INLINE`. The point is to _specialize_ the call to `plusFastCyc`, not inline it. `plusFastCyc` is called in many places in the real code, so duplicating such a large function would not be desirable even if I could force GHC to do it.


The code of interest is the `plusFastCyc` in `Foo.hs`, reproduced here:
    
    {-# INLINEABLE plusFastCyc #-}
    {-# SPECIALIZE plusFastCyc :: 
             forall m . (Factored m Int) =&gt; 
                  (FastCyc (VT U.Vector m) Int) -&gt; 
                       (FastCyc (VT U.Vector m) Int) -&gt; 
                            (FastCyc (VT U.Vector m) Int) #-}
    
    -- Although the next specialization makes `fcTest` fast,
    -- it isn&#39;t useful to me in my real program because the phantom type M is reified
    -- {-# SPECIALIZE plusFastCyc :: 
    --          FastCyc (VT U.Vector M) Int -&gt; 
    --               FastCyc (VT U.Vector M) Int -&gt; 
    --                    FastCyc (VT U.Vector M) Int #-}

    plusFastCyc :: (Num (t r)) =&gt; (FastCyc t r) -&gt; (FastCyc t r) -&gt; (FastCyc t r)
    plusFastCyc (PowBasis v1) (PowBasis v2) = PowBasis $ v1 + v2

The `Main.hs` file has two drivers: `vtTest`, which runs in ~3 seconds, and `fcTest`, which runs in ~83 seconds when compiled with -O3 using the `forall`&#39;d specialization.

The [core shows][4] that for the `vtTest` test, the addition code is being specialized to `Unboxed` vectors over `Int`s, etc, while generic vector code is used for `fcTest`.
On line 10, you can see that GHC does write a specialized version of `plusFastCyc`, compared to the generic version on line 167.
The rule for the specialization is on line 225. I believe this rule should fire on line 270. (`main6` calls `iterate main8 y`, so `main8` is where `plusFastCyc` should be specialized.)






My goal is to make `fcTest` as fast as `vtTest` by specializing `plusFastCyc`. I&#39;ve found two ways to do this:

 1. Explicity call `inline` from `GHC.Exts` in `fcTest`.
 2. Remove the `Factored m Int` constraint on `plusFastCyc`.

Option 1 is unsatisfactory because in the actual code base `plusFastCyc` is a frequently used operation and a *very* large function, so it should not be inlined at every use. Rather, GHC should call a specialized version of `plusFastCyc`. Option 2 is not really an option because I need the constraint in the real code.

I&#39;ve tried a variety of options using (and not using) `INLINE`, `INLINABLE`, and `SPECIALIZE`, but nothing seems to work. (**EDIT**: I may have stripped out too much of `plusFastCyc` to make my example small, so `INLINE` might cause the function to be inlined. This doesn&#39;t happen in my real code because `plusFastCyc` is so large.) In this particular example, I&#39;m not getting any [`match_co: needs more cases`][5] or [`RULE: LHS too complicated to desugar`][6] (and [here][7]) warnings, though I was getting many `match_co` warnings before minimizing the example. Presumably, the &quot;problem&quot; is the `Factored m Int` constraint in the rule; if I make changes to that constraint, `fcTest` runs as fast as `vtTest`.

Am I doing something GHC just doesn&#39;t like? Why won&#39;t GHC specialize the `plusFastCyc`, and how can I make it?

**UPDATE**

The problem persists in GHC 7.8.2, so this question is still relevant.

  [1]: http://lpaste.net/98464
  [2]: http://lpaste.net/98342
  [3]: http://lpaste.net/98840
  [4]: http://lpaste.net/98593
  [5]: http://web.archiveorange.com/archive/v/2B0uXzyXUnvOzzIApVfp
  [6]: https://stackoverflow.com/questions/18792388/haskell-ghc-specialize-causes-rule-left-hand-side-too-complicated-to
  [7]: https://ghc.haskell.org/trac/ghc/ticket/5821
  [8]: http://www.haskell.org/ghc/docs/7.6.2/html/users_guide/pragmas.html

Specialization with Constraints

Is there a simple answer: Why is GHC so big? 

 - OCaml: 2MB
 - Python: 15MB
 - SBCL: 9MB
 - OpenJRE - 26MB
 - **GHC: 113MB**

Not interested in evangelism of &quot;Why I shouldn&#39;t care about the size if Haskell is the right tool&quot;; this is a technical question.

Why is GHC so large/big?

I&#39;m trying to use the `ghc-mod` vim plugin to do type/syntax checking etc. However, I found that `ghc-mod` always uses full paths of types in the error messages, for example:

    test.hs|71 col 13 error| Couldn&#39;t match type ‘Data.Text.Internal.Text’                                                                                   
    ||                with ‘[GHC.Types.Char]’
    || Expected type: containers-0.5.6.2:Data.Map.Base.Map
    ||                  [GHC.Types.Char]
    ||                  ([(integer-gmp-1.0.0.0:GHC.Integer.Type.Integer,
    ||                     integer-gmp-1.0.0.0:GHC.Integer.Type.Integer)],
    ||                   containers-0.5.6.2:Data.Set.Base.Set
    ||                     integer-gmp-1.0.0.0:GHC.Integer.Type.Integer)
    ||   Actual type: containers-0.5.6.2:Data.Map.Base.Map
    ||                  Data.Text.Internal.Text
    ||                  ([(integer-gmp-1.0.0.0:GHC.Integer.Type.Integer,
    ||                     integer-gmp-1.0.0.0:GHC.Integer.Type.Integer)],
    ||                   containers-0.5.6.2:Data.Set.Base.Set
    ||                     integer-gmp-1.0.0.0:GHC.Integer.Type.Integer)
    || In the second argument of ‘containers-0.5.6.2:Data.Map.Base.map’, namely
    ||   ‘zippedMap’
    || In the second argument of ‘(GHC.Base.$)’, namely
    ||   ‘containers-0.5.6.2:Data.Map.Base.map
    ...

which clutters the screen and it&#39;s very hard for me to find out where went wrong. As comparison, this is the error message for the same file using `ghci`:

    test.hs:71:13:
        Couldn&#39;t match type ‘T.Text’ with ‘[Char]’
        Expected type: M.Map [Char] ([(Integer, Integer)], S.Set Integer)
          Actual type: M.Map T.Text ([(Integer, Integer)], S.Set Integer)
        In the second argument of ‘M.map’, namely ‘zippedMap’
        In the second argument of ‘($)’, namely
          ‘M.map
    ...

which is much cleaner. Is there a way to make `ghc-mod` use short names for the types?

Does GHC-mod have to use full names for types?

We are developing a program which receives and forwards &quot;messages&quot;, while keeping a temporary history of those messages, so that it can tell you the message history if requested. Messages are identified numerically, are typically around 1 kilobyte in size, and we need to keep hundreds of thousands of these messages.

We wish to optimize this program for latency: the time between sending and receiving a message must be below 10 milliseconds.

The program is written in Haskell and compiled with GHC. However, we have found that garbage collection pauses are far too long for our latency requirements: over 100 milliseconds in our real-world program.

The following program is a simplified version of our application. It uses a `Data.Map.Strict` to store messages. Messages are `ByteString`s identified by an `Int`. 1,000,000 messages are inserted in increasing numeric order, and the oldest messages are continually removed to keep the history at a maximum of 200,000 messages.

    module Main (main) where

    import qualified Control.Exception as Exception
    import qualified Control.Monad as Monad
    import qualified Data.ByteString as ByteString
    import qualified Data.Map.Strict as Map

    data Msg = Msg !Int !ByteString.ByteString

    type Chan = Map.Map Int ByteString.ByteString

    message :: Int -&gt; Msg
    message n = Msg n (ByteString.replicate 1024 (fromIntegral n))

    pushMsg :: Chan -&gt; Msg -&gt; IO Chan
    pushMsg chan (Msg msgId msgContent) =
      Exception.evaluate $
        let
          inserted = Map.insert msgId msgContent chan
        in
          if 200000 &lt; Map.size inserted
          then Map.deleteMin inserted
          else inserted

    main :: IO ()
    main = Monad.foldM_ pushMsg Map.empty (map message [1..1000000])

We compiled and ran this program using:

    $ ghc --version
    The Glorious Glasgow Haskell Compilation System, version 7.10.3
    $ ghc -O2 -optc-O3 Main.hs
    $ ./Main +RTS -s
       3,116,460,096 bytes allocated in the heap
         385,101,600 bytes copied during GC
         235,234,800 bytes maximum residency (14 sample(s))
         124,137,808 bytes maximum slop
                 600 MB total memory in use (0 MB lost due to fragmentation)

                                         Tot time (elapsed)  Avg pause  Max pause
      Gen  0      6558 colls,     0 par    0.238s   0.280s     0.0000s    0.0012s
      Gen  1        14 colls,     0 par    0.179s   0.250s     0.0179s    0.0515s

      INIT    time    0.000s  (  0.000s elapsed)
      MUT     time    0.652s  (  0.745s elapsed)
      GC      time    0.417s  (  0.530s elapsed)
      EXIT    time    0.010s  (  0.052s elapsed)
      Total   time    1.079s  (  1.326s elapsed)

      %GC     time      38.6%  (40.0% elapsed)

      Alloc rate    4,780,213,353 bytes per MUT second

      Productivity  61.4% of total user, 49.9% of total elapsed

The important metric here is the &quot;max pause&quot; of 0.0515s, or 51 milliseconds. We wish to reduce this by at least an order of magnitude.

Experimentation shows that the length of a GC pause is determined by the number of messages in the history. The relationship is roughly linear, or perhaps super-linear. The following table shows this relationship. ([You can see our benchmarking tests here](https://github.com/jameshfisher/ghc_gc_benchmarks), and [some charts here](https://docs.google.com/spreadsheets/d/1mDXrk8bqPb_nsR__pzHtSxwO8a_6bPVL8hd3Y9lCIm0/edit?usp=sharing).)

    msgs history length  max GC pause (ms)
    ===================  =================
    12500                                3
    25000                                6
    50000                               13
    100000                              30
    200000                              56
    400000                             104
    800000                             199
    1600000                            487
    3200000                           1957
    6400000                           5378

We have experimented with several other variables to find whether they can reduce this latency, none of which make a big difference. Among these unimportant variables are: optimization (`-O`, `-O2`); RTS GC options (`-G`, `-H`, `-A`, `-c`), number of cores (`-N`), different data structures (`Data.Sequence`), the size of messages, and the amount of generated short-lived garbage. The overwhelming determining factor is the number of messages in the history.

Our working theory is that the pauses are linear in the number of messages because each GC cycle has to walk over all the working accessible memory and copy it, which are clearly linear operations.

Questions:

* Is this linear-time theory correct? Can the length of GC pauses be expressed in this simple way, or is the reality more complex?
* If GC pause is linear in the working memory, is there any way to reduce the constant factors involved?
* Are there any options for incremental GC, or anything like it? We can only see research papers. We are very willing to trade throughput for lower latency.
* Are there any ways to &quot;partition&quot; memory for smaller, GC cycles, other than splitting into multiple processes?

Reducing garbage-collection pause time in a Haskell program

Even trivially small Haskell programs turn into gigantic executables. 

I&#39;ve written a small program, that was compiled (with GHC) to the binary with the size extending 7 MB! 

What can cause even a small Haskell program to be compiled to the huge binary?

What, if anything, can I do to reduce this?



Small Haskell program compiled with GHC into huge binary

How can I find the actual amount of memory required to store a value of some data type in Haskell (mostly with GHC)? Is it possible to evaluate it at runtime (e.g. in GHCi) or is it possible to estimate memory requirements of a compound data type from its components?

In general, if memory requirements of types `a` and `b` are known, what is the memory overhead of algebraic data types such as:

    data Uno = Uno a
    data Due = Due a b

For example, how many bytes in memory do these values occupy?

    1 :: Int8
    1 :: Integer
    2^100 :: Integer
    \x -&gt; x + 1
    (1 :: Int8, 2 :: Int8)
    [1] :: [Int8]
    Just (1 :: Int8)
    Nothing

I understand that actual memory allocation is higher due to delayed garbage collection. It may be significantly different due to lazy evaluation (and thunk size is not related to the size of the value). The question is, given a data type, how much memory does its value take when fully evaluated?

I found there is a `:set +s` option in GHCi to see memory stats, but it is not clear how to estimate the memory footprint of a single value.

Memory footprint of Haskell data types

Haskell has an identity function which returns the input unchanged. The definition is simple:

    id :: a -&gt; a
    id x = x

So for fun, this should output `8`:

    f = id id id id id id id id id id id id id id id id id id id id id id id id id id id
    main = print $ f 8

After a few seconds (and about 2 gb of memory according to Task Manager), compilation fails with `ghc: out of memory`. Similarly, the interpreter says `ghci: out of memory`.

Since `id` is a pretty simple function, I wouldn&#39;t expect it to be a memory burden at run time or compile time. What is all the memory being used for?

Why does Haskell&#39;s &quot;do nothing&quot; function, id, consume tons of memory?

I can&#39;t figure out why m1 is apparently memoized while m2 is not in the following:

    m1      = ((filter odd [1..]) !!)
    
    m2 n    = ((filter odd [1..]) !! n)

m1 10000000 takes about 1.5 seconds on the first call, and a fraction of that on subsequent calls (presumably it caches the list), whereas m2 10000000 always takes the same amount of time (rebuilding the list with each call). Any idea what&#39;s going on? Are there any rules of thumb as to if and when GHC will memoize a function? Thanks.

When is memoization automatic in GHC Haskell?

# Current behavior

    Prelude&gt; show _
    
    &lt;interactive&gt;:7:6:
        Found hole ‘_’ with type: a0
        Where: ‘a0’ is an ambiguous type variable
        Relevant bindings include it :: String (bound at &lt;interactive&gt;:7:1)
        In the first argument of ‘show’, namely ‘_’
        In the expression: show _
        In an equation for ‘it’: it = show _

# Desired behavior

It would be nice if GHC would also tell me that the typed hole has the `Show` type class constraint.

# Misc

*GHC Version 7.8.1*

Is there a way to make GHC provide the type class constraints of typed holes?

**Given**:

    data Foo =
      FooString String
      …

    class Fooable a where --(is this a good way to name this?)
      toFoo :: a -&gt; Foo

I want to make `String` an instance of `Fooable`:

    instance Fooable String where
      toFoo = FooString

GHC then complains:

    Illegal instance declaration for `Fooable String&#39;
        (All instance types must be of the form (T t1 ... tn)
         where T is not a synonym.
         Use -XTypeSynonymInstances if you want to disable this.)
    In the instance declaration for `Fooable String&#39;

If instead I use `[Char]`:

    instance Fooable [Char] where
      toFoo = FooString

GHC complains:

    Illegal instance declaration for `Fooable [Char]&#39;
       (All instance types must be of the form (T a1 ... an)
        where a1 ... an are type *variables*,
        and each type variable appears at most once in the instance head.
        Use -XFlexibleInstances if you want to disable this.)
    In the instance declaration for `Fooable [Char]&#39;

**Question**:

* Why can I not make String and instance of a typeclass?
* GHC seems willing to let me get away with this if I add an extra flag. Is this a good idea?



Why can I not make String an instance of a typeclass?

This piece of Haskell code runs *much* slower with `-O`, but `-O` should be [non-dangerous](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/options-optimise.html#optimise-pkgs). Can anyone tell me what happened? If it matters, it is an attempt to solve [this problem](http://tioj.ck.tp.edu.tw/problems/1827), and it uses binary search and persistent segment tree:

    import Control.Monad
    import Data.Array
    
    data Node =
    	  Leaf   Int           -- value
    	| Branch Int Node Node -- sum, left child, right child
    type NodeArray = Array Int Node
    
    -- create an empty node with range [l, r)
    create :: Int -&gt; Int -&gt; Node
    create l r
    	| l + 1 == r = Leaf 0
    	| otherwise  = Branch 0 (create l m) (create m r)
    	where m = (l + r) `div` 2
    
    -- Get the sum in range [0, r). The range of the node is [nl, nr)
    sumof :: Node -&gt; Int -&gt; Int -&gt; Int -&gt; Int
    sumof (Leaf val) r nl nr
    	| nr &lt;= r   = val
    	| otherwise = 0
    sumof (Branch sum lc rc) r nl nr
    	| nr &lt;= r   = sum
    	| r  &gt; nl   = (sumof lc r nl m) + (sumof rc r m nr)
    	| otherwise = 0
    	where m = (nl + nr) `div` 2
    
    -- Increase the value at x by 1. The range of the node is [nl, nr)
    increase :: Node -&gt; Int -&gt; Int -&gt; Int -&gt; Node
    increase (Leaf val) x nl nr = Leaf (val + 1)
    increase (Branch sum lc rc) x nl nr
    	| x &lt; m     = Branch (sum + 1) (increase lc x nl m) rc
    	| otherwise = Branch (sum + 1) lc (increase rc x m nr)
    	where m = (nl + nr) `div` 2
    
    -- signature said it all
    tonodes :: Int -&gt; [Int] -&gt; [Node]
    tonodes n = reverse . tonodes&#39; . reverse
    	where
    		tonodes&#39; :: [Int] -&gt; [Node]
    		tonodes&#39; (h:t) = increase h&#39; h 0 n : s&#39; where s&#39;@(h&#39;:_) = tonodes&#39; t
    		tonodes&#39; _ = [create 0 n]
    
    -- find the minimum m in [l, r] such that (predicate m) is True
    binarysearch :: (Int -&gt; Bool) -&gt; Int -&gt; Int -&gt; Int
    binarysearch predicate l r
        | l == r      = r
        | predicate m = binarysearch predicate l m
        | otherwise   = binarysearch predicate (m+1) r
        where m = (l + r) `div` 2
    
    -- main, literally
    main :: IO ()
    main = do
    	[n, m] &lt;- fmap (map read . words) getLine
    	nodes &lt;- fmap (listArray (0, n) . tonodes n . map (subtract 1) . map read . words) getLine
    	replicateM_ m $ query n nodes
    	where
    		query :: Int -&gt; NodeArray -&gt; IO ()
    		query n nodes = do
    			[p, k] &lt;- fmap (map read . words) getLine
    			print $ binarysearch (ok nodes n p k) 0 n
    			where
    				ok :: NodeArray -&gt; Int -&gt; Int -&gt; Int -&gt; Int -&gt; Bool
    				ok nodes n p k s = (sumof (nodes ! min (p + s + 1) n) s 0 n) - (sumof (nodes ! max (p - s) 0) s 0 n) &gt;= k

(This is exactly the same code with [code review](https://codereview.stackexchange.com/q/85557/24928) but this question addresses another problem.)

This is my input generator in C++:

&lt;!-- language: lang-cpp --&gt;

    #include &lt;cstdio&gt;
    #include &lt;cstdlib&gt;
    using namespace std;
    int main (int argc, char * argv[]) {
        srand(1827);
        int n = 100000;
        if(argc &gt; 1)
            sscanf(argv[1], &quot;%d&quot;, &amp;n);
        printf(&quot;%d %d\n&quot;, n, n);
        for(int i = 0; i &lt; n; i++)
            printf(&quot;%d%c&quot;, rand() % n + 1, i == n - 1 ? &#39;\n&#39; : &#39; &#39;);
        for(int i = 0; i &lt; n; i++) {
            int p = rand() % n;
            int k = rand() % n + 1;
            printf(&quot;%d %d\n&quot;, p, k);
        }
    }

In case you don&#39;t have a C++ compiler available, [this is the result of `./gen.exe 1000`](http://pastebin.com/rDH7zCX9).

This is the execution result on my computer:

&lt;!-- language: none --&gt;

    $ ghc --version
    The Glorious Glasgow Haskell Compilation System, version 7.8.3
    $ ghc -fforce-recomp 1827.hs
    [1 of 1] Compiling Main             ( 1827.hs, 1827.o )
    Linking 1827.exe ...
    $ time ./gen.exe 1000 | ./1827.exe &gt; /dev/null
    real    0m0.088s
    user    0m0.015s
    sys     0m0.015s
    $ ghc -fforce-recomp -O 1827.hs
    [1 of 1] Compiling Main             ( 1827.hs, 1827.o )
    Linking 1827.exe ...
    $ time ./gen.exe 1000 | ./1827.exe &gt; /dev/null
    real    0m2.969s
    user    0m0.000s
    sys     0m0.045s

And this is the heap profile summary:

&lt;!-- language: none --&gt;

    $ ghc -fforce-recomp -rtsopts ./1827.hs
    [1 of 1] Compiling Main             ( 1827.hs, 1827.o )
    Linking 1827.exe ...
    $ ./gen.exe 1000 | ./1827.exe +RTS -s &gt; /dev/null
          70,207,096 bytes allocated in the heap
           2,112,416 bytes copied during GC
             613,368 bytes maximum residency (3 sample(s))
              28,816 bytes maximum slop
                   3 MB total memory in use (0 MB lost due to fragmentation)
                                        Tot time (elapsed)  Avg pause  Max pause
      Gen  0       132 colls,     0 par    0.00s    0.00s     0.0000s    0.0004s
      Gen  1         3 colls,     0 par    0.00s    0.00s     0.0006s    0.0010s
      INIT    time    0.00s  (  0.00s elapsed)
      MUT     time    0.03s  (  0.03s elapsed)
      GC      time    0.00s  (  0.01s elapsed)
      EXIT    time    0.00s  (  0.00s elapsed)
      Total   time    0.03s  (  0.04s elapsed)
      %GC     time       0.0%  (14.7% elapsed)
      Alloc rate    2,250,213,011 bytes per MUT second
      Productivity 100.0% of total user, 83.1% of total elapsed
    $ ghc -fforce-recomp -O -rtsopts ./1827.hs
    [1 of 1] Compiling Main             ( 1827.hs, 1827.o )
    Linking 1827.exe ...
    $ ./gen.exe 1000 | ./1827.exe +RTS -s &gt; /dev/null
       6,009,233,608 bytes allocated in the heap
         622,682,200 bytes copied during GC
             443,240 bytes maximum residency (505 sample(s))
              48,256 bytes maximum slop
                   3 MB total memory in use (0 MB lost due to fragmentation)
                                        Tot time (elapsed)  Avg pause  Max pause
      Gen  0     10945 colls,     0 par    0.72s    0.63s     0.0001s    0.0004s
      Gen  1       505 colls,     0 par    0.16s    0.13s     0.0003s    0.0005s
      INIT    time    0.00s  (  0.00s elapsed)
      MUT     time    2.00s  (  2.13s elapsed)
      GC      time    0.87s  (  0.76s elapsed)
      EXIT    time    0.00s  (  0.00s elapsed)
      Total   time    2.89s  (  2.90s elapsed)
      %GC     time      30.3%  (26.4% elapsed)
      Alloc rate    3,009,412,603 bytes per MUT second
      Productivity  69.7% of total user, 69.4% of total elapsed




Why does this Haskell code run slower with -O?

When compiling my Haskell application with the &lt;code&gt;-Wall&lt;/code&gt; option, GHC complains about orphaned instances, for example:

    Publisher.hs:45:9:
        Warning: orphan instance: instance ToSElem Result

The type class &lt;code&gt;ToSElem&lt;/code&gt; is not mine, it&#39;s defined by [HStringTemplate][1].

Now I know how to fix this (move the instance declaration into the module where Result is declared), and I know [why GHC would prefer to avoid orphaned instances][2], but I still believe that my way is better.  I don&#39;t care if the compiler is inconvenienced - rather it than me.

The reason I want to declare my &lt;code&gt;ToSElem&lt;/code&gt; instances in the Publisher module is because it is the Publisher module that depends on HStringTemplate, not the other modules.  I am trying to maintain a separation of concerns and avoid having every module depend on HStringTemplate.

I thought that one of the advantages of Haskell&#39;s type classes, when compared for example to Java&#39;s interfaces, is that they are open rather than closed and therefore the instances do not have to be declared in the same place as the data type.  GHC&#39;s advice seems to be to ignore this.

So, what I&#39;m looking for is either some validation that my thinking is sound and that I would be justified in ignoring/suppressing this warning, or a more convincing argument against doing things my way.


  [1]: http://www.haskell.org/haskellwiki/HStringTemplate
  [2]: http://www.haskell.org/ghc/docs/6.10.3/html/users_guide/separate-compilation.html#orphan-modules

Orphaned instances in Haskell

Happstack Lite is breaking on me because it&#39;s getting blaze-html version 0.5 and it wants version 0.4.  Cabal says that *both* versions 0.4.3.4 and 0.5.0.0 are installed.  I want to remove the 0.5.0.0 and use just the older version.  But cabal does not have an &quot;uninstall&quot; command, and when I try `ghc-pkg unregister --force blaze-html`, `ghc-pkg` says my command has been ignored.  

What do I do?

**UPDATE**: *Don&#39;t believe it*.  Although `ghc-pkg` claims to ignore the command, the command *isn&#39;t* ignored.  And with Don Stewart&#39;s accepted answer you can remove exactly the version you wish to eliminate.

How can I uninstall a version of a Cabal package?

I wrote this small bit of Haskell to figure out how GHC proves that for natural numbers, you can only halve the even ones:

    {-# LANGUAGE DataKinds, GADTs, KindSignatures, TypeFamilies #-}
    module Nat where
    
    data Nat = Z | S Nat
    
    data Parity = Even | Odd
    
    type family Flip (x :: Parity) :: Parity where
      Flip Even = Odd
      Flip Odd  = Even
    
    data ParNat :: Parity -&gt; * where
      PZ :: ParNat Even
      PS :: (x ~ Flip y, y ~ Flip x) =&gt; ParNat x -&gt; ParNat (Flip x)
    
    halve :: ParNat Even -&gt; Nat
    halve PZ     = Z
    halve (PS a) = helper a
      where helper :: ParNat Odd -&gt; Nat
            helper (PS b) = S (halve b)

The relevant parts of core become:

    Nat.$WPZ :: Nat.ParNat &#39;Nat.Even
    Nat.$WPZ = Nat.PZ @ &#39;Nat.Even @~ &lt;&#39;Nat.Even&gt;_N
    
    Nat.$WPS
      :: forall (x_apH :: Nat.Parity) (y_apI :: Nat.Parity).
         (x_apH ~ Nat.Flip y_apI, y_apI ~ Nat.Flip x_apH) =&gt;
         Nat.ParNat x_apH -&gt; Nat.ParNat (Nat.Flip x_apH)
    Nat.$WPS =
      \ (@ (x_apH :: Nat.Parity))
        (@ (y_apI :: Nat.Parity))
        (dt_aqR :: x_apH ~ Nat.Flip y_apI)
        (dt_aqS :: y_apI ~ Nat.Flip x_apH)
        (dt_aqT :: Nat.ParNat x_apH) -&gt;
        case dt_aqR of _ { GHC.Types.Eq# dt_aqU -&gt;
        case dt_aqS of _ { GHC.Types.Eq# dt_aqV -&gt;
        Nat.PS
          @ (Nat.Flip x_apH)
          @ x_apH
          @ y_apI
          @~ &lt;Nat.Flip x_apH&gt;_N
          @~ dt_aqU
          @~ dt_aqV
          dt_aqT
        }
        }
    
    Rec {
    Nat.halve :: Nat.ParNat &#39;Nat.Even -&gt; Nat.Nat
    Nat.halve =
      \ (ds_dJB :: Nat.ParNat &#39;Nat.Even) -&gt;
        case ds_dJB of _ {
          Nat.PZ dt_dKD -&gt; Nat.Z;
          Nat.PS @ x_aIX @ y_aIY dt_dK6 dt1_dK7 dt2_dK8 a_apK -&gt;
            case a_apK
                 `cast` ((Nat.ParNat
                            (dt1_dK7
                             ; (Nat.Flip (dt2_dK8 ; Sym dt_dK6))_N
                             ; Nat.TFCo:R:Flip[0]))_R
                         :: Nat.ParNat x_aIX ~# Nat.ParNat &#39;Nat.Odd)
            of _
            { Nat.PS @ x1_aJ4 @ y1_aJ5 dt3_dKa dt4_dKb dt5_dKc b_apM -&gt;
            Nat.S
              (Nat.halve
                 (b_apM
                  `cast` ((Nat.ParNat
                             (dt4_dKb
                              ; (Nat.Flip
                                   (dt5_dKc
                                    ; Sym dt3_dKa
                                    ; Sym Nat.TFCo:R:Flip[0]
                                    ; (Nat.Flip (dt_dK6 ; Sym dt2_dK8))_N
                                    ; Sym dt1_dK7))_N
                              ; Sym dt_dK6))_R
                          :: Nat.ParNat x1_aJ4 ~# Nat.ParNat &#39;Nat.Even)))
            }
        }
    end Rec }

I know the general flow of casting the types through instances of the Flip type family, but there are some things that I cannot completely follow:

- What&#39;s the meaning of `@~ &lt;Nat.Flip x_apH&gt;_N` ? is it the Flip instance for x? How does that differ from `@ (Nat.Flip x_apH)`? I&#39;m both interested in `&lt; &gt;` and `_N`

Regarding the first cast in `halve`:

- What do `dt_dK6`, `dt1_dK7` and `dt2_dK8` stand for? I understand they are some kind of equivalence proofs, but which is which?
- I understand that `Sym` runs through an equivalence backwards
- What do the `;`&#39;s do? Are the equivalence proofs just applied sequentially?
- What are these `_N` and `_R` suffixes?
- Are `TFCo:R:Flip[0]` and `TFCo:R:Flip[1]` the instances of Flip?



How to read this GHC Core &quot;proof&quot;?

I&#39;ve been told you can interpret Haskell files (which I assume means they will work like Ruby/Python/Perl). I can&#39;t find the command line option on GHC to do this, though. It always wants to compile my file. Took a look at GHCi as well, but it always dumps me into a repl.

I&#39;m basically wanting to just do `ghc -i MyFile.hs` (where -i is a made up flag that I&#39;m pretending correllates to interpreted mode) and have it execute so that I can get quick feedback while I&#39;m trying out ideas and learning.


How to run a Haskell file in interpreted mode

As I am learning Haskell, I see that there is a lot of [language extensions][exts] used in real life code. As a beginner, should I learn to use them, or should I avoid them at all cost? I see that it breaks compatibility with Haskell&amp;nbsp;98 and limits code to pretty much GHC only. However, if I browse packages on Hackage, I see that most of them are GHC-only anyway.

So, what is an attitude of community towards using language extensions?

And if use of extensions is OK, how can I distinguish extensions which I can use “safely” (those which are likely to become part of the next Haskell standard) from those which are mostly “experimental”? For example, I suppose that [-XDisambiguateRecordFields][recorddisamb] is nice and useful, but is it likely to be supported in the future?

[exts]: http://haskell.org/ghc/docs/latest/html/users_guide/ghc-language-features.html
[recorddisamb]: http://haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#disambiguate-fields


Should I use GHC Haskell extensions or not?

I am confused. I tried to use `print`, but I know people apply `putStrLn`. What are the real differences between them?

    print $ function 
    putStrLn $ function

Difference between print and putStrLn in Haskell

I have been checking out [integer-gmp][1] source code to understand how foreign primops can be implemented in terms of cmm as documented on [GHC Primops page][2]. I am aware of techniques to implement them using [llvm hack][3] or fvia-C/gcc - this is more of a learning experience for me to understand this third approach that interger-gmp library uses.

So, I looked up CMM tutorial on MSFT page [(pdf link)][4], went through [GHC CMM page][5], and still there are some unanswered questions (hard to keep all those concepts in head without digging into CMM which is what I am doing now). There is this code fragment from [integer-bmp cmm file][6]:

    integer_cmm_int2Integerzh (W_ val)
    {
       W_ s, p; /* to avoid aliasing */
    
       ALLOC_PRIM_N (SIZEOF_StgArrWords + WDS(1), integer_cmm_int2Integerzh, val);
    
       p = Hp - SIZEOF_StgArrWords;
       SET_HDR(p, stg_ARR_WORDS_info, CCCS);
       StgArrWords_bytes(p) = SIZEOF_W;
    
       /* mpz_set_si is inlined here, makes things simpler */
       if (%lt(val,0)) {
            s  = -1;
            Hp(0) = -val;
       } else {
         if (%gt(val,0)) {
            s = 1;
            Hp(0) = val;
         } else {
            s = 0;
         }
      }
    
       /* returns (# size  :: Int#,
                     data  :: ByteArray#
                   #)
       */
       return (s,p);
    }

As defined in [ghc cmm header][7]:

    W_ is alias for word.
    ALLOC_PRIM_N is a function for allocating memory on the heap for primitive object.
    Sp(n) and Hp(n) are defined as below (comments are mine):
    #define WDS(n) ((n)*SIZEOF_W) //WDS(n) calculates n*sizeof(Word)
    #define Sp(n)  W_[Sp + WDS(n)]//Sp(n) points to Stackpointer + n word offset?
    #define Hp(n)  W_[Hp + WDS(n)]//Hp(n) points to Heap pointer + n word offset?

I don&#39;t understand lines 5-9 (line 1 is the start in case you have 1/0 confusion). More specifically:
 
 - Why is the function call format of ALLOC_PRIM_N (bytes,fun,arg) that way?
 - Why is p manipulated that way?

The function as I understand it (from looking at function signature in [Prim.hs][8]) takes an int, and returns a (int, byte array) (stored in `s`,`p` respectively in the code).  

For anyone who is wondering about inline call in `if block`, it is cmm implementation of gmp [mpz_init_si function][9]. My guess is if you call a function defined in object file through ccall, it can&#39;t be inlined (which makes sense since it is object-code, not intermediate code - LLVM approach seems more suitable for inlining through LLVM IR). So, the optimization was to define a cmm representation of the function to be inlined. Please correct me if this guess is wrong.

Explanation of lines 5-9 will be very much appreciated. I have more questions about other macros defined in integer-gmp file, but it might be too much to ask in one post. If you can answer the question with a Haskell wiki page or a blog (you can post the link as answer), that would be much appreciated (and if you do, I would also appreciate step-by-step walk-through of an integer-gmp cmm macro such as `GMP_TAKE2_RET1`).


  [1]: https://github.com/ghc/packages-integer-gmp
  [2]: http://hackage.haskell.org/trac/ghc/wiki/Commentary/PrimOps
  [3]: http://breaks.for.alienz.org/blog/2012/02/09/parsing-market-data-feeds-with-ragel/
  [4]: http://www.cminusminus.org/extern/man2.pdf
  [5]: http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/CmmType
  [6]: https://github.com/ghc/packages-integer-gmp/blob/master/cbits/gmp-wrappers.cmm
  [7]: https://github.com/ghc/ghc/blob/master/includes/Cmm.h
  [8]: https://github.com/ghc/packages-integer-gmp/blob/master/GHC/Integer/GMP/Prim.hs
  [9]: http://stuff.mit.edu/afs/sipb.mit.edu/project/stk/src/STk-2.2.0/Mp/gmp-1.3.2/mpz_set_si.c

cmm call format for foreign primop (integer-gmp example)

I had this code:

    class SymbolSet tpe where
      data Symbol tpe :: *
     
    data SSet tpe where
      Identity :: tpe -&gt; SSet tpe
      And :: SSet tpe -&gt; Symbol tpe -&gt; SSet tpe
     
    class HasElem a b where
     
    instance (SymbolSet tpe) =&gt; HasElem (And (Identity tpe) s) s
    instance (HasElem sset s) =&gt; HasElem (And sset s) s

which was compiling in GHC-7.4. However on moving to GHC-7.6 it started giving compilation errors:

    &#39;And&#39; of tpe `forall tpe. tpe -&gt; Symbol * tpe -&gt; SSet tpe&#39; is not promotable

on digging through the docs, I found a new clause added to &quot;Datatype Promotion&quot; pages in [GHC-7.6][1] vs [GHC-7.4][2]

&gt; We do not promote datatypes whose constructors are kind polymorphic,
&gt; involve constraints, or use existential quantification.

My question is: 

 1. What is the rationale behind not promoting such constructors? 
 2. What would be the correct way of doing it?


  [1]: http://www.haskell.org/ghc/docs/7.6.1/html/users_guide/promotion.html#id621045
  [2]: http://www.haskell.org/ghc/docs/7.4.2/html/users_guide/kind-polymorphism-and-promotion.html#promotion

Data Constructor promotion in GHC-7.6

If you&#39;ve bought into the functional programming paradigm, the chances are that you like both Erlang and Haskell.  Both have purely functional cores and other goodness such as lightweight threads that make them a good fit for a multicore world.  But there are some differences too.

Erlang is a commercially proven fault-tolerant language with a mature distribution model.  It has a seemingly unique feature in its ability to upgrade its version at runtime via hot code loading.  (Way cool!)

Haskell, on the otherhand, has the most sophisticated type system of any mainstream language.  (Where I define &#39;mainstream&#39; to be any language that has a published O&#39;Reilly book so Haskell counts.)  Its straightline single threaded performance looks superior to Erlang&#39;s and its lightweight threads look even lighter too.

I am trying to put together a development platform for &lt;i&gt;the rest of my coding life&lt;/i&gt; and was wondering whether it was possible to mix Erlang and Haskell to achieve a best of breed platform.  This question has two parts:

   1. I&#39;d like to use Erlang as a kind of fault tolerant MPI to glue GHC runtime instances together.  There would be one Erlang process per GHC runtime.  If &quot;the impossible happened&quot; and the GHC runtime died, then the Erlang process would detect that somehow and die too.   Erlang&#39;s hot code loading and distribution features would just continue to work.  The GHC runtime could be configured to use just one core, or all cores on the local machine, or any combination in between.   Once the Erlang library was written, the rest of the Erlang level code should be purely boilerplate and automatically generated on a per application basis.  (Perhaps by a Haskell DSL for example.)   How does one achieve at least some of these things?
   2. I&#39;d like Erlang and Haskell to be able to share the same garabage collector.  (This is a much further out idea than 1.)   Languages that run on the JVM and the CLR achieve greater mass by sharing a runtime.  I understand there are technical limitations to running Erlang (hot code loading) and Haskell (higher kinded polymorphism) on either the JVM or the CLR.  But what about unbundling just the garbage collector?  (Sort of the start of a runtime for functional languages.)  Allocation would obviously still have to be really fast, so maybe that bit needs to be statically linked in.  And there should be some mechansim to distinguish the mutable heap from the immutable heap (incuding lazy write once memory) as GHC needs this.  Would it be feasible to modify both HIPE and GHC so that the garbage collectors could share a heap?

Please answer with any experiences (positive or negative), ideas or suggestions.  In fact, any feedback (short of straight abuse!) is welcome.

**Update**

Thanks for all 4 replies to date - each taught me at least one useful thing that I did not know.

Regarding *the rest of coding life* thing - I included it slightly tongue in cheek to spark debate, but it is actually true.  There is a project that I have in mind that I intend to work on until I die, and it needs a stable platform.

In the platform I have proposed above, I would only write Haskell, as the boilerplate Erlang would　be automatically generated.  So how long will Haskell last?  Well Lisp is still with us and doesn&#39;t look like it is going away anytime soon.  Haskell is BSD3 open source and has achieved critical mass.  If programming itself is still around in 50 years time, I would expect Haskell, or some continuous evolution of Haskell, will still be here.

**Update 2** *in response to rvirding&#39;s post*

Agreed - implementing a complete &quot;Erskell/Haslang&quot; universal virtual machine might not be absolutely impossible, but it would certainly be very difficult indeed.  Sharing just the garbage collector level as something like a VM, while still *difficult*, sounds an order of magnitude less difficult to me though.  At the garbage collection model, functional languages must have a lot in common - the unbiquity of immutable data (including thunks) and the requirement for very fast allocation.  So the fact that commonality is bundled tightly with monolithic VMs seems kind of odd.

VMs do help achieve critical mass.  Just look at how &#39;lite&#39; functional languages like F# and Scala have taken off.  Scala may not have the absolute fault tolerance of Erlang, but it offers an escape route for the very many folks who are tied to the JVM.

&gt; While having a single heap makes
&gt; message passing very fast it
&gt; introduces a number of other problems,
&gt; mainly that doing GC becomes more
&gt; difficult as it has to be interactive
&gt; and globally non-interruptive so you
&gt; can&#39;t use the same simpler algorithms
&gt; as the per-process heap model.

Absolutely, that makes perfect sense to me.  The very smart people on the GHC development team appear to be trying to solve part of the problem with a parallel &quot;stop the world&quot; GC.

**[http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel-gc/par-gc-ismm08.pdf][1]**

(Obviously &quot;stop the world&quot; would not fly for general Erlang given its main use case.)  But even in the use cases where &quot;stop the world&quot; is OK, their speedups do not appear to be universal.  So I agree with you, it is unlikely that there is a universally best GC, which is the reason I specified in part 1. of my question that

&gt; The GHC runtime could be configured to
&gt; use just one core, or all cores on the
&gt; local machine, or any combination in
&gt; between.

In that way, for a given use case, I could, after benchmarking, choose to go the Erlang way, and run one GHC runtime (with a singlethreaded GC) plus one Erlang process per core and let Erlang copy memory between cores for good locality.

Alternatively, on a dual processor machine with 4 cores per processor with good memory bandwidth on the processor, benchmarking might suggest that I run one GHC runtime (with a parallel GC) plus one Erlang process per processor.

In both cases, if Erlang and GHC could share a heap, the sharing would probably be bound to a single OS thread running on a single core somehow.  (I am getting out of my depth here, which is why I asked the question.)

I also have another agenda - benchmarking functional languages independently of GC.  Often I read of results of benchmarks of OCaml v GHC v Erlang v ... and wonder how much the results are confounded by the different GCs.  What if choice of GC could be orthogonal to choice of functional language?  How expensive is GC anyway?  See this devil advocates blog post 

**[http://john.freml.in/garbage-collection-harmful][2]**

by my Lisp friend John Fremlin, which he has, charmingly, given his post title &quot;Automated garbage collection is rubbish&quot;.  When John claims that GC is slow and hasn&#39;t really sped up that much, I would like to be able to counter with some numbers. 


  [1]: http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel-gc/par-gc-ismm08.pdf
  [2]: http://john.freml.in/garbage-collection-harmful

Mixing Erlang and Haskell

I read that hash tables in Haskell had performance issues (on the [Haskell-Cafe][1] in 2006 and [Flying Frog Consultancy&#39;s blog][2] in 2009), and since I like Haskell it worried me.

That was a year ago, what is the status now (June 2010)? Has the &quot;hash table problem&quot; been fixed in GHC?


  [1]: http://thread.gmane.org/gmane.comp.lang.haskell.cafe/11070
  [2]: http://flyingfrogblog.blogspot.com/2009/04/f-vs-ocaml-vs-haskell-hash-table.html

Curious about the HashTable performance issues

The design of GHC is based on something called STG, which stands for &quot;spineless, tagless G-machine&quot;.

Now G-machine is apparently short for &quot;graph reduction machine&quot;, which defines how laziness is implemented. Unevaluated thunks are stored as an expression tree, and executing the program involves _reducing_ these down to normal form. (A _tree_ is an acyclic graph, but Haskell&#39;s pervasive recursion means that Haskell expressions form general _graphs_, hence graph-reduction and not tree-reduction.)

What is less clear are the terms &quot;spineless&quot; and &quot;tagless&quot;.

1. I _think_ that &quot;spineless&quot; refers to the fact that function applications do not have a &quot;spine&quot; of function application nodes. Instead, you have an object that names the function called and points to all of its arguments. Is that correct?

2. I thought that &quot;tagless&quot; referred to constructor nodes not being &quot;tagged&quot; with a constructor ID, and instead case-expressions are resolved using a jump instruction. But now I&#39;m not sure that&#39;s correct. Instead, it seems to refer to the fact that nodes aren&#39;t tagged with their evaluation state. Can anyone clarify which (if any) of these interpretations is correct?


All Ghc Solutions on Gang of Coders

Total of 29 Ghc Solutions