Fuzzers for functions

[Janiczek]

The idea, as far as I understand it, is to generate a list of mappings from a to b, and convert that list to a function.

There are a bunch of functions to change these: map works as usual, to change the b into c, but we can also have coMap (profunctor?) that works on the input instead of on the output: given a z -> a function, it changes a -> b to z -> b.

The simplest generated functions map all values to some default value, and more complicated functions have exceptions from the default (ie. "map 9 to 1, map everything else to 0"). Such functions with exceptions do shrink towards the "no exception" case (a constant function).

Prior art:

• https://www.google.com/search?q=%22Shrinking+and+showing+functions%22+Koen+Claessen
• https://www.youtube.com/watch?v=CH8UQJiv9Q4
• https://hackage.haskell.org/package/QuickCheck-2.14.3/docs/Test-QuickCheck-Function.html
• https://hackage.haskell.org/package/QuickCheck-2.13.1/docs/Test-QuickCheck.html#t:Function
• https://hackage.haskell.org/package/QuickCheck-2.13.1/docs/Test-QuickCheck.html#v:Fun
• https://hackage.haskell.org/package/QuickCheck-2.13.1/docs/Test-QuickCheck-Arbitrary.html#t:CoArbitrary

A classic poster child example of "hey we can generate functions" in the PBT context is testing that map f (filter p xs) == filter p (map f xs). (This is not true.)

[gampleman]

I've done this twice before.

The easier way to do this is to have mutability under the hood and simply run the fuzzer for the output type every time the function is called with an input you haven't seen before. Then you can print the resulting table.

The other option I've done in Elm is ask the user for a hashing function for the input type, then use that as the seed for the output type generator. This works well, but a) the ergonomics leave something to be desired b) there is no way to print a table, since it's fully the size of the input.

Neither option is that great and neither is obvious how to shrink them.

If I understand properly, what the proposal here roughly is you generate a positive integer n, then generate n inputs and n+1 outputs, then see if the function input matches one of the generated inputs, in which case return the corresponding output, otherwise return the final output? Shrinking is then making n smaller and shrinking the outputs¹. Printing is also relatively straightforward since you can just print the table (or turn it into semi-valid elm by interspersing if then else).

I guess what that would require is to make fuzzers and tests have a separate representation for executing tests and a separate representation for printing them (which could be useful for other things).

Footnotes

1. Question: do you also shrink the inputs? Seems like a tricky piece of business with this approach will be shrinking efficiently. If a test both provides a function that acts on some type and a value of that type, then for the effect to keep persisting, one would somehow need to shrink both in lockstep... ↩

[Janiczek]

Interesting, my first thought would be to generate some kind of AST that you'd then interpret to get the final generated function.

[gampleman]

AST seems quite difficult to me and difficult to generalize. Like what would the nodes be if the user is trying to do some arbitrary datatype?

I should also point out that the main downside with the table based solution is that it requires equality on the inputs. This makes higher order functions in particular impossible.

[gampleman]

I suppose one thing we could try is sort of a defunctionalized approach, where the user supplies operations and we automatically construct a graph out of them:

type Op =
   Add Op Op | Mutliply Op Op | Negate Op | Constant Int | Arg1


eval : Op -> Int -> Int
eval op arg1 =
   case op of
      Add a b ->
         eval a arg1 + eval b arg1
   
      Mutliply a b ->
         eval a arg1 * eval b arg1

      Negate a ->
         -(eval a arg1)

      Constant num ->
          num

      Arg1 ->
          arg1

fuzzer : Fuzz Op
fuzzer = 
   Fuzz.graph 
      [ Fuzz.Graph.op2 Add
      , Fuzz.Graph.op2 Multiply
      , Fuzz.Graph.op1 Negate
      , Fuzz.Graph.constF (Fuzz.map Constant Fuzz.int)
      , Fuzz.Graph.const Arg1
      ] 
   

test : Test
test = Test.fuzz3 fuzzer fuzzer (Fuzz.list Fuzz.int) "map f >> map g == map (f >> g)" <|
   \fO gO inp ->
       let
          f = eval fO
          g = eval gO
       in
       map f (map g inp)
          |> Expect.equal (map (f >> g) inp)

or some such. Seems like a lot of manual work to get any sort of "interesting" behavior. However, this sort of defunctionlized fuzzing could be quite useful for constructing app tests, especially if we could embelish the graph fuzzer with state and pre/post conditions.

[Janiczek]

I haven't thought about feasibility / usability much, but (from the user's perspective) I'm imagining Fuzz.function : Fuzzer a -> Fuzzer b -> Fuzzer (a -> b) and:

test : Test
test =
  Test.fuzz3 "example test"
    (myStructureFuzzer Fuzz.int) 
    (Fuzz.function Fuzz.int Fuzz.int) 
    (Fuzz.function Fuzz.int Fuzz.char) <|
  \input f g ->
    (input |> MyStructure.map f |> MyStructure.map g) 
      |> Expect.equal (input |> MyStructure.map (f >> g))

ie. no ASTs they'd need to care about.

[gampleman]

Yeah that's more the table approach what you sketched.

All I was trying to point out with the defunctionalized AST is an alternative that might have other usecases, yet still be somewhat useful for function fuzzing.