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,
set!
, setcar!
, setcdr!
, and all
other operations with named ending in "!" are not allowed.
do
and
begin
. That still leaves you with plenty of control
structures to work with, though.
Here are some suggestions:
cond
or if
. The
if
function is a special case of cond
. If
you only use cond
, you'll probably never miss
begin
.
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.
let
(instead of begin
). This most
commonly arises if you
use an if instead of cond
, which is one reason that
cond
is 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
constants #t
and #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:
Type | Values |
---|---|
boolean | #t, #f |
number | integers, floating point, rationals, complex, etc. |
symbol | character sequences (unevaluated atoms) |
The basic composite types provided in Scheme are:
Type | Values |
---|---|
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
cons
which constructs lists from elements and lists as follows: a list of one
element is (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.
Predicate | True If |
---|---|
(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 |
Scheme number
data type includes the integer,
rational, real, and complex numbers.
Some Examples:
Scheme Expression | Operational Meaning |
---|---|
(+ 4 5 2 7 5 2) | 4 + 5 + 2 + 7 + 5 + 2 |
(/ 36 6 2) |
((36 / 6) / 2) = 3 |
(+ (* 2 2 2 2 2) (* 5 5)) |
25 + 52 |
The basic arithmetic operators are:
Symbol | Operation |
---|---|
+ | addition |
- | subtraction |
* | multiplication |
/ | division (can give integer, rational, or real result, depending on arguments) |
quotient | integer division |
modulo | modulus |
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
(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
(car '(123 245 564 898)) is 123 (car '(first second third)) is first (car '(this (is no) more difficult)) is this
cdr
(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
null?
#t
if the object is the empty list,
()
. It returns the null list, ()
(which is
the same as #f
), if the object is anything else.list
(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
(length '(1 3 5 9 11)) is 5
reverse
(reverse '(1 3 5 9 11)) is (11 9 5 3 1)
append
(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
#t
and #f
. However, Scheme treats any value
other than #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 #f
).
Scheme provides not
, and
, and
or
, as well as several tests for equality among
objects.
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:
=
, <
, <=
, >
,
and >=
. 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=?
, string<?
, string<=?
,
string>?
, and string>=?
. Also, for
every stringop? predicate, there is a case-insensitive version
called string-ciop?
(e.g.,
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)
The test-exp
is a boolean expression while the
then-exp
and else-exp
are
expressions. If the value of the test-exp
is true then the then-exp
is evaluated and its
result is returned; otherwise, the else-exp
is
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
then-exp
while (cdr lst)
is the
else-exp
.
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
expression:
(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)
This defines 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
global constants.
An alternative form of definition expression is used to bind a name to a function value:
(define (id formal-params ...) body )
Here, id
is the name being introduced. The
list of zero or more formal-params
determines
both the number of arguments the new function will take, and their
formal parameter names. The body
expression
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
functions.
(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
expressions.
((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 define
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 let
,
let*
and 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.
The 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) )
As with cond
expressions, Scheme programmers often use
square brackets around each name/value pair in a let
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
expression).
let*
is similar in structure to let
except
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) )
In 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
is a 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 insert
is recursively defined.
Let
s 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) ) )
This let
example produces the value 18
.
The basic output operation in Scheme is called display
(the write
and print
functions are similar,
with minor differences in the way they format various types of values).
Note that in DrScheme these functions are only available at
the "Advanced Student" language level and above, since they produce
side-effects.
The function display
prints its argument to the standard
output.
(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 display
and
the operation (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
.
The function 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
argument.
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
expression instead:
(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 #t
if the predicate is true for any element
of the list (and ()
otherwise).
list-search-positive
takes a list and a
predicate, and returns the first element in the list for which the
predicate is true.
list-search-negative
is similar, but looks for the
first element where the predicate is false.
for-all?
takes a list and a predicate and
returns #t
if the predicate is true for every element
of the list (and ()
otherwise).
list-transform-positive
takes a list and a
predicate, and returns a list of all elements for which the
predicate is true.
list-transform-negative
is similar, but looks for
values where the predicate is false.
for-each
is just like map
, except that
for-each
is guaranteed to evaluate its given
function on the lists in order from first to last, while
map
does 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 for-each
and 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-each
will give you the ordering you expect.
reduce
takes 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.
reduce
is 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-right
is the right-associative version of
reduce
.
fold-left
is like reduce
, except
that it always uses the given initial value to start off
the sequence of evaluation.
fold-right
is the right-associative version of
fold-left
.
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 dbl
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.
The 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
replace (*
with 2
x
)(*
.
Another step might replace this S-expression with 2
13
)26
.
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' ); ?>