Re: [q-lang-users] "listof" surprises

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

Marco Maggesi wrote:
>> You could even define yourself a special form 'let'
>> as follows:
>>
>> special let B X;
>> let (A=Z) X = case Z (A,X;);
> 
> I like this very much!  Thanks.

Thought so. :) Q's abilities to define "meta" or "macro" functions like
this make the language much more powerful than other modern FPLs.

But actually this isn't the end of the story yet. For simple cases the
above definition of 'let' is already good enough, but there is an
improved definition which is slightly more involved but also properly
treats the corner cases. In the following I consider the 'let' version
using 'lambda':

special let B X;
let (A=Z) X = (\A.X) Z;

The above version works nicely even in nested expressions as long as
there are no repeated variables. For instance:

==> let (X=1) $ let (Y=X+1) (Y,Y+1)
(2,3)

But note what happens, e.g., if a nested 'let' attempts to bind a
variable which is already bound by an outer 'let' expression:

==> let (X=1) $ let (X=X+1) (X,X+1)
(\1 . (1,1+1)) 2

Ugh. This happens because the outer 'let' gets expanded first and
'lambda' replaces *all* instances of X in the nested 'let' expression.
The same misbehaviour also arises if 'let' is nested inside other
"lambda-binding" expressions, like 'listof':

==> [let (X=X+1) (X,X+1) : X in [1..2]]
[(\1 . (1,1+1)) 2,(\2 . (2,2+1)) 3]

Usually this is not what you want. Instead you want a variable to be
bound by the innermost lambda-binding expression. This can be achieved
by making 'let' known to 'lambda' as a lambda-binding expression which
needs to be expanded recursively. This involves two steps:

- Make 'let' expressions a subtype of the predefined 'Lambda' type.

- In addition to the definition of 'let' itself, also give an equation
for the 'lambdax' function which defines how 'lambda' should expand
nested 'let' expressions.

This machinery is supported by the builtin 'lambda' which will
automagically apply 'lambdax' to all members of subtypes of 'Lambda' in
the lambda body. 'lambdax' is supposed to return a quoted expression
which is substituted for the original lambda-binding expression in the
lambda body.

So here is an overhauled definition which follows these guidelines:

type Let : Lambda = special let B X;
let (A=Z) X = (\A.X) Z;
lambdax (let (A=Z) X) = '((\A.X) Z);

(Other special forms involving 'lambda', like list comprehensions, are
defined in the same fashion, see cond.q.)

This now works as expected:

==> let (X=1) $ let (X=X+1) (X,X+1)
(2,3)

==> [let (X=X+1) (X,X+1) : X in [1..2]]
[(2,3),(3,4)]

Well, at least it works with latest cvs version of the interpreter. ;-)

Unfortunately, the above won't work yet if you define 'let' in terms of
'case', because 'case' expressions aren't an instance of 'Lambda' right
now. Should they be? Probably. Another item for the Q 7.7 TODO list...

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