In case anyone is curious, this is literally the future of programming (I realized it 20 years ago after reading Genetic Programming III by John Koza). The fact that we don't already do this just blows my mind.
For small-scale examples of this, I highly recommend reading up on basic stuff like Karnaugh map simplification and compiler optimization. Once you realize that all computation is just mapping inputs to outputs, and that the main task is actually pruning the search space (not working the problem), everything changes.
Of course, knowing all that, setting up the initial conditions, figuring out the types/ranges/valid values of input, and what the output should be, is half the battle. And it turns out that these are just exactly the tasks you have to do for stuff like training neural nets. It's all going to be machine learning in 10 years is what I'm saying.
Oh and also for anyone interested, today's processors are almost perfectly wrong for this sort of work. Since we're just piping data around (like video games), the cache is borderline useless. Data locality is important though, so just about every core needs its own memory.
My feeling is that AI hasn't improved appreciably in our lifetimes because we're so focused on serial computation that we completely missed the fact that parallel is the way to go. Our brains are 100 billion neurons running at 1 kHz. Kinda hilarious/sad to think about IMHO, but I digress.
You may in fact be right, but I'm keeping away from neural network and AI/ML approaches for now. Part of my motivation here is as a crutch to human understanding - I want the system to be able to fail conclusively (i.e. "no such program at this size and with these assumptions exists" as opposed to "I couldn't find anything"). It's a lot easier to search for a 5-instruction sequence mentally if a computer has told you there _really_ is no 4-instruction sequence.
This is a lot of compiler-type stuff, some bespoke optimizations and - like you say - tons of effort in pruning the search space. The backend to this is a SMT solver, but I have done a great deal of stuff to not get taken hostage by the mysteries of SMT solving (lots of tiny solves rather than handing huge parts of the problem to the solver). SMT solvers are great, and I encourage people to learn to use them, but they often need lots of domain-specific help.
I do think that once I start bootstrapping our way up from short sequences to putting together bigger programs, there will be some AI-ish stuff happening. There are common patterns to how we put together programs that feel like they could be "learned" (after a fashion).
The other big white whale here is to generate a program from a specification rather than from a black box. At the moment the superoptimizer can only make a better version of something that already exists. I do have a few ideas here, too, but there's a stretch goal.
For small-scale examples of this, I highly recommend reading up on basic stuff like Karnaugh map simplification and compiler optimization. Once you realize that all computation is just mapping inputs to outputs, and that the main task is actually pruning the search space (not working the problem), everything changes.
Of course, knowing all that, setting up the initial conditions, figuring out the types/ranges/valid values of input, and what the output should be, is half the battle. And it turns out that these are just exactly the tasks you have to do for stuff like training neural nets. It's all going to be machine learning in 10 years is what I'm saying.
Oh and also for anyone interested, today's processors are almost perfectly wrong for this sort of work. Since we're just piping data around (like video games), the cache is borderline useless. Data locality is important though, so just about every core needs its own memory.
My feeling is that AI hasn't improved appreciably in our lifetimes because we're so focused on serial computation that we completely missed the fact that parallel is the way to go. Our brains are 100 billion neurons running at 1 kHz. Kinda hilarious/sad to think about IMHO, but I digress.