Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

328 lines (266 sloc) 8.788 kB
<!DOCTYPE html>
<meta charset="utf-8">
<link href="//netdna.bootstrapcdn.com/twitter-bootstrap/2.3.2/css/bootstrap-combined.min.css" rel="stylesheet">
<style>
body{
width: 960px;
margin: auto;
}
.node {
cursor: pointer;
}
.node circle {
fill: #fff;
stroke: steelblue;
stroke-width: 1.5px;
}
.node text {
font: 14px sans-serif;
}
.link {
fill: none;
stroke-width: 2px;
}
.ref-link {
fill: none;
stroke-width: 1px;
stroke-dasharray: 6;
}
.node:hover .ref-link {
stroke: slateblue;
}
.menu {
text-align: center;
}
#parser .btn {
padding: 24px inherit;
}
</style>
<body>
<div class="page-header">
<h1><a href="http://en.wikipedia.org/wiki/Lambda_calculus">λ</a> machine <small>as a <a href="http://d3js.org/">d3</a> tree, parsed with <a href="http://pegjs.majda.cz/">PEG</a></small></h1>
</div>
<form class="well form-inline" id="parser" onsubmit="return false;">
<div class="control-group">
<textarea type="text" class="span10" rows="3" name="p"></textarea>
<input class="btn btn-large span2" type="submit" value="parse">
</div>
</form>
<div class="menu">
<a href="javascript:void 0" class="btn btn-large" id="reduce">reduce</a>
</div>
<svg></svg>
<dl id="samples">
</dl>
<small>
<em>
<p>
This is a universal machine, using the untyped lambda calculus, visualized as a tree with d3.js.
# is an abstraction. @ is application. Numbers are variables.
</p>
<p>
The syntax is a simplified version of the De Brujin index, meaning vars match to their Nth parent lambda (#), N being the var name.
It requires explicit applications, ie you can't drop parens.
</p>
<p>
It gets parsed by a parser generated by PEG.js.
Grammar and source on github.
</p>
</em>
</small>
<a href="https://github.com/brycec/vizlamb"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_gray_6d6d6d.png" alt="Fork me on GitHub"></a>
<script src="http://code.jquery.com/jquery-1.9.1.min.js"></script>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="http://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.4.4/underscore-min.js"></script>
<script src="parser.js"></script>
<script src="arborist.js"></script>
<script>
var global = this;
$(function($){
var parserBox = $('#parser textarea');
$('#parser').on('submit', parseTree);
function parseTree(e) {
var tree = {}
try {
tree = parser.parse(parserBox.val());
$('#alert').hide();
global.DATA = tree;
} catch (err) {
var alert = $($('#alert')[0] || $('<div id="alert" class="alert alert-error">'));
alert.detach().text(err);
$('#parser').append(alert);
}
initData();
return false;
}
var reducing = false;
$('#reduce').on('click', function() {
if (reducing) return;
var reducing = true;
var app = _(root).findReducible(),
abs = app.children[0],
arg = app.children[1];
app.marked = abs.marked = 'indianred';
_(abs).forMatchingVars(function(n) {
n.marked = 'lightsteelblue';
});
_(arg).walk(function(n){n.marked = 'lightsteelblue'});
update(app);
setTimeout(function() {
_(abs).substitute(arg);
update(abs);
}, duration * 1.5);
setTimeout(function() {
var result = _(app).popOff();
if (app == root) root = result;
_(abs).walk(function(n){n.marked = null});
update(app);
parserBox.val(_(root).brujin());
}, duration * 1.5 * 2);
reducing = false;
});
// some sample expressions
var samples = {
"(+ 2 3)": "((####((4 2) ((3 2) 1)) (##(2 (2 1)))) (##(2 (2 (2 1)))))",
"Omega": "(#(1 1) #(1 1))",
"Not True": "(#((1 ##1) ##2) ##2)",
"Almost true": "#(##2 1)"
}
// parse initial tree
$('#parser textarea').val(samples['(+ 2 3)']).submit();
// render samples
$.each(samples, function(name, code) {
$('#samples').append($('<dt><a href="javascript:void 0">'+name+'</a></dt><dd>'+code+'</dd>'));
});
$('#samples').on('click', 'dt a', function(e){
var par = $(e.target).parent()
, code = par.next().text();
$('#parser textarea').val(code).submit();
})
});
</script>
<script>
var margin = {top: 20, right: 120, bottom: 20, left: 120},
width = 960 - margin.right - margin.left,
height = 800 - margin.top - margin.bottom;
var i = 0,
duration = 420,
root;
var tree = d3.layout.tree()
.size([height, width]);
var diagonal = d3.svg.diagonal()
.projection(function(d) { return [d.x, d.y]; });
var diagonal2 = d3.svg.diagonal();
var svg = d3.select("svg")
.attr("width", width + margin.right + margin.left)
.attr("height", height + margin.top + margin.bottom)
.append("g")
.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
function initData() {
flare = $.extend(true, {}, DATA);
root = flare;
root.x0 = width / 2;
root.y0 = 0;
update(root);
}
function expandAll(d) {
if (d._children) {
d.children = d._children;
d._children = null;
}
if (d.children) d.children.forEach(expandAll);
}
function update(source) {
// Compute the new tree layout.
var nodes = tree.nodes(root),
links = tree.links(nodes);
// Normalize for fixed-depth.
nodes.forEach(function(d) { d.y = d.depth * 40; });
// Update the nodes…
var node = svg.selectAll("g.node")
.data(nodes, function(d) { return d.id || (d.id = ++i); });
// Enter any new nodes at the parent's previous position.
var nodeEnter = node.enter().append("g")
.attr("class", "node")
.attr("id", function(d) { return "d" + d.id; })
.attr("transform", function(d) { return "translate(" + source.x0 + "," + source.y0 + ")"; });
nodeEnter.append("path")
.attr("class", "ref-link")
.attr("d", function(d) {
var o = {x: 0, y: 0};
return diagonal2({source: o, target: o});
});
nodeEnter.append("circle")
.attr("r", 1e-6)
.style("fill", function(d) { return d._children ? "lightsteelblue" : "#fff"; });
nodeEnter.append("text")
.attr("dy", ".35em")
.text(function(d) { return d.name; })
.style("fill-opacity", 1e-6);
// Transition nodes to their new position.
var nodeUpdate = node.transition()
.duration(duration)
.attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; });
nodeUpdate.select("circle")
.attr("r", 5.2)
.style("fill", function(d) { return d._children ? "lightsteelblue" : d.marked ? d.marked : "#fff"; });
nodeUpdate.select("text")
.attr("text-anchor", function(d) { return d.children || d._children ? "end" : "start"; })
.attr("x", function(d) { return d.children || d._children ? -10 : 10; })
.text(function(d) { return d.name; })
.style("fill-opacity", 1);
// matching abstraction link
nodeUpdate.select('.ref-link')
.attr("transform", function(d) { return "translate(-" + d.x + ",-" + d.y + ")"; })
.attr("stroke", function(d) { return d.marked ? "indianred" : "lightgray"; })
.attr("d", function(d) {
var depth = +d.name, cur = d;
if (_.type(d) == "var") {
cur = _.matchingAbs(d);
}
return diagonal2({source: cur, target: d});
});
// Transition exiting nodes to the parent's new position.
var nodeExit = node.exit().transition()
.duration(duration)
.attr("transform", function(d) {
var target = d.marked ? d : source;
return "translate(" + target.x + "," + target.y + ")";
})
.remove();
nodeExit.select("circle")
.attr("r", 1e-6);
nodeExit.select("text")
.style("fill-opacity", 1e-6);
nodeExit.select(".ref-link")
.attr("d", function(d) { return diagonal2({source: d, target: d}) })
// Update the links…
var link = svg.selectAll("path.link")
.data(links, function(d) { return d.target.id; });
// Enter any new links at the parent's previous position.
link.enter().insert("path", "g")
.attr("stroke", "lightgray")
.attr("class", "link")
.attr("d", function(d) {
var o = {x: source.x0, y: source.y0};
return diagonal({source: o, target: o});
});
// Transition links to their new position.
link.transition()
.duration(duration)
.attr("d", diagonal);
// Transition exiting nodes to the parent's new position.
link.exit().transition()
.duration(duration)
.attr("d", function(d) {
var o = {x: source.x, y: source.y};
return diagonal({source: o, target: o});
})
.remove();
// Stash the old positions for transition.
nodes.forEach(function(d) {
d.x0 = d.x;
d.y0 = d.y;
});
}
</script>
Jump to Line
Something went wrong with that request. Please try again.