4
$\begingroup$

I know that under the hood, for a Haskell program, the GHC compiler uses graph reduction for optimization. Is there any way to view this graphical representation of the program? I haven't been able to find an existing plugin that, given a Haskell program, produces its graphical representation. I am relatively new to Haskell.

Are there research tools available to study and manipulate such graphs?

Improve this question
$\endgroup$
2
  • $\begingroup$ Great question! Welcome to the site. I don't know the answer, but maybe someone else does. $\endgroup$
    – Caleb Stanford
    Commented Jul 10, 2020 at 16:10
  • $\begingroup$ may I suggest that there is maybe an isomorphism betweem the graph reduction done by GHC for optimization (and I guess evaluation/compilation) and the partial evaluation through meta-interpretation for optimization, as seen in Logic Programming (and perhaps tracing JIT interpreter systems such as PyPy)? $\endgroup$
    – Erik Kaplun
    Commented Jan 31, 2022 at 9:27

1 Answer 1

Reset to default
1
$\begingroup$

Welcome to CS.SE!

I cannot present the underlying algorithms themselves, just the concepts they use.

The normal form (NF) of some expression is basically its result, like 42, Just 1, \ x -> 1 + x.

The weak head normal form (WHNF) is some expression which is one of three:

  1. A lambda: \ x -> x + 5 * 6. The NF is \ x -> x + 30.
  2. Data constructor: (3, 2 + 5). The NF is (3, 7). It could be partially applied: (,) (2 * 5). The NF is \ x -> (10, x).
  3. Partially applied built-in function: (+) (2 * 8). The NF is \ x -> 16 + x.

As one can see, WHNF generalizes NF.

So, what have graphs got to do with this? Well, one can understand f e1 e2 ... en as a graph with a node f which is connected with n other nodes: e1, e2, ..., en. Evaluation is the reduction of the nodes1. To show why this is actually very cool I am going to use a picture which I stumbled upon on Wikipedia and HaskellWiki not so long ago:

https://commons.wikimedia.org/wiki/File:Right-fold-transformation.png

So, what is going on in this picture? The idea is simple: when working with lists, we have a binary operation (:) and some initial value []. When we are folding, we have a binary operation f and some initial value z. The data structure does not change - only the nodes of our graph. To get the complete result (NF, that is), we reduce the graph.

(Please note that the initial 1 : 2 : 3 : 4 : 5 : [] could not have been reduced any further; in (pseudo-)haskell the lists are: data [a] = a : [a] | [].)

1Some technical details on evaluation (the basic tools to manipulate graphs, just as you have asked). The programmer might force the reduction. seq x y forces its first argument to the WHNF and returns the second (being basically flip const magically strict in the first argument). More formally:

...seq x y means that whenever y is evaluated to weak head normal form, x is also evaluated to weak head normal form.

If the programmer wants to do the same for the NF, they should take a look at Control.DeepSeq.deepseq.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.