plmrry/README.md

## README.md

      
    Raw
  

              README.md
            
          
    On the right is an interactive force-directed representation of a Turing Machine.
The turing machine reads a tape and writes decimal values such as "0.6."
At each step, a copy of the tape is made, where each value on the tape is mapped to a hue angle in HSL space.

  
## index.html
<html>
<head>
<link href='http://fonts.googleapis.com/css?family=Lato:100,400' rel='stylesheet' type='text/css'>
<style>
body {
    width: 100%;
    height: 100%;
    margin: 0;
}
main {
    display: flex;
    flex-direction: row;
    width: 80%;
    height: 90%;
    margin: 0 auto;
    padding-top: 10px;
    padding-bottom: 10px;
}
svg {
    width: 100%;
    height: 100%;
}
#tape {
    flex: 1 1 0;
    /*border: 1px solid black;*/
}
#turing {
    flex: 4;
    /*border: 1px solid black;*/
}
.square rect {
    /*fill: none;*/
    stroke: #ddd;
}
.square text {
    fill: #999;
    text-anchor: middle;
    font-family: 'Lato', sans-serif;
    font-weight: 100;
    font-size: 4em;
}
.node circle {
    fill: #ddf;
    /*stroke: black;
    stroke-opacity: 0;*/
}
.node text, .link text {
    fill: #333;
    text-anchor: middle;
    font-family: "Helvetica", sans-serif;
    font-weight: 100;
}
.node text {
    font-size: 0.4em;
}
.link text {
    font-size: 0.5em;
}
.link path {
    fill: none;
    /*stroke: #999;*/
}
#end path {
    /*fill: #ccc;*/
}
</style>
</head>
<body>
    <main>
        <svg id="tape">
        </svg>
        <svg id="turing">
        </svg>
    </main>

<script src="//cdnjs.cloudflare.com/ajax/libs/d3/3.5.3/d3.min.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>

<script>
var _tape_length = 30;

var states = d3.range(7).map(function(d, i) {
    var obj = { id: i };
    if (obj.id === 1) obj.initial = true;
    if (obj.id === 3) obj.accept = true;
    return obj;
});

var tape = d3.range(_tape_length).map(function(d, i) {
    var obj = { position: i, symbol: "_" };
    if (i === 0) obj.symbol = 0;
    if (i === _tape_length - 1) obj.symbol = 1;
    return obj;
});

var transitions = [
    { source: getState(0), target: getState(1) },
    { source: getState(1), target: getState(4), inputs: [0, "_"], write: 0.9, move: "R" },
    { source: getState(4), target: getState(1), inputs: [0, "_"], write: 0.75, move: "R" },
    { source: getState(4), target: getState(2), inputs: [1], write: 0.6, move: "L" },
    { source: getState(1), target: getState(2), inputs: [1], write: 0.6, move: "L" },
    { source: getState(2), target: getState(5), inputs: [0.9, 0.75, 0.4, 0.6], write: 0.6, move: "L" },
    // { source: getState(2), target: getState(3), inputs: [0], move: "R"},
    { source: getState(5), target: getState(6), inputs: [0.9, 0.75, 0.6], write: 0.4, move: "R"},
    { source: getState(6), target: getState(2), inputs: [0.9, 0.75], write: 0.3, move: "L" },
    { source: getState(6), target: getState(2), inputs: [0.4, 0.6], write: 0.1, move: "L" },
    { source: getState(5), target: getState(3), inputs: ["_"], move: "R"},
    { source: getState(6), target: getState(3), inputs: ["_"], move: "R"},
    { source: getState(2), target: getState(3), inputs: ["_"], move: "R"},
]

var head = tape[0];

var width = height = 300;

var svg = d3.select("#turing")
    .attr({
        viewBox: "0 0 " + width + " " + height
    });

svg.append("svg:defs").selectAll("marker")
    .data(["end"])
  .enter().append("svg:marker")
    .attr("id", String)
    .attr("viewBox", "0 -5 10 10")
    .attr("refX", 20)
    .attr("refY", 0)
    .attr("markerWidth", 6)
    .attr("markerHeight", 6)
    .attr("orient", "auto")
  .append("svg:path")
    .attr("d", "M0,-5L10,0L0,5");

var line = d3.svg.line()
    .x(function(d) { return d.x; })
    .y(function(d) { return d.y; })
    .interpolate("basis");

var links = [];
var paths = [];
var nodes = [].concat(states);

transitions.forEach(function(link) {
    var s = link.source,
        t = link.target,
        i1 = {},
        i2 = {};

    nodes.push(i1, i2);

    links.push({source: s, target: i1}, {source: i1, target: i2}, {source: i2, target: t});

    paths.push({ transition: link, path: [s, i1, i2, t] });
});

var force = d3.layout.force()
    .size([width, height])
    .nodes(nodes)
    .links(links)
    .on("tick", tick)
    .charge(-50)
    .start();

var links = svg.append("g").classed("links", true)
    .selectAll(".link").data(paths);

links.enter().append("g").classed("link", true)
    .call(function(g) {
        g.each(function(d) {
            d._id = "link-" + d.path[0].id + "-" + d.path[3].id;
        })
        g.append("path")
            .attr("id", function(d) { return d._id; })
            .attr("marker-end", "url(#end)")
            .style("stroke", "#ddd")

        g.append("text")
            .style("fill", "#ddd")
            .text(function(d) {
                var t = d.transition;
                var i = (t.inputs) ? t.inputs.join(",") + " -> " : "";
                var write = (t.write) ? t.write + ", " : "";
                var move = t.move || "";
                return i + write + move;
            })
    })

var nodes = svg.append("g").classed("nodes", true)
    .selectAll(".node").data(states);

nodes.enter().append("g").classed("node", true)
    .each(function(d, i) {
        if (i === 0) d3.select(this).remove();
    })
    .call(force.drag)
    .call(function(g) {
        g.append("circle")
        .attr({
            r: 7
        })
        .style({
            stroke: "black", "stroke-opacity": 0
        })
        g.append("text")
            .text(function(d) { return "q" + d.id; })
            .attr({
                y: 3
            })
    })

function tick() {

    links.select("path").attr("d", function(d) {
        return line(d.path);
    });

    links.select("text")
        .attr("x", function(d) {
            return (d.path[1].x + d.path[2].x) / 2;
        })
        .attr("y", function(d) {
            return (d.path[1].y + d.path[2].y) / 2;
        })

    nodes.call(setTransform);
}

function setTransform(selection) {
    selection.attr("transform", function(d) { return translate(d.x, d.y); })
}

function translate(x, y) {
    return "translate(" + x + "," + y + ")";
}

var initial_state = _.find(states, function(d) { return d.initial === true; });
var current_state = initial_state;

var tape_svg = d3.select("#tape")
    .attr("viewBox", "0 0 1000 4000");

var square_size = 1000 / _tape_length;

var x = d3.scale.ordinal();

var y = d3.scale.ordinal();

var tapes = [];
tapes.push(tape);

function run() {
    var _tape = tape.sort(function(a, b) { return d3.ascending(a.position, b.position) });
    var tape_length = _tape.length;

    x.domain(d3.range(tape_length))
        .rangeBands([0, tape_length * square_size]);

    y.domain(d3.range(tapes.length))
        .rangeBands([0, tapes.length * square_size]);

    var _tapes = tape_svg.selectAll(".tape-container").data(tapes);

    _tapes.enter().append("g").classed("tape-container", true)
        .attr("transform", function(d,i) { return translate(0, y(i)); })
        .call(function(g) {
            var squares = g.selectAll(".square").data(function(d) { return d; });

            squares.enter().append("g").classed("square", true)
                .attr("transform", function(d) { return translate(x(d.position), 0); })
                .call(function(g) {
                    g.append("rect")
                    .attr({
                        width: x.rangeBand(), height: x.rangeBand()
                    })
                    .style({
                        fill: function(d) {
                            var val = parseFloat(d.symbol);
                            if (val > 0) {
                                var color = d3.hsl(val * 360 + 200 % 360, 1, 0.7).toString();
                                return color;
                            } else {
                                return "white";
                            }
                        }
                    })

                    g.append("text")
                        .attr({
                            x: x.rangeBand()/2, y: x.rangeBand()/2, dy: "0.3em"
                        })
                });
        })

    var duration = 50;

    console.info("Current state: %s", current_state.id);
    if (current_state.accept === true) {
        console.info("Accepted.");
        d3.transition().duration(duration).selectAll(".node circle")
            .filter(function(d) {
                return d === current_state;
            })
            .duration(duration)
            .style("stroke-opacity", 1)
            .style("fill", "#cfc");
        return;
    }
    var current_symbol = head.symbol;
    var transitions_for_state = getStateTransitions(current_state);
    var matching_transition = getMatchingTransition(current_symbol, transitions_for_state);

    if (_.isUndefined(matching_transition)) {
        var e = "No matching transition for symbol " + current_symbol + " at state " + current_state.id;
        throw new Error(e)
    }

    var write_value = matching_transition.write;

    if (! _.isUndefined(write_value)) {
        head.symbol = write_value;
        var old_tape = tape.map(function(d) {
            return _.extend({}, d);
        });
        tapes.push(old_tape);
    }

    var direction = matching_transition.move;
    var current_position = head.position;
    var next_position = (direction === "L") ? current_position - 1 : current_position + 1;

    var next_square = getSquare(next_position);
    if (_.isUndefined(next_square)) {
        tape.push({ position: next_position, symbol: "_" });
        next_square = getSquare(next_position);
    }

    var t1 = d3.transition().duration(duration);

    t1.selectAll(".node circle")
        .filter(function(d) {
            return d === current_state;
        })
        .duration(duration)
        .style("stroke-opacity", 1)
        .transition().duration(duration)
        .style("stroke-opacity", 0);

    var t_square = t1.transition().duration(duration);

    var t_path = t_square.transition().duration(duration);

    t_path.selectAll(".link path")
        .filter(function(d) {
            return d.transition === matching_transition;
        })
        .duration(duration)
        .style("stroke", "red")
        .transition().duration(duration)
        .style("stroke", "#ddd");

    t_path.selectAll(".link text")
        .filter(function(d) {
            return d.transition === matching_transition;
        })
        .duration(duration)
        .style("fill", "black")
        .transition().duration(duration)
        .style("fill", "#ddd");

    var t_tape = t_path.transition().duration(duration);

    t_tape.each("end", function(d) {
            console.info("Head: %s", head.position);

            head = next_square;
            current_state = matching_transition.target;

            run();
        })


}

run();

function getMatchingTransition(symbol, transitions) {
    return _.find(transitions, function(t) { return _.contains(t.inputs, symbol); });
}

function getStateTransitions(state) {
    return transitions.filter(function(t) { return t.source === state; });
}

function getSquare(position) {
    return _.find(tape, function(d) { return d.position === position; });
}

function getState(id) {
    return _.find(states, function(d) { return d.id === id; });
}
</script>
</body>
</html>
	<html>
	<head>
	<link href='http://fonts.googleapis.com/css?family=Lato:100,400' rel='stylesheet' type='text/css'>
	<style>
	body {
	width: 100%;
	height: 100%;
	margin: 0;
	}
	main {
	display: flex;
	flex-direction: row;
	width: 80%;
	height: 90%;
	margin: 0 auto;
	padding-top: 10px;
	padding-bottom: 10px;
	}
	svg {
	width: 100%;
	height: 100%;
	}
	#tape {
	flex: 1 1 0;
	/border: 1px solid black;/
	}
	#turing {
	flex: 4;
	/border: 1px solid black;/
	}
	.square rect {
	/fill: none;/
	stroke: #ddd;
	}
	.square text {
	fill: #999;
	text-anchor: middle;
	font-family: 'Lato', sans-serif;
	font-weight: 100;
	font-size: 4em;
	}
	.node circle {
	fill: #ddf;
	/*stroke: black;
	stroke-opacity: 0;*/
	}
	.node text, .link text {
	fill: #333;
	text-anchor: middle;
	font-family: "Helvetica", sans-serif;
	font-weight: 100;
	}
	.node text {
	font-size: 0.4em;
	}
	.link text {
	font-size: 0.5em;
	}
	.link path {
	fill: none;
	/stroke: #999;/
	}
	#end path {
	/fill: #ccc;/
	}
	</style>
	</head>
	<body>
	<main>
	<svg id="tape">
	</svg>
	<svg id="turing">
	</svg>
	</main>

	<script src="//cdnjs.cloudflare.com/ajax/libs/d3/3.5.3/d3.min.js"></script>
	<script src="//cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>

	<script>
	var _tape_length = 30;

	var states = d3.range(7).map(function(d, i) {
	var obj = { id: i };
	if (obj.id === 1) obj.initial = true;
	if (obj.id === 3) obj.accept = true;
	return obj;
	});

	var tape = d3.range(_tape_length).map(function(d, i) {
	var obj = { position: i, symbol: "_" };
	if (i === 0) obj.symbol = 0;
	if (i === _tape_length - 1) obj.symbol = 1;
	return obj;
	});

	var transitions = [
	{ source: getState(0), target: getState(1) },
	{ source: getState(1), target: getState(4), inputs: [0, "_"], write: 0.9, move: "R" },
	{ source: getState(4), target: getState(1), inputs: [0, "_"], write: 0.75, move: "R" },
	{ source: getState(4), target: getState(2), inputs: [1], write: 0.6, move: "L" },
	{ source: getState(1), target: getState(2), inputs: [1], write: 0.6, move: "L" },
	{ source: getState(2), target: getState(5), inputs: [0.9, 0.75, 0.4, 0.6], write: 0.6, move: "L" },
	// { source: getState(2), target: getState(3), inputs: [0], move: "R"},
	{ source: getState(5), target: getState(6), inputs: [0.9, 0.75, 0.6], write: 0.4, move: "R"},
	{ source: getState(6), target: getState(2), inputs: [0.9, 0.75], write: 0.3, move: "L" },
	{ source: getState(6), target: getState(2), inputs: [0.4, 0.6], write: 0.1, move: "L" },
	{ source: getState(5), target: getState(3), inputs: ["_"], move: "R"},
	{ source: getState(6), target: getState(3), inputs: ["_"], move: "R"},
	{ source: getState(2), target: getState(3), inputs: ["_"], move: "R"},
	]

	var head = tape[0];

	var width = height = 300;

	var svg = d3.select("#turing")
	.attr({
	viewBox: "0 0 " + width + " " + height
	});

	svg.append("svg:defs").selectAll("marker")
	.data(["end"])
	.enter().append("svg:marker")
	.attr("id", String)
	.attr("viewBox", "0 -5 10 10")
	.attr("refX", 20)
	.attr("refY", 0)
	.attr("markerWidth", 6)
	.attr("markerHeight", 6)
	.attr("orient", "auto")
	.append("svg:path")
	.attr("d", "M0,-5L10,0L0,5");

	var line = d3.svg.line()
	.x(function(d) { return d.x; })
	.y(function(d) { return d.y; })
	.interpolate("basis");

	var links = [];
	var paths = [];
	var nodes = [].concat(states);

	transitions.forEach(function(link) {
	var s = link.source,
	t = link.target,
	i1 = {},
	i2 = {};

	nodes.push(i1, i2);

	links.push({source: s, target: i1}, {source: i1, target: i2}, {source: i2, target: t});

	paths.push({ transition: link, path: [s, i1, i2, t] });
	});

	var force = d3.layout.force()
	.size([width, height])
	.nodes(nodes)
	.links(links)
	.on("tick", tick)
	.charge(-50)
	.start();

	var links = svg.append("g").classed("links", true)
	.selectAll(".link").data(paths);

	links.enter().append("g").classed("link", true)
	.call(function(g) {
	g.each(function(d) {
	d._id = "link-" + d.path[0].id + "-" + d.path[3].id;
	})
	g.append("path")
	.attr("id", function(d) { return d._id; })
	.attr("marker-end", "url(#end)")
	.style("stroke", "#ddd")

	g.append("text")
	.style("fill", "#ddd")
	.text(function(d) {
	var t = d.transition;
	var i = (t.inputs) ? t.inputs.join(",") + " -> " : "";
	var write = (t.write) ? t.write + ", " : "";
	var move = t.move \|\| "";
	return i + write + move;
	})
	})

	var nodes = svg.append("g").classed("nodes", true)
	.selectAll(".node").data(states);

	nodes.enter().append("g").classed("node", true)
	.each(function(d, i) {
	if (i === 0) d3.select(this).remove();
	})
	.call(force.drag)
	.call(function(g) {
	g.append("circle")
	.attr({
	r: 7
	})
	.style({
	stroke: "black", "stroke-opacity": 0
	})
	g.append("text")
	.text(function(d) { return "q" + d.id; })
	.attr({
	y: 3
	})
	})

	function tick() {

	links.select("path").attr("d", function(d) {
	return line(d.path);
	});

	links.select("text")
	.attr("x", function(d) {
	return (d.path[1].x + d.path[2].x) / 2;
	})
	.attr("y", function(d) {
	return (d.path[1].y + d.path[2].y) / 2;
	})

	nodes.call(setTransform);
	}

	function setTransform(selection) {
	selection.attr("transform", function(d) { return translate(d.x, d.y); })
	}

	function translate(x, y) {
	return "translate(" + x + "," + y + ")";
	}

	var initial_state = _.find(states, function(d) { return d.initial === true; });
	var current_state = initial_state;

	var tape_svg = d3.select("#tape")
	.attr("viewBox", "0 0 1000 4000");

	var square_size = 1000 / _tape_length;

	var x = d3.scale.ordinal();

	var y = d3.scale.ordinal();

	var tapes = [];
	tapes.push(tape);

	function run() {
	var _tape = tape.sort(function(a, b) { return d3.ascending(a.position, b.position) });
	var tape_length = _tape.length;

	x.domain(d3.range(tape_length))
	.rangeBands([0, tape_length * square_size]);

	y.domain(d3.range(tapes.length))
	.rangeBands([0, tapes.length * square_size]);

	var _tapes = tape_svg.selectAll(".tape-container").data(tapes);

	_tapes.enter().append("g").classed("tape-container", true)
	.attr("transform", function(d,i) { return translate(0, y(i)); })
	.call(function(g) {
	var squares = g.selectAll(".square").data(function(d) { return d; });

	squares.enter().append("g").classed("square", true)
	.attr("transform", function(d) { return translate(x(d.position), 0); })
	.call(function(g) {
	g.append("rect")
	.attr({
	width: x.rangeBand(), height: x.rangeBand()
	})
	.style({
	fill: function(d) {
	var val = parseFloat(d.symbol);
	if (val > 0) {
	var color = d3.hsl(val * 360 + 200 % 360, 1, 0.7).toString();
	return color;
	} else {
	return "white";
	}
	}
	})

	g.append("text")
	.attr({
	x: x.rangeBand()/2, y: x.rangeBand()/2, dy: "0.3em"
	})
	});
	})

	var duration = 50;

	console.info("Current state: %s", current_state.id);
	if (current_state.accept === true) {
	console.info("Accepted.");
	d3.transition().duration(duration).selectAll(".node circle")
	.filter(function(d) {
	return d === current_state;
	})
	.duration(duration)
	.style("stroke-opacity", 1)
	.style("fill", "#cfc");
	return;
	}
	var current_symbol = head.symbol;
	var transitions_for_state = getStateTransitions(current_state);
	var matching_transition = getMatchingTransition(current_symbol, transitions_for_state);

	if (_.isUndefined(matching_transition)) {
	var e = "No matching transition for symbol " + current_symbol + " at state " + current_state.id;
	throw new Error(e)
	}

	var write_value = matching_transition.write;

	if (! _.isUndefined(write_value)) {
	head.symbol = write_value;
	var old_tape = tape.map(function(d) {
	return _.extend({}, d);
	});
	tapes.push(old_tape);
	}

	var direction = matching_transition.move;
	var current_position = head.position;
	var next_position = (direction === "L") ? current_position - 1 : current_position + 1;

	var next_square = getSquare(next_position);
	if (_.isUndefined(next_square)) {
	tape.push({ position: next_position, symbol: "_" });
	next_square = getSquare(next_position);
	}

	var t1 = d3.transition().duration(duration);

	t1.selectAll(".node circle")
	.filter(function(d) {
	return d === current_state;
	})
	.duration(duration)
	.style("stroke-opacity", 1)
	.transition().duration(duration)
	.style("stroke-opacity", 0);

	var t_square = t1.transition().duration(duration);

	var t_path = t_square.transition().duration(duration);

	t_path.selectAll(".link path")
	.filter(function(d) {
	return d.transition === matching_transition;
	})
	.duration(duration)
	.style("stroke", "red")
	.transition().duration(duration)
	.style("stroke", "#ddd");

	t_path.selectAll(".link text")
	.filter(function(d) {
	return d.transition === matching_transition;
	})
	.duration(duration)
	.style("fill", "black")
	.transition().duration(duration)
	.style("fill", "#ddd");

	var t_tape = t_path.transition().duration(duration);

	t_tape.each("end", function(d) {
	console.info("Head: %s", head.position);

	head = next_square;
	current_state = matching_transition.target;

	run();
	})


	}

	run();

	function getMatchingTransition(symbol, transitions) {
	return _.find(transitions, function(t) { return _.contains(t.inputs, symbol); });
	}

	function getStateTransitions(state) {
	return transitions.filter(function(t) { return t.source === state; });
	}

	function getSquare(position) {
	return _.find(tape, function(d) { return d.position === position; });
	}

	function getState(id) {
	return _.find(states, function(d) { return d.id === id; });
	}
	</script>
	</body>
	</html>