This section introduces the basic language features of Scheme.
An expression is a unit of the language: a combination of syntactically correct characters and something that can be evaluated by an interpreter.
A combination is a list of expressions, surround by parentheses, denoting a procedure application. The first element in the list is the operator. Subsequent expression are the operands. This method of expressing operations, with the operator first followed by the operands, is called prefix notation.
(<operator> <operand1> <operand2> ...)The value of a combination is the obtained by the application of
operator (a procedure) to the arguments (which are values)
given by the evaluation of the operands (which are expressions).
We can define variables using define,
(define <varName> <varValue>)Note that the define procedure does not follow the steps for
evaluating combinations described in the paragraph above:
evaluating
(define x 3)does not apply define to two arguments, one of which is the value of the symbolxand the other of which is 3, since the purpose of the define is precisely to associatexwith a value. (That is,(define x 3)is not a combination.)
Procedures that do not follow the general evaluation rule are called special forms. Each special form has its own evaluation rule.
The define procedure can be used to define procedures as well, these
are called compound procedures:
(define (<name> <formal params>) <body>)For example:
(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))The substitution model is used to help us think about how compound procedures are evaluated: > To apply a compound procedure to arguments, evaluate the body of the > procedure with each formal parameter replaced by the corresponding > argument.
Using the substitution model there are two different way in which to evaluate a compound procedure:
An example using the square compound procedure:
(square (+ 1 5))
(square 6)
(* 6 6)(square (+ 1 5))
(* (+ 1 5) (+ 1 5))
(* 6 6)Applicative order and normal order evaluation will produce that same value for procedures that can be interpreted using the substitution model.
Scheme uses applicative order evaluation. This is mainly due to its advantage over normal order for procedures that can’t be interpreted using the substitution model. Normal order evaluation, of course, has its advantages which will be explored in later sections.
A case analysis can be performed using the cond special form
(cond (<pred1> <exp1>)
(<pred2> <exp2>)
...
(<predN> <expN>))where pred are predicates that evaluate to #t/#f and the
expressions exp are the possible values of cond. Predicates are
successively evaluated, the expression associated with the first true
predicate is the value returned by cond, subsequent predicates and
expressions are not evaluated. If none of the predicates are true an
unspecified value is returned.
Note that in cases where #t/#f is expected any value not #f is
considered as #t (that is, 0 and "" are also “true”).
The cond expression also supports a catch-all case: the keyword
else can be used in place of the last predicate, its associated
value is returned in the case where all predicates are false.
(cond (<pred1> <exp1>)
...
(else <expN>))The if special form can be used when there are only two cases:
(if <pred> <consequent> <alternative>)The <alternative> does not need to be supplied, in which case, if
the <pred> is false that an unspecified value is returned.
There are primitive predicates such as <, = and >.
There are logical composition operations:
(and <pred1> ... <predN>)the predicates pred are evalutated from left to right, if a
predicate is false subsequent predicates are not evalutated and the
and expression is false. If all predicates are true then the and
expression is true
(or <pred1> ... <predN>)similar to and – the predicates pred are evaluated until the
first true in which case the or expression is true. If all
predicates are false then the or expression is false
(not <pred>)the negation of pred
A description for Newton’s method for finding the square root of a number:
whenever we have a guess y for the value of a square root of a number x, we can always produce a better guess by averaging y with x/y
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (sqrt x)
(sqrt-iter 1.0 x))In the example above, the process of finding the square root of a number has been broken down into sub-tasks performed by separate procedures. Each procedure is completely self-contained in performing its specified task.
When a procedure is self-contained so that knowledge of its implementation is not curcial to its use, it can be readily used as a module in the definitions of other procedures, that is, the use can treat it as a box block or procedural abstraction.
For example, in the good-enough? procedure, whether square is
defined in terms of mulitplcation or exponentials and logarithms
ought not be of concern to the user
(define (square x) (* x x))
(define (square x)
(exp (double (log x))))
(define (double x) (+ x x))It should also not matter, in the second version of square, that x
is used as the formal parameter in both square and double. This
potential mix up is avoided by making formal parameters local to their
procedures.
The meaning of procedures should be independent of the paramenter names chosen by the author. That is, the following pair should be indistinguishable to the user:
(define (square (x) (* x x))
(define (square (y) (* y y))A consequence of this requirement is that parameter names remain local to the procedure and leads to the idea of a bound variable: if the name of a bound variable is consistently changed throughout a procedure definition the meaning of the procedure is unchanged. We say that the procedure binds its formal parameters.
A varible that is not bound is free and the set of expressions for a binding defines a name is called the scope of that name. In procedure definition, the bound variables declare as the formal parameters of the procedure have the body of the procedure as their scope.
Formal parameters are no the only names that can be made local to a
procedure, internal definitions are also local to that procedure. For
example, instead of 5 separate procedures the sqrt procedure can be
written as one procedure with internal definitions:
(define (sqrt x)
(define (good-enough? guess x)
(< (abs (- (square guess) x))
0.001))
(define (improve guess x)
(average guess
(/ x guess)))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(sqrt-iter 1.0 x))Such nesting of definitions is called block structuring.
In addtion to restricting the names floating in our environment,
block strucutres allow us to simplify the internally defined procedures.
For example, the sqrt procedure:
(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))Since x is a bound variable in the definition of sqrt, internally
defined procedures, good-enough, improve and sqrt-iter, are in
the scope of x. Thus, it is not necessary to pass x explicitly to
each of these procedures, the x in these procedures is a free
variable, taking the value bound by the procedure sqrt.
This is an example of lexical scoping, where free variables in procedures are taken to refer to bindings made in the environment in which the procedure was defined.