baxter@zola.ics.uci.edu (Ira Baxter) (07/09/90)
In <1990Jul8.011033.947@dhw68k.cts.com> stein@dhw68k.cts.com (Rick 'Transputer' Stein) writes: > [about Stanford professor J. R. Koza's scheme for 'breeding' computer programs that pass a specification test of some kind to get better programs to pass that same test] The test to see if the program matches the specification is crucial. If this test is simply "Does program A produce output O for some input I" for a large number of pairs of <I,O>, this scheme can't possibly work, for the simple reason that there is no guarantee that any program that correctly processes N input pairs has any chance of correctly processing pair N+1. Consequently, the process can't terminate with a trustworthy program. If a newly bred program is tested with a theorem prover against a formal spec, I suppose Koza has a better chance, but I can't see how one can combine program fragments from two seperate programs that operate correctly on non-overlapping sets of pair, and get a result which is more likely to be provably correct. I don't know of anybody that can prove any particular program correct automatically (and folk have been trying for 20+ years, now) let alone one generated by cut-n-paste, so even if his cut-n-paste scheme had merit, he'd have to solve another major problem before his entire scheme flew. This idea sounds, on the surface, a bit insane. Anybody got any more details? >My comments on this: >1) I didn't think it was possible to split up an input tape, in the Turing >sense, and splice it back together so that your code is now a hybrid of the >original instructions which is more efficient or correct. Me neither. See above. >2) I thought the only way to build reuseable software was ala Draco, i.e., >a constraint-based input specification. By Draco, I assume you mean Jim Neighbor's domain-oriented transformation system. If you do, I don't know what you mean by "constraint-based input specification", Draco certainly doesn't have those. What do you mean, the *only* way? There are presumably many ways to build reusable software. Writing a FORTRAN subroutine is another way. The problem with reusable software isn't so much writing it, as it is storing it in a way it can be retrieved when you want the same effect, and customizing it to your current problem. Your style of "reuse" is driven by the retreival and customization mechanisms; these will determine how you build the software. See G. Arango's thesis: @phdthesis(Arango88a:thesis-domain-engineering, title = "{Domain Engineering for Software Reuse}", author = "Guillermo Arango", school = "Department of Information and Computer Science, University of California at Irvine", month = "July", year = 1988, note = "Available as Advanced Software Engineering Project RTP086", >3) Does anyone know of a commercially-born product which was hatched from >this "binary primordial software solution?" I don't. I'd run if a vendor offered to sell me one. The closest thing I know of is the commercial Beagle classification generator, which is based loosely on John Holland's genetic algorithms stuff. Now you know as much as I do about it. -- Ira Baxter