arun@mandrill (Arun Lakhotia) (05/06/88)
Some weeks (may be months) back, an article by Micha Meier had some comments on repeat-fail loop vs tail-recursive loops, including: > There is no reasonable argument to force people to use > tail-recursive loops instead of repeat-fail loops; which led Saumya Debray to write: > There may or may not be arguments to *force* anyone to avoid failure- > driven loops, but there are a couple of reasons one might want to avoid > them anyway: Meier's argument in favor of failure-driven loop was related to efficiency issues. Debray's argument against it was that it is trickier to write "correct" failure driven loop, supporting his argument by an incorrect translation of a tail-recursive loop to a failure-driven one. Their arguments hint that, forgetting efficiency, one type of loop can be transformed to other. I believe this can only be true for a restricted class of programs, or is there a general "transformation" scheme from one to another (without any restriction). Could someone pass me pointers to literature that deal with transformations in either directions, and/or give the characteristics of programs that can be transformed in either directions. In particular I am curious about, Debray's comment: >(2) It's not too hard to automate the transformation from tail-recursive > loops to failure-driven loops (with a little guidance from the user, > in the form of simple compiler directives), especially for the usual > case of deterministic loops. Intuitively speaking: At the termination of a failure-driven loop, variables bindings performed during the execution of a failure-driven loop, are eventually lost (due to failures). However, those done in a tail-recursive loop remain, if the loop terminates successfully - deterministic or not. It would be nice, thus, to know how tail-recursive loops can be transformed to failure-driven loops, *** without using any side-effects ***. Arun
debray@arizona.edu (Saumya Debray) (05/07/88)
In article <2467@mandrill.CWRU.Edu>, arun@mandrill (Arun Lakhotia) writes: > In particular I am curious about, Debray's comment: > > It's not too hard to automate the transformation from tail-recursive > > loops to failure-driven loops ... > > Intuitively speaking: At the termination of a failure-driven loop, > variables bindings performed during the execution of a failure-driven > loop, are eventually lost (due to failures). However, those done in a > tail-recursive loop remain, if the loop terminates successfully - > deterministic or not. It would be nice, thus, to know how > tail-recursive loops can be transformed to failure-driven loops, > *** without using any side-effects ***. I don't know of any transformation of this sort that, in the general case, doesn't use side effects _somewhere_. The point is that the user's code is tail recursive, and hence (hopefully) free of side effects. When this is transformed to a failure-driven loop, side effects are introduced, precisely for the reason you mentioned: for saving and restoring argument values. But this is transparent to people who're trying to read and/or understand the program. References: - S. K. Debray, "Program Transformations for Failure Driven Space Reclamation in Prolog", TR 85/32, Dept of Computer Science, SUNY at Stony Brook, Dec 1985. - S. K. Debray and D. S. Warren, "Towards Banishing the Cut from Prolog", manuscript, 1987. -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: {allegra, cmcl2, ihnp4} !arizona!debray