About how to initialize in LOOP

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

Hi,

[I'v been much more involved with specifications than actual code in recent years.
 And it shows...]

clisp generates almost perfect code for WITH and AND WITH clauses. Witness:
(macroexpand-1'(loop with (a b) = (foo) and (nil c d) = (bar)))
 (BLOCK NIL
  (LET ((#:PATTERN-4434 NIL))
   (LET ((A (CAR (SETQ #:PATTERN-4434 (FOO))))       (B (CAR (CDR #:PATTERN-4434)))
         (C (CAR (SETQ #:PATTERN-4434 (CDR (BAR))))) (D (CAR (CDR #:PATTERN-4434)))) #)))

Note how thanks to LET, all named variables a b c d are evaluated in a context that
may refer to outer bindings of these variables. Hence (loop WITH a = (foo a) ...)
works as one would expect in Common Lisp (or any LISP with LET).

What I propose for LOOP in clisp is to apply the exact same scoping rules that govern
WITH (possibly joined by AND) to named variables in FOR clauses.
That will make (LOOP FOR vars ON vars ...) work.

So let's look at FOR clauses.
I call init forms all those that are to be executed *once* before iteration begins,
in order to supply initial values or limits valid across the whole iteration.

FOR # IN init-form BY init-form
FOR # ON init-form BY init-form
FOR # ACROSS init-form
FOR # BEING EACH/THE HASH-KEYs IN/OF init-form
FOR # BEING EACH/THE [PRESENT/EXTERNAL-]SYMBOLs IN/OF init-form
FOR # BY init-form UPTO/BELOW init-form FROM init-form
REPEAT init-form

Note that the repeatedly evaluated form in:
FOR # = form
is *not* an init-form. Is this obvious to everybody?

There's one final case that needs close attention:
FOR # = arguably-init-form THEN later
Here one can argue about the context in which to evaluate the form that provides the
value in the first iteration. Half of the following text deals with that exception.


Proposal: FOR-AS-EQUALS-THEN-HAS-INIT-FORM
Consider for-as-equals-then as
FOR # = init-form THEN form
i.e. apply aforementioned handling about variable scoping and init forms.

Benefits:
 - Named variables are immediately bound, hence values are readily available in every
    subsequent clause as well as INITIALLY clauses.
 - left-to-right evaluation across all init-forms is globally preserved.
 - Easy to grasp and to explain.
 - Implements ANSI issue 222 (which didn't reach consensus).
   http://clhs.lisp.se/Issues/iss222_w.htm

However, this proposal appears incompatible with CLHS 6.1.1.4: "form1 and form2 in
for-as-equals-then form include the lexical environment of all loop variables."

Sad, very sad. They should have distinguished for-as-equals-then and for-as-equals.
As the discussion around issue 222 shows, the committee did not reach a consensus, to
the texts were not changed. The ancient MIT LOOP implements this behaviour.

We can consider implementing issue 222 for the sake of clarity and dependability. With it,
the lexical environment of init-forms becomes as clear as in DO/DO*/DOLIST.


Proposal: FOR-AS-EQUALS-FIRST-THEN-LATER
Consider for-as-equals-then as
FOR # = form1 THEN form2

Because per CLHS 6.1.1.4 (quoted above), first-iteration need be evaluated in an
environment including all loop variables, the implementor of clisp's current loop
IMHO wrongly concluded that all following FOR clauses (here including those joined by
AND) must be evaluated there as well, to respect left to right evaluation order
requirements, causing known bugs and scoping rules very hard to explain or even
understand, as scoping now depends on former clauses.

Instead, this proposal follow CLHS by the letter to "initialize the variables [...]  by
setting it to the result of evaluating form1 on the first iteration, then ..."
-- Initialize, not bind! I.e. bind to NIL, later initialize to form1.

That definition can work, considering that LOOP users need be aware of code motion
anyway -- Think how (LOOP INITIALLY (princ 2) WITH a = (princ 1) RETURN a) prints 12
(can anybody reveal an implementation that produces another output?).

In effect, it will be very similar to for-as-in-list, for-as-across or for-as-hash:
 - The named variables need default bindings when declared;
 - It is only upon entering iteration that actual values will be supplied.

(loop for a = (princ 1) then b for b below (princ 2) do (princ (list a b)))
would print 21 by that proposal.

Benefits are:
 - The lexical environment requirement in CLHS 6.1.1.4 is obeyed to the letter.

One can argue that this rule does not make much sense without *additional* rules about
values of variables within that environment, i.e. to what values have other named loop
variables been initialized? Have INITIALLY clauses been evaluated already (see below
FOR-AS-EQUALS-THEN[-VERY]-LATE)?

>From an implementation POV, one may try hard to avoid an extra control variable
"is-first-iteration" by initializing before entering the loop (as in INITIALLY) and
stepping at the end of each iteration. However, that interferes with observable
values in FINALLY clauses, I'll not talk about that now.


Proposal: FOR-AS-EQUALS-THEN-EARLY
In for-as-equals-then, initialize the variables prior to any INITIALLY.
(yet still in full lexical scope of all loop variables in the loop prologue).

Benefits:
- Named variables are ready for use within INITIALLY.
- which distinguishes it from for-as-equals without THEN, so the user has the choice.


Proposal: FOR-AS-EQUALS-THEN-LATE
In for-as-equals-then, initialize the variables just upon entering the loop
body. INITIALLY clauses will only see default values.

Benefits:
- Very close to for-as-equal without then, where I don't plan at all to duplicate the
  step form in the loop prologue and the loop body.

Disadvantages:
- Precisely that it's late, so INITIALLY only ever sees default values.


Proposal: FOR-AS-EQUALS-THEN-VERY-LATE
In for-as-equals-then, initialize the variables within the loop body, after
evaluating the termination tests of preceding FOR-AS clauses.

clisp did/does this.
(loop for vars on vars for x = (error) then 2 return vars) would not error out.

Benefits:
- Obeys the letter of CLHS: "setting it ... on the first iteration".

Disadvantages:
- INITIALLY only ever sees default values.
- Even FINALLY may only see the default, not form1.
  (And you haven't even seen my proposals about the loop body :-)


Proposal: FOR-AS-INITIALLY-INTERLEAVE-LET
The LET forms resulting from FOR-AS initforms and WITH clauses could alternate
easily. That would make it trivial to globally respect left to right evaluation across
FOR-AS, WITH and even INITIALLY clauses.

This is not strictly conforming to CLtL2 or CLHS. They require INITIALLY to lie in the
loop prologue, which is inside the TAGBODY, hence after all LET forms, instead of amid
LET forms.

Benefits:
- Global left to right evaluation order between INITIALLY, WITH and FOR-AS initforms
- Outer variables are still accessible to early WITH clauses
- Easy to explain (yet different from CLtL2 & ANSI-CL)

Disadvantage
 - Not the letter of CLtL2 or CLHS.
 - Disallows LOOP-FINISH within INITIALLY, as the (GO epilogue) tag is not visible.
   But if you need to exit that early, why not use (RETURN-FROM named x)?


Proposal: FOR-AS-INITIALLY-GROUP-PROLOGUE
Group all INITIALLY clauses in the prologue, following all variable initializations.

Benefits:
- Values of driver variables readily accessible in INITIALLY
- Easy to explain (after grasping code movement)

Disadvantage:
- Code movement, hence no global left to right evaluation order between INITIALLY and FOR-AS/WITH initforms
Do you interpret ANSI-CL to expect a global order of evaluation across INITIALLY and FOR/AS-WITH clauses?


Proposal: FOR-AS-INITIALLY-INTERLEAVE-PROLOGUE
Use dummy LET bindings, assign variables later in the prologue, which enables an
interleaving with INITIALLY clauses, hence benefitting left to right evaluation.

This is somehow what clisp's LOOP currently does.

Benefits:
- Global left to right evaluation order between INITIALLY and FOR-AS/WITH initforms

Disadvantages:
- LOOP for VARS on VARS won't work (without further tricks, e.g. see FLET below).
- INITIALLY evaluates in an environment including all variables, yet values are not
  yet available, depending on clause order, so it's somehow unreliable.


Proposal: FOR-AS-EQUALS-THEN-INTERLEAVE
Interleave the initialization of for-as-equals-then variables with INITIALLY forms.

Benefits:
- left to right evaluation is obeyed.

Disadvantages:
- It may appear inconsistent to obey left to right with for-as-equals-then only,
  when all other for-as forms init-forms are evaluated and bindings were established
  long before any INITIALLY.


Proposal: FOR-AS-EQUALS-THEN-FLET-FOR-SCOPE
Maintain the complexity in clisp's current loop, and fix some scoping bugs by adding
even more complexity. FLET can be used to evaluate init-forms in an outer scope not
comprising all loop variables.

(LOOP FOR a = (princ 1) FOR vars ON (princ vars) RETURN (list a b))
would expand to something containing
(let ((A nil))
  (flet ((#:on-init () (princ VARS)))
    (let ((VARS nil))
      (tagbody ... (setq A (princ 1)) (setq VARS (#:on-init)) ...))))

Benefits:
 - At least the scoping rules become explainable.
 - Visible order of evaluation is obeyed.

Disadvantage:
 - Poor performance, likely needs closure.

Proposal: FOR-AS-PROLOGUE-FIX
clisp's current loop contains complicated logic in an attempt to satisfy requirements
on lexical environments, global left to right evaluation, and optimization ideas
(binding with actual values is faster than producing dummy bindings and initializing
later).  It uses LET bindings first, then degrades to (P)SETQ inside TAGBODY.
Fix that logic not to degrade in unexpected (and unwarranted) cases.

Benefits:
 - Visible order of evaluation is globally obeyed.

Disadvantages:
 - (loop FOR x = # THEN # FOR vars ON vars ...) becomes unable to satisfy user expectations, e.g. bug #375;
   (loop FOR vars ON vars FOR x = # THEN # ...) would work as expected(!).
 - initforms sometimes evaluated in an environment including all variables, sometimes
   not. How to document and explain that to users?


Proposal: STATUS-QUO
Live with bug #667 and bug #375 and a few others I've not yet written about.


What proposal to choose?

In a 2005 posting to comp.lang.lisp, Kent M. Pitman wrote:
"And there are places like LOOP where people disagree in what I'd bet is
a useless dispute because I think LOOP, while complicated, is not so
complicated that we couldn't force implementations to agree _enough_
that the ability to define loop paths could be portably achieved without
infringing the part of LOOP that should _not_ be exposed, which is what
is the right and most efficient expansion for any given implementation in
order to benchmark well.  The more you try to pin down that latter part,
the more you just require Common Lisp to be slow.  Some parts are
meant to be kept abstract."

So the intension seems to be to make LOOP fast by not overspecifying it.  That
pretty much rules out the overhead of the FLET trick IMHO.  Does it imply that
the few requirements that ANSI-CL imposes upon LOOP become even more important
to obey strictly?

| Case \ Proposal       | 1:INIT-FORM | 2:FIRST      | 3:FLET  | 4:QUO       |
|-----------------------+-------------+--------------+---------+-------------|
| vars on vars          | yes         | yes          | yes     | no          |
| form1 in lex. env.    | no          | yes          | yes     | yes         |
| left to right         | strict      | except first | strict  | strict      |
| ready in initially    | yes         | yes          | yes     | interleaved |
| initially interleaved | compatible  | compatible   | ?       | yes         |
| overhead              | lowest      | low          | highest | middle      |

I'm sorry this table is very incomplete. This text is so long already, and there's no TL;DR.

In case you didn't guess ;-) my vote is
   FOR-AS-EQUALS-FIRST-THEN-LATER together with
 + FOR-AS-EQUALS-THEN-EARLY ; i.e. for-as-equals-then is almost an init-form like the others
 + FOR-AS-INITIALLY-GROUP-PROLOGUE
Benefits:
 - FOR vars ON vars never sees NIL.
 - FOR a = form1 [then form2] evaluates both forms in an env. including all variables.
 - Well defined values within INITIALLY.
 - Easy enough to document
 - Shall be performant by favouring LET over additional SETQ; i.e. I'm biased
   towards performance thanks to reordering, left to right evaluation order
   across all LOOP clauses.

Regarding a future Lisp, my vote would be
   FOR-AS-EQUALS-THEN-HAS-INIT-FORM ; i.e. implement issue 222
 + FOR-AS-INITIALLY-INTERLEAVE-LET
even though that means that LOOP-FINISH is not available in INITIALLY.

If you favour global left to right evaluation order, I believe your vote will be
   FOR-AS-PROLOGUE-FIX   
 + FOR-AS-INITIALLY-INTERLEAVE-PROLOGUE
 + FOR-AS-EQUALS-THEN-INTERLEAVE
 and maybe include FOR-AS-EQUALS-THEN-VERY-LATE

Regards,
	Jörg