The Common Lisp LOOP Macro for Racket

1 Introduction

This is an implementation of Common Lisp’s LOOP macro for Racket. The LOOP macro is similar to all of Racket’s for/* macros, combined with Python’s for loop, except it’s more powerful than either.

Examples:

(define (sift pred? list)

(loop for value in list

when (pred? value) consing value into gold

else consing value into dirt

finally (return (values (reverse gold) (reverse dirt)))))

> (loop for x in '(a b c d e f g)

for y from 0

when (even? y)

collect x)

→ (a c e g)

> (loop for x in '(a b c d e f g)

for y in '(1 2 3 4 5 6 7)

with-collection-type hash

collect (cons x y))

→ #hash((g . 7) (b . 2) (a . 1) (c . 3) (d . 4) (e . 5) (f . 6))

LOOP can also do the job of for/and:

(loop for x in a-list

for y in another-list always (and (number? x)

(symbol? y)))

...or for/or:

(loop for x in a-list thereis (symbol? x))

...or for/sum:

(loop for x in a-list when (integer? (sqrt x)) sum x)

...or you can convert a list into a hash table:

(loop with collection-type 'hash/immutable

for key-value in '((key . val) (key2 . val2))

collect key-value)

...or you can write an old-fashioned while loop:

(loop for line = (read-line socket)

while (not (eof-object? line))

do

(display line)

(newline)

finally

(close-input-port socket))

The loop macro can also iterate over generators as defined in the racket/generator package.

(loop for item in (gen)

do

(displayln item))

Since racket/generator provides no non-ambiguous way to end a generator, arrange for your generator to yield the value end-of-generator to terminate the loop, or use an explicit return clause to exit.

2 Enabling return

In Common Lisp, the LOOP macro is often used in conjunction with return and return-from. This library defines return as a macro which invokes a continuation that can be tucked away within this module.

return is defined as a macro and not a function because in Common Lisp, it’s legal to do this:

(return (values 1 2 3 4))

...where a function would not be able to receive the multiple values. return and its hidden continuation are defined as follows:

When the LOOP macro is invoked, it sets the return-cc parameter with its own continuation, which is only an escape continuation.

There is also a return action clause, which is discussed below.

3 The Main Body

3.1 Variables used during macro expansion

The traditional Scheme way to write anything at all is to define all the variables as arguments to a recursive loop-function, and to change those variables, you pass every variable to the next iteration of the loop-function, giving new values for the variables that should be different for the next iteration. At first I began with a design like that (and most of the supporting functions are still written this way), but as the number of variables grew, it became more than a little difficult to pass all of them as arguments at every point in the program where the loop-function was called. Every time a new variable was added, it was necessary to go back and change all the points where recursion took place. A big chunk of the code I wrote this way had to be deleted and rewritten from scratch.

As a result, I ended up taking most of the variables out of the loop-function’s argument list and just changing them with set!. It may be less "Rackety", but it gets the job done.

The main body of the macro iterates over all the clauses and builds the following variables:

• finally is the finally clause, which gets executed after everything else. It can be bypassed with a return form. Often, a return form is used in a finally clause to cause the loop to return loop-local variables.

• iterations is a syntax-list of all the variables that must be changed with each iteration of the loop, along with a snippet of code that does the change. An example of what might be in this variable is #'((variable-name (add1 variable-name)) (var2 (cdr var2))) The iterations get executed just as the loop is recursing into the next iteration

• preconditions is a list of Boolean forms that determine if the loop body will be executed. Most of these forms are begin forms that also iterate something.

• current-condition is a list of boolean clauses that is built while processing if clauses.

• loop-conditions A syntax-list of conditions that will be combined with the and operator to determine if the loop should continue. These are checked just before the iterations are executed.

• action-clauses This is a list of action forms that will be combined with the current-conditions if they are defined, otherwise they go into the body naked.

• current-cond-body This is a list of clauses for a cond form. This implements the if and else, and do clauses of the loop. The current-condition gets added to this list along with code from one or more action clauses.

• body is a collection of all action clauses and current-cond-bodys to be executed.

• list-defs are let-bindings for any lists that are being iterated over using a for clause. They are named with the (gensym) function.

• let-defs are let-bindings for any variables bound with a for clause.

3.2 Variables representing identifiers

References to identifiers in the <loop-body> below need to be made from the code in the variables above, and this code is generated outside of the scope of the <loop-body>. Because of Racket’s hygienic macros, the only way to do this is to put the identifiers themselves into variables that have a wider scope. Some of these identifiers are just the names of variables within the local-loop block, but others may be changed during macro expansion:

• call-with-cc determines the type of continuation that will be used. This was going to be used to implement a yield clause, which would change it from call/ec (the default) to call/cc, but the racket/generator package already provides a yield form that can be used effectively from within the loop macro, so I’ll save myself the headache of reinventing generators for Racket.

• initial-count, initial-sum, initial-string, and initial-collection are initial values for collector variables. They default to #f unless the relevant clause is used. The #f value is used to control the return value of the loop.

These variables can then be combined to form the loop itself, as it will eventually be expanded.:

The return-continuation is used for all exits from the loop.

All the lists being iterated over are iterated just before all other iterations, including binding of loop variables to the first element of the list. Each list has a corresponding variable that is bound to the next element of the list via the car function. This binding is all that takes place during the iterations, and must happen after the lists themselves have been cdr’d off.

4 Handling Conditional Statements

Common Lisp’s LOOP facility allows the use of if and else clauses that alter the behavior of the loop. Expansion of these clauses proceeds as follows:

1. Rewrite all when clauses as if clauses

2. Put the if foo clause into current-condition, pushing any existing current-condition onto a stack first so that nested ifs can be handled.

3. If an action clause (such as do, collect, count, etc) is encountered while a current-condition exists, combine the action clause and the current-condition into a clause that can be added to a cond form (current-cond-body). The and operator is added to the front of the current-condition list, unless current-condition is the word else.

4. After an action clause, an else clause can be encountered, which goes into the current-condition, ultimately adding another clause to the current-cond-body when an action clause is encountered.

5. If an end clause is encountered, a cond statement is created with the current-cond-body and added to the body.

6. If an if clause is encountered after if condition action-clause ..., rewrite it as if it was preceded by end.

4.1 Managing a stack of nested if-clauses

(loop for item in list

if (something? item)

if (something-else? item)

do (frobnicate item)

else if (third-thing? item)

do (replicate item)

else

(notify item))

The LOOP macro must support syntax like the above, with the effects you would expect based on the indentation shown. This requires managing a stack. If an if clause is encountered while another one is already being processed, the variables pertaining to the existing if must be pushed onto a stack, and popped from that stack when the end of the nested if clause is reached.

4.2 Rewrite when and unless clauses

The chunk of code below is evaluated within the context of a syntax-case macro called loop-body.

4.3 Collect if clauses

4.4 Collect else and else if clauses

4.5 AND

If AND appears after an action clause, then a subsequent action clause will be part of the previous conditional.

4.6 END

The end clause denotes the end of conditional processing. Action clauses after this will be treated as unconditional, or as belonging to the outer-level if clause. Whatever current-cond-body is being built gets inserted into the body at this point.

5 Action clauses

The action clauses are where the current-condition gets combined with some code to add to a current-cond-body.

Most action clauses only accept one form as an argument, but the do clause is special. Any compound form (ie, one surrounded by parentheses) following the do clause is part of the action clause, and a do without an action clause is illegal. This means the do form cannot be processed by rewriting it into another do form. Instead, it is rewritten as a do-internal form, which is ignored if the form following it is not a compound form.

5.1 Unavoidable boilerplate

There are various chores that each action clause must accomplish on its own. Unfortunately, macro hygiene makes it impossible to define macros to do it. The macros must be defined in a separate file due to limitations in Racket, and due to the hygiene, local variables here wouldn’t be visible to the code generated by the macro.

One thing that each action clause must do is detect whether two action clauses have been written in a row, which breaks the conditional. For example in the following code:

(loop for x from 1 to 10 if (even? x) collect x do (displayln x))

..the do clause should be interpreted as if it was preceded by an end clause. That is, the cond form that goes with the if clause should be generated before generating the code that implements the do clause. The check for whether this should be done is:

The current-condition is the boolean expression (missing its and operator) that determines whether the action-clause should be executed. If there is no current-condition, then that means the action-clause being processed should be executed unconditionally. But if even if there is a current-condition, it may be a stale current-condition left over from a previous action-clause. The current-condition is only fresh if the and? flag is set.

Therefore, if the above expression is true, it is safe to go ahead and process the action clause, otherwise an end clause must be inserted and processed first. The code to do the inserting varies between action clauses just enough to prevent it from being put in a chunk.

After the action-clause needs no further preprocessing, the next thing that must happen is that some code must be generated. What exactly is generated differs between each action-clause, but all action-clause generated code goes into a list, where it is later either placed into a cond form, or added naked to the body.

The generated snippet of code is added with this function:

After adding its action-clause code to the action-clauses using add-action-clause, every action-clause must check if the clause is conditional or not. If the clause is conditional (that is, if current-condition is non-empty), then the action-clauses are left alone for later processing, and the body is not modified, as this will be handled in the end clause. But if the action-clause is unconditional, its contents must be added to the body now.

When do-internal runs out of compound forms, then everything is placed into the body using the boilerplate code.

5.2 Other Action Clauses

5.2.1 return

In addition to being able to use the return macro in a do clause, the LOOP macro also supports return as a clause. It can be simply implemented by rewriting it as a do-internal clause, the only problem being that an extra compound-form following the return clause would be interpreted as belonging to the do-internal clause. That case must be guarded against.

5.2.2 collect

The collect clause tells the loop to store a value in a collection list, which will be returned.

The loop macro also supports collecting into a specific variable.

(loop for x in list when (odd? x) collect into odds)

Doing this requires a separate version of the above macro. It wasn’t possible to combine the above’s functionality because there’s no way to compare syntax-objects to tell if an identifier that appears in the pattern equals collection or another macro variable.

Furthermore, because the collection variable can be accessed during iteration, and must be a list in the correct order, it is not possible to cons the list in reverse order and then reverse it, as is done with the implicit collector. Instead, adding to the end of the list is done with append, which makes collect into O(n) for each iteration where a collect into occurs. A loop that uses collect into on every iteration could be as slow as O(n2). Therefore, a warning is issued every time collect into is encountered at compile time.

Also, more than one collect into clause can appear that refer to the same variable. Therefore, a special procedure is needed that adds to the let-defs only if the variable is not already defined there.

That function which adds the let-def only if it wasn’t previously added, is defined as follows:

5.2.3 cons

Because collect into is such a uselessly pathological case in Racket (in contrast with how useful it is in Common Lisp), an extension is provided: cons into operates like collect into, except the resulting list is seen in reverse order. There is no cons without into, and if there was, it’d be a synonym for collect.

5.2.4 collect variants

The collect clause can return different types. The return type is controlled by the collection-type variable, which can be set using the with-collection-type clause. When the loop is about to return, it checks the collection-type and constructs a return value as follows:

That last two conversions are not provided by Racket. They must be implemented here.

5.2.5 append

This is like collect, except the value must be a list, which will be appended to the end of the collection.

5.2.6 sum

This clause adds the given value to a numerical accumulator, which is then returned.

5.2.7 count

Counts the number of times the expression evaluates as true.

5.2.8 minimize and maximize

This binds the smallest random number seen into min-random:

(loop repeat 100 minimizing (random 100) into min-random ...)