Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!rochester!daemon
From: @DOUGHNUT.CS.ROCHESTER.EDU:miller@CS.ROCHESTER.EDU
Newsgroups: comp.lang.prolog
Subject: Re: Naive Reverse
Message-ID: <1989Apr3.203445.11749@cs.rochester.edu>
Date: 4 Apr 89 00:34:45 GMT
Organization: U of Rochester, CS Dept, Rochester, NY
Lines: 31

From: Brad Miller <miller@CS.ROCHESTER.EDU>

    Date: 3 Apr 89 00:48:56 GMT
    From: broome@adm.BRL.MIL (Paul Broome )

    Sorry, my article was terribly terse and not really about benchmarks. I had in
    mind using the flexibility of Prolog to explore different algorithms for
    NP-complete problems. In particular, replacing generate and test methods with
    those that test (or constrain) while generating.   There's an example in CHIP
    (Constraint Handling in Prolog (Dincbas, LP'88)) where these methods beat
    existing ones in Fortran. Are there others?  

I don't understand how using Prolog as a test bed for algorithms has
something to do with benchmarks.

I certainly concur that naive reverse only excercises the unifier and
procedure call; I think a better benchmark of logic programming systems
would include something that required backtracking, at least in the naive
case. The benchmark would then examine the strategy of the logic system to
best implement search for a particular solution, or search for all
solutions. The problem with too general a benchmark, however, is that it
won't allow you to isolate exactly what you are testing.

I'd be interested if anyone has an idea for a benchmark that would, for
example, do well in a system that does intelligent backtracking and poor in
a system that does naive, but doesn't otherwise stress the sorts of things
naive reverse does, i.e. unification and procedure call.

----
Brad Miller		U. Rochester Comp Sci Dept.
miller@cs.rochester.edu {...allegra!rochester!miller}