Re: [q-lang-users] "and then" and stack usage

[<Dr....@t-...>]

ww wrote:
> I've been exploring Q recently and I've noticed that "and then" doesn't
> seem to run in constant space. From it's definition (in the docs), I was
> expecting that it could reuse the stack frame but that doesn't seem to be 
> the case. Am I missing something?

Hi, Walt,

I thought about this problem a little more -- it's really been haunting 
me. ;-) So here's the result of my contemplations...

The Q docs say that a definition is tail-recursive only if the recursive 
call is the last (i.e., outermost) call on the right-hand side of a 
rule. (If the rhs is an expression sequence X1||...||Xn then the same 
criterion is applied to the last member of the sequence.) This criterion 
is a bit more stringent than what you find, e.g., in Scheme. In 
particular, if the rhs takes the form X and then Y, then Y does *not* 
qualify as a tail call, since the application of (and then) is the 
outermost call.

If we take this definition for granted, then the problem is actually 
with the definition of (=) on lists from the prelude, which is *not* 
tail-recursive. That will have to be fixed (along with some other, 
similar definitions, like the definition of `all' and `any' in stdlib.q).

Here's another example which shows the problem and the possible 
solution; both foo and bar implement an operation like `all' which 
verifies that all list members satisfy the given predicate P):

def L1 = nums 1 10, L2 = nums 1 100;

foo P [X|Xs]	= P X and then foo P Xs;
foo P []	= true;

bar P [X|Xs]	= bar P Xs if P X;
		= false otherwise;
bar P []	= true;

==> foo (>0) L1; stats; foo (>0) L2; stats
true
0 secs, 41 reductions, 43 cells
true
0 secs, 401 reductions, 403 cells

==> bar (>0) L1; stats; bar (>0) L2; stats
true
0 secs, 31 reductions, 6 cells
true
0 secs, 301 reductions, 6 cells

Obviously, the second definition is executed in a tail-recursive fashion 
while the first one is not; this can also be seen explicitly when 
running both functions with the debugger:

==> foo (>0) L1
   0>  tailcall.q, line 4: foo (>0) [1,2,3,...]  ==>  (>0) 1 and then 
foo (>0) [2,3,4,...]
(type ? for help)
:
**  1>0  ==>  true
**  (>0) 1  ==>  true
   1>  tailcall.q, line 4: foo (>0) [2,3,4,...]  ==>  (>0) 2 and then 
foo (>0) [3,4,5,...]
:
...

==> bar (>0) L1
   0>  tailcall.q, line 7: bar (>0) [1,2,3,...]  ==>  bar (>0) 
[2,3,4,...] if (>0) 1
:
**  1>0  ==>  true
**  (>0) 1  ==>  true
   0>  tailcall.q, line 7: bar (>0) [1,2,3,...]  ==>  bar (>0) [2,3,4,...]
:
++  bar (>0) [1,2,3,...]  ==>  bar (>0) [2,3,4,...]
   0>  tailcall.q, line 7: bar (>0) [2,3,4,...]  ==>  bar (>0) 
[3,4,5,...] if (>0) 2
:
...

Of course, one could argue that Q's notion of tail-recursive definitions 
is a bit too restricted there. The question arises whenever a special 
form reduces to nothing but one of its special arguments. In this case 
the interpreter could actually carry out the reduction *before* 
evaluating the special argument; currently it's the other way round, 
following the general rule that a special argument is evaluated as soon 
as its value is required. For various technical reasons, I'd rather like 
it to stay that way, but I'm open to suggestions there.

Any comments?

Albert

-- 
Dr. Albert Gr"af
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikwissenschaft.uni-mainz.de/~ag