visualize-cbn: Visualize CBN reduction

[ bsd3, development, program ] [ Propose Tags ]

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


[Skip to Readme]
Versions 0.1.0.0, 0.1.0.1
Change log ChangeLog.md
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
Maintainer edsko@well-typed.com
Category Development
Source repo head: git clone https://github.com/well-typed/visualize-cbn
Uploaded by EdskoDeVries at Sun Mar 4 12:57:15 UTC 2018
Distributions NixOS:0.1.0.1
Executables visualize-cbn
Downloads 299 total (13 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs not available [build log]
Last success reported on 2018-03-04 [all 2 reports]
Hackage Matrix CI

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for visualize-cbn-0.1.0.1

[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.

Example

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

1

(whnf)

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

<html>
<body>

<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>
</table>

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

</body>
</html>

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