Named loop and recur-to: working patch extending loop/recur to nested loops
215 views
Skip to first unread message
Michał Marczyk
Sep 10, 2017, 2:21:04 PM9/10/17
to cloju...@googlegroups.com
Hi,
Currently loop/recur is limited to "single-layered" loops: loop forms can occur inside other loop forms, but there is no facility for "recuring to an outer loop".
A few years ago I posted a proposal to add support for nested loops to Clojure with a proof-of-concept patch to ClojureScript with syntax and semantics that I think suffice to make nested loops feel natural while remaining a natural extension of the core loop/recur model, with the same explicit tail recursion benefits:
(loop foo […] ; named loop
…
(loop […] ; intervening loop
…
(loop […] ; innermost loop
…
(recur-to foo …)))) ; recur to the named loop;
; NB. this must be in tail position
; w.r.t. *all* three loops
I have now implemented a complete patch enabling the proposed feature in Clojure (the first link is to a branch based on current master, that is, the "prepare for next development iteration" commit after 1.9.0-alpha17; the second is to the current tip of this branch for future reference):
I also opened a ticket in JIRA so as to have a place to post the above in the form of a patch file:
The remainder of this email sets out the proposal in more detail, states its key properties in a somewhat rigorous form, briefly summarizes the implementation approach and discusses certain design choices made in the patch.
Overview
========
The idea is that one could write e.g.
(let [m (two-dimensional-matrix)]
(loop iloop [i 0] ; named loop
(if (< i i-lim)
(loop [j 0] ; nested anonymous loop
(if (< j j-lim)
(do
(work)
(recur (inc j))) ; recur to the innermost loop
(recur-to iloop (inc i)))) ; recur to iloop
(done))))
and, provided that each recur-to form is in tail position with respect to all its enclosing loop forms up to and including its target and the number of arguments passed to each recur-to form matches the number of loop locals of the target loop (plus one for the leading loop name argument), this should compile and behave much like nested loops in Java.
The proposed syntax is modelled on Scheme's named lets, although semantically
those are quite different – this proposal is strictly limited to expanding the loop/recur model to nested loops in a natural way. Of course named fn forms ought also to be valid recur-to targets.
Key properties of named loops and recur-to
==========================================
With the above-linked patch in place, the following rules are enforced at compilation time:
1. Each recur-to form must be in tail position with respect to all its enclosing loop forms, whether named or not, up to and including its target (which may be a named loop or fn form).
2. It is an error to specify a recur-to target which does not occur among the names of the recur-to form's enclosing loop or fn forms with respect to which it is in tail position.
3. It is not possible to recur-to across try.
4. The number of arguments passed to recur-to beyond the initial target/label argument must match the number of formal parameters of the target loop or fn form.
5. Shadowing loop names is permissible; recur-to can only target the innermost loop of the given name among those with respect to which it is in tail position. Loop locals introduced by a shadowed named loop remain visible within the shadowing loop (unless they are themselves shadowed by identically named locals).
NB. loop names are *not* locals. In particular, they neither shadow nor are shadowed by locals of the same name. This point merits a longer discussion; see the section on design choices at the end of this email.
The innermost loop or fn form can always be targeted using plain recur, whether it is named or not. Additionally (recur-to nil …) is equivalent to (recur …) (even when the innermost loop or fn form is actually named), and (loop nil […] …) is equivalent to (loop […]).
Summary of the implementation approach
======================================
The patch modifies the handling of loop labels in the compiler and implements the few necessary tweaks to the loop macro.
It also introduces an optional name argument to the loop* special form. (It is optional primarily so as to avoid breaking any non-core macros that emit loop* directly.)
Finally, it renames the recur special form to recur*; recur and recur-to become macros defined in clojure.core. See the section on design choices below for alternative approaches.
Design choices
==============
1. During development, purely as a matter of convenience at that stage, I had a separate loop-as macro that accepted a name argument. I thought it reasonable to add the naming feature directly to loop, particularly since fn already takes an optional name. Still, loop-as is a valid alternative design.
2. Should it be desirable to avoid renaming the existing recur special form to recur* and reimplementing recur as a macro, a new recur-to special form could be added. (Alternatively, one could keep recur as it is while adding recur-to as a macro delegating to a new recur* special form.)
3. Should it be desirable to preserve the option of treating loop names as locals in the future, it would probably be preferable to make them shadow and be shadowed by locals now, as otherwise elevating them to the status of locals at a later point would be a breaking change. To give an example of why such a future change might be useful, if tail call elimination support arrives in a future JDK spec, one might consider whether it'd be useful to adopt a Scheme-like approach with the loop name treated as a local bound to a function with a single arglist corresponding to the loop locals of the named loop; the closure allocations this would entail could perhaps be optimized away if the local is never referenced.
It bears pointing out that if TCE support does materialize, it will enable a range of alternative designs. For example, Scheme-style named lets could then be introduced as a feature of the let macro. Thus it seems to me that it is reasonable to restrict loop/recur/recur-to to label+goto-style looping only, even in a hypothetical future with VM TCE support, and that there is no reason to afford local-like treatment to loop names; hence the current no-shadowing-interactions approach of the patch.
Cheers,
Michał
Mark Engelberg
Sep 10, 2017, 3:21:10 PM9/10/17
to clojure-dev
I have felt the lack of this feature before when working with nested loops. This proposal seems exceptionally detailed and well thought out. Thanks!
Nicola Mometto
Sep 10, 2017, 3:24:53 PM9/10/17
to cloju...@googlegroups.com
Not a comment on the proposed enhancement but on the impl:
changing the signature of a special form (in this case loop* and
the change of recur from a special form to a macro) is usually a
no-no, as it is a breaking change.
--
You received this message because you are subscribed to the Google Groups "Clojure Dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure-dev...@googlegroups.com.
To post to this group, send email to cloju...@googlegroups.com.
Visit this group at https://groups.google.com/group/clojure-dev.
For more options, visit https://groups.google.com/d/optout.
Reply all
Reply to author
Forward
0 new messages