portable perspectives

a blog about programming, life, universe and everything

Writing a Shakespeare interpreter with Parrot

During the winter holidays I thought it would be fun to start learning something more about Parrot, and see how hard it would be to write an interpreter using it.

I thought that it could been nice to try implementing something simple but fun, and so I decided to try with the Shakespeare Programming Language (SPL).

Shakespeare is a beautiful language, as you can see from the code for printing fibonacci's numbers and the task proved interesting. Since parrot provides tools to generate a language skeleton it was damn fast to be up and running.

Parsing

Writing the grammar with PGE is pretty easy, for example this is the code to parse constants in the form "a pretty lady"

rule immediate {
  <article>? [<adjective> ]* <noun> {*} 
}
token noun {
  |<positive_noun>
  |<negative_noun>
  |<neutral_noun> 
  |<nothing>
}

token adjective {
  |<positive_adjective>
  |<neutral_adjective>
  |<negative_adjective>
  |<first_person_possessive>
  |<second_person_possessive>
  |<third_person_possessive>
}

(the grammatical parts (nouns, adjectives etc) were easily generated from a script and some wordlists)

The only problem was understanding that rules and tokens in PGE have the "ratchet" property of never backtracking and that longest-token-matching is (still?) not working in PGE. This mean that for example the string "an empty house" would not parse correctly when the adjective rule is ['a' | 'the' | 'an'] because 'a' would match and the rule would never backtrack. Some reordering fixed the issue.

Generating the AST is again pretty easy: you basically associate a callback method in the actions file to each rule that you want to transform and use the standard PAST::* classes to generate it, which can be as simple as this

# generating constants
method immediate($/) {
  my $value := 1;
  if $<noun><negative_noun> {
    $value := -1;
  }
  elsif $<noun><nothing> {
    $value := 0;
  }
  for $<adjective> {
    # "your" and "my" ignored
    unless $_<first_person_possessive> || 
       $_<second_person_possessive> || 
       $_<third_person_possessive> {
      $value:= $value*2;
    }
  }
  make PAST::Val.new( :value( $value ) );
}

method test($/, $k) {
  my $test := PAST::Var.new(:name('condition'));
  make PAST::Op.new( $test, 
                 $($<sentence>),
                 :pasttype($k)); # $k = "if" or "unless"
}

The actions file is written in Not Quite Perl which is a pretty basic language although it lacks sme things that would be useful in general IMHO, such list flattening. If needed though they can be used by associating the NQP classes with classes of another parrot language, such as perl6's or ruby's or lua's.

Another small issue I had was trying to conflate capture of single and multiple occurrences of a string, such as

|'exit'  <character>**{1} {*} #= exit
|'exeunt' <character> ['and' <character>]+ {*} #= exit

without explicit quantification (**{1}), the action method would get a scalar reference for the first case and a list reference for the second, and since I cannot write @($character) (NQP does not know about this) I needed an additional conditional in the action code. By explicitly quantifying I always get a list and everything is nice.

The runtime

Basic runtime functions can be written using the PIR intermediate representation, a form of high level assembly that knows about objects, namespaces, exceptions and more. Some of the code is slightly involuted because of the shakespeare language nature: most operations actually refer to both the speaker and the other character currently on stage, but it is usually quite simple to follow

.sub 'enter'
    .param string char
    get_global $P0, char
    unless null $P0 goto fin
    die "no such character in the cast!"
  fin:
    $P0['onstage'] = 1
.end

I also tweaked a little the main routine (autogenerated) to add an additional stage to the compiler. Namely, since I could not set a global "case insensitive" flag for the grammar, I introduced a pre-parsing pass to transform the input in lower case. There are probably better ways to do this, but it seems to work.

Testing

Obviously, I needed to test this. Parrot provides some tools to manage this, namely checking that the compiler outputs the right things at each stage, or that the program output is the one expected. I decided to go through another route, again wonderfully supported, of supporting TAP natively in the language.

This means you have test support builtin in the shakespeare language, bringing it up to date to the best software engineering practices.

This was admittedly extremely easy: I just added some syntax and a couple of runtime functions to print the plan ("1...10") and the test result ("ok 2", "ok 3" etc). Parrot's test harness knows how to manage that and so everything works fine.

Since I did not want to copy the existing source code I wrote everything from scratch (bar the wordlists) and used the supplied examples as reference. So I also added those to the test suite.

It seems, though, that parrot's Parrot::Test does not manage program input, so I used a ruby script as a driver. Which gets actually executed from perl, who knows about the "#!/usr/bin/env ruby" header better than me.

I was trying to port it to perl, but I'm not satisfied with the outcome, I must investigate a bit more

Conclusions

You can get the code through bitbucket, and it should work with today's (january '09) Parrot. All in all this was fun, people in #parrot and #perl6 are nice and helpful, parrot already offers great support for writing your own language and, well, you should try it too :)

Oh, and I passed my last university exam. too :D

AddThis Social Bookmark Button

4 Responses to “Writing a Shakespeare interpreter with Parrot”

  1. Shlomi Fish Says:

    Congrats for passing your university exam! Does this mean you’re graduating?

  2. gabriele Says:

    thank you a lot :)

    Well, it means the only thing left is to defend my thesis, but that (usually) is an easy thing.. there are oscillations on the final mark you’ll get but in the end you graduate anyway :)

  3. Bernhard Schmalhofer Says:

    I have add information about shakespeare-parrot to https://trac.parrot.org/parrot/wiki/Languages. Welcome to the club.

  4. gabriele Says:

    oh, thank you I did not think about it :)

Sorry, comments are closed for this article.