Variadic Function in Scheme

Question

I have to define a variadic function in Scheme that takes the following form: (define (n-loop procedure [a list of pairs (x,y)]) where the list of pairs can be any length.

Each pair specifies a lower and upper bound. That is, the following function call: (n-loop (lambda (x y) (inspect (list x y))) (0 2) (0 3)) produces:

(list x y) is (0 0)
(list x y) is (0 1)
(list x y) is (0 2)
(list x y) is (1 0)
(list x y) is (1 1)
(list x y) is (1 2)

Obviously, car and cdr are going to have to be involved in my solution. But the stipulation that makes this difficult is the following. There are to be no assignment statements or iterative loops (while and for) used at all.

I could handle it using while and for to index through the list of pairs, but it appears I have to use recursion. I don't want any code solutions, unless you feel it is necessary for explanation, but does anyone have a suggestion as to how this might be attacked?

Answer 1

The standard way to do looping in Scheme is to use tail recursion. In fact, let's say you have this loop:

(do ((a 0 b)
     (b 1 (+ a b))
     (i 0 (+ i 1)))
    ((>= i 10) a)
  (eprintf "(fib ~a) = ~a~%" i a))

This actually get macro-expanded into something like the following:

(let loop ((a 0)
           (b 1)
           (i 0))
  (cond ((>= i 10) a)
        (else (eprintf "(fib ~a) = ~a~%" i a)
              (loop b (+ a b) (+ i 1)))))

Which, further, gets macro-expanded into this (I won't macro-expand the cond, since that's irrelevant to my point):

(letrec ((loop (lambda (a b i)
                 (cond ((>= i 10) a)
                       (else (eprintf "(fib ~a) = ~a~%" i a)
                             (loop b (+ a b) (+ i 1)))))))
  (loop 0 1 0))

You should be seeing the letrec here and thinking, "aha! I see recursion!". Indeed you do (specifically in this case, tail recursion, though letrec can be used for non-tail recursions too).

Any iterative loop in Scheme can be rewritten as that (the named let version is how loops are idiomatically written in Scheme, but if your assignment won't let you use named let, expand one step further and use the letrec). The macro-expansions I've described above are straightforward and mechanical, and you should be able to see how one gets translated to the other.

---

Since your question asked how about variadic functions, you can write a variadic function this way:

(define (sum x . xs)
  (if (null? xs) x
      (apply sum (+ x (car xs)) (cdr xs))))

(This is, BTW, a horribly inefficient way to write a sum function; I am just using it to demonstrate how you would send (using apply) and receive (using an improper lambda list) arbitrary numbers of arguments.)

---

Update

Okay, so here is some general advice: you will need two loops:

1. an outer loop, that goes through the range levels (that's your variadic stuff)
2. an inner loop, that loops through the numbers in each range level

In each of these loops, think carefully about:

1. what the starting condition is
2. what the ending condition is
3. what you want to do at each iteration
4. whether there is any state you need to keep between iterations

In particular, think carefully about the last point, as that is how you will nest your loops, given an arbitrary number of nesting levels. (In my sample solution below, that's what the cur variable is.)

After you have decided on all these things, you can then frame the general structure of your solution. I will post the basic structure of my solution below, but you should have a good think about how you want to go about solving the problem, before you look at my code, because it will give you a good grasp of what differences there are between your solution approach and mine, and it will help you understand my code better.

Also, don't be afraid to write it using an imperative-style loop first (like do), then transforming it to the equivalent named let when it's all working. Just reread the first section to see how to do that transformation.

All that said, here is my solution (with the specifics stripped out):

(define (n-loop proc . ranges)
  (let outer ((cur ???)
              (ranges ranges))
    (cond ((null? ranges) ???)
          (else (do ((i (caar ranges) (+ i 1)))
                    ((>= i (cadar ranges)))
                  (outer ??? ???))))))

Remember, once you get this working, you will still need to transform the do loop into one based on named let. (Or, you may have to go even further and transform both the outer and inner loops into their letrec forms.)