Lisp and Code Mutation

So exams for summer courses are done, and I have no job. I do have a small contract, but other than that I have plenty of time on my hands. So I'm working on a tiny little idea I had (if you've been following this blog for any amount of time I tend to get a fair few of those).

One thing I've always found interesting about Lisp (for this article we can assume I'm talking about Common Lisp) is the homoiconicity. Well I don't know enough of the language to comment on its practical nature - I've been having a nightmare of a time getting into it, documentation online is not great and there seems to be a lot of simple things (like string padding) that aren't there, or at least not that I can find - some of the things you can do with the language are downright amazing. Ruby likes to boast that it can do metaprogramming, but it is nowhere near as powerful as what Lisp can do.

Anyway, enough on the impressions of the language (I'm a language snob, I know). Let's get to this idea. A friend of mine who is doing her master's at University of Calgary in swarm theory was out visiting about a month ago for a conference on genetic algorithms and evolutionary computing called GECCO. So of course, we ended up talking about the subject. She said that with much of the current research, what they do with genetic algorithms is they put a set of inputs into a program, and then let the program find an "optimal" version of those variables. I thought this was interesting, but limited. See, the variables will change, but the code? Nope, it will stay fixed. The algorithm doesn't change, just the variables within it. Now when working with large neural networks this isn't bad at all, but sometimes maybe the program is the thing that should be changed and not the inputs.

So it got me thinking. In Lisp, because of homoiconicity, code is data and therefore can be manipulated as data. So what if you wrote a program that took as an input another program and a specification, and would alter the program in random ways and check if the program still matched the specification? It would be very interesting to see what would come out.

An even more interesting thing is this: what if the specification was incomplete? If it is too incomplete, the program might not even work anymore. However if the specification just checks the important bits, it's possible that a program outputted by the program re-writer could do some interesting extra things outside of the specification. Most likely not, but it could happen.

Finally as a closing note, there will be programmers who will point out that you could write a program re-writer in any language. It's just the nice thing about Lisp is that you can read in and parse the program by going (read input), which returns an s-expression representing the code that was just read in. It is trivially simple. Then on top of that you can manipulate this s-expression all you like, and then output it to a new file by going (pprint sexp out) and you have an output which is still Lisp. So the whole time, you're working with a single language and there is no real need for any intermediate forms.