Mutable Syntax in Mercury

Mutable Syntax in the Mercury Programming Language

Introduction

The Mercury programming
language is a compiled, strict, pure, type-safe logical and
functional programming language. Its programming methodology is
based on predicate logic, with syntax and semantics in line with
that of Prolog. Along with logic, it has a fully integrated
Hindley-Milner type system with lambda-terms, very much in the
style of the Haskell programming
language.

The smooth integration of Prolog with Haskell sounds like a
marriage of programming paradigms to release the programmer into
Coding Nirvana, as it were. This is how it is for most cases, as the
language has a consistent design philosophy backed up by
well-researched principles and explained by copious and clear
documentation with numerous practical examples. What remains are
niche constructs, that is: constructs that may be helpful for
specific problems, but are not strictly necessary, nor generally
applicable.

One such niche construct, one that I turn to quite often when
programming in Prolog, is the op/3 declaration, or,
the ability to introduce new syntax into the language so that I
may model the problem more naturally. This document covers
extending the language to include the op/3
declaration in its full breath of functionality.

Alternatives, and Raison d'être

The approach we take is the modify the compiler so that it
accepts the op/3 directive in a module and
thereafter, within only that module, parse the operator
declared with the specification and priority given in the
directive. This may seem like a drastic measure, so we must
consider the alternatives before choosing this course of action.
There are basically four viable, albeit inferior, alternatives:

1. The Mercury programming language provides the grave
   syntactic construct which converts the standard prefixed call
   to an infix one:

   fn(X, Y) becomes X `fn` Y
   

   
   

   See, for example, the pprint module, as it used to
   make extensive use of this style (until it recently deprecated
   this approach to use one of the builtin operators, instead).
   Just as the Mercury language developers have discovered, this
   approach has at least two drawbacks:

   
   
   
   
   
   1. these infix "operators" are clearly marked as
      second-class citizens, unnecessarily lengthening what is
      supposed to be a concise
      representation;¹
      and,
   
   
   2. only binary infix operators are allowed under this syntax; I
      often find it useful to type values using a postfix
      type.
   
   
   
   




2. One could construct a specialized instance of
   the op_table typeclass from the ops
   module and thereafter use read_term_with_op_table/4
   from the term_io module to parse strings at
   runtime. See samples/calculator2.m provided with the
   distribution for an example program that demonstrates this
   approach.

   
   
   

   This approach also has its own set of associated problems:

   
   
   
   
   
   1. Constructing one's own op_table is excessive
      when using only a few operators and tedious when introducing
      many operators. This manual process steals precious time
      away from program development that addresses the problem,
      itself.
   
   
   2. Until now, there was no "cookbook" approach addressing
      the problem of how to create a mutable syntax.
      The ops module and the sample calculator program
      are well-documented and provide good examples of how to
      implement static syntax, but provide no guidance for
      constructing dynamic, mutable, syntax. For this, one had to
      design such a framework from first
      principles.²
   
   
   3. An user-defined op_table instance may only be
      used at runtime. The Mercury compiler, as implemented, does
      not allow such tables during module compilation.
   
   
   

3. Third, use one of the available scanners (such as
   samples/lex/) or parser generators (such as samples/moose/) to
   create a language syntax-aware preprocessor that substitutes
   operators and their arguments with the well-formed term
   replacement. Problems:

   
   
   1. This is highly redundant and fruitless exercise,
      as the compiler has its own parse phase that does the same
      work, and with the language itself in flux (as is the case for
      any living language) changes to the syntax quickly render a
      system created by these means obsolete. Parser generators
      for other programming languages provide complete grammars
      for every version of the host programming language, Mercury
      has no parser generator with such grammars, so this task is
      left to a user of these kinds of systems.
   
   
   2. Furthermore, although the domain-specific languages for
      these tools closely follow the Mercury programming language
      to do their work, they do have their own languages that
      require time and effort to master. When presented with
      powerful parsing facilities built right into logic
      programming languages (I'm referring specifically to Definite
      Clause Grammars (DCGs)), one must weigh the costs of learning
      these languages before embarking on such an endeavor.
   
   

4. Worst for last: as with C/C++, create a specific
   preprocessor that parses the source file, converting annotated
   operators to equivalent Mercury terms by following the
   preprocessing directives. This approach requires so much work
   (the C preprocesser is a compiler-sized program) and has so many
   known pitfalls (such as replacing elements inappropriately (in
   a quoted string, for example) and causing an unacceptable
   disjunction between the generated executable and the original
   source base (confusing debugging and error reporting efforts),
   that it should not receive serious
   consideration;³
   it does not in this document, at any rate.

By embedding the op/3 syntax into the compiler, the
changes we make are hygenic in that they are part of the
language syntax, not external and blindly unaware of it, as is the
case with with C preprocessor and immediate so that they
may be used at compile time in the module in which they are
declared. This implementation also limits the lexical scope
of the operator within the module in which it is
declared,⁴
preventing these declarations from corrupting modules that
eventually use modules with specialized syntax.

The desired state is to integrate the op/3
declaration fully into the the language, so that, e.g., facts may
be stated in their vernacular and still be compiled into
executable content in the Mercury idiom, as in this real-world
example:

for the open weekly timecard ending date(2006, 1, 6):
employee cgi_emp_001 billed [
3 hours on sunday - date(2006, 1, 1),
16.5 hours on monday - date(2006, 1, 2),
5 hours on tuesday - date(2006, 1, 3),
5 hours on wednesday - date(2006, 1, 4)
] against contract lt_2005_001.

Far from being a contrived pedagogical
example,⁵ the
above illustrates the various typing uses of op/3
defined syntax, both prefix ('employee cgi_emp_001')
and postfix ('3 hours'). The above fact is certainly
"only" a data term (in fact, as well as being a data term, the
above fact also contains op/3-based data
terms), but fully actualized operators exist as well; the Prolog
syntax
module is rife with such examples. These uses of
op/3-declared syntax (describing entity
relationships clearly and as activated syntax) are in no way
limited to the rather straightforward problems of accounting, but
are also used in production expert systems handling over 1,000,000
transactions per day; the use of these extensions are tied
directly to rule findings satisfying customer requirements.

In short, op/3-declared syntax is used extensively in
production systems built using Prolog serving real-world
requirements under heavy demands. With the preexisting extensions
for purity, typing, and functional programming, imagine the
utility and expressivity that could be obtained with Mercury so
extended!

Implementation

Now that we have justification for modifying the compiler,

nothing remains but to get to it. Fortunately, the Mercury
compiler, after some study, yields a straightforward
implementation approach.

First things first: the
ops module uses a discriminator (the type
category) to choose among
different uses for an operator (e.g. unary '-'
verses binary '-'). This discriminator is internal,
and, as we need the same functionality when defining new
operators, so we externalize that type in library/ops.m by moving
the type declaration from the implementation section to the
interface.

Given this type, we now decorate predefined (inflexible) op table
that will permit additional syntax declarations. For this, we
need to index the operator and its category to the
syntax declaration, and then make this new type an
op_table (typeclass) instance ... we add this type
to the interface of compiler/prog_io_util.m:

:- type op_map == map(pair(string, ops.category), op_info).
:- type mercury_op_map ---> mercury_op_map(ops.table, op_map).
:- instance ops.op_table(mercury_op_map).

To further support the new type, we need information against
which we index, and we need supporting predicates to construct
the information for the parser when encountering the
operator (the declarations for this also go into the interface of
compiler/prog_io_util.m):

:- type op_info ---> op_info(ops.specifier, ops.priority).
:- func op_specifier_from_string(string) = ops.specifier.
:- func op_category_from_specifier(ops.specifier) = ops.category.

The op_specifier_from_string function simply takes
an input string, e.g. "xfx", and coverts it to the
equivalent specifier representation, e.g. the functor
xfx. The op_category_from_specifier
function follows the (implied) convention of the ops
module, which is all prefix specifier types
(including binary prefix) are the before
category and all other specifier types
(one of several different infix and postfix possibilities) are
the after category type. The complete
set of changes are enumerated explicitly in
the email on the
implementation.

After we augment the functional of the ops module,
we need to integrate this into the compiler's parser module
(which is actually called prog_io). The efficacious
point is where the parser works at the module
level,⁶ this
occurs, after some initialization in read_module/11,
in read_all_items/7. We initialize the op map here
(with a call to init_mercury_op_map), and then pass
along that nascent syntax map to the calls that parse the items in the
module (by modifying the signatures
of read_first_item/9
and the recursive calls read_items_loop_2/11
and read_items_loop/10).

So, for example, read_items_loop/9 becomes:

read_items_loop(ModuleName,
SourceFileName, !Msgs,
!Items, !Error, Syn0,
!IO)

... where Syn0 is the new syntax map. This map is
initialized in the new read_all_items/7 before
calling read_items_loop/10 with the goal:

init_mercury_op_map(init_mercury_op_table,
Syntax)

The magic occurs in module parser's
read_term_with_op_table/5 (called via
read_item/7) which normally scans and parses the
items in the module. When it encounters an op/3
declaration, however, it eventually resolves to the
process_decl/8 back in the prog_io
module, which reads the declaration and then adds the syntax
declaration to the op map, enhancing the syntax for the current
module.

When read_all_items/7 completes its iteration on a
module's items, it exits, discarding the op_map
instance and any syntax it accumulated from op/3
declarations in that module, returning the compiler to the base,
Mercury-defined, syntax. So that the "next" module starts fresh
without syntax from other modules polluting the compilation.

Reconsideration

"Worse is Better"⁷

After some discussion on the Mercury maillist, it was resolved
that dynamic syntactic extensions should be external to the
compiler. So, Logical Types has developed separate compiliation
system that converts modules with syntactic enhancements to
plain-jane Mercury equivalents. For modules with no syntactic
enhancements, `ltq' is equivalent to `mmc
--make --infer-all'. For modules with op/3
declarations in the implementation, `ltq' first
parses the module and writes out all terms canonically. After
this translation, the system compiles the modules into the
resulting executable or library.

Operation

This system reduces rather nicely by using facilities provided
by the Mercury compiler, and another declarative system:
make. `mmc -M <file>'
discovers file's dependencies and stores these in a
makefile variable $(<file>.ms) in the file
<file>.dv Given this,
ltq simply builds a makefile with the enumerated
dependencies and then calls the system that manages the dynamic
syntax, which then writes out syntactically-enhanced modules in
their canonical form (called `dopp'). Both
ltq and dopp are available, along
with samples as

dynamic_ops.tgz.

Conclusion

This study came from my experience with the ease of use of
mallable syntax in Prolog and comments in the Mercury sources
about the need to add op/3 declarations as well as
at least two aborted implementation attempts to do so. In the
ensuing process, where I did implement this solution, quite a
discussion emerged on the maillist on the estetic of allowing the
user to introduce or to change syntax, and how to go about doing
it properly. This implementation is one approach, and is offered
to assist those who wish to add syntactic extensions to their
Mercury systems.

---

Endnotes

1	The normal infix operators do not have this grave branding, and for good reason. Imagine writing algebraic statements, such as the following: Aroot = sqrt((B * B - 4 * A * C) / 2 * A) - B while shackled to the grave syntax: Aroot `=` (sqrt(((B `*` B) `-` (4 `*` A `*` C)) `/` (2 `*` A)) `-` B) Note the extra parentheses -- these are now necessary, as the grave syntax does not communicate operator precedence. Also note that the single-character operators are now three times their original size. Given the above, it's tempting to avoid infix syntax altogether... (setq aroot (- (sqrt (/ (- (* b b) (* 4 a c)) (* 2 a))) b)) ...but I have no desire to write out the parsed internal representation by hand (it may look like Lisp, circa 1965, because the syntax of most Lisps (with one notable exception) is also its parsed internal representation), so the Mercury prefix code is therefore presented: '='(Aroot, '-'(sqrt('/'('-'('*'(B, B), '*'('*'(4, A), C)), '*'(2, A))), B)) There! Isn't the canonical tree syntax so much better than the cons syntax? Drek!
2	This is not all that bad, given the documentation and the calculator2.m sample. In calc4.m we provide a straightforward example using the map type.
3	This pronouncement in no way prevented this author from submitting such a proposal to the Mercury team. Ah, the blessed ignorance of youth! All was not in vain, however: every misstep hides the seeds of greatness: one of the responses showed that samples/expand_term.m (the responder was the author of that module, in fact) provides the functionality of Prolog's term_expansion/2 predicate, which is an essential prerequesite for implementing Aspect-Oriented Programming (AOP) in predicate-logic based languages (specifically Prolog). How aspects are implemented in Mercury shall be a topic for another paper.
4	In ISO Prolog op/3 declarations have global extent.
5	[Bratko2001], § 3.3 demonstrates op/3 declared syntax with such charming statements... :- op(300, xfx, plays). :- op(200, xfy, and). Term1 = jimmy plays football and squash. Term2 = susan plays tennis and basketball and volleyball. ...but then the textbook quickly redeems itself -- it is still my preferred Prolog textbook -- with a meatier problem, which I adapt for your enjoyment: ruth was the executive director at wncog. sally was the executive administrative_assistant at wncog. diane was the director of the human_resources department at wncog. juan was the administrative_assistant of the human_resources department at wncog. sunny was the director of the finance department at wncog. stuart was the director of the operations department at wncog. joe was the system_administrator of the operations department at wncog. ?- Who was the director of the What department at wncog. Who = diane, What = human_resources ; Who = sunny, What = finance ; Who = stuart, What = operations ; no I leave the op/3 declarations as a coding challenge to the enterprising reader.
6	Prolog's op/3 declarations have global extent, but I consider this a mistake in the presence of a module system -- op/3 should only affect the module in which is it declared.
7	"Worse Is Better" the catchy title of one of the most fameous apologies (after Socrates', of course), is available from several sources: http://www.jwz.org/doc/worse-is-better.html is one such.

Works Consulted

[Bratko2001]

Prolog Programming for Artificial Intelligence, 3rd ed., Ivan Bratko, Addison-Wesley, Reading, Massachusetts, 2001.

---

author:	Douglas M. Auclair (email: dauclair at hotmail dot com)
date:	January 3, 2006
This document is copyright © 2006 by Logical Types, LLC. under the GNU FDL, version 1.2

Installation Instructions

Installation Instructions for Quicksilver

PowerPC/Apple architecture

Decompress the archive in a directory of your choice (alias==$dir) Modify the script mmc in directory $dir/quicksilver-0.12.1.powerpc-apple-darwin8.3/bin so that the MERCURY_COMPILER variable points to $dir/quicksilver-0.12.2.powerpc-apple-darwin8.3/lib/mercury/bin/powerpc-apple-darwin8.3/lib/mercury_compile and so that the MERCURY_CONFIG_DIR variable points to $dir/quicksilver-0.12.2.powerpc-apple-darwin8.3/lib/mercury Export the following environmental variables with the following values: MERCURY_HOME $dir/quicksilver-0.12.2.powerpc-apple-darwin8.3 MERCURY_STDLIB_DIR $MERCURY_HOME/lib/mercury Add the following paths to your DYLD_LIBRARY_PATH environmental variable: $MERCURY_STDLIB_DIR/lib/reg.gc/powerpc-apple-darwin8.3 $MERCURY_STDLIB_DIR/lib/powerpc-apple-darwin8.3 Add the following path to your PATH environmental variable: $MERCURY_HOME/bin Add the following path to your MANPATH environmental variable: $MERCURY_HOME/man You should be able to do the following with the file hello.m: $ mmc --make hello $ ./hello Since this compiler allows op/3 declarations, the following module, play.m, demonstrates this capability. I intentionally left out some declarations, so compiliation is slightly different: $ mmc --infer-all --make play $ ./play

Creating syntax with op/3 can become complicated when several operators interact to create a term. I've provided a module that prints the canonical representation of a parsed term (write_canonical.m) and a testing module (test_op.m) that allows prototyping of operator declarations and allows submitting terms under that syntax. The whole test system may be built in the usual way: $ mmake test_op.depend $ mmake test_op

Copyright © 2006, Logical Types, LLC. All rights reserved.

qcheck 2.0

Introduction

QuickCheck
is a system developed by John Hughes and Koen Claessen. Its
premise is that comprehesive testing can be obtained by combining
a testing specification language and test data automation
("random testing"). It has been ported to several languages from
its native Haskell: the Mercury programming language provides a QuickCheck facility in their
"extras" distribution, called qcheck.

As it stands, the original qcheck (herein after
referred to as Q1) is an excellent piece of work,
fully capable of testing entire systems. It can decipher how to
generate example data from user-defined types. It also provides
examples for various general and specific situations where the
user may wish to exercise control over the ranges or frequencies
of the data generated. What, then, would need to be changed?

Not much, it turns out. The fundamental aspects of the system
-- comprehesive unit testing fed by randomly-generated values and
directed by a test specification remain intact, but there are
several features to comprehensive testing that can be added to
improve this system. Q1 is good at verifying
that one particular predicate behaves as it should, but it gives
no indication that all the (interface) predicates of a system
have been tested. Further, the user has some control over the
detail reported for each test, but, for a user wishing a summary
report, even the smallest report allowed is too much detail:
adding a facility that give the user complete control over
reportage becomes necessary for larger systems. Finally,
Q1 has an excellent facility to generate random
values for user-defined types, but for primitive types (such as
char, int, and float), the
approach is a bit arcane (only mentioned in one of the last
examples) and lossy -- giving the user control over the random
number generator itself, and integrating that part of the system
with the goal of ease of use will carry forward the automation of
user-defined typed values as well as simplify controlling ranges
of generated primitive values.

These improvements were the aim of this new version: keep the
essence of previous version while adding these new layers to help
the tester verify much larger systems. The first two aims
outlined above, that of comprehension and detail, are addressed
by the new reporting facility that exists both outside
qcheck2 proper and is also integrated into its
state. The third aim, more and simpler control over
randomly-generated values, incorporate changes that now allow the
user to define their own random number generator (or to use the
very excellent one supplied) and also to change the generator's
behavior in the midst of testing. We will address each aim, and
their implementations, in the following sections.

Aims

Aim 1: Comprehension

One question that testing frameworks, such as QuickCheck, must
eventually address, particularly for larger systems, is the one
of completeness. Or, "has the entire functionality of the system
been tested?" Under the first implementation this is a difficult
question to answer, and the root of this problem is a rather
trivial one to fix: the second input argument to
qcheck/[4,7,8] is a string that has the
purpose of describing the test to be performed. Typing this
argument as a string is rather limitting: although
the (human) user can seen the purpose from the description, the
problem is that encoding the test description as a
string does not facilitate reasoning about test
results mechanically, which makes it difficult for the system to
report on what was and, importantly, was not, covered in the
testing.

A new accumulated state variable

The fix to this problem is therefore simple: generalize the test
description argument to any (univeral) type. This way other
systems may, for example, generate a model of the system being
tested and then, after the tests are completed, a method of
tabulating and reporting the results. The internals of
Q1 change in two ways: first, the description
type signature is relaxed, and second, as reportage is spread
across several calls to qcheck/[4,7,8], we will
defer the commitment of outputting results until the user so
determines. In this case, we convert the state variable from
io.state (which commits the output) to a specific
accumulator (that simply collects it):

:- pred qcheck(T, Desc, int, list(list(frequency)),
      general_frequencies, list(user_gen_type(RNG)),
      qstate(RNG, Desc), qstate(RNG, Desc))
<= (testable(T), random_number_generator(RNG)).

:- mode qcheck(in, in, in, in, in, list_skel_in(user_gen_inst(RNG)),
      in, out) is det.

where:

T	the type (pred/func) to test
Desc	a generic type describing the test
int	number of tests
list(list(frequency))	list of specific frequencies (as per Q1)
general_frequencies	list of general frequencies for testing (described later)
list(user_gen_type(RNG))	user-defined types for value generation, as per Q1, specialized on the random number generator
qstate(RNG, Desc)	The state variable collecting test results and keeping the random number generator au courant

The typeclass testable(T) is as per
Q1; and the random number generator typeclass
(random_number_generator(RNG)) will be
discussed under the value generator aim.

For the new types for qcheck2:

:- type general_frequencies == assoc_list(type_desc, list(frequency)).
:- type qstate(RNG, Description)
---> qstate(generator(RNG), map(Description, test_results)).
:- type test_results
---> test_results(int, int, int, bag(univ))
;    falsifiable(univ).

The above qstate type shows that the test
description is mapped to the test_results type, as
qcheck/[4,7,8] is called for each test, it
accumulates the test results indexed by the (generic)
description.

The Program Modelling Tool

As Description can be of any type, we can now allow
the user to pass in a simple description string, as
in Q1, or, alternatively, we can enhance the
description with something that we can use as a declarative
index. In Prolog, we could use the
index of the module-qualified name of the predicate. Mercury is
not as dynamic a system to allow any number of
module/predicate/function values for
Description,¹
so we will employ a preprocessing system to identify and alias
all interface predicate/function types to a uniform (enumerated)
type. One such system is qcpt available from
logicaltypes.com
packaged into the

ltq system. From an input set of files, qcpt
generates the following types:

:- program_module
---> <names of modules in system>.
:- func all_program_modules = list(program_module).
:- func all_public_predicates = list(full_predicate_signature).

:- type public_predicate_signature
---> public_predicate / int.

:- type full_predicate_signature
---> public(program_module, public_predicate_signature).

:- type test_desc == pair(full_predicate_signature, string).

:- type public_predicate
---> <names of interface predicates>.

Example

Say we wish to test a single module, for example the

peano module. By running ...

$ qcpt peano.m

... the file qcheck2.tests_digests_types.m is
generated with the above type declarations and the following
specific realizations:

% ...

:- type program_module
---> peano.

% ...

:- type public_predicate
---> increment
;    peano
;    to_peano.

:- implementation.

all_program_modules = [
peano
].

all_public_predicates = [
public(peano, increment/2),
public(peano, peano/2),
public(peano, to_peano/2)
].

A new reporting facility

Given that we now have collected all the public (or interface)
predicates and functions of a system, it is now also possible to
determine the completeness of the testing, in that all of those
predicates were tested. It simply now falls to a system to
collect the results of testing and report the results. The user
may attack this task any number of ways, but we also provide one
implementation in module
qcheck2.tests_digest_reports. The predicate

show_module_tests_summary(Results,
!IO)

does all this work by comparing the
accumulated test Results (typed as an
assoc_list(test_desc, test_results), where
test_desc is provided by module
qcheck2.tests_digest_types (generated from the
tested module using qcpt), and the
assoc_list is the accumulated result of calling a
set of qcheck/[4,7,8] goals).

The show_module_tests_summary/3 predicate reports
the total number of tests (and those that passed) within each
module and reports the number of predicates that succeeded all
unit testing. This predicate also reports, by name and arity,
the predicates not tested by the framework.

Example

The following report ...

$ ./peano_unit_tests_missing_to_peano

Qcheck2 tested the following modules:
*** 6/6 tests passed on 2/3 predicates in peano
(did not test to_peano/2)

... shows that my modifications to module
peano_unit_tests (I commented out the
to_peano/2 tests) resulted in all tests passing, but
the test suite did not provide full coverage of the
peano module's functionality.

Traditional Reportage

Module qcheck2.reports provides two ways to report
results as Q1 did:

show_test_results_sets(Results, !IO)
show_test_results(Description, test_results, !IO)

The predicate show_test_results_sets/3 simply
iterates over Results, calling
show_test_results/4 at each iteration.
The predicate show_test_results/4 reports the
results from qcheck/[4,7,8] in the style of
Q1.

Example

Here are some of the results reported from running
peano_unit_tests_with_failing_test with a call to
show_test_results_sets/3:

	...
1)	Test description : public(peano, increment / 2) - "Makes sure we get a successor" Number of test cases that succeeded : 100 Number of trivial tests : 0 Number of tests cases which failed the pre-condition : 0
2)	Test description : public(peano, increment / 2) - "Checks increment/2\'s compare" Number of test cases that succeeded : 19 Number of trivial tests : 0 Number of tests cases which failed the pre-condition : 81 Distributions of selected arguments : 13 {0, 1} 5 {1, 2} 1 {2, 3}
3)	Test description : public(peano, to_peano / 2) - "Tests string creation" Falsifiable : i(-68)
	...

The above examples demonstrate 1) a sample
test report where all the tests succeeded (with no reportage on
the test values used), 2) a sample where some
test values were unusable (with reportage), and
3) a sample where the predicate and test
values (by intention) failed the test. These tests are of the
same form as those of Q1. The major difference is
that test tests are reported separately from the
qcheck/[4,7,8] call. This separation allows delayed
(even permanently delayed) reporting of results.

Aim 2: Generation

Q1 offers a dizzying array of options when giving
the user control over what test values are generated and how they
are generated, that is, if these values are to be generated from
user-defined, or complex (not builtin), types. It also offers a
generator of such power that it is dubbed: "The Mother of all
Random Number Generators" by its creator. Impressive as the
above offerings are (and they are, in fact, impressive) there are
two glaring wants: first, one is required to
use the supplied generator -- users are not permitted alternate
generators for their own testing, and this becomes an issue when,
for example, "pure" randomness (such as the values provided by
random.org), or
cryptological-strength randomness is a requirement of the tested
system, and, second, restricting the ranges of primitive
builtins (or other "unbound" enumerated types (such as
integer)) is not directly feasible (albeit possibly
with some esoteric indirection). We address each of these wants
in the new system in this document by turns.

Want 1: User-supplied random number generators

Q1 was built to hide its inner workings. This
software principle is considered to be good practice, but, since
one of the inner workings is random number generation to generate
test values, this good practice obstructs the ability to replace
the random number generator when so required. The new
architecture in qcheck2 exposes the random number
generator in the state variable, allowing its replacement by
alternate equivalent types. The change also comes with a
supplied state initialization predicate that provides the default
random number generator.

The design of the system requires the user to wrap their random
number generator (hereinafter referred to as the RNG)
in type described in the next section, and
it must conform to the following typeclass:

:- typeclass random_number_generator(RNG) where [
% gives a random float on the range [0, 1)
pred rnd(float::out, RNG::in, RNG::out) is det,
pred reseed(int::in, RNG::unused, RNG::out) is det
].

where:

rnd/3	supplies a float between 0.0 and 1.0 and updates the state of the RNG; and
reseed/3	reinitializes the RNG with the seed supplied as the first argument.

Want 2: User-controllable numeric ranges

It is very easy for the user of Q1 to specify a
discriminated-union type and have the system generate test
examples. The problem is for builtin types:
Q1 does not consider bounds when
generating floats, ints
and, surprisingly,
chars.²
One could argue that by choosing unbound types, the user must be
prepared to accept any value those types describe, and indeed
this is true. Where this argument falls apart is when the user
wishes to test predicates within their nominal ranges. Certainly
the test framework should generate test data that tests beyond
the ranges, but when every test case offered is extrinsic,
nothing is gained by submitting that predicate to random
testing. In short, the user must be allowed direct control over
ranges of test values of builtin types when the situation
warrants.

:- type generator(RNG)
---> generator(int_range, float_range, character_type, RNG).

where:

int_range

is either

range(int, int) or unbound

Endnotes

1

Well, this statement is not true in all cases -- if all the tested predicates had the same type and modality then one may simply use the name of the predicate as the Description. See, for example, modules foo and foo_unit_tests included in the distribution. The material point here is that although it is possible to use the name of a predicate as the Description it is not realistic given that most systems use predicates with different types, arities, and modalities.

2

Q1 treats strings as list(int), where each element is a char-equivalent int, which can be positive, negative or, as is most often the case, of very large magnitude.

Contact Information: dauclair at hotmail.com 703-300-0447
Copyright © 2006-2007, Logical Types, LLC. All rights reserved.