5 ms·

I did a bit of research in program synthesis, which is probably the closest academic field to this sort of thing (albeit in the realm of programming languages r

by tikhonj 10y ago

I did a bit of research in program synthesis, which is probably the closest academic field to this sort of thing (albeit in the realm of programming languages rather than AI/ML). I have two main conclusions: • Current methods to generate programs fundamentally do not scale. Most practical research is about how to extend small-scale synthesis systems to large-scale problems, rather than synthesizing large programs outright. • The best way to scale these systems is to make them more interactive. Let the programmer do what's easy for humans and use synthesis for the parts easy to automate. This is another way of saying that program synthesis is less about fully automatic programming and more about (radically) better development tools. I am confident that we will not have automatic programming systems that can handle non-trivial programs by themselves in the next 10/20 years, barring the sort of paradigm-shifting breakthroughs we can't really predict. Instead, we will have systems that can generate some amount of code and work in tandem with programmers—perhaps through sketching[1], programming by demonstration or just much-improved Intellisense. The current trajectory is that programming is to become easier, not obsolete. The result will not be fewer programmers but more programmers, largely because people with less expertise will be able to become programmers: think Jevons Paradox[2] for programming. Programming as a job will change and people will certainly have to adapt, but the job as a whole is not going anywhere. [1]: https://people.csail.mit.edu/asolar/papers/thesis.pdf https://people.csail.mit.edu/asolar/papers/thesis.pdf [2]: https://en.wikipedia.org/wiki/Jevons_paradox https://en.wikipedia.org/wiki/Jevons_paradox

Houshalter 10y ago
Current program synthesis isn't that advanced. At least not compared to state of the art AI. Recently AI has proved it can beat expert humans at all perfect information games. Go has a ridiculously huge search space, but by using neural networks AIs can learn to narrow it down to a manageable size. Program synthesis is just like a perfect information game. You have a search space, a state, a set of goals, etc. You could theoretically make it into a board game, and have human experts challenge computers at it.
- tikhonj 10y ago
  I think that measuring state spaces is really misleading. (Although we totally did that to aggrandize how good our synthesis system was, at least to ourselves :P. The space of possible programs, even short ones in a small language, quickly gets hilariously large.) Past a certain point the structure of a space is what matters which dictates how well any given search strategy will perform, and that doesn't readily generalize across domains. I have not seen anything that would lead me to believe that results like AlphaGo will meaningfully generalize to such an extent. I still think that it would take more than just incremental work to get from where we are now to scalable program synthesis.
  - Houshalter 10y ago
    You are right, but I'm just trying to say that AI is now believed to be able to beat all perfect information games. If you could model program synthesis as a game (regardless how boring/unfun it might be) computers could beat expert humans at it. OR, we have game that humans are still better at, and AI researchers at big companies will spend years attacking it for fame and glory. Either way it's interesting.
- throwawaykeno 10y ago
  > You could theoretically make it into a board game But not actually. Program synthesis is hard even if you have perfect formal requirements. In practice, gathering formal requirements is by far the most difficult task. You're probably better off building a system using modern development practices than trying to collect formal requirements Let alone translating those requirements into code, which is easier than coming up with the requirements but still difficult. > Recently AI has proved... FYI, it's not as if the program synthesis folks haven't heard of neural nets... you're giving researchers who actually do this stuff all day surprisingly little credit.
  - Houshalter 10y ago
    I think that getting the formal requirements is in some ways easier than programming. People can describe the things they want the computer to do, like sorting a list so it's all in order. Actually coming up with an algorithm that does that efficiently is much harder, and is where bugs come from. I mean yes good program synthesis wouldn't replace programmers on it's own. But it would radically change how programming is done and make our lives much easier. I'm just saying that AI is a quickly advancing field and predictions like "not in 20 years" have been defied months later. Applying deep reinforcement learning to tasks like game playing is relatively novel, and has only really started to succeed in the last 2 years.

by tikhonj 10y ago

Houshalter 10y ago

Current program synthesis isn't that advanced. At least not compared to state of the art AI. Recently AI has proved it can beat expert humans at all perfect information games. Go has a ridiculously huge search space, but by using neural networks AIs can learn to narrow it down to a manageable size. Program synthesis is just like a perfect information game. You have a search space, a state, a set of goals, etc. You could theoretically make it into a board game, and have human experts challenge computers at it.

tikhonj 10y ago
I think that measuring state spaces is really misleading. (Although we totally did that to aggrandize how good our synthesis system was, at least to ourselves :P. The space of possible programs, even short ones in a small language, quickly gets hilariously large.) Past a certain point the structure of a space is what matters which dictates how well any given search strategy will perform, and that doesn't readily generalize across domains. I have not seen anything that would lead me to believe that results like AlphaGo will meaningfully generalize to such an extent. I still think that it would take more than just incremental work to get from where we are now to scalable program synthesis.
- Houshalter 10y ago
  You are right, but I'm just trying to say that AI is now believed to be able to beat all perfect information games. If you could model program synthesis as a game (regardless how boring/unfun it might be) computers could beat expert humans at it. OR, we have game that humans are still better at, and AI researchers at big companies will spend years attacking it for fame and glory. Either way it's interesting.
throwawaykeno 10y ago
> You could theoretically make it into a board game But not actually. Program synthesis is hard even if you have perfect formal requirements. In practice, gathering formal requirements is by far the most difficult task. You're probably better off building a system using modern development practices than trying to collect formal requirements Let alone translating those requirements into code, which is easier than coming up with the requirements but still difficult. > Recently AI has proved... FYI, it's not as if the program synthesis folks haven't heard of neural nets... you're giving researchers who actually do this stuff all day surprisingly little credit.
- Houshalter 10y ago
  I think that getting the formal requirements is in some ways easier than programming. People can describe the things they want the computer to do, like sorting a list so it's all in order. Actually coming up with an algorithm that does that efficiently is much harder, and is where bugs come from. I mean yes good program synthesis wouldn't replace programmers on it's own. But it would radically change how programming is done and make our lives much easier. I'm just saying that AI is a quickly advancing field and predictions like "not in 20 years" have been defied months later. Applying deep reinforcement learning to tasks like game playing is relatively novel, and has only really started to succeed in the last 2 years.