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?

$\endgroup$
2
  • $\begingroup$ Great question! Welcome to the site. I don't know the answer, but maybe someone else does. $\endgroup$ 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$ Jan 31, 2022 at 9:27

1 Answer 1

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.

$\endgroup$
0

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .