StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It sounds like you're doing something very much like <a href="http://reddit.honestbleeps.com/" rel="nofollow noreferrer">genetic programming</a>; even if you aren't, GP has to solve some of the same problems—using randomness to generate valid programs. The approach to this that is typically used is to work with a syntax tree: rather than storing <code>x + y * 3 - 2</code>, you store something like the following:</p> <p><img src="https://i.imgur.com/9i837.png" alt="A sample syntax tree."></p> <p>Then, instead of randomly changing the syntax, one can randomly change nodes in the tree instead. And if <code>x</code> should randomly change to, say, <code>+</code>, you can statically know that this means you need to insert two children (or not, depending on how you define <code>+</code>).</p> <p>A good choice for a language to work with for this would be any Lisp dialect. In a Lisp, the above program would be written <code>(- (+ x (* y 3)) 2)</code>, which is just a linearization of the syntax tree using parentheses to show depth. And in fact, Lisps expose this feature: you can just as easily work with the object <code>'(- (+ x (* y 3)) 2)</code> (note the leading quote). This is a three-element list, whose first element is <code>-</code>, second element is another list, and third element is <code>2</code>. And, though you might or might not want it for your particular application, there's an <code>eval</code> function, such that <code>(eval '(- (+ x (* y 3)) 2))</code> will take in the given list, treat it as a Lisp syntax tree/program, and evaluate it. This is what makes Lisps so attractive for doing this sort of work; Lisp syntax is basically a reification of the syntax-tree, and if you operate at the syntax-tree level, you can work on code as though it was a value. Lisp won't help you read <code>/dev/random</code> as a program directly, but with a little interpretation layered on top, you should be able to get what you want.</p> <p>I should also mention, though I don't know anything about it (not that I know much about ordinary genetic programming) the existence of <a href="http://en.wikipedia.org/wiki/Linear_genetic_programming" rel="nofollow noreferrer">linear genetic programming</a>. This is sort of like the assembly model that you mentioned—a linear stream of very, very simple instructions. The advantage here would seem to be that if you are working with <code>/dev/random</code> or something like it, the amount of interpretation needed is very small; the disadvantage would be, as you mentioned, the low-level nature of the code.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload