CS 486/686 Tutorial Notes 
by Bowen Hui, b2hui@logos.uwaterloo.ca

List of Topics to Cover:
========================
Part I - Basics                Part II - Strengths
   0. Starting Scheme            11. Recursion and Tail-Recursion
   1. Various Facts              12. How letrec Works
   2. Form                       13. Procedures as Arguments and Return Values
   3. Procedures              
   4. Define                   Part III - Other Data Types
   5. Conditionals               14. Quoting
   6. Evaluation Rules           15. Pairs and Lists
   7. Example to Sum Up          16. Vectors
   8. Strings and Characters   
   9. Scoping                  Part IV - Topics
  10. Sequencing                 17. Mutation

0. Starting Scheme
------------------
a. The Scheme interpreter for this course is Scheme->C, which is available
   on the undergrad.math machines. Further information and sources about
   this particular implementation of Scheme can be found at:

	ftp://ftp.digital.com/pub/DEC/Scheme-to-C/

b. To run Scheme, type:

	> sci

c. To exit Scheme, type:

	> (exit)

d. Copies of the MAN pages are located in ~cs486/man/manl/ and on-line
   Scheme references are available at:

	http://www-swiss.ai.mit.edu/scheme-home.html

e. The main references for this set of tutorial notes are taken from:

        i. ~cs486/Tutorials/Scheme/
       ii. Manis & Little (1995). _The_Schematics_of_Computation_, Prentice Hall.

1. Various Facts
----------------
a. To evaluate Scheme expressions, either: 
   i.  load a text file that consists of the Scheme expressions 
	> (load "<filename>")
   ii. or type in these expressions at the prompt
	> (+ 1 3)
	...

b. Scheme is case sensitive only in strings and character constants.
   The following are equivalent:
	(define a 9)     
	(DEFINE A 9)
	(DeFiNE a 9)
   but these pairs are not:
	(define x "abc") != (define x "AbC")
	(define a1 #\a)  != (define a2 #\A) 

c. Comments begin with ";". The convention is to use ";;;" to start a
   comment.

d. Scheme uses prefix notation. Here is a sample session:

	> (+ 2 3)                             ;;; prefix notation
	5
	> (+ (+ 1 2) 3)                       ;;; nested argument
	6
	> +
	#*PROCEDURE*
	> i like scheme                       ;;; ERROR
	***** I Top-level symbol is undefined
	(EVAL ...)
	(SCREP_REP ...)
	(READ-EVAL-PRINT ...)

   However, you can do something like the ones below which will be explained
   later:
	> "i like scheme"
	"i like scheme"
	>'scheme
	scheme

e. Only parentheses, quote marks (single, double, backward), spaces, and the
   commas serve as delimiters. For example, 
	x=a*y+3 
   is evaluated as one single symbol.

2. Form
-------
a. Everything in Scheme is a form.
   A form is either a number, or an application with the following syntax:
   (op arg-1 ... arg-n), where "op" is an operator, "arg-i" is the i'th
   argument.

	e.g. 35, 82
	e.g. (+ 1 2 3 4 5)
	      | |_______|
	      op    \-> args

3. Procedures 
-------------
a. A procedure is a lambda form with the following syntax:
   (lambda (arg-1 ... arg-n) <body-form>), where "lambda" is a keyword,
   "arg-i" is the i'th argument passed into the body of the procedure, and
   "<body-form>" is a form (see #2 for the definition of a "form").

	> (lambda (x) (+ x 1))
	#*PROCEDURE#

   In order to evaluate a procedure, we must treat the lambda form as an
   operator and pass in appropriate arguments, like so:
   
	             op
	    |------------------|
	> ( (lambda (x) (+ x 1)) 8)
	9

   8 gets passed in as "x" and (+ x 1) becomes (+ 8 1) which evaluates to 9.
   If the body is constant, then the value of the argument simply gets
   ignored.
	
	> ( (lambda (a) (+ 2 3)) 10)
	5

   What would this evaluate to?
   
	> ( (lambda (a a) (+ 7 a)) 5 6)  
	...?

   Some evaluators would generate an error message because two arguments are
   given the same name and the evaluator gets confused because it doesn't
   know which value of the two arguments should be used inside the body.
   However, some evaluators, such as sci, picks one of the two arguments and
   evaluates the body. Since this style yields unreliable results, one
   should avoid it altogether.

4. Define 
---------
a. To create variables, we can use "define" to bind "<form>" to "<name>".
   The syntax follows: (define <name> <form>)

	> (define a 4)
	> (define b a)
	> b
	4
	> (define sum (+ 4 4))
	> sum
	8
	
b. We already saw how procedures are created in Scheme. If we want to give
   names to these procedures, we simply do the following:
	(define <name> (lambda (arg-1 ... arg-n) <body>))

   which is syntactically equivalent to:
	(define (<name> arg-1 ... arg-n) <body>)

	> (define add1 (lambda (n) (+ n 1)) )

   We have created a procedure named "add1" that takes one argument and
   return its value plus 1. For example:
   
	> (add1 3)
	4
	
   Given the above two syntax for "define", the alternate way of defining
   add1 is: (define (add1 n) (+ n 1))

5. Control Structures
---------------------
This section is pretty obvious, so no explanation is provided. Instead,
there will be a big example at the end to illustrate how the operators are
used.

a. "and"
	(and <condition-1> ... <condition-n>)
b. "or"
	(or <condition-1> ... <condition-n>)
c. "not"
	(not <condition>)
d. "if "
	(if <condition> <then>)
   or
	(if <condition> <then> <else>)
   or
	<condition>       ;;; this is the SAME as: (if <condition> #t #f)

e. see manual for "cond" and "case"

f. Example:
   Write a procedure called happy? that takes two percentages as arguments,
   and returns #t if one of the percentages is a passing grade and both
   percentages are not lower than 30%, and #f otherwise.

   A solution:

    (define passing 50)
    (define min 30)
    (define happy?
      (lambda (mark1 mark2)
	(and (or (>= mark1 passing) (>= mark2 passing))
          (and (not (< mark1 min)) (not (< mark2 min)))
      )))

6. Evaluation in Scheme 
-----------------------
We will go over just the basics of the rules of evaluation in Scheme in
order to know the values that various Scheme forms have.

Although the evaluation rules given here are not complete, the main
advantage to learning these rules is to help us figure out what Scheme is
doing and how we can write and debug programs without (too much) guessing.

a. Every expression returns a value.
b. Some expressions also have side effects.
   e.g. define, set!

c. Assume that evaluation takes place from left to right.
   *** not all interpreters have the same order of evaluation
   *** the importance of this rule will become more apparent when we talk
   about scoping later

d. Numbers: a number evaluates to itself
	> 3
	3              

e. Variables: 
	> (define a 5)                    ;;; "define"s do not evaluate
	> a                               ;;; gets the binded value
	5
	> (define b (+ 3 7))              
	> b                               ;;; evaluates (+ 3 7) as 10 before 
	10                                ;;; binding it to b

f. Procedures
	> (lambda () (display "hello"))   ;;; lambdas evaluate to procedures
	#*PROCEDURE*
	> +                               ;;; primitive procedures
	#*PROCEDURE*
	> (define p1 (lambda () (display "hello")))
	> p1
	#*PROCEDURE*
	> (p1)                            ;;; applying p1
	hello
	
g. Applications
	> ( (lambda (a b) (+ a b)) 4 (- 9 1))
	                                  ;;; must evaluate the arguments 
	                                  ;;; 4 and (- 9 1) before passing them
	                                  ;;; in as "a" and "b"
	  ( (lambda (a b) (+ a b)) 4 (- 9 1))
	                                  ;;; once evaluated...
	  ( (lambda (a b) (+ a b)) 4 8)   ;;; pass them in *in order*
	  (+ 4 8)                         ;;; now apply the value of +
	12

   Whenever Scheme sees a set of brackets, it expects that the form is an
   application. (Recall that everything in Scheme is a form, and a form is
   either a number or an application of the syntax (op arg-1 ... arg-n).)

   A common mistake is having extra sets of brackets:
	> (+ 1 2)
	3
	> (+ (1) 2)
	ERROR - "1" is not a defined operator in Scheme

   Highlight the note that says:
	*Note* Remember: brackets mean application!!!

h. Conditionals
	if  - evaluates <condition>, and then evaluate either the <then> clause
	      OR the <else> clause, but not both
	and - evaluates all <conditions> OR until #f is one of the values
	or  - evaluates all <conditions> OR until #t is one of the values

   For example:
   (if (equal? 4 5) 
    (+ 1 10)
    (+ 0 10))                         

   Only the else clause gets evaluated.

7. Exercises
-----------
Example:
	x = -b + sqrt( b^2 - 4ac )
	    ----------------------
		         2a           
   The positive solution for x can be computed by:
	(define quadp
	  (lambda (a b c)
	    (/ (+ (- b) 
	          (sqrt (- (* b b) (* 4 a c))))
	       2a)))

a. In relativity theory, the factor of time at which an object moves as
   experienced by the observer to that experienced by a stationary observer
   is calculated by the Lorentz formula:

	sqrt( 1 - v /c )

   where v is the object's velocity and c is 299 800 000 m/s. Write a
   procedure called "lorentz" that takes v as an argument and returns the
   factor of time between the two observers.

b. Trace out the steps of how Scheme would evaluate the following:
	> (lorentz 300)

8. Strings and Characters
-------------------------
a. Some useful operators for manipulating strings and characters:

	#\A, #\space. #\newline              ""
	char=?                               "scheme"
	char-ci?                             string=?
	char<?                               ...other equality stuff
	...other equality stuff              string-ref
	char-alphabetic?                     substring
	char-numeric?                        string-append
	integer->char                        string
	char->integer                        make-string

   Again, no explanation is provided here. Check the manuals for their
   syntax and usage.

9. Scoping
----------
a. Three types: let, let*, letrec
   All of which are syntactically equivalent to a lambda statement.

b. The syntax for all three follow the same as the following:
    (LET ( (name-1 form-1) ... (name-n form-n) )
       <body>)
   This statement binds name-i to form-i and then executes the <body>.

   Compare this syntax with that of a lambda statement:
    ((lambda (name-1 ... name-n) <body>) form-1 ... form-n)

   With this kept in mind, let us look at the differences among these three
   types of let statements. Consider:

	> (let ((a (+ 1 1))
	        (b 3))
	   (+ a b))
	5

   We can locally define variables "a" and "b" within the scope of the let
   statement, but once we step outside of the let, variable "a" is
   undefined.

	> a
	ERROR 

   Similarly, if we try to define a variable based on another one within the
   same let statement, an error is generated.

	> (let ((a 2)
	        (b (+ a 3)))
	   (+ a b))
	ERROR

   There are two ways around this problem. The most immediate solution is to
   nest two let statements together. However, when the code gets
   complicated, nesting will make the code less readable. This is where let*
   comes in. Both solutions are demonstrated below:

	> (let* ((a 2)                    > (let ((a 2))
	         (b (+ a 3)))                (let ((b (+ a 3)))
	   (+ a b))                           (+ a b)))
	7                                 7

   In addition to defining local variables, let statements can define local
   procedures. Here is an example of a procedure called time-in-seconds that
   given the hour, minute, and second of a specific time, will compute the
   number of seconds that specific time converts to. This procedure has two
   "helper" procedures, hTos and mTos, that are defined locally.

	> (define time-in-seconds
	   (lambda (h m s)
	    (let ((hTos (lambda (h) (* h 3600)))
		      (mTos (lambda (m) (* m 60)))
	         )
	     (+ (hTos h) (mTos m) s)
	    )))

   The third type of let statement is letrec, which handles recursive
   procedures. Since we haven't covered recursion, we will come back to
   letrec in part 12.


10. Sequencing 
--------------
a. To ensure that a set of forms get executed in a particular order, use
   "begin" like so: (begin <form-1> ... <form-n>)

	> (if #t 
	   (begin (display "hello")
	          (newline)                 ;;; outputs a carriage return
	          (display "how are you"))
	   (display "goodbye"))
	hello
	how are you

b. Note that lambdas have implicit begins already, so it is not necessary to
   insert a begin statement (although it is not wrong).

	> ((lambda (n) (display n)
	               (display (+ n 1))
	               (display (+ n 2))) 0)
	012

11. Recursion
-------------
a. Other programming languages use loops (for, while, repeat, etc.),
   Scheme uses the notion of calling helper procedures, or calling itself.

b. A simple use of recursion:

    (define notveryuseful
     (lambda (n)
      (if (> n 0)                      ;;; base case
       (notveryuseful (- n 1))         ;;; recursive call
      )))

   This procedure does nothing other than calls itself n times. Here are
   better examples:

   Factorial: n! = n x n-1 x ... x 1

    Code:                              Trace Session:
    (define n!                         > (n! 3)
     (lambda (n)                          (* 3 (n! 2))
      (if (<= n 1)                         (* 3 (* 2 (n! 1)))
       1                                  (* 3 (* 2 1))
       (* n (n! (- n 1)))                (* 3 2)
      )))                              6
   
   Power: a^n = a x a x ... x a (n times)

    Code:                              Trace Session:
    (define power                      > (power 2 5)
     (lambda (a n)                        (* 2 (power 2 4))
      (if (<= n 0)                         ...
       1                                      (* 2 (* 2 (* 2 (* 2 (* 2 1)))))
       (* a (power a (- n 1)))             ...
      )))                              32

   Now, let's define a procedure called mul, which takes two numbers and
   multiplies them. We can view multiplication as a recursion process
   because we can rewrite a x b = a + ... + a (b times).

	Code:                              
	(define mul
	 (lambda (a b)
	  (if (= b 0)
	   0 
	   (+ a (mul a (- b 1))))))

	Tracing:
	> (mul 5 4)
	  (+ 5 (mul 5 3))
	   (+ 5 (+ 5 (mul 5 2))) 
	    (+ 5 (+ 5 (+ 5 (mul 5 1))))           
	     (+ 5 (+ 5 (+ 5 (+ 5 (mul 5 0)))))    
	     (+ 5 (+ 5 (+ 5 (+ 5 0))))
	    (+ 5 (+ 5 (+ 5 5)))
	   (+ 5 (+ 5 10)) 
	  (+ 5 15)
	20

   The problem with mul is speed - mul is very slow because it has to "wait
   around" for the other mul's that it calls. Solution: tail-recursion.
	
   With tail-recursion (TR), we will introduce a helper procedure for mul,
   called mhelper. The actual work that mhelper does is basically the same
   as mul, but we will store the calculated value in a temporary variable
   called acc (stands for accumulator).
 
	Code:                              
	(define mhelper 
	 (lambda (a b acc)
	  (if (= b 0)
	   acc
	   (mhelper a (- b 1) (+ a acc))
	  )))

	(define mulTR
	 (lambda (a b)
	  (mhelper a b 0)))

   Now mulTR serves as an interface to the user and does no computation at
   all. When we trace mulTR, it will be obvious that it is much faster than
   mul.
	
	Tracing:
	> (mulTR 5 4)
	(mhelper 5 4 0)
	(mhelper 5 3 5)
	(mhelper 5 2 10)
	(mhelper 5 1 15)
	(mhelper 5 0 20)
	20

c. Comparing non-tail-recursive definitions to tail-recursive definitions:

    Multiplication: a x b

    (define mul                        (define mulTR
     (lambda (a b)                      (lambda (a b)
      (if (= b 0)                        (mhelper a b 0)))
       0
       (+ a (mul a (- b 1)))           (define mhelper
      )))                               (lambda (a b acc)
                                         (if (= b 0)
                                          acc
                                          (mhelper a (- b 1) (+ a acc))
                                         )))

    Sum of Squares: 1^2 + ... + n^2

    (define sumsq                      (define sumsqTR
     (lambda (n)                        (lambda (n)
      (if (= n 0)                        (sshelper n 0)))
       1
       (+ (* n n)                      (define sshelper
          (sumsq (- n 1)))              (lambda (n acc)
      )))                                (if (= n 0)
                                          acc
                                          (sshelper (- n 1) (+ acc (* n n)))
                                         )))

d. Exercise:
   Write a procedure called fib that computes the Fibonacci series. Then
   write a procedure called fibTR that uses tail-recursion to compute the
   series.


12. How letrec Works
--------------------
a. We saw in section 9 that we can use letrec to handle recursive
   procedures but we didn't really know what that means. So now we will
   explain this idea with an example. Suppose we want to write a procedure
   called power that computes x^n which uses a local helper procedure (as
   opposed to the global ones above). Let's try:

	> (define power (lambda (x n)
	   (let (( helper (lambda (x n acc)
	                   (if (= n 0)
		                (helper x (- n 1) (* x acc))))))
	    (helper x n 1))))

   This procedure is syntactically correct, but when we evaluate it:

	> (power 2 4)
	ERROR

   NOTE - Scheme does not complain about the semantic error when we type in
   the definition, it is only when we try to evaluate (power 2 4) that it
   complains. Why? Recall that "define" does not evaluate its arguments
   (cf. evaluation rules in section 6).

   So what is the problem here? Let's convert the helper procedure into a
   lambda form:

   (let ((helper (lambda (x n acc) 
                   (if (= n 0) (helper x (- n 1) (* x acc))))))
     (helper x n 1))

   ( (lambda (helper) (helper x n 1))
     (lambda (x n acc) (if (= n 0) (helper x (- n 1) (* x acc)))) )

   The evaluation rules say that for an application, we need to evaluate its
   arguments first before passing them into the procedure. Here, we try to
   evaluate the form: (lambda (x n acc) (if (= n 0) (helper x (- n 1) (* x
   acc)))), which has helper in it. So the evaluator sees helper, doesn't
   understand it, and generates an error message.

   Would let* help? No, because let* is just like having nested let
   statements and nesting does not solving the problem here.

   Solution - use letrec.
    (define power (lambda (x n)
     (letrec ((helper ...)) 
       (helper x n 1))))

   How does letrec work? What letrec does is it puts an initial dummy value
   (say, #f) as the binding for its arguments. This way, when Scheme
   evaluates the definition of the helper procedure, it won't generate an
   error because it sees a binding for helper. Once the argument is
   evaluated, the value of helper will change to this new definition, so
   when we apply (helper x n 1), it will use this new definition.
	
   It seems like letrec is an improvement on let* and let* is an improvement
   on let. However, consider the problem we had before with let, but this
   time using letrec:
  
	> (letrec ((a (sqrt 3))
	           (b (sqrt a)))
	   b)
	ERROR

   We still get the same problem because the order of evaluation is not
   guaranteed in Scheme.

c. Summary of binding rules:
   GLOBAL:
	define - binds form to name
   LOCAL:
	lambda - binds the k'th form to the k'th name
	let    - binds the k'th form to the k'th name at the SAME time
	let*   - binds the k'th form to the k'th name one by one
	       - strictly evaluates left to right
	letrec - binds the k'th form to the k'th name one by one 
	       - *BUT* does not guarantee order of evaluation!!!
	       - can handle recursion 
	         (uses dummy initial forms and then mutates it)

13. Procedures as Arguments and Return Values
---------------------------------------------
a. The idea of passing procedures as arguments and returning them as values
   is not new to us as the syntax remains unchanged. All we do is think of
   the procedures as variables. Here are some examples of using procedures
   as arguments and returned values:

	> (define add3 (lambda (x) (+ x 3)))
	> (define applyTo3 (lambda (p x) (p x 3)))

   We have defined add3, which is a procedure that takes a number and
   returns the sum of that number plus 3. applyto3 takes a procedure and a
   number as arguments, and passes this number and 3 into that procedure.
   For example:

	> (applyTo3 + 8)
	11

   Here, "p" evaluates to "+" and "x" evaluates to "8", so (p x 3) becomes
   (+ 8 3) => 11. Similarly:
   
	> (applyTo3 - 10)
	7
	> (define applyTo4 (lambda (p) (p 4)))
	> (applyTo4 sqrt)
	2
	> (applyTo4 (lambda (y) (+ y 3)))
	7

   The following example results in an error:
   
	> (applyTo4 (lambda (x y) (+ x y)))

   An error occurs because applyTo4 takes a procedure "p" that takes one
   argument only (in our case, only "4" is passed into "p"). Since the
   procedure (lambda (x y) (+ x y)) expects two arguments, a syntax error is
   generated.

   Returning procedures as values is simple as well. For example:
	
	> (define add-n
	   (lambda (n)
	    (lambda (x)
	     (+ x n))))

   add-n returns a procedure that takes one number, x, as an argument.
   
	> (add-n 5)
	#*PROCEDURE*

   (add-n 5) is a procedure that evaluates to (lambda (x) (+ x 5)).
   To evaluate the body of the inner lambda statement, we need to pass
   numbers into both lambda statements:
   
	> ((add-n 5) 7)
	12

b. Why would we want to do this? Suppose we have a predefined procedure
   called encrypt-string that takes a string and encrypts it.

	> (encrypt-string "aeiou")
	bfjpv

   This encryption method may not be very useful if we don't know how it
   works and cannot systematically reproduce the results. Therefore, one can
   imagine that we may want to supply our own method of encryption. 

   Suppose "right1" is a procedure that takes a string and shifts each
   character one position to the right and the last character wraps around.
   For example:
   
	> right1
	#*PROCEDURE*
	> (encrypt-string right1 "abc")
	bca

   This version of encrypt-string allows us to pass in our own encryptor.

   On the other hand, suppose we have a set of encryptors and we want to
   randomly choose one, we can create a get-random-fcn that randomly selects
   one and returns it.
   
	> (get-random-fcn)
	split-merge
	> (get-random-fcn)
	gibberish
	> (define encryptor (get-random-fcn))

c. Example:
   One way to write encrypt-string is for it to take a procedure, proc, and
   a string, str, and applies proc to every character in str. The code
   follows.

    (define encrypt-string
     (lambda (proc str)
	  (enchelper proc str 0 (string-length str))))

    (define enchelper
     (lambda (proc str pos len)
      (if (>= pos len)
       ""
       (string-append (proc (string-ref str pos))
                      (enchelper proc str (+ pos 1) len))
      )))

d. Exercise (very open question):
   Write out the definition for get-random-fcn that fits the following
   template. To do so, you should look into the Scheme primitives case and
   random.
   
    (define get-random-fcn
     (lambda ()
      ...
     ))

14. Quoting
-----------
a. Two syntax: (quote <form>)
               '<form>

b. Quoting blocks out evaluation. The quote mark instructs Scheme to treat
   its argument as a piece of data without evaluating it.

	> (pat 3)
	ERROR
	> '(pat 3)
	(PAT 3)
	
15. Pairs and Lists (box and arrow diagrams need to be added)
-------------------
a. A pair is a structure that consists of two values. The first value is
   referred to as "the CAR of the pair" and the second is "the CDR of the
   pair".

b. Constructors and Accessors:
   (cons a b) makes a pair with values a, b (assuming a & b are defined)
   (car p)    retrieves the first element in p
   (cdr p)    retrieves the second element in p

	> (cons 1 2)
	(1 . 2)

   The pair is displayed as follows: open bracket, "1" (or whatever is in
   the car), whitespace, dot, whitespace, "2" (or whatever is in the cdr),
   close bracket.

	> (cons (+ 1 2) "bowen")
	(3 . "bowen")

   In the above example, note that the car is 3 and not (+ 1 2).

	> (define x (cons (eq? 0 1) 100))
	(#f . 100)
	> (car x)
 	#f
	> (cdr x)
	100
	> (pair? x)
	#t

   There are shorthands for nesting car's and cdr's as well:
   (cadr p)   = (car (cdr p))
   (caddr p)  = (car (cdr (cdr p)))
   (cdar p)   = (cdr (car p))
   (cddr p)   = (cdr (cdr p))
   (cdaar p)  = (cdr (car (car p)))
   ... etc.

c. Scheme uses a shorthand to display the contents of pairs. Consider:
   
	> (cons (cons 1 2) 3)
	((1 . 2) . 3)         

   which is what we would expect, but:

	> (cons 1 (cons 2 3))
	(1 2 . 3)                                  
	> (cons 1 (cons 2 (cons 3 4)))
	(1 2 3 . 4)                                

   These do not print out as (1 . (2 . 3)) and (1 . (2 . (3 . 4)))
   respectively. It turns out that Scheme has a printing rule to simplify
   the display of this data structure. The rule can be worded as the
   following:

	Scheme prints a pair as (car . cdr)
	unless the cdr is itself a pair, then
	   it prints (car cadr . cddr)
	unless the cddr is itself a pair, then
	   it prints (car cadr caddr . cdddr)
	unless ...

   Another point about the way Scheme prints is with a null "element". For
   now, we will just note that 

	> (cons 1 (cons 2 (cons 3 '())))
	(1 2 3)
	
   returns "(1 2 3)" and NOT "(1 2 3 . ())". (See section 15.e for
   explanation.)

d. With the nesting of pairs, it is easy to see that we can extend the
   concept of a pair into a more complicated data structure.
	
	> (cons (cons 1 2) 3)
	((1 . 2) . 3)
	> (cons (cons 3 7) (cons 4 8))
	((3 . 7) . (4 . 8))
	> (cons 1 (cons 2 (cons 3 (cons 4 5))))
	(1 2 3 4 . 5)

   This leads to a "list".

e. A list is either a null list, or a pair whose cdr is a list. A null list
   is represented as ().

   The reserved word "list" is a constructor in Scheme. Compare "list" to
   "cons":

	> (list a b)
	(a b)
	> (cons a (list b c))
	(a b c)
	> (cons 1 '())
	(1)
	> (list 1)
	(1)
	> (+ (list 1) 2)
	ERROR
	> (list (cons 1 2) 3)
	((1 . 2) 3)

   list? is a predicate similar to pair?.

	> (define a (cons 1 (list 2 3)))
	> (list? a)
	#t
	> (define b (cons (list 1 2) 3))
	> (list? b)
	#f

   We conclude that a list is just a pair where the car of the _last_ cdr is
   a null list.

f. A useful operator is "map" which applies a given function to the rest of
   its arguments. The syntax is: (map <n-ary function> <list-1> ... <list-n>)

    > (map - '(1 2 3))
    (-1 -2 -3)
    > (map - '(1 2 3) '(1 2 3))
    (0 0 0)
    > (map + '(1 2 3) '(1 2 3) '(1 2 3))
    (3 6 9)
    > (map (lambda (x) (+ x x)) '(1 2 3 4 5))
    (2 4 6 8 10)

g. Primitives we should know regarding pairs and lists:
   null?, pair?, list?, cons, car, cdr, append, length, reverse, map,...

   Write a procedure that traverses a list and prints out its elements.
   (Assume that none of the car's are lists as well.)
	
	(define printlist
	 (lambda (ali)
	  (if (null? ali)                   ;;; base case
	   (newline)
	   (begin
	     (display (car ali))            ;;; check that ali is pair first
		 (display "  ")
		 (printlist (cdr ali)))         ;;; recurse on the rest of the list
	  )))

h. Note: append, cons, list -- generate new lists and the original list
   remain unchanged (see example in 15.i).
	
i. Example: 
   Given a list of names such as the following:
   (define names '( (John Q Public) 
                    (Malcolm X) 
                    (Admiral Grace Murray Hopper) 
                    (Spot) 
                    (Aristotle) 
                    (A A Milne) 
                    (Z Z Top) 
                    (Sir Larry Olivier) 
                    (Miss Scarlet) ))
   Write a procedure called get-first-name that returns the first name 
   (i.e. the first element) for all the names in the given name list.

    (define get-first-name
     (lambda (namelist)
      (if (null? namelist)
       '()
       (cons (car (car namelist))
             (get-first-name (cdr namelist))))))

   Earlier, we mentioned that cons generates a new list and the original
   list remains unchanged. So here, get-first-name returns a list that is
   separate from namelist. This means if we were to change the contents of
   the list returned by get-first-name, the change will not affect namelist.

j. Exercises:
   i. Draw the box and arrow diagrams for the following lists:
	(cons 1 2)
	(list 1 2)
	(a b c)
	(a (b . c) d)
	((a . b) . (c . d))
	(a (b) (c . '()) (d e) ((f (g) h) . i))

   ii. Define the Scheme primitive list? according to its recursive
   definition.

   iii. Define a procedure called (get-present <wordlist>) such that when it
   is given a list of (regular) English words in the past tense, it extracts
   the common suffix "ed" and returns a list of words in the present tense.
   For example:

	> (define words (list "snowed" "jumped" "watched" "pointed" "listened"))
	> (define suffix "ed")
	> (get-present words)
	(snow jump watch point listen)

16. Vectors
-----------
Vectors are fairly straightforward, so no explanation is provided.

a. By definition, vectors are a collection of items that have constant
   access time. You should use vectors over lists when the time complexity
   of your program is an issue.

b. Constructors and Accessors:
   (make-vector k x)                     return a new vector of k elements,
                                         if x is given then all k elements
                                         will be set to x by default
   (list->vector <item-1> ... <item-n>)  make a list containing the
                                         evaluated arguments in the given
                                         order
   (vector-ref <vector> k)               get the k'th element of vector

   ... and so forth
   (vector-length <vector>)              returns the length of vector
   (vector->list <vector>)               converts a vector into a list
   (vector-set! <vector> k x)            sets the k'th element of vector to x
   (vector? x)                           returns #t if x is a vector, 
                                         #f otherwise

c. Exercise:
   Write a procedure that counts the number of times "#f" appears in a
   vector.

17. Mutation
------------
a. Scheme passes its variables by value, so when you change the values of
   the variables, they do not get changed "permanently". For example: 
   
	> (define balance 100)
	> balance
	100
	> (- balance 20)
	80
	> balance
	100                                  ;;; PROBLEM!!!

   In this example, we see that balance does not get updated appropriately.
   (Although it is probably to our benefit that we can keep withdrawing
   money from our bank accounts and still have $100 in it. We just have to
   make sure that we do not deposit any money into it!)

   What we want is something like the following:

	> (set! balance (- balance 50))
	> balance
	50
	> (set! balance (+ balance 20))
	> balance
	70

   With "set!", we can write a procedure called withdraw and use it as
   follows:

	> (define withdraw
	   (lambda (amount)
	    (set! balance (- balance amount))))
	> (withdraw 70)
	> balance
	50

b. Exercise:
   Write a procedure called deposit that behaves like withdraw but it adds
   money to the variable balance.

c. Other mutation functions:
	(set-car! <pair> <new>)      
   which mutates the value stored in the car of <pair> to the value in
   <new>, and <new> can be any Scheme form,
	(set-cdr! <pair> <new>)      
   which mutates the value stored in the cdr of <pair> to the value in
   <new>, and <new> can be any Scheme form.

   Here are some examples for mutating pairs:

	> (define px (list 1 3 5 7 9))
	> px
	(1 3 5 7 9)
	> (set-car! (cdr px) 0)
	> px
	(1 0 5 7 9)
	> (set-cdr! px '())
	> px
	(1)

d. Note: The variable mutated by set! should be previously defined.

e. Exercise:
   Write a procedure (vleft! <vector>) that shifts all the elements of a
   vector to the left while the leftmost element is "wrapped around" to the
   rightmost position. In other words, the elements a-0,a-1,...,a-n becomes
   a-1,...,a-n,a-0.