[iterate-devel] Re: Macroexpansion, bindings and information flow (Iterate package)

[Andreas Fuchs]

(This is the first time I've opened c.l.l in a long time, and I didn't
intend to post anything, but then... (-:)

I'm cross-posting this to the iterate-devel mailing list.

On Mon, 15 Nov 2004 10:15:35 +0100, Joerg Hoehle wrote:
> I came across J.Amsterdam's Iterate package and would like to address
> its main weakness: correct, lexical aware code expansion.
> 
> I believe in its over 10 years of existence, it's never been able to
> correctly handle this form:
>     (macrolet ((over(x) `(collect ,x)))
>       (iterate
> 	(for n in '(1 2 3))
> 	(flet ((over(x)(declare (ignore x)) (collect 2)))
> 	  (over n)))) ; would yield (2 2 2) if correct

Actually, the current version of iterate can handle that clause pretty
well (since iterate--main--1.0--patch-6, since when we pass the *env*
argument to macroexpand calls). 

What it can't handle (and what I think you meant to post, anyway) are
nested macrolet clauses, like:

     (iterate
       (macrolet ((over(x) `(collect ,x)))
       (for n in '(1 2 3))
       (flet ((over(x)(declare (ignore x)) (collect 2)))
         (over n)))) ; would yield (2 2 2) if correct

because the code walker does not know how to extend the environment with
this nested macrolet. 

> One reason is that it does not contain a code walker aware of lexical
> bindings.

Right. I think that's partly due to the fact that it's impossible to have
a macrolet (and symbol-macrolet)-aware code walker in portable CL without
reimplementing half of common lisp. (-:

> I actually wonder whether Iterate actually needs a full code walker,
> thereby duplicating functionality found in every Lisp implementation,
> or whether Iterate could be written without one, possibly by clever
> use of MACROLET and/or *MACROEXPAND-HOOK*?

An iterate that doesn't code walk could end up being more friendly to its
maintainer. Iterate in its current form relies very heavily on the code
walker, so you'd end up re-implementing most of it from scratch (probably
not such a bad thing, either (-:)

*macroexpand-hook*, now there's an idea. From the code walker, it might be
possible to put a closure in there which can expand the macrolet by
itself. That would be interesting to try out (you'd still have to create a
macro function from the macrolet's definition. hmm)

> Here's one of the problems: Iterate allows a (COLLECT x INTO var)
> clause to appear anywhere deep inside the body of (Iterate ...),
> contrary to LOOP. As a result, it's only after COLLECT has been
> encountered that Iterate knows which bindings it must create in its
> top level expansion.  Information flows from deep inside to the
> outermost level. How to do that?
> 
> E.g.
> (iterate ... (collect x into a) ... (collect ... into b) ...)
> -> `(let (a b) ... ...)
> (iterate ... no-collect-at-all ...)
> -> `(let () ...) or (progn ...)
> 
> Do you have an idea how such a COLLECT INTO macro could be written
> without duplicating a code walker?

Unfortunately, ANSI CL doesn't specify the order in which macros are
expanded, but if it did, you /might/ be able to signal conditions which
the outer *macroexpand-hook* functions could know how to treat. All this
is highly speculative, but it would be a pretty neat hack. (-:

> This seems hairy to me if one wants it to work both in interpreted
> and compiled modes, since with an interpreter, the COLLECT form may
> only be encountered upon evaluation of (COLLECT #) --really late.

Right. That's probably part of the reason why ANSI doesn't specify
macroexpand order.

> If it's not possible without a code walker, are there portable means
> to use the implementation's code walking engine? It seems a pity to me
> that something like AUGMENT-ENVIRONMENT (in CLtL2) was not
> standardized in ANSI-CL.
> Section 8.5, Environments, of CLtL2 see
> http://www.supelec.fr/docs/cltl/clm/node102.html

It seems like most implementations offer code walker support similar
to ClTl2's. While not ANSI CL, these might be your best bet.

Cheers,
-- 
Andreas Fuchs, <asf at boinkor.net>, asf at jabber.at, antifuchs