C      !"#$%&'()*+,-./0123456789:;<=>?@AB non-portable (GHC-specific) experimentalhttp://www.cs.chalmers.se/~nad/C' isFunction f' returns D  iff the top level " constructor"  of f is a function arrow. E>This function is rather fragile, but should be OK. It is only  used by Test.ChasingBottoms.ApproxShow, which should only be used C for debugging purposes anyway. The unit type is not considered to  be a tuple. CEFGCEFG$non-portable (preemptive scheduling) experimentalhttp://www.cs.chalmers.se/~nad/ n c runs c for at most n seconds (modulo  scheduling issues). 1 If the computation terminates before that, then   v is returned, where v is the resulting value. Note 5 that this value may be equal to bottom, e.g. if c = H   #Test.ChasingBottoms.IsBottom.bottom. - If the computation does not terminate, then  is  returned. . If the computation raises an exception, then  e is  returned, where e is the exception. . takes a delay in microseconds. Note that the E resolution is not necessarily very high (the last time I checked it B was 0.02 seconds when using the standard runtime system settings  for GHC). ) is a variant which can be used for pure  computations. The definition,     n =  n . I   ensures that  1 #Test.ChasingBottoms.IsBottom.bottom  usually returns  < something>. ( 1 (H   #Test.ChasingBottoms.IsBottom.bottom) usually returns   #Test.ChasingBottoms.IsBottom.bottom; in other words, the D computation reaches whnf almost immediately, defeating the purpose  of the time-out.)  is the equivalent variant of :    n =  n . I  non-portable (GHC-specific) experimentalhttp://www.cs.chalmers.se/~nad/Natural numbers. No Data.Generics.Basics.Data instance is provided since the $ implementation should be abstract.   0 == J (, for other total natural numbers it is D .   0 == K ,   (n+1) == L  n for a  total natural number n.  2 performs primitive recursion on natural numbers.   is a fold on natural numbers:     g h =   g (M  N  h . O )    non-portable (exceptions) experimentalhttp://www.cs.chalmers.se/~nad/   a returns J  if a is distinct from bottom. If  a> equals bottom and results in an exception which is caught by   7, and this exception is of a certain kind (see below),  then   a = D . Other caught exceptions are  re-thrown. If a+ never reaches a weak head normal form and ! never throws an exception, then   a never terminates. The exceptions that yield D  are those that correspond to  " pure bottoms"0, i.e. bottoms that can originate in pure code. D Assertions are excluded, since their behaviour depends on compiler @ flags (not pure, and a failed assertion should really yield an = exception and nothing else). The same applies to arithmetic 4 exceptions (machine dependent, except possibly for  Control.Exception.DivideByZero$, but the value infinity makes that  case unclear as well). 7 generates a bottom that is suitable for testing using   .  s raises an exception (P ) that  is not caught by  . Use s to describe the exception.  timeOutLimit works like   , but if   timeOutLimit is L  lim%, then computations taking more than  lim> seconds are also considered to be equal to bottom. Note that C this is a very crude approximation of what a bottom is. Also note  that this "function"- may return different answers upon different , invocations. Take it for what it is worth. 3 is subject to all the same scheduling vagaries as  #Test.ChasingBottoms.TimeOut.timeOut.    non-portable (GHC-specific) experimentalhttp://www.cs.chalmers.se/~nad/@Monad for generating results given previously generated pattern  matches. A  a6 should be implemented almost as other generators for  the type a, with the difference that  should be C used wherever the resulting function should be allowed to pattern D match (typically for each constructor emitted). See example above. The type of a  generator. Q8This newtype is (currently) necessary if we want to use  ' as an argument to a type constructor. %The type of a generator transformer. 0 packages up the possible outcomes of a pattern E match in a style suitable for generating functions. A pattern match  is a generator (R%) transformer based on the top-level " constructor, and a sequence (see   @http://www.soi.city.ac.uk/~ross/software/html/Data.Sequence.html) of  .es based on the children of that constructor. )A generator transformer, in the style of S. .Further pattern matches made possible by this  match. <Generator for continuous, not necessarily strict functions. B Functions are generated by first generating pattern matches, and  then generating a result.  specialises :    =   Generic implementation of  construction. TLowering of a .  Lifting of a R. U Returns the V in scope. 6 makes sure that the pattern matches get to influence  the generated value. See . W;Extracts some pattern matches to trigger right away. These C triggered pattern matches may result in new pattern matches which + may in turn also be triggered, and so on. XConcatenates arguments. YComposes arguments. Z Partitions a [-. The first argument (a positive integer) is C the relative probability with which elements end up in the second ! part compared to the first one.  Lifting of \.  Lifting of ].  Lifting of ^.  Lifting of _. ! Lifting of `. " Lifting of a. # Lifting of b. $An implementation of  a which is suitable when a  is flat and has an c% instance. Yields bottoms around 10%  of the time. %This  yields finite partial lists. &This  yields infinite partial lists. 'This * yields finite or infinite partial lists.  !"#$%&' !"#$%&' !"#$%&'non-portable (GHC-specific) experimentalhttp://www.cs.chalmers.se/~nad/)The d  instance of ( makes sure that  ) n) behaves (more or less) like the derived  version of e ", with the following differences:  After n- levels of descent into a term the output is  replaced by "_". 6 All detectable occurences of bottoms are replaced by "_|_". ' Non-bottom functions are displayed as "< function /= _|_>". ,Precedence level. ()*+,,()*+()*+)*+,non-portable (GHC-specific) experimentalhttp://www.cs.chalmers.se/~nad/--5 is a class for approximation functions as described =in The generic approximation lemma, Graham Hutton and Jeremy AGibbons, Information Processing Letters, 79(4):197-201, Elsevier Science, August 2001,  &http://www.cs.nott.ac.uk/~gmh/bib.html. .Instances are provided for all members of the d  type class. Due to the limitations of the  Data.Generics approach to generic Dprogramming, which is not really aimed at this kind of application, Athe implementation is only guaranteed to perform correctly, with Frespect to the paper (and modulo any bugs), on non-mutually-recursive >sum-of-products datatypes. In particular, nested and mutually >recursive types are not handled correctly with respect to the Epaper. The specification below is correct, though (if we assume that the d  instances are well-behaved). In practice the .+ function can probably be more useful than /. It traverses down all% subterms, and it should be possible 4to prove a variant of the approximation lemma which .  satisfies. .. n x traverses n levels down in x and replaces all $ values at that level with bottoms. // works like ., but the traversal and C replacement is only performed at subterms of the same monomorphic = type as the original term. For polynomial datatypes this is  exactly what the version of approx described in the paper above  does. -./-./-././non-portable (GHC-specific) experimentalhttp://www.cs.chalmers.se/~nad/004 contains methods for testing whether two terms are 4 related according to the semantic domain ordering. 55 tweak x y returns K  if x and y are  incomparable, and L  o otherwise, where o :: f  ! represents the relation between x and y. 9x 6 y and x 7 y& compute the least upper and greatest  lower bounds, respectively, of x and y in the semantical A domain ordering. Note that the least upper bound may not always  exist. 8 This functionality was implemented just because it was ' possible (and to provide analogues of g  and h  in the i  = class). If anyone finds any use for it, please let me know. ::4 contains methods for testing whether two terms are  semantically equal. >=The behaviour of some of the functions below can be tweaked. @ If equal to L  n, an . n is performed on A all arguments before doing whatever the function is supposed to  be doing. A If equal to L  n', then all computations that take more  than n3 seconds to complete are considered to be equal to  *. This functionality is implemented using  . BNo tweak (both fields are K ). 0123456789:;<=>?@AB>?@AB:;<=01234567890 123456789123456789:;<=;<=>?@A?@ABnon-portable (GHC-specific) experimentalhttp://www.cs.chalmers.se/~nad/C  !"#$%&'()*+,-./0123456789:;<=>?@ABj !"#$%&'()*+,-.//0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXXYZ[\ ]^_` ab cd e f g h ai j klmnopqrstuvwxyz{|}~   ChasingBottoms-1.2.2Test.ChasingBottoms.TimeOutTest.ChasingBottoms.NatTest.ChasingBottoms.IsBottom'Test.ChasingBottoms.ContinuousFunctionsTest.ChasingBottoms.ApproxShowTest.ChasingBottoms.ApproxTest.ChasingBottoms.SemanticOrdTest.ChasingBottoms.IsTypeghc-primGHC.Boolbase Control.MonadControl.Exception.Base Data.Maybe Data.TuplePreludeControl.OldExceptionQuickCheck-1.2.0.0Test.QuickCheckcontainers-0.2.0.1 Data.Sequence Data.Data Text.Show GHC.OrderingData.OrdTest.ChasingBottomsResult ExceptionNonTerminationValuetimeOut timeOutMicrotimeOut' timeOutMicro'NatisSuccfromSuccnatrecfoldNisBottombottomnonBottomErrorisBottomTimeOut MakeResultMakePMGenTransformer PatternMatchapplymorefunction functionTomatchlift' transform arbitrary'choose' elements'oneof' frequency'sized'resize'flat finiteListOfinfiniteListOflistOf ApproxShowapproxShowsPrec approxShows approxShowPrecApprox approxAllapprox SemanticOrd!>=!<=!semanticCompare\/!/\! semanticJoin semanticMeet SemanticEq==!/=! semanticEqTweak approxDepth timeOutLimitnoTweak isFunctionTrueisTupleisStringisListGHC.Basereturn GHC.IOBaseevaluateFalseNothingJustcurry$sndAssertionFailedGenTransformer'Gen coarbitraryrungetPMsPatternMatches getMatchesconcatcompose partitionSeq arbitrarychooseelementsoneof frequencysizedresize ArbitraryDataGHC.Show showsPrecOrdering GHC.ClassesmaxminOrd