Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ukma!husc6!cmcl2!adm!broome From: broome@adm.BRL.MIL (Paul Broome ) Newsgroups: comp.lang.prolog Subject: Re: Naive Reverse Message-ID: <18957@adm.BRL.MIL> Date: 5 Apr 89 03:34:07 GMT References: <1989Apr3.203445.11749@cs.rochester.edu> <10073@megaron.arizona.edu> Reply-To: broome@brl.arpa (Paul Broome (SECAD/CTAB) ) Organization: Ballistic Research Lab (BRL), APG, MD. Lines: 25 Disclaimer: Just my opinions In article <10073@megaron.arizona.edu> debray@arizona.edu (Saumya K. Debray) writes: :> From: Brad Miller :> 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 don't know that it's done, but I'd say it's even proper for a compiler to transform naive reverse into its more efficient cousin. If it implements the general unfold/fold technique it's just good optimization. But that changes the complexity of the computation and defeats the purpose of the benchmark. The two goals, optimization and benchmarking, clash. > I don't understand how using Prolog as a test bed for algorithms has > something to do with benchmarks. The graph (map) coloring problem, on the other hand, is a member of the class of problems for which no deterministic polynomial time algorithm is known; it seems to _require_ search. So whatever tricks the compiler/programmer does would be welcomed as a contribution toward an important problem instead of as a defeat of the benchmark. Paul