Testing multiple implementations of a protocol

Testing multiple implementations of a protocol is a recurrent task. For example, we may have multiple datasets that we need to check for integrity. Or we may want to check multiple implementations of an abstract data type. In this blog post, we will use Logtalk’s dictionaries library to illustrate how the Logtalk language features and the lgtunit tool greatly simplify this common task.

The dictionaries library defines a dictionary protocol (also known as a map or associative array) and three different implementations: a naive implementation using a binary tree, a red-black tree implementation, and an AVL tree implementation. The tests are necessarily the same and independent of the details of a particular implementation. Therefore, the tests need to take as a parameter the particular implementation being tested. This is easily accomplished by using a parametric object:

:- object(tests(_DictionaryObject_),
    extends(lgtunit)).

    ...

:- end_object.

This allows us to run e.g. the tests for the AVL tree implementation provided by the avltree object using the query:

?- tests(avltree)::run.

The object parameter, _DictionaryObject_, is a parameter variable and its semantics are simple: the compiler unifies the parameter with any occurrence of the parameter variable within the object. For example:

test(dictionary_next_4_01) :-
    _DictionaryObject_::as_dictionary([], Dictionary),
    \+ _DictionaryObject_::next(Dictionary, _, _, _).

But this is verbose, specially when writing a large number of tests. We can take further advantage of the parameter variable to simplify the tests by using implicit message sending for all the predicates being tested:

:- uses(_DictionaryObject_, [
    as_dictionary/2, as_list/2,
    clone/3, clone/4, insert/4, delete/4, update/4, update/5, empty/1,
    lookup/3, previous/4, next/4, min/3, max/3, delete_min/4, delete_max/4,
    keys/2, values/2, map/2, map/3, apply/4, size/2, valid/1, new/1
]).

Thanks to this uses/2 directive, the test above can be simplified to:

test(dictionary_next_4_01) :-
    as_dictionary([], Dictionary),
    \+ next(Dictionary, _, _, _).

The only detail missing is how to run the tests for all dictionary implementations:

?- lgtunit::run_test_sets([tests(avltree), tests(bintree), tests(rbtree)]).

The lgtunit::run_test_sets/1 predicate conveniently generates a single code coverage report for all the implementations and also allows generating a single TAP report or xUnit report. When the protocol implementations are only know at runtime, we can easily construct a list of all the implementations by using the implements_protocol/2-3 and conforms_to_protocol/2-3 reflection predicates. For example, we can rewrite the query above as:

?- findall(tests(Object), implements_protocol(Object,dictionaryp), Sets),
   lgtunit::run_test_sets(Sets).
NOTES

See the dictionaries library directory for the actual tester.lgt driver file that is used for running the tests.

The XML files for the code coverage and the xUnit reports were generated using the logtalk_tester automation script:

$ cd $HOME/logtalk/library/dictionaries
$ logtalk_tester -f xunit -c xml

The HTML version of the code coverage report linked above was then generated using the commands:

$ cd $HOME/logtalk/library/dictionaries
$ xsltproc \
  --stringparam prefix logtalk/ \
  --stringparam url https://github.com/LogtalkDotOrg/logtalk3/tree/aa18ac872371165fbce99bb1efa8e026e1ad79d2 \
  -o coverage_report.html coverage_report.xml

The HTML version of the xUnit report linked above was then generated using the third-party converter xunit-to-html with the following commands:

$ cd xunit-to-html-master
$ java -jar saxon9he.jar \
  -o:$HOME/logtalk/library/dictionaries/xunit_report.html \
  -s:$HOME/logtalk/library/dictionaries/xunit_report.xml \
  -xsl:xunit_to_html.xsl

These commands can be easily automated in CI/CD contexts. For automation examples see e.g. the available Logtalk GitHub actions and workflows.