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

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

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*?

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?

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.

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

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

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.

*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)

  (symbol-macrolet ((paradox t))
    (macrolet ((when-symbol-macro (form &environment env)
                 (when (nth-value 1 (macroexpand-1 'paradox env))
                   form)))
      (iterate (for x in '(1 2 3))
               (when-symbol-macro
                 (collect x into paradox)))))

If Iterate binds PARADOX as a variable, then that binding hides
the symbol macro, and WHEN-SYMBOL-MACRO expands to NIL, so
Iterate shouldn't see the COLLECT clause and has no reason to
bind PARADOX.  But in that case, the symbol macro remains visible
and WHEN-SYMBOL-MACRO passes the COLLECT clause through, so
Iterate should bind PARADOX after all.

At first, I thought the binding problem could be solved by first
walking the body once with an environment that doesn't include
any accumulation variables, selecting the variables, and then
walking the body again with the resulting environment and
verifying that the same variables get selected again.  However,
this scheme does not allow a macro in the body to expand to a
form that accumulates to a gensym variable.  One could just
forbid that but I think it would feel unobvious to the
programmer.

I see the following ways to resolve the situation:

(a) Specify that any macros expanding to accumulation forms must
    not depend on whether the accumulation variables are already
    in the environment.  This does not require any change in the
    Iterate implementation.  However, I am not sure it is not
    possible to violate this requirement inadvertently.

(b) Require the programmer to list all the accumulation variables
    with an (:into a b c) form at the top of the body.  Signal an
    error if the code attempts to accumulate into any other
    variables.  This too would be incompatible with gensyms
    chosen in the body, but at least that would be obvious to the
    programmer.  On the plus side, this would allow a nested
    Iterate form to accumulate to a variable bound by the outer
    Iterate form.

(c) Deduce the accumulation variables from the body, but not by
    expanding macros.  Instead, define Iterate-specific walkers
    for all standard CL macros, and give the programmer a way to
    define walkers for her own macros.  The walkers must then
    satisfy the requirement of (a) but that is not a big problem
    because they are already specific to Iterate.  This would
    also ensure that the bindings made by

      (iterate (case t
                 (() (:collect t :into y))))

Doesn't this mean that (nth-value ...) is undefined as well?

Oops, this arguments sounds like use of macroexpand need be forbidden
inside macrolet!?!

BTW, my interpretation is opposite of yours: Iterate does not detect
'(collect into paradox) from an eagle's perspective. Instead, it
proceeds top-down to walk the code. Therefore, when when-symbol-macro
is encountered, Iterate has not yet seen the collect clause, therefore
it has not yet bound paradox as a variable. As a result, NTH-VALUE
returns T because the symbol-macro got expanded. Then only, Iterate
gets to see the collect clause, which causes it to generate a variable
binding for paradox.

As a result, the symbol-macro is shadowed. Iterate collects into a
distinct variable and returns nil (you may wish to add a
(finally (return paradox)) clause to see that).

There's some point, though: if Iterate could yield an expansion
without itself resorting to macroexpand, then when-symbol-macro would
be expanded in a environment context where the Iterate expansion would
have bound variables (via LET), causing different behaviour.

But that's little surprise, no? It all depends on what time and
environments macroexpansion occurs. I can't remember a point where CL
makes some guarantees or recommendatiosn on this.

Did I miss something?

It would be an Iterate rather different from the one we know. But it
might be worthwhile if it can then work without macroexpanding its body.

I haven't investigated whether that would be the only change from the
current Iterate though. Currently, quite a few of Iterate forms lead
to the creation of internal variables (but internal means they may not
affect macroexpansion).

t...@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:

I believe Iterate uses lexical variables because that's what's felt
efficient. a p-list of name/values would have lookup cost at
run-time. Ten years ago, that would have been reason enough not to
advertise Iterate as a good replacement for LOOP/DO etc.

However, I've never seen a documented restriction on loop variables.
E.g. in both Iterate-1.0.9 and CLISP's LOOP, this does not
work as expected:
(loop initially (setq x (list 'a 'b)) ; try and prefill x
      for i in '(1 2 3)
      collect i into x
      finally (return x))
I don't know whether this is correct (portable) code.

BTW, drop me a note if you want to test my version of Iterate. I did
nearly two dozen small changes and bugfixes to Iterate-1.0.9.