include_template( 'mini-banner.html' ); ?> Scheme Tutorial include_template( 'mini-page-start.html' ); ?>
[ This tutorial is adapted from an old one written at Walla Walla College. In some places, it still contains links to the on-line MIT Scheme documentation rather than DrScheme documents, but the basic information is the same for all R5RS-compliant Scheme implementation. ]
section_title( 'Introduction' ) ?>
Scheme is an imperative language with a functional core. The functional core is based on the lambda calculus. In this tutorial only the functional core and some simple I/O is presented. For the purposes of this class, only the functional core of the language should be used. Hence,
setcdr!, and all other operations with named ending in "!" are not allowed.
begin. That still leaves you with plenty of control structures to work with, though. Here are some suggestions:
iffunction is a special case of
cond. If you only use
cond, you'll probably never miss
let. That means using recursion in spirit whenever you need to repeat a series of actions. Alternatively, you can define a separate recursive function if you prefer.
begin). This most commonly arises if you use an if instead of
cond, which is one reason that
condis often preferred.
In functional programming, parameters play the same role that assignments do in imperative programming. Scheme is an applicative programming language. By applicative, we mean that a Scheme function is applied to its arguments and returns the answer. Scheme is a descendent of LISP. It shares most of its syntax with LISP but it provides lexical rather than dynamic scope rules. LISP and Scheme have found their main application in the field of artificial intelligence.
The purely functional part of Scheme has the semantics we expect of mathematical expressions. One word of caution: Scheme evaluates the arguments of functions prior to entering the body of the function (eager evaluation). This causes no difficulty when the arguments are numeric values. However, in cases where you do not want one or more arguments to be evaluated, non-numeric arguments must be preceded with a single quote to prevent their evaluation. The examples in the following sections should clarify this issue.
Scheme is a weakly typed language with dynamic type checking and lexical scope rules.section_title( 'The Structure of Scheme Programs' ) ?>
A Scheme program consists of a set of function definitions. There is no structure imposed on the program and there is no main function. Function definitions may be nested. A Scheme program is executed by submitting an expression for evaluation. Functions and expressions are written in the form
This syntax differs from the usual mathematical syntax in that the function name is moved inside the parentheses and the arguments are separated by spaces rather than commas. For example, the mathematical expression 3 + 4 * 5 is written in Scheme as(function_name arguments)
(+ 3 (* 4 5))
Some additional examples:
(+ 3 5) (fac 6) (append '(a b c) '(1 2 3 4))
The first expression is the sum of 3 and 5. The second presupposes the
existence of a function
fac to which the argument of 6 is
presented. The third presupposes the existence of the function
append to which two lists are presented. Note that the
single quote in front of each argument in this third example is
required to prevent the (eager) evaluation of the lists. Without
the use of those two single quotes, both list arguments would
themselves be interpreted as function applications.
Note the uniform use of the standard prefix
notation for functions.
Among the constants (atoms) provided in Scheme are numbers, the boolean
#f, the empty list (), and
strings. Here are some examples of atoms and a string:
A, abcd, THISISANATOM, AB12, 123, 9Ai3n, "A string"
Atoms are used for variable names and names of functions. Scheme is case-insensitive, and it is common to use lower case or mixed case for readability (despite the examples in the text). Please do not write your code in all caps!
Some of the simple types provided in Scheme are:
|number||integers, floating point, rationals, complex, etc.|
|symbol||character sequences (unevaluated atoms)|
The basic composite types provided in Scheme are:
|dotted pair||a simple two-item record, not discussed here|
|list||parenthesized, space-separated sequence of items|
|function||all functions and procedures|
The list is the most frequently used composite data structure in Scheme. A list is an ordered set of elements consisting of atoms or other lists. Lists are enclosed by parentheses with elements separated by white space, as in LISP. Here are some examples of lists:
(A B C) (138 abcde 54 18) (SOMETIMES (PARENTHESIS (GET MORE)) COMPLICATED) ()
Lists are can be represented in functional notation. There is the empty
list represented by () and the list construction function
which constructs lists from elements and lists as follows: a list of one
(cons X ()) and a list of two elements is
(cons X (cons Y ())).
A predicate is a function that returns a boolean result. By
convention, Scheme predicates have names that end in a question mark
?). A type predicate is a boolean function that
is used to determine membership in a given type.
Since Scheme is weakly typed, Scheme provides a wide variety of type
checking predicates. Here are some of them.
|(boolean? arg )||arg is a boolean|
|(number? arg )||arg is a number|
|(pair? arg )||arg is a pair (a list or dotted pair)|
|(list? arg )||arg is a list|
|(symbol? arg )||arg is a symbol|
|(procedure? arg )||arg is a function|
|(null? arg )||arg is empty list|
|(zero? arg )||arg is zero|
|(odd? arg )||arg is odd|
|(even? arg )||arg is even|
number data type includes the integer,
rational, real, and complex numbers.
|Scheme Expression||Operational Meaning|
|4 + 5 + 2 + 7 + 5 + 2|
||((36 / 6) / 2) = 3|
||25 + 52|
The basic arithmetic operators are:
|/||division (can give integer, rational, or real result, depending on arguments)|
section_title( 'Lists' ) ?>
Lists are the basic structured data type in Scheme. Note that in the following examples the parameters are quoted. The quote prevents Scheme from evaluating the arguments. Here are examples of some of the built in list handling functions in Scheme.
(cons '1 '(2 3 4)) is (1 2 3 4) (cons '(1 2 3) '(4 5 6)) is ((1 2 3) 4 5 6) (cons '1 '2) is (1 . 2)
The last example is a dotted pair and the others are lists.
(car '(123 245 564 898)) is 123 (car '(first second third)) is first (car '(this (is no) more difficult)) is this
(cdr '(7 6 5)) is (6 5) (cdr '(it rains every day)) is (rains every day) (cdr (cdr '(a b c d e f))) is (c d e f) (car (cdr '(a b c d e f))) is b
#tif the object is the empty list,
(). It returns the null list,
()(which is the same as
#f), if the object is anything else.
(list 'a) is (a) (list 'a 'b 'c 'd 'e 'f) is (a b c d e f) (list '(a b c)) is ((a b c)) (list '(a b c) '(d e f) '(g h i)) is ((a b c)(d e f)(g h i))
(length '(1 3 5 9 11)) is 5
(reverse '(1 3 5 9 11)) is (11 9 5 3 1)
(append '(1 3 5) '(9 11)) is (1 3 5 9 11)
section_title( 'Boolean Expressions' ) ?>
The standard boolean objects for true and false are written
#f. However, Scheme treats any value
#f as true and only
#f as false
(Some implementations, such as MIT Scheme, treat the empty list
() as if it were the same as
or, as well as several tests for equality among
The most common comparison operator is
equal? which works
for all objects. Scheme also provides
eqv? (which works
for everything but lists or pairs) and
eq? (which only
works correctly for atoms), but
equal? is recommended to
beginners for all comparisons.
For numeric values, the normal relational operator symbols are used:
>=. Since prefix notation is used uniformly in
Scheme, when you mean to test x < y, you write it as:
(< x y).
For string values, predicates that use a lexicographic ordering exist:
string>=?. Also, for
every stringop? predicate, there is a case-insensitive version
string-ci=? performs a case-insensitive equality comparison).
Conditional expressions are of the form:
(if test-exp then-exp) (if test-exp then-exp else-exp)
test-exp is a boolean expression while the
expressions. If the value of the
is true then the
then-exp is evaluated and its
result is returned; otherwise, the
evaluated and its result is returned.
Some examples include:
(if (> n 0) (= n 10)) (if (null? lst) lst (cdr lst) )
In the second example above,
lst is the
(cdr lst) is the
Scheme has an alternative conditional expression that is more like a multi-way if statement (or a case statement) in that several test-result pairs may be listed. It takes one of two forms:
(cond (test-exp1 exp ...) (test-exp2 exp ...) ... ) (cond (test-exp exp ...) ... (else exp ...) )
The following conditional expressions are equivalent.
(cond ; Test condition ; Result to return ((= n 10) m) ((> n 10) (* n m)) ((< n 10) 0) ) (cond ((= n 10) m) ((> n 10) (* n m)) (else 0) )
To aid readability, many Scheme programmers use square brackets (
]) around each test/value pair in a
(cond ; Test condition ; Result to return [(= n 10) m] [(> n 10) (* n m)] [(< n 10) 0] ) (cond [(= n 10) m] [(> n 10) (* n m)] [else 0] )
Scheme will only match right square brackets with left square brackets,
and right parentheses with left parentheses, so these delimiters can also
aid in detecting incorrectly balanced parentheses within any particular
branch of the
cond expression. Otherwise, they mean the
same thing that parentheses do.
Definition expressions bind names and values and are of the form:
(define id exp)
Here is an example of a definition.
(define pi 3.14)
pi to have the value 3.14. This is not an
assignment statement since it cannot be used to rebind a name to a new
value. Definitions of this form are most often used to introduce
An alternative form of definition expression is used to bind a name to a function value:
(define (id formal-params ...) body )
id is the name being introduced. The
list of zero or more
both the number of arguments the new function will take, and their
formal parameter names. The
defines the meaning of the function.
Here is a definition of a squaring function.
(define (square x) (* x x) )
Here is an example of an application of the function (exact output may differ depending on the Scheme implementation being used):
1 ]=> (square 3) ;Value: 9
Here are function definitions for the factorial function, gcd function, Fibonacci function and Ackerman's function.
(define (fac n) (cond [(= n 0) 1] [else (* n (fac (- n 1))) ] ) ) (define (fib n) (cond [(= n 0) 0] [(= n 1) 1] [else (+ (fib (- n 1)) (fib (- n 2))) ] ) ) (define (ack m n) (cond [(= m 0) (+ n 1)] [(= n 0) (ack (- m 1) 1)] [else (ack (- m 1) (ack m (- n 1)))] ) ) (define (gcd a b) (cond [(= a b) a] [(> a b) (gcd (- a b) b)] [else (gcd a (- b a))] ) )
Here are definitions of the list processing functions, sum, product, length
and reverse. You'll notice that many function definitions in Scheme
are recursive, and are written as
cond expressions, where
the base case(s) are listed first, followed by the recursive case(s).
This is an extremely common pattern, especially for list processing
(define (sum lst) (cond [(null? lst) 0] [else (+ (car lst) (sum (cdr lst)))] ) ) (define (product lst) (cond [(null? lst) 1] [else (* (car lst) (product (cdr lst)))] ) ) (define (length lst) (cond [(null? lst) 0] [else (+ 1 (length (cdr lst)))] ) ) (define (reverse lst) (cond [(null? lst) ()] [else (append (reverse (cdr lst)) (list (car lst)))] ) )
In addition to top-level function definitions introduced using
define it is also possible to define custom functions
"in-line" for various purposes. This is done through a lambda
expression. Lambda expressions are unnamed functions of the form:
(lambda (id ...) exp )
The (possibly empty) list of symbols
(id ...) is
the list of formal parameters to the annonymous function, and
exp represents the body of the lambda
expression. Here are two examples the application of lambda
((lambda (x) (* x x)) 3) is 9 ((lambda (x y) (+ x y)) 3 4) is 7
In both of these examples, the lambda expression appears as the first element in a function application, and thus denotes the function to apply. You can also bind the result of a lambda expression to a name:
(define square (lambda (x) (* x x)))
This is exactly the same as the alternative form of define presented
earlier. In fact, the "function form" of
presented above is just shorthand for using a lambda expression; both
of the following are equivalent:
(define (name params) body) ; just shorthand for ... (define name (lambda (params) body))
What good are lambda expressions? They are most commonly used for two purposes:
Defining one-time-use (or "throw away") functions that are being passed as custom values to higher-order functions.
Creating a customized function to serve as the return value for a higher-order function.
Scheme provides for local definitions by permitting definitions to be
nested. Local definitions are introduced using
letrec. Each of these forms may
introduce a sequence of local bindings. For purposes of efficiency
the bindings are interpreted differently in each of the ``let'' functions.
let values are computed and bindings are done in parallel,
which requires all of the definitions to be independent.
Here are some examples:
; this binds x to 5 and yields 10 (let ( (x 5) ) (* x 2) ) ; this bind x to 10, z to 5 and yields 50. (let ( (x 10) (z 5) ) (* x z) )
cond expressions, Scheme programmers often use
square brackets around each name/value pair in a
declaration list for readability and improved error detection:
; this binds x to 5 and yields 10 (let ( [x 5] ) (* x 2) ) ; this bind x to 10, z to 5 and yields 50. (let ( [x 10] [z 5] ) (* x z) )
Think of a
let expression as a local declaration
block. The first item in the let is a list of name-value pairs
(note the way the parentheses are written in the examples here).
The first value in each pair is a new name to introduce, and the
second is the value to bind to that name. Lexical scoping rules are
used, so "redefining" an existing name really introduces a new "local"
name that hides the outer definition (which will once again be visible
after the end of the
let* is similar in structure to
for the way the values are evaluated. In
let*, the values
and bindings are computed sequentially, which means that later definitions
may depend on the earlier ones.
(let* ( [x 10] [y (* 2 x)] ) ; Not legal for "let" (* x y) )
letrec, the bindings are
in effect while values are being computed to permit mutually recursive
definitions. As an illustration of local definitions here is an
insertion sort definition with the insert function defined locally.
Note that the body of
isort contains two expressions, the first
letrec expression and the second is the expression whose
value is to be returned.
(define (isort lst) (letrec ( ; Only one local definition: insert [insert (lambda (x l) (cond [(null? l) (list x)] [(<= x (car l)) (cons x l)] [else (cons (car l) (insert x (cdr l)))] ) ) ] ) ; Now, the body of the letrec (cond [(null? lst) ()] [else (insert (car llst) (isort (cdr lst)))] ) ) )
In this example,
letrec is used since
is recursively defined.
Lets may be nested. For example:
(let ( [a 3] [b 4] ) ; The body of the first let (let ( [double (* 2 a)] [triple (* 3 b)] ) ; The body of the second let (+ double triple) ) )
let example produces the value
The basic output operation in Scheme is called
display prints its argument to the standard
(display (+ 3 5))
This expression displays the result of the addition expression.
Display prints out all forms of Scheme data, including
human-readable representations of lists. It also prints character
strings (leaving out the surrounding double quotes). Most plain
text output can be produced using just
(newline), which simply prints a new line
character on standard output.
A higher order function (or functional) is a function that either expects a function as a parameter or returns a function as a result. In Scheme functions may be passed as parameters and returned as results. Scheme has several higher-order functions for manipulating lists (see Scheme Reference Manual Section 7: List Operations for more information).
One powerful functional for dealing with lists is
map takes two arguments: a function to
apply, and a list of values. It returns a new list which is the
result of applying its first argument to each element of its second
1 ]=> (map odd? '(2 3 4 5 6)) ;Value: (() #t () #t ())
Here is another example:
(define (dbl x) (* 2 x)) (map dbl '(1 2 3 4))
If the function being passed into
map is not generally
useful and you do not want to go to the trouble of creating a
separate, stand-alone definition for it, you can use a lambda
(map (lambda (x) (* 2 x)) '(1 2 3 4))
Actually, in Scheme,
map can be used on functions of any
arity (that is, any number of arguments), as long as you provide the
correct number of arguments:
1 ]=> (map + '(1 2 3 4) '(5 6 7 8)) ;Value: (6 8 10 12)
Some other powerful higher-order functions for manipulating lists include:
there-exists?takes a list and a predicate and returns
#tif the predicate is true for any element of the list (and
list-search-positivetakes a list and a predicate, and returns the first element in the list for which the predicate is true.
list-search-negativeis similar, but looks for the first element where the predicate is false.
for-all?takes a list and a predicate and returns
#tif the predicate is true for every element of the list (and
list-transform-positivetakes a list and a predicate, and returns a list of all elements for which the predicate is true.
list-transform-negativeis similar, but looks for values where the predicate is false.
for-eachis just like
map, except that
for-eachis guaranteed to evaluate its given function on the lists in order from first to last, while
mapdoes not guarantee the order of evaluation (and usually operates on the lists you give it from the rear forward instead). For purely functional operations, there is no difference between
map, but if you are generating output (to standard output or a file) as a side-effect of the function you pass in, then
for-eachwill give you the ordering you expect.
reducetakes a binary operation, an initial value, and a list, and successively applies the binary operator "in between" pairs of elements in the list, accumulating a result. For example,
(reduce + 0 '(1 2 3 4))produces 10.
reduceis left associative, and only uses the initial value if the given list is empty (in which case the initial value is the answer produced).
reduce-rightis the right-associative version of
reduce, except that it always uses the given initial value to start off the sequence of evaluation.
fold-rightis the right-associative version of
See Scheme Reference Manual Section 7: List Operations for information on these operations.section_title( 'Hints on Handling Common Errors' ) ?>
The four most common errors that beginning Scheme programmers in this course make are:
If you are using DrScheme, set the language level to "Intermediate Student with lambda" (or a more restricted teaching language--use the Language->Choose Language... menu command). DrScheme enforces restrictions on how you use many of Scheme's features and will give specific help on these types of errors when they occur. In addition, this setting will ensure that you do not use any features that use mutable state (i.e., that force a variable's value to change using imperative features).section_title( 'Debugging and Tracing' ) ?>
DrScheme provides a Stepper that can be used to interactively step through the evaluation of any expression. To use the stepper, make sure that you have the language level set to a restricted subset of Scheme between "Beginner" and "Intermediate Student with lambda" (more advanced language levels, including full R5RS Scheme, do not support the stepper).
Suppose you have defined your own function called
and you would like to trace its execution on a sample value, like
13. If your already have a definition for
dbl in the
definitions window, just add the expression you want to trace to
the bottom of the definitions window:
(define (dbl x) (* 2 x)) ; The expression to step through (dbl 13)
Now, press the
Step button at the top of the window.
Step button starts the Stepper, which shows the
evaluation of a program as a series of small steps. Each evaluation
step replaces an expression in the program with an equivalent one
using the evaluation rules of DrScheme. For example, a step might
Another step might replace this S-expression with
These are the same rules used by DrScheme to evaluate a
program. Clicking Step opens a new window that contains the
program from the definitions window, plus five new buttons:
Home, |< Application, < Step, Step >, and Application >|. Clicking Step >
performs a single evaluation step, clicking < Step retraces back a
single step, and clicking Home returns to the initial program.
Clicking Application >| jumps forward to the next top-level expression in the definitions window, and |< Application returns to the previous one.
One important note: The Stepper has trouble with test cases in the current version of DrScheme. There are two ways around this limitation, however. First, you can move the expression you wish to trace earlier in your source file, and/or move your test cases closer toward the end. The Stepper will work fine on expressions it evaluates before it reaches your first test case. Second, you can instead temporarily comment out any test cases appearing before the expression to place--just place the cursor at the beginning of the line containing the test case box and add a semicolon in front of it. If you use the second approach, be sure to uncomment your test cases once you are done stepping so that you will get credit for them in program submissions!include_template( 'mini-page-end.html' ); ?>