What is the relationship between lists and pairs?
What is the difference between proper and improper
lists?
What is an interpreter?
What is the difference between y and 'y?
How can I cope with all of these parentheses?
How does that (apply apply (list procedure? ... thing on page 22 of EPL work?
What is a predicate? Where does the name
"predicate" come from?
What is the difference between a function and a procedure?
Is (lambda (x) (+ x
5)) a procedure?
Why does Scheme allow you to override things like the
+ operation?
What is lexical scoping?
What is a block-structured language?
Why does Scheme use prefix notation?
What is the relationship between lists and pairs?
A pair consists of two fields, the car and the cdr. Pairs are sometimes used for other things, but their
main use in Scheme is as building blocks for lists. A (linked) list containing n items is
represented by nn pairs. The car of the ith pair contains the ith list item,
and the cdr of the ith pair contains a reference (pointer) to the i+1st pair. The
cdr of the last pair is null. If the cdr of the last pair is anything other than null, then we have an improper list.
A list is proper if and only if one of the following is true: (a) it is empty, or (b) Its cdr is a proper list.
What is the difference between proper and
improper lists?
A proper list is the same kind of list that you saw in CSSE 220/230.
Each node (in Scheme, a node is known as a "pair" or "cons
cell") contains two parts, the data (car) and a
pointer to the next node (cdr).
The cdr of the last node in
a proper list is null. The external representation of a list is simply a
parenthesized collection of elements, such as (a
b c d e f g).
There is nothing to prevent you from putting something other than a null
pointer in the cdr
of the last node; if you do so, you get an improper list. For example, in (a b . c),
there are two pairs. The first pair contains a in its car,
and a pointer to the second pair in its cdr. The second node contains b
and c. In the early part of this
course, we will almost always use proper lists. The following transcript may help make things clearer:
> ; a proper list, constructed in a few different ways:
(list 2 3 4)
(2 3 4)
> (cons 2 (list 3 4))
(2 3 4)
> (cons 2 (cons 3 (cons 4 '())))
(2 3 4)
> '(2 . (3 . (4 . ())))
(2 3 4)
> ; an improper list, constructed in a couple of different ways:
(cons 2 (cons 3 4))
(2 3 . 4)
> '(2 . (3 . 4))
(2 3 . 4)
> (define proper '(2 3 4))
> (define improper '(2 3 . 4))
> (cddr proper)
(4)
> (cddr improper)
4
> (cdddr proper)
()
> (cdddr improper)
Exception in cdddr: incorrect list structure (2 3 . 4)
> (length improper)
Exception in length: (2 3 . 4) is not a proper list
> (length proper)
3
What is an interpreter?
An interpreter is simply a program that reads instructions in some
programming language and "executes" them. A good example is a typical
microprocessor. It reads a program in that processor's machine language and
executes it. An interpreter for a high level language does a similar thing, but
it uses software, not just hardware, to do the interpretation. A compiler
usually translates a high-level language source file into a machine language
object file which can be interpreted by the hardware. A Java compiler
translates Java source code into Java Byte Code, which can then be interpreted
by the Java Virtual Machine. Many Scheme interpreters (including Chez
Scheme, but not Petite Chez scheme) compile source code into byte code
before executing it, and have a facility for saving the compiled code so that
it will load faster next time.
What is the difference between y and
'y?
Both involve the symbol y.
When used by itself, y stands
for the value of the variable named y,
and causes the Scheme interpreter to look up the current value of this
variable. The quote prevents the evaluation, and 'y just stands for the symbol y itself. In Scheme, as in
Maple, it is possible to do purely symbolic computations, so there needs to be
a way to represent an unevaluated symbol. Scheme's way is to quote it. Note
that 'y is an abbreviation for (quote
y)
How can I cope with all of these parentheses?
Like in any programming language, breaking lines at appropriate places and
using a reasonable, consistent indentation scheme (no pun intended) can help a
lot. Emacs can also help:
Esc ctrl-f moves the cursor to
the end of the next (sub)expression.
Esc ctrl-b moves the cursor to
the beginning of the previous (sub)expression.
Esc ctrl-k deletes the next
(sub) expression and places it in the kill ring (so it can be pasted in
somewhere else via ctrl-y).
When
you type a closing paren (or closing brace or
bracket), Emacs temporarily blinks the matching
opening symbol.
Mainly, you'll just need a couple of weeks of using Scheme, and
you'll get used to the parentheses.
How does that (apply apply (list procedure? ... thing on page 22 of EOPL-1 work? A few years ago, I wrote a detailed explanation. Even with the explanation, I admit that this example is a bit heavy for a Scheme beginner. See: apply.html .
What is a predicate? Where does the name
"predicate" come from?
A predicate is any procedure that returns a true or false value. You can
recognize a built-in Scheme predicate because its name (almost always) ends in
a question mark (an exception is =). You should give similar names to
predicates that you write (such as divisible-by-7?).
The name comes from mathematical logic. My Webster's New World College
Dictionary gives this definition for predicate :
"something that is affirmed or denied about the subject of a
proposition." Thus the application (integer? x) is used to affirm or deny that
the variable x currently contains an integer value.
What is the difference between a function and a
procedure?
The generic CS lingo is that functions return values, while procedures
don't return anything. Java metalanguage uses the word "method" for
both, and C uses "function" for both.
Some languages, such as Pascal,
In C they are all called functions
but some are used as procedures; in
Scheme they are all called
procedures but most are used as
functions. From now on in our discussion of Scheme, I will usually mean the same thing
when I say "function" or "procedure".
Is (lambda (x) (+
x 5))
a procedure?
Not exactly. (lambda (x) (+ x 5)) is a piece of Scheme code.
When the interpreter evaluates this code, it builds a data structure that
represents an "add 5" procedure (Later we will call such a data
structure a closure.) So strictly speaking a procedure is a Scheme
internal thing, while a lambda expression is source code. When the context does
not allow for easy confusion, however, it is often convenient to refer to the lambda
expression itself as a procedure.
When we are writing a Scheme interpreter, it will be very important to distinguaish between the code (lambda expression) and the
procedure (an internal data structure of our interpreter) that is created when
we evaluate that code.
Why does Scheme allow you to override things like the
+ operation?
In Scheme, there are no "arithmetic operators". + is simply a
variable name, and its default value is the addition procedure. In Scheme,
as in many other languages, you can change the value of a variable. Thus you can change the
value that is bound to +.
What is lexical scoping?
In a lexically scoped language, you can determine the scope of each variable declaration/introduction
by looking at the code. The opposite is dynamic scoping in which the scope of a
variable depends on the order in which things have been executed. We will examine these in some detail about 2/3 of the
way through this course.
What is a block-structured language?
In a block-structured language, code declared in an inner block can refernce variables that are
defined in an outer block that encloses the inner block, but not the other way around. In java, blocks are created by the use of curly braces; in Scheme by an inner let, lambda, let*, or letrec.
What are symbols, and how are they used?
I am not sure that there is a good short answer to this question, but here is a good long answer:
ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_103.html
Why does Scheme use prefix notation?
Claude's opinion: because prefix notation is simple, flexible, and easy to learn/use.