Make Your Own Scheme ‘Reference Card’

Gary T. Leavens

September 18, 1995

Introduction

This ‘card’ is based on the subset of Scheme used in Scheme and the Art of Programming by George Springer and Daniel P. Friedman (1989, McGraw-Hill and MIT Press).

The material is organized by chapters, so that you can fill it in as you go through the course. This card is “do it yourself” in the sense that we do not provide all the information for all of

Scheme. The idea is for you to learn by filling in the missing information yourself, following the examples that we do supply. Missing information is only indicated by blank space. You should write in the blank spaces to help your learning.

You may also want to make notes for yourself on this card with other information you find useful, such as describing what things do in words. Another useful thing to do with this card is to reorganize it. For example, you might want to collect the information by types (booleans, symbols, pairs, etc.). You might also try to write down equations relating the operations of the various types.

Syntax Conventions

Scheme keywords and other parts of scheme code are written in a typewriter font; for example, define. Grammatical symbols, which are placeholders for what you write, are written in an italic font; for example, expr.

In syntax, “…” means that instances of the preceding parentheses-balanced grammatical form may occur zero or more times. For example,

(operator operand …)

means that there may be zero or more operands in a procedure call. For example, (no-arg-proc) and (p 1 2) are both ways to instantiate this syntax.

Type Conventions

A type can be thought of as a set of values with certain associated procedures. For example we use “number” as the name of the type of all numbers (both exact and inexact, real and integer) in Scheme. The procedures that work on numbers include + and *.

We write the types of procedures using a notation like (→ (S T U) V), which is the type of a procedure that takes 3 arguments (the first of type S, the second of type T, and the third of type U) and returns a result of type V. For example, + is a procedure of type (→ (number number) number). We use a colon (:) for the phrase “is of type” (or “has type”). For example, we write

+ : (→ (number number) number)

Since Scheme does not do type checking before a program is run, the elements of a list do not all have to be of the same type. Such a list is heterogeneous; a list, all of whose elements are of the same type is homogeneous. We use types of the form “(list T)” for the type of homogeneous lists, whose elements all have type T; for example, we may write “(list integer)”, “(list number)”, or “(list symbol)”. We use the type “(list datum)” for the type of heterogeneous lists, because we think of the type “datum” as the type of all the values in Scheme. For example, lists, procedures, symbols, and numbers all have type datum. As another example, we could write for cons:

cons : (→ (datum (list datum)) (list datum)).

We abbreviate “(list datum)” as “list” when space is at a premium.

The names of other types with components are written similarly; for example, we write “(tree number)” or “(pair symbol symbol)”.

Sometimes, especially in chapter 7 and beyond, we wish to use the type information to show how data is transformed. For this it is convenient to use type variables, which are consistently replaced in a type when that type is used. Type variables capital letters such as: T, S, U, V, and W. For example, for Scheme’s built in procedure map we write:

map : (→ ((→ (S) T) (list S)) (list T)).

This type has several instances, that is consistent replacements of actual types for the type variables. For example, some instances are:

(→ ((→ (boolean) integer) (list boolean)) (list integer)) (→ ((→ (number) number) (list number)) (list number)) (→ ((→ ((list symbol)) (list datum)) (list (list symbol))) (list (list datum))).

The first of the above examples is what one would use when checking the types of the application (map positive? '(3 -2 1)); the second of these examples would be used in checking the types of the application (map add1 '(3 -2 1)). Since “datum” is a type, if we write such a type for

cons,

cons : (→ (T (list T)) (list T))

then it has the type given earlier as an instance.

We do not emphasize the formality of the type names and phrases, but try to write something that is easy to understand.

1 Chapter 1

See pages 6–7 (in Scheme and the Art of Programming) for the syntax of symbol and number. On page 7 the term variable is introduced. In what senses is a variable like a symbol? In what senses are they different? The grammatical symbol for variable is var.

Almost everything in Scheme is an expression. What does an expression look like in general? (See page 7.) Write down examples to illustrate the various cases. The grammatical symbol for an expression is expr.

We adopt the convention that unexplained grammatical symbols are equivalent to expressions. For example test used in the syntax of cond and if is equivalent to expr. These different names are used to guide you.

1.1 Special Forms

Syntax  Example  Notes

(define var expr)     (define ten (+ 5 5)) binds ten to 10.
(quote expr)          (quote ten)  don’t evaluate ten
'expr  '(a b xyz)

(operator operand …)

The form (define var expr) is not an expression. All the other forms are expressions.

1.2 Numbers

Name : Type  Example or Notes
+  : (→ (number number) number) addition

-  :
*  :
/  :

number? : (→ (datum) boolean)

1.3 Interaction With Scheme and Files

Name  : Type  Example or Notes

transcript-on : (→ (string) void) (transcript-on "foo.out")

:  records your session with Scheme
:  in the file named “foo.out”

transcript-off : → void  (transcript-off)

The procedure transcript-on does not return a result, and this is why its return type is listed as “void”.

1.4 Lists

Name : Type  Example or Notes
'() : (list T)  the empty list
cons : (→ (T (list T)) (list T))
car : (→ ((list T)) T)  requires: the argument is not empty

cdr :

c....r :  the . is a or d, up to 4 defined
pair? : (→ (datum) boolean)
null? : (→ (datum) boolean)

1.5 Booleans

Name  : Type  Example or Notes
#t  : boolean  logical truth
#f  : boolean
boolean? : (→ (datum) boolean)

1.6 Other Predicates

Name  : Type  Example or Notes
symbol? : (→ (datum) boolean)

procedure? :

eq?  : (→ ((or symbol pair) (or symbol pair)) boolean)

eqv? : (→ ((or number symbol boolean)

(or number symbol boolean)) boolean)

equal?  : (→ (datum, datum) boolean)

Something has type “(or symbol pair)” if it is either a symbol or a pair.

2 Chapter 2

2.1 Special Forms

Syntax  Example  Notes

(lambda (parameter …)

body)

                           (lambda (x) (cons x '()))

makes a procedure

(cond

(condition_{1} body_{1})

⋮

(condition_{n} body_{n})

  (else body_{n+1}))

(if condition

consequent alternative)

Normal usage.

(if condition
consequent)

                           (if (null?  ls)
                             (writeln "n too large"))

Only for side effects.

(and expr_{1} expr_{2} … expr_{n}) (or expr_{1} expr_{2} … expr_{n}) (begin expr_{1} … expr_{n})

The parameters in a lambda are not expressions, but names of formal parameters. All the other forms are expressions.

2.2 Lists

Name : Type Example or Notes ; list : (→ (T …) (list T))

The procedure list takes zero or more arguments; so we write … in the type.

2.3 Booleans

\frac{Name : Type Example or Notes}{not :}

Note that and and or are special forms.

2.4 Debugging

Name : Type Example or Notes ; writeln : (→ (datum …) void)

The writeln operation does not return a useful result. So we write “void” for the return type to signify this. Note that void is not the type of a value.

2.5 Strings

Name : Type Example or Notes "a string" : string

2.6 Interaction With Scheme and Files

Name : Type Example or Notes ; load : (→ (string) datum) (load "foo.ss") runs code in “foo.ss”

3 Chapter 3

3.1 Numbers

Name  : Type  Example or Notes
integer? : (→ (number) boolean)

real?  :
positive? :
negative? :
zero?  :

add1  : (→ (number number) number)

sub1  :

The procedures add1 and sub1 are in Chez Scheme and PC Scheme, but may not be in other dialects of Scheme.

There are many other numeric procedures summarized on page 76.

3.2 Lists

Name  : Type  Example or Notes
length : (→ (list) number)

list-ref :

3.3 Error Reporting

Name : Type Example or Notes ; error : (→ (datum …) poof) (error "should be" 5) prints “Error: should be 5”

The procedure error not only has no return value, it does not return at all! Instead it rather returns to the user prompt.

3.4 Basic Procedures for Ratls

Name  : Type  Example or Notes
make-ratl : (→ (integer integer) ratl) requires: the second argument is non-zero
numr  : (→ (ratl) integer)
denr  : (→ (ratl) integer)

4 Chapter 4

4.1 Lists

Name : Type  Example or Notes
append : (→ ((list T) (list T)) (list T))

reverse :

4.2 Trees

Name  : Type  Example or Notes ; atomic-item? : (→ (datum) boolean)

The procedure atomic-item? is my own invention, and will be discussed in class.

5 Chapter 5

5.1 Special Forms

Syntax  Example  Notes
(let ((var_{1} val_{1})

…

(var_{n} val_{n})) body)

                      (let ((x 2)) (+ x x))

binds x to 2 and returns 4

(letrec ((var_{1} val_{1})

…

(var_{n} val_{n})) body)

The vars in a let and letrec are not expressions, but are names of local variables. All the other forms are expressions. The vals in a letrec are usually lambda expressions.

5.2 Basic Procedures for Polynomials

Name  : Type  Example or Notes
the-zero-poly : poly  represents 0x^{0}, which is 0
degree  : (→ (poly) natural)

leading-coef :
rest-of-poly :

poly-cons  : (→ (natural real poly) poly) requires: 3rd argument’s degree is
:  less than the 1st argument, or 0

6 Chapter 6

6.1 Strings

Name  : Type  Example or Notes
string-append : (→ (string string) string)

string-length :
substring  :
symbol->string :
string=?  :
string-ci=? :

6.2 Implicit Begin

What special forms allow an implicit begin in their body? Which do not? What do you think the grammatical symbol body really stands for?

6.3 Input and Output

Name : Type  Example or Notes
display : (→ (datum) void) prints things in human-readable format

write :

read : → datum  (read) gets a value entered from the keyboard

newline :

Note that display and writeln do not return anything useful. The procedure read takes no arguments.

7 Chapter 7

7.1 Special Forms

Syntax  Example  Notes (lambda var body) (lambda ls ls) makes a procedure that returns its argument list

Note that this version of lambda is for defining procedures that take many arguments, like list, writeln, and error. The normal version was described in Chapter 2. The var in an unrestricted lambda is not an expression, but a the name of the parameter list.

7.2 Procedures that take Procedures as Arguments

Name  : Type  Example or Notes
map  : (→ ((→ (S) T) (list S)) (list T))
for-each : (→ ((→ (S) void) (list S)) void)
apply : (→ ((→ (datum …) T) (list datum)) T)

You may wish to make a similar table for the examples in this chapter of procedures that return procedures as arguments. None of these are built in to Scheme, but a few examples follow below to help you get started.

Name  : Type  Example or Notes
compose  : (→ ((→ (T) U) (→ (S) T)) (→ (S) U))
member-c? : (→ (T) (→ ((list T)) boolean))
apply-to-all : (→ ((→ (S) T)) (→ ((list S)) (list T)))

7.3 Procedural Abstractions of Flat and Deep Recursion

Name  : Type  Example or Notes
flat-recur  : (→ (T (→ (S T) T)) (→ ((list S)) T))

deep-recur : (→ (T (→ (S T) T) (→ (T T) T))

(→ ((tree S)) T))

deep-recur-abs : (→ (T (→ (S T) T) (→ (T T) T) (→ (datum) boolean))

(→ ((tree S)) T))

The procedure deep-recur-abs is my own invention, and will be discussed in class.

8 Chapter 8

8.1 Basic Procedures for Sets

Name  : Type  Example or Notes

the-empty-set : (set T)

empty-set? : (→ ((set T)) boolean)

set?  :
pick  :
residue  :
adjoin  :

8.2 Basic Procedures for Ordered Pairs

Name : Type  Example or Notes
make-op : (→ (S T) (ordered-pair S T))

op?  :

op-1st : (→ ((ordered-pair S T)) S)

op-2nd :

9 Chapter 9

9.1 Vectors

Name  : Type  Example or Notes
make-vector  : (and (→ (integer) (vector datum)) (→ (integer T) (vector T))) (make-vector 2 'x)
list->vector  : (→ ((list T)) (vector T))
vector  : (→ (T …) (vector T))

vector?  :

vector-generator : (→ ((→ (natural) T))

(→ (natural) (vector T)))

vector-length :
vector-ref  :

vector-set!  : (→ ((vector T) integer T) void)

The procedure vector-generator is not built-in to Scheme, but is one of the basic procedures for vectors.

9.2 Basic Procedures for Matrices

Name  : Type  Example or Notes

matrix-generator : (→ ((→ (natural natural) T))

(→ (natural natural) (matrix T)))

matrix-ref : (→ ((matrix T))

(→ (natural natural) (matrix T)))

matrix-rows  :
matrix-cols  :

matrix-set! : (→ ((matrix T))

(→ (natural natural T) void))

10 Chapter 10

10.1 Timing

Name : Type Example or Notes ; timer : (→ ((→ (datum) datum) datum) void)

10.2 Relational Calculus

Name : Type Example or Notes ; unlist : (→ ((→ (datum …) T)) (→ (list datum) T))

11 Chapter 11

11.1 Special Forms

Syntax  Example  Notes (set! var val)  (set! x (+ x 7))

11.2 List Mutation

Name  : Type  Example or Notes
set-car! : (→ ((pair S T) S) void)

set-cdr! :

12 Chapter 12

12.1 Special Forms

\frac{Syntax  Example  Notes}{(case target ((key_{1,1} key_{1,2} …) body_{1}) … ((key_{n,1} key_{n,2} …) body_{n}) (else body_{n+1}))}

A key is syntactically an expression, but is interpreted as if it were quoted.

12.2 Operations for Boxes

Name  : Type  Example or Notes
box-maker : (→ (T) (box T))
send type : (→ ((box T)) symbol)
send show : (→ ((box T)) T)  does not print anything

 send update! : (→ ((box T) T) void) (send update!  my-box 3)

send swap! : (→ ((box T) T) T)
send reset! : (→ ((box T)) void)

We write send before the names of instance operations, to show that they are not truly procedures with the types indicated, but the names of messages.

12.3 Operations for Counters

Name  : Type  Example or Notes
counter-maker : (→ (T (→ (T) T)) (counter T))

 send type  :
 send show  :

 send update! : (→ ((counter T)) void)  (send update!  my-counter)

 send reset! :

There are too many other types in chapter 12 to describe them all here. But you may want to describe them all for yourself using these examples to get you started.

Where to Look for More Details

R. Kent Dybvig’s book The Scheme Programming Language (1987, Prentice-Hall) describes the whole language. The current defining document for Scheme is the “Revised^{4} Report on the Algorithmic Language Scheme,” edited by W. Clinger and J. Rees (Nov. 2, 1991). The “Revised^{3} Report” was published in ACM SIGPLAN Notices, volume 21, number 12 (December 1986), pages 37–79.

The type system used in this document is similar to that originated by R. Milner and used in the programming language Standard ML (See “A Theory of Type Polymorphism in Programming,” Journal of Computer and System Sciences, volume 17, number 3 (December 1978), pages 348– 375.) A more tutorial presentation of this kind of type system is found in the survey article “On Understanding Types, Data Abstraction and Polymorphism,” by L. Cardelli and P. Wegner, which appears in ACM Computing Surveys, volume 17, number 4 (December 1985), pages 471–522. The idea of the type “datum” arises from the idea of subtyping, although the name itself comes from the book Essentials of Programming Languages, by D. P. Friedman, M. Wand, and C. T. Haynes (McGraw-Hill, 1992).

Acknowledgements

Thanks to the student management team of Spring 1993 for notational suggestions, and the Chris Haynes for a discussion on notation. Thanks to P. Wadler for a discussion about the type of call/cc which solidified my idea of the type “poof” as a subtype of every type.