4

I hope this post isn't too "Fringe" - I'm sure someone will just kill it if it is :)

Three things made me want to reach out about this now:

  1. Decoupling is so in the forefront of design.
  2. TDD inspires the idea that it doesn't matter how a program comes to exist as long as it works.
  3. Seeing how often the adapter pattern is applied to achieve (1).

I'm almost sure this has been tried from a memory of reading about it around the year 2000 or so. If I had to guess, it was maybe about and earlier version of the Java Spring framework. At this time we were not so far from days when the belief was that computer programs could exhibit useful emergent behavior. I think the article said it didn't work, but it didn't say it was impossible.

I wonder if since then it has been deemed impossible or simply an illusion due to a false assumption of similarity between a brain and a CPU. I know this illusion existed because I had an internship in 1996 where I programmed neural nets that were supposedly going to exhibit "brain damage".

STILL, after all that, I'm sitting around this morning and not able to shake the idea that it should be possible to have a method of programming to allow autonomous components to find each other, attempt to collaborate and their outputs evaluated against a set desired results.

Aaron Anodide
  • 5,463
  • 5
  • 28
  • 37
  • The usefulness of a program is hard to define. Most of the time figuring what behavior would be useful is the main job of a programmer. Quick note: Neural networks have nothing to do with the brain. – Simon Bergot Apr 14 '12 at 21:01
  • on point 1 - i mean do they make any existing tests pass? on point 2 - i disagree but its probably just a matter of semantics - the "neurons" in neural networks are threshold functions that were conceived as a metaphor for the biological neuron (nobody really thought it was that simple, but they thought it might lead to a similarly behaving system - something that only happened in very minuscule amounts) – Aaron Anodide Apr 14 '12 at 21:07
  • Emergent behavior is different from useful behavior. Packet storms on a network and runs on a bank are emergent behaviors, but they aren't useful. I think we're still at the stage where we feel pretty clever if we can predict the onset of emergent behavior, and a long way from designing it to particular ends. – Charles E. Grant Apr 14 '12 at 21:52
  • you think i should strike emergent behavior from the wording of the post or how might you edit it? – Aaron Anodide Apr 14 '12 at 21:54
  • 2
    Your question is very vague. As written it sounds like you are hopping for a genie to pop out of a bottle and grants your wishes even before you state them. Genetic algorithms, cellular automata and neural networks can all generate complex behavior, and can be used to implement sophisticated algorithms, but in order to get them to solve a particular problem they have to be carefully designed to that purpose. I don't know if it's what you intend, but as written it sounds like what you're hopping for is more mind reading than AI. – Charles E. Grant Apr 14 '12 at 22:30
  • thanks for the honest feedback.. if this question doesn't get closed first, I'll add the concrete but simplistic example I thought of but didn't do... – Aaron Anodide Apr 14 '12 at 22:32
  • I tweaked the title a little just now, maybe its clearer – Aaron Anodide Apr 14 '12 at 22:38
  • 2
    I really am not intending to rag on you, but what constitutes a 'valid' program? It's a simple word, but it's sweeping a bunch of stuff under the rug. In the most general case it's known that there is no single algorithm that can correctly identify whether an arbitrary program and input will halt or not. In a rough sense genetic algorithms are combining compatible components to create valid programs, but it's not a magic bullet. The developer has to encode the problem into a genetic representation and come up with a 'fitness' function, which I suppose is something like your notion of 'valid. – Charles E. Grant Apr 14 '12 at 23:31
  • @CharlesE.Grant I believe that genetic algorithms are at least a significant portion of the answer to this OPs question. I have seen them used, in toy fashion at least, to put together very small sections of code, I do not recall if it was at the block, function, or line level, but in a way nearly identical to what the OP asked. I implore you to post GAs as an answer without _too many_ caveats. – Joshua Drake May 11 '12 at 20:25
  • @AaronAnodide in addition to GAs, see Agents and the [Semantic Web](http://en.wikipedia.org/wiki/Semantic_Web#Purpose)"`, as originally envisioned, is a system that enables machines to "understand" and respond to complex human requests based on their meaning.`" – Joshua Drake May 11 '12 at 20:29
  • I have always been extremely intrigued by the semantic web - it seems like the idea has been floating for a long while but the reality is somewhat elusive.. – Aaron Anodide May 11 '12 at 21:00
  • Aaron, did you read my answer? If you find it acceptable, mark it so, if not, please comment. – Adam L Davis Aug 01 '13 at 15:13

1 Answers1

1

Disclaimer: I'm not a researcher, just an interested developer.

The short answer is Yes, this has been done, at least with web-services and with formulaic requirements, not tests.

I assume your question to mean, "given that several algorithms exist, and a set of tests exist, can a program attempt to combine those algorithms randomly trying to pass the tests?"

I agree with Charles E. Grant's assertion that once you start randomly creating programs you run into the Halting Problem (it's impossible to determine if there is an infinite loop in a program), so this can be a problem, but it can be overcome by methodically creating the program, not randomly.

Likewise, whenever you start asking the question, "can we automate this generally?" you very likely approach AI-complete. In other words, any sufficiently complex problem requires a human-level intelligence to solve. To get around this, you need to limit the scope of your question. For example, can a program automatically...

  1. generate code based on requirements? NASA has done extensive research in code generation, but the formal specification required is just as difficult as coding. This goes all the way back to at least 1971, called "Automatic Program Synthesis"
  2. combine existing web-services based on requirements (see "Value-Added Web Services Composition Using Automatic Program Synthesis")
  3. combine read-only web-services (see Automatic composition of information-providing web services based on query rewriting)
  4. create a program for statistical data analysis (see "AutoBayes")
  5. generalize an edit of text (see Avi Bryant at 27:01 who stole it from MIT/MassEdit)
  6. create rules for categorizing text? See below.

A simpler question in computing is "given two existing clusters of data, create a filter that can categorize new data with low error-rates." Text-categorization, such as Spam-filtering falls in this realm. This is a well-studied area and many algorithms exist for solving this problem. RIPPER is one such algorithm, which creates the smallest set of rules that categorize text accurately, much like Einstein's Constraint: "Everything should be kept as simple as possible, but no simpler."

This is all I could find/know. If someone could find something more like what this question asks, I would be very interested. I think what you will find though is that the resulting program will only be as good as your input. The amount of "Tests" you would have to write would be so large, you'd be better off just writing the program.

PS: I had a lot more links but stackexchange won't let me post them :-(

Glorfindel
  • 3,137
  • 6
  • 25
  • 33
Adam L Davis
  • 76
  • 3