Posted by Tom Moertel
Tue, 12 Sep 2006 21:30:00 GMT
I am on the planning committee for the 2006 Pittsburgh Perl
Workshop and serve as the primary point of contact for
speakers. That means I get the inside scoop on the talks.
And from what I have seen, all I can say is, These
talks kick ass. Well, actually I can say one more thing:
If there is any possible way you can manage to get yourself to Pittsburgh, Pennsylvania
on Saturday, 23 September 2006, do not wait, do not mull
it over, register now for the Pittsburgh Perl Workshop.
If you miss this one, you’ll probably end up weeping in front of your keyboard for a long, long time.
PPW ’06 has speakers from the worlds of finance,
bioinformatics, engineering, politics, health care, insurance, Web-2.0
start-ups, environmental monitoring, and mathematics. And they all
have fascinating things to share with you about how they make Perl
work for them and about how you can make Perl work for you.
Registration is only $20 – can you imagine that, in an age when
programming conferences routinely cost hundreds if not thousands of dollars? – and all of the talks show you how to use
Perl to do real work, solve real problems, and make your real life as a
programming professional a whole lot saner. Even if you think
you don’t care about Perl, you ought to be a part of
PPW ’06 just for the rare opportunity to discover something
you may have overlooked. (At $20, when are you ever going to get
a chance like this again?)
Posted in perl, pittsburgh
Tags cool, perl, pittsburgh, ppw, ppw06, stuff, talks
1 comment
no trackbacks
Posted by Tom Moertel
Thu, 17 Aug 2006 06:21:00 GMT
As promised, here’s a Perl version of a dynamic-programming-based solver
for the Google Code Jam “countPaths” problem. It is a straight
translation of my improved Ruby implementation.
As you might expect, the Perl version was pretty fast. It proved faster than the
other scripting-language implementations I tried (in this rather unscientific benchmark, not to be taken seriously):
All timings were taken while solving the maximum-size, all-the-same-letter
problem on my 1.8-GHz Opteron box.
Here’s the Perl implementation:
#!/usr/bin/perl
# Tom Moertel <tom@moertel.com>
# 2006-08-16
#
# Perl-based solution to the Google Code Jam problem "countPaths".
# See http://www.cs.uic.edu/~hnagaraj/articles/code-jam/ for more.
use strict;
use warnings;
use List::Util 'sum';
use Math::BigInt;
sub count_paths {
my ($grid, $word) = @_;
my $rword = reverse $word;
my $rowmax = $#$grid;
my $colmax = length($grid->[0]);
my ($slab, $sum);
for my $i (0 .. length($rword) - 1) {
my $char = substr $rword, $i, 1;
($slab, my $previous_slab) = ([], $slab);
for my $r (0 .. $rowmax) {
my ($row, $line) = ($grid->[$r], $slab->[$r] ||= []);
for my $c (0 .. $colmax) {
$line->[$c] = $char ne substr($row,$c,1) ? 0 : $i == 0 ? 1 : do {
$sum = 0;
my $clo = $c > 0 ? $c - 1 : $c;
my $chi = $c < $colmax ? $c + 1 : $c;
for my $nr (($r>0 ? $r-1 : $r) .. ($r<$rowmax ? $r+1 : $r)) {
for my $nc ($clo .. $chi) {
$sum += $previous_slab->[$nr][$nc]
if $nr != $r || $nc != $c;
}
}
$sum;
}
}
}
}
sum map @$_, @$slab;
}
print count_paths([("A"x50)x50], "A"x50), $/;
# 3.03835410591851e+47
Update: I simplified the code a whisper by
removing an unnecessary variable
$counts. Here’s a diff
if you’re curious about what’s changed:
--- countpaths.pl.orig 2006-08-18 00:16:56.000000000 -0400
+++ /countpaths.pl 2006-08-18 00:19:30.000000000 -0400
@@ -19,11 +19,11 @@
my $rword = reverse $word;
my $rowmax = $#$grid;
my $colmax = length($grid->[0]);
- my ($counts, $slab, $sum);
+ my ($slab, $sum);
for my $i (0 .. length($rword) - 1) {
my $char = substr $rword, $i, 1;
- ($slab, my $previous_slab) = ($counts->[$i] ||= [], $slab);
+ ($slab, my $previous_slab) = ([], $slab);
for my $r (0 .. $rowmax) {
my ($row, $line) = ($grid->[$r], $slab->[$r] ||= []);
for my $c (0 .. $colmax) {
Update 2: Augmented the introductory paragraph with a parenthetical
comment that reminds readers that these single-fuzzy-data-point-style
timings should not be taken seriously. Also removed the word
“bested,” which might suggest that there is an optimization
contest in play. Please, no wagering.
Update 3: Stripped another variable ($j), which was
completely unused and leftover from previous implementation. (See
why you shouldn’t code late at night?)
Posted in programming, perl, fun stuff
Tags code, countpaths, google, jam, perl, puzzles, wordpaths
2 comments
no trackbacks
Posted by Tom Moertel
Tue, 27 Jun 2006 18:21:00 GMT
I have a bunch of LectroTest news. LectroTest, as you may know, is a specification-based,
automatic testing system for Perl. It may look like Haskell’s QuickCheck, but it tastes like sweet, sweet Perl.
LectroTest 0.3500 was released
This version adds automatic tools for recording and playing back
failures. Using them, you can automatically build regression-testing
suites and incorporate them into your testing plan. All it takes
is one new line of code:
use Test::LectroTest
regressions => "regressions.txt"; # <-- that's it!
See the docs on CPAN for more.
My thanks to Steffen Müller, who suggested the feature and is already
using it in cool stuff such as Number::WithError.
Slides from “Testing Tips with LectroTest” are now online
You can get the slides from my talk to the Pittsburgh Perl Mongers on
2006-06-14 here: Talk / Testing Tips with
LectroTest.
In the talk, I covered some of the newer LectroTest features, such as
regression testing and Test::LectroTest::Compat, which lets you mix
LectroTest with other Perl testing modules.
The LectroTest Emporium opens!
I have very little artistic ability. Nevertheless, alarming numbers
of people seem to love the fiercely metallic mascot I created for
LectroTest.
At the last Perl Mongers meeting, for example, people
actually told me (somewhat sternly) I should put the adorable LectroTest Robot on
t-shirts. I am now delighted to announce that I have taken their
advice:
Introducing: The LectroTest Emporium
Some important points:
- Yes, it’s a CafePress store
- I’m not making any money on these things
- I’m using direct printing, not heat-transfer printing, so
the Robot won’t crack, feel stiff, or suffer from a yellowish
transfer background. (CafePress has a comparison of the methods if you want the full details.)
Some items I have moral reservations about offering:
- LectroTest Robot Teddy Bear -
Who would be so reckless as to allow something as fierce and as powerful
as the LectroTest Robot to come into direct contact with a defenseless, cuddly
teddy bear?
- LectroTest Robot Baby Bib -
Actually, this is a great idea: your infant and the Robot
exist in a symbiotic relationship. When your baby gets food all over the
bib, the Robot will consume it (using a electrochemical process not
entirely dissimilar to our human concept of “digestion”). Thus is the
baby cleaned and the Robot fueled. It’s win-win.
- LectroTest Robot Dog T-Shirt -
I am fairly certain that the immense weight of the Robot would easily
crush any smaller animal. This product strikes me as a very bad idea.
The T-shirts, on the other hand, are the robot’s meow. Check out the
full collection at The LectroTest Emporium.
Posted in perl, fun stuff, testing, marketing, talks
Tags lectrotest, perl, testing
1 comment
no trackbacks
Posted by Tom Moertel
Tue, 14 Mar 2006 22:39:00 GMT
Last week I gave a brief talk for the Pittsburgh Perl
Mongers about embedding domain-specific languages
into Perl. The slides from the talk are now available:
Embedding an XHTML template language into Perl.
Posted in programming languages, perl, talks
Tags dsls, perl, pghpm, talks
no comments
no trackbacks
Posted by Tom Moertel
Wed, 01 Mar 2006 20:17:00 GMT
While we read, our minds subconsciously correct mistakes and overlook omissions in the steam of words we see, especially when reading familiar texts. This mental feature, which allows us to skim long documents, has a nasty drawback when we are writing: it makes it our own mistakes harder to spot.
One of the most common writing mistakes that our brains stealthily correct is the the duplicate word problem. For example, I inserted a double the into the previous sentence. Did you catch it?
If so, don’t be too proud of your accomplishment. It is easier to see errors in others’ writing than in your own. Your brain is attuned to your natural writing patterns and much more likely to repair your mistakes without your knowing.
To overcome this problem, some writers recommend reading your work backward, but I think computers are a more practical solution.
Here’s the Perl script that I use to spot duplicate words:
#!/usr/bin/perl -n00
# dupwords.pl - find duplicate words in the input stream
print "$ARGV: para $.: ($1)\n"
while /(\b(\w+)\b\s+\b\2\b)/sg;
I use this script from Emacs via shell-command-on-region. I also use it from the command line to find duplicate-word errors in batch:
find . -name '*.txt' | xargs dupwords.pl
The duplicate-words problem is a favorite for programming cookbooks, so if you don’t like my recipe (or Perl), you have many other options.
Posted in perl, writing
Tags perl, tools, writing
1 comment
no trackbacks
Posted by Tom Moertel
Tue, 01 Nov 2005 19:41:00 GMT
Over the weekend I attended Damian
Conway’s talk on Sufficiently Advanced
Technologies,
hosted by the Pittsburgh Perl Mongers and
presented at CMU.
Read more...
Posted in programming, perl
Tags conway, damian, perl, talks
no comments
no trackbacks
Posted by Tom Moertel
Tue, 08 Feb 2005 17:00:00 GMT
It seems that LectroTest is picking up in popularity because I am starting to get regular requests and feedback. Recently, two related requests came in regarding something that I had put off: Figuring out how to merge specification-based testing, which samples thousands of trials per property check, with case-based testing, which runs one trial per case.
The rub is that case-base testing in Perl is managed by Test::Builder and a related family of modules that are designed to make that kind of testing easy. One convenience they offer is that calling test functions like cmp_ok not only performs a test, in this case a general comparison, but also reports the result of the test to the test harness.
So what happens if somebody wants to perform a cmp_ok test from within a LectroTest property specification? When the property is checked, LectroTest will test whether the property holds by sampling a thousand random trials (by default), each of which will end up calling cmp_ok. Can you see where this is going? Yup, the test harness will end up seeing one thousand separate tests instead of the single test of the property.
The solution to this problem, as to all problems of distinction, is hackery. The Test::* family of modules ends up filtering all calls to test functions such as cmp_ok down to the Test::Builder module’s ok method. This method does two things. First, it reports the result of the test to the test harness without giving us a chance to say otherwise. (Naughty!) Second, it returns the result of the test back to the original caller. As far as property checks are concerned, the first part is bad, and the second is good.
To get rid of the bad part, I redefine the ok method during property checks. I put the implementation into a new module, Test::LectroTest::Compat, that exports a single function holds. This function is used to inject a property check into a plain-old Test::Simple- or Test::More-style test plan. For example, here’s a test plan that uses the new module:
use Test::More tests => 2;
use Test::LectroTest::Compat;
my $prop_nonnegative = Property {
##[ x <- Int, y <- Int ]##
cmp_ok(my_function( $x, $y ), '>=', 0);
}, name => "my_function output is non-negative" ;
holds( $prop_nonnegative ); # assert that the prop holds
cmp_ok( 0, '<', 1, "trivial 0<1 test" ); # a "normal" assertion
# ... and so on ...
What does holds do when called? It redefines Test::Builder’s ok method, runs the property-check trials, restores ok, and finally reports the property check’s result via the newly-restored ok. From there, Test::Builder takes over and does the magic necessary to incorporate the result into the test session’s TAP output.
The code that does all this is as follows:
sub holds {
my ($diag_store, $results) = check_property(@_);
my $success = $results->success;
(my $name = $results->summary) =~ s/^.*?- /property /;
$Test->ok($success, $name);
my $details = $results->details;
$details =~ s/^.*?\n//; # remove summary line
$details =~ s/^\# / /mg; # replace commenting w/ indent
$Test->diag(@$diag_store) if @$diag_store;
$Test->diag($details) if $details;
return $success;
}
sub check_property {
no strict 'refs';
no warnings;
my $diag_store = [];
my $property = shift;
local *Test::Builder::ok = \&disconnected_ok;
local *Test::Builder::diag = sub { shift; push @$diag_store, @_ };
return ( $diag_store,
Test::LectroTest::TestRunner->new(@_)->run($property) );
}
sub disconnected_ok { $_[1] ? 1 : 0 }
You can see that there is one extra bit of hackery going on. I also redefine Test::Builder’s diag method to capture any diagnostic output that may be emitted during the trials. Typically, this occurs only when a trial fails, and in that case the output is almost certainly worth passing back to the user in context. To ensure that the user sees it in context, I hold on to the captured output until the property check is complete and then roll it into the normal LectroTest diagnostic output. It looks great:
not ok 3 - property 'x is a natural number' falsified in 2 attempts
# Failed test (t/compat.t at line 32)
# '0'
# >
# '0'
# Counterexample:
# $x = 0;
In the first part you see the typical cmp_ok output that the assertion 0 > 0 failed. The second part is the LectroTest counterexample that shows at what part of the test space the assertion failed.
It takes some complicated footwork, but the resulting dance is beautiful. To see two markedly different testing systems – and in some ways markedly different testing philosophies – working in step with one another is gratifying. I suspect that most real-world testing problems can be solved better by a combination of the two approaches than by either alone. Thus I am especially happy about this integration.
After some more refinement, I am going to incorporate Test::LectroTest::Compat into the main distribution. For now, you can get a copy in the LectroTest/FAQs section of the Community Projects site.
Posted in perl, testing
Tags lectrotest, perl, testing
no comments
no trackbacks
Posted by Tom Moertel
Fri, 10 Sep 2004 16:00:00 GMT
Just a quick note to mention LectroTest, a Perl project I have been working on recently. It’s inspired by QuickCheck for the Haskell programming language. The motivation is that traditional unit testing requires programmers to spell out each and every case to test, which seems like an awful lot of work, much of which probably isn’t necessary. Even so, the payoff of unit testing is real, and we ought to do it. Thus the goal becomes to reduce the pain while keeping the gain.
Rather than working at the level of individual test cases, why not tell the computer about the shape of the “test space” and let the computer generate the cases automatically? That’s what LectroTest does. You declare properties and assert that they hold over a certain test space. LectroTest then generates random cases from within the space and tests your assertion for each. If LectroTest is able to “break” whatever you’re testing, it emits a counterexample that you can feed back into your code to debug the error. (Counterexamples also make for nice regression tests.)
If you write code in Perl and want another option for testing your code, give LectroTest a look.
Posted in programming, perl, testing
Tags lectrotest, perl, testing
no comments
no trackbacks
Posted by Tom Moertel
Wed, 11 Aug 2004 16:00:00 GMT
I have Sprint PCS Vision, which means that my cell phone provides a small web browser that I can use to surf the web while on the go. Sprint, in keeping with the fine tradition of phone-company weaselry, has provided its Vision customers with a home page that links to a number of crippled services in order to promote their “premium,” for-pay versions of the services.
For example, Sprint has partnered with The Weather Channel (TWC) for its Vision weather. If you want anything other than the most fundamental weather information, say a radar snapshot of your home’s geographical region, you must fork over $3.99 per month – that’s almost fifty bucks per year! – for the privilege.
Yeah, I’ll be doing that.
Am I supposed to be impressed by the ability to retrieve “detailed” weather information on my cell phone? O Corporate Masters, thank you for solving the Mobile Weather Problem! I hand you my tribute of $3.99 this month with delight, for the value of your technical prowess is beyond priceless. [Opens wallet.]
No, I think that the correct solution to the Mobile Weather Problem is for me to write a small Perl script, which, having just done it, I can say with confidence is a simple task. How hard is it to fetch the forecast and radar image from the National Weather Service and drop the results into an XHTML Basic page? Let’s see, it takes fewer than 150 lines of code, including the code to handle caching and downed NWS servers, focus the radar image on my home and scale it down to cell phone–screen size, and perform text-messaging style word abbreviation.
If I’m going to spend fifty bucks on weather-related purchases this year, it will not be on “premium” mobile-phone services. I would much rather use the money to buy a mighty fine umbrella.
P.S. If you’re curious, here’s my mobile-weather Perl script. It has a few specializations for my geographical region, but it should be easy to adapt to your needs.
Posted in perl, web development
Tags cgi, perl, weather, web
no comments
no trackbacks
