Scheme Programming/Looping

Simple Recursion

Scheme is very odd in one sense, it has no expressions designed for looping, repeating or otherwise doing something more than once at a general level. The only easy way to do this is recursion, that is, designing a procedure such that it meets 2 criteria:

1. The procedure must have a base case that it stops at
2. The procedure must call itself, possibly with modified arguments.

The most simple recursive procedures to write are tail recursive procedures. Lets think about how to compute the factorial of an integer. The factorial of an integer is that integer, multiplied by every integer below it.

$n!=n\cdot (n-1)\cdot (n-2)\cdots 1$

Now with a little bit of ingenious observation, we notice something special about this function:

$n!=n\cdot (n-1)!$

Now all we need to do is have a base case. 0! is 1 (the mathematical explanation of this is beyond the scope of this book). Now that we have a relationship between a factorial and a factorial of a different (smaller) number, and a base case, we can quickly write a recursive definition of a factorial function:

(define ! 
 (lambda (n) 
  (if (= n 0) 
    1 
    (* n (! (- n 1))))))

Now all we have to do is test that it works.

> (! 5)
120
> (! 6)
720

As you can see, this appears to work. This shows the general form of the most basic recursive functions.

(define <Name>
 (lambda (<Params>)
  (if (<Base Predicate>)
    <Base Case Body>
    (<Operation> (<Name> <Modified Parameters>))))

However, this leads to an inefficient method of computing the factorial of an integer, as Scheme must keep track of all of the intermediate variables. For example, lets look at the execution flow of (! 5)

(! 5)
(* 5 (! 4))
(* 5 (* 4 (! 3)))
(* 5 (* 4 (* 3 (! 2))))
(* 5 (* 4 (* 3 (* 2 (! 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (! 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120

Notice how this expands and contracts again, and that each intermediary value is stored. This is very inefficient with regards to the amount of space needed. Imagine trying to find the factorial of 1000. You'd need 1000 little notes of where you'd been so far. Unless there is no other way, this is generally discouraged.

Let's try implementing a slightly more abstract way of doing this. Think about summing a series of values together:

$\sum _{n=Lower}^{Upper}f(n)$

Which translates to:

$f(Lower)+f(Lower+1)+\cdots +f(Upper)$

This can also be translated into a Scheme procedure

(define sum 
 (lambda (f lower upper)
  (if (> lower upper)
    0
    (+ (f lower) (sum f (+ 1 lower) upper)))))

Once again, we can test this;

> (sum (lambda (x) x) 1 10) ; Using lambda here to only output the numbers 1 through 10
55

Which also exhibits similar flaws to the previous factorial procedure: It takes up a lot of 'stack space'.

The 'do' form

There is also an iterative construct, do, which can simplify writing some functions. For example, this procedure sums all the elements of the given list:

(define (sum/display lst)
  (do ((remaining lst (cdr remaining))
       (final-sum 0 (+ final-sum (car remaining))))
    ((null? remaining) final-sum)
    (display (car remaining))
    (newline)))

(sum/display '()) 
> 0

(sum/display '(1 2 3 7))
1
2
3
7
> 13

Here, the local variables remaining and final-sum are given the initial values of lst and 0, respectively. Then the test case, here (null? remaining) is evaluated. If the test succeeds, then the following expression is evaluated and becomes the final value of the entire do form. If it fails, Scheme evaluates the display and newline lines for their side effects, then redefines remaining and final-sum with the values (cdr remaining) and (+ final-sum (car remaining)) respectively. We can generalize this as follows:

(do ((var1 base1 exp1) (var2 base2 exp2) ...)
  ((test? ...) final-exp)
 side-effecting-statements ...)

This first creates the variables var1, var2, ... and gives them the initial values base1, base2, ... Then the test case (test? ...) is evaluated, and if it succeeds, the function evaluates and returns final-exp. If the test fails, side-effecting-statements ... are executed, var1, var2, ... are redefined with the new values from exp1, exp2, ... and then the test case is evaluated again. Failing to provide a proper test case could potentially lead to either an error in Scheme or an infinite loop.

map and for-each

Scheme defines two functions to iterate over a list. map and for-each both iterate over every element of a list and call a procedure with each element. Map stores the return values of each call to the function, while for-each does not:

(map (lambda (x) (* x 2)) '(1 2 3 4 5 6))
> (2 4 6 8 10 12)

(for-each (lambda (x)
            (display (* x 2))
            (newline))
  '(1 2 3 4 5 6))
2
4
6
8
10
12
>

For-each is in fact similar to the "foreach" loop found in many programming languages. In fact, we could define such a loop as new syntax, adding it to the language:

(define-syntax foreach
 (syntax-rules ()
  ((_ ((variables lists) ...)
    body ...)
   (for-each (lambda (variables ...) body ...) lists ...))))

The resulting "foreach" form iterates over multiple lists in parallel:

(foreach ((number '(1 2 3 4 5))
          (letter '(a b c d e)))
 (display (list number letter))
 (newline))

(1 a)
(2 b)
(3 c)
(4 d)
(5 e)
>

Iterative recursion

We can use iterative recursion to reduce the space requirements of many procedures. We shall look at the factorial procedure once again. Rather than keeping a long list of all the values to be multiplied at a later date, we could keep an ever-changing answer, and pass it to the next call of our procedure. Let's look at how this works when applied to the factorial function:

(define !-it
 (lambda (n current)
  (if (= n 0)
    current
    (!-it (- n 1) (* n current)))))

Now we can check that it works:

> (!-it 5 1)
120
> (!-it 6 1)
720

As we can see, this both has an automatic advantage and disadvantage. We make it use less space, and we need to effectively specify the base case when it is invoked. We shall investigate the computational process it generates first.

We shall follow the computation of 5! through once again, but using the iterative procedure this time:

(!-it 5 1)
(!-it 4 5)
(!-it 3 20)
(!-it 2 60)
(!-it 1 120)
120

Notice how this one never expands and then contracts again, and there is nothing "left to later" (often referred to as "Deferred processing"), and this version of the procedure only keeps track of 2 variables, regardless of the size of its input.

Now we shall tackle the issue of the extra, unnecessary parameter; this requires a slight re-definition of the procedure,

(define !
 (lambda (x)
  (define !-internal
   (lambda (n current)
    (if (= n 0)
      current
      (!-internal (- n 1) (* n current)))))
  (!-internal x 1)))

This solves the problem by showcasing a previously un-introduced feature of Scheme. That is; functions may, internally, contain definitions of new functions and variables. These are not visible outside the procedure. This new procedure solves both of our previous problems with the first recursive factorial procedure. It operates in both constant space, and it is easy to use.

Now we shall show that sum can also be implemented in a very similar way:

(define sum
 (lambda (f lower upper)
  (define sum-int
   (lambda (f lower upper current)
    (if (> lower upper)
      current
      (sum-int f (+ lower 1) upper (+ (f lower) current)))))
  (sum-int f lower upper 0)))

An interesting side note is that both factorial and summation can be abstracted to a more generic procedure, that can be used for even more than factorials and sums. Allowing for products, numerical integration and other interesting methods to be implemented. I'll leave this as an exercise to the reader (it's not overly challenging, but if you've not done any programming before, or you don't have a mathematical background, this exercise can be challenging).

Looping Over Lists

Suppose we have a list, and we need to find if an element exists in that list. We would have to go through every element of that list, and check it against our desired result.

(define exists-in?
 (lambda (ele lis)
  (cond ((null? lis) #f)
        ((equal? ele (car lis)) #t)
        (else (exists-in? ele (cdr lis))))))

Notice how we first check that we aren't out of elements to check against, this prevents us trying to take the cdr of an empty list (thus causing an error). Then, we check to see if we have a match, Otherwise, carry on searching. Unless you have an infinite list (this is possible in Scheme, we'll see how later), this procedure will reach a definite answer.

We also may have the problem of adding two to every element of a list.

(define plustwo
 (lambda (lis)
  (cond ((null? lis) nil)
        (else (cons (+ (car lis) 2)
                    (plustwo (cdr lis)))))))

Here, we are 'mapping' each element of the list to some value. In this specific case, that value is the value of each element of the list, plus two. What if we wanted to multiply the value of every element of a list by 3? Or find the square root? We would have to write the code each time, and each would look very similar. It would be more reasonable to abstract what the particular function is and allow the programmer to substitute it in each time.

(define map
 (lambda (f lis)
  (cond ((null? lis) nil)
        (else (cons (f (car lis))
                    (map f (cdr lis)))))))

Now we can define plustwo more succinctly:

(define plustwo 
 (lambda (lis) 
  (map (lambda (x) (+ x 2)) lis)))

This shows a very important concept in Scheme. Function can be passed around just like numbers, strings, atoms, and other things. Using this idea, we can go on to address the problem of finding if an element is in a list as above.

We first notice that the output of the function can only be #t or #f, or some error. Ignoring the error case to begin with, we can begin to write a way of abstracting out the case of testing each individual element for some predicate. We can then use that function to find if any element is equal to any given value, using map.

We'd like to be able to "fold up" a list of such values into a single value: #t if any of the values are #t, or #f otherwise. We'll name our function foldr.

(define foldr
 (lambda (f e lis)
  (cond ((null? lis) e)
        (else (f (car lis) 
                 (foldr f e (cdr lis)))))))

We can now use this folding function to define a function called any, which tells us if any of a list satisfy a predicate (a predicate being a function which returns #t or #f).

(define any
 (lambda (pred lis)
  (foldr (lambda (x acc) (or x acc)) 
      #f 
      (map pred lis))))

Using this function we can re-write exists-in? as a much simpler function.

(define exists-in?
 (lambda (ele lis)
  (any (lambda (x) (equal? x ele))
     lis)))

Which can more easily be read as "Is any element of the list 'lis' equal to 'ele'?". It is also shorter, and given that foldr, map and any have been implemented correctly, easier to find any problems with it.

Folds are often used in functional programming to express solutions to a problem in a very succinct way, or to avoid re-writing the same code for defining a recursion repeatedly.