Scheme Tutorial

Introduction

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 definition may be nested. A Scheme program is executed by submitting an expression for evaluation. Functions and expressions are written in the form

(function_name arguments)

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

(+ 3 (* 4 5))

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

takes two arguments and returns a pair (list).

 (cons '1 '2)          is   (1 . 2)
 (cons '1 '(2 3 4))      is   (1 2 3 4)
 (cons '(1 2 3) '(4 5 6))  is   ((1 2 3) 4 5 6)

The first example is a dotted pair and the others are lists. \marginpar{expand} Either lists or dotted pairs can be used to implement records.

car

returns the first member of a list or dotted pair.

     (car '(123 245 564 898))             is   123
     (car '(first second third))           is   first
     (car '(this (is no) more difficult))   is  this

cdr

returns the list without its first item, or the second member of a dotted pair.

     (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?

returns \#t if the {\bf obj}ect is the null list, (). It returns the null list, (), if the object is anything else.

list

returns a list constructed from its arguments.

     (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

returns the length of a list.

     (length '(1 3 5 9 11))                 is  5

reverse

returns the list reversed.

     (reverse '(1 3 5 9 11)) is  (11 9 5 3 1)

append

returns the concatenation of two lists.

     (append '(1 3 5)  '(9 11))  is  (1 3 5 9 11)

Functions

Definition expressions bind names and values and are of the form:

     (define {\em id exp})

Here is an example of a definition.

     (define pi 3.14)

This defines {\tt 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.

Lambda Expressions

User defined functions are defined using lambda expressions. Lambda expressions are unnamed functions of the form:

         (lambda ({\em id...}) {\em exp} )

The expression {\tt (id...)} is the list of formal parameters. and {\tt 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

Here is a definition of a squaring function.

(define square (lambda (x)  (* x x)))