This document is an informal definition of the subset of Scheme which we will use in the class. If you wish to consult references, look for those that describe the Scheme dialect of Lisp or use the initial chapters of our recommended text The Scheme Programming Language, Second Edition, by R. Kent Dybvig or see
http://www.swiss.ai.mit.edu/~jaffer/r4rs_toc.html(Revised(4) Report on the Algorithmic Language Scheme) for the offical language definition and
http://www.swiss.ai.mit.edu/~jaffer/scm_toc.html(SCM Scheme Implementation) for the documentation on SCM, the implementation of sheme that we are using.
Informally, Scheme programs consist of S-expressions (or forms), entities that have the structure of lists. In Scheme, everything -- data structures, function definitions, and function calls -- is an S-expression; therefore, everything has the syntax of a list. The syntax of Scheme is so simple that we can give an EBNF grammar for the whole language in one rule:
1.51.5
We will later give an extended grammar with more semantic details. Remember that we are only studying the pure functional aspects of Scheme.
We are executing Scheme in an interpreter, although compilers exist
for this language. The execution model to keep in mind is the
(print (eval (read))) loop in the interpreter; it reads from
the input an S-expression, evaluates it and then prints the result.
When you evaluate an S-expression, (e1 e2 e3 ... ek), a sequence of
events occur in order:
e1 to get a function to apply. Usually,
e1 is just an atom, and evaluating it just means getting its
value; note that in scheme, a ``function name'' like car is
really just a variable whose value is the a data structure
representing the code for the function.e2, e3, ... ek to get values of
the arguments of this function.(1 2) at the
Scheme prompt would result in an error because the value of 1 is 1,
which is not a valid data structure to use as a function.
We can inhibit this evaluation in Scheme by
quoting the object. For example, typing '(1 2) would
have resulted in Scheme writing back to us the list (1 2).
Figure: Incomplete Syntax of Scheme
Figure 1 shows a EBNF grammar for Scheme for which we discuss some
semantic details in this section.
This grammar lists some primitive functions that work on lists,
namely car, cdr and cons as well as some predicates,
namely null?, and zero?.
The functions car and cdr are used to get at elements or
sublists of a list.
car is used to extract the first element of a list;
that is, (car '(1 2)) is 1 and (car '((1) 2)) is
(1). The difference between these two lists (1 2) and
((1) 2) is that the first one has two elements, the atoms 1 and
2, whereas the second one has two elements, the list (1) and
the atom 2.
cdr is used to get at the rest of the list, ``leftover'' after a car
operation. Therefore, (cdr '(1 2)) is the list (2) and
(cdr '((1) 2)) is the list (2) as well. Note that after
we take car or cdr of a list that list remains unchanged; nothing is
destroyed in it. This is sometimes called ``copy semantics''. These
functions are merely a way of accessing sublists within a list.
These two functions can be nested; for example, (car (cdr '(1 (2
3) 4))) is the list (2 3) since (cdr '(1 (2 3) 4)) is
((2 3) 4) whose car is (2 3). One can write this
combined function in shorthand notation as (cadr '(1 (2 3) 4)),
thereby using the d and a to indicate the order of application
of the car's and cdr's.
cons is used to construct lists from an element and
a list (i.e., a car and a cdr). Thus, (cons 1 '(2 3)) is
(1 2 3) and
(cons '(1) '(2 3)) is ((1) 2 3).
if and cond are the conditional operators in Scheme.
The syntax of if and cond are shown below and their
semantics explained.
(if e1 e2)
(if e1 e4 e5)
The meaning of the first of these expressions is that e1 is
evaluated, and if its value is true, the expression e2 is then
evaluated and returned as the value of the if expression.
The second if expression has a similar meaning: e1 is
evaluated and if its value is true, the expression e4 is
evaluated and returned as the value of the if; otherwise, the
expression e5 is evaluated and returned as the value of the
if.
(cond (e1 c1) (e2 c2) ... (ek ck)).
The meaning of this construct is as follows: The ei are
S-expressions which evaluate to true or false. The ci are
arbitrary Scheme S-expressions. First e1 is evaluated. If it
is true, then c1 is evaluated and returned as the value of the
cond. Otherwise, e2 is evaluated and checked for truth value
etc. We continue to evaluate e3, e4, e5,...
until we find the first true value. Then the corresponding expression
ci is evaluated and its value returned as the value of the
cond. Often ek is else, which always evaluates to true
so that the last case ``catches'' all other cases. If no ei
evaluates to true, then the cond expression returns #f,
i.e. false.
null? is a unary predicate which returns true (i.e., #t)
if its argument is NIL (i.e., empty list or the atom NIL) and
#f otherwise.
zero? is a unary predicate which returns true if its argument
has value 0 and #f otherwise.
integer? is a unary predicate which returns true if its
argument is an integer and #f otherwise.
list? is a unary predicate that returns true if its argument is
a list and #f otherwise.
The special forms define and lambda allow you to define
Scheme functions, named and unnamed, respectively. For example, we
can define the function that increments integer values by 1:
(define (add1 x) (+ 1 x))Then we can call this function; for example,
(add1 2) would
return 3.
There are sometimes situations when we need a function locally but we don't need to name it.
>(define (one-ups l) (map (lambda (x) (+ x 1)) l)) > (one-ups '(2 4 5)) (3 5 6)Here the lambda expression defines a function which adds one to its argument. Since we only need this function here, as an argument to map, there is no reason to give it a name.
The comment character is a semicolon (;). If it appears anywhere on a line, the characters to the right of it are ignored as they are a comment.
Try coding the following simple Scheme functions:
last, a function that returns the last element in a list. Do not
use the built-in function reverse which reverses the elements
of a list or the reverse function from your textbook.stem, a function that returns the list obtained by removing the last
element from the argument list. Again, do not use the built-in function
reverse which reverses the elements of a list or the reverse
function from your textbook.second, a function that returns the second element of its
argument list.and2, a function that will take the logical ``and'' of
its two arguments. Do not use the built-in function and.or2, a function that will take the logical ``or'' of its
two arguments. Do not use the built-in function or.
scm at the shell prompt.
To make the Scheme interpreter read a file funs.scm containing
a Scheme program you have written, type the command (load
"funs") at the Scheme prompt. To make the Scheme interpreter evaluate
an expression, for example in order to call a function you have
written, type the expression to the interpreter followed by
<return>.
Of course, you can also use a shell buffer in emacs to run Scheme. Some people prefer to run Scheme in an emacs buffer, as then it is easy to change buffers, edit your Scheme function, change buffers again and reload your functions to rerun them.
A useful built-in function is pretty-print command for files, which can print out their contents. To use this you type (require 'pprint-file) at the system prompt when you start up scheme. Then, you can invoke this command on a file by typing (pprint-file "app1.scm").
This section presents a sample execution in our Scheme interpreter of the following Scheme function:
; len computes the length of its argument list (only top level
; elements are counted, so len is a "shallow" function i.e. it
; doesn't splice into sublists. For example (len '(1 (2 (3)) 5)) = 3.
(define (len x)
(cond ((null? x) 0)
(else (+ 1 (len (cdr x))))))
which is available in the file:
/ug/u3/ryder/scheme/programs/len-app-atom-new.scm
on the undergrad SUNs. Here is a copy of the screen image. Notice that the Scheme prompt is ;SPMgt;; all else is typed by the system, or added as comments (with ;** afterwards. Note that the directory paths in this example maybe different than those you will see this year.
98 romulus!programs> scheme
SCM version 4e1, Copyright (C) 1990, 1991, 1992, 1993, 1994 Aubrey Jaffer.
SCM comes with ABSOLUTELY NO WARRANTY; for details type `(terms)'.
This is free software, and you are welcome to redistribute it
under certain conditions; type `(terms)' for details.
;loading "/usr/local/lib/scm/Transcen.scm"
;done loading "/usr/local/lib/scm/Transcen.scm"
;Evaluation took 50 mSec (0 in gc) 10785 cells work, 13896 bytes other
> (load "len-app-atom-new") ;** loading in a file
;loading "len-app-atom-new"
;done loading "len-app-atom-new.scm"
;Evaluation took 20 mSec (0 in gc) 185 cells work, 234 bytes other
#<unspecified>
> (len '(a b c)) ;** a legal function application
;Evaluation took 0 mSec (0 in gc) 27 cells work, 33 bytes other
3
> (len 'z) ;** an illegal function application and error
;** message from the system
ERROR: cdr: Wrong type in arg1 z
;Evaluation took 0 mSec (0 in gc) 10 cells work, 31 bytes other
> (len '(1 2 3 (4))) ;** another legal function application
;Evaluation took 0 mSec (0 in gc) 31 cells work, 39 bytes other
4
> ^C ;**if you forget and type Control-C at Scheme
ERROR: user interrupt
;Evaluation took 0 mSec (0 in gc) 0 cells work, 0 bytes other
> ;EXIT :** what happens when you type Control-d to leave Scheme
To debug your Scheme programs, you have two options: either you can
trace sequences of function calls using trace or you can set
arbitrary breakpoints in your code and examine expressions defined during
execution using break.
To use trace, you need to first execute:
(require 'trace)
in the interpreter. This allows you to trace calls/returns to specific functions, such as foo, by typing:
(trace foo)
When you want to stop tracing a function, invoke
(untrace foo)
An example of using trace is provided below:
> (define (len ls) (if (null? ls) 0 (+ 1 (len (cdr ls))))) (define (len ls) (if (null? ls) 0 (+ 1 (len (cdr ls))))) ;Evaluation took 0 mSec (0 in gc) 36 cells work, 42 bytes other #<unspecified> > (len '(a b c)) ;Evaluation took 0 mSec (0 in gc) 27 cells work, 33 bytes other 3 > (require 'trace) ;loading /usr/local/lib/scm/slib/trace ; loading /usr/local/lib/scm/slib/qp ; done loading /usr/local/lib/scm/slib/qp.scm ; loading /usr/local/lib/scm/slib/alist ; done loading /usr/local/lib/scm/slib/alist.scm ;done loading /usr/local/lib/scm/slib/trace.scm ;Evaluation took 50 mSec (0 in gc) 2725 cells work, 1933 bytes other #<unspecified> > (trace len) ;Evaluation took 0 mSec (0 in gc) 106 cells work, 31 bytes other #<unspecified> > (len '(a b c)) "CALLED" len (a b c) "CALLED" len (b c) "CALLED" len (c) "CALLED" len () "RETURNED" len 0 "RETURNED" len 1 "RETURNED" len 2 "RETURNED" len 3 ;Evaluation took 0 mSec (0 in gc) 1313 cells work, 83 bytes other 3 > (untrace len) ;Evaluation took 0 mSec (0 in gc) 85 cells work, 31 bytes other #<unspecified> > (len '(a b c)) ;Evaluation took 10 mSec (0 in gc) 22 cells work, 31 bytes other 3 ;;*******end of execution***********