noekel@uklirb.UUCP (07/09/87)
Hi, does anyone out there in netland know whether it is possible to write a Prolog program that (1) *generates* natural numbers in ascending order, (2) does not make use of side effects (assert, retract etc.), (3) generates the first n numbers in time O(n). The toplevel predicate should be nat(X), which is of course invoked with X uninstantiated. Any number of additional predicates are admitted. Note that the program should be self-contained, i.e. I'm not interested in programs like next_nat(X,Y) :- Y is X+1. which leave it to the responsibiliy of the calling program to "conserve" the last number generated until the time the next number is needed. Be warned that complexity can creep in through your backdoor - especially if you use many auxiliary predicates. The number of exits and redos and the number of variable renamings needed to get at the next number deep within a recursion also take time and count therefore! Alternatively I would very much appreciate a negative result - preferably in the form of a proof. Please, post your contributions to this notes group or mail to: UUCP: ...!mcvax!unido!uklirb!noekel
lhe@sics.se (Lars-Henrik Eriksson) (07/14/87)
In article <29400001@uklirb.UUCP> noekel@uklirb.UUCP writes: >does anyone out there in netland know whether it is possible to write a Prolog >program that > >(1) *generates* natural numbers in ascending order, >(2) does not make use of side effects (assert, retract etc.), >(3) generates the first n numbers in time O(n). > If you want the predicate to generate successive integers each time it is called, then it is impossible to do without side effects. Suppose the predicate foo/1 would do what you want. Then different calls foo(X) would instantiate X to different integers. In Prolog, as in any other language, this can only be done with side effects. If no side effects were involved, the program would have no way of knowing that it had been called before. In logic programming, it is conceivable that you could write a predicate foo/1 such that foo(N) holds for ANY natural number N, but some complex control information make sure that successive calls with N uninstantiated instantiates it to successive natural numbers, but I guess that is not really what you want. (It couldn't be done in Prolog anyway). Lars-Henrik Eriksson, Swedish Institute of Computer Science lhe@sics.sics.se ...mcvax!enea!sics!lhe
biep@cs.vu.nl (J. A. "Biep" Durieux) (07/16/87)
In article <1343@sics.se> lhe@sics.se (Lars-Henrik Eriksson) writes: >In article <29400001@uklirb.UUCP> noekel@uklirb.UUCP writes: >>does anyone out there in netland know whether it is possible to write a Prolog >>program that >> >>(1) *generates* natural numbers in ascending order, >>(2) does not make use of side effects (assert, retract etc.), >>(3) generates the first n numbers in time O(n). >> > >If you want the predicate to generate successive integers each time it is >called, then it is impossible to do without side effects. I believe what he wants is something like: numbers(X) :- count(0, X). ; or whatever number you want to start with count(X, X). count(X, Y) :- Z = X+1, count(Z, Y). In this way, *on backtracking*, all natural numbers are generated. (Thanks to Hans Weigand, who once helped me out of a similar problem). I think this program meets the three specified criteria, except perhaps that due to interpreter inefficiencies time might exceed O(n). -- Biep. (biep@cs.vu.nl via mcvax) Net weight is determined by considering contents only. (From: How to become an important usenet person)