visualize-cbn: Visualize CBN reduction

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

CBN interpretation and visualization tool. Exports in text format, coloured text (ANSI) or HTML/JavaScript.

[Skip to Readme]


Change log
Dependencies ansi-terminal (==0.6.*), base (>=4.8 && <4.11), blaze-html (>=0.8 && <0.10), blaze-markup (>=0.7 && <0.9), containers (==0.5.*), data-default (==0.7.*), optparse-applicative (>=0.12 && <0.15), parsec (==3.1.*), template-haskell, text [details]
License BSD-3-Clause
Copyright Well-Typed LLP
Author Edsko de Vries
Category Development
Source repo head: git clone
Uploaded by EdskoDeVries at 2018-03-04T12:56:21Z


Maintainer's Corner

For package maintainers and hackage trustees

Readme for visualize-cbn-

[back to package description]

Call-by-name interpretation and visualization tool

Haskell and other call-by-name languages use lazy evaluation as their default evaluation strategy. For beginners and advanced programmers alike this can sometimes be confusing. The visualize-cbn tool is designed to help in such cases; it is a simple interpreter for a mini-Haskell-like language which outputs the state of the program at every step in a human readable format. It can also generate a HTML/JavaScript version with "Previous" and "Next" buttons to allow to step through a program.


Consider the following example program:

fac = (\n ->
    if le n 1
      then 1
      else mul (@fac (sub n 1)) n

main = @fac 1

The syntax is not quite Haskell, but hopefully it should be pretty self-explanatory. The parser is pretty finicky; look at some of the examples in examples/ to deduce what the syntax is. The only somewhat odd feature is the identifies marked with an at-sign (@); these corresponds to pointers in the heap. For programs in their initial state (i.e., as written down), the only heap pointers we expect are to CAFs (constant applicative forms; values defined at the top-level of the program).

Stepping through

We can step through the evaluation of this program using

visualize-cbn -i examples/fac.hs --show-trace --hide-prelude

This will result in something like

** 0

fac 1

(apply fac)

** 1

if 1 <= 1
  then 1
  else fac (1 - 1) * 1

(delta: 1 <= 1)

** 2

if True
  then 1
  else fac (1 - 1) * 1

(if True)

** 3



At every step it lists the current state of the program, as well as the reduction rules that apply. There are some options for tweaking the output; see --help.

Generating HTML/JavaScript

The tool can also generate HTML/JavaScript:

cr visualize-cbn -i examples/fac.hs --javascript foo.js

The resulting .js file can be embedded in a HTML page (such as a blog post); a minimal HTML page illustrating how this is done is given by


<a onclick="cbnPrev()">Prev</a>
<a onclick="cbnNext()">Next</a>
(step <span id="cbn_step">Step</span>, <span id="cbn_status">Status</span>)

<table width="100%" border="1" cellpadding="5" style="border-collapse: collapse;">
<tr><td><div style="font-family: monospace;" id="cbn_term">Term</div></td></tr>
<tr><td><div style="font-family: monospace;" id="cbn_heap">Heap</div></td></tr>

<script type="text/javascript" src="foo.js"></script>


(This .html file was not written to illustrate HTML best practices :-) ) See the Well-Typed blog post about the tool for an example output.