home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / programm / 3377 < prev    next >
Encoding:
Internet Message Format  |  1992-12-31  |  2.1 KB
  1. Path: sparky!uunet!olivea!charnel!rat!usc!rpi!batcomputer!cornell!karr
  2. From: karr@cs.cornell.edu (David Karr)
  3. Newsgroups: comp.programming
  4. Subject: Re: Programming by Description of Output...
  5. Message-ID: <1992Dec31.154623.28659@cs.cornell.edu>
  6. Date: 31 Dec 92 15:46:23 GMT
  7. References: <1992Dec30.174004.4168@cs.cornell.edu> <C036t1.KCH@phage.cshl.org> <1992Dec30.233659.7290@black.ox.ac.uk>
  8. Organization: Cornell Univ. CS Dept, Ithaca NY 14853
  9. Lines: 37
  10.  
  11. In article <1992Dec30.233659.7290@black.ox.ac.uk> ke94002@black.ox.ac.uk (Daniel J Mitchell) writes:
  12. >
  13. > This method of programming is usually called 'deriving programs'
  14. >-- the original work is Edsger Dijkstra's _A Discipline of
  15. >Programming_ (Prentice-Hall, 1976), [...]
  16. >
  17. > It also can wind up deriving /very/ elegant algorithms (qv the
  18. >longest upsequence problem, covered in Gries and Morgan) for
  19. >difficult problems.
  20.  
  21. I've derived programs and the methods can indeed yield very elegant
  22. solutions.  But I think Dijkstra intended the process to at least be
  23. guided by human intelligence.  He once gave as an example the
  24. following problem:
  25.  
  26.     Two diagonally opposite corner squares have been removed
  27.     from an 8x8 chessboard.  Determine whether it is possible
  28.     to "tile" the remaining squares with 31 1x2 dominoes.
  29.  
  30. The problem can be solved by exhaustive search, but it is much
  31. better to observe that there are 32 squares of one color to be
  32. covered, while each domino can only cover one square of each color.
  33.  
  34. > As to doing it automatically, the only thing I know of is a
  35. >language called ML which reputedly is a great deal higher level
  36. >than most languages, and comes close to being able to take
  37. >specifications of the above form as code. (I think. I'm probably
  38. >wrong about that, on reflection..)
  39.  
  40. ML is a functional rather than an imperative language, but it
  41. still encodes "algorithms" in some sense.  That is, you can define
  42. a function "sort" that returns the sort of a list, or you can define a
  43. function "sorted" that tells you if a list is sorted, but you cannot
  44. just give the system the definition of "sorted" and the instructions
  45. "make this be true."
  46.  
  47. -- David Karr (karr@cs.cornell.edu)
  48.