Category: Programming

Don’t Interpret Me Wrong: Improvising Tests for an Interpreter

I’m in love with the Crafting Interpreters book. In it, Bob Nystrom teach us how to writer an interpreter by implementing a little programming language called Lox. It was a long time since I had so much fun programming! Besides being well-written, the book is funny and teach way more than I would expect. But I have a problem.

The snippets in the bug are written in a way we can copy and paste them. However, the book has challenges at the end of each chapter, these challenges have no source code and sometime they force us to change the interpreter a lot. I do every one of these exercises and as a result my interpreter diverges too much from the source in the book. Consequently, I often break some part of my interpreter.

How to solve that?

Unity tests would be brittle since the code structure changes frequently. End-to-end tests seem more practical in this case. So, for each new feature of the language, I wrote a little program. For example, my interpreter should create closures, and to ensure that I copied the Lox program below to the file counter.lox:

return count;
}

var counter = makeCounter();
counter(); // “1”.
counter(); // “2”.</code></pre>
<p>

This program result should be the numbers 1 and 2 printed in different lines. So I put these values in a file called counter.lox.out. The program cannot fail either, so I created an empty file called counter.lox.err. (In some cases, it is necessary to ensure the Lox program will fail. In these cases, the file .lox.err should have content.)

Well, I wrote programs and output files for various examples; now I need to compare the programs’ results to the expected outputs. I decided to use the tool that helps me the most in urgent times: shell script. I did a Bash script with a for iterating over all examples:

done</code></pre>
<p>

For each example, I executed the Lox program, redirecting the outputs to temporary files:

Now, we compare the real output with the expected output through diff. When it compares two files, diff returns 0 if there is no difference, 1 if there exists a difference or 2 in case of error. Since in Bash the conditional if considers 0 as true, we just check the negation of diff‘s exit code.

If the program prints something in standard output that is different from what is in its .lox.out file, we have a failure:

if ! diff $l.out $out
then
FAIL=1
fi
done</code></pre>
<p>

We also check the standard error and the .lox.err file:

if ! diff $l.out $out
then
FAIL=1
fi

if ! diff $l.err $err
then
FAIL=1
fi
done</code></pre>
<p>

Finally, I check if there was some failure and report the result:

if ! diff $l.out $out
then
FAIL=1
fi

if ! diff $l.err $err
then
FAIL=1
fi

if [ &quot;$FAIL&quot; = &quot;1&quot; ]
then
echo &quot;FAIL&quot; $l
else
echo &quot;PASS&quot; $l
fi
done</code></pre>
<p>

Not all of my Lox programs can be checked, though. For example, there is a program which times loop executions, it is impossible to anticipate the value it will print. Because of that, I added the possibility to jump some programs: we need just to create a file with the .lox.skip extension:

out=$(mktemp)
err=$(mktemp)
java -classpath target/classes/ br.com.brandizzi.adam.myjlox.Lox $l &gt; $out 2&gt; $err

if ! diff $l.out $out
then
FAIL=1
fi

if ! diff $l.err $err
then
FAIL=1
fi

if [ &quot;$FAIL&quot; = &quot;1&quot; ]
then
echo &quot;FAIL&quot; $l
else
echo &quot;PASS&quot; $l
fi
done</code></pre>
<p>

If, however, I have a Lox example and it does not have expected output files (nor the .lox.skip file) then I have a problem and the entire script fails:

out=$(mktemp)
err=$(mktemp)
java -classpath target/classes/ br.com.brandizzi.adam.myjlox.Lox $l &gt; $out 2&gt; $err

if ! diff $l.out $out
then
FAIL=1
fi

if ! diff $l.err $err
then
FAIL=1
fi

if [ &quot;$FAIL&quot; = &quot;1&quot; ]
then
echo &quot;FAIL&quot; $l
else
echo &quot;PASS&quot; $l
fi
done</code></pre>
<p>

With that, my test script is done. Let us see how it behaves:

$ ./lcheck.sh
PASS examples/attr.lox
PASS examples/bacon.lox
PASS examples/badfun.lox
PASS examples/badret.lox
PASS examples/bagel.lox
PASS examples/bostoncream.lox
PASS examples/cake.lox
PASS examples/checkuse.lox
PASS examples/circle2.lox
PASS examples/circle.lox
1d0
< 3
1c1
<
---
> [line 1] Error at ',': Expect ')' after expression.
FAIL examples/comma.lox
PASS examples/counter.lox
PASS examples/devonshinecream.lox
PASS examples/eclair.lox
PASS examples/fibonacci2.lox
PASS examples/fibonacci.lox
PASS examples/func.lox
PASS examples/funexprstmt.lox
PASS examples/hello2.lox
PASS examples/hello3.lox
PASS examples/hello.lox
PASS examples/math.lox
PASS examples/notaclass.lox
PASS examples/noteveninaclass.lox
PASS examples/point.lox
PASS examples/retthis.lox
PASS examples/scope1.lox
PASS examples/scope.lox
PASS examples/supersuper.lox
PASS examples/thisout.lox
PASS examples/thrice.lox
SKIP examples/timeit.lox
PASS examples/twovars.lox
PASS examples/usethis.lox
PASS examples/varparam.lox

Oops, apparently I removed the support for the comma operator by accident. Good thing I wrote this script, right?

I hope this post was minimally interesting! Now, I am going to repair my comma operator and keep reading this wonderful book.

(This post is a translation of Não me Interprete Mal: Improvisando Testes para um Interpretador.)

Give Doctest a chance

Doctest is one of my favorite Python modules. With doctest, it is possible to execute code snippets from documentation. You could, for example, write something like this in your  turorial.md…

>>> f()
1

…and then execute the command python -mdoctest tutorial.md. If f() returns 1, nothing will happen. If it returns something else, though, an error message will appear, similar to this one:

**********************************************************************
File "f.txt", line 2, in f.txt
Failed example:
    f()
Expected:
    1
Got:
    2
**********************************************************************
1 items had failures:
   1 of   2 in f.txt
***Test Failed*** 1 failures.

It is an impressive tool, but also an unpopular one.  The problem is, Doctest is often improperly used. For example, it is common to try to write unit tests with doctests. Great mistake.

Nonetheless, I believe it is unfair to disregard the module due to these misunderstandings. Doctest can and should be used for what it does best: to keep your documentation alive, and even to guide your development!

Let me show an example.

When you don’t know what to do

Some days ago, I was writing a class to modify an HTML document using xml.dom.minidom. At one point, I needed a function to map CSS classes to nodes from the document. That alone would be a complicated function! I had no idea of where to start.

In theory, unit tests could be useful here. They just would not be very practical: this was an internal, private function, an implementation detail. To test it, I’d have to expose it. We would also need a new file, for the tests. And test cases are not that legible anyway.

Reading the documentation from the future

Instead, I documented the function first. I wrote a little paragraph describing what it would do. It alone was enough to clarify my ideas a bit:

Given an xml.dom.minidom.Node, returns a map
from every “class” attribute to a list of nodes
with this class.

Then, I though about how to write the same thing, but with a code example. In my head, this function (which I called get_css_class_dict()) would receive xml.dom.minidom document. So, I wrote an example:

    >>> doc = xml.dom.minidom.parseString(
    ...     '''
    ...     
    ...         
    ...







    ...         
    ...     
    ...     ''')

Given this snippet, I would expect the function to return a dict. My document has two CSS classes, “a” and “b,” and then my dict would have two keys. Each key would have a list of the nodes with the CSS class. Something like this:

    >>> d = get_css_class_dict(doc)
    >>> d['a']  # doctest: +ELLIPSIS
    [, ]
    >>> d['b']  # doctest: +ELLIPSIS
    []

I put these sketches in the docstring  of get_css_class_dict(). So far, we have this function:

def get_css_class_dict(node):
    """
    Given an xml.dom.minidom.Node, returns a map from every "class" attribute
    from it to a list of nodes with this class.

    For example, for the document below:

    >>> doc = xml.dom.minidom.parseString(
    ...     '''
    ...     
    ...         
    ...







    ...         
    ...     
    ...     ''')

    ...we will get this:

    >>> d = get_css_class_dict(doc)
    >>> d['a']  # doctest: +ELLIPSIS
    [, ]
    >>> d['b']  # doctest: +ELLIPSIS
    []
    """
    pass

I could do something similar with unit tests but there would be much more code around, polluting the documentation. Besides that, the prose graciously complements the code, giving rhythm to the reading.

I execute the doctests and this is the result:

**********************************************************************
File "vtodo/listing/filler.py", line 75, in filler.get_css_class_dict
Failed example:
    d['a']
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python3.6/doctest.py", line 1330, in __run
        compileflags, 1), test.globs)
      File "", line 1, in 
        d['a']
    TypeError: 'NoneType' object is not subscriptable
**********************************************************************
File "vtodo/listing/filler.py", line 77, in filler.get_css_class_dict
Failed example:
    d['b']
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python3.6/doctest.py", line 1330, in __run
        compileflags, 1), test.globs)
      File "<https://suspensao.blog.br/disbelief/wp-admin/edit-tags.php?taxonomy=category;doctest filler.get_css_class_dict[3]>", line 1, in 
        d['b']
    TypeError: 'NoneType' object is not subscriptable
**********************************************************************
1 items had failures:
   2 of   4 in filler.get_css_class_dict
***Test Failed*** 2 failures.

I’m following test-driven development, basically, but with executable documentation. At once, I got a readable example and a basic test.

Now, we just need to implement the function! I used some recursion and, if the code is not the most succinct ever at first…

def get_css_class_dict(node):
    """
    Given an xml.dom.minidom.Node, returns a map from every "class" attribute
    from it to a list of nodes with this class.

    For example, for the document below:

    >>> doc = xml.dom.minidom.parseString(
    ...     '''
    ...     
    ...         
    ...







    ...         
    ...     
    ...     ''')

    ...we will get this:

    >>> d = get_css_class_dict(doc)
    >>> d['a']  # doctest: +ELLIPSIS
    [, ]
    >>> d['b']  # doctest: +ELLIPSIS
    []
    """
    css_class_dict = {}

    if node.attributes is not None and 'class' in node.attributes:
        css_classes = node.attributes['class'].value

        for css_class in css_classes.split():
            css_class_list = css_class_dict.get(css_class, [])
            css_class_list.append(node)
            css_class_dict[css_class] = css_class_list

    childNodes = getattr(node, 'childNodes', [])

    for cn in childNodes:
        ccd = get_css_class_dict(cn)
        for css_class, nodes_list in ccd.items():
            css_class_list = css_class_dict.get(css_class, [])
            css_class_list.extend(nodes_list)
            css_class_dict[css_class] = css_class_list  

    return css_class_dict

…at least it works as expected:

$ python -mdoctest vtodo/listing/filler.py 
**********************************************************************
File "vtodo/listing/filler.py", line 77, in filler.get_css_class_dict
Failed example:
    d['b']  # doctest: +ELLIPSIS
Expected:
    []
Got:
    []
**********************************************************************
1 items had failures:
   1 of   4 in filler.get_css_class_dict
***Test Failed*** 1 failures.

Wait a minute. What was that?!

When the documentation is wrong

Well, there is a mistake in my doctest! The span element does not have the “b” class—the div element does. So, I just need to change the line

[<DOM Element: span at ...>]

to

[<DOM Element: div at ...>]

and the Doctest will pass.

Isn’t it wonderful? I found a slip in my documentation almost immediately. More than that: if my function’s behavior changes someday, the example from my docstring will fail. I’ll know exactly where the documentation will need updates.

Making doctests worth it

That is the rationale behind Doctest. Our documentation had a subtle mistake and we found it by executing it. Doctests do not guarantee the correctness of the code; they reinforces the correctness of documentation. It is a well-known aspect of the package but few people seem to believe it is worth it.

I think it is! Documentation is often deemed an unpleasant work but it does not have to be so.  Just as TDD make tests exciting, it is possible to make documentation fun with doctests.

Besides that, in the same way TDD can point to design limitations, a hard time writing doctests can point out to API problems. If it was hard to write a clear and concise example of use for your API, surrounded by explaining text, it is likely too complicated, right?

Give Doctest a chance

In the end, I see doctests limitations. They are surely inadequate for unit tests, for example.  And yet, doctest makes documenting so easy and fun! I don’t see why it is so unpopular.

Nonetheless, its greatest advantage is how doctest makes the development process easier. Some time ago, I joked that we need to create DocDD:

With Doctest, it is not just a joke anymore.

This post is a translation of Dê uma chance a Doctest.