🚀 go-pugleaf

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