[q-lang-users] Matching with special constructors

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

Hi all,

there is yet another issue related to streams and other lazy data 
structures in Q that I'd still like to resolve in the 7.1 release. It 
would be nice to discuss this here on the list because it affects 
certain aspects of pattern matching in a non-backward compatible way, 
and maybe there are some other solutions for the issue that I haven't 
stumbled upon yet.

The problem has been brought up by Yann Orlarey who noticed the 
following usability issue with lazy data structures in Q. (I'm taking 
streams here as an example; note that I use the new syntactic sugar for 
streams understood by the 7.1 version of the interpreter.)

For the sake of a concrete example, suppose we want to define a function 
which "deinterleaves" a list by replacing pairs of successive list 
elements with a tuple. For instance:

==> deinterleave [1..10]
[(1,2),(3,4),(5,6),(7,8),(9,10)]

This operation can easily be defined on lists as follows:

deinterleave []		= [];
deinterleave [X,Y|Xs]	= [(X,Y)|deinterleave Xs];

Now let's consider the literal translation of this definition to streams:

deinterleave {}		= {};
deinterleave {X,Y|Xs}	= {(X,Y)|deinterleave Xs};

Let's try this with the infinite stream of all positive integers:

==> {1..}
{1|iterate (+1) ((+1) 1)}

==> deinterleave {1..}
deinterleave {1|iterate (+1) ((+1) 1)}

Well, this doesn't work as expected because of the suspended tail 
iterate (+1) ((+1) 1) of the stream, which doesn't match {Y|Xs} so the 
second equation cannot be applied before the tail is evaluated.

While the above result is consistent with the way that special forms 
currently work in Q, I'd really like Q to do "the right thing" here. 
With the current interpreter, you're forced to write something like the 
following to force evaluation of the stream's tail:

deinterleave {X|Xs}	= {(X,Y)|deinterleave Ys} where {Y|Ys} = Xs;

Which is rather awkward. I agree with Yann that the right thing here is 
that the original definition should "just work" as is. The only 
reasonable way I see to make this work is to interleave pattern matching 
with evaluation. Specifically, the pattern matcher, when trying to match 
a pattern inside a suspended argument, should evaluate that argument 
recursively before proceeding. AFAICT, that's also the way that this 
situation would be handled in other languages which provide pattern 
matching on lazy data structures.

Of course this changes the way that special forms work, so it will not 
be backward-compatible. I still think that I should do this change. What 
do you think? Any other solution approaches? Any other opinions on what 
would be "the right thing" here?

Cheers,
Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag