A few weeks ago I posted a question about random reduction order. I have got several answers and have collected them all here. (As far as I can tell they have not been on the mailing list before.) My question was apparently ambiguous - explaining some of the diversity of the answers. What I meant with random reduction order was a reduction order where at each reduction step a redex is picked at random. I guess that is not very clear either, but anyway... Of course the effectiviness of it would be another question altogether. Sverker Nilsson <[EMAIL PROTECTED]> wrote the original question: > > Will a random reduction order always terminate if there is > any reduction order that will terminate? > > I am also interested in pointers into the litterature (preferrably > by FTP). > > /Sverker > > > Denis Howe <[EMAIL PROTECTED]> wrote: > > Will a random reduction order always terminate if there is any > > reduction order that will terminate? > > Surely if there exists any order which may fail to terminate then a > random order may fail to terminate (even if there also exists an order > which always terminates). Obvious, no? > > -- > Denis Howe <[EMAIL PROTECTED]> > Free On-Line Dictionary of Computing > WWW URL http://wombat.doc.ic.ac.uk/ Alastair Reid <[EMAIL PROTECTED]> wrote: > Unless you want to invoke a fairness principle, no - you could > "randomly" choose strict evaluation order and fail. > > Even if you do invoke fairness, I think the answer may be no (at > least) unless you use a very restrictive notion of "fair": > > Suppose your graph has 2 redexes: one that leads to termination > and another which increases the graph size and introduces many more > redexes. > Now you randomly choose a redex but the chance of choosing that one > good redex has gotten smaller so again you miss the good one. > > Alastair <[EMAIL PROTECTED]> wrote: > Sverker, > > > > Will a random reduction order always terminate if there is > > any reduction order that will terminate? > > No. Consider that a random order will be `bounded'(*) by normal-order > and applicative-order reduction. There are a number of cases where > the former would succeed but the latter will fail. Therefore, there > is a chance that the random scheme will also fail to terminate. > > Cheers, > > Andy. > > (*) this is fairly woolly, but I'm trying to say that the random order > will result in a reduction sequence somewhere in between the two other > methods. > > [EMAIL PROTECTED] (George McA. Beshers) wrote: > On Sep 27, 6:53pm, Sverker Nilsson wrote: > > Subject: random reduction order? > > Will a random reduction order always terminate if there is > > any reduction order that will terminate? > > Theory or Practice? > > I would think the answer would be yes given some fairness > criteria (so that the terminating evaluation order is > guaranteed to make progress), although I have never seen > a proof. > > As a practical matter you would need to be wary of > evaluating under a guard, e.g., executing a division > by 0 which would not have been evaluated in either > eager or lazy evaluation because an if. > > > > I am also interested in pointers into the litterature (preferrably > > by FTP). > > You might look for information associated with the Id > language or parallel Haskell, both at mit. > > > > > George Beshers > [EMAIL PROTECTED] > > Hibbitt, Karlsson, & Sorensen, inc. > 1080 Main St. Pawtucket, RI 02860 > Tel (401) 727-4200; Fax: (401) 727-4208 Arvind <[EMAIL PROTECTED]> wrote: > A reduction strategy that chooses redexes in random order will > be normalizing (with respect to some notion of an answer, e.g., > Weak Head Normal Form or Normal Form) if it is fair, i.e., it does > not neglect a redex forever. A standard technique to make a > reduction fair is to underline redexes in a term, and then to do > all the underlined redexes before doing any newly created ones. > > A lot has been written on this topic in the Term Rewriting literature. > Jan-Wilem Klop's work is a good starting point. > > Arvind [EMAIL PROTECTED] (Kevin Hammond) wrote: > >Will a random reduction order always terminate if there is > >any reduction order that will terminate? > > Intuitively no. Consider a term with two possible reduction sequences, one > of which > terminates, one of which doesn't. There is a 50% probability that the > randomly chosen > sequence will terminate! > > f x = (error "Boom",x) > > main = print (f 1) > > If the system is either strongly normalising, or confluent, then any needed > reduction can be > however be chosen at random (error is not a needed redex in this sense, > since it is not > necessary to reduce it in order to reduce the initial term). > > >I am also interested in pointers into the litterature (preferrably > >by FTP). > > Start with Barendregt's book (if you haven't already), and consider work on > term/graph rewrite > systems (e.g. by Klop, Sleep, Kennaway, Plasmeijer), which generalises the > lambda-calculus > notion of reduction. Richard Kennaway ([EMAIL PROTECTED]) is a good person > to ask about reduction orders and can probably give you FTP pointers. > > Warning, this can be heavy going! > > Regards, > Kevin >
