Turtle graphics (JavaScript)

From LiteratePrograms

A small web-browser hosted turtle graphics language:

Turtle graphics are one of the best known features of Logo. Although originally, turtle graphics were produced mechanically by robotic turtles, the best known variety is the software simulation. As an educational tool, the turtle is often fondly remembered, perhaps because it took the rather abstract notion of programming as implementing arbitrary algorithms with a sequence of instructions manipulating the limited state of a computer, and modelled it with the concrete notion of drawing arbitrary pictures with a sequence of instructions manipulating the limited state of a turtle.

Contents 1 Theory 2 Practice 2.1 Parser 2.2 Interpreter 2.3 System dictionary 3 Wrapping up

Theory

The approach is direct: we parse the source expression to form a program tree, which we then interpret to produce graphical output.

This results in a classic hylomorphism: the parsing is an anamorphism which takes the implicit structure in a text string and unfolds it into an explicitly structured parse tree, while the interpretation is a catamorphism which takes the explicitly structured parse tree and folds it into an implicitly structured vector graphic.

Both the parser and interpreter are very simplistic; they mainly take care of the ancillary details needed to map a string of source text to a sequence of function applications from the system dictionary, which draw the graphics onto a blank canvas. The most complicated aspect is due to the fact that we have taken the unusual approach of implementing a reversible turtle, whose plans can be run either forwards or backwards, and hence we need to provide for interpretation in both directions. (See inverse and under).

Practice

Caveat: the author is not in the habit of writing JavaScript — as one can write FORTRAN in any language, this may be very non-idiomatic.

Parser

The parser is rather minimal. tokens takes a source string, and tokenizes it into a list of open-brackets, close-brackets, and source words. tree then takes this list and produces a nested list-of-lists according to the bracketing. Composing the two recovers the tree form of the source expression. tree o tokens :: string → [[token]]

Nothing fancy, but as long as one is not concerned with decent error recovery, it suffices.

<<parser>>=
function tokens(s) { return s.replace(/([\[\]])/g," $1 ").split(/\s+/) }
function tree(v)
{
  var t = []
  v.nxt = function() { return this.length ? this.shift() : ']' }
  for(var e = v.nxt(); e != ']'; e = v.nxt()) { t.push(e == '[' ? tree(v) : e) }
  return(t)
}

Interpreter

The interpreter is simplistic as well. interp and donext walk along the top-level list of tokens, using checkop to map each token into an action function which we evaluate by calling it with the graphics context (ctx) as an argument and the remaining token tree (v) as a continuation. (checkarg is the equivalent of checkop when we wish to evaluate a list element directly as a (list of) token(s), not as an action function) The fancier way of saying this is to note that these action functions are endofunctors on and hence interp takes a token tree to a value in the turtle monad. interp :: [[token]] → Turtle picture

Again, the simplicity comes at the cost of error handling.

<<interpreter>>=
function checkarg(e) { return (plan[e] || e) }
function checkop(e)  { return (dict[e] || user[e] || ignore) }
function ignore(ctx, v) { }
function donext(ctx, v) { checkop(v.shift())(ctx,v) }
function interp(ctx, v) { for(v = codevec(v); v.length; donext(ctx,v)); }

Note that checkop looks up words in the system dictionary first, then checks for user definitions. There are no system level plans, so checkarg simply looks up plans in the user dictionary, or returns literals as-is. These dictionaries are the major data structure of, and contain almost all of the behavior for, this interpeter — which is why up to now everything has been rather straightforward. Before we get into the dictionaries themselves, though, we will attach some convenience functions to the token trees passed as continuations:

• sarg extracts a scalar argument, peeling it off the head of the continuation.
• varg expects to find a list argument instead of a scalar, but otherwise behaves like sarg.
• call, like its machine-level equivalent, inserts a new continuation before the current one.

<<vm>>=
function codevec(l)
{
  var v = l.slice(0)
  v.sarg = function() { return checkarg(this.shift()) }
  v.varg = function() { return [].concat(this.sarg()) }
  v.call = function(l) {
		for(var w = codevec(l); w.length; this.unshift(w.pop())); }
  return v
}
var plan = {}	// source tokens for user-defined words
var user = {}	// functions for user-defined words
var dict = {	// functions for system-defined words
system dictionary
}
inverter

System dictionary

At last, after all that preparation, we reach the heart of the interpreter: the definitions of the system functions. So far we have mostly been shuffling symbols around; this is where the real work gets down. The <canvas> tag graphics state manipulation functions and the codevec convenience functions provide a small virtual machine which these words manipulate.

<<system dictionary>>=
'pen':		function(ctx,v) { ctx.penState = !ctx.penState },
'mirror':	function(ctx,v) { ctx.scale(1,-1) },
'reverse':	function(ctx,v) { ctx.scale(-1,1) },
'turn':		function(ctx,v) { ctx.rotate(v.sarg()*3.1415926/180) },
'forward':	function(ctx,v) { ctx.translate(v.sarg(),0); ctx.displace() },
'scale':	function(ctx,v) { 
			var sc = v.sarg()
			ctx.lineWidth /= sc
			ctx.scale(sc,sc)
				},
'repeat':	function(ctx,v) { 
			var n  = v.sarg()
			var rv = v.varg()
			if(n < 0)	{ n = -n; rv = invert(rv) }
			while(n--)	{ interp(ctx, rv) }
			/////////////////////
			// if(n == 0)	return
			// v.call(rv.concat(['repeat',n-1,rv]))
			/////////////////////
				},
'poly':		function(ctx, v) {
			var n  = v.sarg()
			var a  = 360/(n<0?-n:n)
			v.call(['repeat',n,v.varg().concat(['turn',a])]) },
'def':		function(ctx,v) {
			var name = v.shift()
			plan[name] = v.varg()
			user[name] = function(ctx,v) { v.call(plan[name]) }
				},
'inverse':	function(ctx,v)	{ v.call(invert(v.varg())) },
'identity':	function(ctx,v) { v.call(       v.varg() ) },
'under':	function(ctx,v) {
			var av = v.varg()
			var uv = v.varg()
			v.call(av.concat(uv.concat(invert(av))))
				},
'within':	function(ctx,v)	{
			var av = v.varg()
			var wv = v.varg()
			v.call(av.concat(wv.concat(av)))
				},
'flip':		function(ctx,v) {
			var fn = v.sarg()
			var bv = v.varg()
			var av = v.varg()
			v.call([fn,av,bv])
				},
'':		ignore

Almost as complex is invert: the code that, given a plan (ov) in the form of a token tree, does a little symbol-shuffling to produce the token tree (nv) coding for the plan run in reverse.

• pen,mirror, and reverse are their own inverses.
• turn, forward, scale, repeat, and poly merely need their scalar argument inverted appropriately.
• inverse and identity are inverses of each other.
• the higher order functions, under and within, must apply invert recursively
• flip and user definitions merely iterate invert on their expansions

<<inverter>>=
function invert(ov)
{
  var ov = codevec(ov)
  var nv = []
  while(ov.length)  {
    var e = ov.sarg()
    switch(e)  {
    case 'pen':
    case 'mirror':
    case 'reverse':
      nv.unshift(e)
      break
    case 'turn':
    case 'forward':
      nv = [e,-ov.sarg()].concat(nv)
      break
    case 'scale':
      nv = [e,1/ov.sarg()].concat(nv)
      break
    case 'repeat':
    case 'poly':
      var c  = ov.sarg()
      var ev = ov.varg()
      nv = [e,-c,ev].concat(nv)
      break
    case 'inverse':
      nv = ['identity',ov.varg()].concat(nv)
      break
    case 'identity':
      nv = ['inverse',ov.varg()].concat(nv)
      break
    case 'under':
      var av = ov.varg()
      var uv = ov.varg()
      nv = [e,av,invert(uv)].concat(nv)
      break
    case 'within':
      var av = ov.varg()
      var wv = ov.varg()
      nv = [e,invert(av),invert(wv)].concat(nv)
      break
    case 'flip':
      var fn = ov.sarg()
      var bv = ov.varg()
      var av = ov.varg()
      e = [fn,av,bv]
      // fall through
    default:
      return invert(e.concat(ov)).concat(nv)
    }
  }
  return nv
}

Wrapping up

Now we provide a driver that will manipulate elements in a given web page (as well as provide platform workarounds).

Note that the driver is the only portion of this implementation that deals in absolute coordinates. Something must, because we want to start the turtle in a known state at the midpoint of the canvas — the terrapin station.

<<driver>>=
function turtle(t,c)
{
  /////////////////////////
  if(document.getElementById("kludge").checked)	{
    dict['forward'] = function(ctx,v)	{
	var x = v.sarg()
	if(ctx.penState)	{
		ctx.beginPath()
		ctx.moveTo(0,0)
		ctx.lineTo(x,0)
		ctx.stroke()
	}
	ctx.translate(x,0)
    }
  } else {
    dict['forward'] = function(ctx,v) {
	ctx.translate(v.sarg(),0); ctx.displace() }
  }
  /////////////////////////
  var txt = document.getElementById(t)
  var cvs = document.getElementById(c)
  var src = txt.value
  var ctx = cvs.getContext("2d")
  ctx.save()
  ctx.clearRect(0,0,cvs.width,cvs.height)
  ctx.translate(cvs.width/2,cvs.height/2)
  ctx.beginPath()	// start track display
  ctx.moveTo(0,0)
  ctx.penState = 1
  ctx.displace = function() { this.penState ? ctx.lineTo(0,0)
					    : ctx.moveTo(0,0) }
  plan = {}
  user = {}
  interp(ctx, tree(tokens(src)))
  ctx.stroke()		// show the track
  ctx.beginPath()	// start turtle display
  ctx.moveTo(0,-5)
  ctx.lineTo(20,0)
  ctx.lineTo(0, 5)
  ctx.closePath()
  ctx.fill()		// show the turtle
  ctx.restore()
}
function init() { document.getElementById("kludge").checked = !!window.opera }

Finally, we create a web page embedding the source and output windows, as well as some sample turtle programs and documentation.

<<terrapin.htm>>=
<html><head>
<title>a buggy concatenative turtle</title>
<!-- 20070131 [DL] swap renamed flip.  improve tokenization -->
<!-- 20060822 [DL] lame kludge for Opera 9.01 -->
<!-- 20060820 [DL] written -->
<script type="text/javascript"><!--
<<vm>>
<<interpreter>>
<<parser>>
<<driver>>
//--></script>
<style type="text/css">
body	 { font-family: arial; font-size: 10pt;
	   background-color: #CCC; color: #000; }
h1	 { font-size: 14pt; }
canvas   { background-color: #EEE; }
textarea { background-color: #EEE; }
.doc	 { float: right; border: 1px solid #000; background-color: #FEC; }
</style></head><body onLoad="init();turtle('txt','cvs')">
<h1>a buggy concatenative turtle <i>(mobilis terrapin)</i></h1>
<canvas height=256 width=256 id="cvs" onClick="turtle('txt','cvs')"></canvas>
<button onClick="turtle('txt','cvs')"><< draw </button>
<textarea cols=60 rows=20 id="txt" onPaste="turtle('txt','cvs')">
def jog [ forward 30 under [ turn 45 ] [ forward 10 ] ]
def joggle [ under jog reverse reverse ]
poly 16 [ poly 4 joggle ]
</textarea>
<p>Requires javascript and <canvas> support <small> (Safari,Opera,Firefox?)</small>.  Userproofing not included.</p>
<p>My Opera can't hack matrix changes while drawing — if you don't see any output, enable
<label for="kludge"> the
<input id="kludge" type="checkbox" onClick="turtle('txt','cvs')"/>
bletcherous kludge</label></p> 
<hr>
<div class="doc">
<table>
<tr><td>pen             </td><td> toggle pen up/down</td></tr>
<tr><td>mirror		</td><td> toggle left/right</td></tr>
<tr><td>reverse		</td><td> toggle forward/back</td></tr>
<tr><td>turn X		</td><td> rotate X degrees</td></tr>
<tr><td>forward X	</td><td> translate X units</td></tr>
<tr><td>scale X		</td><td> multiply unit size</td></tr>
<tr><td></td></tr>
<tr><td>repeat N [ ]	</td><td> repeat a plan N times</td></tr>
<tr><td>poly N [ ]	</td><td> repeat with implicit turning</td></tr>
<tr><td>within [ ] [ ]	</td><td> sandwich a plan<br>(within a b == a b a)</td></tr>
<tr><td></td></tr>
<tr><td>inverse [ ]	</td><td> produce the opposite of a plan <br>(inverse a == a<sup>-1</sup>)</td></tr>
<tr><td>under [ ] [ ]	</td><td> make a do/undo sandwich<br>(under a b == a b a<sup>-1</sup>)</td></tr>
<tr><td></td></tr>
<tr><td>flip NAME	</td><td> switch argument order<br>(flip f b a == f a b)</td></tr>
<tr><td>def NAME [ ]	</td><td> define a subplan<br>(sorry, no arguments)</td></tr>
</table>
</div>
repeat 4 [ forward 100 turn 90 ]<br>
<hr>
poly 6 [ poly 36 [ reverse pen forward 20 ] ]<br>
<hr>
def spot [ poly 6 [ forward 10 ] ]<br>
def arm [ under [ forward 70 turn -60 ] ]<br>
poly 12 [ arm spot ]<br> 
<hr>
def coil [ repeat 300 [ turn 5 forward 5 scale .99 ] ]<br>
def branch [ flip under [ ] ]<br>
poly 2 [ branch coil ]<br>
<hr>
def jog [ forward 30 under [ turn 45 ] [ forward 10 ] ]<br>
def joggle [ under jog reverse reverse ]<br>
poly 6 [ poly 5 joggle ]<br>
<hr>
def t [ turn 90 ]<br>
def f [ forward 60 ]<br>
def h [ forward 30 ]<br>
def x [ under [ under t f ] h ]<br>
<br>
def u [ under t f h ]<br>
def q [ under [ repeat 2 u ] ]<br>
def w [ under [ repeat 1 u ] ]<br>
def e [ under [ repeat 0 u ] ]<br>
<br>
poly 4 [ q [<br>
poly 4 [ w [<br>
poly 4 [ e [ <br>
x inverse x<br>
] ] ] ] ] ]<br>
</body> </html>

The web page defaults to the lotus-like program displayed at the beginning of this article.

Download code