Flow Control

One of a series of tutorials about Scheme in general
and the Wraith Scheme interpreter in particular.

Copyright © 2011 Jay Reynolds Freeman, all rights reserved.
Personal Web Site: http://JayReynoldsFreeman.com
EMail: Jay_Reynolds_Freeman@mac.com.

This tutorial is about how Scheme decides what to do next when it is running a program, or perhaps more accurately, about the procedures, special forms, and so on that you can put in a program to tell Scheme what to do next. I have mentioned a few of those things in previous tutorials -- we already know how procedure applications work, and how one procedure can call others, and we have seen the "if" statement several times. Yet there are more.

For review, and in order not to overlook the basics, let me remind you about procedure applications, and while we are at it I will mention the uses of special forms and macros, since they look the same in a program: They all look like embedded unquoted lists.

When a Scheme interpreter encounters an unquoted list, the first thing it does is always the same, and happens completely automatically, with no further intervention or instructions on your part. Scheme evaluates the first item of the list, and then decides what to do next based on what kind of thing it turns out to be after evaluation. Most often, the first item of a list to be evaluated will be a symbol -- the name of a variable -- so the evaluation is merely the looking up of the value bound to that symbol in the current environment list. Thus unless you have done something really weird, like redefining "+", when Scheme tries to evaluate the list

it will look up the symbol "+" and will find a binding for it in the top-level environment, where it is bound to the Scheme procedure that performs addition.

Yet the elements of lists to be evaluated do not have to be as simple as the symbol "+". For example, consider

where I have used whitespace to set off the first element of the list by itself. In this case, the first item of the list is itself a list, and a nested one to boot; namely "(car (cdr (list 3 + "foo")))". Scheme will have to evaluate that list as well, and because of the nesting it will have to do so recursively: It starts to evaluate the list that begins with "car", then has to put that aside to evaluate the list that begins with "cdr" in order to get the argument for "car", and then it will have to put "cdr" aside as well, in order to evaluate "(list 3 + "foo")" to get the argument for "cdr". Now, "(list 3 + "foo")" evaluates to "(3 #<Built-in procedure "+"> "foo")", the cdr of that is "(#<Built-in procedure "+"> "foo")", and the car of that is "#<Built-in procedure "+">". So the car of the original list, which was

evaluates to "#<Built-in procedure "+">".

Once Scheme has evaluated the car of a list, it looks at the evaluated car to decide what to do next. If the evaluated car is a procedure, Scheme then evaluates all the remaining items of the list, recursively if necessary, and passes those evaluated items to the procedure as its arguments. If the evaluated car is a special form, Scheme merely looks up the code associated with the special form and lets it run; Scheme does not automatically evaluate the rest of the items of the list, it lets the special form code decide whether to do that or not.

We haven't studied macros yet, but a macro is a Scheme object that has a lambda expression -- a procedure -- associated with it. When the car of a list being evaluated evaluates to a macro, Scheme again does not evaluate any of the remaining items in the list. Instead, it looks up the lambda expression associated with the macro, applies that lambda expression to the entire list being evaluated, and then evaluates the result thereof. You can think of a macro as a means of turning a list to be evaluated into something else, before the actual evaluation takes place.

The point of discussing procedure applications in the context of flow control is that in a great many cases, procedure applications are all the flow control you need. A large proportion of the procedures that Scheme users create consist simply of nested procedure calls; no other forms to control the flow of execution are used or are necessary.

We have run into a number of places where Scheme will happily evaluate many expressions instead of just one, such as within the body of a lambda expression. In general, though, you can't do that without using the begin macro. The sole purpose of "begin" is to allow the sequential evaluation of a whole block of expressions. When Scheme encounters a "begin" form, it evaluates the expressions within it in order, and returns whatever the last expression does. For example

Note that the "#t"s returned from the individual calls to "display" do not show up anywhere; the calls to "display" are made for their side-effects; namely, printing something.

The "begin" form is particularly useful with "if", because "if" takes a single expression for its consequent and also for its alternative. If there is more than one thing to do in the consequent or the alternative, you can use "begin" to get everything done.

What "begin" does is -- once again -- provide syntactic sugar over lambda expressions. When Scheme sees a "begin", it makes a lambda expression of no arguments, whose body contains all the statements that were inside the "begin", and uses that lambda expression in a procedure application (with no arguments, of course).

We have already seen if, but let's review. It has two forms,


In either case, Scheme first evaluates the <test> and then decides what to do next. It the <test> evaluates to anything that counts as "true" -- that is, anything other than the false boolean, #f -- Scheme evaluates the <consequent> and returns whatever it returned as the result of the "if". If the <test> is false, then in the first case, Scheme evaluates the <alternative> and returns whatever it returned as the result of the "if", but in the second case, where there is no <alternative>, Scheme simply returns #f.

The fact that "if" does not evaluate both the <consequent> and the <alternative> means that you can use "if" without worrying about unintended side effects: Only the side effects for the branch of the "if" actually taken will occur.

Sometimes programmers need to deal with a situation in which a whole lot of things might be happening, and they have some notion of priority, in that some possibilities are more important than others, and should be looked at first. In English, the plan for dealing with such a group of prioritized conditions might look like this.

If you try to write out Scheme code for such a situation, it can get kind of cluttered.

Some people would format that differently, perhaps like

but no matter how you format it, a long chain of "if"s is sometime clumsy. If you find it so, Scheme provides a form called cond -- which stands for "conditional" -- that may be useful in such situations. Using it, we could write the psuedocode just given as follows, where I have used whitespace to line up the things to do in a neat column.

A "cond" form contains a bunch of cond clauses, each comprising a list whose first element is a test. When Scheme encounters a "cond" statement, it goes through the cond clauses one at a time, evaluating each test in turn. When and if it finds a test that evaluates to true, Scheme executes the rest of the statements in that cond clause -- there can be more than one, though our example only has single statements -- and returns whatever the last statement does, as the return value of the "cond".

If no test in any cond clause evaluates to true, the "cond" returns #t.

The reserved word "else" is allowed in the "test" position of the last cond clause in a cond. It acts the same way that "#t" would in that position.

Here are some examples of cond

There is another form, case, that works much like cond. The distinction is that whereas "cond" evaluates many tests in figuring out what to do, "case" evaluates a single expression just once, and compares the result (using "eqv?") to a variety of constants, looking for a match. Here is a simple example of case.

In that example, the expression that "case" evaluated was merely "number", but more complicated expressions are allowed. Furthermore, instead of having just one constant to compare against in looking for a match, you can use a list of constants.

The examples just shown have "case" working with numbers, and that is one of its most common uses, but any kind of Scheme objects may be used instead.

Now let's talk about a new procedure, apply, that captures the essence of a procedure application in a slightly different form. By using "apply", we can apply a procedure to some arguments without actually writing a procedure application out as a parenthesized list. For example,

is precisely equivalent to

That example is kind of silly, though. What "apply" is really for is situations when you go through some long lengthy process to decide what procedure to use, or perhaps you construct a lambda expression, or perhaps you build up the argument list by some other long lengthy process. Then you end up writing code like

There is one twist to "apply" that is sometimes useful. In the examples just given, "apply" was called with two arguments, the first being a procedure and the second a list of arguments to be passed to that procedure, but it is also possible to call "apply" with more than two arguments. When that happens, "apply" builds a single list of arguments to be passed to the procedure, by prepending the "extra" arguments to the final one. That is, if you call

what happens is the same as if you had called

That is,

is precisely equivalent to

Having "apply" support more than two arguments in this way makes it easy to use "apply" with one of those procedures that can be called with several specifically named arguments and an optional list of more; that is, with a procedure that might have been defined as something like

There are times when you want to apply the same procedure many times, to many different arguments. Scheme has two procedures to help. One is intended for situations in which you are interested in gathering up the results of all those procedure applications, another when you are only interested in their effects.

The procedure for use in gathering up results is map. Here are some examples. Suppose you want to take the negative of each number in a list; that is, you have a list of numbers and you would like to apply "-" to each item in the list and gather up the results. Here's how:

Or suppose you are using a procedure that takes two arguments. Perhaps you have a bunch of right triangles and you would like to calculate the hypotenuse of each of them. You make up a list whose elements are the first sides of each triangle, and another list of the second sides in the same order. Then you use map with the "hypotenuse" function and those two lists. So, suppose you have three triangles, whose sides are respectively (3, 4), (8, 15) and (5, 12). The two lists of sides are going to be (list 3 8 5) and (list 4 15 12). Your code might be

The general idea is that you call "map" with a first argument that is a procedure, followed by as many lists as the procedure takes arguments; "map" applies the procedure to consecutive groups of elements of the lists and returns a list of the results.

Scheme guarantees that the returned list of results will be in the order that matches the order of arguments in the given lists; for example, in the "hypotenuse" example, 5 is the hypotenuse of the triangle whose sides were 3 and 4, and so on. Scheme does not guarantee that the individual procedure applications that map requires will take place in the same order as the elements of the list; for example, "map" might end up calculating the hypotenuse of the (8, 15) triangle before the (3, 4) triangle. A Scheme implementation might use parallel processing to perform the various procedure applications in an arbitrary order, but if it does, it must finally build up a list of results in the correct order, to return from "map".

All of the list arguments to "map" must have the same length.

The procedure for use in calling the same procedure many times for side effects is for-each. Here are some examples. Suppose you have a list of strings and want to display them all.

Notice two things in that last example: First, "for-each" did not return anything particularly useful -- there was no list of results. Second, "for-each" did go through the procedure applications in the same order as the arguments in the list; that is, the result was not scrambled -- we got "Feed the cat now!" and not something like "the Feed now! cat". Indeed, "for-each" guarantees to do its procedure applications in the order of the arguments in its lists, so that the side effects happen in that same order.

Like "map", "for-each" can deal with procedures that take more than one argument, simply by accepting more than one list of arguments.

All of the list arguments to "for-each" must have the same length.

If you are familiar with just about any other programming language, you will be expecting Scheme to have some kind of looping construct, like "for" or "while" in C++ or Java. Scheme does have such a construct -- it is called do -- but it is complicated enough that I am going to leave it out of this tutorial. You can read about it in the R5 report or in the Wraith Scheme Dictionary, if you wish.

What is more, it is usually faster and simpler to use some of Scheme's other forms to do most of the things you might want to do with a looping construct. Suppose you are working with arrays of numbers, and you wish to perform some operation on each element of an array. Scheme uses the word "vector" where many other languages use "array", so your numbers are probably stored in vectors. Use vector->list and list->vector to convert the vectors to and from lists, and use "map" to perform your operations. For example, here is how to multiply the corresponding elements of two vectors and create a vector that contains the results.

It would perhaps be even simpler and more straightforward to keep the numbers in lists, and not use vectors.

I am not telling you not to use "do", but I am telling you that you really ought to learn to use "map" and "for-each" to full advantage first, particularly if you have previous experience with other programming languages that use the more conventional kind of "for" and "while" loops.

Scheme also has a very powerful way to perform more general kinds of loops, even infinite loops (that is, loops that never end). It is called tail recursion, and we will learn more about it in the next tutorial.

-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)

Wraith Face