Techniques for Programming in Scheme

-- Techniques for Programming in Scheme --

** Part I : General Programming Techniques **

- Evaluating Expressions

The most important skill a programmer must have is the ability to evaluate every possible expression in the computer programming language. (Or at least those necessary to do some useful work.) When developing a program, you should avoid using expressions that won't evaluate correctly (or at all). If you don't know how to evaluate an expression, then it's only proper to assume it will have negative effects, and you should avoid using it in your own code.

Similar to speaking in foreign language, if you just put words together, chances are people will laugh at your ignorance. I would also hate to be the one to mutter an insult or threat that may lead to violence. In a program, scattering symbols about may result in the computer mockingly report an ERROR to you, or if you are unfortunate, may cause the computer to crash.

The moral of this is, "only use expressions if you know they will cause the expected result." Your ability to program will be directly related to your ability to formulate simple expressions into more complex expressions, all aimed at a common goal of doing some useful work. In order to explain to a worker how to do his work, I must use plain English; in order to explain to a Scheme Interpreter how to do its work, I must use plain Scheme.

- Designing and Using Procedures

The first steps to writing or using procedures is to define their major features. Procedures are most clearly characterized by looking at their parameters, return values, and their implemented tasks. Given two procedures with different names, and all of those characteristics being equal, they may as well be the same procedure. (In other words, names aren't important, it's what they do that counts.)

Everytime you use or define a new procedure, it should be characterized by:
1) Parameters - What does the procedure use?
2) Work - What does the procedure do (generally) to get to the return value?
3) Return Value - What value does the procedure return?

If you find a procedure and cannot identify these elements, then using it could be hazardous! That red button you press could start World War III!

* Parameters

What do we need to know about the parameters? Like a recipe, we need to know what goes in to get what we want out. If we add the wrong ingredients, it could be poisonous, or putrid! The parameter types should be defined clearly to avoid using an incorrect data type (if you are asked to put in a chicken egg, you'd better not make it a ceramic egg!). Also make sure that you know the proper number of arguments, and their appropriate order in the parameter list (putting them in the wrong order is like swapping the ingredients in a recipe).

* Work

What do we need to know about the work done? There are many ways at getting to the same goal. Some ways are better than others given particular circumstances. If I want a cake out of mixing the ingredients, then I want to have a general idea of how it's done. This would also help me decide whether or not another procedure may be more appropriate.

* Return Value

What do we need to know about the results? Whenever we do something, it's critical that we identify the outcome. If we want to bake a cake, we don't want a mud pie as a result. Similarly, procedures must have their results defined so we know if the output is what we need and expect. If I'm throwing a party, mud pies are probably not going to impress my friends!

When you write your own procedures, it's always nice to describe what its characteristics are in the form of a comment. This is invaluable for the instances when you go back to your code and need to recall what purpose it serves! My favorite method is shown in the example:

; merge - Merges two given lists into a single list by alternating
;          between both lists.  In the front of the list, the odd numbered
;          elements are from the first list, and the even numbered elements
;          are from the second list.  In the case of unequal length lists,
;          the remaining elements that can't be merged are appened to
;          the end.
; PARAMETERS:
;    list1 - The first list to be merged with the second.
;    list2 - The second list to be merged with the first.
; RETURNS:
;    The list representing the values of the two given lists, list1 and
; list2 merged together.
;
(define (merge list1 list2)
  (cond ((empty? list1) list2)
        ((empty? list2) list1)
        (cons (car list1)
              (cons (car list2)
                    (merge (cdr list1) (cdr list2)))) ))

** Part II : Examining Code Through Pattern Matching **

- Determining the Result of an Expression

Understanding the results of evaluating an expression is extremely important. By looking at code, you should be able to determine not only what the result of evaluating an expression is, but also what type of result it needs to have to avoid causing an error. This analysis is accomplished by examining the form of the expression, as shown in my document on "How to form Scheme expressions," and by the three characteristics of the involved procedures.

Starting with a simple example, what if we were given the following expression?

(list 23 2 'cat (lambda () 5))

What will this expression return when evaluated? First we must notice that it isn't a special form. Being a normal list expression, we know that the first element must be a procedure, and the rest are expressions which will be evaluated to become the actual parameters of the procedure.

To determine the result of evaluating this procedure, we need to know the return value characteristic of the procedure. By looking up the procedure 'list' in Scheme's specification, we find out that it is a primitive procedure which takes zero or more arguments of any type and returns a list data type. So what data type should we expect from evaluating this expression? A list of data.

Will the actual parameters cause any errors in this expression? The list procedure takes any type of data, and we find only numbers, symbols, and procedures as its actual parameters. These fit the acceptance of any type of data perfectly.

Okay, what if we are given a homework problem that puts question marks in a list that will be evaluated, and it looks like this:

(??? 4 '(1 3 6))

Is there any way to tell what the ??? have to represent? Let's see! Could it be a special form? It's possible, and we can't tell by just looking at this expression. We can see that it is highly unlikely that it is a special form by finding out which forms it could fit. The two forms that should come to mind are DEFINE and IF ('if' can lack the alternative, but will return an unspecified value if the predicate is false). DEFINE can be quickly rejected by noticing that we'd have to bind something to the number '4'. This is illegal and would produce an error. What about IF? Although possible, using IF with a predicate that was a number instead of a #t or #f value is unlikely. This tells us that we should treat this list as a normal form.

Given that this list is being evaluated as a normal form, what can we say about it? The first element "must" evaluate to a procedure and the following elements must evaluate to the actual parameters of the procedure. Now we know the ??? must be a procedure, but what are the procedure's characteristics? Well, the procedure takes two actual parameters, the first evaluates to a number and the second to a list of numbers. We don't know if the return value has to be anything special because it's not used. It's also impossible to tell what the procedure must do to the two given actual parameters. The final conclusion would be that it must be a procedure that takes two arguments (we can't define what the arguments "have to be" since we don't know how they are used).

- Analyzing Procedures

Being able to determine what a group of expressions do is also important. Let's characterize the simple procedure given:

(define (map fn lst)
  (if (equal? lst '()) '()
      (cons (fn (car lst)) (map fn (cdr lst))) ))

The best way to approach this procedure is by assuming nothing. This means we should try to determine what data types are going to be used in the parameter list and return value.

Let's start with determining the data type of the formal parameter 'fn'. We need to ask ourselves about where and how it is used in the procedure. The first occurance is in the expression (fn (car lst)). What can we tell about what the symbol 'fn' must be bound to by looking at this expression? It's the first element of the list to be evaluated... This means it must evaluate to a procedure! How many parameters does this procedure require? Since the list has only one element other than the procedure, it will have one parameter. Now how about the type of data the parmeter takes? By looking at the expression which defines the parameter's value, (car lst), we see that it must be the first element, the car, in a pair represented by the symbol 'lst'. We cannot tell that it has to be any special value. We can see that the return value of 'fn' is being stored in a pair, but we also cannot tell what type of value it will be.

Now let's finish determining the data type of 'lst'. While determining the type of 'fn', we discovered that 'lst' pointed to a pair with some element in its car that the procedure 'fn' could take as its parameter. Looking at the base case predicate expression (equal? lst '()), we have further evidence that this is a pair that makes up a list. Observing the expression (map fn (cdr lst)) shows that (cdr lst) must return a value that is the same type as 'lst'. We can now be confident that 'lst' makes up a list of data that 'fn' can be applied to. (Note that the cdr of a list is always another list, unless the list is an empty list.)

The base case evaluates to an empty list. This result tells us that the return value is most likely a list of something. To find out what it is a list of, we must look at the other possible return values. The second possible return value is created by evalutating (cons (fn (car lst)) (map fn (cdr lst))). We should notice that the cons pair constructor can form lists if the first actual parameter is a value in the list and the second actual parmater is a list of more values. The first actual parameter is found by evaluating (fn (car lst)). This tells us that the elements in the list will be the same type of data as returned by the procedure 'fn'. The second actual parameter is formed by evaluating (map fn (cdr lst)). Considering that we've already determined that this 'map' procedure returns a list of values, this cons must also construct a list. Our final conclusion is that the 'map' procedure has a return type of "a list of elements of the type returned by the procedure 'fn'."

What does the procedure do? Let's break it into parts. If it's given an empty list, the base case, we get an empty list back. We now continue on looking at the rest of the cases in order. If it's not an empty list, it becomes a list who's first element is the result of applying 'fn' to the first element of 'lst' and ending with 'map' applied with the same procedure 'fn' to the rest of 'lst'. Simply, this returns a list with all of the values of applying 'fn' to each element in 'lst'.