q-lang-users

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

[ww <wwa...@ea...>]

Hi,

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?

I'm running QPad version 5.0.

Thanks,

Walt
 
My Example;

randoml N:Int  = randoml [] N;

randoml L:List N:Int = randoml (push L random) (N-1) if N>0;
                               = L otherwise;

% C:\Documents and Settings\ww\My Documents\randoml.q

==> def A=randoml 10

==> def B=randoml 100

==> (A=A)
true

==> stats
0 secs, 31 reductions, 41 cells

==> (B=B)
true

==> stats
0 secs, 301 reductions, 401 cells

==> version
"5.0"

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?

No, you're right, the compiler doesn't do any tail call optimization 
with (and then) or (or else) right now. Hmm, that would certainly be 
useful. This case is a little more involved than (||), I have to think 
about it ...

Albert

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

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

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

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

/me wrote:
> 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?
> 
> I thought about this problem a little more -- it's really been haunting 
> me. ;-) So here's the result of my contemplations...
> 
> [snipped]

I thought about it still some more, and finally decided that this is 
really a bug that needs to be solved. Said and done. ;-) So in cvs you 
can now find a new version of the interpreter that is fully 
tail-recursive. That is, tail calls are now optimized for builtins and 
special arguments just as for user-defined rules. Thus, e.g., (=) and 
`all' on lists now run in constant stack space, without the need to 
rewrite anything. Enjoy! :)

Albert

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

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

[ww <wwa...@ea...>]

----- Original Message -----
From: "Albert Graef" <Dr....@t-...>
To: <q-l...@li...>
Cc: <wwa...@ea...>
Sent: Sunday, February 15, 2004 4:10 PM
Subject: Re: [q-lang-users] "and then" and stack usage


> /me wrote:
> > 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?
> >
> > I thought about this problem a little more -- it's really been haunting
> > me. ;-) So here's the result of my contemplations...
> >
> > [snipped]
>
> I thought about it still some more, and finally decided that this is
> really a bug that needs to be solved. Said and done. ;-) So in cvs you
> can now find a new version of the interpreter that is fully
> tail-recursive. That is, tail calls are now optimized for builtins and
> special arguments just as for user-defined rules. Thus, e.g., (=) and
> `all' on lists now run in constant stack space, without the need to
> rewrite anything. Enjoy! :)
>
> Albert
>
> --
> Dr. Albert Gr"af
> Email:  Dr....@t-..., ag...@mu...
> WWW:    http://www.musikwissenschaft.uni-mainz.de/~ag

Thank you! What a nice surprise. I'll try the new version this
weekend.

Walt

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

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

ww wrote:
> Thank you! What a nice surprise. I'll try the new version this
> weekend.

Wait a few hours more, then Q 5.1 will be out, and you don't have to 
build it from cvs yourself. :)

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