Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ncar!noao!arizona!debray
From: debray@arizona.edu (Saumya K. Debray)
Newsgroups: comp.lang.prolog
Subject: Re: Naive Reverse
Message-ID: <10073@megaron.arizona.edu>
Date: 4 Apr 89 15:23:27 GMT
References: <1989Apr3.203445.11749@cs.rochester.edu>
Organization: U of Arizona CS Dept, Tucson
Lines: 34

> From: Brad Miller <miller@CS.ROCHESTER.EDU>
>
> I certainly concur that naive reverse only excercises the unifier and
> procedure call;

On modern Prolog systems, it doesn't even do this too well, since
it can be compiled into very compact code with much of the procedure
calling and unification optimized away.  I've heard stories that one
commercial Prolog vendor[*] managed to compile append/3 into
sufficiently few machine instructions that code for the whole
procedure fit into the instruction cache of the 68020, giving huge
LIPS numbers.  A competing vendor[*] apparently felt compelled to
introduce an "append" instruction in their interpreter after this,
to match these LIPS figures.

[*] I have friends at both places, and financial interests in neither.
    Hence (and also because aforementioned friends are quite likely to
    referee my papers in the future), both these systems will go unnamed.

> 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 ...

I'd think any "search"-type program with a poorly chosen order of
goals would do (e.g. map coloring).  The problem with most intelligent
backtracking schemes  is that because of the runtime overhead they incur,
they end up doing well on badly written programs but poorly on well
written ones.

-- 
Saumya Debray		CS Department, University of Arizona, Tucson

     internet:   debray@arizona.edu
     uucp:       arizona!debray