Loops in Racket…for this course

Looping behavior is common in programming languages. In CSCI 150, you learned about for and while loops in Python.

for x in range(10):
    print(x)

In CSCI 151, you saw similar loops in Java. Here’s a fragment of code summing the values stored in a linked list using a while loop.

Node *n = head;
int sum = 0;
while (n != null) {
    sum += n.val;
    n = n.next;
}

Racket has a number of constructs which provide loop-like behavior.

In CSCI 150, you learned another way to get loop-like behavior: recursion. In this course, you are required to use recursion and are forbidden from using loops.

Let’s look at two common looping mechanisms in Racket that you may not use in this course and how to get the same behavior using recursion. (These are the two mechanisms you’re most likely to find if you search the Internet for loops and Racket.)

for

The first looping mechanism is for. Here’s an example Racket program that performs the same computation as the Python loop above using Racket’s for.

(for ([x (range 10)])
  (displayln x))

The semantics of for—which is to say, the behavior of for—is to evaluate the body of the loop (displayln x) with x bound to each element of the list in turn. That is, (displayln 0), (displayln 1), …, (displayln 9).

The functional programming approach for such loops is to rewrite the loop to use explicit recursion. Here’s a template for basic recursion in Racket.

(define (some-recursive-function lst)
  (cond [(empty? lst) base-case]
        [else recursive-case]))

This defines a function with the awkward name, some-recursive-function which takes a list as an argument and binds it to a variable named lst. If lst is the empty list, then some-recursive-function evaluates and returns the base-case expression (or expressions). Otherwise, the list is not empty and in the recursive-case, we can use (first lst) and make a recursive call, passing the rest of the list.

Here’s the complete example.

(define (display-list lst)
  (cond [(empty? lst) (void)]
        [else
         (displayln (first lst))
         (display-list (rest lst))]))

Note that the recursive-case contains two expressions, the displayln and the recursive call to display-list. Most of the functions you’ll write in this class will involve constructing values rather than printing them (we let DrRacket print data for us in most cases). As a result, you’ll likely have just a single (potentially quite complex) expression for the recursive case (or cases) and you’ll do something with that result.

Here’s how we would sum up the values in a list which is a more typical example of recursion in Racket.

(define (sum lst)
  (cond [(empty? lst) 0]
        [else (+ (first lst)
                 (sum (rest lst)))]))

Notice that 0 is the base case and the recursive case adds the first element of the list to the result of the recursive call to sum on the rest of the list.

Note that for is designed for the unusual case where we don’t care about the values produced by the body of the loop. Instead, we only care about side effects like printing out values.

One consequence of this is we cannot use for to implement sum without using something else we’re not going to be using in this course: mutation. That is, we’d need to initialize some sum variable to 0 and then modify the value each time through the loop.

(define (bad-sum lst)
  (let ([sum 0])
    (for ([x lst])
      (set! sum (+ sum x)))
    sum))

This feels pretty natural when coming from an imperative language like Python or Java but it is not how we write functional code.

To be clear, you may not use for or for* or for/list or any other for construct in CSCI 275. Similarly, unless specifically directed to (in the MiniScheme project), you may not use set! or any other function that involves modifying the values of variables.

let loop

The second construct you’re likely to find if you search for loops and Racket is what’s known as a “named let.” A named let is simply syntactic sugar for some other common Racket syntax that you should use instead.

Here’s an example, again computing a sum of elements in a list.

(define (sum lst)
  (let loop ([lst lst]
             [result 0])
    (if (empty? lst)
        result
        (loop (rest lst)
              (+ result (first lst))))))

There’s nothing special about the name loop used in let loop, but it’s the name you’ll see most often. As you can see, this code gives the impression that there’s a loop happening here: There are two loop variables, lst and result which are initialized to the argument lst and 0, respectively. The body of the loop checks if lst is empty and if so, returns result. Otherwise, it starts the next iteration of the loop with lst bound to the rest of lst and result bound to the sum of result and the first element of the list.

In reality, what is happening is this is defining a new function named loop that has two parameters, lst and result. The body of the let is the body of the loop function. Rather than starting the next iteration of the loop as I wrote above, calling loop is actually just making a standard recursive call.

let loop implements what I have called “accumulator-passing style” in which functions have extra accumulator parameters which are used to store intermediate values of computation.

Let’s implement sum using an explicit recursive helper function.

(define (sum lst)
  (letrec ([f (λ (lst result)
                (if (empty? lst)
                    result
                    (f (rest lst)
                       (+ result (first lst)))))])
    (f lst 0)))

This code is explicit that it’s creating a new recursive function named f that has parameters lst and result. The body of the letrec is the call to f, passing the initial values.

To be clear, you may not use named let (let loop) in this course. Use the explicit form with a letrec instead.