2 ms·

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 in

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.

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.