Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!munnari!mulga!lee
From: lee@mulga.oz (Lee Naish)
Newsgroups: comp.lang.prolog
Subject: Re: Prolog riddle summary - (nf)
Message-ID: <2140@mulga.oz>
Date: Thu, 30-Jul-87 23:14:55 EDT
Article-I.D.: mulga.2140
Posted: Thu Jul 30 23:14:55 1987
Date-Received: Sun, 2-Aug-87 01:26:37 EDT
References: <29400002@uklirb.UUCP>
Reply-To: lee@mulga.UUCP (Lee Naish)
Organization: Comp Sci, Melbourne Uni, Australia
Lines: 31

In article <29400002@uklirb.UUCP> noekel@uklirb.UUCP writes:
>	nat(X) :- nat1(X,0).
>
>	nat1(X,X).
>	nat1(X,Y) :- Z is Y+1, nat1(X,Z).
>
>All my attempts were O(n**2) and the above solution was no
>exception! In fact it is a good example for the problem of nesting calls
>that I mentioned in the original posting. With each number generated there
>is one more pending call to nat1 and none of these calls are ever exited for
>good. This primarily a space problem
True, without tail recursion optimization there will be N stack frames
in use after the Nth number has been returned. ie O(N).

>It also means that with each number generated one needs one more variable
>renaming to arrive at the answer substitution in terms of the variables of
>the query, and this is a time problem.
Its true that in simple implementations there will be N copies of X around
but unless the implementation is extremely brain damaged, all the copies
will be pointing directly to the original variable, not arranged in a chain
of length N.  To get the next solution, only the top stack frame is changed.
ie. space is O(N) but time (dereferencing and manipulating the stack)
is O(1) to get the next solution and therefore O(N) to get N solutions.

>nat1 is tail-recursive and can be optimized by almost any Prolog *compiler*
Making space O(1) but the same time complexity.

Off hand, I cant think of how compilation techniques can improve
time complexity, though there is a factor of a few hardware-years.

	Lee Naish