Reminds me of this essay that pg wrote in 2005, titled The Submarine. Someone linked it in another thread here on HN recently.
> One of the most surprising things I discovered during my brief business career was the existence of the PR industry, lurking like a huge, quiet submarine beneath the news. Of the stories you read in traditional media that aren't about politics, crimes, or disasters, more than half probably come from PR firms.
First, I've never heard of program synthesis, and it seems like an interesting topic. Could you point me to some resources so I can learn more about it?
Second. I take issue with this statement:
> "trying to generate new code by modelling old code has the obvious limitation that no genuinely new code can be generated"
I disagree. We've seen GAN's generate genuinely new artwork, we've seen music synthesizers do the same. We've also seen GPT-3 and other generative text engines create genuinely interesting and innovative content. AI dungeon comes to mind. Sure, it's in one way or another based on it's training data. But that's what humans do too.
Our level of abstraction is just higher, and we're able to generate more "distinct" music/code/songs based on our own training data. But that may not hold in the long term, and it also doesn't mean that current AI models can do nothing but regurgitate. They can generate new, genuinely interesting content and connections.
I'll leave it to the GP to give a lit review, but will say that CS has (always had) a hype-and-bullshit problem, and that knowing your history is good way to stay sober in this field.
> We've also seen GPT-3 and other generative text engines create genuinely interesting and innovative content.
Making things humans find entertaining is easy. Markov chains could generate genuinely interesting and innovative poetry in the 90s. There's a Reply All episode on generating captions for memes or something where the two hosts gawk in amazement at what's basically early 90s tech.
> They can generate new, genuinely interesting content and connections.
Have you ever dropped acid? You can make all sorts of fascinating content and connections while hallucinating. Seriously -- much more than when you're sober. Probably shouldn't push to prod while stoned, though.
Art and rhetoric are easy because there's really no such thing as "Wrong". That's why we've been able to "fake creative intelligence" since the 80s or 90s.
Almost all software that people are paid to write today is either 1) incredibly complicated and domain-specific (think scientists/mathematicians/R&D engineers), or else 2) interfaces with the real world via either physical machines or, more commonly, integration into some sort of social processes.
For Type 1, "automatic programming" has a loooong way to go, but you could imagine it working out eventually. Previous iterations on "automatic programming" have had huge impacts. E.g., back in the day, the FORTRAN compiler was called an "automatic programmer". Really.
For Type 2, well, wake me up there's a massive transformer-based model that only generates text like "A tech will be at your house in 3 hours" when a tech is actually on the way. And that's a pretty darn trivial example.
There is a third type of software: boilerplate and repetitive crap. Frankly, for that third type, I think the wix.com model will always beat out the CoPilot model. And it's frankly the very low end of the market anyways.
The following is a comprehensive introduction and survey of recent work in the field:
https://www.microsoft.com/en-us/research/wp-content/uploads/...
Regarding novelty, neural networks are excellent at interpolation but awful at extrapolation. What I mean by interploation is that the models learned by a neural network represent a dense region of cartesian space circumscribed by the neural net's training instances. The trained model can recognise and generate instances included in this dense region, including instances not included in its training set, by interpolation, but it is almost completely incapable of representing instances outside this dense region by extrapolation [1].
So basically what I'm saying above is that deep learning language model code generators can't extrapolate to programs that are not similar to the programs they've been trained on. Hence, no real novelty. But you can go a long way without such novelty hence my expectation that e.g. Copilot can be a nice boilerplate generator.
______________
[1] My standard reference for this is the following article by François Chollet, maintainer of Keras:
https://blog.keras.io/the-limitations-of-deep-learning.html
See also the second part of the series of articles where possible ways are proposed to address this limitation:
https://blog.keras.io/the-future-of-deep-learning.html
The latter is relevant to the conversation because the author basically proposes augmanting current deep learning approaches with a form of program synthesis.
Look up the work of Cordell Green. He invented the idea and built a company around it.
Since my first programming job, I've generated code in whatever language I'm using with that language. SQL from SQL, Perl from Perl, etc. And/or regular expressions.
This page:
https://en.wikipedia.org/wiki/Metaprogramming
leaves the impression that using programs to make programs requires a special language or special features, and it was rather a dead end in AI.
I think what you describe is the task of putting together parts of a program according to a configuration. That's a related task and you could certainly see it as a kind of program synthesis, but because it's a common task that we know how to do well, it's not really what program synthesis research is focused on.
Some programming languages are definitely better suited to program synthesis than others. That's particularly the case with languages that have little of what I'd call "ceremony", syntax that's not really necessary to express the behaviour of a program, but are there to help the programmer organise the code, such as classes, maybe, or interfaces, say.
I don't know that metaprogramming was a dead end in AI. I hear that a lot for many subjects of AI research that are still active. I mean, if you asked machine learning researchers ten years ago about neural networks they'd tell you "it's a dead end", or "we tried that and it didn't work" etc. So, unless you're very knowledgeable about a subject of AI research my suggestion is to be cautious when extracting conclusions from a perfunctory perusal of wikipedia or blog posts etc. That's not where most of the knowledge is stored for such deep subjects as AI research.
This sounds like a description of a parser generator.
When I post in conversations like this I do it in the hope that my comments will invite robust debate from knowledgeable contributors, that will challenge my assumptions and my knowledge and help me refine my understanding of the subjects I am interested in. This comment is really so much not that, that it hurts.
There are two parts, at least, to sentience: the observer and the actor. In yogic traditions, "you" are the part that "hears" the voice in your head, not the voice itself. I think this, while it may not necessarily be true of "real" minds, has a lot of utility when it comes to designing artificial ones.
I think general AI is probably going to be lots of individual parts structured around a central observational unit, which then makes preprogrammed higher level decisions on where to distribute inputs and outputs of several external nn, score the results of it's actions, and then use the results for reinforcement and/NEAT or something similar to improve it's central decision making.
This technique of a simple, preprogrammed decision maker given inputs and outputs of stochastic processes is already in use in autonomous navigation (see the GT robotics course on coursera)[1].
The actor doesn't need to understand meaning, the observer assigns meaning to the actions of the actor.
1. "Free Online Course: Control of Mobile Robots from Coursera | Class Central" https://www.classcentral.com/course/conrob-404
https://sunblaze-ucb.github.io/program-synthesis/index.html
I think of large LMs trained on code as something that will sample strings from the space of "code humans might write". This isn't nothing, but as you say it's unlikely to produce programs that solve problems no human has solved before. However, assuming you have a rigorous enough spec, I don't see why you couldn't use something like reinforcement learning on such a model in conjunction with traditional verification tools...
Anyway, I agree it's unfortunate that program synthesis has been overlooked in the latest AI code generation craze -- I've mentioned it to a few journalists when talking about things like Copilot but it doesn't tend to end up in the final article.
I'm pretty sure that as you say deep learning will be used for program synthesis, in fact it already has - the article above mentions a few applications and startups etc. I'm really curious to see how all this will pan out a few years from now. But the applications that are developed commercially are really trying to implement programming aids, rather than solutions to the full program synthesis problem, which, in a nutshell, is to be able to generate arbitrary programs from a specification of some sort.
I'm skeptical that deep learning can really solve this more general (and much harder) problem. The reason I'm skeptical is that neural networks are great approximators but they're not known for their great precision, I guess. With program synthesis the point is usually to really get a program that does what the specification says, no ifs and buts and no 80%-there's. I don't know how neural netwokrs can do in this, but I don't think the answer is "very well".
>> Anyway, I agree it's unfortunate that program synthesis has been overlooked in the latest AI code generation craze -- I've mentioned it to a few journalists when talking about things like Copilot but it doesn't tend to end up in the final article.
Well, thanks for fighting the good fight :)
You've piqued my curiosity, of course. Can you share one of the articles you mention?
https://www.wired.com/story/ai-latest-trick-writing-computer...
https://cacm.acm.org/news/253785-will-ai-rewrite-coding/full...
I think my optimism for deep learning methods here comes not from their ability to generate code from scratch but as a way to guide a search process in the space of programs. By analogy, Go and chess are also domains where approximations won't do, but DNNs have had excellent success in finding better search strategies for the game tree. That's the kind of thing that I think might be successful here.
Yes, there seems to be a trend of using deep learning to guide classical search. The first time I noticed it was in AlphaGo. I was initially skeptical but it seems to have picked up and be producing results.
Personally I'm not interested in that approach very much because my work is on constructive approaches, that completely avoid a search. Don't let me bore you with it (it's my doctoral research... you know how students get with their theses :) but there's links in my sig if you're curious.
And thus the ball is moved back to the human programmers court, as it has since Cobols sentences and paragraphs were supposed to allow managers and business analyst to write code.
I'm actually surprised about the Maruary, Apruary etc error. That is something that FlashFill should be able to handle very well. Strange.
Do you have a link to some post or comment etc with more context about that gif? Maybe it was an older version of the tool? It works correctly (generates month names) in my version of Excel (360 I think?).
Although I do see the Maruary etc error while I fill-in "February" (but not after I drag the cross-handle thingy down).
I’m optimistic about the prospects of some combination of logic solvers and deep learning. As you mention, natural language specs are only approachable with a language model. I think logical constraints could function as really powerful regularization on the output of neural network code gen. Like, constraining output to only programs that satisfy logical constraints inferred from the language.
Also, some forms of programming are super non-trivial to describe and are much more easily specified with input output pairs. This is where the more traditional synthesis approaches really shine. Excel flashfill works astoundingly well for this.
>> Also, some forms of programming are super non-trivial to describe and are much more easily specified with input output pairs.
I agree of course, but then I would, wouldn't I? That's the kind of thing I'm studying...
The Gulwani et al. work behind FlashFill made a huge impression in program synthesis circles when it first came out.
From my point of view (my field of study is basically program synthesis for logic programs) code generation with large language models is not really comparable to what can be achieved with traditional program synthesis approaches.
The main advance seems to be in the extent to which a natural language (i.e. English) specification can be used, but natural language specifications are inherently limited because of the ambiguity of natural language. Additionally, trying to generate new code by modelling old code has the obvious limitation that no genuinely new code can be generated. If you ask a language model to generate code it doesn't know how to generate - you'll only get back garbage. Because it has no way to discover code it doesn't already know how to write.
So Copilot, for example, looks like it will make a fine boilerplate generator - and I'm less skeptical about its utility than most posters here (maybe partly because I'm not worried my work will be automated) but that's all that should be expected of it.