I wonder if you could find a representation for computer programs that eliminated all of the degrees of freedom that were syntax errors, leaving only valid programs. In a sense that's what an AST is but you can still have invalid ASTs. I bet it would be a lot easier to generate interesting programs in a representation like that.
There is cartesian genetic programming and some lisp-like models to encode a program as a tree where all combination are valid.
Combined with recent work on convolutional graph DNNs, this might be a good approach.
