Wednesday, November 10, 2021

Map Compasses (Part 3): A Minimal CDL Interpreter

Welcome back to my blog series on implementing procedurally-generated map compasses!  You may recall that by the end of the previous blog post I had a parser in Nearley that could recognize compass descriptions consisting of two commands:  CIRCLE and SPACE.   Given the description 'SPACE(10) CIRCLE(1.5, "black", "none")' our parser confirms this is legal and returns a parse tree with two items at the top-level, corresponding to the SPACE and the CIRCLE commands.  That's nice, but how does it get us closer to drawing a circle?

The commands I've created actually look something like Javascript function calls.  If I had a Javascript function called “CIRCLE" that drew a circle I could just about execute the CIRCLE command as soon as it was parsed and recognized.  And in fact Nearley provides you the capability to do that.  To any Nearley rule, you can attach some Javscript to be executed when the rule is (successfully) completed.  So I can take the CIRCLE rule:

circleElement -> “CIRCLE" “(" decimal “," dqstring “," dqstring “)"

and augment it with some Javascript that should be run when the rule is complete: 

circleElement -> “CIRCLE" “(" decimal “," dqstring “," dqstring “)" {% CIRCLE(data) %}

The Javascript to be run is enclosed in “{%" and “%}" and must be a function that takes a single argument.  In this case, I'm calling a Javascript function called CIRCLE and passing in “data" as an argument.  What's this “data" thing?  It's the parse tree result for this rule.  In this case, it's an array with 8 items.  The first item is the string “CIRCLE".  The second item is the string “(".  The third item is the string that matched the “decimal" rule.  And so on.  So the CIRCLE Javascript function could use that data array to decide how to draw the circle and draw it right as the description of the circle is parsed.  If I extended that to all parts of our language, I could draw the complete compass as the CDL description was being parsed in Nearley.

That's pretty cool, but there are a couple of reasons I don't want to draw that way.  First of all, the kind of Javascript allowed in the post-processing step of Nearley rules is pretty limited.  For example, I probably want to draw that circle in a particular page element but there isn't any easy way to pass in that information.  Second, I would be limited to drawing routines that are neatly encompassed in a single Nearley rule.  Doing something like saving a color and reusing it later would be difficult.

A more flexible approach is to use the post-processing to translate into an “intermediate" language -- some kind of data structure that's easier to use than text -- and then have an interpreter that translates from the intermediate language into a drawing.  For the intermediate language I'm going to use a Javascript object for each CDL command and I'll fill the object in with an operation type and the parsed arguments.

 circleElement -> “CIRCLE" “(" decimal “," dqstring “," dqstring “)"
{% data => ({op: “CIRCLE", lineWidth: data[2], lineColor: data[4], fillColor: data[6]}) %}

So now I have a Javascript arrow function that takes the parse result from this rule and uses it to fill in a Javascript object.  Nearley will now return this object instead of the parse result.  Once I've done this for all the commands in the Compass Description Language the parser will return a list of parsed objects instead of the parse tree.

The rule for the space command is straightforward:

spaceElement -> “SPACE" “(" decimal “)" {% data => ({op:SPACE, n: data[2]}) %}

There's one more change that I need to make in the top-level rule, mostly for convenience:

compassBG -> BGelement:+ {% data => data[0].map(a => a[0]) %}

Without this fix, every object is returned as an array of a single element.  (In general, there might be multiple return values for every rule, but this grammar always has only one.)  This strips off all those unnecessary arrays. 

With these changes in place, when I run the parser the result is in the intermediate language -- an array of objects:

Okay, we have a program!  Now we need an interpreter.

An interpreter is a computer program that takes a computer program in a (usually) different language and interprets it, i.e., makes the program do what it is supposed to do.  Of course writing an interpreter for a language like Javascript is a difficult undertaking, but CDL is a very simple language and I'll be able to write a very simple interpreter.

A program in CDL is just a list of objects, so at a high level the interpreter will just be a loop that runs through the list of objects and interprets each object based upon the operation:

function interpretCDL(cdl, debug=false) {
    for(let i=0;i<cdl.length;i++) {
	const op = cdl[i].op;
	if (op == 'CIRCLE') {
	    // Draw a circle
	    if (debug) console.log('Draw a circle.');
	} else if (op == 'SPACE') {
	    // Skip some space
	    if (debug) console.log('Skip some space.');
	} else {
	    console.log('executeCDL encountered an unknown opcode: '+op);
	};
    };
};

This doesn't do much yet, but it's enough code to test out.  I'll modify the code on the Test button so that it passes the parsed CDL to the interpreter.

function test() {
    console.log('About to test.');
    const result = interpretCDL(parseCDL('SPACE(10) CIRCLE(1.5, "black", "none")', true), true);
};

And here's the result:

So we've taken a simple program in CDL, parsed it and interpreted it!

That's all fine, but eventually we're going to want to do more than print log messages to the console, so let's work on setting up an area to draw to the screen.  There are basically two steps to this:  (1) establish an element on the web page to hold the drawing, and (2) get a pointer for this element to the Javascript program.

To draw in SVG, you need to have an <SVG> element in the web page.  I've already done this in the test.html page in the repository:
      <div id="map" style="margin-left:10px;">
	<svg id="svg" width="500" height="500"></svg>
      </div>

The basic structure of test.html is stolen from Dragons Abound.  There's a column along the left side of the web page that is reserved for controls like the Test button, and the remainder of the page is the “map" area and is filled with a 500x500 SVG.

To pass the SVG element into the Javascript requires some more work in the HTML file for the web page.  That part looks like this:

    <script type="module">
      import Compass from './compass.js';
      var testButton = document.getElementById("testButton");
      var svg = d3.select("#svg");
      testButton.onclick = function () {
	  Compass.test(svg); };
    </script>
I've used the HTML <script> tag to add Javascript to the web page.  After importing the compass code, I use getElementById() to get a pointer to the Test button.  getElementById() is a function that walks through HTML to find an HTML element with the specified name.  In this case, the “document" variable refers to the current web page, so document.getElementById() searches the current web page to find a named element.   Once I've found the Test button I can attach the test function from my compass code to the button so that it runs when the button is clicked.

For the SVG element I do something a little bit different.  Here I use the D3 select function to find the SVG element.  This returns a D3 selection instead of the actual SVG element.  D3 is a fantastic Javascript library that makes working with SVG much simpler than trying to manipulate the SVG directly.  D3 is really intended for making data visualizations, not fantasy maps.  I'm using it largely because I started years ago with Martin O'Leary's mapmaking code, and he used D3 so I did too.  But I've found it useful enough to stick with it.

Lastly, let's check to make sure the SVG is working (and demonstrate how D3 eases using SVG).  I'll add some code to draw a purple circle to the test function.  That looks like this:
    svg.append('circle')
	.attr('cx', 25)
	.attr('cy', 25)
	.attr('r', 25)
	.style('fill', 'purple');
D3 adds methods to SVG selections, so adding new elements to the SVG is a simple as appending the proper object type and setting attributes and styles as necessary.
And that's all it takes.

A reminder that if you want to follow along from home, you need to download the Part 2 branch from the Procedural Map Compasses repository on Github and get the test web page up and open the console.  Part 1 of this series has more detailed instructions, but the short version (on Windows) is to double-click mongoose-free-6.9.exe to start up a web server in the Part 3 directory, and then select the test.html link.  You can also try out this code on the web at https://dragonsabound-part3.netlify.app/test.html although you'll only be able to run the code, not modify it.

Next time I'll start implementing the interpreter routines for the CDL commands.

Suggestions to Explore

  • The printed output of the CDL parser isn't very useful because the returned values just print as “[object Object]".  Write a function to “pretty print" the CDL objects in some format that shows the operation name, e.g., “{CIRCLE op}" and use this to improve the debug output.

  • Read about D3 and see if you can add lines to the purple circle from the center out to 12 o'clock, 3 o'clock, 6 o'clock and 9 o'clock.

  • The if-then-else at the heart of the interpreter exists to associate the operation name (e.g., SPACE, CIRCLE) with the code to implement that operation.  Another way to go from a string to an associated value in Javascript is to build an object that you use as a code dictionary:
    let code = {'CIRCLE': function () { console.log('Draw a circle.'); },
                'SPACE': function () { console.log('Skip some space'); } };
    
    Modify interpretCDL() to use a code dictionary as above.  What are the advantages / disadvantages of this approach compared to the if-then-else approach?


No comments:

Post a Comment