home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / programm / 3375 < prev    next >
Encoding:
Internet Message Format  |  1992-12-30  |  2.1 KB
  1. Path: sparky!uunet!pipex!bnr.co.uk!uknet!mucs!m1!bevan
  2. From: bevan@cs.man.ac.uk (Stephen J Bevan)
  3. Newsgroups: comp.programming
  4. Subject: Re: Programming by Description of Output...
  5. Message-ID: <BEVAN.92Dec31001940@panda.cs.man.ac.uk>
  6. Date: 31 Dec 92 00:19:40 GMT
  7. References: <C01yxr.BGF@phage.cshl.org> <1992Dec30.174004.4168@cs.cornell.edu>
  8.     <C036t1.KCH@phage.cshl.org>
  9. Sender: news@cs.man.ac.uk
  10. Organization: Department of Computer Science, University of Manchester
  11. Lines: 38
  12. In-reply-to: boutell@isis.cshl.org's message of 30 Dec 92 19:15:01 GMT
  13.  
  14. In article <C036t1.KCH@phage.cshl.org> boutell@isis.cshl.org (Tom Boutell) writes:
  15.    In article <1992Dec30.174004.4168@cs.cornell.edu> karr@cs.cornell.edu (David Karr) writes:
  16.    >In article <C01yxr.BGF@phage.cshl.org> boutell@isis.cshl.org (Tom Boutell) writes:
  17.    >>Initial state:
  18.    >>Array A[] contains n whole numbers... 
  19.    [deleted]
  20.    >How much easier is it to specify a program by predicates on its input
  21.    >and output rather than by an algorithm?  
  22.  
  23. I find that the spec. is usually shorter, but there are times when a
  24. particular implementation (algorithm) is shorter than the spec.
  25.  
  26.  
  27.    An excellent question. I gather Prolog programmers have discovered
  28.    it is often as much or more work than writing the algorithm, as
  29.    you point out.
  30.  
  31. Getting back to the sorting example: if the arrays are changed to
  32. lists, then a spec is :-
  33.  
  34.   sort(List, Sorted_List) :-
  35.     permutation(List, Sorted_List),
  36.     ordered(Sorted_List).
  37.  
  38. Suitable definitions of `permutation' and `ordered' are left as an
  39. excercise for the reader.
  40.  
  41. By using various transformations you can move from the spec. to a
  42. particular algorithm, say a quicksort (sic) or mergesort or you alter
  43. the spec. to ensure that the sort is stable.  Someone here did some
  44. work on automatically transforming Prolog programs (the thesis
  45. specifically covers generation of various sort routines from the above
  46. spec).  If you are interested in program transformation in general, it
  47. is worth looking at papers/books on Bird-Merteens Formalism, CIP, VDM
  48. and Z or for a more gentle introduction try _Science of Programming_
  49. by Gries.
  50.  
  51. bevan
  52.