Showing posts with label hacking. Show all posts
Showing posts with label hacking. Show all posts

Monday, March 01, 2010

Perl: conditional use and scope

A reader asks

If I conditionally load a perl module, do those module variables get passed to the whole perl script.

if ( some_test ) {
  use "perlmodule_001";
}
else {
  use "perlmodule_002";
}
Are the elements of either perl module available outside the if statement?

The main program from the question has a syntax error:

syntax error at prog0 line 2, near "use "perlmodule_001""

Perl's documentation for use explains:

use Module

Imports some semantics into the current package from the named module, generally by aliasing certain subroutine or variable names into your package. It is exactly equivalent to

BEGIN { require Module; Module->import( LIST ); }
except that Module must be a bareword.

Note the bareword constraint at the end: the compiler doesn't like the double quotes around the argument to use. Our friend was likely thinking of the older require operator that does accept strings and arbitrary expressions in general.

Say we have two modules with alternative definitions of $Foo and $Bar:

package Perlmodule_001;

use Exporter 'import';
our @EXPORT = qw/ $Foo $Bar /;

our $Foo = "apple";
our $Bar = "orange";

1;

and

package Perlmodule_002;

use Exporter 'import';
our @EXPORT = qw/ $Foo $Bar /;

our $Foo = 42;
our $Bar = "w00t!";

1;

Note the use of Perlmodule_001, for example, rather than perlmodule_001: the perlmodlib documentation notes, “Perl informally reserves lowercase module names for 'pragma' modules like integer and strict.”

Consider the following simple driver:

#! /usr/bin/perl

use warnings;
use strict;

if (@ARGV && $ARGV[0] eq "two") {
  use Perlmodule_002;
}
else {
  use Perlmodule_001;
}

sub maybeUndef {
  defined $_[0] ? $_[0] : "<undefined>";
  # got 5.10?
  # $_[0] // "<undefined>";
}

print "Foo = ", maybeUndef($Foo),  "\n",
      "Bar = ", maybeUndef($Bar),  "\n";

It uses maybeUndef to explicitly show when a value is undefined and also to silence potential undefined-value warnings.

The program seems to run as intended

$ ./prog1
Foo = apple
Bar = orange

but the output is the same even when an argument of two is supplied on the command line!

$ ./prog1 two
Foo = apple
Bar = orange

The good news is that the imported variables are in scope for the rest of the program, as indicated in the above documentation for use (with emphasis added):

Imports some semantics into the current package from the named module …

To understand why we never see Perlmodule_002's $Foo and $Bar, note that use “is exactly equivalent to” require at BEGIN time, and the perlmod documentation explains exactly when that is (with added emphasis):

A BEGIN code block is executed as soon as possible, that is, the moment it is completely defined, even before the rest of the containing file (or string) is parsed.

So the compiler sees use Perlmodule_002 and processes it. Then it sees use Perlmodule_001 and processes it. When the compiler finishes digesting the rest of the code, it's time for the execution phase, when the @ARGV check finally takes place. As written, Perlmodule_001 will always win!

Because ordinary modules affect the current package, useing an ordinary module inside a conditional block is entirely misleading. I was careful to qualify the previous statement for ordinary modules because the effects of some pragmatic modules (e.g., strict and integer—note the lowercase names!) are limited tightly to the enclosing block only.

The fix is to process @ARGV at BEGIN time and conditionalize the module imports with the equivalent require and import:

#! /usr/bin/perl

use warnings;
use strict;

BEGIN {
  if (@ARGV && $ARGV[0] eq "two") {
    require Perlmodule_002;
    Perlmodule_002->import;
  }
  else {
    require Perlmodule_001;
    Perlmodule_001->import;
  }
}

sub maybeUndef {
  defined $_[0] ? $_[0] : "<undefined>";
  # got 5.10?
  # $_[0] // "<undefined>";
}

print "Foo  = ", maybeUndef($Foo),  "\n",
      "Bar  = ", maybeUndef($Bar),  "\n";

An alternative is protecting use with eval as in

BEGIN {
  if (@ARGV && $ARGV[0] eq "two") {
    eval "use Perlmodule_002";
  }
  # ...

so a particular use runs only when control reaches its eval but is ignored otherwise. This is a safe, sensible use of eval.

Either way, the program now does what we expect!

$ ./prog2
Foo  = apple
Bar  = orange
$ ./prog2 two
Foo  = 42
Bar  = w00t!

You might wonder why the code has to be inside a BEGIN block after the uses are conditionalized. If you have the strict pragma enabled—and you should!—it wants variables to be imported and declared before execution begins. Otherwise, compilation will fail because for all it knows, $Foo and $Bar in the main package were typos.

Saturday, September 19, 2009

Haskell craps

A Haskell neophyte at $WORK talked about writing a craps simulator as a learning exercise. The rules, limiting consideration to pass-line bets, are complex enough to make it an interesting kata. Designing a processor for the game's complex prop bets, on the other hand, might make a good interview discussion.

Front matter:

> module Craps ( games
>              , rolls
>              , runTests
>              , Game
>              , Roll
>              ) where

> import Data.List ((\\))
> import System.Random (randomRs,Random,RandomGen)
> import Test.QuickCheck (choose,forAll,oneof,sized,Arbitrary(..),Gen,Property)
> import Test.QuickCheck.Batch (defOpt,run,TestOptions(..))
> import qualified Test.QuickCheck.Batch as QC
Craps is played with two dice:
> data Roll = Roll Int Int
>   deriving (Show)
At the pass line, the bettor can win two ways and lose two ways. With no point, rolls of 7 or 11 win (“natural”), and rolls of 2, 3, or 12 lose (“craps”). Any other roll becomes the point, and the shooter continues until she rolls the point again (“pass” or “win”) or 7 (“seven out”).
> data Game = Natural Roll
>           | Pass [Roll]
>           | CrapOut Roll
>           | SevenOut [Roll]
>   deriving Show
To generate a lazy list of rolls, pass a random-number generator (created, for example, with newStdGen, and use as many as you need. The second case in the definition of go silences a partial-function warning (“Pattern match(es) are non-exhaustive” with ghc), viz. empty and singleton lists. We'll always have at least two elements because randomRs produces an infinite list of bounded random numbers.
> rolls :: RandomGen g => g -> [Roll]
> rolls g = go $ randomRs (1,6) g
>   where
>     go (a:b:xs) = Roll a b : go xs
>     go _ = undefined
Now that we have as many rolls as we want, let's separate them into games. For the trivial case, if you aren't rolling, you aren't playing:
> games :: [Roll] -> [Game]
> games [] = []
Before the shooter establishes a point, we watch for magic numbers:
> games (r:rs) | any (rolled r) [7,11]   = Natural r : games rs
> games (r:rs) | any (rolled r) [2,3,12] = CrapOut r : games rs
Otherwise, whatever the shooter rolled becomes the point. The game ends when the shooter rolls 7 or makes the point.
> games (pt:rs) = go rest : games rs'
>   where
This inner go is also partial. If the list of rolls is finite, every point must be resolved, either pass or seven out. Note that the roll that ends the round will be the first element of the snd of the pair we get from break, so we use pattern matching to grab it and tack it on the end of the round.
>     go xs@(final:_) = outcome $ reverse xs
>       where outcome | final `rolled` 7 = SevenOut
>                     | otherwise        = Pass
>     go _ = undefined
>     (ensuing,x:rs') = break (\r -> r `rolled` 7 || r `eq` pt) rs
>     rest = x : reverse (pt : ensuing)
rolled is a simple helper for testing whether the shooter rolled a particular number, e.g., r `rolled` 7 as seen above.
> rolled :: Roll -> Int -> Bool
> rolled r = (== total r)
Two rolls are equal if they have the same total (yes, Lispers, I should have spelled it equal):
> eq :: Roll -> Roll -> Bool
> a `eq` b = total a == total b

> total :: Roll -> Int
> total (Roll a b) = a + b
Everything below is for testing with classic QuickCheck. Earlier iterations used this Arbitrary instance, but now it's window dressing.
> instance Arbitrary Roll where
>   arbitrary = do a <- choose (1,6)
>                  b <- choose (1,6)
>                  return $ Roll a b
>   coarbitrary = undefined
vectorOf turns a generator's crank a few times. We'll use this to generate multiple non-point rolls, for example. Note the use of sequence to allow pseudo-random number generator state to update between rolls.
> vectorOf :: Int -> Gen a -> Gen [a]
> vectorOf n gs = sequence [ gs | _ <- [1..n] ]
After the come-out roll establishes a point, the difference between a win and a loss is whether the game's last roll is 7 or the point. If pass is true, we generate a winner, otherwise a loser.
> afterComeOut :: Bool -> Int -> Gen [Roll]
> afterComeOut pass n = do
>   n' <- choose (1,n)
>   pt <- oneof points
>   rs <- vectorOf n' (oneof $ noPoint pt)
>   let rollpt = mkRoll pt
>       final = if pass then rollpt else seven
>   return $ rollpt : rs ++ [final]
>   where
>     noPoint p = mayroll $ except [7,p]
>     points = map return $ except [2,3,7,11,12]
>     seven = Roll 3 4
>     except = ([2..12] \\)
Our testing strategy will be to generate games of all four types and then make sure they're correctly recognized. For example, the test for passes will use expect isPass ...
> expect :: (Game -> Bool) -> [Roll] -> Bool
> expect what = all what . games
mayroll creates a list of generators ultimately for use with oneof, e.g., mayroll [2,3,12] in the crap-out property.
> mayroll :: [Int] -> [Gen Roll]
> mayroll = map (return . mkRoll)
QuickCheck opens the throttle on the size of testcases with sized, and many connects to this hook.
> many :: [Gen Roll] -> Int -> Gen [Roll]
> many what n = do
>   n' <- choose (1,n)
>   vectorOf n' (oneof what)
mkRoll starts from a roll total and backs into the individual components. An obvious improvement would be adding choices other than 1 and 6.
> mkRoll :: Int -> Roll
> mkRoll t = Roll less (t - less)
>   where less | t <= 6    = 1
>              | otherwise = 6
Now we get to the properties that use QuickCheck's forAll to generate random test data of the appropriate class and check for the expected results.
> prop_crapOut :: Property
> prop_crapOut =
>   forAll allCraps $ expect isCrapOut
>   where isCrapOut (CrapOut _) = True
>         isCrapOut _ = False
>         allCraps = sized $ many craps
>         craps = mayroll [2,3,12]

> prop_natural :: Property
> prop_natural =
>   forAll allNats $ expect isNat
>   where isNat (Natural _) = True
>         isNat _ = False
>         allNats = sized $ many nats
>         nats = mayroll [7,11]

> prop_sevenOut :: Property
> prop_sevenOut =
>   forAll allSevenOuts $ expect is7Out
>   where is7Out (SevenOut _) = True
>         is7Out _ = False
>         allSevenOuts = sized $ afterComeOut False

> prop_pass :: Property
> prop_pass =
>   forAll allPasses $ expect isPass
>   where isPass (Pass _) = True
>         isPass _ = False
>         allPasses = sized $ afterComeOut True
Finally, a simple test driver so we don't have to check them one-by-one:
> runTests :: IO ()
> runTests = do
>   let opts = defOpt { no_of_tests = 200 }
>   QC.runTests "crap out"  opts [ run prop_crapOut ]
>   QC.runTests "natural"   opts [ run prop_natural ]
>   QC.runTests "seven out" opts [ run prop_sevenOut ]
>   QC.runTests "pass"      opts [ run prop_pass ]

Saturday, July 11, 2009

Just for you, Madeline

My five-year-old daughter is learning to read. I made flash cards for us to practice phonics and recognition, and I wrote this simple app to give her a way to practice on her own too. Thanks to the Wiktionary folks for the pronunciations.

Along with the buttons, you can advance by pressing Enter or Right-Arrow and hear the word with S or space bar.

The code is available on GitHub.

Saturday, June 27, 2009

Installing curl from hackage on Cygwin

On a Windows machine, I upgraded to ghc-6.10.3 and was in the process of building and installing libraries from hackageDB, Haskell's CPAN—hmm, or should that be Haskell's CTAN?

I had already upgraded cabal-install:

$ cabal --version
cabal-install version 0.6.2
using version 1.6.0.3 of the Cabal library
I was unsuccessful installing curl from a cmd.exe prompt:
c:\>cabal install curl
Resolving dependencies...
Configuring curl-1.3.5...
cabal: Error: some packages failed to install:
curl-1.3.5 failed during the configure step. The exception was:
sh: runGenProcess: does not exist (No such file or directory)
Fair enough: installing curl requires a real shell, so let's try from inside Cygwin:
$ cabal install curl
Resolving dependencies...
Configuring curl-1.3.5...
checking for gcc... /cygdrive/c/ghc/ghc-6.10.3/gcc
checking for C compiler default output file name... a.exe
checking whether the C compiler works... yes
checking whether we are cross compiling... no
checking for suffix of executables... .exe
checking for suffix of object files... o
checking whether we are using the GNU C compiler... yes
checking whether /cygdrive/c/ghc/ghc-6.10.3/gcc accepts -g... no
checking for /cygdrive/c/ghc/ghc-6.10.3/gcc option to accept ANSI C... none needed
checking how to run the C preprocessor... /cygdrive/c/ghc/ghc-6.10.3/gcc -Bc:/ghc/ghc-6.10.3/gcc-lib -Ic:/ghc/ghc-6.10.3/include/mingw -E
configure: error: curl libraries not found, so curl package cannot be built
See `config.log' for more details.
cabal.exe: Error: some packages failed to install:
curl-1.3.5 failed during the configure step. The exception was:
exit: ExitFailure 1
I already installed Cygwin's curl-devel package, so maybe I needed to help the linker along (note the DOS-ish paths because the mingw gcc bundled with ghc doesn't know about Cygwin):
$ cabal configure \
        --extra-include-dirs=c:/cygwin/usr/include \
        --extra-lib-dirs=c:/cygwin/usr/lib
Same failure as above.

Maybe if I build the package by hand:

$ cd /tmp

$ cabal fetch curl
Resolving dependencies...
No packages need to be fetched. All the requested packages are already cached.

$ cabal unpack curl
Unpacking curl-1.3.5...

$ cd curl-1.3.5/

$ cabal configure --extra-lib-dirs=c:/cygwin/usr/lib --extra-include-dirs=c:/cygwin/usr/include
Resolving dependencies...
Configuring curl-1.3.5...
checking for gcc... gcc
checking for C compiler default output file name... a.exe
checking whether the C compiler works... yes
checking whether we are cross compiling... no
checking for suffix of executables... .exe
checking for suffix of object files... o
checking whether we are using the GNU C compiler... yes
checking whether gcc accepts -g... yes
checking for gcc option to accept ANSI C... none needed
checking how to run the C preprocessor... gcc -E
configure: creating ./config.status
config.status: creating curl.buildinfo
cabal.exe: Missing dependency on a foreign library:
* Missing C library: curl
This problem can usually be solved by installing the system package that
provides this library (you may need the "-dev" version). If the library is
already installed but in a non-standard location then you can use the flags
--extra-include-dirs= and --extra-lib-dirs= to specify where it is.
No dice.

I tried fiddling with the environment (CC, CFLAGS, LD, and LDFLAGS) and running ./configure by hand, but that produced only frustration.

"If you can't beat 'em, join 'em," I said, and

$ cp /usr/lib/libcurl.a /cygdrive/c/ghc/ghc-6.10.3/gcc-lib/

$ cabal install curl --extra-include-dirs=c:/cygwin/usr/include
[...]
/usr/bin/ar: creating dist\build\libHScurl-1.3.5.a
Installing library in C:\Program Files\Haskell\curl-1.3.5\ghc-6.10.3
Registering curl-1.3.5...
Reading package info from "dist\\installed-pkg-config" ... done.
Writing new package config file... done.
Success!

Thursday, June 25, 2009

Find GPS Info

A coworker asked if I knew of a way to convert batches of hundreds of street addresses to lat/lons. The Geo::Google module on CPAN looked promising at first, but it seems to have fallen into disrepair. A solution was straightforward with the Google Maps API.

Give it a spin! Enter street addresses in the top textarea (one per line), click Search, and you should get a CSV-ish output on the bottom.

Tuesday, June 23, 2009

Setting up a simple test with Cabal

With the Cabal build and packaging system for Haskell, add a simple test program to your build with a couple of easy steps.

First, add the following to your project's cabal file:

Build-Type: Custom

...

flag test
  description: Build test program.
  default:     False

Executable test
  hs-source-dirs:  src, test
  other-modules:   MyModule1, MyModule2
  main-is:         Main.hs
  build-depends:   base
  if !flag(test)
    buildable:     False
When enabled (via cabal configure -ftest but otherwise off), this builds an extra program called test.

The custom build type gives you more flexibility in your setup script, so add code such as the following to Setup.hs:

main = defaultMainWithHooks hooks
  where hooks = simpleUserHooks { runTests = runTests' }

runTests' :: Args -> Bool -> PackageDescription -> LocalBuildInfo -> IO ()
runTests' _ _ _ lbi = system testprog >> return ()
  where testprog = (buildDir lbi) </> "test" </> "test"
When you run cabal test, it will kick off your test program whose source is in test/Main.hs.

This approach has a few drawbacks. Users must explicitly enable the test builds. Building the test program entails rebuilding the other libraries in your package. Installing from a -ftest configuration will also install your test program.

Monday, June 15, 2009

FFI: C function taking pointer to array

Say you want to call the following C function from Haskell: The parameter tarray is a pointer to an array of floats. From C, you'd use it along the following lines:
    float times[2];
    etime_(times);
    printf("user time=%f, system time=%f\n", times[0], times[1]);
But in the Haskell world, even though such destructive updates are anathema, we can still talk back and forth.

First, we enable the Foreign Function Interface language pragma:

> {-# LANGUAGE ForeignFunctionInterface #-}
Then some front matter:
> module Main where
> import Foreign (Ptr)
> import Foreign.Marshal.Array (allocaArray,peekArray)
> import Control.Monad (mapM_)
We let Haskell know about the C function we want to call with an import declaration:
> foreign import ccall etime_ :: Ptr Float -> IO Float
To prepare for the call to the C function, allocaArray creates a new buffer and passes a handle to it (ta in the example below) to an action that calls etime_, pulls the data with peekArray, and returns these values along with the value returned from etime_ in a tuple:
> etime :: IO (Float, Float, Float)
> etime = do
>   allocaArray 2 $ \ta -> do
>     t <- etime_ ta
>     [user,sys] <- peekArray 2 ta
>     return (t,user,sys)
Use the etime action as in the following example:
> main :: IO ()
> main = do
>   (t,user,sys) <- etime
>   putStrLn $ "user time:    " ++ show user
>   putStrLn $ "system time:  " ++ show sys
>   putStrLn $ "process time: " ++ show t

Sunday, June 07, 2009

GWT not hitting breakpoints in hosted mode

With Eclipse 3.4.2 (Ganymede), Google Web Toolkit, and JDK 1.6.0_14, the debugger seemed to ignore my breakpoints while running the hosted-mode browser even though the breakpoint indicators had checkmarks while the app was running. I added calls to GWT.log, and the server's log output demonstrated that control was definitely passing through my breakpoints.

Google's Rajeev Dayal confirms the problem, and Eclipse has a ticket associated with this issue.

One workaround is falling back to JDK 1.6.0_13. If you don't have it yet, download it from Sun, and tell Eclipse about it:

  1. In Eclipse select Window > Preferences.
  2. In the Preferences dialog, select Java > Installed JREs.
  3. In the Installed JREs panel, select the Add... button.
  4. In the Add JRE dialog, select Standard VM and then the Next button.
  5. Select the Directory... button next to the textbox labeled JRE home and navigate to the JRE bundled with JDK 1.6.0_13 (e.g., C:\Program Files\Java\jdk1.6.0_13\jre). This should add several JARs to the list of JRE system libraries.
  6. Select the Finish button.
  7. Back in the Installed JREs panel, check the JRE for update 13, and then click
Set breakpoints, launch the debugger, and your application should now be stopping when control reaches the specified lines of code!

UPDATE: early-access release 6u18 is reported to fix this problem.

Saturday, June 06, 2009

Quidquid latine dictum sit, altum videtur

Sally suggested the title quote has a dynamic equivalent in C “and could be even more obfuscated!”

What do you think?

#include <stdio.h>
char s[]=" iptanohs iosonwa' nltnsud \
rfud";int i=sizeof s;void p(int n){n<i
?p((n<<1)+1),putchar(*(s+n)),p((n+1)
<<1):3;}int main(){p(0);putchar('\n');}

Loading object files into ghci

On Haskell-Cafe, Murray asked about loading objects associated with FFI imports in ghci.

FFI is Haskell's Foreign Function Interface and allows interoperability with other languages, e.g., calling into a C library from Haskell or using your Haskell module from a C program. For more examples, see the FFI cookbook.

GHC's interactive environment, invoked with ghci, evaluates Haskell code in a REPL, loads and runs compiled modules, and provides familiar debugger functionality such as stepping, tracing, and catching exceptions.

Consider the following simple Haskell program that comprises two modules: Even though our program is split into multiple modules, we need point ghci at the main module, and it will follow the other dependencies:

$ ghci hello.hs 
GHCi, version 6.10.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
[1 of 2] Compiling Message          ( Message.hs, interpreted )
[2 of 2] Compiling Main             ( hello.hs, interpreted )
Ok, modules loaded: Main, Message.
*Main> main
Hello, world!
(If you're invoking ghci from Cygwin, you'll want to use ghcii.sh.)

With FFI, you have to hold ghci's hand a little. Consider the following shell script: The environment variable PREFIX is the path to the parent of the lib directory where your library lives. In my case, I ran ./configure --prefix=$PREFIX to ultimately install mylib in a non-standard location.

We might look for a directory named dist if building with Cabal.

The FFI gateway between my Haskell code and my C library is in a file named mylib.hs and compiles to mylib.o, whose path ghci needs to know in order to load all dependencies.

Finally, we invoke ghci. This particular program used hxt, the Haskell XML Toolbox, and mylib links against HDF5, the expat XML parser, and the single-precision FFTW.

For projects built with Cabal, the build system already knows all this information. With cabal-install, it's already possible to configure, build, test, and install Haskell packages. It'd be sweet to be able to easily load complex packages in ghci instead of having to resort to such hackery!

Friday, June 05, 2009

Waiting for Go-done

A coworker called this morning wanting to know how to get a list of files that do not contain the text 'Program complete' on any line. They run jobs in big batches, and each process writes its output to a separate file. The running times vary, and they wanted an easy way to see at a glance which processes are still running.

Running grep -v will print all lines that don't match the given pattern, but that doesn't help in this case because we want to treat the output files as though each contained a single line.

With the -c option, grep outputs the number of lines that matched. Say we have outputs named output1 through output4, and the odd-numbered jobs are finished. This would give us

$ grep -c 'Program complete' output*
output1:1
output2:0
output3:1
output4:0
The pattern requires quotes because it contains a space. Without the quotes, grep would search for Program in files named complete, output1, and so on.

The outputs for the processes still running are the ones containing zero matches, so let's look for those:

$ grep -c 'Program complete' output* | grep ':0$'
output2:0
output4:0
Remember that a dollar sign in a regular expression anchors the match to the end.

Quick cleanup with sed gives us the names of the outputs (backslash is the shell's line-continuation marker that lets us split long lines):

$ grep -c 'Program complete' output* | \
  grep ':0$' | \
  sed -e 's/:0$//'
output2
output4

UPDATE: Turns out there's a much easier way to do it. GNU grep has a --files-without-match option (aka -L), so the command is the simple

$ grep -L 'Program complete' output*
output2
output4

Tuesday, April 14, 2009

Thinking functionally

Carey's been learning functional programming with F#, and as a learning exercise he solved in F# Project Euler's Problem 1.

Consider the meat of a solution in Haskell (with which we'd get the answer via sum $ multiples 1000 [3,5]): Data.List's union function computes the union of two lists, e.g.,

Prelude Data.List> union [1..3] [3..6]
[1,2,3,4,5,6]
The types of expressions convey a lot about what they do, so let's pick apart the above definition:
*Main Data.List> :t foldl union []
foldl union [] :: (Eq a) => [[a]] -> [a]
*Main Data.List> foldl union [] [[1..3],[3..6]]
[1,2,3,4,5,6]
*Main Data.List> foldl union [] [[1..3],[3..6],[1..7]]
[1,2,3,4,5,6,7]
So the fold allows us to compute the union of an arbitrary number of lists. If this still seems puzzling, remember that the sum of a list of numbers is foldl (+) 0. Take a look at the graphic representation of fold to help your intuition.

The dot is function composition—chosen for its similar appearance to ∘ as used in many math texts, e.g., (fg)(x). Recall from algebra class that you understand composed functions by reading "inside-out."

So we know we're computing a union of lists, and from the problem statement, we want products of 3 and 5. So the rest must be generating those products.

Its name makes takeWhile's value obvious, but consider an example:

Prelude Data.List> takeWhile (<4) [1..10]
[1,2,3]
So that's capping the products at whatever the value of max is, but what about the goofiness inside?
*Main Data.List> :t flip (map . (*)) [1..]
flip (map . (*)) [1..] :: (Num a, Enum a) => a -> [a]
Although it may not be obvious yet, this is generating all multiples of a given n.

With flip, we reverse the operands of a binary function:

*Main Data.List> :t flip
flip :: (a -> b -> c) -> b -> a -> c
But what are we flipping?
*Main Data.List> :t map . (*)
map . (*) :: (Num a) => a -> [a] -> [a]
Point-free style looks unintelligible coming from an imperative background, but you'll see it all over in Haskell code. Someone once quipped that Haskell is to manipulating functions as Perl is to manipulating strings. We might equivalently write the above function as
*Main Data.List> :t \n xs -> map (n*) xs
\n xs -> map (n*) xs :: (Num a) => a -> [a] -> [a]
Note that backslash is lambda, i.e., the function above takes two arguments with its value being xs scaled by n.

This particular definition has issues. We have to build in the upper-bounding machinery because the function isn't lazy. Consider:

*Main Data.List> take 10 $ multiples 1000 [3,5]
[3,6,9,12,15,18,21,24,27,30]
Notice the absence of multiples of 5. They don't come until much later:
*Main Data.List> elemIndex 10 $ multiples 1000 [3,5]
Just 334
Also, union is overkill because we can make use of our knowledge that the multiples will emerge in increasing order: Notice that we no longer have to force an upper bound, and the merged result is nicer:
*Main> take 10 $ multiples [3,5]
[3,5,6,9,10,12,15,18,20,21]

Friday, April 10, 2009

Vanity search

At work, we're evaluating Safari Books Online. I knew they offered more than only O'Reilly titles, so I hoped to find Scott Chacon's Git Internals. No dice.

Maybe in need of a pick-me-up after such a harsh letdown, I searched for my own name. In the results were books that I tech-edited (Perl Developer's Dictionary and SAMS Teach Yourself Perl in 24 Hours), O'Reilly books that have my work, and a few where I'm mentioned in the acknowledgements—Real World Haskell being of recent note.

I was surprised to see a hit in Perl Debugged by Peter Scott and Ed Wright. In Section 3.5, the authors gave a list of people whose code readers ought to emulate, e.g., Larry Wall, Gisle Aas (author of LWP), Tom Christiansen, Nat Torkington, Mark Jason Dominus (author of Higher-Order Perl), Chip Salzenberg, Gurusamy Sarathy, and—both last and least—your humble host!

Saturday, March 21, 2009

Digest tag population

In comp.lang.lisp, Ken Tilton relayed a fun exercise involving a two-tiered list of pet populations, selections, and an unusual sort order. He proposed it as a test of language mastery because of his requirement to write "in one go" a single-function solution.

This style of development would be highly unusual with Lisp. Having the whole language available at an interactive read-eval-print loop promotes an incremental, bottom-up approach. As Paul Graham explains, bottom-up design in Lisp is more than building up a library: experienced programmers modify the language itself to make expressing the problem more straightforward.

I wrote a solution in Haskell: Aspects need improvement. The name of the type-synonym PetTags is plural, which is often better expressed as a list type, e.g., [PetTag]. The sort comparison functions (used on lines 39 and 40) are inconsistent in expression. The definition feels clunky and verbose.

In comp.lang.haskell, Florian Kreidler made my code much more elegant:

A more natural Haskell development style would be writing a function, checking it for correctness, and repeating in tiny increments. In the code below, I first wrote flatten, then I wrote select to extract the desired animals, followed by largest to extract the top n by population, and finally I wove them together to create digestTagPopulation.

(Github has a feature request for embedding particular revisions of gists. That would have come in handy in this post.)

Wednesday, February 18, 2009

Scraping data from a program's output

Consider a (truncated) output from vmstat on AIX:
  2031616 memory pages
  1953185 lruable pages
   935166 free pages
        1 memory pools
   170943 pinned pages
     80.0 maxpin percentage
  ...
Say you want to grab the values for memory pages and free pages. Below, I explain a couple of ways to do it.
#! /usr/bin/perl

use warnings;
use strict;

no warnings "exec";

open my $fh, "vmstat -v |"
  or die "$0: can't execute vmstat: $!\n";

my %vmstat;

while () {
  chomp;
  my($n,$desc) = split " ", $_, 2;

  $vmstat{$desc} = $n;
}

print "Memory pages: $vmstat{'memory pages'}\n",
      "Free pages:   $vmstat{'free pages'}\n";
When the filename argument to open ends with a pipe, Perl runs the named command and makes its output available on the returned filehandle. I turn off the autogenerated error (no warnings "exec") because I like my format better.

Looking at vmstat's output, each line has a value and a description, so the plan is to read each line and stash the parameters where we can find them later. A hash is a perfect data structure for this task.

Most of the time, the pattern to the split operator is a regular expression, but with no arguments (or a pattern of a lone space) it acts like awk, throwing away leading whitespace. Because the descriptions contain spaces, we don't want to split on them and tell Perl to give us back exactly two fields. Because we've limited the number of splits, we have to remove the trailing newline with chomp.

The output is straightforward: print the desired values.

You can of course be more clever:

#! /usr/bin/perl

%vmstat = reverse `vmstat -v` =~ /(\S+) (.+)/g;

print "Memory pages: $vmstat{'memory pages'}\n",
      "Free pages:   $vmstat{'free pages'}\n";
Instead of a piped open, this time we use backticks (``) to capture vmstat's output and from the output extract the values and descriptions.

The regular expression \S+ means a sequence of one or more non-whitespace characters, and this matches the numbers in the output. You might be tempted to use \d+ (one or more digits), but this will give you surprising results on the floating-point numbers.

By default, dot does not match newline, so the (.+) subpattern matches through the rest of the current line — the description in this case.

The /g regular-expression switch means we get all possible non-overlapping matches.

The list returned from the match will look like (2031616, "memory pages", 1953185, "lruable pages", ...), but that's the opposite order from hash initialization, i.e., key then value. The reverse operator fixes this problem.

Friday, February 13, 2009

25 random songs

Bo hit me with the 25 random songs meme. Who wants to push buttons when you can write a program?
#! /usr/bin/perl

use warnings;
use strict;

use File::Find;

use constant CHOOSE_N => 25;

@ARGV = "." unless @ARGV;

my @mp3;
my $matches = sub {
  push @mp3 => $File::Find::name
    if /\.mp3$/i;
};

find $matches => @ARGV;

# Fisher-Yates-Knuth
for (my $n = $#mp3; $n >= 1; $n--) {
  my $k = int rand($n+1);
  @mp3[$k,$n] = @mp3[$n,$k];
}

for (1 .. CHOOSE_N) {
  last unless @mp3;
  my $song = shift @mp3;

  # e.g., .../Music/Bob Marley/Kaya/08 - Crisis.mp3
  if ($song =~ m!^.*/([^/]+)/[^/]+/\d+\s+-\s+(.+)\.!) {
    my($artist,$title) = ($1,$2);
    print qq{$_. "$title," $artist\n};
  }
}

The output:
  1. "The End," The Doors
  2. "Misty Morning," Bob Marley
  3. "My Mood Swings," Elvis Costello
  4. "Concerto Emperor: II. Adagio un poco moto," Ludwig van Beethoven
  5. "What's the Matter Here?," 10,000 Maniacs
  6. "Trench Town Rock," Bob Marley
  7. "Final Hour," Lauryn Hill
  8. "These Are Days," 10,000 Maniacs
  9. "Want-Ad Blues," John Lee Hooker
  10. "Loser," Beck
  11. "Sonata Pathétique: II. Adagio cantabile" Ludwig van Beethoven
  12. "Peer Gynt Suite No. 2: Ingrid's Lament," Edvard Grieg
  13. "4 Better or 4 Worse (interlude)," The Pharcyde
  14. "Bonita Applebum," A Tribe Called Quest
  15. "Hard Hearted Woman," John Lee Hooker
  16. "Jeremy," Pearl Jam
  17. "Toccata and Fugue in D minor," Johann Sebastian Bach
  18. "Ya Mama," The Pharcyde
  19. "Pennyroyal Tea," Nirvana
  20. "Concerto in C minor for Violin and Oboe," Johann Sebastian Bach
  21. "Sex Type Thing," Stone Temple Pilots
  22. "Drive," R.E.M.
  23. "People Are Strange," The Doors
  24. "Vivrant Thing - Violator (feat. Q-Tip)," A Tribe Called Quest
  25. "The New Pollution," Beck

Thursday, January 15, 2009

They see me rollin': a probability problem

Say you're playing 7-card stud and are dealt rolled-up deuces. If you see the case deuce as someone else's door, what is the probability that you'll bring it in?

In stud high games, the player with the lowest upcard is the bring-in. Suits break ties, with different places using different orders, so let's use bridge order, i.e., clubs, diamonds, hearts, and spades. Deuce of clubs always pays the bring-in.

The search space is small enough to use brute force. Front matter first:

> import Control.Monad
> import qualified System.IO.UTF8 as UTF8
> import Text.Printf
Modeling suits is straightforward:
> data Suit = C | D | H | S deriving (Show, Ord, Eq, Enum)
Haskell's deriving clause saves tedious definitions. For example, making Suit an instance of the Ord typeclass means that clubs are less than diamonds and so on.

We walk through all possibilities and report the probability:

> main = do
>   mapM_ display doors
>   putStrLn $ printf "Hero bringin probability: %.3f%%"
>                     (100.0 * k / n :: Float)

Simulate the deal. Automatically deriving an instance of the Enum typeclass allows us to use shorthand for all suits. From the problem statement, we know our hero will see two deuces, and the others are in the hole. Enumerating all possibilities is trivial with a list comprehension.

>   where doors = deal [C .. S]
>         deal xs = [ (h,v) | h <- xs, v <- xs, h /= v ]

Here we apply the definition of probability: the ratio of the number of times an event occurs with the total number of events:

>         hero  = [1.0 | (h,v) <- doors, h < v ]
>         (k,n) = (sum hero, fromIntegral $ length doors)

Given a pair of hero and villain door cards, pretty-print it to the standard output:

> display (h,v) = UTF8.putStrLn bringin
>   where hv = "Hero: " ++ (suit h) ++ ", Villain: " ++ (suit v)
>         bringin | h < v     = hv ++ " *"
>                 | otherwise = hv
>         suit C = "♣"
>         suit D = "♦"
>         suit H = "♥"
>         suit S = "♠"

Output:

Hero: ♣, Villain: ♦ *
Hero: ♣, Villain: ♥ *
Hero: ♣, Villain: ♠ *
Hero: ♦, Villain: ♣
Hero: ♦, Villain: ♥ *
Hero: ♦, Villain: ♠ *
Hero: ♥, Villain: ♣
Hero: ♥, Villain: ♦
Hero: ♥, Villain: ♠ *
Hero: ♠, Villain: ♣
Hero: ♠, Villain: ♦
Hero: ♠, Villain: ♥
Hero bringin probability: 50.000%

Friday, October 31, 2008

Accountability, one element at a time

At the end of September and beginning of October, the U.S. House of Representatives voted on a proposed bailo"rescue" plan for poorly managed Wall Street firms. HR 3997 was the first vote, and it failed so back to the drawing board! In the words of Rep. Ron Paul of Texas, "It’s amazing, you take a very, very bad bill, appropriating $700 billion, you can’t get enough votes to pass it so you take it back out, you make it much worse and take it up to over $800 billion." The "much worse" version was the one that passed, so the obvious question is which of our public servants made this possible? This post is a literate Haskell program: copy-and-paste it into a file with the extension "lhs" (say, turncoats.lhs) to get a working program! First, a bit of front matter to import libraries that we'll be using.
> {-# LANGUAGE Arrows #-}

> module Main where
> import Control.Monad
> import Data.List (groupBy, intercalate, sort)
> import qualified Data.Map as M
> import System.Environment
> import Text.XML.HXT.Arrow
The House makes available on the web results of recorded votes:
> hr3997 = "http://clerk.house.gov/evs/2008/roll674.xml"
> hr1424 = "http://clerk.house.gov/evs/2008/roll681.xml"
Despite the way they look in your browser, the resources linked above are XML document instances — verify for yourself with View Source — that we can use for a little accountability. The agenda for our program is straightforward: pull the results of the votes, extract the votes from each, and output the flip-floppers. As a bit of lagniappe, we group the principled stalwarts into classes according to how they changed their votes.
> main :: IO ()
> main = do
>   a <- runX $ readDoc hr3997 >>> votes
>   b <- runX $ readDoc hr1424 >>> votes
>   let turncoats = flipFlops a b
>   forM_ (groupBy same (sort turncoats)) $
>     \ xs -> do
>       let (v,v',_) = head xs
>           n = show $ length xs
>       putStrLn $ v ++ " -> " ++ v' ++ ": (" ++ n ++ ")  "
>       putStrLn $ intercalate ", " (map name xs)
>       putStrLn ""
>   where
>     a `same` b = before a == before b && after a == after b
>     before (v,_,_) = v
>     after  (_,v,_) = v
>     name   (_,_,n) = n
>     readDoc = readDocument [(a_tagsoup, "1")]
We'll represent each vote by pairing a representative's name with his yea-or-nay:
> type Name = String
> type Vote = (Name, String)
For a baseline, we use HR 3997 to build a hash table whose keys are representative names and whose values are the corresponding votes. Then for each vote from HR 1424, we compare the latter vote against the former, making note of those members who changed their votes. As the type of flipFlops indicates, the result is a list of tuples of the form (former-vote, latter-vote, rep-name).
> flipFlops :: [Vote] -> [Vote] -> [(String, String, Name)]
> flipFlops before after =
>   let prev = M.fromList before
>   in after >>= ff prev
>   where
In cases where a member did not vote on the earlier issue, lookup produces an error value, which is Nothing inside the Maybe monad. In Haskell, we don't get NullPointerExceptions. The astute reader will note that flipFlops is not fully general: it doesn't report cases where representatives voted on the former question but not the latter.
>     ff prev (name, latter) =
>       case M.lookup name prev of
>         Just former -> if former == latter
>                          then []
>                          else [(former,   latter, name)]
>         _           ->        [("<none>", latter, name)]
These are the bits that worry about slogging through the XML, but XPath makes it straightforward: the expression below says we want all recorded-vote elements, and those are children of the vote-data element, which are children of the rollcall-vote element at the document root.
> votes :: ArrowXml a => a XmlTree Vote
> votes = getXPathTrees "/rollcall-vote/vote-data/recorded-vote" >>>
>   proc rv -> do
>     name <- getName -< rv
>     vote <- getVote -< rv
>     returnA -< (name, normalize vote)
Consider the structure of a recorded-vote element:
<recorded-vote>
    <legislator>Cramer</legislator>
    <vote>Aye</vote>
</recorded-vote>
So for each recorded-vote, we extract the inner-text of the legislator and vote child elements.
>   where
>     getName = getChildren >>>
>               isElem >>> hasName "legislator" >>>
>               xshow getChildren
>     getVote = getChildren >>>
>               isElem >>> hasName "vote" >>>
>               xshow getChildren
Due to supremely lovely irony, yea is not yea nor nay nay in the recorded votes, so we have to normalize.
>     normalize "Yea" = "Y"
>     normalize "Yes" = "Y"
>     normalize "Aye" = "Y"
>     normalize "Nay" = "N"
>     normalize "No"  = "N"
>     normalize v     = v

Finally the output:

N → Y: (58)
Abercrombie, Alexander, Baca, Barrett (SC), Berkley, Biggert, Boustany, Braley (IA), Buchanan, Carson, Cleaver, Coble, Conaway, Cuellar, Cummings, Dent, Edwards (MD), Fallin, Frelinghuysen, Gerlach, Giffords, Green, Al, Hirono, Hoekstra, Jackson (IL), Jackson-Lee (TX), Kilpatrick, Knollenberg, Kuhl (NY), Lee, Lewis (GA), Mitchell, Myrick, Ortiz, Pascrell, Pastor, Ramstad, Ros-Lehtinen, Rush, Schiff, Schmidt, Scott (GA), Shadegg, Shuster, Solis, Sullivan, Sutton, Terry, Thompson (CA), Thornberry, Tiberi, Tierney, Wamp, Watson, Welch (VT), Woolsey, Wu, Yarmuth

Not Voting → Y: (1)
Weller

Y → N: (1)
McDermott

Saturday, August 18, 2007

Word ladder in Haskell

Another followup to my earlier post about searching for word ladders, this time using Haskell!

This blog post is a Haskell program, written using the "literate comment" convention.

First a bit of front matter. This implementation of the word-ladder search will use the State and list monads.


> module Main where
> import Control.Monad.State
> import Data.Char
> import Data.List (find)
> import Data.Set (Set, member, difference)
> import qualified Data.Set as Set
> import System.Environment (getArgs)
> import System.Exit

The idea is simple: read the dictionary, search for the desired ladder, and show it to the user:


> main :: IO ()
> main = do
>   (start, goal, dict) <- getArgs >>= parse
>   fullDictionary <- readDictionary dict
>   print $ search start goal (trim fullDictionary start)

Remember that getArgs is an action that returns the list of command-line arguments. We bind this action to the following:


>   where parse [start,goal,dict] = return (start,goal,dict)
>         parse [start,goal]      = return (start,goal,"/usr/dict/words")
>         parse _ =
>           putStrLn "Usage: ladder start goal [ dictionary ]" >>
>           exitWith (ExitFailure 1)

Haskell's pattern matching shows that the program takes two or three arguments. The first two are the start and goal words. The optional third argument is the path to a dictionary (one word per line) to use.

We condition the dictionary by eliminating words whose lengths differ from the length of the start word and also converting everything to lowercase.


>         trim :: [String] -> String -> [String]
>         trim words start = filter (sameLength start) (lc words)
>
>         sameLength start = (== length start) . length
>
>         lc = map (map toLower)

The search can fail, so result is of type Maybe [String]. Handling both cases is straightforward:


>         print Nothing = putStrLn "No ladder found."
>         print (Just a) = mapM_ putStrLn a

The dictionary's format is simple, so reading it is a matter of extracting the lines from the file:


> readDictionary :: FilePath -> IO [String]
> readDictionary path = liftM lines $ readFile path

Now for the fun bits. Imagine a graph where nodes are words from the dictionary and where edges are between words that are "one hop' from each other, i.e., words that could be on consecutive "rungs" of a ladder.

Beginning with the start word, the program performs a breadth-first search of this graph. We call the set of words reached in the most recent iteration the "fringe." When the fringe contains the goal word, we're done.

The state monad simulates destructive update in imperative programming languages. (Haskell is purely functional.) Without it, we'd have to explicitly thread the state value through the call chain, but with it, we retrieve and update the state value with get and put as below:


> search start goal words =
>   evalState (loop [[start]]) (Set.fromList $ filter (/=start) words)
>   where
>     loop :: [[String]] -> State (Set String) (Maybe [String])
>     loop [] = return Nothing
>     loop paths = do
>       next <- step paths
>       let newFringe = fringe next
>       words <- get
>       put $ words `difference` newFringe
>       if goal `member` newFringe
>         then return $ Just (winner next)
>         else loop next

The list monad is handy for representing nondeterministic computations. In concept at least, the search carries around a list of lists that has all of the partial results computed so far.

For example, if the start word is dog, the state value on the second iteration might be [["dog", "dig"], ["dog", "fog"], ["dog", "bog"]]. This approach might seems to be a memory pig, but it remains surprisingly frugal.

To proceed to the next iteration of the search, for each partial result (one ladder beginning with the start word) we find the as-yet unseen neighbors of its last element (a member of the current fringe) and replace the current partial result with new ones for each of the neighbors. Again, consider the partial results at the second iteration in the previous paragraph.


>     step :: [[String]] -> State (Set String) [[String]]
>     step paths = do
>       words <- get
>       return $ paths >>= augment words
>
>     augment :: Set String -> [String] -> [[String]]
>     augment words path = [ path ++ [n] | n <- ns ]
>       where ns = Set.elems $ neighbors (last path) words
>     
>     neighbors :: String -> Set String -> Set String
>     neighbors word words = Set.filter (oneHop word) words
>       where oneHop [] [] = False
>             oneHop (x:xs) (y:ys) | x /= y = xs == ys
>                                  | otherwise = oneHop xs ys

As described above, the fringe is the set of words at the ends of the partial ladders computed so far:

>     fringe :: [[String]] -> Set String
>     fringe paths = Set.fromList (map last paths)

Once we've seen the goal in the fringe, we return the ladder that ends with the goal word:

>     winner :: [[String]] -> [String]
>     winner paths =
>       case (find ((== goal) . last) paths) of
>         Nothing -> undefined
>         Just a -> a