home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / programm / 3372 < prev    next >
Encoding:
Text File  |  1992-12-30  |  1.4 KB  |  38 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!rpi!batcomputer!cornell!karr
  3. From: karr@cs.cornell.edu (David Karr)
  4. Subject: Re: Programming by Description of Output...
  5. Message-ID: <1992Dec30.174004.4168@cs.cornell.edu>
  6. Organization: Cornell Univ. CS Dept, Ithaca NY 14853
  7. References: <C01yxr.BGF@phage.cshl.org>
  8. Date: Wed, 30 Dec 1992 17:40:04 GMT
  9. Lines: 27
  10.  
  11. In article <C01yxr.BGF@phage.cshl.org> boutell@isis.cshl.org (Tom Boutell) writes:
  12. >Initial state:
  13. >Array A[] contains n whole numbers. 
  14. >Final state:
  15. >Array B[] contains n whole numbers such that each element of
  16. >A[] appears in B[] and for all i such that 1<=i<n, B[i]<B[i+1].
  17. >
  18. >How might the problem of calculating B[] (a sorted version of
  19. >A[]) be solved in a general fashion, absent a known
  20. >method of sorting?
  21.  
  22. This sounds like automatic programming, which is an old idea.
  23. Frederick P. Brooks mentioned it in an article a couple of years ago,
  24. entitled (I think) "No Silver Bullet."
  25.  
  26. How much easier is it to specify a program by predicates on its input
  27. and output rather than by an algorithm?  I contend it's not as easy
  28. as one might hope.  For example, is the following legal I/O for your
  29. specification:
  30.  
  31. A[] (input):   3 2 1 3 2 1 3 2 1
  32. B[] (output):  1 2 3 3 3 3 3 3 3
  33.  
  34. Each element of A[] appears in B[], but not with the same count of 
  35. repetitions.  Is this what you intended?
  36.  
  37. -- David Karr (karr@cs.cornell.edu)
  38.