The ChasingBottoms package

[ Tags: library, mit, testing ] [ Propose Tags ]

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 time-out:

@> timeOut' 1 (reverse [1..5\
) >>= print] Value [5,4,3,2,1]@
@> timeOut' 1 (reverse [1..\
) >>= print] NonTermination@

The time-out functionality can be used to treat "slow" computations as bottoms:

> let tweak = Tweak { approxDepth = Just 5, timeOutLimit = Just 2 }
@> semanticEq tweak (reverse [1..\
, [1..]) (bottom :: [Int], [1..] :: [Int])] True@
> let tweak = noTweak { timeOutLimit = Just 2 }
@> semanticJoin tweak (reverse [1..\
, True) ([] :: [Int], bottom)] Just ([],True)@

This can of course be dangerous:

> let tweak = noTweak { timeOutLimit = Just 0 }
@> semanticEq tweak (reverse [1..100000000\
) (bottom :: [Integer])] True@

Timeouts can also be applied to IO computations:

@> let primes = unfoldr (\(x:xs) -> Just (x, filter ((/= 0) . (`mod` x)) xs)) [2..\
@]
> timeOutMicro 100 (print $ filter ((== 1) . (`mod` 83)) primes) >>= print
[167,499NonTermination
> timeOutMicro 100 (print $ take 4 $ filter ((== 1) . (`mod` 83)) primes) >>= print
[167,499,997NonTermination
> timeOutMicro 100 (print $ take 4 $ filter ((== 1) . (`mod` 83)) primes) >>= print
[167,499,997,1163]
Value ()

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.nott.ac.uk/~nad/publications/danielsson-jansson-mpc2004.html).

The code has been tested under GHC 6.8. Most parts can probably be ported to other Haskell compilers, but that would require some work. The TimeOut functions require preemptive scheduling, and most of the rest requires Data.Generics; isBottom only requires exceptions, though.


[Skip to Readme]

Properties

Versions 1.2.2, 1.2.4, 1.3.0, 1.3.0.1, 1.3.0.2, 1.3.0.3, 1.3.0.4, 1.3.0.5, 1.3.0.6, 1.3.0.7, 1.3.0.8, 1.3.0.9, 1.3.0.10, 1.3.0.11, 1.3.0.12, 1.3.0.13, 1.3.0.14, 1.3.1, 1.3.1.1, 1.3.1.2, 1.3.1.3
Dependencies base (>=2 && <4), containers (>=0.1 && <1), mtl (>=1.1 && <2), QuickCheck (>=1.1 && <2), random (==1.*) [details]
License OtherLicense
Copyright Copyright (c) Nils Anders Danielsson 2004-2008.
Author Nils Anders Danielsson
Maintainer http://www.cs.nott.ac.uk/~nad/contact.html
Category Testing
Home page http://www.cs.nott.ac.uk/~nad/software/#Chasing Bottoms
Uploaded Tue Mar 18 19:00:19 UTC 2008 by NilsAndersDanielsson
Distributions Debian:1.3.0.13, NixOS:1.3.1.3, Tumbleweed:1.3.1.2
Downloads 8362 total (168 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]
Hackage Matrix CI

Modules

[Index]

Flags

NameDescriptionDefaultType
small_base

Choose the new smaller, split-up base package.

EnabledAutomatic

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for ChasingBottoms-1.2.4

[back to package description]
ChasingBottoms
--------------

Building
--------

To build: Use Cabal, or use ghc --make Test.ChasingBottoms. (If
Test.ChasingBottoms is already installed you may need to add something
like -ignore-package ChasingBottoms.)

Do not use Cabal to build the documentation. Use make docs instead.
You may need to edit the Makefile first.

To run through the test suite, execute Test.ChasingBottoms.Tests.main.

Possible future work
--------------------

* Making it easier to test equality etc. of functions. (This may be
  easier using the new version of Scrap your boilerplate, Scrap your
  boilerplate with class.)

* More custom generators for partial and infinite values.

Known bugs
----------

None.