A while back I wrote a parser for R6RS Scheme numbers, or the
string->number procedure. Numbers in Scheme are somewhat
sophisticated and can be written in some surprising variations and I
wanted some test inputs for verifying that the parser doesn’t crash on
valid inputs. Luckily, the number syntax is specified in such a way
that a Prolog program easily can be written that generates test inputs.
SWI-Prolog supports an alternative syntax called definite clause grammars (DCG) that is suitable for this task. The specification in R6RS is written in a similar BNF syntax so translation is very easy. Except for this there is nothing particular about Prolog itself that makes it suitable for this task and alternatives such as miniKanren or µKanren could be used instead.
Let’s get down to numbers. The datum syntax can be found in R6RS section 4.2.1, which has this to say:
The rules for ⟨num R⟩, ⟨complex R⟩, ⟨real R⟩, ⟨ureal R⟩, ⟨uinteger R⟩, and ⟨prefix R⟩ below should be replicated for R = 2, 8, 10, and 16. There are no rules for ⟨decimal 2⟩, ⟨decimal 8⟩, and ⟨decimal 16⟩, which means that number representations containing decimal points or exponents must be in decimal radix.
In the following rules, case is insignificant.
So we’ll need to remember to replicate the rules for every radix and to handle both upper and lower case letters. (Luckily DCG handles the first for us). This text is followed up by rules that look something like this (made to be less compact than in the specification):
⟨digit⟩ → 0 ∣ 1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 ∣ 6 ∣ 7 ∣ 8 ∣ 9
…
⟨number⟩ → ⟨num 2⟩ ∣ ⟨num 8⟩ ∣ ⟨num 10⟩ ∣ ⟨num 16⟩
⟨num R⟩ → ⟨prefix R⟩ ⟨complex R⟩
⟨complex R⟩ → ⟨real R⟩
∣ ⟨real R⟩ @ ⟨real R⟩
∣ ⟨real R⟩ + ⟨ureal R⟩ i
∣ ⟨real R⟩ - ⟨ureal R⟩ i
∣ ⟨real R⟩ + ⟨naninf⟩ i
∣ ⟨real R⟩ - ⟨naninf⟩ i
∣ ⟨real R⟩ + i
∣ ⟨real R⟩ - i
∣ + ⟨ureal R⟩ i
∣ - ⟨ureal R⟩ i
∣ + ⟨naninf⟩ i
∣ - ⟨naninf⟩ i
∣ + i
∣ - i
…
If one’s not familiar with BNF this might be tricky to read. Rules are surrounded by ⟨brackets⟩ and can be referred to using the same syntax. Things outside the brackets are right arrows (→) saying that the thing on the left side is defined as what’s on the right side. The right side contains references to rules, vertical bars (∣) to define multiple options, and literal characters to say that “this character must be here”.
One way to use this is for determining if a particular string is a
valid number or not. The first rule defines a number as one of four
possible things. To see if a string is a number a program can follow
the rules and try to match every character in the string to a
character in a rule. For the string "52697461" there should be a way
to get all the way from the ⟨number⟩ rule to ⟨digit⟩, and not just
once but eight times. The path might be through ⟨num 10⟩ or
⟨num 16⟩, it doesn’t really matter which.
Here is one (abbreviated) path that takes us through the rules from
⟨number⟩ to "+i": ⟨number⟩ ⇒ ⟨num 2⟩ ⇒ ⟨prefix 2⟩ ⟨complex
2⟩ ⇒ (prefix can be empty) ⇒ ⟨complex 2⟩ ⇒ + i. A program can be
written that walks all paths in the rules and when it finds a dead end
prints the characters it has collected along the way, and then
backtracks to continue on another path.
In Prolog with DCG the program looks remarkably similar to the rules in the specification (disregarding the insignificance of case for a moment):
scheme_number --> (num(2); num(8); num(10); num(16)).
num(R) --> prefix(R), complex(R).
complex(R) --> (real(R);
real(R), "@", real(R);
real(R), "+", ureal(R), "i";
real(R), "-", ureal(R), "i";
real(R), "+", naninf(R), "i";
real(R), "-", naninf(R), "i";
real(R), "+i";
real(R), "-i";
"+", ureal(R), "i";
"-", ureal(R), "i";
"+", naninf(R), "i";
"-", naninf(R), "i";
"+i";
"-i").
real(R) --> (sign, ureal(R);
"+", naninf(R);
"-", naninf(R)).
naninf(10) --> ("nan.0"; "inf.0").
ureal(R) --> (uinteger(R);
uinteger(R), "/", uinteger(R);
decimal(R), mantissa_width).
decimal(10) --> (uinteger(10), suffix;
".", digits(10), suffix;
digits(10), ".", digits0(10), suffix;
digits(10), ".", suffix).
uinteger(R) --> digits(R).
prefix(R) --> (radix(R), exactness;
exactness, radix(R)).
suffix --> ("";
exponent_marker, sign, digits(10)).
exponent_marker --> ("e"; "s"; "f"; "d"; "l").
mantissa_width --> (""; "|", digits(10)).
sign --> (""; "+"; "-").
exactness --> (""; "#i"; "#e").
radix(2) --> "#b".
radix(8) --> "#o".
radix(10) --> ""; "#d".
radix(16) --> "#x".
digit(2) --> ("0";"1").
digit(8) --> ("0";"1";"2";"3";"4";"5";"6";"7").
digit(10) --> ("0";"1";"2";"3";"4";"5";"6";"7";"8";"9").
digit(16) --> ("0";"1";"2";"3";"4";"5";"6";"7";"8";"9";
"a";"b";"c";"d";"e";"f";
"A";"B";"C";"D";"E";"F").
digits(R) --> (digit(R);
digit(R), digits(R)).
When developing ones own solution I suggest to start small, focus on
the basic rules with almost only characters, and build on more rules
later when that’s working. There are two primary ways to use this
program. Firstly it can check if a string is a valid number or not.
Load the program into SWI-Prolog and call scheme_number with a
string and the empty list. Prolog will print true or false and might
wait for the user to type a command (try . or ;).
$ swipl -s numbers.pl
% numbers.pl compiled 0.00 sec, 42 clauses
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.6)
…
?- scheme_number("52697461", []).
true ;
true ;
true ;
true ;
false.
?- scheme_number("42i", []).
false.
From the first test it looks like there are four different ways to
parse "52697461" as a number (e.g. as decimal and hexadecimal). The
program can also be run in the other direction and generate all numbers:
$ swipl -s numbers.pl
% numbers.pl compiled 0.00 sec, 42 clauses
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.6)
…
?- forall(scheme_number(X, []), writef("%s\n", [X])).
#b0
#b1
#b00
#b01
#b000
#b001
…
Oops! It is really printing all numbers. Some modifications need to be made before the program is useful. The final version has case-insensitivity added and some sample strings for those cases that would otherwise generate digits forever. After these modifications it prints useful test inputs, although it can no longer recognize all numbers. Even though the search space is now finite the program still outputs 523 908 unique numbers. But that is just a consequence of the notation.
The program finds some very strange looking numbers, e.g.
#e#d-inf.0-49.83e+49|53i and #o#e-0755/0755@-0755/0755. The first
is the exact decimal complex number with real part -∞ and
imaginary part -49.83⋅1049 with mantissa width 53. The
second is the octal exact complex number with both magnitude and angle
-1 (i.e. -1∠-1). Kind of hard to see, though. Many Scheme
implementations do not support exact complex numbers and they should
reject these inputs.
The testing doesn’t stop after all the lovely test cases have been fed through the parser that’s being tested. Unfortunately the program can’t generate all invalid numbers, so using its output does not completely test an implementation. A parser tested only using the strategy presented here could accept or even crash on invalid inputs. (However if crashes are possible then american fuzzy lop can be used to automatically find crashing test cases).
The fact that the parser doesn’t reject valid inputs also doesn’t say much about if the input was parsed correctly. However the test inputs can be fed through the parser and printed, and then be compared to a reference printout (e.g. generated with a trusted implementation).
This was written as part of a series of articles on stuff that has been lying around on this website for a long time without any real commentary. The original version of the number generator was written in 2012, revised the following year, and revised again for this article.