Deterministic Random Testing

I've just written an implementation of a weighted random shuffle. Because the function is random, it won't return the same results every time. This makes it hard to unit-test; I can't just run it on some given input and assert it returns some given output. Indeed, by its nature, any ordering of the results is potentially valid. One way to solve this is to run it a large number of times, counting the frequency of various output results, and asserting that roughly the right proportion of results are returned. Of course, exactly how close "roughly right" is, is hard to determine.

This isn't a very satisfactory testing method, however. Get the tolerance too tight, and spurious random differences cause tests to fail unnecessarily. Too loose, and you might miss a subtle logic bug that skews the probabilities of some case.

The weighted random shuffle algorithm calls int rand $limit a number of times, each time passing in a small integer. This effectively uses the RNG like a dice roll, randomly selecting some integer 0 .. $limit - 1. Because each call takes a small integer, and because the algorithm is entirely deterministic for any given set of random results, this suggests a better testing method. If we could instead enumerate all possible returns of random numbers, each one exactly once, we can generate all possible results from the shuffle algorithm in their ideal proportions. Because this will be an exact deterministic count, free from randomness, we can assert exact values for the results.

So this is what I did. I've created a module, for now simply called Unrandom, which exports one function, unrandomly. It is used like the following:

use Unrandom 'unrandomly';

unrandomly {
  my $da = 1 + int rand 6;
  my $db = 1 + int rand 6;
  say "Roll 2d6: $da + $db = " . ($da+$db);
};

The unrandomly function has the effect of replacing the rand function with one under its control while it runs the block of code. It runs the block of code a number of times, enumerating the entire tree of possible return values, in a given deterministic order:

Roll 2d6: 1 + 1 = 2
Roll 2d6: 1 + 2 = 3
Roll 2d6: 1 + 3 = 4
Roll 2d6: 1 + 4 = 5
Roll 2d6: 1 + 5 = 6
Roll 2d6: 1 + 6 = 7
Roll 2d6: 2 + 1 = 3
Roll 2d6: 2 + 2 = 4
...
Roll 2d6: 6 + 5 = 11
Roll 2d6: 6 + 6 = 12

Because each possible combination is returned exactly once, we can unit test that this dice-rolling algorithm does in fact give us the right distribution of results; there will be exactly one 2, two 3s, etc... We don't have to run it a few million times, and check that we got "roughly" the right number; we can be exact.

While I'm using this code in a unit-test, there's nothing directly test-related in the code. It could be useful anywhere that statistical modelling is used, or other problems involving random integer generation.

I'm now just looking for a good name to call it, so I can extract it from the unit tests and give it a life of its own on CPAN.

Suggestions anyone?

Extended colour support, terminals, and ECMA-48

tl;dr summary: Terminal authors - please accept CSI 38:5:123 m as well as anything else, to set extended colours. NOTE THE COLON. Many terminals these days are starting to support extended colour modes; specifically things like 256 colours. They're all doing it wrong.

CSI 38;5;123 m

No no no no no. That is NOT what you think. It does not select colour 123 from palette 5. CSI arguments are separated by semicolons. This sets three unrelated SGRs; 38, 5, and 123. 38 sets a foreground colour to .. er.. nothing in particular. 5 is blinking mode, 123 has no defined meaning to my knowledge. All the other following are exactly identical:

CSI 5;38;123 m
CSI 38 m CSI 5 m CSI 123 m

ECMA-48 already defines a perfectly good way for parameters to take sub-parameters. It's the colon. The correct way to encode this concept is

CSI 38:5:123 m

Why does this matter? It matters for parsers not to have to understand what is going on. Consider

CSI 3;38:9:5:4:3:2:1;11;1

This is equivalent to

CSI 3 CSI 38:9:5:4:3:2:1 CSI 11; CSI 1

I.e. I have no idea what palette 9 is, but I can definitely parse out the contents of this SGR from the others, knowing exactly where it ends. I don't have to "just know" that palette 9 happens to take 5 parameters. The CSI encodes this. My own terminal emulator library, libvterm, already understands these colon-based arguments. It parses them correctly. This is important for other palettes that don't take just one value. For example, the RGB, RGBA, CMY, and CMYK palettes. It's vital to be able to parse out these sub-arguments from the single SGR 38 or 48. Standards exist for a reason, people. Please use them.

---

Edit 2012/12/20: actually, I have recently learned that xterm now supports this in its correct form as well, since xterm patch 282.

When failure isn't failure

Lately I have been looking at two different problems, with a common theme.

My first problem concerns Parser::MGC, and its ability to read input lazily as needed, rather than needing to slurp an entire file all at once. This ability is provided by the from_reader method, which takes a CODE reference to a reader function.

As the documentation points out, this is only supported for reading input that's broken across skippable whitespace. This is because it's implemented by calling the reader function to look for more input if the current input buffer is completely exhausted. It cannot work in general, for splitting the input stream arbitrarily, because Perl's regular expression engine does not give sufficient feedback. It is not possible to ask, after a match attempt, whether the engine reached the end of the stream, For example, when looking for a match for m/food/, an input of "fool" definitely fails, whereas an input of "foo" is not yet a failure, because it might be that reading more input from the stream can complete the match. If the regular expression engine gave such feedback, then the reader function could be invoked again to provide more input that may help to resolve the parse.

My second problem concerns how to handle UTF-8 encoded data in nonblocking reads. An IO::Async::Stream object wraps a bytestream, such as a TCP socket or pipe. If the underlying stream contains UTF-8 encoded Unicode text, then the Unicode characters need to be decoded from these bytes, by using the Encode module.

The trouble here is that Encode does not provide a way to do this sanely. It is quite likely that a multibyte UTF-8 sequence gets split across multiple read calls. To cope with such a case, Encode has a mode where it will stop on the first error it encounters (called FB_QUIET), returning the prefix it has decoded so far, and deleting the bytes so consumed from the input. The intention here is that another call supplies more bytes, and it continues from there. Problem is, it returns on any failure, whether that's running out of input bytes or encountering an invalid byte. Without the ability to distinguish these two different conditions, it is impossible to handle nonblocking or stream-based UTF-8 decoding while still having sensible error handling.

The common theme of these two problems is that neither considers the nature of a failure, treating various reasons the same. Both cases have two kinds of failure: one a failure because something has been received that is not correct; the other a failure because something that would be correct has simply not yet been received.

Sometimes, failure is not really failure at all. Sometimes it is simply deferred success that is yet to happen.

Carp from somewhere else

Carp provides two main functions, carp and croak, as replacements for core Perl's warn and die. The functions from Carp report the file and line number slightly differently from core Perl; walking up the callstack looking for a different package name. The idea being these are used to report errors in values passed in to the function, typically bad arguments from the caller.

These functions use the dynamic callstack (as provided by caller()) at the time the message is warned (or thrown) to create their context. One scenario where this does not lead to sensible results is when the called function is internally implemented using a closure via some other package again.

Having thought about this one a bit, it seems what's required is to split collecting the callstack information, from creating the message. Collect the information in one function call, and pass it into the other.

This would be useful in CPS for example. Because the closures used in CPS::kseq or kpar aren't necessarily invoked during the dynamic scope of the function that lexically contains the code, a call to croak may not be able to infer the calling context. Even if they are, the presence of stack frames in the CPS package would confuse croak's scanning of the callstack. Instead, it would be better to capture the calling context using whence, and pass it into whoops if required for generating a message.

For example, this from IO::Async::Connector:

sub connect
{
   my ( %params ) = @_;
   ...

   my $where = whence;

   kpar(
      sub {
         my ( $k ) = @_;
         if( exists $params{host} and exists $params{service} ) { 
            my $on_resolve_error = $params{on_resolve_error} or whoops $where, "Expected 'on_resolve_error' callback";
            ...
}

These functions would be a fairly simple replacement of carp and croak; capture the callsite information at entry to a function, and pass it to the message warning function.

It does occur to me though, the code will be small and self-contained, and not specific to CPS. I think it ought to live in its own module somewhere - any ideas on a name?

IPv6 in Perl

A lot of people are talking about IPv6 lately. And perhaps with good reason - it's been years in coming, but finally we're really starting to run out of IPv4 addresses. Tools like the IPv4 Address Report may put a certain amount of panic on things with their realtime Flash-based countdown widget, but the problem is real and does need sorting.

The latest development release of Perl; perl-5.13.9, now has full support for IPv6, and the new address handling functions specified in RFC 2553. The new functions all live in Socket.

As well as the low-level AF_INET6 constant, and the pack_sockaddr_in6 and unpack_sockaddr_in6 structure functions (already in place in 5.13.8 in fact), there is now the full set of getaddrinfo, getnameinfo and associated constants. These allow fully protocol-agnostic handling of connections and addresses. There is now enough in core to support IO::Socket::IP. This is a fully protocol-agnostic replacement of IO::Socket::INET.

use IO::Socket::IP;

my $sock = IO::Socket::IP->new(
   PeerHost    => "www.google.com",
   PeerService => "www",
) or die "Cannot construct socket - $@";

printf "Now connected to %s:%s\n", $sock->peerhost_service;

...

What could be simpler?

Perhaps now is the time to make a case for putting IO::Socket::IP itself in the core distribution, such that when perl-5.14.0 comes out, it will be properly ready for the next 30 years of the Internet?

IO::Socket::IP's API is designed to be a drop-in replacement for the IPv4-only IO::Socket::INET. Any program currently using INET ought to work exactly the same, by simply substituting IP instead, and now will also work on IPv6.

If you maintain a distribution that uses IO::Socket::INET, please try out IO::Socket::IP instead. I'd be very keen to hear from anyone who finds it doesn't JustWork in their situation.

See also my earlier post on the subject; Perl - IO::Socket::IP

Perl - IO::Async - version 0.34

There's been four releases of IO::Async since I last wrote about version 0.30. Here's a rough summary of the more important changes and additions between then and version 0.34:

• New Notifier class IO::Async::Timer::Absolute, to invoke events at a fixed point in the future.


• New Notifier class IO::Async::PID, to watch a child process for exit(2).


• New Notifier class IO::Async::Protocol::LineStream, to implement stream protocols that use lines of plain text.


• New method on IO::Async::Protocol that wraps connect(2) functionallity, allowing for simpler network protocol client modules.


• IO::Async::Loop->connect's on_connect_error and IO::Async::Loop->listen's on_listen_error continuations now both receive errno information.


• New direct name resolution methods on IO::Async::Resolver for getaddrinfo(3) and getnameinfo(3). The resolver is now directly accessible from the IO::Async::Loop.


• IO::Async::Resolver supports deadline timeouts.


• IO::Async::Stream->write supports taking a CODE reference to dynamically generate data for the stream on-demand.


• IO::Async::Stream->write supports an on_flush callback.


• The IO::Async::Loop->new magic constructor now caches the loop. This is useful for wrapping modules, other event system integration, etc..


• Documentation has been rearranged to add new EVENTS sections, documenting the events that Notifier classes can fire either as callbacks in coderefs, or as methods on subclasses.


• Various bugfixes, other documentation additions

Event loops and Jenga; or 24 Advent Calendar Events in One Go

There are many event loops systems in Perl. Do they play together?

I was thinking about this recently, at my LPW2010 talk about IO::Async. In the hackathon the following day, I managed to write IO::Async::Loop::POE; a way to run IO::Async atop POE.

So I started thinking further; if you can run one event loop system on top of another, how high can we stack them? Can we build a tower, putting each atop the previous, growing taller. Each new layer we try to add would start to get harder, more difficult, increasing the chances the whole thing came crashing down. Sortof like a Jenga tower.

So what would a Perl event loop Jenga tower look like?

My attempt looks like this: (326 lines, jenga.pl)

The output looks something like this:

$ perl jenga.pl
AnyEvent resolved 127.0.0.1:80
Glib reads Hello world!
POE reads Hello world!
POE resolved 127.0.0.1:80
IO::Async reads Hello world!
AnyEvent reads Hello world!
AnyEvent listener accepted
POE listener accepted
IO::Async resolved 127.0.0.1:80
AnyEvent connected received
POE connected received
IO::Async listener accepted
IO::Async connected received
Glib child exited 0
POE child exited 0
IO::Async child exited 0
AnyEvent child exited 0
Glib timer
POE timer
IO::Async timer
AnyEvent timer
^CIO::Async SIGINT
AnyEvent SIGINT
POE SIGINT
Stopping...

That's 24 events. Count them. It combines Glib, POE, IO::Async and AnyEvent. It performs a basic filehandle read, a child process watch, and a timed wait in each of these four systems. Because Glib lacks signal watching, only the other three perform this. The other three are also used to perform name resolution, socket listening, and socket connecting.

Everyone seems to be doing Advent Calendar blogs this year. 24 daily posts, each showing one small thing. Someone suggested I should write a Perl Event systems advent calendar. So perhaps here, consider this to be one. Except it has 24 windows all in one go.

As it turns out, it's possible to make this tower a little higher. There's a module to run Event beneath Glib; that is, it replaces the core polling function of Glib to use Event instead. And I suspect it may just about be possible to run Tk on Glib, and the POE on Tk.

At some point in the new year, I have some plans to turn this one-program script into a more useful resource of examples and translations. The Rosetta Stone for Unix provides a cross-reference for looking up Unix concepts between different systems. I feel that a similar attempt at Perl event loops could be quite useful too.