4 ms·

Doesn't TDD basically provide a spec? Write a test, then let the AI generate a program that passes the test. If the program is still buggy, you didn't write suf

Doesn't TDD basically provide a spec? Write a test, then let the AI generate a program that passes the test. If the program is still buggy, you didn't write sufficient tests.

felixge 10y ago
I don't think it's that simple. Imagine a simple add(int32, int32) int32 function. Unless you write a test for all 2^32 * 2^32 possible inputs and their expected outputs, how could you guarantee that the AI will come up with the "correct" implementation? Automated tests are generally not practical for proofing program correctness. Why would you expect them to be sufficient as a specification format?
- geophile 10y ago
  Software produced by a typical business app developer is not provably correct either. TDD of AI generated code could not hope to produce something more correct. As your tests get better, so would the software produced both by the human and the AI. For your add(int32, int32) function: While an AI-generated implementation is not provably correct unless the test contains 2^64 inputs, I think it's pretty likely that a correct implementation would in fact be generated pretty quickly.
  - spaced_out 10y ago
    I don't think it's as likely as you assume. Let's say you ask the computer to implement your adder, and you feed it the results of a few dozen, or a few hundred uint32 a + uint32 b = uint32 c operations. By coincidence, however, in all of those operations, every time bit a[14] is zero, bit c[26] also happens to be zero. The computer may produce an implementation which assumes this is always the case. The computer may also reason it does not need to look at some of the input bits, if say, for all of the tests, bit b[2] == bit b[16]. It may seem that a solution with assumptions like those are more complex than a simple addition operation, and thus the computer will find the addition solution first, but "simple" is a matter of perspective. Addition requires a logic cascade through the entire number, since the carries of the lower bits must be passed to the upper bits, which requires a critical path equal to the entire length of the inputs/outputs. In searching for an implementation which satisfies the few dozen/hundred test cases you feed it, making assumptions like those in the first paragraph can drastically shorten the critical path, and require far less logic since it's ignoring much of the input. Thus algorithmically, the addition operation may be seen as more complex.
- geophile 10y ago
  (BTW, I don't think it's that simple either. Just pointing out that TDD is a possible approach to avoiding the infinite recursion of specs-are-just-programs-in-a-higher-level-language.)
- jononor 10y ago
  With property-based testing one can describing the behavior over the entire domain(s) of valid inputs. Sampling is used to draw a set of cases to actually test, up to a certain number of test. Knowledge about boundary conditions in the domain can help catching failures earlier, though plain random seems to be pretty darn effective (at least for code written by humans). Candidates with dead code should maybe be punished. Candidates with higher complexity should maybe be punished.
falcolas 10y ago
To completely specify a program via tests, you've effectively written the program. You've also probably written somewhere around 2x the code the actual program would require as well. I'd be more curious to see an AI write tests...
- marcosdumay 10y ago
  > ou've also probably written somewhere around 2x the code the actual program would require as well. If you go trough the easiest path, you just need to write the program and compare the results with the AI's ;) But if you go on a case by case basis, your work will grow exponentially with the program size, not a mere 2x.
naasking 10y ago
Tests are much more verbose than specs. Test validate existential properties, ie. there exist inputs where property P is true, but specs can also specify universal properties, ie. for all inputs property P is true. Static types also specify universal properties, which is why tests can't replace types, even in theory. But tests+types could be a type of spec.
- skybrian 10y ago
  Tests can constrain a problem enough so a human programmer can understand what was intended. In theory, many programs will pass the tests, but in practice most matching programs will be convoluted and in poor taste - they only pass the tests and not the general rules implied by the test cases. In other words, there are additional constraints implied by common-sense principles of software engineering. Developing an AI that can infer a simple, tasteful set of general rules (and suitable types) from a small set of test cases is certainly hard but not theoretically impossible.
a-priori 10y ago
A few years ago I read a post by Bob Martin about how you can solve code kata problems by applying a sequence of 'transformations' to pass one test at a time. His method is very mechanical... so mechanical, in fact, that I think it may be possible to automate it. So I started tinkering with the concept, and I've got a bit of a start on it here: https://github.com/michaelmelanson/autocoder https://github.com/michaelmelanson/autocoder What's there is very rudimentary. The main class is a good place to start. Basically I'm building up a library of transformations that can describe solutions to kata problems (the 'word wrap' one currently). The next step is to create a search algorithm to derive an ordered sequence of transformations from that library to pass an ordered sequence of tests.
- hcs 10y ago
  You might find Perelman et al's "Test-Driven Synthesis" paper interesting, it also cites that post as inspiration. http://homes.cs.washington.edu/~djg/papers/tds-pldi2014.pdf http://homes.cs.washington.edu/~djg/papers/tds-pldi2014.pdf

Doesn't TDD basically provide a spec? Write a test, then let the AI generate a program that passes the test. If the program is still buggy, you didn't write sufficient tests.

felixge 10y ago

I don't think it's that simple. Imagine a simple add(int32, int32) int32 function. Unless you write a test for all 2^32 * 2^32 possible inputs and their expected outputs, how could you guarantee that the AI will come up with the "correct" implementation? Automated tests are generally not practical for proofing program correctness. Why would you expect them to be sufficient as a specification format?

geophile 10y ago
Software produced by a typical business app developer is not provably correct either. TDD of AI generated code could not hope to produce something more correct. As your tests get better, so would the software produced both by the human and the AI. For your add(int32, int32) function: While an AI-generated implementation is not provably correct unless the test contains 2^64 inputs, I think it's pretty likely that a correct implementation would in fact be generated pretty quickly.
- spaced_out 10y ago
  I don't think it's as likely as you assume. Let's say you ask the computer to implement your adder, and you feed it the results of a few dozen, or a few hundred uint32 a + uint32 b = uint32 c operations. By coincidence, however, in all of those operations, every time bit a[14] is zero, bit c[26] also happens to be zero. The computer may produce an implementation which assumes this is always the case. The computer may also reason it does not need to look at some of the input bits, if say, for all of the tests, bit b[2] == bit b[16]. It may seem that a solution with assumptions like those are more complex than a simple addition operation, and thus the computer will find the addition solution first, but "simple" is a matter of perspective. Addition requires a logic cascade through the entire number, since the carries of the lower bits must be passed to the upper bits, which requires a critical path equal to the entire length of the inputs/outputs. In searching for an implementation which satisfies the few dozen/hundred test cases you feed it, making assumptions like those in the first paragraph can drastically shorten the critical path, and require far less logic since it's ignoring much of the input. Thus algorithmically, the addition operation may be seen as more complex.
geophile 10y ago
(BTW, I don't think it's that simple either. Just pointing out that TDD is a possible approach to avoiding the infinite recursion of specs-are-just-programs-in-a-higher-level-language.)
jononor 10y ago
With property-based testing one can describing the behavior over the entire domain(s) of valid inputs. Sampling is used to draw a set of cases to actually test, up to a certain number of test. Knowledge about boundary conditions in the domain can help catching failures earlier, though plain random seems to be pretty darn effective (at least for code written by humans). Candidates with dead code should maybe be punished. Candidates with higher complexity should maybe be punished.

falcolas 10y ago

To completely specify a program via tests, you've effectively written the program. You've also probably written somewhere around 2x the code the actual program would require as well. I'd be more curious to see an AI write tests...

marcosdumay 10y ago
> ou've also probably written somewhere around 2x the code the actual program would require as well. If you go trough the easiest path, you just need to write the program and compare the results with the AI's ;) But if you go on a case by case basis, your work will grow exponentially with the program size, not a mere 2x.

naasking 10y ago

Tests are much more verbose than specs. Test validate existential properties, ie. there exist inputs where property P is true, but specs can also specify universal properties, ie. for all inputs property P is true. Static types also specify universal properties, which is why tests can't replace types, even in theory. But tests+types could be a type of spec.

skybrian 10y ago
Tests can constrain a problem enough so a human programmer can understand what was intended. In theory, many programs will pass the tests, but in practice most matching programs will be convoluted and in poor taste - they only pass the tests and not the general rules implied by the test cases. In other words, there are additional constraints implied by common-sense principles of software engineering. Developing an AI that can infer a simple, tasteful set of general rules (and suitable types) from a small set of test cases is certainly hard but not theoretically impossible.

a-priori 10y ago

A few years ago I read a post by Bob Martin about how you can solve code kata problems by applying a sequence of 'transformations' to pass one test at a time. His method is very mechanical... so mechanical, in fact, that I think it may be possible to automate it. So I started tinkering with the concept, and I've got a bit of a start on it here: https://github.com/michaelmelanson/autocoder https://github.com/michaelmelanson/autocoder What's there is very rudimentary. The main class is a good place to start. Basically I'm building up a library of transformations that can describe solutions to kata problems (the 'word wrap' one currently). The next step is to create a search algorithm to derive an ordered sequence of transformations from that library to pass an ordered sequence of tests.

hcs 10y ago
You might find Perelman et al's "Test-Driven Synthesis" paper interesting, it also cites that post as inspiration. http://homes.cs.washington.edu/~djg/papers/tds-pldi2014.pdf http://homes.cs.washington.edu/~djg/papers/tds-pldi2014.pdf