home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / lisp / lispnews / text0339.txt < prev    next >
Encoding:
Text File  |  1985-11-10  |  4.9 KB  |  98 lines
  1.  
  2. Please, please, please stop trying to compare the performance of Lisp and
  3. Prolog by considering micro-benchmarks!  Even in languages that are
  4. essentially "the same" (from my perspective as a semanticist/language
  5. designer or from the perspective of a Prolog programmer, FORTRAN, Pascal,
  6. Modula 2, and Ada are all the same); such benchmarks are imperfect guides.
  7. When comparing Lisp and Prolog, where the programs one might write to do a
  8. particular problem might be radically different in strategy, anything that
  9. compares the performance of tiny programs conveys almost no useful
  10. information.
  11.  
  12. Please, please, please, PLEASE don't try to compare Prolog with Lisp (etc.)
  13. using LIPS as a part of the measure! In comparing Prolog implementations, I
  14. suppose LIPS might be of some interest, but when comparing Lisp with Prolog,
  15. they don't help at all. The reason is simple: if Lisp is not suited for
  16. doing logical inferences (in the Prolog sense) quickly, then the good Lisp
  17. programmer simply does not formulate his solution using logical inferences.
  18. (Patient: Doctor! Doctor! It hurts when I do this. Doctor: Well, then don't
  19. do that.) It's like saying that my APL implementation, which uses lazy
  20. evaluation and a bit of cleverness to compute
  21.  
  22.     +/ ,((iota n) o.= iota n) x A +.x B
  23.  
  24. (the trace of the matrix product of nxn matrices A and B, I think) in time
  25. O(n^2) instead of O(n^3), is "faster" than my FORTRAN implementation, which
  26. requires time O(n^3) to do a direct transcription of this algorithm
  27. (actually forming the full matrix product).  
  28.  
  29. I think it wrong to say
  30.  
  31.    "To do [deduction, searching, pattern matching and other AI-stuff] in
  32.     Franzlisp you must write Lisp functions and suffer the loss in speed
  33.     associated with simulating functionality in a high-level language."
  34.  
  35. because one DOESN'T use simulation if one wants speed, but instead goes
  36. after an entirely different kind of solution (I won't argue that this
  37. solution is "just as easy" as the Prolog solution; there are certainly many
  38. instances in which Prolog solutions are simpler, and I haven't the foggiest
  39. notion what the story is for large systems.)  
  40.  
  41.     * * *
  42.  
  43. Finally, a question.  I was struck by Sanjai Narain's  comment:
  44.  
  45.     "However, in C-Prolog, you can do also do deduction, searching, 
  46.      pattern matching and a lot of other AI-stuff at the same speed."
  47.  
  48. I notice that the Prolog digest is full of interesting puzzles whose
  49. solution involves search. But are these representative? I think pattern
  50. matching is certainly a big part of any Prolog program, but do deduction and
  51. searching really form a big part of actual Prolog applications in practice?
  52.  
  53. I recall an article by Drew McDermott called the "The Prolog Phenonmenon"
  54. that appeared (I think) in SIGArt at some point, maybe July '82. He asked
  55. why it was that Prolog had not died out, as had PLANNER, which also
  56. purported to support searching et al. He said some things on what he liked
  57. and disliked about Prolog, and then made the following comment (emphasis
  58. mine):
  59.  
  60.     "The Europeans went in a different direction [from the Americans
  61.      in reaction to the problems of PLANNER-like languages].  What
  62.      they liked best about logic was its variable-binding machinery.
  63.      Their attitude towards backtracking has been simply that it is a
  64.      programmer's duty to remember that his program will be executed
  65.      backward as well as forward, that his programs must correct bad
  66.      guesses as well as exploit good ones.  If the backwards
  67.      execution blows up, he must debug his program, not rewrite the
  68.      interpreter [the American approach], just as with more prosaic
  69.      kinds of infinite loops.  Once this burden was shifted away
  70.      from the language implementer and onto the programmer, the
  71.      logical [!] next step was to freeze the interpreter design
  72.      and make it as efficient as possible.  THE RESULT IS A 
  73.      PROGRAMMING LANGUAGE, NOT A PROBLEM SOLVER OR THEOREM PROVER;
  74.      it doesn't compete with NOAH, but with Lisp.  And it's my
  75.      impression that it competes pretty well.
  76.      
  77.          "The effect is to reverse the usual images of the American 
  78.      and European computer scientists.  In this case, the Americans
  79.      have pursued impractical theoretical studies, while the
  80.      Europeans have bummed the hell out of a hack."
  81.  
  82. (By "backward execution," he is referring to backtracking, I believe). To
  83. put this another way, one doesn't use Prolog's backtracking to do AI-style
  84. (i.e., very large) search, but rather to do very local and carefully-
  85. controlled "search," in the sense of "search this list (tree, ....) for an
  86. element equal to this one" or "try all permutations of this tiny set for one
  87. that satisfies P." Likewise, one doesn't use it to do what an AI
  88. investigator would call "deduction." One CAN convince the Prolog machinery
  89. to do more general AI-style searching efficiently, but only at the expense
  90. of vastly obscuring the original clear, simple, declarative form of the
  91. program.
  92.  
  93. Not being a real Prolog hacker (yet) I don't really know how accurate this
  94. view is, and would appreciate some reaction (preferably semi-quantitative).
  95.  
  96.  
  97.  
  98.