Although Scheme provides quite a few procedures, there are many more it doesn't provide. This isn't a problem because programmers can define their own procedures using lambda expressions. The format of a lambda expression is:

LAMBDA ::= (lambda PARAMETERS BODY)

The first input to lambda is simply a list of symbols called parameters:

PARAMETERS ::= (SYMBOL ...)

The body of a lambda expression is a parameterized expression:

BODY ::= PARAMETERIZED-EXPRESSION

A parameterized expression is a Scheme expression that may contain parameters from the parameter list. For example, here's a new procedure that computes |x - y|, the distance between two real numbers x and y:

(define dist (lambda (x y) (abs (- x y))))

The parameters are x and y, and the body is the parameterized expression: (abs (- x y))

Unlike ordinary expressions, a parameterized expression can't be evaluated until the parameters are replaced with appropriate Scheme values called arguments. This happens when the procedure appears as the operator in an application. The arguments are the values of the operands.

For example, assume the following definitions have been made:

(define num1 30)
(define num2 -14)

To evaluate the application:

(dist (+ num1 8) num2)

the Scheme evaluator (1) evaluates dist, (2) evaluates the operands (+ num1 8) and num2, (3) replaces x and y in the body of dist by the operand values, the arguments 38 and -14. This produces the expression: (abs (- 38 -14)). Finally, (4) since this expression no longer contains parameters, it can be evaluated to produce the ultimate answer, 52:

> (dist (+ num1 8) num2)
52

Some people feel the format of a definition involving a lambda expression is too complicated. For this reason many Scheme implementations provide an alternative format called a procedure block, which drops the lambda operator and combines the procedure name and parameters into a single list called the header:

PROCEDURE-BLOCK ::= (define HEADER BODY)
HEADER ::= (PROCEDURE-NAME PARAMETER ...)

Here is the definition of the distance procedure using a procedure block:

(define (dist x y) (abs (- x y)))

Although we will use procedure blocks, there are places where it is still necessary to use lambda expressions. Readers should develop the ability to translate quickly between the two forms.

Let's work through another example. Comparing truncated numbers using = or zero? can be dangerous due to rounding errors. Assume the following definitions have been made:

(define (square z) (* z z))

(define num
   (- 1 (+ (square (sin 3)) (square (cos 3)))))

A fundamental trigonometric identity tells us num should be 0, but Scheme seems to believe differently:

> (zero? num)
#f
> (= num 0)
#f

When truncated numbers are combined, rounding errors can accumulate to produce significant errors. For example, the actual value of num is a tiny but positive real number:

> num
1.11022e-16

A predicate is any procedure that returns a Boolean value: #t or #f. Scheme predicates conventionally have names ending with a question mark. For example, the name big? suggests the procedure returns #t if its input is big, and #f if it isn't. The only exceptions to this convention are the not predicate and the primitive predicates that compare numbers: =, <, >, <=, and >=. (Older implementations of Scheme allow =?, <?, >?, <=?, and >=? as synonyms for these procedures.)

We want a predicate that determines if two numbers are close; following Scheme's convention, let's name this procedure close? The definition of close? can take advantage of the dist procedure defined earlier:

(define (close? a b) (<= (dist a b) _delta))

Where _delta is a constant representing our error tolerance. For now we can set its value to 10^-20.

(define _delta 1e-20)

If close? is the inexact analog of =, then the inexact analog of zero? should be called small?:

(define (small? z) (close? z 0))

When it encounters the application (small? num), the Scheme evaluator replaces z by the value of num in the parameterized body of small?

(close? 1.11022e-16 0)

Next, 1.11022e-16 replaces a and 0 replaces b in the parameterized body of close?:

(<= (dist 1.11022e-16 0) _delta)

Before the comparison can be made, 1.11022e-16 replaces x and 0 replaces y in the body of dist:

(abs (- 1.11022e-16 0))

Since there are no parameters in this expression, it can be fully evaluated. Its value replaces the application of dist in the body of close?:

(<= 1.11022e-16 _delta)

Notice that _delta is not a parameter, it is a constant defined in the global environment. Therefore, this expression can be fully evaluated to produce the final answer, #t:

> (small? num)
#t

Why did we choose to call our error tolerance _delta? Recall from calculus that epsilon and delta are the conventional names of small, positive reals, but then why not choose delta rather than _delta as a name?

The name _delta at least contains the name delta, and if a user defines a constant named delta, it will have no impact on the behavior of small?. On the other hand, if a user defines a constant called _delta (presumably the chance this will happen is small):

(define _delta 100)

then small? no longer works:

> (small? num)
#f

The definitions of small?. close?, dist, and _delta can be placed in a file called math.scm. The expression:

(load "math.scm")

can be placed at the top of any file of definitions that need them.

Suppose we want to define a procedure called pipe-volume that computes the volumes of pipes closed at both ends by hemispherical caps:

(define (pipe-volume len rad) ???)

How should we begin? A top-down strategy is suggested by the Modularity Principle:

The pipe is built out of three pieces: a cylinder and two hemispherical caps. Glued together, the caps form a sphere having the same radius as the cylinder. This suggests we can naturally decompose the procedure into a sum of volumes:

; = volume of length len & radius rad capped pipe
(define (pipe-volume len rad)
   (+ (cylinder-volume len rad)
      (sphere-volume rad)))

Programs should not be needlessly difficult to understand. To achieve this goal experienced programmers follow three basic literacy principles:

Returning to our procedure, we discover the supporting procedures, cylinder-volume and pipe-volume are not pre-defined. We'll have to provide our own definitions. We can consult a Geometry book to find the formulas for the volumes of a cylinder and a sphere:

Translating the first formula into Scheme gives:

; = volume of length len & radius rad cylinder
(define (cylinder-volume len rad)
   (* len (circle-area rad)))

(define four-thirds-pi (* (/ 4 3) pi))

Pi is often predefined. If not, it can be defined by:

(define pi (acos -1)) ; since (cos pi) = -1

Translating the second formula into Scheme gives:

; = volume of radius rad sphere
(define (sphere-volume rad)
   (* four-thirds-pi (cube rad)))

; = area of radius rad circle
(define (circle-area rad)
   (* pi (square rad)))

To finish we only need to define square and cube:

; = z^2
(define (square z) (* z z))

; = z^3
(define (cube z) (* z z z))

Compare the definitions above with the following equivalent, but inefficient, hard to understand, and poorly structured definition:

(define (pipe-volume i x) (+
      (* i pi x x) (* 2
(/ 2 3) x x x)))

We can make this definition even harder to understand by decomposing it into incoherent subtasks:

(define (pipe-volume a b) (+
      (* (helper1 a b) b)
(* (helper2 b) b b)))

Where the helper1 and helper2 procedures compute incoherent mathematical functions that only have meaning in the context of the volume procedure:

(define (helper1 u v) (* u pi v))
(define (helper2 l) (* 2 (/ 2 3) l))

In applicative Scheme the only tools for building procedures are application and abstraction (i.e. lambda expressions). Although we will learn in Chapter Eight that this is all we need, building procedures with such simple tools is like making furniture with a Swiss Army knife, possible, but challenging.

In this chapter we restrict ourselves to applicative Scheme. Our purpose is to wean readers away from statement sequencing, the principle program-building tool provided by languages like Pascal, FORTRAN, and C. In the next chapter we will begin adding to our tool kit.

A coercion is a procedure that transforms members of one domain into equivalent members of another domain, where the meaning of "equivalent" is subject to interpretation and debate. By convention, the name of a Scheme coercion usually has the form:

domain->range

Where "domain" indicates the input domain, "->" means "to", and "range" indicates the output domain. Scheme provides ten basic coercions:

In addition, Scheme provides four procedures for coercing real numbers into integers:

and procedures that coerce exact numbers into inexact numbers and back again:

The best way to remember these coercions is to remember the following coercion map:

> (string->number "532.678")
532.678
> (number->string 532.678)   ; 10 = default radix
"532.678"
> (number->string 26 2)      ; 2 = optional radix
"11010"
> (string->number "1A" 16)   ; 16 = optional radix
26
> (string->symbol "cat")
cat                  
> (symbol->string 'cat)
"cat"
> (list->string '(#\c #\a #\t))
"cat"
> (string->list "cat")
(#\c #\a #\t)
> (list->vector '(42 #t "hello"))
#(42 #t "hello")
> (vector->list #(42 #t "hello"))
(42 #t "hello")
> (char->integer #\a)
97               ; 97 = ASCII code for #\a
> (integer->char 97)
#\a

The coercions from reals to integers are subtly different. Assume r is any real number, then:

The differences between these procedures are tricky when r is negative:

> (floor -4.5)
-5               ; = largest int ≤ -4.5
> (truncate -4.5)
-4               ; = int part of -4.5
> (ceiling -4.5)
-4               ; = smallest int ≥ -4.5
> (round -4.5)
-4                ; = closest (even) int to -4.5

Here are some sample calls to the coercions between exact and inexact numbers. Unfortunately, these coercions don't always yield the expected result:

> (inexact->exact .5)
1/2
> (exact->inexact 1/2)
.5

We can define our own coercions by composing these coercions. For example, the following procedures coerce character vectors into symbols and vice-versa:

; = symbol made from a vector of chars
(define (vector->symbol char-vector)
   (string->symbol
      (list->string (vector->list char-vector))))

; = char vector made from a symbol
(define (symbol->vector symbol)
   (list->vector
      (string->list
         (symbol->string symbol)))

The data flow structures of these procedures can be viewed as pipelines formed by composed procedures:

MILE, YARD, FOOT, INCH ::= REAL

There are six basic coercions between these domains, these three:

; = # yards in m miles
(define (mile->yard m)
   (* 1760 m))   ; 1 mile = 1760 yards

; = # feet in y yards
(define (yard->foot y) (* 3 y))

; = #inches in f feet
(define (foot->inch f) (* 12 f))

together with their inverses: inch->foot, foot->yard, and yard->mile. Other coercions can be defined by composing the basic coercions. For example:

; = # inches in m miles
(define (mile->inch m)
   (foot->inch (yard->foot (mile->yard m))))

A palindrome is any string which is the same spelled forward or backward (upper and lower case letters aren't distinguished). For example, "Rotator", "YrekaBakery", and "RaceCar" are palindromes. How can we define a predicate that detects palindromes?

; = #t, if string is a palindrome
(define (palindrome? string) ???)

If we had a procedure for reversing strings:

; = reverse of string
(define (string-reverse string) ???)

we could use it to reverse palindrome?'s input string, then compare the result with the original input string using string-ci=?:

; = #t, if string is a palindrome
(define (palindrome? string)
   (string-ci=? string (string-reverse string)))

Scheme does provide a procedure for reversing lists:

For example:

> (reverse '(a e i o u))
(u o i e a)

Unfortunately, Scheme does not provide procedures for reversing strings and vectors, but these are easily defined using our coercions. For example:

; = reverse of string
(define (string-reverse string)
   (list->string (reverse (string->list string))))

Every organism plays a special role in its environment. We think of this role as the organism's purpose or function. Biologists explain an organism's function in terms of its internal organization or structure. Of course function does not always follow structure. Evolution, adaptation, learning, differentiation, and mutation are all examples of the environment imposing new roles on an organism or species that may eventually lead to structural changes.

The structure-function duality is also important in Computer Science and Programming. For a procedure, we identify structure with body and function with purpose. The structure-function duality also applies to data. For example, the structure of a number is its representation: binary, octal, decimal, hexadecimal, etc. The function of a number is its interpretation: the distance between two points on a number line. (Can environment influence function?)

The Abstraction Principle simply states:

This means people should be able to use a procedure or value without knowing how it is implemented. It also means programmers can change the implementation without worrying about breaking user programs.

One technique for hiding the representation of data in a given domain is to present the user with abstract procedures for manipulating domain members. This collection of procedures is called an interface, an abstract data type, or an ADT. Typically, an ADT consists of constructors for building new members of the domain, selectors for dissecting existing members of the domain, and predicates for recognizing domain members.

Following the Abstraction Principle, we will not have much to say about how pairs, lists, vectors, and strings are represented. Instead, we present the constructors and selectors for each domain.

A constructor is a procedure that builds a composite value from its components. Scheme provides six basic constructors. Assume val and vali are arbitrary Scheme values and c and ci are arbitrary Scheme characters:

In addition, some implementations of Scheme provide constructors for complex and rational numbers:

Where n and m are integers (m ≠ 0), and x and y are reals. Here are some sample applications:

> (cons 't #t)   ;
(t . #t)
> (list #f "f" #\f 'f)
(#f "f" #\f f)
> (vector #f "f" #\f 'f)
#(#f "f" #\f f)
> (make-vector 10 0)
#(0 0 0 0 0 0 0 0 0 0)
> (string #\I #\B #\M)
"IBM"
> (make-string #\? 10)
"??????????"
> (/ 4 6)
2/3
> (make-rectangular 3 -4)
3-4i
> (make-polar 3 -4)
-1.960930862590836+2.2704074859237844i

Why do we need constructors? Why can't we replace every call to a constructor by an equivalent literal? For example, why would we write:

(define origin (list 0 0 0))

when we could write:

(define origin '(0 0 0))

Constructors are needed when components aren't known in advance. Compare the following programmer-defined constructors for three dimensional points represented as lists:

(define (make-point1 x y z) '(x y z))

(define (make-point2 x y z) (list x y z))

The second constructor works well:

> (make-point2 0 0 0)
(0 0 0)
> (make-point2 1 2 3)
(1 2 3)

But the first constructor always returns the same incorrect result:

> (make-point1 0 0 0)
(x y z)
> (make-point1 1 2 3)
(x y z)

Why did this happen? Remember, the single quote instructs the evaluator to interpret what follows literally. Thus, the evaluator interpreted the body of make-point1 as a list of three symbols: x, y, and z. Each time make-point1 is called, this same list is returned.

The same problem occurs with vectors, strings, and pairs. Assume the following definitions have been made:

(define x #\a)
(define y #\b)
(define z #\c)

Now compare the following evaluations:

> (vector x y z)
#(#\a #\b #\c)
> #(x y z)
#(x y z)
> (string x y z)
"abc"
> "xyz"
"xyz"
> (cons x y)
(#\a . #\b)
> '(x . y)
(x . y)

A selector is a procedure that returns the component of a composite value at a given position. In a sense, constructors and selectors are inverse operations. Scheme provides five basic selectors:

Where vi is any value, k is any unsigned integer, and ci is any character. Notice the first item in a list, vector, or string has position 0.

In addition, some implementations of Scheme provide selectors for rational and complex numbers:

One violation of the Abstraction Principle has become a tradition among LISP and Scheme programmers. Assume the following definition has been made:

(define vowels '(a e i o u))

Inside the computer vowels is identical to the pair:

(a . (e i o u))

Of course the list (e i o u) is represented as the pair (e . (i o u)), therefore vowels is actually represented as the pair:

(a . (e . (i . (o . (u . ())))))

The point is, we can use car and cdr to extract the head and tail of vowels, and cons to add new elements to the beginning of vowels:

> (car vowels)
a
> (cdr vowels)
(e i o u)
> (cons 'y vowels)
(y a e i o u)

Like all the procedures discussed so far, these procedures are non-destructive. The volatile lists produced by cdr and cons disappeared and vowels remained unchanged:

> vowels
(a e i o u)

Be sure you understand the different behavior of cdr on lists and pairs. The list (a b) is the same as the pair (a . (b)), not the pair (a . b). Therefore cdr returns (b) when applied to (a b), and b when applied to (a . b):

> (cdr '(a b))
(b)
> (cdr '(a . b))
b

Scheme provides some popular compositions of car and cdr. Assume p is any list or pair, then:

If your implementation of Scheme doesn't predefine the combination of cars and cdrs you need, just define it yourself:

(define (cddadr x) (cdr (cdadr x)))

Scheme provides other procedures for searching, appending, and computing lengths of sequences. These are described in detail in Appendix 2.2.    Sequences.

An association list (alist) is a list of pairs called associations or bindings:

ALIST ::= (ASSOCIATION ... )

An association is a pair of the form:

ASSOCIATION ::= (PROPERTY . VALUE)

where PROPERTY is any Scheme value that identifies a type of property (name, height, marital status, etc.) and VALUE is the value of the property (Smith, 6'2", single, etc.)

Association lists are useful for representing records, graphs, and tables. Tables and graphs will be discussed later in the chapter. In this section we consider records.

A record (called a struct in C) represents the relevant properties of a person, place, or thing. We can represent a record as a list of associations in which PROPERTY is a symbol that names the property. For example, a student record might contain the name, social security number, and grade point average of a student:

((name . "Picard") (ssn . 998869999) (gpa . 3.75)))
((name . "Moe") (ssn . 002869999) (gpa . 1.5))
((name . "Spock") (ssn . 905869999) (gpa . 3.9))

We can view student records as a new domain of composite values:

STUDENT
   ::= ((name . STRING) (ssn . INTEGER) (gpa . REAL))

As such, it makes sense to define an ADT (constructors and selectors) for the new domain. The constructor for the student domain expects a name, social security number, and grade point average for input:

; = record representing a student
(define (make-student name ssn gpa)
   (list (cons 'name name)
         (cons 'ssn ssn)
         (cons 'gpa gpa)))

We can use pair and list selectors to implement student selectors:

; = name of student
(define (name student)
   (cdar student))

; = social security number of student
(define (ssn student)
   (cdadr student))

; = grade point average of student
(define (gpa student)
   (cdaddr student))

Since the computer must perform some book keeping work each time a procedure is called, it might be more efficient to define these selectors as synonyms for the single procedures they call:

(define name cdar)
(define ssn cdadr)
(define gpa cdaddr)

Of course we could have used list-ref to select associations. This might have been a better choice, but it is important to gain experience combining car and cdr.

Here are some sample constructions:

(define picard (make-student "Picard" 998869999 3.75))

(define moe (make-student "Moe" 002869999 1.5))

(define spock (make-student "Spock" 905869999 3.9))

and some sample evaluations:

> (ssn spock)
905869999
> (name moe)
"Moe"
> (gpa picard)
3.75

Here are some trivial applications of our selectors and constructor:

; = #t if student's gpa < 2.0
(define (probation? student)
   (< (gpa student) 2.0))

; = result of updating student's gpa to new-gpa
(define (update-gpa student new-gpa)
   (make-student
      (name student) (ssn student) new-gpa))

Note that updating the gpa of a student record involves constructing a new record identical to the old record except for the new gpa.

A procedure that expects each of its inputs to be from a specific domain is called monomorphic. Attempting to apply a monomorphic procedure to inputs from different domains results in a type error. Except for the constructors, all the procedures we have studied so far have been monomorphic.

The body of a polymorphic procedure is completely or partially type independent. In other words, the algorithm doesn't particularly care about the types of its inputs. Therefore a polymorphic procedure appears to work on inputs from a variety of domains. It's easy for programmers to define polymorphic procedures. Here are a few examples. Make sure you understand why they are polymorphic:

(define (id val) val)      ; the identity procedure

(define (always-0 val) 0)

(define (first val1 val2) val1)

(define (second val1 val2) val2)

(define (make-pair val) (cons val val))

Scheme provides several primitive polymorphic predicates which are discussed below.

In addition to the five monomorphic equality predicates:

=, char=?, char-ci=?, string=?, string-ci=?

Scheme provides three polymorphic equality predicates:

eq?, equal?, eqv?

Comparing arbitrary values is controversial because there are two competing notions of equivalence: physical and structural. Two values are physically equivalent if they have the same address in the computer's memory, i.e. if they are literally the same object. Two values are structurally equivalent if they have the same mathematical structure, or, at the risk of oversimplifying, if they look the same when printed by the Scheme interpreter. The eq? predicate tests for physical equivalence, while the equal? predicate tests for structural equivalence.

Predicting when two values are physically equivalent is tricky. Two composite values are not physically equivalent if they are created by separate calls to a constructor. For example, assume the following definitions have been made:

(define vals1 (list 1 2 3))
(define vals2 (list 1 2 3))
(define vals3 vals2)

All three lists are structurally equivalent. In addition, vals2 is physically equivalent to vals3, but vals2 and vals1 are not physically equivalent since they were created by separate calls to the list constructor:

> (eq? vals1 vals2)
#f
> (eq? vals2 vals3)
#t

Structurally equivalent literal values may or may not be physically equivalent depending on the Scheme implementation:

> (eq? '(1 2 3) '(1 2 3))
unspecified
> (eq? 5 5)
unspecified

The empty list, #f, and structurally equivalent symbols are the notable exceptions. These are unique objects in all Scheme implementations:

> (eq? 'cat 'CAT) ; symbols are case insensitive
#t
> (eq? #f #f)
#t
> (eq? '() '())
#t

The eqv? predicate is a hybrid between eq? and equal? For simple values (numbers, Booles, chars, symbols) it tests for structural equivalence, but for composite values (lists, strings, vectors, pairs) it tests for physical equivalence.

The eq? predicate is normally used for comparing symbols. Since #f and the empty list are unique values, Scheme provides special polymorphic procedures for recognizing them:

(not val)   = (eq? val #f)

(null? val)   = (eq? val '())

Although #f is a unique object in Scheme, in most contexts any value other than #f can be used instead of #t. Let's call any value other than #f unfalse. We can design a simple predicate to test for unfalse values:

(define (unfalse? val) (not (not val)))

Another category of polymorphic predicates are recognizers. A recognizer usually has a name like domain? and returns #t if its input belongs to domain, and #f otherwise. There are fifteen primitive recognizers:

Recognizing values can get tricky. Make sure you understand the following evaluations:

> (pair? '(a e i o u))
#t               ; non-empty lists are pairs!
> (pair? '())         
#f               ; but not the empty list!
> (real? 1)
#t               ; all integers are reals
> (integer? 1.0)
#t               ; representation independence
> (integer? 1.1)
#f
> (procedure? '+)
#f               ; '+ is a symbol
> (procedure? +)
#t
> (boolean? '())
#f               ; = #t in PC-Scheme!

Often related data can be organized into a table. For example, the following table represents scores on some recent Star Fleet Academy math tests:

NAME      TEST1      TEST2      TEST3
Picard    92        90       89
Moe       34        37       36
Spock       99       100       99

Each column in the table can be represented by an association list:

(define test1
   '(("Picard" . 92) ("Moe" . 34) ("Spock" . 99)))

(define test2
   '(("Picard" . 90) ("Moe" . 37) ("Spock" . 100)))

(define test3
   '(("Picard" . 89) ("Moe" . 36) ("Spock" . 99)))

In this association PROPERTY is the name of the student and VALUE is the associated test score. The entire table can be represented by an association list of association lists:

(define tests
   (list (cons 'test1 test1)
         (cons 'test2 test2)
         (cons 'test3 test3)))

In this case PROPERTY is an identifier that names VALUE, the table of test scores.

Scheme provides three procedures for searching association lists:

Each expects an association list and a key as input:

Assoc uses equal? to compare keys, while assv uses eqv? and assq uses eq? Here are some sample evaluations:

> (assoc "Moe" test1)
("Moe" . 34)
> (cdr (assoc "Moe" test2))
37
> (assv 'test2 tests)
(("Picard" . 90) ("Moe" . 37) ("Spock" . 100))
> (assv "Moe" test2)
unspecified
> (cdr (assoc "Spock" (cdr (assq 'test3 tests))))
99

The value of (assv "Moe" test2) was unspecified because eqv? was used to compare "Moe" with the "Moe" inside test2. In some versions of Scheme this returns 37, while in other versions #f may be returned.

The graph of a procedure proc is the set of points (x, y) in the plane such that y = (proc x). For example, the graph of the square procedure is the parabola:

{(x, y) | y = x2}

An association list can be used to represent the graphs of procedures with only finitely many inputs. For example, suppose we want to implement a procedure that translates digit names to their corresponding numeric value:

> (string->digit "one")
1
> (string->digit "three")
3
> (string->digit "nine")
9

This procedure only has ten valid inputs: "zero" to "nine". This suggests we could represent its graph as an association list:

(define string->digit-graph
   '(("zero" . 0) ("one" . 1) ("two" . 2)
    ("three" . 3) ("four" . 4) ("five" . 5)
    ("six" . 6) ("seven" . 7) ("eight" . 8)
    ("nine" . 9)))

We can implement the procedure as a simple search of the graph:

; = coercion of string to corresponding digit
(define (string->digit string)
   (cdr (assoc string string->digit-graph)))

Could assv have been used in this definition instead of assoc?

Map and apply are examples of meta procedures because each expects an arbitrary procedure and a list as input:

In the case of apply, the list is treated as inputs to the procedure parameter:

> (apply + '(2 3 4 5))
14
> (apply lcm '(2 3 4 5))
60
> (apply cons '(x 2))
(x . 2)
> (apply append '((1 2 3) (4 5 6) (7 8 9)))
(1 2 3 4 5 6 7 8 9)

Apply is useful when we may not know the procedure or inputs in advance. For example, to compute the average of a list of numbers we divide the sum of the list by its length. But how can we compute the sum of a list of unknown numbers? The solution is to use apply:

; = average of numbers in the list nums
(define (average nums)
   (/ (apply + nums) (length nums)))

As another example, here's a simple predicate that determines if a list of names is sorted:

; = #t if names is sorted
(define (sorted? names) (apply string-ci<=? names))

If map's procedure input expects two or more inputs, then two or more list inputs of equal length must be provided to map:

> (map cons '(1 2 3) '(4 5 6))
((1 . 4) (2 . 5) (3 . 6))
> (map + '(1 2 3) '(4 5 6))
(5 7 9)

Assume test scores are recorded as association lists of the form:

TEST ::= ((STUDENT . SCORE) ... )
STUDENT ::= STRING
SCORE ::= REAL

We can use map with the average procedure defined earlier to compute the average of arbitrary tests:

; = average score of test
(define (test-avg test)
   (average (map cdr test)))

We can use the map procedure to define two useful predicates. Both expect a predicate pred? and a list vals as input.

The all? predicate converts vals into a list of booleans by mapping pred? along vals. #t is returned if #f is not a member of the mapped list:

; = #t if for all v in vals (red? v) = #t
(define (all? pred? vals)
   (not (member? #f (map pred? vals))))

The some? predicate also converts vals into a list of Booleans using map, but returns #t in case #t is a member of the mapped list:

; = #t if some (pred? v) = #t for some v in vals
(define (some? pred? vals)
   (member? #t (map pred? vals)))

The member? predicate is defined using Scheme's member procedure, which is defined in the appendix:

(define (member? val vals)
   (unfalse? (member val vals)))

We can use these predicates to implement many other useful predicates. For example, not all lists can be coerced into strings, only lists of characters. Therefore, it might be useful to have a predicate that determines if a list consists of only characters:

; = #t if all members of list vals are characters
(define (char-list? vals)
   (all? char? vals))

Suppose we need predicate that returns #t if its input is a string containing a vowel. We can coerce the string into a list, then use some? with the vowel? predicate defined earlier:

; = #t if string contains a vowel
(define (contains-vowel? string)
   (some? vowel? (string->list string)))

All numbers can be combined by addition (+), subtraction (-), multiplication (*), and division (/). The addition and multiplication operators can combine arbitrarily long sequences of numbers:

> (+ 1 2 3 4 5 6 7 8 9 10)
55
> (* 1 2 3 4 5 6 7 8 9 10)
3628800

Even a single input or no inputs at all are allowed:

> (+ 2)   ; implicit second input is 0
2
> (* 2)   ; implicit second input is 1
2
> (+)      ; implicit inputs are both 0
0
> (*)      ; implicit inputs are both 1
1

Division and subtraction normally combine pairs of numbers:

> (/ 5 3)
5/3
> (/ 5.6 7.9)
.7088607594936708
> (- 3 8.2)
-5.199999999999999

With one input division and subtraction compute multiplicative and additive inverses respectively (i.e. 1/z and -z):

> (- 5.2)
-5.2
> (/ 7)
1/7
> (/ 7.0)
.142857142857143

Of course all four operations can combine numbers from any of the number domains:

> (+ 2 3/5 4.9 5+6i 3e2)
312.5+6i
> (* 2 3/5 4.9 5+6i 3e2)
8820.+10584.i
> (/ 3/5 4+2i)
3/25-3/50i
> (- 3/5 5+6i)
-22/5-6i
> (- 4-3i)
-4+3i
> (/ 4+2i)
1/5-1/10i

All numbers can be compared using Scheme's = and zero? predicates. Assume zi and z are numbers:

The following predicates are based on the usual ordering of the real numbers. Assume ri and r are reals:

Order predicates are restricted to reals because the complex numbers don't have a "usual" order.

An ordered domain is any domain that comes equipped with a natural ordering. REAL is not Scheme's only ordered domain. STRING and CHAR also have natural orderings derived from the ASCII codes of characters.

Assume ci is a character, ci <A cj means the ASCII code of ci is less than the ASCII code of cj, and ci =A cj means the ASCII code of ci is the same as the ASCII code for cj. (Note: the order of ASCII codes for letters and digits agrees with the usual alphabetic order.) Scheme provides the following predicates for comparing characters:

Scheme provides similar predicates for comparing strings. Assume si is a string, si <s sj means si is a prefix of sj, or if ci is the first character in si that's different from the corresponding character cj in sj, then ci <A cj. If si and sj are identical, then we write si =s sj:

Scheme also provides case insensitive (ci) versions of these predicates:

Here are some sample evaluations:

> (string=? "HeLlO" "hElLo")
#f
> (string-ci=? "HeLlO" "hElLo")
#t
> (char-ci<? #\a #\Z)
#t
> (char<? #\a #\Z)
#f
> (char<? #\tab #\# #\2 #\5 #\? #\Z #\a #\rubout)
#t
> (string<? "" " " "a" "aaa" "ab")
#t

Of all the number domains only the integers are not closed under division. For example, 1 and 2 are integers, but 1/2 is not. This makes the question which integers divide a given integer critical. Scheme provides seven basic procedures for determining various divisibility properties. Assume n, m, n1, ..., nk are integers:

These procedures require further explanation. Number Theory (i.e. Arithmetic) begins with the long division algorithm every child learns in elementary school, but which can be stated more pretentiously as a theorem:

Scheme provides the quotient and remainder procedures for computing q and r given m and n as inputs:

> (quotient -14 3)
-4
> (remainder -14 3)
-2

We can use Scheme's odd? and even? predicates to determine if an integer is or isn't divisible by two, or, more generally, we can use the remainder procedure to determine if any integer divides another:

; = #t if m divides n
(define (divides? m n)
   (zero? (remainder m n)))

We could express this as a Scheme procedure:

; = #t if m is congruent to n mod k
(define (congruent? m n k)
   (divides? (- m n) k))

A basic theorem regarding congruence is:

For example:

Scheme provides the modulo procedure for computing n given m and k:

> (modulo -14 -3)
-2
> (modulo -14 3)
1

The modulo procedure can be useful for implementing modular arithmetic, i.e. arithmetic that "wraps around" when answers get too big.

; = m + n mod k
(define (mod+ m n k) (modulo (+ m n) k))

; = m * n mod k
(define (mod* m n k) (modulo (* m n) k))

; = m - n mod k
(define (mod- m n k) (modulo (- m n) k))

; = m/n mod k
(define (mod/ m n k) (modulo (quotient m n) k))

For example, suppose we want to add the hours on a military clock (i.e. 0 HRS to 23 HRS). We use the "modulo" implementations of +, *, and -:

; = time h hours after time t
(define (hours+ t h) (mod+ t h 24))

For another example, binary arithmetic is arithmetic restricted to the domain of domain of binary values, called bits:

BIT ::= 0 | 1

Curiously, 1 is its own additive and multiplicative inverse. I.e. 1 + 1 = 0 and 1 * 1 = 1. We can implement bit versions of +, *, -, and /:

= binary sum of bits b1 and b2
(define (bit+ b1 b2) (mod+ b1 b2 2))

Here are some sample evaluations:

> (hours+ 9 10)
19
> (hours+ 9 19)
4
> (hours+ 20 20)
16
> (bit+ 1 1)
0

Obviously the modulo and remainder procedures are very similar. In fact:

|(remainder m n)| = |(modulo m n)|

(remainder m n) takes the sign of m, while (modulo m n) takes the sign of n.

A common divisor of an integer sequence n1, n2, ..., nk is any positive integer n that divides each number in the sequence. I.e. for each i:

> (divides? ni n)
#t

The greatest common divisor of n1, n2, ..., nk is the largest of all the common divisors of n1, n2, ..., nk. Scheme provides a procedure for computing greatest common divisors:

> (gcd 32 48 -60)
4
> (gcd 20 30 40)
10

Two integers are relatively prime if their greatest common divisor is 1. We can implement this definition as a Scheme predicate:

; = #t if m & n are relatively prime
(define (rel-prime? m n)
   (= 1 (gcd m n)))

A common multiple of an integer sequence n1, n2, ..., nk is any positive integer n that can be divided by each number in the sequence. I.e. for each i:

> (divides? n ni)
#t

The least common multiple of n1, n2, ..., nk is the least of all the common multiples of n1, n2, ..., nk. Scheme provides a procedure for computing least common multiples:

> (lcm 32 48 -60)
480
> (lcm 20 30 40)
120

Logarithms and exponents play an important role in growth and decay problems. Scheme provides procedures for computing logs and exponents to the base e, where e is the irrational number approximated by e = 2.718281828459045.

If e isn't a predefined constant, we can define it ourselves as follows:

(define e (exp 1))   ; since e1 = e

Some implementations of Scheme provide a procedure for computing exponents to an arbitrary base:

Unfortunately, there is no corresponding procedure for computing logarithms to an arbitrary base. Instead, we must define our own using the formula:

Translating this formula into Scheme is simple. We call it logt to remind us of its relationship with expt:

; = log y base x
(define (logt x y) (/ (log y) (log x)))

Of course exponents and bases can be decimals, ratios, even complex numbers:

> (expt 2 3)
8
> (expt 9 1/2)
3.0000000000000004
> (expt 27 (/ 1 3))
2.9999999999999996
> (expt 2+3i 1+1i)
-.8636068988831277+1.0368893969147763i
> (expt 25 1/2)
4.999999999999999
> (expt 2 1000)
107150860718626732094842504906000181056140481170553360744375038837035105112493612249319837881569585812759467291755314682518714528569231404359845775746985748039345677748242309854210746050623711418779541821530464749835819412673

The last example shows some implementations of Scheme use multiple-precision arithmetic.

Scheme also provides a square root procedure:

Amazingly, this procedure even works on negative numbers:

> (sqrt -1)
+i

We don't really need a square root procedure. Recall that the nth root of z is z1/n. We can use this formula to define a procedure for computing nth roots:

; = z^(1/n)
(define (nth-root z n) (expt z (/ n)))

We can compute the value V of an investment of P dollars invested for n years at an annual interest rate of r compounded annually using the formula:

V = P(1 + r)n

Translating this into Scheme is easy using expt:

; = value of $p investment at rate r after n periods
(define (value p r n)
   (* p (expt (+ 1 r) n)))

Trigonometric functions are important for modeling harmonic motion (vibration, oscillation, etc.). Scheme provides the usual assortment of trigonometric procedures. All of these procedures assume angles are measured in radians:

The atan procedure accepts one or two inputs. Assume z is a complex number and x and y are real numbers:

We can easily define csc, sec, and cot procedures:

; = csc of z radians
(define (csc z) (/ (sin z)))

; = cot of z radians
(define (cot z) ???)   

; = sec of z radians
(define (sec z) ???)   

If pi isn't a predefined constant in the implementation of Scheme we are using, we can define it ourselves as follows:

(define pi (acos -1))   ; since (cos pi) = -1

Scheme provides several groups of procedures for analyzing, combining, and dissecting sequences.

Appending two sequences means concatenating them into a single sequence. Scheme provides primitive procedures for appending lists and strings, but not vectors (this is left as an exercise). Assume valsi is a list and stri is a string:

Here are some sample calls:

> (string-append "Is" tan" "bul")
Istanbul
> (append '(a) '(e) '(i) '(o u))
(a e i o u)

Of course we can use cons to add an element to the beginning of a list, but Scheme provides no procedure for adding an element to the end of a list. However, we can implement such a procedure using append:

; = result of adding val to end of vals
(define (cons-last val vals)
   (append vals (list val)))

Notice that it was necessary to coerce val into a list before applying append. Unlike cons, append expects all of its inputs to be lists.

Scheme provides procedures for computing lengths of strings, vectors, and lists:

Where vals is a list, vec is a vector, and str is a string. Here are some sample evaluations:

> (string-length "Hello")
5
> (length '((1 2 3) (4 5 6)))
2
> (vector-length #(a e i o u))
5

Why doesn't Scheme provide a procedure for computing lengths of pairs?

The tail of a sequence is the sequence less some of its initial members. For example, the tails of the string "orange" are:

"orange, "range", "ange", "nge", "ge", "e", and "".

The tails of the vector #(a e i o u) are:

#(a e i o u), #(e i o u), #(i o u), #(o u), #(u), and #().

The tails of the list (a e i o u) are:

(a e i o u), (e i o u), (i o u), (o u), (u), and ().

Scheme provides a wide variety of procedures for extracting list tails. We have already seen that the procedures cdr, cddr, cdddr, etc. can be used for this purpose. Some implementations of Scheme also provide a procedure called list-tail that extracts the tail of a list beginning at a given integer position n ≥ 0:

Assume the following definition has been made:

(define vowels '(a e i o u))

Here are some sample calls to list-tail. Remember, the first item of a list is in position 0:

> (list-tail vowels 3)
(o u)
> (list-tail vowels 0)
(a e i o u)
> (list-tail vowels 100)
()

Additionally, Scheme provides three procedures for extracting tails beginning at some specific member:

These procedures all work the same way:

The three procedures differ in the way val is compared to members of vals. Member uses equal?, memv uses eqv?, and memq uses eq? This can lead to some confusion as the next example shows:

> (member "Al" '("Rolf" "Al" "Lars"))
("Al" "Lars")   
> (memq "Al" '("Rolf" "Al" "Lars"))
?               ;"Al" may not be eqv? to "Al" in vals
> (member 'Al '(Rolf Al Lars))
(Al Lars)      ; Al is equal? to a list member
> (member "Al" '(Rolf Al Lars))
#f            ; vals is a list of symbols, not strings
> (memq 'Al '(Rolf Al Lars))
(Al Lars)   ; equal? = eqv? for symbols

People often mistake the member procedures for predicates. This isn't true, but we can use them to define corresponding predicates. The idea is if val is a member of vals, then (member val vals) returns a non-empty list, otherwise it returns #f. Hence:

; = #t if val is in vals
(define (member? val vals)
   (unfalse? (member val vals)))

We can use this predicate to define others. For example, assume the following definition is made:

(define vowels
   '(#\a #\A #\e #\E #\i #\I #\o #\O #\u #\U))

(define punctuation '(#\. #\, #\; #\: #\! #\? #\-))

To determine if a character is a vowel or a punctuation mark, we only need to search the appropriate list:

(define (vowel? char)
   (member? char vowels))

(define (punctuation? char)
   (member? char punctuation))

Oddly, Scheme doesn't provide procedures for extracting the tails of vectors. This is no problem since we can coerce any vector to a list, extract the tail, and coerce the result back to a vector. For example:

; = tail of vec beginning at val
(define (vector-member val vec)
   (list->vector (member val (vector->list vec))))

; = tail of vec beginning at position pos
(define (vector-tail vec pos)
   (list->vector (list-tail (vector->list vec) pos)))

Here are some sample evaluations:

> (substring "Apple" 2 4)
"pl"
> (substring "Apple" 0 3)
"Apl"

Notice that the substring begins with the character in the position indicated by the first position input, but ends with the character one position before the second position input. We can use the sublist procedure to define procedures for extracting prefixes and suffixes of strings:

; = prefix of string ending at position pos - 1
(define (prefix string pos)
   (substring string 0 pos))

; = suffix of string beginning at position pos
(define (suffix string pos)
   (substring string pos (string-length string)))

These procedures can be used to develop predicates that test if one string is a prefix or suffix of another:

; = #t if string2 is a prefix of string1
(define (prefix? string1 string2)
   (string=?
      string2
      (prefix string1 (string-length string2))))

; = #t if string2 is a suffix of string1
(define (suffix? string1 string2)
   (string=?
      string2
      (suffix
         string1
         (- (string-length string1)
            (string-length string2)))))

Unfortunately, Scheme does not provide this procedure. How could we define it? We could try to combine the substring procedure with the coercions between lists and strings:

; = sublist between positions start and (end - 1)
(define (sublist vals start end)
   (string->list
      (substring (list->string vals) start end)))

This works pretty well when vals is a list of characters:

> (sublist '(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7) 2 5)
(#\2 #\3 #\4)

But of course doesn't work at all if vals contains non-characters:

> (sublist '(0 1 2 3 4 5 6 7) 2 5)
error: bad input to list->string

Let's start over using the Top Down Approach. We can use list-tail to chop off the unwanted members between position 0 and position start:

(list-tail vals start)

How can we loose the members from position end to the last position of the list? This would be easy if we had a procedure that extracted list prefixes. First, let's be clear about what a list prefix is. A list prefix should be a list consisting of all but a few of the last members of a list. For example, the prefixes of (a e i o u) are:

(a e i o u)
(a e i o)
(a e i)
(a e)
(a)
()

The list-prefix procedure can be specified by:

We can use this to implement sublist. In this case the input to list-prefix will be the tail: (list-tail vals start). We will want to chop off the elements of this list beginning with pos = (end - 1) - start:

; = sublist between positions start and (end - 1)
(define (sublist vals start end)
   (list-prefix (list-tail vals start)
                (- (- end 1) start)))

Unfortunately, Scheme does not provide a procedure for extracting list prefixes. Let's write a procedure to do this. The form of our definition will be:

; = prefix of vals ending at position pos
(define (list-prefix vals pos) ???)   ; stub

Our plan is to reverse the result of applying list-tail to the reversed input list:

(reverse (list-tail (reverse vals) position2))

What should position2 be? How is it related to the position parameter? Observe that an element in position k of a length n list is in position n - (k + 1) of the reversed list. For example, o is in position 3 of vowels, but in position 5 - (3 + 1) = 1 of (reverse vowels). Therefore, if we wish to retain the first k members of an arbitrary input list vals, we will want to retain the last n - (k + 1) members of (reverse vals), where n is (length vals):

; = prefix of vals ending at position pos
(define (list-prefix vals pos)
   (reverse (list-tail (reverse vals)
                      (- (length vals) (+ pos 1)))))

; = result of removing item at position k from vals
(define (remove vals k)
   (append (list-prefix vals (- k 1))
          (list-tail vals (+ k 1))))

How can we insert an item into position pos of a list vals, or replace the item in position pos of vals with a new item:

; = result of inserting item at position pos in vals
(define (insert vals item pos) ???)

; = result of replacing member at
; position pos by item in vals
(define (replace vals item pos) ???)

The arity of a procedure is the length of its parameter list. A 0-ary procedures has arity = 0. Scheme's exit and transcript-off are examples of 0-ary procedures. Unary procedures have arity = 1. Car, cdr, length, abs, and number? are examples of unary procedures. Binary procedures have arity = 2. Cons, eq?, remainder, modulo, apply, and list-ref are examples of binary procedures. A 3-ary procedure has arity = 3. Substring is an example of a 3-ary procedure.

Procedures with higher arities are rare. However, there are some procedures that accept any number of inputs. We call these procedures n-ary procedures. Lcm, gcd, list, string, vector, +, *, <, and max are examples of n-ary procedures.

Scheme provides a mechanism that allows programmers to define n-ary procedures. The last parameter of a procedure is an options parameter if it is preceded by a period. (A space must separate the period and the parameter.) If the number of arguments exceeds the number of parameters, then the interpreter gathers the left-over arguments into a list and binds this list to the options parameter. Otherwise, the options parameter is bound to the empty list.

As an example, let's write an n-ary version of the average procedure:

; = average of all parameters
(define (avg . nums) (average nums))

The avg procedure can be called with any number of inputs:

> (avg 3 4 5)
4
> (avg 5 6 7 8 9)
7

Let's rewrite the rel-prime? predicate defined earlier as an n-ary procedure. Recall, a list of integers are relatively prime if their gcd = 1:

; = #t if all parameters are relatively prime
(define (rel-prime? . ints) (= 1 (apply gcd ints)))

Here are some sample calls:

> (rel-prime? 2 4 6 8 10)
#f
> (rel-prime? 3 5 7 22 13 17)
#t

Although Scheme provides "and" and "or" procedures, they are control structures that won't be introduced until the next chapter. In the meantime, we can define our own versions using the some? and all? predicates defined earlier:

; = #t if all parameters ≠ #f
(define (and? . vals) (all? unfalse? vals))

; = #t if some parameters ≠ #f
(define (or? . vals) (some? unfalse? vals)))

Recall, a value is unfalse if it is different from #f:

(define (unfalse? val) (not (not val)))

For example, we can use our or? predicate to determine if a number b is between two other numbers a and c:

; = #t if b is between a and c
(define (between? a b c)
   (or? (<= a b c) (<= c b a)))

As another example, we can combine apply, or?, and reverse to determine if a list of strings is sorted:

; = #t if parameters are sorted
(define (sorted? . strings)
   (or? (apply string<? strings)
       (apply string<? (reverse strings))))

Here are some sample evaluations:

> (sorted? "cat" "cow" "dog" "rat")
#t
> (sorted? "ray" "fish" "bat")
#t
> (sorted? "cat" "cow" "bat" "dog")
#f

When a Scheme session ends all declared bindings stored in the Global Environment disappear. At the start of the next session the definitions that created these bindings will have to be repeated. This process is simple if the definitions have been saved in a definition file.

A definition file (also called a program file) is a text file containing Scheme definitions. The definitions in a definition file can be loaded into Scheme either using special editor commands or by using Scheme's load procedure. Assume defs.scm is the name of a definition file, then:

Warning: Definition files and transcript files are different. Do not attempt to load a transcript file.

The edit-test-debug cycle describes the structure of a typical Scheme session:

The number of times a programmer loops through the cycle depends on the size of the program being developed. The time it takes to loop through one cycle can range from a few seconds to a few weeks and can depend on the programming environment being used.

Many versions of Scheme allow programmers to switch between the interpreter, an editor, and a debugger without terminating the session.

Solutions to the following problems are to be given in applicative Scheme; do not use procedures or special forms discussed in subsequent chapters. You may use the definitions given in this chapter as well as solutions to other problems in this chapter. (Although you will have to include these definitions in your definition file so you can test your definitions.) You may also define any supporting procedures you need. You are not required to validate inputs, i.e. assume all inputs will be valid. (Input validation begins in Chapter Three.) Be sure to test all your definitions.

Assume the following definitions have been made:

(define x 100)
(define y 200)
(define z 300)
(define dog "dog")
(define graph
   '(("one" . 1) ("two" . 2) ("three" . 3)))

Evaluate the following expressions. If they contain errors, explain them. If their values are unspecified in Essential Scheme, indicate this with a question mark. Use your Scheme interpreter to check your work, but be careful, your interpreter may not be 100% compliant with Essential Scheme.

(eq? "hello" "hello")   (eq? 'hello 'hello)   
(assoc "one" graph)   (assq "one" graph)   
(member "one" graph)   (real? x)
(real? 'x)      (eqv? 5 (+ 2 3))

(pair? '(1 2 3 4 5))
(eq? 5 5)
(char-ci=? #\c 'c)
(+ 2 3 (display (+ 4 1)))
(eq? dog dog)
(eq? dog "dog")
(eq? dog (string #\d #\o #\g))
(eq? 'dog 'dog)
(eq? dog 'dog)
(reverse (vector->list #(2 3 4)))

(reverse (vector->list #(2 3 4)))
(member 'i '(a e i o u))
(member #\i '(a e i o u))
(memq 2 '(1 2 3 4 5))
(string=? dog 'dog)
(string=? dog (string #\d #\o #\g))

(map car '((a . b) (c . d) (e . f)))
(apply cons '((1 . 2) (2 . 3)))
(+ (truncate -4.2)
   (floor -4.2)
   (gcd 4 12 22)
   (lcm 3 4 6))
(eq? (string #\h #\e #\l #\l #\o)
    (string #\h #\e #\l #\l #\o))
(+ (list-ref (list x y z) 0) (list-ref '(x y z) 1))

If Scheme did not provide the string constructor, how could you implement it?

Assume r is any real number. Implement the following procedure:

Hint: use the abs procedure.

If Scheme did not provide modulo, how could you define it? (Hint: You may want to use the sign procedure developed above, and the remainder procedure.

Write a procedure that expects the rate r of return on an investment compounded annually, and returns the length of time required for the investment to double. Do not use the "Rule of 72."

If Scheme did not provide expt, how could you define it?

If Scheme did not provide tan, how could you define it?

The sum of a geometric series of the form ar0 + ar1 + ar2 + ... arn is given by the formula S = a(1-rn)/(1 - r). Implement this as a Scheme procedure.

If n is any unsigned integer, then 1 + 2 + ... + n = the nth triangle number = n(n + 1)/2. Implement this as a Scheme procedure.

As a particle moves faster, its mass increases according to the Lorenz formula:

where v = the velocity of the particle, c = the speed of light, and mrest = the rest mass of the particle. Implement this as a Scheme procedure.

Define the following coercions by composing existing coercions:

Recall the formula for transforming degrees to radians:

Use this formula to define the coercions:

Implement versions of all the trigonometric procedures that assume angles are measured in degrees instead of radians:

(define (degree-sin z) ???)

Define the following coercions. Don't hesitate to compose your own coercions to form new coercions:

kbyte->byte, byte->kbyte      ; 1 kilobyte = 210 bytes
byte->mbyte, mbyte->byte      ; 1 megabyte = 220 bytes
byte->gbyte, gbyte->byte      ; 1 gigabyte = 230 bytes
byte->tbyte, tbyte->byte      ; 1 terabyte = 240 bytes
kbyte->gbyte, gbyte->kbyte

Of course the coercion char->integer does not map digits like #\8 to their corresponding numerical values. Write a Scheme procedure that does:

> (char->digit #\8)
8
> (char->digit #\0)
0

Your procedure should work on computers that encode characters using ASCII codes or IBM's EBCDIC codes.

There are two ways to use vectors to represent a 3x3 matrix like:

Row major form represents M as a vector consisting of three points that represent the first, second, and third rows of M:

#(#(3 2 4) #(1 0 12) #(7 -1 5))

Column major form represents M as a vector consisting of three points that represent the first, second, and third columns of M:

#(#(3 1 2) #(2 0 -1) #(4 12 5))

In the following exercises we will assume matrices are represented using row major form. We will also use the notation Mij to indicate the row i column j entry of M. For example:

M23 = 12

Assume A, B, and C are 3x3 matrices and P is a point, implement the following procedures:

Generalize mat* in the previous exercise so that it multiplies nxn matrices.

Write an n-ary procedure that appends arbitrarily many vectors:

(define (vector-append . vecs) ???)   ; stub

If the graph of a procedure is represented by an association list of the form:

GRAPH ::= ((INPUT1 . OUTPUT1) ... )

then its inverse is represented by the same association list, but with each pair reversed:

((OUTPUT1 . INPUT1) ... )

Implement a reversing procedure that expects an arbitrary alist as input, and returns the inverse alist as a value:

> (graph-reverse '((a . 1) (b . 2) (c . 3)))
((1 . a) (2 . b) (3 . c))

Assume Scheme did not provide truncate. How could you define it?

Implement a procedure that extracts the last element of a list::

> (last '(a e i o u))
u

Assume Scheme didn't have a string-ref procedure. How could you implement one?

How could you implement quotient if Scheme did not provide it?

How could you define char<? if Scheme did not provide it?