Following that paper, a friend and I implemented a simple MCMC-based synthesizer for the GreenArrays chip (a very low-power and rather obtuse architecture based

Following that paper, a friend and I implemented a simple MCMC-based synthesizer for the GreenArrays chip (a very low-power and rather obtuse architecture based on a variant of Forth). Most of the code is up on GitHub in several different repos[1][2]. I'm actually rather proud of some of the code, especially part of the F18A interpreter (F18A is the name of the instruction set on GreenArrays chips). It's rather short and neat. [1]: https://github.com/TikhonJelvis/array-forth https://github.com/TikhonJelvis/array-forth [2]: https://github.com/jacobt/mcmc-synthesis https://github.com/jacobt/mcmc-synthesis My version actually supports loops and even self-modifying code. This no doubt has some performance implications--my current approach is to throttle each test case to take at most as many steps as the input program does. For various reasons, I found it easier to just allow loops than to try to stick to loop-free code. I found that their correctness measure--looking at the number of bits that differs from the expected result--was basically useless for GreenArrays. I actually have some graphs lying around which show how it basically doesn't vary until it suddenly finds a correct program and shoots up to being 100% correct immediately. It does not exhibit the nice hill-climbing behavior that we want. For better or worse, I have not been able to get this style of approach to perform as well as a similar synthesizer using an SMT solver (namely Microsoft's Z3). The advantage with the MCMC system is that it's easily parallelizable. It can also deal with certain programs that can choke up the SMT-based version. The SMT-based system has problems dealing with lots of bits, so we usually run it pretending that the architecture uses ~4 bits instead of 18 (yes, it uses 18 by default!). So for problems requiring more precision, the MCMC approach might be better. Similarly, the SMT system does not model memory terribly efficiently, so problems needing a lot of mutated memory might be better for the randomized system. Also, I should add that I know literally nothing about machine learning and even less about SMT solvers, so it's not surprise that the things I have written don't perform terribly well. Basically, my only solace is that this project's code is mostly rather elegant. I learned quite a bit about programming at a high level of abstraction from this project--some of the things I ended up doing rely on significantly more abstract reasoning than anything I've done before. Anyhow, it's cool to see people reading about something I've been playing around with for a while now. Even if I find the whole field a trifle annoying :P. If you want to play around with this sort of synthesizer, I have uploaded both a generic library based around MCMC[3]--it's surprisingly simple--and the GreenArrays-specific code[4] to cabal, so they're both just a cabal install away. [3]: http://hackage.haskell.org/package/mcmc-synthesis http://hackage.haskell.org/package/mcmc-synthesis [4]: http://hackage.haskell.org/package/array-forth http://hackage.haskell.org/package/array-forth