Dec 21, 2012

A simple turtle graphics Domain Specific Language (DSL) parser

I've been working through some of the exercises in 'The Pragmatic Programmer' while using it to mentor a colleague.  In particular, I spent a bit of time working on the Domain Specific Language section and considering creating little DSLs to provide flexible control. I've painfully implemented DSLs in SystemVerilog/ UVM sequences in the past and thought about how I typically do this: build a parser, create tokens, then dispatch various execution functions to implement the commands.  Often, the pain of building all these pieces in a language like C or SV is enough of a barrier that I wouldn't even start.  

The example in the book is a simple Logo/ Turtle control language.  Pen up, Pen down, draw, turn, etc. It tries to simplify things by using single letter command codes and only one optional argument.

P 2


W 2

N 1

E 1 

S 1


I know Python has a Logo/ Turtle engine built in so I decided to try to write a command parser/ dispatcher that would work with that, and let me write commands in a text file and have them execute Python Turtle commands.

Here's an example script (you can see the results of this at the end of this post):

color "green"
goto 0 -50 # comments are allowed
circle 50
color "red"
write "Done!"
sleep 2

I thought initially about having to parse out all the commands and arguments, then writing a large switch/ case statement (or the Python equivalent with a dictionary).  After thinking about it a little longer I realised I didn't have to do that at all.  I could use the Introspection in Python to look up available methods and if they exist, call them. In fact, as not finding the method will just cause an exception, I can just try executing any command and if it fails, catch it and move on.

So after parsing the input text stream (throw away comments, break up tokens using whitespace) then I just try to execute the command in the global namespace.  I've pulled all the turtle functions into that namespace, so any turtle function is a valid command in my little parser.  The globals()[command[0]] in the code below looks up the function in the global namespace and then calls it, using the other parts of the command (command[1:]), after they've each been processed through the Python eval function to convert them from strings to whatever format they happen to be (numbers or strings mainly).  The final trick in this is using the * operator to take take a list and pass it as one argument after another to the function:

globals()[command[0]](*(map(eval, command[1:])))

And that's all that's needed to implement a full Logo language parser and execution engine. The command syntax is fault tolerant and reports errors, with line numbers.  New commands can be added easily, by defining new functions.  They'll be automatically supported as they are added to the namespace.

Being able to pull something like this together quickly means that writing little Domain Specific Languages is possible and quite a low bar.  Doing something similar in C is often more daunting and even worse in a language like SystemVerilog, with such a poor string and file handling library.  There's a real value in being able to program at such a high level, that can greatly enhance what's possible or likely to be attempted in a verification environment. You could do this in SystemVerilog, but how often would you even think to attempt it, without rejecting it as too much work?


# pull all the turtle commands into the global namespace, so they are valid commands
from turtle import *

# Use these 3 lines to make 'sleep' and 'exit' useable commands
from time import sleep
from sys import exit, argv

# Given a handle to a series of strings of commands, do them
def parse_and_draw(commands):
    for (line_number, line) in enumerate(commands):
        line = line.split('#')[0]  # throw away comments

        if line:  # if there is anything left after getting rid of comments

            command = line.strip().split(' ')  # parse using spaces to delimit tokens  
                                               # a big limitation of this, we can't have strings with spaces
                                               # e.g.,  "hello world" won't work as it'll get split up
                                               # into ['"hello', 'world"'] neither of which bits are valid when eval'ed

            if command[0]:  # if we have any command left 
                            # (e.g., an indented comment would dissappear)

                    # The meat of the dispatcher is the next line
                    # using a try/ except means we can always try to run any command
                    # and assume that it is valid and catch if it isn't.
                    # globals() returns a dictionary of every function defined in the global namespace
                    # including all the turtle commands because of the from turtle import *
                    # command[0] is used as a key to look up the function name
                    # we then pass all of the other tokens (command[1:]) through eval (using map)
                    # and pass them as arguments to the function we looked up

                    globals()[command[0]](*(map(eval, command[1:])))

                    # a key error occurs if we don't find command[0] in the global namespace
                except KeyError:
                    print 'Unknown command', command[0], 'on line ', line_number

                    # Some other error occurred (e.g., the called function raised an Exception)
                    # report it here and continue on (if we didn't catch it, the program would end)
                except Exception as e:
                    print 'Invalid command', command[0], 'on line ', line_number,  e

if __name__ == '__main__':
    # open the first file on the command line, get commands from that and run them
    commands = open(argv[1]).xreadlines()

    # note that the parse and draw routine works on a list of commands, it doesn't know about files
    # or anything else.  This seperation is is useful, as we can get commands from anywhere


12:21:12 10:37 AM

There are comments.

Feb 23, 2009

the death of books

ghost rider

The reports of my death are greatly exaggerated

- Mark Twain

It seems that some universities are moving away from physical books, switching entirely to electronic textbooks. My initial reaction is that this is just a little bit crazy. Electronic reference materials have a place, but I have a real difficulty with only electronic textbooks as being the best approach. Certainly there is a financial justification and a reduction in the physical weight the students have to carry. There is no doubt an advantage for the book stores, having to carry less physical inventory and ship it around the country.

But none of this takes into account how you interact with a physical book. It just isn't the same having the material online or on a PDF in a laptop. A screen is harder to read (a good laptop screen is still less than 100dpi, books and print are 300dpi or more) and as it is a lower resolution than printed material, you can only see a small amount of the information at a time. Diagrams and accompanying text are often hard to see all in one place. This is part of the reason why reading on a screen can be so tiring. Also the backlit text is harder on the eyes than reading from a page. The second drawback is how you physically interact with a book - flicking quickly through pages, marking pages with a highlighter, inserting post-it notes, curling up in a chair to read a book, spreading several books and notes out across a table. All of these metaphors may eventually be replaced with digital analogues that are as powerful or more so, but it seems we are quite far from that time.

The Amazon Kindle is probably about as good as this gets just now and from what I can tell, it still falls far below a good hunk of printed tree. The Kindle does have a higher resolution screen, which helps with reading for a long time, but the screen is small and the navigation feels clunky. Laptops are worse.

I do find a lot of value in online reference books. I've had a subscription to O'Reilly's Safari for over a year now and have found it to be invaluable, particularly when traveling. I can have access to a variety of reference texts, easily searchable, almost always available (if you have an internet connection). However, I've never been able to read any of the books I have on my Safari subscription, for more than a few pages. It just doesn't seem to work for me. No doubt I'm destined to become a relic in my views on reading, but it seems that we approach reading on a screen differently to a book. I'd love to have some sort of larger Kindle device, linked to a Safari subscription. Some way to really read those books on Safari, rather than just treating them as reference works. It always feels that this is just right around the corner, yet we never quite get there.

There are comments.

Feb 16, 2009

edward tufte and presenting data


I was lucky enough to attend a seminar from Edward Tufte, a couple of weeks ago, on the Presentation of Data and Information. Edward Tufte is probably best known for the book 'The Quantitative Display of Visual Information' and was an engaging and entertaining presenter. He has a very different style from the normal Powerpoint-driven presentation approach. In fact, much of his work is railing against the uses and abuses of Powerpoint and similar slide techniques.

The main take-away I got from the whole day was that if you have to communicate complicated data sets or information, that you really need to consider how people will use and interact with the data first. Too often, we go straight to presentation software and start trying to work out how to express the information in slides, rather than taking the time to consider if there are other, better ways to impart the information. Tufte was very keen on the concept of a 'super-graphic' which is a data rich, high resolution physical handout that lets participants see and consider a lot of data at once. A map is a great example of a super-graphic, or the weather page in a typical newspaper. A key part of this is that paper is much higher resolution than a typical computer screen (72dpi to 600dpi means you can show a whole lot more data in the same space). This is why multiple display screens are really useful for serious work. It also means that printing out and sharing data is a great way to get information infront of people in a meeting, rather than drip feeding it from slides)

I compare this idea to another guide I saw in the same week on creating powerpoint presentations that admonishes that there should never be more than 8 numbers on any slide or graphic. Tufte's response to this was repeatedly 'when did we become so stupid, just because we walked into a business meeting?' People handle large, complex data displays every day in the real world. People read and study sports scores in a newspaper, or financial reports without any trouble at all.

Let the data drive the presentation format, rather than the presentation software drive how the data is displayed.

There are comments.