Delving the depths of computing,
hoping not to get eaten by a wumpus

By Timm Murray

Quoting in Documentation

2015-08-28

I just ran across a small niggle in the DateTime::Format::Strptime docs:

%N Nanoseconds. For other sub-second values use %[number]N.

I needed a 3-decimal sub-second value, so I went off and dutifully wrote:

my $formatter = DateTime::Format::Strptime->new(
    pattern => q{'%FT%T.%[3]N%z'}, 
);

Note my simple-stupid copy of the square brackets. This creates dates like:

2015-08-28T13:31:55.%[3]N-0400

Which is not at all what I had in mind. Then I smacked my forehead, remembering printf() conventions, and wrote:

my $formatter = DateTime::Format::Strptime->new(
    pattern => q{'%FT%T.%3N%z'}, 
);

No square brackets, and everything works fine.

This issue of direct quoting conventions reminds me of an entry on writing style from the Jargon File:

Consider, for example, a sentence in a vi tutorial that looks like this:

Then delete a line from the file by typing “dd”.

Standard usage would make this

Then delete a line from the file by typing “dd.”

but that would be very bad — because the reader would be prone to type the string d-d-dot, and it happens that in vi(1), dot repeats the last command accepted. The net result would be to delete two lines!

This isn’t quite a “standard usage” issue. It’s an American usage issue. British style for quotes sensibly puts the period on the outside, in agreement with the Jargon File above.

The problem with the Strptime method above is that the convention is ad-hoc, hoping that the reader will catch on to the author’s intent. This tends to cause problems for newer programmers, and even more experienced programmers may take a few iterations to catch on. In some cases, it could also confuse programmers with a different social background.

One solution is to lay out a style guideline at the beginning of the documentation. Programming books will often do this. It’s also similar to the way RFC2119 lays out the definitions of “MUST”, “SHOULD”, etc. in a way that’s intended to be used by other RFCs.

The problem here is that you’re expecting your readers to know that much more before getting into the nuts and bolts of your library. Language and protocol definitions need to be specified very precisely, but library documentation doesn’t necessarily require that–clarity of understanding and succinctness can be better than rigor. Plus, there’s bound to be competing systems of style guidelines, and readers will have to know all of them, or at least the more popular ones.

Instead, it’s enough to give a quick example. Consider if the Strptime docs had said something like:

%N Nanoseconds. For other sub-second values use %[number]N. Example: ‘%T.%3N’

And now there is no question on the square brackets being included in the string or not. Everything the reader needs to know is encapsulated in a single location of the docs–no referencing back to other sections or documents.

Don't use is() in Test::More

2015-06-19

#!perl
use v5.14;
use warnings;
use Test::More tests => 2;

my $val = "2.123450";

is( $val, 2.123450 );
cmp_ok( $val, '==', 2.123450 );

This results in:

1..2
not ok 1
#   Failed test at tmp/bad_is.pl line 9.
#          got: '2.123450'
#     expected: '2.12345'
ok 2
# Looks like you failed 1 test of 2.

The issue is fairly obvious when it’s laid out like this: is() does a string comparison, which means that trailing zero matters. One day, though, I promise you, you’ll hit a problem like this and will spend hours debugging it, only to smack your forehead when you finally see it. You can prevent that by explicitly giving a comparison operator to cmp_ok() instead.

This is somewhat similar to the issues seen in the ‘==’ operator in JavaScript and PHP, where the language makes a guess about how to coerce the types and gets it wrong (or at least, produces unexpected behavior). Those languages invented ‘===’ to solve that, which is madness.

Musings on Big-Oh and the Schwartzian Transform

2015-06-10

Not a new topic, but one I’ve been mulling over recently.

Let’s start with a basic sort operation in Perl over a series of DateTime objects:

my @sorted_dates = sort { DateTime->compare( $a, $b ) } @dates;

Perl 5.6 and earlier used quicksort, and after that used mergesort. There’s also a sort pragma if you want to specify something else.

Now, quicksort has an average runtime of O(n * log(n) ), but there’s a few terrible cases where it goes quadratic–O(n2). Quadratic is bad; the only good thing about quadratic is that it’s not polynomial (that is, O(2n), where the exponent is variable rather than the base, which makes us start using phrases like “assume we have until the end of the Universe to finish this run . . . “). The one nice thing is that quicksort has a few friendly cases where it’s O(n). With mergesort, almost everything is O(n * log(n) )–that is, giving up a few nice cases in exchange for never going quadratic.

What really is all this Big-Oh stuff? One way to think about it is that it’s the number of times you loop over something. It doesn’t tell you how long each iteration of the loop will take, just on how many times it will iterate. If you’re walking a list, that’s O(n), where n is the number of elements of a list. If you walk it twice, that’s O(2n). For an algorithm that runs in O(n * log(n)), things will take longer than O(n) when n > 10 (because log(10) == 1).

(This is why a hash lookup is sometimes slower than a balanced binary tree. Hash lookups are constant time, O(1) (well, it is if we squint a little), and balanced binary trees are O(log(n)) worst case. But that constant time in hashes is very big, and the tree’s loop is very tight. It doesn’t take many entries for hashes to catch up, though.)

So when we look at the sort above, we notice that we’ll want to keep expensive operations out of the subroutine we’re passing to sort. That subroutine will be called O(n * log(n)) times (roughly speaking), so let’s try to hoist expensive operations out of it.

This is exactly what the Schwartzian Transform does. Let’s start by having a map() execute before the sort to pull out some easily sortable data from our DateTime objects. The Unix epoch will do nicely for this (use hires epoch if you need to):

my @sort_friendly_dates = map {[ $_->epoch, $_ ]} @dates;

Now we can modify our sort algorithm to pull out that first entry in the arrayref and do a straight numeric comparison:

my @sorted_dates = sort { $a->[0] <=> $b->[0] } @sort_friendly_dates;

Perl’s spaceship (<=>) operator does a numeric sort, which will be faster than the lexicographical sorting of the cmp operator (which gets even more complicated if you’re Tom Christiansen). If you can sort based on numbers rather than strings, that’s always better.

Now we want to get at our original object rather than the arrayrefs we created, so we do another map() to pull that out:

my @final_sorted_dates = map { $_->[1] } @sorted_dates;

Now let’s combine all that together in a single statement to get the Schwartzian Transform as it’s usually seen:

my @sorted_dates = map { $_->[1] }
    sort { $a->[0] <=> $b->[0] }
    map {[ $_->epoch, $_ ]} @dates;

This ends up being O(2n) for the two maps, plus O(n * log(n)) for the sort. But we’re making that O(n * log(n)) cheaper per iteration, so it’s a win overall if @dates is big enough.

Can we take this further? If we can collapse that arrayref into a straight string or number, then we can remove the subroutine passed to sort entirely. This means perl will do a lexicographic sort completely within its internals without the extra time taken to call a Perl subroutine (which more than makes up for the extra time of a lexicographic sort rather than straight numeric). This isn’t always easy, but in this case we could do it by throwing away our DateTime objects entirely in the first map() (first by order of operations, that is), and then rebuilding it with the epoch data passed to the second map():

my @sorted_dates = map { DateTime->from_epoch( epoch => $_ ) }
    sort
    map { DateTime->epoch } @dates;

This form is called the “Guttman-Rosler Transform”. It may or may not be faster than an equivalent Schwartzian, depending on how expensive destructing/reconstructing the object is. That would also do all kinds of fucky things to runtimes with threaded garbage collectors, but it’s not too bad for a refcounting language like Perl5. If you’re serializing things into strings, care has to be taken that you’ll get the output objects deserialized the same way on the flip side. Big-Oh is the same as the Schwartzian.

One thing that I think is overlooked about the Schwartzian is improving separation of concerns. The sort routine is not responsible for formatting data in a way that’s sortable, and there’s no need to copy/paste the same code for $a and $b. That’s the sole job of the first map(). Once you recognize the idiom, your eyes can easily fall to the place where the data munging is happening. This makes the Schwartzian a nice idiom even when its performance improvement is marginal.

Device::GPS v0.714874475569562

2015-05-23

Device::GPS v0.714874475569562 is released. I started writing this after looking at the problems with Perl’s GPS support. Using a callback interface eliminates the delay in GPS::NMEA, where it polls the serial connection until it gets the NMEA sentence it’s looking for.

Should be up on CPAN mirrors shortly.

Welcome, EEWeb.com Readers

2015-05-18

The Wumpus Cave is EEWeb.com‘s site of the day! Here’s a few links to old entries that y’all might be interested in:

Happy reading!

Improving Perl's GPS Support

2015-05-17

A little while ago, I wrote an article for PerlTricks on GPS and Perl, primarily using the GPS::NMEA module. Accessing GPS data was one part of a larger project I’m working on (recording telemetry data for car racing). Unfortunately, I also discovered some limitations in the GPS::NMEA module.

Firstly, as we discovered after the article was published, the coordinates returned are not decimals that you can just stick into Google Maps and get the right location. I had thought the inaccuracy was due to taking readings indoors (it was only off by a few miles), but it turned out to be something else. The decimal portion is actually the number of arcminutes rather than an actual decimal. This isn’t documented anywhere in the module. The correction is easy, but I feel like the module ought to be doing it for me, or at least document what’s coming out.

Secondly, the module gathers data like this:

until ($self->parse eq 'GPRMC') {
    1;
}

This comes out of GPS::NMEA->get_position(). This reads the data off the serial port line-by-line until it sees one starting with “GPRMC”, which indicates the line has the position data. There are other commands being sent, such as altitude and velocity, but those are thrown away until it hits the next position data line. This means that if you want to read both position and velocity (as I do in my project), you’ll be waiting much longer than you should for each of those.

This would benefit from a callback interface to get the data as it comes in a loop.

Lastly, there are license issues. It’s under the classic “same terms as Perl itself”, which is problematic. What version of Perl? Earlier ones were GPL-only, and newer ones add the option for the Artistic license.

There are issues with the Artistic license itself, too, especially the first version (which Perl5 still uses). The FSF has criticized it as “too vague; some passages are too clever for their own good, and their meaning is not clear. We urge you to avoid using it, except as part of the disjunctive license of Perl.”

Also, you can’t guarantee what terms Perl will have in the future. While it’s unlikely to happen, the US government could argue that since Larry wrote the early versions under their watch, they could swallow up the whole thing. A more likely scenario (given the problems with the Artistic license above ) is that the Perl devs could change the license at any time. They wouldn’t necessarily change it to something you like–remember the flamewars about the GPLv3 in the larger FOSS community?

I hate to rewrite GPS::NMEA, because some of the comments and code indicates that there was a lot of time spent getting it to work with the quirks of different GPS modules and OSen. For Perl code that originated in the late-90s, it’s very well written. If it were just a matter of the first two technical issues, we could probably work out a better interface on top of the existing code. I’m uncomfortable working with the license issues, though, so a rewrite may be the only way to go.

Really, really small computers from UMN

2015-04-16

https://www.youtube.com/watch?v=xYct31tFHnc

Top Gear is dead . . .

2015-03-25

. . . and I’m OK with that. I was rewatching shows from series 7 and 8, and those were the types of shows I wanted to watch. At some point, it became less about cars and more about cocking about in vaguely car-related ways. It was still fun, and I still watched it, but I felt like it was missing something.

The BBC may try to revive it with new presenters. Problem is, the current three have perfect chemistry together, which was a 1 in a million chance of working out (which is the fundamental reason why Top Gear Australia and US were never going to work). They might try to change it back into a straight car show like old Top Gear, but the brand probably can’t go back to that.

The current presenters may try to revive the concept under a new organization (Netflix? who knows). Fans underestimate the complications involved in that. They may not have access to the track, studio, production staff, or connections to the car industry that they did before. There’s more to putting on a show than filming a couple of old blokes with cars.

Meanwhile, some of the actions of the fanbase have been horrid. Jezza punches a guy for not providing hot meals, and they blame the BBC for suspending and firing Jezza. Plus, the victim started to get death threats, which is all kinds of fucked up.

Even the fanbase that doesn’t go to the deep end of the shit pool still dips their toes in. “Je Suis Clarkson”? Charlie Hebdo is a satirical newspaper that got shot up by religious extremists. Clarkson punched a guy in the face. Let’s have some perspective here, huh?

I still really like Regular Car Reviews. All the review sites were trying to ape the Top Gear style for years. Regular Car Reviews is the first in a while to try something different. Their 1995 Miata review was an instant classic (just like the car itself).

How did Linux become a second-class citizen on Arduino?

2015-03-20

Using Linux with Arduino reminds me a lot of using Oracle with Perl; it works, but there’s a lot of things that aren’t up to the same level as other combinations. For Oracle and Perl, it’s somewhat understandable, as Perl comes from a FOSS background and Oracle, well…doesn’t.

That’s not true of Arduino however. Mac OSX seems to have better support than Linux, and Windows is almost seamless. I find it all very odd, because when it comes to most FOSS stuff, Linux support is easy, Mac OSX tends to work with minimal effort, and you’re a bit surprised when things work right on Windows. Somehow, Arduino has gone the other way round.

Just some examples I’ve come across:

I suspect that these issues came about because Arduino was successfully marketed to people outside of the normal FOSS community. This meant a lot of people were developing and testing things on Windows and often Mac, but rarely Linux.

Got stuff that needs to be attached to other stuff? Use Attach::Stuff

2015-03-06

I’m in the middle of a project that’s going to be continaing a Raspberry Pi, the Rpi camera module, a GPS breakout board, an accelerometer breakout board, and a microphone breakout board. All that needs to be screwed into a lasercut case.

Now, the lasercutter at The Bodgery takes its own special format (naturally), but can also import DXF and PLT files, among others. Both of these can be exported by Inkscape, and I’ve generally found the PLT export works a little better. In any case, Inkscape can take an SVG file, which I can create programmatically in Perl easily enough.

So I worked out how to do all that with the SVG module. Thing is, the majority of boards are covered by these steps:

  1. Draw a box x mm by y mm
  2. Place a list of screw holes at designated coordinates, which all have the same radius

Which is really easy to wrap up into a single class, which gives back an SVG object with the bits above already done. If there’s something slightly more complicated to do (like making a box for the Rpi camera’s lens), then you can draw that in yourself with the SVG object you have in hand.

Here’s an example for Adafruit’s Ultimate GPS module:

use v5.14;
use warnings;
use Attach::Stuff;

my $attach = Attach::Stuff->new({
    width                => 26,
    height               => 34,
    screw_default_radius => 1.25,
    screw_holes          => [
        [ 3,       3 ],
        [ 26 - 3,  3 ],
    ],
});
my $svg = $attach->draw;
print $svg->xmlify;

All the stuff from the Raspberry Pi Foundation has schematics out there already, so that was easy. Adafruit’s breakout boards, however, don’t seem to have any published schematics (Sparkfun isn’t any better, as far as I can tell), so I got out the callipers and started measuring. Had to do some guess work with the screw hole location and size. After a few iterations of prototypes being etched into cardboard, I got a design that looks like it will work.

Attach::Stuff v0.652389025389315 should be out to the CPAN mirrors shortly.

← Prev Next →

Copyright © 2024 Timm Murray
CC BY-NC

Opinions expressed are solely my own and do not express the views or opinions of my employer.