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