3 ms·

Out of curiosity, how do you go about generating "random valid well defined programs"? I thought about doing something like this for testing my own toy language

• pfdietz 5y ago
  Basically by a top down approach. For example, to generate a random integer valued form, pick one of N fixed rules and invoke it. A rule for a form of size S might be "generate some value k in [1,S-1] and then partitions S-1 into k integers, generate an integer valued form for each, then produce the form that is their sum." At the leaf nodes, generate constants or variables. Keep track of the variables that are in scope as you do this (and their types.) This is a pretty standard approach used in compiler testing. In languages like C you have problems ensuring the program doesn't cause undefined behavior, but Common Lisp is much nicer in that respect -- for example, evaluation order of arguments to functions is defined, and you don't have to worry about integer operations overflowing. All this has made me appreciate language specifications that really nail down what programs are supposed to do. The forms generated are constrained if one wants them to be easily reducible while preserving validity. Hypothesis has a nice solution to that problem, which I didn't use, as this was done a decade and a half earlier.
  • DylanSp 5y ago
    Interesting, I'll have to take a stab at trying something like that. Thanks for the reply!