[comp.software-eng] Breeding Computer Programs

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

dgg@aplcomm.JHUAPL.EDU (David Gawron) (07/09/90)

In article <1990Jul8.011033.947@dhw68k.cts.com>
stein@dhw68k.cts.com (Rick 'Transputer' Stein) writes:
>
>2) I thought the only way to build reuseable software was ala Draco, i.e., 
>a constraint-based input specification.


Where can I find info on Draco?


					Dave Gawron
					dgg@aplcomm.jhuapl.edu

johnc@plx.UUCP (John C.) (07/10/90)

I read about Danny Hillis' experiments in a transcript of his 
"Simulated Evolution" talk delivered at Esther Dyson's 1990 Personal
Computing Forum.  (Dyson introduced him by saying, "Danny Hillis
founded Thinking Machines some years ago with the goal of creating a
computer that could be proud of him and his people.")

Hillis summarized his sorting-algorithm evolution results:

  "As it turns out, it's not the best 16-element sorter in
  the world.  If I had done this in 1968 this would be the
  best program for sorting.  But in 1969 somebody found one
  that requires only 60 lines of code instead of 61.  So it's
  not the best sorting program in the world, but it's a
  pretty good one and was produced entirely by this automatic
  process."


-- 
John Ciccarelli
Plexus Software, 5200 Great America Pkwy, Suite 200, Santa Clara CA 95054
email: ...sun!plx!johnc,  voice: 408-982-4842,  fax: 408-727-4864

abbott@aerospace.aero.org (Russell J. Abbott) (07/10/90)

In article <2421@plx.UUCP> johnc@plx.UUCP (John C.) writes:
> ...
> [Danny] Hillis summarized his sorting-algorithm evolution results:
>
>  "As it turns out, it's not the best 16-element sorter in
>  the world.  If I had done this in 1968 this would be the
>  best program for sorting.  .  [It] was produced entirely by 
>  this automatic process."

Anyone have any technical references to any published material on this
or any of the other genetic algorithm program-generation stuff?
Thanks.