[Haskell] ANNOUNCE: Chasing Bottoms
Nils Anders Danielsson
nad at cs.chalmers.se
Fri Jun 18 19:26:41 EDT 2004
Excerpt from the documentation at
http://www.cs.chalmers.se/~nad/software/ChasingBottoms/docs/:
Chasing Bottoms
===============
Do you ever feel the need to test code involving bottoms (e.g. calls to
the error function), or code involving infinite values? Then this library
could be useful for you.
It is usually easy to get a grip on bottoms by showing a value and waiting
to see how much gets printed before the first exception is encountered.
However, that quickly gets tiresome and is hard to automate using e.g.
QuickCheck (http://www.cs.chalmers.se/~rjmh/QuickCheck/). With this
library you can do the tests as simply as the following examples show.
Testing explicitly for bottoms:
> isBottom (head [])
True
> isBottom bottom
True
> isBottom (\_ -> bottom)
False
> isBottom (bottom, bottom)
False
Comparing finite, partial values:
> ((bottom, 3) :: (Bool, Int)) ==! (bottom, 2+5-4)
True
> ((bottom, bottom) :: (Bool, Int)) <! (bottom, 8)
True
Showing partial and infinite values (\/! is join and /\! is meet):
> approxShow 4 $ (True, bottom) \/! (bottom, b)
"Just (True, b)"
> approxShow 4 $ (True, bottom) /\! (bottom, b)
"(_|_, _|_)"
> approxShow 4 $ ([1..] :: [Int])
"[1, 2, 3, _"
> approxShow 4 $ (cycle [bottom] :: [Bool])
"[_|_, _|_, _|_, _"
Approximately comparing infinite, partial values:
> approx 100 [2,4..] ==! approx 100 (filter even [1..] :: [Int])
True
> approx 100 [2,4..] /=! approx 100 (filter even [bottom..] :: [Int])
True
The code above relies on the fact that bottom, just as error "...",
undefined and pattern match failures, yield exceptions. Sometimes we are
dealing with properly non-terminating computations, such as the following
example, and then it can be nice to be able to apply a timeout.
> let primes = unfoldr (\(x:xs) -> Just (x, filter ((/= 0) . (`mod` x)) xs)) [2..]
> timeOutMicro 100 (print $ filter ((== 1) . (`mod` 32)) primes) >>= print
[97,193,257Nothing
> timeOutMicro 100 (print $ take 5 $ filter ((== 1) . (`mod` 32)) primes) >>= print
[97,193,257,353Nothing
> timeOutMicro 100 (print $ take 5 $ filter ((== 1) . (`mod` 32)) primes) >>= print
[97,193,257,353,449]
Just ()
All the type annotations above are required.
For the underlying theory and a larger example involving use of
QuickCheck, see the article "Chasing Bottoms, A Case Study in Program
Verification in the Presence of Partial and Infinite Values"
(http://www.cs.chalmers.se/~nad/publications/danielsson-jansson-mpc2004.html).
Source code:
http://www.cs.chalmers.se/~nad/software/ChasingBottoms/chasing-bottoms.tar.gz.
/NAD
More information about the Haskell
mailing list