Property-Driven Grammar Development

by Sean Cribbs

Back when I first learned about parsing expression grammars (PEGs), I was impressed by the test-driven grammar development demo that the author of Treetop had created. TDD, BDD, and friends are a given in the Ruby community, but are not as popular in the Erlang world. On the other hand, QuickCheck is the most powerful tool for testing Erlang, given that it can generate random test cases and quickly reduce found errors to the minimal failing case (the most important part!).

A few weeks ago Rich Hickey released an informal specification edn, a subset of Clojure syntax for expressing data, and the on-the-wire format for Datomic. Since I have a PEG/Packrat tool and QuickCheck, it seemed like a perfect weekend project to attempt property-driven development on. (With minimal modification, one could use PropEr or Triq to do this, too.) I’m not going to go into detail about how to use QuickCheck, but I’ll try to cover the relevant bits as I go.

Now, the interesting part about testing a parser with QuickCheck is that you have to do the work twice! That is, you must define a generator for a subset of the language at the same time that you develop the rule that parses it; the challenge will be avoiding the “ugly mirror” problem. With some more formal methods than I take here, one might be able to use the grammar as both generator and parser, an exercise I leave to you, kind reader.

Usually I try to attack developing a grammar by selecting the simplest construct – usually a terminal deep in the syntax tree – and implementing that, then build up the language as I go with more terminals and simple non-terminals until I reach the top level. Since the simplest and most prolific terminal in edn is whitespace, we’ll start there. In my first pass at this, I started by writing my properties in the grammar file, but that quickly became unmanageable, so my examples below will keep them separate. Whitespace in edn is defined as any tab character, carriage return, linefeed, horizontal space, or comma, so let’s create a QuickCheck generator for that.

%% edn_eqc.erl
-module(edn_eqc).
-ifdef(EQC).
-compile([export_all]).
-include_lib("eqc/include/eqc.hrl").

gen_ws() -> oneof([9, 10, 11, 12, 13, 32, $,]).

-endif.

I use the oneof generator because each of the whitespace types is independent and none are preferred over another, meaning that they don’t need to shrink to a specific value. Since we need binaries and not just bytes as parser input, and all streams in edn are UTF-8 encoded, let’s modify the generator a little bit and add a convenience macro for converting to UTF-8.

%% [snip]
-define(to_utf8(X), unicode:characters_to_binary(lists:flatten(X), utf8, utf8)).

gen_ws() ->
    ?LET(X,
         list(oneof([9, 10, 11, 12, 13, 32, $,])),
         ?to_utf8(X)).

The ?LET macro allows you to wrap a non-abstract operation around a generator so that you can modify the concrete value after it is generated, while still returning a generator that QuickCheck can understand. Now we can sample that generator and see if it makes sense. (Note that I’ve skipped over some setup stuff you’ll need to do with rebar to make it a proper app. I put edn_eqc.erl in test/.)

$ rebar get-deps compile eunit compile_only=true
$ erl -pa .eunit
 
1> eqc_gen:sample(edn_eqc:gen_ws()).
<<"\t \n">>
<<>>
<<"\f ">>
<<>>
<<"\f\r,\f,">>
<<>>
<<" \v\r\n">>
<<",\f\n">>
<<"\n, \n\v\n">>
<<>>
<<>>
ok

Great, now we should define what the property of parsing whitespace should be, namely, that it is ignored. However, given that edn can be used to stream data, and has a native list type, returning an empty list when the stream has only whitespace would not make sense. Returning a tagged error tuple, which is Erlang’s convention, would also be presumptious, given that edn has a tuple type. Therefore, I’m going to choose to return a sentinel value of '$space' for now, and I’ll later insert a throw at the top level so we can detect empty streams. Luckily, it will be simple to change this later.

%% Must be after the EQC include, since it will try to define similar
%% macros.
-include_lib("eunit/include/eunit.hrl"). 

%% [snip]

prop_whitespace() ->
    ?FORALL(Spaces, gen_ws(),
           '$space' == edn:parse(Spaces)).

Now let’s run it!

$ rebar qc
==> edn (qc)
NOTICE: Using experimental 'qc' command
Compiled test/edn_eqc.erl
prop_whitespace: Starting Quviq QuickCheck version 1.25.1
   (compiled at {{2011,10,1},{13,42,22}})
Licence for Basho reserved until {{2012,10,11},{11,19,8}}
Failed! Reason: 
{'EXIT',{undef,[{edn,parse,[<<>>],[]},
                {edn_eqc,'-prop_whitespace/0-fun-0-',1,
                         [{file,"test/edn_eqc.erl"},{line,16}]},
                {eqc,'-f777_0/2-fun-4-',3,[]},
                {eqc_gen,'-f321_0/2-fun-0-',5,[]},
                {eqc_gen,f186_0,2,[]},
                {eqc_gen,'-f321_0/2-fun-0-',5,[]},
                {eqc_gen,f186_0,2,[]},
                {eqc_gen,gen,3,[]}]}}
After 1 tests.
<<>>
ERROR: One or more QC properties didn't hold true:
[prop_whitespace]

Woops, we got undef because we didn’t define our grammar module yet! Let’s open up edn.peg and add the grammar rule.

whitespace <- [,\s\v\f\r\n\t]+ `'$space'`;

Briefly, we’ve defined the whitespace non-terminal as parsing from one-or-more characters in the class of visible whitespaces plus the comma character, and returning the Erlang atom '$space'. Now let’s compile the grammar and try it again.

$ rebar compile qc skip_deps=true
==> edn (compile)
Compiled src/edn.peg
src/edn.erl:109: Warning: function p_all/4 is unused
Compiled src/edn.erl
==> edn (qc)
NOTICE: Using experimental 'qc' command
src/edn.erl:109: Warning: function p_all/4 is unused
Compiled src/edn.erl
Compiled test/edn_eqc.erl
prop_whitespace: Starting Quviq QuickCheck version 1.25.1
   (compiled at {{2011,10,1},{13,42,22}})
Licence for Basho reserved until {{2012,10,11},{11,19,8}}
Failed! After 1 tests.
<<>>
ERROR: One or more QC properties didn't hold true:
[prop_whitespace]
ERROR: qc failed while processing /Users/sean/Development/edn: rebar_abort

Hmm, an empty content is a valid input, but shouldn’t be recognized as a space. Let’s make that generator predicated as non-empty on the property.

%% QuickCheck property for whitespace
prop_whitespace() ->
    ?FORALL(Spaces, non_empty(gen_ws()),
           '$space' == edn:parse(Spaces)).
$ rebar compile qc skip_deps=true
==> edn (qc)
NOTICE: Using experimental 'qc' command
src/edn.erl:109: Warning: function p_all/4 is unused
Compiled src/edn.erl
Compiled test/edn_eqc.erl
prop_whitespace: Starting Quviq QuickCheck version 1.25.1
   (compiled at {{2011,10,1},{13,42,22}})
Licence for Basho reserved until {{2012,10,11},{11,19,8}}
....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests

Alright, we can parse whitespace! *facepalm* Let’s quickly add a few more simple language constructs, namely nil and booleans so we can see how to start building up the structure around these terminals. Again we start with the generators:

gen_nil() -> <<"nil">>.

gen_bool() -> oneof([<<"true">>, <<"false">>]).

Native Erlang values generate themselves in QuickCheck, so simply returning the <<"nil">> value means that that will always be generated from the gen_nil() function. We can sample those generators again if we like, but they will be unsurprising. Instead, let’s define a property for nil:

prop_nil() ->
    ?FORALL(Nil, ws_wrap(gen_nil()),
            nil == edn:parse(Nil)).

Notice I haven’t defined that ws_wrap function yet. Remember that our goal here was to treat whitespace simply as a separator, so the property we want to define is that a real terminal surrounded by whitespace parses into that terminal. Let’s teach QuickCheck how to wrap things in whitespace by making another generator, using our handy ?LET macro again:

%% Wrap another generator in whitespace
ws_wrap(Gen) ->
    ?LET({LWS, V, TWS}, 
         {gen_ws(), Gen, gen_ws()},
         ?to_utf8([LWS, V, TWS])).

Thanks to ?LET, ws_wrap defines a generator that will create some amount of leading whitespace (maybe none), evaluate the passed generator, and then some trailing whitespace (maybe none) and flatten it into a UTF-8 binary. Perfect, check that property!

$ rebar qc skip_deps=true
==> edn (qc)
NOTICE: Using experimental 'qc' command
Compiled test/edn_eqc.erl
prop_nil: Starting Quviq QuickCheck version 1.25.1
   (compiled at {{2011,10,1},{13,42,22}})
Licence for Basho reserved until {{2012,10,11},{11,19,8}}
Failed! After 1 tests.
<<"nil">>
prop_whitespace: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
ERROR: One or more QC properties didn't hold true:
[prop_nil]
ERROR: qc failed while processing /Users/sean/Development/edn: rebar_abort

We’ve got a failing property again, and look how it shrunk! It’s easy to see what broke, namely that, DUH, we didn’t define how to parse nil. That’s easy to fix:

nil <- "nil" `nil`;
whitespace <- [,\s\v\f\r\n\t]+ `'$space'`;

Now, I could run the property again, but I’ll save you the pain; simply adding that rule isn’t going to cut it because nil must be surroundable by whitespace. Also, neotoma won’t compile that grammar because it contains nonterminals that are not referred anywhere else – its convention is that the first rule is the entry point to the grammar. Let’s add some rules that allow us to describe the syntactic form of whitespace, and the semantic behavior of empty streams at the same time.

edn <- whitespace? (term:term whitespace?)* `
case Node of
  %% Nothing but whitespace
  [ _, []] ->
        throw({edn,empty});
  %% Just one datum
  [ _, [[{term,Term}, _]]] ->
       Term;
  %% Lots of terms
  [ _, Terms ] ->
        [ T || [{term, T}, _WS] <- Terms ]
end
`;
 
term <- nil ~;
nil <- "nil" `nil`;
whitespace <- [,\s\v\f\r\n\t]+ `'$space'`;

This is the first time we’ve seen significant code in the grammar, so I’ll try to describe what’s going on. In neotoma grammars, you can include inline code between backticks or comment-braces (%{, %}) that will be run when a rule is successfully parsed. Within that code block, the variable Node is sequence of terms that was parsed, so you can manipulate that to build the data structures you want to result from the parse. In the previous two rules, we’ve been ignoring the parse result and simply returning static values. In our new term rule, we are using the special-form of ~ to skip doing any transformation, which is the equivalent of writing %{ Node %}, but much less noisy.

Now let’s focus our attention on the top-level rule, edn, which encapsulates our whitespace and stream behavior. It says that leading whitespace is optional, followed by zero-or-more terms separated by whitespace. We tag the terms as they are parsed so they are easier to pattern-match on and extract. Now in the code block, we can do something with parse. If the parenthesized portion parses zero times, the result will be an empty list, so we handle that case by throwing a special term like I mentioned above. In the case of parsing only a single term, we want to return only that term, and it not wrapped in a list, so we special-case that parse as well. Finally, if there is a stream of terms, for now we will just extract them and return them in a list.

Let’s recompile the grammar and try our properties again.

$ rebar compile qc skip_deps=true
==> edn (compile)
Compiled src/edn.peg
Compiled src/edn.erl
==> edn (qc)
NOTICE: Using experimental 'qc' command
Compiled src/edn.erl
prop_nil: Starting Quviq QuickCheck version 1.25.1
   (compiled at {{2011,10,1},{13,42,22}})
Licence for Basho reserved until {{2012,10,11},{11,19,8}}
....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_whitespace: Failed! Reason: 
{'EXIT',{{case_clause,{edn,empty}},
         [{eqc,'-f777_0/2-fun-4-',3,[]},
          {eqc_gen,'-f321_0/2-fun-0-',5,[]},
          {eqc_gen,f186_0,2,[]},
          {eqc_gen,'-f321_0/2-fun-0-',5,[]},
          {eqc_gen,f186_0,2,[]},
          {eqc_gen,gen,3,[]},
          {eqc,'-f758_0/1-fun-2-',3,[]},
          {eqc_gen,'-f321_0/2-fun-1-',4,[]}]}}
After 1 tests.
ERROR: One or more QC properties didn't hold true:
[prop_whitespace]
ERROR: qc failed while processing /Users/sean/Development/edn: rebar_abort

Woops, we broke the whitespace property because we didn’t expect the throw! (One might call this letting your code get ahead of your tests.) Let’s change that to use an assertion provided by eunit.

%% You must put this AFTER the EQC header file.
-include_lib("eunit/include/eunit.hrl").

%% [snip]

prop_whitespace() ->
    ?FORALL(Spaces, gen_ws(),
            ok == ?assertThrow({edn, empty}, edn:parse(Spaces))).

Run that one more time.

$ rebar qc skip_deps=true
==> edn (qc)
NOTICE: Using experimental 'qc' command
Compiled test/edn_eqc.erl
prop_nil: Starting Quviq QuickCheck version 1.25.1
   (compiled at {{2011,10,1},{13,42,22}})
Licence for Basho reserved until {{2012,10,11},{11,19,8}}
....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_whitespace: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests

Cool, now we can integrate that boolean generator and write a property for it.

prop_bool() ->
    ?FORALL(Boolean, ws_wrap(gen_bool()),
            lists:member(edn:parse(Boolean), [true, false])).

I think you get the drill now, let’s assume you ran that, you would get the {edn, empty} thrown because it will stop parsing at the first valid tree before an unknown character. Let’s add the rule to the grammar:

edn <- whitespace? (term:term whitespace?)* `
case Node of
  %% Nothing but whitespace
  [ _, []] ->
        throw({edn,empty});
  %% Just one datum
  [ _, [[{term,Term}, _]]] ->
       Term;
  %% Lots of terms
  [ _, Terms ] ->
        [ T || [{term, T}, _WS] <- Terms ]
end
`;

term <- boolean / nil ~;
boolean <- "true" / "false" `binary_to_existing_atom(Node, utf8)`;
nil <- "nil" `nil`;
whitespace <- [,\s\v\f\r\n\t]+ `'$space'`;

On the term rule, we just added boolean to one of the possible terms, using ordered choice, and use the binary_to_existing_atom/2 BIF in the boolean rule to create the proper Erlang term. One last time, let’s compile the grammar and run the properties:

$ rebar compile qc skip_deps=true
==> edn (compile)
Compiled src/edn.peg
Compiled src/edn.erl
==> edn (qc)
NOTICE: Using experimental 'qc' command
Compiled src/edn.erl
prop_nil: Starting Quviq QuickCheck version 1.25.1
   (compiled at {{2011,10,1},{13,42,22}})
Licence for Basho reserved until {{2012,10,11},{11,19,8}}
....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_whitespace: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_bool: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests

Puzzler

So far I’ve lead you through it by hand, including most of the missteps along the way. I’ve gone way past this point in the actual project, including doing more complicated-to-parse types like numbers. Given the grammar and properties in the project on Github, can you figure out why prop_symbol() fails? The answer is subtle.

$ rebar qc skip_deps=true
==> edn (qc)
NOTICE: Using experimental 'qc' command
Compiled test/edn_eqc.erl
Compiled src/edn.erl
prop_whitespace: Starting Quviq QuickCheck version 1.25.1
   (compiled at {{2011,10,1},{13,42,22}})
Licence for Basho reserved until {{2012,9,30},{14,35,1}}
....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_bool: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_nil: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_unescape: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_string: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_symbol: ............................................................................................................................................................................................................................................................................Failed! After 269 tests.
<<"\v\v\n\r  ,, ,\r\t-3fAloF0oZXp8 ,">>
Shrinking...(3 times)
<<"-3">>
prop_character: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_integer: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
prop_float: ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
OK, passed 500 tests
ERROR: One or more QC properties didn't hold true:
[prop_symbol]
ERROR: qc failed while processing /Users/sean/Development/edn:
rebar_abort

Comments

© 2006-present Sean CribbsGithub PagesTufte CSS