5 ms·

In order to really solve this, you couldn't use an LLM, at least not one in any shape that we have now. You'd need something that actually understands the lang

In order to really solve this, you couldn't use an LLM, at least not one in any shape that we have now. You'd need something that actually understands the language. What is a lifetime, what is scope, what are types, functions, variables, etc. Something that can contextually look at correct, incomplete, or broken programs and reason about what they're doing by knowing the rules that the language operates on and following them to a conclusion. It would also need to understand high-level design patterns and structure to not just know what's happening in the literal sense "this variable is being incremented" but also in a more abstract sense "this variable keeps track of references because this is mixed C/Python code that needs that to handle deallocation". Something that recognizes patterns both within and outside of the code, with appropriately fuzzy matching where needed. And I think importantly you'd need to be able to query it at a variety of levels. What's happening on a line-by-line basis and what's happening at the high level at a given point of code. One OR the other isn't sufficient. That is not a simple ask. We're a long way away from something that smart existing.

LeifCarrotson 3y ago
What LLM text generation has shown is that you don't actually have to understand English to generate pretty decent English. You just have to have enough examples. This is where the massive corpus of source code available on the Internet can help generate a "LSM" (large software model) if you can expose the tokens as the lexer understands them in the training set. If your LSM sees a trillion examples of correct usage of lifetime and scope and types and so on, then in the same way that an LLM trained on English grammar will emit text with correct grammar as if it understands English, your LSM will generate software with correct syntax as if it understands the software. Whatever the definition of "understands" is in the context of an LLM.
- fragmede 3y ago
  right. we're already abstracting from English words and characters into tokens, piping code through half a compiler so the LSM is given the AST to train on doesn't seem all that far fetched.
- abeppu 3y ago
  But: - natural language is flexible, computer languages are less so. - "pretty decent English" still includes hallucinations. I've seen companies whose product demo for generating marketing copy just makes up a plausible review. Hallucinating methods, variables, other packages/modules yields broken code. - the human thought behind natural language is not feasible to directly provide to a model. An IR corresponding to the source of the program is feasible to provide. A trace of the program executing is feasible to provide. Grounding an LLM in the rich exterior world that humans talk about is hard; grounding an LSM in the rich internal representations accessible to an IDE or a debugger is achievable.
- majormajor 3y ago
  "pretty decent english" is a pretty fuzzy bar. Indeed, Chat GPT 4 and Copilot can generate "pretty decent code" that will look fine to the average human coder even when it's incorrect (making up methods or getting params wrong or slighly missing requirements or similar). The level of precision required for "pretty decent non-trivial code" is much higher than prose that looks like it was written by an educated human, so I share the idea that if it was augmented - even in really stupid ways like asking the IDE if it would even compile, in the case of Copilot, before suggesting it to the user - it would work much better at a much lower effort than increasing it's understanding implicitly by orders of magnitude.
- staunton 3y ago
  > you don't actually have to understand English to generate pretty decent English. You just have to have enough examples. I would have thought babies have been showing this beyond a doubt since time immemorial.
  - deleted 3y ago
    [deleted]
  - eru 3y ago
    No, because we can't look into their skulls, to figure out whether they 'understand', whatever that means.
abeppu 3y ago
Absolutely it's not a simple ask. But research in program synthesis was making interesting progress before LLMs came along. I think it would be better to ask how ML can improve or speed up those efforts, rather than trying to make a general ML model "solve" such a complex problem as a special case. A step in this direction, which I've been trying to figure out as a side project, and which I would love someone to scoop me on and build a real thing, is to stitch an ML model into into a (mini)kanren. Minikanren folk have built relational interpreters for small languages but not for a "real" industrial language (so far as I'm aware). These small relational interpreters can generate programs given a set of relational statements about them (e.g. "find f so that f(x1) == y1, f(x2) == y2, ..."). Because they're actually examining the full universe of programs in their small language, they will eventually find all programs that satisfy the constraints. But their search is in an order that's given by the structure/definition of the interpreter, and so for complex sets of requirements, finding the _first_ satisfying example can be unacceptably slow. But what if the search were based on the softmaxed outputs of an ML model, and you do a least cost search? Then (roughly) in the case that beam-search generation from the ML model would have produced a valid answer, you still find it in roughly the same time, but you _know_ it's valid. In the case where a valid answer requires that in a small number of key places, we have to take a choice that the model assigns low probability, then we'll find it but it takes longer. And in the case that all the choices needed to construct a valid answer are low-probability under the model, then we're basically in the same place that the vanilla minikanren search was.
- aeonik 3y ago
  I've thought a lot about this as well, and I'm convinced it's a really great way forward assuming the model can have some inference of the search space of the queries that it's going to run. It's too easy to fall into infinite loops for something with only a naïve understanding of the questions.
dontupvoteme 3y ago
An interface layer is 70% of the value for 10% of the work.
PoignardAzur 3y ago
I keep seeing these takes and I still think OthelloGPT disproves them. So far it really looks like a sufficiently large LLM with a sufficiently large / high-quality dataset can learn basically anything (given a slightly generous interpretation of the word "sufficiently"). In case of code completion, I think just training on program output in addition to source code would already unlock huge capability boosts.
eru 3y ago
> You'd need something that actually understands the language. What is a lifetime, what is scope, what are types, functions, variables, etc. Why is that more important for programming languages than for human natural languages?
- Night_Thastus 3y ago
  Because if you use a somewhat odd phrasing, uncommon terms, weird sentence structure, etc - human beings are very good at figuring out what is meant. We can interpolate, we can extrapolate, we can estimate and understand context. Very incomplete language can still be understood with the right context. A compiler cannot do these things. The code must follow the rules of the language perfectly, or the code won't compile. And further, it doesn't understand intention like a human can. It doesn't know that you intended to loop over all items in a collection - if you have an off-by-one error it'll happily compile that regardless.

LeifCarrotson 3y ago

What LLM text generation has shown is that you don't actually have to understand English to generate pretty decent English. You just have to have enough examples. This is where the massive corpus of source code available on the Internet can help generate a "LSM" (large software model) if you can expose the tokens as the lexer understands them in the training set. If your LSM sees a trillion examples of correct usage of lifetime and scope and types and so on, then in the same way that an LLM trained on English grammar will emit text with correct grammar as if it understands English, your LSM will generate software with correct syntax as if it understands the software. Whatever the definition of "understands" is in the context of an LLM.

fragmede 3y ago
right. we're already abstracting from English words and characters into tokens, piping code through half a compiler so the LSM is given the AST to train on doesn't seem all that far fetched.
abeppu 3y ago
But: - natural language is flexible, computer languages are less so. - "pretty decent English" still includes hallucinations. I've seen companies whose product demo for generating marketing copy just makes up a plausible review. Hallucinating methods, variables, other packages/modules yields broken code. - the human thought behind natural language is not feasible to directly provide to a model. An IR corresponding to the source of the program is feasible to provide. A trace of the program executing is feasible to provide. Grounding an LLM in the rich exterior world that humans talk about is hard; grounding an LSM in the rich internal representations accessible to an IDE or a debugger is achievable.
majormajor 3y ago
"pretty decent english" is a pretty fuzzy bar. Indeed, Chat GPT 4 and Copilot can generate "pretty decent code" that will look fine to the average human coder even when it's incorrect (making up methods or getting params wrong or slighly missing requirements or similar). The level of precision required for "pretty decent non-trivial code" is much higher than prose that looks like it was written by an educated human, so I share the idea that if it was augmented - even in really stupid ways like asking the IDE if it would even compile, in the case of Copilot, before suggesting it to the user - it would work much better at a much lower effort than increasing it's understanding implicitly by orders of magnitude.
staunton 3y ago
> you don't actually have to understand English to generate pretty decent English. You just have to have enough examples. I would have thought babies have been showing this beyond a doubt since time immemorial.
- deleted 3y ago
  [deleted]
- eru 3y ago
  No, because we can't look into their skulls, to figure out whether they 'understand', whatever that means.

abeppu 3y ago

Absolutely it's not a simple ask. But research in program synthesis was making interesting progress before LLMs came along. I think it would be better to ask how ML can improve or speed up those efforts, rather than trying to make a general ML model "solve" such a complex problem as a special case. A step in this direction, which I've been trying to figure out as a side project, and which I would love someone to scoop me on and build a real thing, is to stitch an ML model into into a (mini)kanren. Minikanren folk have built relational interpreters for small languages but not for a "real" industrial language (so far as I'm aware). These small relational interpreters can generate programs given a set of relational statements about them (e.g. "find f so that f(x1) == y1, f(x2) == y2, ..."). Because they're actually examining the full universe of programs in their small language, they will eventually find all programs that satisfy the constraints. But their search is in an order that's given by the structure/definition of the interpreter, and so for complex sets of requirements, finding the _first_ satisfying example can be unacceptably slow. But what if the search were based on the softmaxed outputs of an ML model, and you do a least cost search? Then (roughly) in the case that beam-search generation from the ML model would have produced a valid answer, you still find it in roughly the same time, but you _know_ it's valid. In the case where a valid answer requires that in a small number of key places, we have to take a choice that the model assigns low probability, then we'll find it but it takes longer. And in the case that all the choices needed to construct a valid answer are low-probability under the model, then we're basically in the same place that the vanilla minikanren search was.

aeonik 3y ago
I've thought a lot about this as well, and I'm convinced it's a really great way forward assuming the model can have some inference of the search space of the queries that it's going to run. It's too easy to fall into infinite loops for something with only a naïve understanding of the questions.

dontupvoteme 3y ago

An interface layer is 70% of the value for 10% of the work.

PoignardAzur 3y ago

I keep seeing these takes and I still think OthelloGPT disproves them. So far it really looks like a sufficiently large LLM with a sufficiently large / high-quality dataset can learn basically anything (given a slightly generous interpretation of the word "sufficiently"). In case of code completion, I think just training on program output in addition to source code would already unlock huge capability boosts.

eru 3y ago

> You'd need something that actually understands the language. What is a lifetime, what is scope, what are types, functions, variables, etc. Why is that more important for programming languages than for human natural languages?

Night_Thastus 3y ago
Because if you use a somewhat odd phrasing, uncommon terms, weird sentence structure, etc - human beings are very good at figuring out what is meant. We can interpolate, we can extrapolate, we can estimate and understand context. Very incomplete language can still be understood with the right context. A compiler cannot do these things. The code must follow the rules of the language perfectly, or the code won't compile. And further, it doesn't understand intention like a human can. It doesn't know that you intended to loop over all items in a collection - if you have an off-by-one error it'll happily compile that regardless.