The associated reading is again from An Introduction to Scheme and its Implementation, specifically the "let" and "let*" parts of the "Local Variables and Lexical Scope" section, the "letrec" part of the "Procedures" section, and the "and and or" part of the "Basics" section. Don't worry yet about the discussions of "Lexical Scope" in these sections--we'll get to that later in Lecture 9.
There are times when just a straight formula is a little ungainly for a function definition. In mathematics, we commonly write
Let a = 1 + xy
b = 1 - y
in f(x,y) = xa^2 + yb + ab
Notice: Uninitialized string offset: 1 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 150
instead of writing
f(x,y) = x(1+xy)^2 + y(1-y)+(1+xy)(1-y)
The formulas a and b are examples of an important abstraction mechanism called local variables. Would it be proper to substitute one value for x in the first part and another value for x in the second? Clearly not, that violates the conventions that we're all familiar with. It is understood that the variables in the first part of the formulation and the variables in the second part are the same.
Scheme has a way of writing functions with local variables. For instance, we could write the function f as
(define f (lambda (x y)
(let ((a (+ 1 (* x y)))
(b (- 1 y)))
(+ (* x (square a)) (* y b) (* a b)))))
You'll notice that except for being a little more terse and having a few
more parentheses, this closely resembles what we do in mathematics. The
placement of the parentheses is important, so lets have a little syntactic
digression. The general form of the let statement is
(let (( )
( )
.
.
.
( ))
)
In general, we can say that let takes two arguments, the first being a list of bindings and the second an expression in which to use these bindings.
There's nothing that says that let has to be used inside a function definition; the following expression tells us a little more about how let works:
(define x 5)
(+ (let ((x 3))
(+ x (* x 10)))
x)
When this expression is evaluated, it returns the value 38 since in the expression (+ x (* x 10)), x is bound to 3, but outside the parentheses that enclose the let, x is defined to be 5. (We'll talk more about variable scope rules later.)
The order of evaluation and binding is important when defining local variables. For example, consider the following expressions:
(define a 0)
(let ((a 3)
(b (+ a 1))
(+ a b))
What is the value returned by this expression? To answer this, you have to
know what the value of a is at the time b is defined.
Is it 0, or is it 3? In Scheme, it's 0. All of the expressions are evaluated,
then all of the variables are bound to the respective results
of these expressions. So, "3" evaluates to 3, and"(+ a 1)"
evaluates to "(+ 0 1)" or 1. Then, a and b are bound to 3 and 1 respectively.
So, the value returned for (+ a b) is 4.
If you want sequential binding, you can nest the let expressions accordingly:
(define a 0)
(let ((a 3))
(let ((b (+ a 1))
(+ a b)))
This would bind evaluate 3 and bind it to a, then evaluate (+ a 1) to get 4 and bind it to b, then evaluate (+ a b) as (+ 3 4) or 7.
Scheme also includes a separate operator for defining sequential bindings (one variable, then the next, then the next, etc.), and it's called let*:
(define a 0)
(let* ((a 3)
(b (+ a 1))
(+ a b))
This would also return 7.
Semantics refers to what a programming language construct, such as
the let construct we just discussed, means. There are a number
of ways to describe the semantics of a programming language feature. One
of the easiest ways to describe the semantics of a particular feature is to
translate it into some other feature that is well understood. This is
called a translational semantics. In this section we will give a
translational semantics for the let expression of Scheme.
We know that a lambda expression binds variables. Since this section is about syntactic abstraction, you might guess that we can implement a let expression using a lambda expression. Indeed, you can.
Consider a let expression with the following form:
(let (( )
( )
.
.
.
( ))
)
The semantics of this expression, binds the value of
((lambda ( ...)
)
... )
Just as we could do without a for loop in a language like C++ (how would you do it instead?), we could do without a let statement in Scheme, but it would not be nearly as nice to read.
Lots of languages have features like this that are redundant with other features in the language but which make things a lot easier to read/write. These are called syntactic sugar. Like most sugar products, they aren't really necessary but make just make life a lot more enjoyable.
Don't make the mistake of thinking that this local binding rule is somehow unique to Scheme; the same semantics applies to local variables in languages such as Pascal and C. For example, consider the following Pascal program:
function foo(x:integer):integer;
var y: integer;
begin
y := 4;
foo := x + y;
end;
This program has the same meaning as the following program that does not use local variables:
function foo(x:integer):integer;
function bar(y:integer):integer;
begin
bar := x + y;
end;
begin
foo := bar(4);
end;
Remember, we said that procedures were just like any other type of data in Scheme. So, we can define local variables that are procedures just as we would any other type of variable:
(let ((sqr (lambda (x) (* x x)))
(cube (lambda (x) (* x x x))))
(+ (sqr 3) (cube 4))
This is especially useful when we want to define some "helper" functions that are used within a particular function but aren't otherwise accessible by the rest of our code.
Using let to define local procedures breaks down, though, for
recursive functions. Consider the following simplest (and admittedly, dumbest)
recursive function:
(let ((f (lambda () (f))))
(f))
This defines a function that does nothing but call itself, and then we call that function. Not that useful a program--but it should at least run, right? Well, here's what happens when we type it in:
reference to undefined identifier: f
So, what happened? We defined f, didn't we? Remember the order
in which things happen:
So, at the time we evaluate "(lambda () (f))", f
has not yet been defined. There's the problem: we can't build a nameless function
that calls f and then later give that function the name "f".
The solution is to use a separate construct that has to work a little harder
to set up the local variables. This is called "letrec"
and can be used to define recursive functions. The syntax is the same as for
let:
(letrec ((f (lambda () (f))))
(f))
This now runs, though I wouldn't advise typing it in for obvious reasons.
Question: Why have both let and letrec in the language if letrec
can do everything let can?
We've already seen Scheme's conditional operators like if and
cond. Scheme has other operators for working with boolean logic,
including and, or, and not.
Logical operators such as and and or have a special semantics. They have variable arity, which is nothing special, but there is something else.
To see what is special about them, let's consider a procedural definition of and using our evaluation model. When we evaluate a procedure, we
So, in the expression (and false true true true) we must evaluate each subexpression, before we apply and and determine that the expression is false. If these subexpressions were lengthy procedures, then they must all be evaluated first.
Many languages have short-circuited logical operators, which stop evaluating subexpressions as soon as the result of the whole is known. Scheme's and and or operators are short-circuited. So are C++'s and Java's. The following C++ or Java expression will never produce a divide-by-zero error:
if (x != 0 && y/x > 0) ...
nor will its Scheme equivalent:
(if (and (not (= x 0))
(> (/ y x) 0))
...)
We can make the following inductive semantic translations for and and or:
(and test_1 test_2 ... test_n)
(if test_1
(and test_2 ... test_n)
false
)
(or test_1 test_2 ... test_n)
(let ((*value* test_1))
(if *value*
*value*
(or test_2 ... test_n)
)
)
So, and and or don't follow the normal evalution
rule. You can't make your own functions that would work like they do:
(define my-and (lambda args)
(if (car args)
(apply my-and (cdr args))
#f
))
Why wouldn't this work like Scheme's and operator does?
All languages have things like these that must be evaluated in a special order
other than the normal evaluation rules for function calls. These are called
special forms. The operators for define, lambda,
let, let*, letrec, if, cond,
and, or, etc. are all special forms. +,
-, *, /, and not are built-in
functions, not special forms.
Make sure you know the difference between special forms and built-in functions. This isn't just a Scheme thing--it's a different inherent in all programming languages, and all interpreters and compilers treat special forms separately from built-in functions. C++ has lots of special forms, but it also has lots of functions built into standard libraries. The same applies to Java.
Last updated at 9:03 am on Friday, July 15, 2005.