euc2003

[Luke Gorrie]

"Thomas Arts" <thomas.arts@REDACTED> writes:

> As Björn already pointed out, the version does handle recursive
> datatypes definitions.

We have this pretty well covered now, but all the same here's the
follow-up that John Hughes mailed me earlier:



I saw your mail on the Erlang list archive, but I haven't figured out how to
contribute myself yet. Maybe you could copy this to the list?

I simplified the sets generator in my talk, and avoided talking about the
need to limit the size of generated sets in order to ensure termination.
It's the only simplification I made, and seemed necessary given that the
talk anyway threatened to exceed the slot. But maybe that was a mistake... I
hadn't really expected that people would immediately try out the code on the
slides! Mea culpa.

Anyway, the solution we use is to observe the size parameter that all
generators receive, and then use it to limit the size of sets generated. I
should explain that while all generators receive a size parameter, which
increases gradually during testing, its interpretation is entirely up to the
programmer. For example, here is the sets generator I used for the results
in the talk:

set() -> ?SIZED(Size,set(trunc(math:sqrt(Size))+1)).

set(0) -> return({'@',sets,new,[]});
set(Size) ->
  frequency([return({'@',sets,new,[]}),
      {6,?LET(L,list(int()),return({'@',sets,from_list,[L]}))},

{6,?LET(S,set(Size-1),?LET(E,int(),return({'@',sets,add_element,[E,S]})))},

?LET(S,set(Size-1),?LET(E,int(),return({'@',sets,del_element,[E,S]}))),
      ?LET({S1,S2},two(set(Size div 3)),return({'@',sets,union,[S1,S2]})),
      ?LET({S1,S2},two(set(Size div
3)),return({'@',sets,intersection,[S1,S2]})),
      ?LET({S1,S2},two(set(Size div
3)),return({'@',sets,subtract,[S1,S2]})),

?LET(S,set(Size-1),?LET(P,function(bool()),return({'@',sets,filter,[P,S]})))
]).

If one sticks to 100 tests, the size only ranges up to 21, so maybe taking
its square root was a bit drastic... it's a question of judgement how large
test cases one wants vis a vis how faast one wants testing to be. At any
rate, you see that a small modification of the code I showed ensures that
generation terminates.

One principle we try to follow is that as the size parameter increases, so
all possible sets should be generatable. Thus if we continue testing long
enough, any fault will eventually be revealed.

John