HTE in Practice — QuickMutate

Recently, me and John Hughes have been working on different approaches to do mutation testing on Haskell code. John is co-author of QuickCheck and we thought of making the same tool for automating mutation testing to some extent. I loaded up emacs and here is my first attempt to develop QuickMutate

First, let me start by quoting from Wikipedia on mutation testing: "Mutation testing involves modifying a program’s source code or byte code in small ways." The mutations should not break the execution and therefore the mutated programs should pass the type checking. So, I grabbed a version of HTE available online and installed it with Cabal.

> module Test.QuickMutate where
> 
> import Language.Haskell.THIH.Typecheck.Load
> import Language.Haskell.THIH.Typecheck.Types hiding (Module)
> import Language.Haskell.Exts.FromTHIH
> import Language.Haskell.Exts hiding (Name)
> import Data.List

Since it is needed to mutate and change different parts of the program, I decided to use Uniplate to do the generics.

> import Data.Generics.Uniplate.Data 

Also, it is required to typecheck all of the mutated programs without interruptions, therefore, I used the following hack:

> import Control.DeepSeq
> import System.IO.Unsafe
> import Control.Exception as CE
> 
> tcHSE :: Module -> Maybe String
> tcHSE ast =  unsafePerformIO $ 
>              CE.catch 
>                (let x = show $ tcHSEModuleWithPrelude ast
>                 in deepseq x (return $ Just x))    
>                ((\_ -> return Nothing) 
>                  :: (SomeException  -> IO (Maybe a))) 

For automating mutation testing, we need a database of mutation operators. It can be modeled as a list of pairs of names (quantified).

> type MutationOps = [(QName,QName)]

Therefore, the mutating function takes the database of mutation operators and the program and generates the mutated programs.

> mutate :: MutationOps -> Module -> [Module]

As the first step, I defined the transformations using Uniplate:

> mutateE :: (QName , QName) -> Exp -> Exp      
> mutateE p e = transformBi (mutateQ p) e
> 
> mutateQ :: (QName , QName) -> QName -> QName
> mutateQ (op,op') x 
>  | x == op   = op'
>  | otherwise = x       
> 
> mutate dic m = let 
>    ms'     = [transformBi (mutateE pair) m  | pair <- dic]
>    -- ...

Then, I used HTE to infer the type of the original program and all the mutated programs. Finally, I filtered out mutated programs with bad types, types different from the original type and duplications.

>    -- ...
>    Just ty = tcHSE m
>    ms''    = filter ( \ m'-> Just ty == tcHSE m') ms'
>    in (nub (m : ms'') )

To make it easier to play with the code, I made a front-end that takes string instead of AST.

> mutateStr :: [(String,String)] -> String -> [String]
> mutateStr dic inp = let 
>  ParseOk m = parseModule inp
>  in map prettyPrint $ concat $ map getDecl 
>     $ mutate [(toQn x ,toQn y ) | (x,y) <- dic] m
>  where
>   toQn :: String -> QName 
>   toQn inp = let ParseOk (Var m ) = parseExp inp in m              
> 
>   getDecl :: Module -> [Decl]              
>   getDecl(Module _ _ _ _ _ _ dcs) = dcs

Then I started to test.

Testing if it actually does the mutation where it should:

> test_new =  mutateStr  [("(+)","(-)")]  "f x = x + x" 
ghci> test_new 
  ["f x = x + x","f x = x - x"]

Testing if it accepts a mutation that results in valid, yet different type:

> test_wrong = mutateStr [("(+)","(++)")] "f x = x + x"
ghci> test_wrong 
  ["f x = x + x"]

Testing if it accepts a mutation that does not typecheck:

> test_bad   = mutateStr [("(+)","f")]    "f x = x + x"
ghci> test_bad 
  ["f x = x + x"]

Testing if it removes duplications:

> test_dup   = mutateStr [("(-)","(+)")]  "f x = x + x"
ghci> test_dup 
  ["f x = x + x"]

So far it behaves as expected. Of course, there is much more left to do; this is just the beginning!

Posted in Articles | 1 Comment

Updates on Haskell-Suite

The last month was a very busy one!

Here are some updates and good news:

  • Haskell-Name is alive now and is being actively developed! Thanks to Roman
  • Haskell-Types  vLocalAssumptions had some progress but still much work is left.
  • Haskell-Desugar is online if you have not noticed yet.
  • Haskell-Compile & Haskell-Interpret had some progress; I am currently implementing a backend using Epic, the backend of Agda, Epigram and Idris.
  • I am currently writing a paper on how to map back the inferred types from the desugared code to the original code. If everything goes as expected, this bidirectionality will be added to HTE.
  • There are also two other tiny projects:
    Haskell-Dependency which does the dependency analysis and the related transformations.
    Haskell-Dictionary which removes the constraints by using dictionaries.
  • Added to the wish-list / future plan:
    Developing translation to System FC (aka GHC Core)
    Metaprogramming / Template Haskell
  • Few nice ongoing research projects, yet still too early to judge

Well, I am excited about these, lots of fun! I am currently, struggling with my schedule, pushing it to get a few more hours to work on these. Things may go slow, but in general there would be steady progress.
Indeed, I would welcome any sort of support!

Aside | Posted on by | 2 Comments

HIW 2012 – Haskell Suite

Update: the sound is fixed now!

Posted in Articles | Leave a comment

Haskell 2010 Records as Syntactic Sugar

To support the record system of Haskell 2010/98 in HTE, it is enough to add the following rules to the desugaring phase:

  • Generating Functions

    For each datatype D,
    > data X = X1 | X2   Int | X3 { l1 :: String} | X4  { l2 :: Int, l1::String}

    1. Default data constructors:
      for each constructor Ci,  generate a function named newCi of type newCi :: D that constructs a new value of type D using Ci and undefined in each field.
      > newX1,newX2,newX3,newX4 :: X
      > newX1 = X1
      > newX2 = X2 undefined
      > newX3 = X3 undefined
      > newX4 = X4 undefined undefined
    2. Match functions:
      for each constructor Ci, generate a function named isCi of type isCi :: D -> Bool that checks if a value of type D is tagged with Ci.
      > isX1, isX2, isX3, isX4 :: X -> Bool
      > isX1 = \x -> case x of { X1         -> True ; _ -> False}
      > isX2 = \x -> case x of { X2 _     -> True ; _ -> False}
      > isX3 = \x -> case x of { X3 _     -> True ; _ -> False}
      > isX4 = \x -> case x of { X4 _ _ -> True ; _ -> False}
    3. Getter functions:
      for each label li :: Ti, generate a function named li of type li :: D -> Ti that extracts value of  the field labeled li.
      > l1 :: X -> String
      > l1 = \x -> case x of  { X3 x0 -> x0 ; X4 _ x0 -> x0 ; _ -> error “error!”}
      > l2 :: X -> Int
      > l2 = \x -> case x of {X4 x0 _ -> x0  ; _ -> error “error!”}
    4. Setter functions:
      for each label li :: Ti, generate a function named setli of type setli :: Ti -> D -> D that sets value of the field labeled li.
      > setl1 ::  String -> X  -> X
      > setl1 = \v -> \x -> case x of  { X3  _ -> X3  v ; X4  x0 _ -> X4  x0 v ; _ -> error “error!”}
      > setl2 :: Int -> X -> X
      > setl2 = \v -> \x -> case x of {X4 _ x0 -> X4  v  x0  ; _ -> error “error!”}
  • Desugar record update expression as a chain of setter function applications.
    > x { l1 = “test”, l2 = 1}   —>  ((setl2 1)   . (setl1 “test”)) x 
  • Desugar record constructor expression as the record update of  corresponding default data constructor.
    > X4 { l1 = “test”, l2 = 1} —> newX4 { l1 = “test”, l2 = 1}
  • Desugar  the empty record pattern Ci {} as a guard using the match function isCi.
    > f  (X2{})  = “test”  —> f x0 | isX2 x0 = “test”
  • Desugar the non-empty record pattern using patter guards, getter functions and empty record pattern.
    > f  (X4 {l2= 2, l1=x}) = “test”  —> f  (x0@(X4 {}))  | 2 <- l2 x0, x <- l1 x0 = “test”
  • Desugar data declaration with record syntax to the normal ADT syntax.
    data X = X1 | X2   Int | X3 { l1 :: String} | X4  { l2 :: Int, l1::String}
    >   —>
    > data X = X1 | X2   Int | X3            String    | X4             Int          String

For more details:
https://github.com/shayan-najd/Haskell-Desugar/blob/master/Language/Haskell/Exts/Desugar/Record.hs

Posted in Articles | 2 Comments

HTE at Haskell Implementors Workshop 2012

Niklas Broberg is going to present HTE and the broader philosophy behind it at Haskell Implementors Workshop 2012.

You can find the abstract at:
http://www.haskell.org/haskellwiki/HaskellImplementorsWorkshop/2012/Broberg

Posted in Articles | 3 Comments

HTE – v. Haskell 2010 at Github

You can find the code for HTE (v. Haskell 2010) at:

https://github.com/shayan-najd/HTE

You may read the previous posts about the architecture and design of HTE.

It has the following known issues:

  • Records are not supported yet! Soon, I will explain in more details. I am currently working on adding support for extensible records and variants. 
  • It relies on a name resolution process developed as a separate package (Haskell-Name-Exts). But, the code should still be entirely usable. 
  • The dependency analysis is too simplistic! A separate package will take care of it (Haskell-Dependency-Exts).
  • Just a basic interface
  • Bugs!

You may start from :

https://github.com/shayan-najd/HTE/blob/master/Language/Haskell/THIH/Typecheck/Load.hs

For example:

ghci> tcStringWithPrelude3 “data X = X; f y = X”

[("f","forall (t0 :: *) . t0 -> X")]

Feedback is more than welcome.

 

Posted in Articles | Leave a comment

Haskell-Type-Exts Passed the Final Evaluation

I just received an email from Google Open Source Programs Team stating:

Congratulations, from our data it seems that you have successfully passed the Final Evaluations.

What a wonderful adventure! Invaluable experience that I truly owe to my mentor, Niklas Broberg, without whom I would still be decoding meanings out of the Greek symbols in the research papers. Also, I would like to thank Haskell.Org committee and Google for making this project a possibility.

Soon, I will put a snapshot (08/20) of the code (v. Haskell 2010) for the public access.

Posted in Articles | Leave a comment