Scheme Tutorial
(a rough guide for CS486 students)

Scheme at Waterloo

There are two useful Scheme systems at on undergrad.math. One is the Scheme->C system. This an implementation of the Scheme language by Digital Equipment Corporation. There are two programs sci and scc. sci is an interpreter, and scc generates compiled code (by translating the code to C). Warning scc can be very slow to run.

Another Scheme system available on some of the machines is MIT Scheme. This is the program scheme. This system has the advantage that it has a built in compiler, thus it can be a faster way to write your programs. Additionally, it can be installed on a PC. The home page for MIT Scheme is http://www-swiss.ai.mit.edu/scheme-home.html.

Note that evaluating the expression (exit) exits the Scheme system.

The Scheme Report (5) is the definitive reference for the Scheme language.

Introduction to Scheme

Case
Scheme is case sensitive only in strings and character constants.
Comments.
Any characters on a line that follow a semicolon ";" are ignored.
Arithmetic expressions.
These are evaluated in a uniform manner. There is no complex precedence between operators, instead every thing is represented in "prefix" form and the operators can take an arbitrary number of arguments.
```
 (+  2  2) ;compute the sum of 2 and 2
 ==> 4

 (* 2 3 4) ;compute the product of 2 3 and 4
 ==> 24
```
Evaluation Procedure
In its simplest form Scheme evaluates an expression by the following rules.
1. To evaluate a symbol we take its value. Numeric symbols like 0, 1, 2, 2.3, etc. have the same value as their symbolic representation.
```
     
   2.1 ; evaluate to the value of the symbol "2.1" which is
       ; predefined to be equal to the number 2.1.
    
   x   ; evaluate to the value of the symbol "x"
   ==> ERROR.
       ; This causes an error as x is UNDEFINED. Type Ctrl-D to get
       ; out of the debugger.

   (define x 2)
    ==> X
       ; This sets the value of the symbol x to be the value of the
       ; symbol 2. This means that the value of x becomes the number 2.
       ; NOTE. Symbols like numbers that have a predefined value cannot
       ; have their value reset.
   x
   ==> 2
       ; Now x has a value.

   +
   ==> #*PROCEDURE*
       ; Other symbols besides the numbers have predefined values. These
       ; symbols often have as their value predefined procedures.
```
2. To evaluate a list, i.e., something within brackets (...) we find the value of the first element of the list. This element's value must be a PROCEDURE. We then apply this procedure (function) to the list of arguments computed by obtaining the value of (evaluating) each of the other elements of the list.
```
  (+ 2 2)
  ==> 4
      ; apply the function associated with "+" to the result of
      ; evaluating "2" and "2".

  (+ (* 2 2) (* 3 3))
  ==> 13
      ; apply the function associated with "+" to the
      ; result of evaluating "(* 2 2)" and "(* 3 3)".
```
Hence, we have a direct way, via function nesting to express a particular order of evaluation.
There are three important points:
1. Many languages make a distinction between a statement like x = 2 + 2, and an expression like 2 + 2. Statements have effects, but they do not return values. In Scheme there is no such distinction, every expression returns a value and some expressions also have effects, but even these expressions return a value.
2. The lexical rules for Scheme are much simpler than the rules for other languages. Only parenthesis, quote marks (single, double, and backward), spaces, and the comma serve to separate symbols from each other. Hence, x=a*y+3 is evaluated to be a single symbol, not seven different tokens as in most other languages.
```
 (define x=a*y+3 2)
 ==> X=A*Y+3      
     ; We have just defined the symbol with name "X=A*Y+3" to have the
     ; value 2

 (* x=a*y+3 3)
 ==> 6
     ; This symbol behaves just like any other symbol.
 
```
3. Scheme has no need to use a symbols to delimit statements. Expressions are always delimited by parenthesis. Hence the semicolon is used simply to mark the beginning of a comment, and blank lines are allowed in the middle of expressions.
```
 (+ 2 ; this is ignored
    3 ; as is this and the blank lines below
 
    4 ; ) however this close parenthesis is also ignored

 )    ; now the expression ends and it is parsed as (+ 2 3 4)

 ==> 9
```
Symbolic Computation
Scheme is designed to manipulate lists of symbols: LIST Processing.
```
  
 (append '(Pat Kim) '(Robin Sandy))
 ==> (PAT KIM ROBIN SANDY)
```
1. "append" appends together two lists of names.
2. Quote (') is a special function (it is equivalent to (quote ...)). It is special because it does not evaluate its argument. It returns its unevaluated argument as its value. Thus when we evaluate the arguments to append ('(Pat Kim) and '(Robin Sandy)) (remember the evaluation procedure given above), we are in fact evaluating (quote (Pat Kim)). This results in the value (Pat Kim), i.e., the value returned is the unevaluated argument. So append receives two lists as arguments.
```
 '(Pat Kim)
 ==> (PAT KIM)
 
```
3. Quote can be applied to any expression. It returns that expression instead of evaluating it:
```
 'John
 ==> JOHN
 '(John Q Public)
 ==> (JOHN Q PUBLIC)

 John              
 ==> ***** JOHN Top-level symbol is undefined
     ; ERROR: John is not a bound variable (i.e., the symbol JOHN has
     ; not been assigned a value.

 (define John "A Jolly Good Fellow")
 ==> JOHN
     ; give John a value.
    
 (John Q Public)
 ==> ***** EXEC Argument value is not a function: JOHN
    ; ERROR: John has a value but its value is not a function. Hence,
    ; Scheme does not know how to evaluate the expression.

 (quote (john q public))
 ==> (JOHN Q PUBLIC)
    ;Using a "'" is simply shorthand for calling the function quote.
    ;'expression <==> (quote expression)
```
4. Symbolic computation can be mixed with numeric computations in a uniform way.
```
 (append '(Pat Kim) (list '(John Q Public) 'Sandy))
 ==> (PAT KIM (JOHN Q PUBLIC) SANDY)

 (length (append '(Pat Kim) (list '(John Q Public) 'Sandy)))
 ==> 4
```
There are 4 important points:
1. Scheme attaches no external significance to the objects it manipulates. We can think of (Robin Sandy) as a list of two first names, but to Scheme they are simply two symbols.
2. To do the above examples we had to know that "append", "length", "+", e.g., are defined functions in Scheme. Scheme provides a collection of standard procedures, that are listed in the Scheme report. To learn Scheme you have to learn some set of these functions as well as learning the basic rules for forming expressions and determining what they mean.
3. Symbols in Common Scheme are not case sensitive. You can input in mixed case, but Scheme always converts all characters to uppercase, except for string expressions (see the language's Lexical Conventions in the Scheme report).
4. A wide variety of symbols are allowed inside symbols, numbers, letters, and other punctuation marks like "+" or "!". So you can use names like "$=>Yen" to name functions instead of dollars-to-yen. However, as always, symbol names should be informative with respect to their usage.
Variables
1. Besides predefined symbols like "2" we will in general want to assign values to symbols. There is one function for doing assignment: set! (CONVENTION: usually functions that modify symbol values are names that end with "!". Similarly functions that evaluate to true or false (predicates) are given names that end in "?")
```
 (define p)
 (set! p '(John Q Public))
 ==> (JOHN Q PUBLIC)
    ; sets the symbol "P" to have as its value the list
    ; (JOHN Q PUBLIC).
```
2. The Scheme standard does not define a return value for set. So do not write expressions like:
```
 (define q)
 (set! q (set! p 'John))
 ==> JOHN
    ; ERROR: Works in Scheme-to-C (the system you are using) but NOT
    ; PORTABLE.

 (set! x 10)
 (+ x (length p))
 ==> 13
    ; equal to 10 + 3
```
3. The Scheme standard also requires that a variable be defined prior to being able to set! it. Note that some Scheme systems do not require this. A set! can be done on an undefined variable. But to do so is also non-portable.
Special Forms
1. Note that set! violates the evaluation rules. In particular, it does not evaluate its first argument, instead it uses the symbol name directly.
2. Although the evaluation process we discussed above is the one normally used by Scheme there are a few special symbols that are treated differently. set! is one of these.
3. We have already seen other special forms that evaluate in a different way from the standard. quote, and define are two of the special forms we have already seen. quote does not evaluate any of its arguments, and define does not evaluate its first argument.
Lists
1. append: join a collection of lists, all arguments must be lists.
```
 (append '(a b c) '(d e f) '(g h i))
 ==> (A B C D E F G H I)
```
2. length: compute the length of a list
```
 (length (append '(a b c) '(d e f) '(g h i)))
 ==> 9
```
3. list: form a list of the arguments, which might be lists of symbols.
```
 (list 'a 'b 'c)
 ==> (A B C)
     ; The arguments to list can also be lists, giving us lists of
     ; lists.

 (list '(a b) 'c 'd)
 ==> ((A B) C D)
```
4. We can access parts of the list.
```
 (set! p '(John Q (the Public)))
 ==> (JOHN Q (THE PUBLIC))

 (car p)
 ==> JOHN
    ; return the first element of a list.
   
 (cdr p)
 ==> (Q (THE PUBLIC))
    ; return the rest of the list, i.e., all of the list except for the
    ; first element.

 (cadr p)
 ==> Q
    ; return the second element of the list.

 (caddr p)
 => (THE PUBLIC)
   ; return the third element
   ; note that this element is itself a list.

 (cadddr p)
 ==> ***** CAR Argument not a PAIR
   ; Tried to get the fourth element, but list only has 3 elements.
```
  car gets the first element, cdr get the rest of the list. There are 28 predefined compositions of these functions where, e.g., caddr is the function that applies cdr then cdr then car. See the predefined functions listed in the Scheme report.
  
  EXERCISE 1.
  We can make things easier for ourselves by defining functions with more reasonable names to access elements of lists. For example, we can define the function first to return the first element of a list with the definition
```
 (define (first x) (car x))
==> FIRST
```
  Similarly we can define
```
 (define (rest x) (cdr x))
==> REST
```
  This syntax defines the value of the symbol first to be a function of one argument. The function body (the second item in the define) is simply to apply car to the argument x. Similarly we can define
```
 (define (rest x) (cdr x)))
```
  to return the rest of the list excluding the first item.
```
 (first p)
 ==> JOHN
```
  To Do: Define the additional functions second, third, fourth, fifth, sixth, seventh, eighth, ninth, tenth and eleventh to return the respective items from a list. Test your functions. Your functions should utilize the predefined c...r functions explained in the reference manual to he maximum extent possible. In particular, you should minimize the number of nested function calls in your definition.
5. We can build more complex lists
```
 (set! p '(JOHN Q PUBLIC))
  ==> (JOHN Q PUBLIC)

 (cons 'Mr p)
 ==> (MR JOHN Q PUBLIC)

 (cons (first p) (rest p))
 ==> (JOHN Q PUBLIC)
    ; Note that this always returns the same expression as p.

 (set! town (list 'Anytown 'Canada))
 ==> (ANYTOWN CANADA)

 (list p 'of town 'may 'have 'already 'won!)
 ==> ((JOHN Q PUBLIC) OF (ANYTOWN CANADA) MAY HAVE ALREADY WON!)

 (append p '(of) town '(may have already won!))
 ==> (JOHN Q PUBLIC OF ANYTOWN CANADA MAY HAVE ALREADY WON!)

 p
 ==> (JOHN Q PUBLIC)
```
  cons stands for construct, it takes an element (E) and a list (L) and constructs a new list whose first is element is E and whose rest is L.
  Note that append, cons, and list generate new lists. The original list p remains unchanged.
New Functions
1. Just like other values a symbol can have a "function" as its value. There are number of ways to generate a "function" that be used as the value for a symbol. The easiest is to use a special form of "define". However, "define" is simply short hand for setting a symbol to have as its value a lambda expression.
2. See the Scheme Report for an description of the the different forms of define. But the one that is most useful for now is the form
```
  (define (variable formals) body)
```
  This form defines variable to have a function as its value. That function takes the list of arguments formals and evaluates body (a sequence of expressions) with formals bound to the passed parameters and returns the value of the last expression evaluated in body.
3. Say names are represented as lists of the form (first-name [middle-name]* last-name) where the list may include any number (including zero) of middle-names. We could write a function to return the first name as follows:
```
 (define (first-name name)
    (first name))
 ==> FIRST-NAME
```
  [Note that "first" was defined above.]
  For example:
```
 (set! p '(John Q Public))
 ==> (JOHN Q PUBLIC)
 (first-name p)
 ==> JOHN
 (first-name '(Wilma Flint))
 ==> Wilma

 (set! names '( (John Q Public) (Malcolm X) (Admiral Grace Murray
                Hopper) (Spot) (Aristotle) (A A Milne) (Z Z Top) (Sir
                Larry Olivier) (Miss Scarlet)))
 ==>((JOHN Q PUBLIC) (MALCOLM X) (ADMIRAL GRACE MURRAY HOPPER) (SPOT)
     (ARISTOTLE) (A A MILNE) (Z Z TOP) (SIR LARRY OLIVIER) (MISS SCARLET))

 (first-name (first names))
 ==> JOHN
```
4. When dealing with lists, recursive functions that traverse down the list are often a convenient and efficient way of performing some computation. For example, say we want to obtain a list of all first names from a list of names.
```
 (define (get-first-names name-list)
   (if (null? name-list)
       '()
       (cons (first-name (first name-list))
             (get-first-names (rest name-list)))))
 ==> GET-FIRST-NAMES

 (get-first-names names)
 (JOHN MALCOLM ADMIRAL SPOT ARISTOTLE A Z SIR MISS)
```
  This function works by recursing down name-list. If name-list is the empty list '(), then return that, else grab the first-name of the first element of the name-list and cons it onto the front of a recursively computed list of first names from the rest of the name-list. Conceptually the list gets build from the bottom up as we return from a sequence of function invocations. In fact, the Scheme interpreter (and compiler) is tail recursive, so functions that end by calling themselves are in fact computed via iteration not recursion.
EXERCISE 2
Assuming that names are represented as above, i.e., lists of the form (first [middle]* last), where there may be any number of middle names (i.e., 0 or more). Define the Scheme function last-name that will obtain the last name from a name.
Using Functions
The above function get-first-names can easily be generalized. One of the key features of Scheme is that it treats functions like any other value. In particular they can be passed and returned from other functions. Here is a more general form of get-first-names
```
 (define (map-names fnc name-list)
   (if (null? name-list)
       '()
       (cons (fnc (first name-list))
             (map-names fnc (rest name-list)))))
 ==> MAP-NAMES
```
This function takes as an extra argument the function to be applied to each name. It returns a list of the values computed by this function, one for each element of the name-list. So our previous function get-first-names can be duplicated with the call
```
(map-names first-name names)
 ==>(JOHN MALCOLM ADMIRAL SPOT ARISTOTLE A Z SIR MISS)
   ; first-name is evaluated. Its value is a function that is passed to
   ; map-names. 
```
In fact this ability to apply a function to every item of a list is so common that there is a predefined function in Scheme called "map" that does exactly this. (See map in the Scheme report). So we could accomplish the same with:
```
 (map first-name names)
 ==> (JOHN MALCOLM ADMIRAL SPOT ARISTOTLE A Z SIR MISS)
```
The map function is a function that takes a function and a list, and returns a new list that is the result of applying the function to every element of the list individually.
Note that if we had used the expression
```
 (map 'first-name names)
 ==>***** APPLY Argument is not a PROCEDURE: FIRST-NAME
```
We would get an error inside of map as instead of passing a function we would be passing simply the symbol first-name.
map can also be applied with functions taking multiple arguments:
```
 (map - '(1 2 3 4))
 ==> (-1 -2 -3 -4)
     ;apply unary minus.

 (map - '(1 2 3 4) '(1 2 3 4))
 ==> (0 0 0 0)
     ;apply binary minus

 (map + '(1 2 3) '(1 2 3) '(1 2 3))
 ==> (3 6 9)
     ; apply + with 3 arguments.
```
In general map takes an n-ary function and n lists. It applies the function to the n first elements of the lists, then to the n second elements of the lists, etc. All of the lists must be the same length. It returns a list containing the values of the function evaluations.
Conditionals
Our version of first-name does not handle titles very well! Say we want a version that ignores titles like ADMIRAL, SIR, MISS, etc.
First we could define the list of symbols we consider to be titles:
```
 (define *titles*
   '(Mr Mrs Miss Ms Sir Madame Dr Admiral Major General))
 ;  
 ;  A list of titles that can appear at the start of a name
```
The convention is to give special variables that will act as global parameters names that start and end in *.
Now we can give first-name a new definition using another special form the if form which looks like:
```
 (if test then-part [else-part])
```
As in all if's the test is evaluated, if it returns a true value, the then-part is executed and its value returned as the value of the if expression. Otherwise, if the else part is present, it is executed.
By the Scheme standard only the value #f counts as false, every other Scheme value counts as true (including the empty list '() and the symbol NIL, both of which in count as false in other lisp dialects).
```
 (define (first-name name)
  ; Select the first name from a name represented as a list.
  (if (member (first name) *titles*)
      (first-name (rest name))
      (first name)))
```
Now the new "first-name" function gives
```
 (map first-name names)
 ==> (JOHN MALCOLM GRACE SPOT ARISTOTLE A Z LARRY SCARLET)

 (first-name '(Madame Major General Paula Jones))
 ==> PAULA
```
Note that first-name is defined recursively. If the first element of the list is a member of the list of titles, it peels off that element and calls itself again on the rest of the list. In this way it can peel off Madam Major General before returning PAULA in the above example.

Tracing
We can find out more about the execution sequence of first-name by tracing it. This is accomplished by calling the trace function:

 (trace first-name)
 ==> (FIRST-NAME)

Now we obtain

 (first-name '(john q public))
 (FIRST-NAME (JOHN Q PUBLIC))
 ==> JOHN
 JOHN
 
 (first-name '(Madame major general paula jones))
 (FIRST-NAME (MADAME MAJOR GENERAL PAULA JONES))
   (FIRST-NAME (MAJOR GENERAL PAULA JONES))
     (FIRST-NAME (GENERAL PAULA JONES))
       (FIRST-NAME (PAULA JONES))
       ==> PAULA
     ==> PAULA
   ==> PAULA
 ==> PAULA
 PAULA

This provides calling information every time first-name is called.

  
(untrace first-name)

Turns tracing off.

Higher Order Functions
One of the strengths of Scheme is that functions can not only be called, they can also be manipulated like every other object. For example, we can define a function that takes another function as an argument: a higher order function:
We define "map-append" that takes two arguments, a function, and a list, and maps that function over the list _appending_ together all of the results. (Note that since we are using append we have to ensure that the function passed always returns lists, as append only takes list arguments.)
```
 ;Apply fn to each element of the list and append the results
 (define (map-append fn the-list)
   (apply append (map fn the-list)))
```
What is apply?
```
 (apply + '(1 2 3 4))
 ==> 10

 (apply append '((1 2 3) (a b c)))
 ==> (1 2 3 A B C)
```
Basically, apply is used to apply a function to its arguments when those arguments are contained in a list. (Generally, such a list is the result of some other computation.) So map-append first does a map. This applies fn to every element in the-list and produces a list of results. If fn is a function that returns a list, we will get a list of lists. Hence, when we apply append to this list of arguments (each of which itself a list, which is correct since append requires lists as arguments), we will get a final list containing all of the elements in the individual sublists. E.G.
```
 (define (self-and-double x) (list x (+ x x))) 
 
 (self-and-double 3)
 ==> (3 6), returns a list as required by map-append!

 (map self-and-double '(1 10 300))
 ==> ( (1 2) (10 20) (300 600) )

 (map-append self-and-double '(1 10 300))
 ==> ( 1 2 10 20 300 600)
```
Consider the following problem:
Given a list of elements, return a list consisting of all of the numbers in the original list and the negation of those numbers. E.g., the input (testing 1 2 3 test) would produce the output (1 -1 2 -2 3 -3)
```
   
 (define (numbers-and-negations input)
   ;Given a list, return only the numbers and their negations.
   (map-append number-and-negation input))

 (define (number-and-negation x)
   ;If x is a number return a list of x and -x, else the empty list.
   (if (number? x)
       (list x (- x))  ; note apply unary minus to x
       `()))

 (numbers-and-negations '(testing 1 2 3 test))
 ==> (1 -1 2 -2 3 -3)
```
Here is an alternate definition of map-append which builds up the list one element at a time instead of calling mapcar:
```
 (define (map-append fn the-list)
  ;Apply fn to each element of the-list and append the results.
  (if (null? the-list)
      '()
      (append (fn (first the-list))
              (map-append fn (rest the-list)))))
```
Unnamed functions
So far every function we have used has been either predefined or defined via define which associates a name/symbol with a function definition. However, define is simply shorthand for setting the value of a symbol to be a lambda expression.
```
  (lambda parameter-list function-body)
```
A lambda expression is simply an expression that evaluates to a procedure. Hence it is appropriately used as the first element of an expression. In standard Scheme evaluation the value of the symbol/expression appearing in the first position of a list is used as a function to apply to the remaining elements of the list. All procedures are in fact the result of evaluating lambda expressions.
```
 ((lambda (x) (+ x 2)) 4)
 ==> 6   ;apply +2 to the argument 4
```
The procedures that arise due to evaluating lambda expressions can be treated just like any other value. They can be stored in data structures, passed to procedures, returned as values from procedures, etc. A few more examples:
```
 (map (lambda (x) (+ x x))
         '(1 2 3 4 5)) 
 ==> (2 4 6 8 10)

 (map-append (lambda (l) (list l (reverse l)))
          '((1 2 3) (a b c)))

 ==> ((1 2 3) (3 2 1) (A B C) (C B A))
```
Why lambda's? Why not simply provide a name for every function as other languages require you to do?
1. It allows the programmer to avoid cluttering up the program with superfluous names. Just as it is often clearer to write (a+b)*(c+d) as an expression rather than invent variables like temp1 and temp2 to hold (a+b) and (c+d), so it can be clearer to define a function as a lambda expression rather than inventing a name for it.
2. More importantly, lambda expressions make it possible to create new functions at run time. This is a powerful technique not possible in most programming languages.

Other Data Types:
Strings are enclosed in double quotes. They evaluate to themselves

 "abc"
 ==> "abc"

There are a set of predefined functions for dealing with strings.

 (string-length "abc")
 ==> 3

 (string #\a #\b #\c)
 ==> "abc" ;creates a string from its character constant arguments.

 (string-append "abc" "def")
 ==> "abcdef"

 (string->list (string-append "abc" "def"))
 ==> (#\a #\b #\c #\d #\e #\f) ;return a list of the characters.

Summary The Execution model for Scheme
1. Every expression is either a list or an atom.
2. Every list is evaluated to be either a special form expression or a function application.
3. A special form expression is defined to be a list whose first element is a special form operator. The evaluation of the expression depends on the particular special form operator. We have seen
```
  
  define
  set!
  quote    (')
  if
  lambda
```
4. A list is evaluated by first evaluating the arguments and then applying the value of the first element to the values of the rest of the elements of the list.
5. A symbol evaluates to the most recent value that has been assigned to that symbol (via "set!" for example).
6. A nonsymbol atom evaluates to itself. These include numbers and strings, and others.
What makes Scheme Different
One can argue that the features listed below are good, but there are also arguments that these are bad. You can decide on your own as your experience with Scheme increases.
1. Built in support for lists: Lists are a very versatile data structure. They can be defined in any language, but Scheme makes them easy to use. Scheme also provides vector data structures.
2. Automatic Storage Management. Scheme programmers don't need to keep track of memory allocation.
3. Dynamic typing: Scheme is not a strongly typed language. This makes generic functions that operate on many similar types easier to write in Scheme.
4. First-class Functions: A first-class object is an object that can be used anywhere and can be manipulated in the same ways as any other kind of object. In C and Pascal, it is possible to pass functions to other functions, but functions are not first-class objects. It is not possible to create new functions while the program is running, nor is it possible to create anonymous functions without giving them a name.
5. Uniform Syntax. No complex precedence rules and other structure.
6. Interactive Environment. Because it is interpreter based one can dynamically redefine functions or other pieces of the program without recompiling the rest of the program. But most importantly one can test out functions, and expressions interactively without having to write "stubs" to call these functions as in "C".
7. Extensibility. Because of the uniform syntax and other features it is easy to define your own language on top of Scheme.

More about Scheme

cond
is one of the most used control structures in Scheme:
```
   (cond (test expressions)
         (test expressions)
         ...)
```
The test's are evaluate one by one, the first one that evaluates to a true value causes the expressions to be evaluated. The value of the last of these expressions is returned as the value of the cond special form. If no expressions are present the value of the test is returned. A final else condition is allowed, (or you can simply set the last test expression to #t).
Two other useful control structures are:
```
  (and a b c)          ===   (cond (a (cond (b c))))
   ;  
   ;  evaluate a, if non-nil evaluate b, if non-nil evaluate c, etc. 
   ;  
  (or a b c)           ===   (cond (a) (b) (c))
   ;  evaluate a then b then c stopping if one is non-nil
```
Do not use and and or for anything other than testing a logical condition, it's bad style! E.g.
```
 (and (> n 100)
      (princ "N is large.")) ; yuck!

 (or (<= n 100)
     (princ "N is large."))  ; YUCK!!!

 (cond ((> n 100)
        (princ "N is large.")) ; ok.
```
Scope
1. Scheme is statically scoped. That is, the value of a variable is determined by the value of that variable associated with a lexically apparent binding of that variable. E.g.,
```
  (define x 2) ;Top level defines are lexically apparent to all
               ;other levels.
               
  (define (test1 x)
     (+ x x))  ;The top level x in this procedure has been hidden by
               ;the parameter x.
               
  (define (test2 y)
     (+ x y))  ;The top level x is not hidden so we have access to the
               ;top level.
               
  (define (test3 z)
     (+ yy z))  ;No yy defined at top level or at this level, an
                ;error.
 (test1 3)
 ==> 6

 (test2 4)
 ==> 6
 
 (test3 4)
 ==> error.
```
2. Variables with local scope. Often we want to define a variable with local scope, e.g., inside of a procedure we might want to use a local variable.
  let is used to define a local variable which has the scope of the body of the let expression.
```
    (let ( (variable init) (variable init) ... )
           body...)
```
  E.g.,
```
 (let ((x 40)
       (y (+ 1 1)))
    (+ x y))       
 ==> 42
```
  let is equivalent to defining parameters to an anonymous function, so the following is equivalent
```
((lambda (x y) (+ x y)) 40 (+ 1 1))
```
  First, all of the values are evaluated, and then they are bound to the variables, and finally the body is evaluated using those bindings. Note that with the standard let the new local variable values are not available for the initializations of the other variables. E.g.
```
 (let ((x 2) (y 3))
   (* x y))
 ==> 6

 (let ((x 2) (y (+ x 3)))
   (* x y))  
 ==> error x undefined when trying to initialize y.
 
```
  Also, note that lets can be nested, and then scope obeys the rule of "use the innermost" value. E.g.,
```
 (let ((x 2) (y 3))
    (let ((x 7)
          (z (+ x y)))
      (* z x)))
 ==> 35
```
  In this example, z is set to 2 + 3, as x in z's initialization does refers to the outermost x. When (* z x) is evaluated, however, the x refers to the innermost x (= 7).
3. Nested definitions. A function can have internal functions. There are two ways of doing this.
```
 (define (test*+ x y)
    (let ((fn* (lambda (a b) (* a b))))
       (fn* (+ x y) (+ x y))))

 (test*+ 2 3)
 ==> 25
```
  In this form we have used a let to define a local variable. The value of that variable happens to be a function. A syntactically cleaner method is to use internal defines.
```
 (define (test*+ x y)
   (define (fn* a b) (* a b))
   (fn* (+ x y) (+ x y)))

 (test*+ 2 3)
 ==> 25
```
  However, the nested definitions cannot call other nested definitions in their bodies. To overcome this difficult you would need to use the let form described above, but with the special let letrec, see the Scheme report.
Iteration.
Recursive functions that are tail recursive, i.e., the last executed expression is to call themselves, are guaranteed to be compiled into iterative functions. Scheme provides an iteration construct, but in fact it is simply a syntactic device that converts the expressions to recursion. Nevertheless, it is sometimes useful to think about things iteratively. The iteration construct is do
```
  (do ((variable1 init1 step1)
       ...)
      (test expr)
   body ...)   
```
The do initialize all of the local variables in the first list using the init expressions to determine their initial value. It then evaluates test if the result is #f then the expressions of body are evaluated one by one. Then each variable is set to the result of evaluating the step expressions, and we try the test again. When test evaluates to a true value, do returns the value of expr. E.g.
```
 (set! x '(1 2 3 4 5))
 (do ((y x (cdr y))
     (sum 0 (+ sum (car y))))  ; two local variables, y and sum.
   ((null? y) sum))            ; test, and empty body.
    
==> 15
```
Utilizing tail recursion.
Recursion is natural in Scheme. A common form of recursion is to recurse down a list doing something to first and passing rest to the recursive call. Recursion stops when the function is passed an empty list, e.g., to compute the length of a list recursively
```
 (define (length1 list)
    (if (null? list)
      0
      (+ 1 (length1 (rest list)))))

 (length1 '(1 2 3 4 5 6 7 8 9 0))
 ==> 10
```
However in this form each recursive call of length1 requires the allocation of memory on the stack. We have to keep information about the current invocation of the function as well as recurse.
However the following version of length is tail recursive. It does not need to keep any information in the current invocation, but simply passes all of the necessary information to the recursive call. Tail recursive functions are always optimized by Scheme. In particular, the interpreter can release any memory allocated for the original call before making the recursive call.
```
 (define (length2 list)
   (define (tailr-length list len-so-far)
     (if (null? list)
         len-so-far
         (tailr-length (rest list) (+ 1 len-so-far))))
   (tailr-length list 0)) 
 
 (length2 '(1 2 3 4 5 6 7 8 9 0))
 ==> 10
 
 (length2 '())
 ==> 0
```

Equality
There are 3 tests for equality in Scheme, each one being more liberal than the next:

 (eq? 'x 'x)
 ==> #t
           ; test for objects with the same machine address. 
           ; Symbols are always eq? if they have the same name.

 (eq? 1023 1023)
 ==> ??     ; #t in Scheme-to-C, but NOT required in the standard.
           ;   the same machine address so they are identical.

 (eq? 1024.0 1024.0)
 ==> #f     ; #f in Scheme-to-C floats do not have the same machine
           ; address.

 (eqv? 1024.0 1024.0)
 ==>  #t    ; the next level of equality tests for "eq?"
           ; numeric equivalence, and a few other forms of equivalence.

 (eqv? '(x) '(x))
 ==> #f     ;lists are stored at different locations even
           ; if they have the same structure. Hence they are
           ; not "eq?" nor are they "eqv".

 (equal? '(x) '(x))
 ==> #t     ;equal? recursively checks for equal structures. (don't use
           ;on circular structures.

 (equal '(0.1) '(0.1))
 ==> #t     ;equal? is stronger than eqv?

 (eq? "abc" "abc")
 ==> #F

 (eqv? "abc" "abc")
 ==> #F
 
 (equal? "abc" "abc")  ;equal? also does string equality.
 ==> #T

I/O
Input into Scheme is very easy as the programmer has a complete lexical and syntactic parser available. The parser is called read and is used by the Scheme interpreter itself. When it is called it will read and return a single Scheme expression. Hence, if you can design your application so that it reads Scheme expressions they your input worries are over. In cases where Scheme-expressions are inadequate read-char can read characters.
One can set up input and output ports that are attached to files. read, for example can take a port argument. Besides the Scheme function display you will probably find the format (unfortunately both MIT and Scheme-to-C have different versions of format, see the specific documentation listed on the Scheme resources page.

EXERCISE 3.

Trees can be represented as recursive list structures. For example, the list

 ((1 2) 3 4)

can be viewed as representing the tree


              |
       --------------------
       |      |           |
     -----    3           4
     |   |
     1   2

In such structures we can walk the tree by doing recursion. We can detect when we reach a leaf node by using the predicate pair?

pair?returns #t if its argument is a cons cell (leaves are not pairs?). Note that in this structure only the leaves of the tree store useful information.

To Do:Write a recursive function called

 print-tree

Which takes a list and returns a string that contains the leaves of the tree from left to right, with no separators. See the description of

 (format #f ...)

and the description of (string-append ...) in the references contained in the Scheme resources page. Use the format specifier ~a to output the leaves.

Your function should handle null terminated branches properly, i.e., by outputting the empty string in their place.

Examples: your function should produce the following results

 (print-tree '())
 ==> ""

 (print-tree 'a)
 ==> "A"

 (print-tree '((1 2) (3 4)))
 ==> "1234"

 (print-tree '((1 2 ()) (3) 4))
 ==> "1234"

Scheme Tutorial (a rough guide for CS486 students)

Scheme at Waterloo

Introduction to Scheme

EXERCISE 1.

EXERCISE 2

More about Scheme

EXERCISE 3.

Scheme Tutorial
(a rough guide for CS486 students)