See also
This chapter introduces the Scheme programming language from scratch.
Scheme is a programming language whose main syntactic unit is the expression. The syntax of Scheme is fully parenthesized and its operations use the prefix notation.
In the standard notation of mathematics, binary operators are infix in that they are written between their two operands. For example, to express the addition of 2 and 3, one writes:
2 + 3
Operations are nested using parentheses:
(2 + 3) - 4
In the prefix notation, operators are written before their operands. For example, to express the addition of 2 and 3, one writes:
+ 2 3
Nested operations need no parentheses:
- + 2 3 4
In the postfix notation, operators are written after their operands. For example, to express the addition of 2 and 3, one writes:
2 3 +
Nested operations need no parentheses:
2 3 + 4 -
Scheme uses the prefix notation, in a fully parenthesized way, like Lisp:
(+ 2 3)
(- (+ 2 3) 4)
So to say it again, parentheses in Scheme are not, ah, parenthetical as when writing algebraic expressions in mathematics, to disambiguate. They play an absolutely essential role to state expressions, and so all of them need to be systematically written down.
Note: in the following grammar, braces {...} are a meta-notation to group what is between “{” and “}”. When followed by a “+”, it means “once or more”, and when followed by a “*”, it means “zero times or more”.
An identifier is written with letters, digits, and most of the funky characters on our keyboard (-, *, ?, !, etc.), excluding quote, backquote, and comma as well as # in first position. One can Read The Friendly Manual (the 4 first paragraphs) for detail, but this level of detail won’t be at the exam.
Scheme comments start with a semi-colon (i.e., ;) and go until the end of the line.
Most of this chapter illustrates part of the BNF above through an interactive session with Chez Scheme’s read-eval-print loop:
Chez Scheme Version 9.5.4
Copyright (c) 1984-2020 Cisco Systems, Inc.
>
For further precisions and details, look at Kent Dybvig’s textbook (and use its index, as well as the index of the Chez Scheme Version 8 User’s Guide). The rest of the BNF is addressed in a subsequent chapter, culminating in the midterm project where a self-applicable syntax checker will be implemented.
Pablito: Chez Scheme’s read-eval-print loop?
Halcyon: Chez Scheme is the implementation of Scheme we are considering here.
Pablito: Thanks. And its read-eval-print loop?
Anton: We are prompted to type something after > – which is the prompt of the read-eval-print loop.
Dana: If we type ^D – i.e., the end-of-file character in many operating systems – the loop stops and we exit the Scheme world.
Alfrothul: Then either of two things happens, depending on whether what we typed is syntactically correct or not.
Anton: If it is syntactically incorrect, an error message is printed and the read-eval-print loop is resumed.
Alfrothul: And if it is syntactically correct, it is evaluated.
Bong-sun: And then either of three things happens:
Anton: If the evaluation raises an error, an error message is printed and the read-eval-print loop is resumed.
Alfrothul: And if the evaluation yields a value, this value is printed and the read-eval-print loop is resumed.
Pablito: And if the evaluation does not terminate?
Dana: Well, this one is a conendrum because is the evaluation actually not terminating or has it just not terminated yet and we should just keep waiting?
Pablito: So what do we do?
The fourth wall: How about you all just wait until the postlude about divergence at the end of this chapter?
Halcyon: Sure, we can do that.
The fourth wall: Thanks. For now, let’s study Scheme expressions, starting with numbers.
Numbers evaluate to themselves.
Here is a sample of integers:
> 33
33
> -22
-22
> +11
11
> 0
0
> +0
0
> -0
0
>
Integers are normalized on the fly as they are read:
> 00100
100
>
NB. Natural numbers are implicitly represented as non-negative integers, and positive natural numbers are implicitly represented as positive integers.
Here is a sample of rationals:
> 1/2
1/2
>
Rationals are normalized on the fly as they are read:
> 4/6
2/3
> -6/4
-3/2
> 4/1
4
> 6/3
2
> 007/001
7
>
The denominator of a rational number cannot be 0:
> 3/0
Exception in read: cannot represent 3/0
Type (debug) to enter the debugger.
>
Here is a sample of reals:
> 1.23
1.23
> -1.23
-1.23
> 1.000
1.0
> 00100.000
100.0
>
There are two Booleans and each of them evaluates to themselves.
For example:
> #t
#t
> #f
#f
>
A Scheme character is written with a # followed by a \ and then the character itself. For example, the character c is written as #\c and the character " (double quote) is written as #\".
Characters evaluate to themselves.
For example:
> #\c
#\c
>
#\"
>
Food for thought:
Pablito: Hang on.
Halcyon: Sure.
Pablito: This is the part where we spring into action.
Halcyon: Let’s spring into action!
Pablito: So a Scheme character is written with a # followed by a \ and then the character itself.
Halcyon (sententiously): Yes. That’s what is written just above.
Pablito: But what if this character is # or \?
Halcyon (meditatively): That is indeed the question.
Pablito: Well, let’s try:
> #\#
#\#
>
Halcyon: OK, that’s one.
Pablito: And here is the other:
> #\\
#\\
>
Halcyon: All right!
Bong-sun: Let’s see. The space character now:
> #\
#\space
>
Halcyon: Aha, it prints as #\space. Let me try, let me try:
> #\space
#\space
>
Pablito: So characters are self-evaluating, but some are aliases of others.
Bong-sun: Looks like.
Pablito: OK. Let’s move on.
Scheme strings are delimited by double quotes and contain ordinary characters.
Strings evaluate to themselves.
For example:
> "hello world"
"hello world"
>
To specify a double quote in a string, one prefixes it with a backslash. To specify a backslash in a string, one also prefixes it with a backslash:
> "hello \" world"
"hello \" world"
> "hello \\ world"
"hello \\ world"
>
Bong-sun (muttering to herself): What about the empty string? Well, the empty string contains zero characters so let’s try:
> ""
""
>
Bong-sun: OK.
Evaluating the expression
(time e)
yields the result of evaluating
e
and, as a byproduct, prints out how much time and space were spent evaluating e.
For example:
> (time 32)
(time 32)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
32
>
Alfrothul (muttering to himself): How about measuring how much time it takes to measure time:
> (time (time 32))
(time 32)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time (time 32))
no collections
1 ms elapsed cpu time
0 ms elapsed real time
1008 bytes allocated
32
>
Anton (entering the fray): And how about measuring how much time it takes to measure the measuring of time:
> (time (time (time 32)))
(time 32)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time (time 32))
no collections
0 ms elapsed cpu time
0 ms elapsed real time
1008 bytes allocated
(time (time (time 32)))
no collections
0 ms elapsed cpu time
0 ms elapsed real time
2016 bytes allocated
32
>
Halcyon: We have such beautiful navels, don’t we?
An if-expression consists of a test, a consequent, and an alternative, all of which are expressions.
To evaluate an if-expression, the test is first evaluated:
Illustration 1: If the test evaluates to #f, the consequent is ignored and the alternative is evaluated:
> (if #f 1 2)
2
> (if #f (time 1) 2)
2
>
Illustration 2: If the test evaluates to #t, the alternative is ignored and the consequent is evaluated:
> (if #t 1 2)
1
> (if #t 1 (time 2))
1
>
Illustration 3: The test could be an if-expression:
> (if (if #t #t #f) 1 2)
1
> (if (if #f #t #f) 1 2)
2
> (if (if #t #f #t) 1 2)
2
> (if (if #f #f #t) 1 2)
1
>
Illustration 4: The consequent could be an if-expression (and so could the alternative):
> (if #t (if #f 0 1) 2)
1
> (if (time #t) (if (time #f) (time 0) (time 1)) (time 2))
(time #t)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time #f)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time 1)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
1
>
Illustration 5: Tests that evaluate to another value than #f are interpreted as #t:
> (if 33 1 2)
1
> (if #\c 1 2)
1
> (if "hello world" 1 2)
1
>
Bong-sun: In the description of how to evaluate an if-expression, there are three cases.
Alfrothul: Yes – either evaluating the test does not terminate, or evaluating the test raises an error, or evaluating the test yields a value.
Anton: And in the latter cases, there are two sub-cases – either the value is #f or it is another value.
Bong-sun: But then why are the illustrations only about the third case?
Anton: True that. We are only shown examples where the tests evaluate to a value.
Dana: That’s because we do not know yet how to write an expression whose evaluation does not terminate and because we do not know yet how to write an expression whose evaluation raises an error.
Halcyon: But we will soon, won’t we?
Alfrothul: I think we can count on that.
The fourth wall: Can we proceed?
Bong-sun: Thank you all. And yes, let’s.
An and-expression comprises zero or more sub-expressions.
Evaluating an and-expression consists in evaluating its sub-expressions from left to right under the following conditions:
So for example, given any (syntactically valid) Scheme expressions e1, e2, and e3, to evaluate (and e1 e2 e3), we need to process its arguments, which are e1, e2, and e3.
To process e1, e2, and e3, we first evaluate e1:
To process e2 and e3, we first evaluate e2:
All in all, if evaluating e1 and e2 yields values that are not #f, then evaluating (and e1 e2 e3) reduces to evaluating e3.
Illustration 1: Evaluating an and-expression that comprises no sub-expressions yields #t:
> (and)
#t
>
Illustration 2: Evaluating an and-expression that comprises one sub-expression yields the result of evaluating this sub-expression:
> (and #t)
#t
> (and #f)
#f
>
Illustration 3: When an and-expression comprises several sub-expressions, all the first of whom evaluate to values that are not #f, evaluating this and-expression yields the result of evaluating the last sub-expression:
> (and #t #t)
#t
> (and #t #f)
#f
> (and 1 2 3)
3
> (and 1 2 3 4 5 #f)
#f
>
Illustration 4: When an and-expression comprises several sub-expressions, the first of whom evaluate to values that are not #f and the next one evaluates to #f, evaluating this and-expression yields #f and the remaining sub-expressions are ignored:
> (and 1 #f 3)
#f
> (and (time 1) (time #f) (time 3))
(time 1)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time #f)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
#f
>
Anton: Wow.
Alfrothul: Yes, Anton?
Anton: What a complicated way to explain how and-expressions are evaluated.
Alfrothul: How would you explain it?
Anton: Well, evaluate all the expressions from left to right. The first one that diverges – by which I mean whose evaluation does not terminate – makes the and-expression diverge. The first one that raises an error – by which I mean whose evaluation raises an errror – makes the and-expression raise this error. The first one that evaluates to #f makes the and-expression evaluate to #f. And if all the sub-expressions evaluate to values that are not #f, the and-expression evaluates to the last value.
Alfrothul: Yes, it is simpler.
Mimer: But it is inaccurate for Scheme.
Anton: Inaccurate for Scheme?
Mimer: Yes. In the explanation, it is essential to say that if evaluating all but the last sub-expressions evaluate to a value that is not #f, then evaluating the and-expression reduces to evaluating the last sub-expression.
Dana: And indeed all the explanations of how compound forms are evaluated contain “evaluating the compound form reduces to evaluating [one of its sub-expressions]”.
Bong-sun: Yes. That is true for if-expressions, and-expressions, or-expressions, and applications in this chapter – I have just checked.
Mimer: And that is essential.
Alfrothul: Why?
Mimer: I hate to say it, but you are not in position to know yet.
Alfrothul: You mean you don’t want to make a forward reference in the course material?
Mimer: Yes.
Halcyon (boldly): Let me guess. Is it because of tail recursion?
The Greek chorus: EVERYBODY LOOKS AT HALCYON.
Mimer: Interesting guess, Halcyon. Why are you mentioning tail recursion?
Halcyon (adjusting his new moustache with panache): Well, in the lecture, the background picture features the message “Tail-recursion is its own reward.”, so it is an easy guess.
Mimer: And a good one too, but since “recursion” and a fortiori “tail recursion” are not defined yet, you will all have to be patient for now.
Anton: So what’s inaccurate in my explanation?
Dana: Its last component, namely “And if all the sub-expressions evaluate to values that are not #f, the and-expression evaluates to the last value.”
Anton: Why?
Dana: Because all the sub-expressions – including the last one – are computed before the last value is returned, so evaluating the and-expression does not reduce to evaluating its last sub-expression.
Anton: Which Mimer says is essential. OK, I’ll accept that for now.
Mimer: Thanks. Let’s move on.
The goal of this exercise is to restate and-expressions using if-expressions so that each restated expression means the same as the corresponding given and-expression.
Make sure that in each restated expression, the explanation of how it is evaluated contains “evaluating the restated expression reduces to evaluating [one of its sub-expressions]”.
Subsidiary questions:
Restate the following and-expressions so that they do not use and and so that each restated expression means the same as the corresponding given and-expression:
An or-expression comprises zero or more sub-expressions.
Evaluating an or-expression consists in evaluating its sub-expressions from left to right under the following conditions:
So for example, given any (syntactically valid) Scheme expressions e1, e2, and e3, to evaluate (or e1 e2 e3), we need to process its arguments, which are e1, e2, and e3.
To process e1, e2, and e3, we first evaluate e1:
To process e2 and e3, we first evaluate e2:
All in all, if evaluating e1 and e2 yields #f, then evaluating (or e1 e2 e3) reduces to evaluating e3.
Illustration 1: Evaluating an or-expression that comprises no sub-expressions yields #f:
> (or)
#f
>
Illustration 2: Evaluating an or-expression that comprises one sub-expression yields the result of evaluating this sub-expression:
> (or #t)
#t
> (or #f)
#f
>
Illustration 3: When an or-expression comprises several sub-expressions, all the first of whom evaluate to #f, evaluating this or-expression yields the result of evaluating the last sub-expression:
> (or #f #f)
#f
> (or #f #t)
#t
> (or #f #f #t)
#t
> (or #f #f #f 42)
42
>
Illustration 4: When an or-expression comprises several sub-expressions, the first of whom evaluate to values #f and the next one evaluates to a value that is not #f, evaluating this or-expression yields this value and the remaining sub-expressions are ignored:
> (or #f #t #f)
#t
> (or #f 2 #f)
2
> (or (time #f) (time 2) (time #f))
(time #f)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time 2)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
2
>
We will revisit and-expressions and or-expressions later on.
A definition is composed of a name (an identifier that is globally visible – we refer to it as a “global name”) and a definiens (an expression).
To evaluate a definition, the definiens is first evaluated.
If evaluating the definiens does not terminate, then evaluating the definition does not terminate either.
If evaluating the definiens raises an error, then evaluating the definition raises this error.
If evaluating the definition yields a value, the global name is bound to this value and henceforth it denotes this value:
> (define x (time 1))
(time 1)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
> x
1
> (define y x)
> y
1
>
If the name in the definition was already bound, it is henceforth re-bound to the value of the definiens:
> y
1
> (define y 2)
> y
2
>
This redefinition, however, does not affect the other global bindings. In the following scenario,
x is first bound to 3; henceforth, x denotes 3;
z is then bound to the denotation of x, i.e., 3; henceforth, both z and x denote 3;
x is then redefined and bound to 4; henceforth, x denotes 4 while z still denotes 3;
finally, z is redefined and bound to 5; henceforth, z denotes 5 while x still denotes 4:
> (define x 3)
> x
3
> (define z x)
> z
3
> x
3
> (define x 4)
> x
4
> z
3
> (define z 5)
> z
5
> x
4
>
It is an error to evaluate an unbound variable. Once defined, however, a variable is bound forever (i.e., until the end of the session with Chez Scheme):
> foobarbaz
Exception: variable foobarbaz is not bound
Type (debug) to enter the debugger.
> (define foobarbaz 32)
> foobarbaz
32
> ^D
Process scheme finished
Chez Scheme Version 9.5.4
Copyright (c) 1984-2020 Cisco Systems, Inc.
> foobarbaz
Exception: variable foobarbaz is not bound
Type (debug) to enter the debugger.
>
N.B.: ^D is obtained with C-d, i.e., by pressing the control key and typing the letter d.
A lambda-abstraction consists of formal parameters and a body. The body is an expression. The formal parameters consist of zero or more variables that are grouped between parentheses. All these variables must be distinct.
Evaluating a lambda-abstraction yields a user-defined procedure, a Scheme value that implements a function.
Illustration 1: The following lambda-abstractions have zero, one, and two formal parameters:
> (lambda () 33)
#<procedure>
> (lambda (x) x)
#<procedure>
> (lambda (x y) x)
#<procedure>
>
Illustration 2: When a lambda-abstraction has at least two formal parameters, the formal parameters must be distinct:
> (lambda (x x) x)
Exception: invalid parameter list in (lambda (x x) x)
Type (debug) to enter the debugger.
>
If you have a procedure with ten parameters,you probably missed some.—Alan Perlis‘s programming epigram #11
In a lambda-abstraction with non-fixed arity, the formal parameters consist of one variable or of zero or more variables that are grouped between parentheses, possibly with a dot before the last variable. All these variables must be distinct.
Illustration 1: A lambda-abstraction can just have one formal parameter:
> (lambda xs xs)
#<procedure>
>
Illustration 2: A lambda-abstraction can have several formal parameters, the last of which is preceded by a dot, and all of which must be distinct:
> (lambda (x y . zs) x)
#<procedure>
> (lambda (x y . y) x)
Exception: invalid parameter list in (lambda (x y . y) x)
Type (debug) to enter the debugger.
>
Many predefined procedures exist in Scheme, and are denoted by variables:
> +
#<procedure +>
> -
#<procedure ->
> not
#<procedure not>
> exit
#<procedure exit>
>
(We will study these procedures soon.)
Procedures can be applied to arguments, as seen next.
The arity of a procedure is the number of arguments this procedure can be applied to:
A user-defined procedure has a fixed arity if it is the result of evaluating a lambda-abstraction constructed with <lambda-formals-with-fixed-arity>. Its arity is then the number of variables among its formal parameters.
For example, the procedure denoted by (lambda () 33) has arity 0 and the procedure denoted by (lambda (x1 x2 x3 x4 x5 x6 x7 x8 x9 x10) 33) has arity 10.
A user-defined procedure has a non-fixed arity (or, as coined by Christopher Strachey, it is variadic) if it is the result of evaluating a lambda-abstraction constructed with <lambda-formals-with-non-fixed-arity>.
For example, the procedure denoted by (lambda xs 33) and the procedure denoted by (lambda (x1 x2 . xs) 33) are variadic. The first one can be applied to any number of arguments. The second one must be applied to at least two arguments.
User-defined variadic procedures will be addressed in a subsequent chapter.
An application consists of an operator (which is an expression, i.e., not a keyword) and zero or more operands (which are expressions).
When evaluating the expression
(e0 e1 e2 ... eN-1 eN)
the sub-expressions e0, e1, ..., and eN are evaluated in an unspecified order:
If evaluating one of these sub-expressions does not terminate, then evaluating this application does not terminate either.
If evaluating one of these sub-expressions raises an error, then evaluating this application raises this error too.
Otherwise evaluating all of these sub-expressions yields the values v0, v1, ..., and vN.
If v0 is not a procedure, evaluating the application yields an error.
Otherwise v0 is a procedure. The values v1, ..., and vN are the actual parameters of the application. (Informally, both of e1, ..., and eN and of v1, ..., and vN are referred to as “the arguments” of this procedure when there is no ambiguity.)
If v0 is a fixed-arity procedure of arity N, say the result of evaluating (lambda (x1 ... xN) e), then the formal parameters x1, ..., xN are respectively bound to the actual parameters v1, ..., vN, and evaluating the application reduces to evaluating e in a local environment that extends the current environment and where each of the formal parameters denotes the corresponding actual parameter:
> ((lambda (x1 x2 x3) x1) 1 2 3)
1
> ((lambda (x1 x2 x3) x2) 1 2 3)
2
> ((lambda (x1 x2 x3) x3) 1 2 3)
3
>
This way to respectively bind each of the formal parameters to the corresponding actual parameter is said to be “by position”: the first formal parameter is bound to the first actual parameter, the second to the second, etc.
It is an error to apply a user-defined procedure with fixed arity when its number of formal parameters does not match the number of actual parameters. So if v0 is a procedure of arity M, say the result of evaluating (lambda (x1 ... xM) e), where N (the number of actual parameters) and M (the number of formal parameters) are distinct, then evaluating the application yields an error:
> ((lambda (x) x) 10 20)
Exception: incorrect argument count in call ((lambda (x) x) 10 20)
Type (debug) to enter the debugger.
> ((lambda (x y) x) 10)
Exception: incorrect argument count in call ((lambda (x y) x) 10)
Type (debug) to enter the debugger.
>
We will see how to apply a procedure with non-fixed arity in a later chapter.
Loki: I just thought of an amusing question for the exam.
Mimer (prudently): Yes, Loki?
Loki: This question is inspired by Alan Perlis’s epigram about procedures with ten parameters.
Mimer: OK?
Loki: It involves a procedure with ten formal parameters and only eight actual parameters.
Mimer: Figures.
Loki: See? The procedure has ten formal parameters but it is missing some actual parameters.
Mimer: Either that or it should have eleven formal parameters but we missed one.
Loki: True. That would make another amusing question for the exam.
Mimer: Well...
Loki: I didn’t think you had it in you, Mimer.
Mimer: Er... Thanks but no thanks. I don’t have it in me.
Is there an observable difference between the lambda-abstractions (lambda (x) x) and (lambda (y) y)?
Hint: They both implement the identity function.
Corollary: Do names of formal parameters matter?
Each of these two lambda-abstractions evaluate to a procedure, and the only thing we can do with these procedures is to apply them. Since they both implement the identity function, applying them to the same input returns the same output. So we cannot distinguish them: There is no observable difference between these two procedures.
Corollary: The names of formal parameters do not matter.
As in the C programming language, the order in which actual parameters are evaluated is unspecified in Scheme, so that the programmer does not rely on it.
Here is a simple illustration. The computation of each actual parameter is timed and the scenario illustrates that the timed computations does not always take place in the same order:
> ((lambda (a b c) a) (time 1) (time 2) (time 3))
(time 2)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time 3)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time 1)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
1
> ((lambda (a b c) b) (time 1) (time 2) (time 3))
(time 1)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time 3)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time 2)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
2
> ((lambda (a b c) c) (time 1) (time 2) (time 3))
(time 1)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time 2)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
(time 3)
no collections
0 ms elapsed cpu time
0 ms elapsed real time
0 bytes allocated
3
>
In the body of the lambda-abstraction that gave rise to it, a procedure may refer to a yet-undefined global variable. Applying this procedure then raises an error, unless this global variable has been defined in the meanwhile:
> (define foo (lambda () foobarbaz))
> (foo)
Exception: variable foobarbaz is not bound
Type (debug) to enter the debugger.
> (define foobarbaz 32)
> (foo)
32
>
The global variable referred to in a procedure denotes the current value of this global variable:
> (define foobarbaz 33)
> (foo)
33
>
A trace-lambda-abstraction is much like a lambda-abstraction: in addition, it is given a name. Evaluating a trace-lambda-abstraction yields a “traced procedure”. A traced procedure behaves just like a normal user-defined procedure except that, when it is applied, it prints its actual parameters and then its result. This printing feature is precious in that it provides a way to visualize the evaluation process of Scheme.
In this scenario, a traced procedure is applied to 1, 10, and 100, and returns one of its arguments:
> ((trace-lambda example (x1 x2 x3) x1) 1 10 100)
|(example 1 10 100)
|1
1
> ((trace-lambda another-example (x1 x2 x3) x2) 1 10 100)
|(another-example 1 10 100)
|10
10
>
In this scenario, a traced version of the identity procedure is applied 0, 1, 2, and then 3 times:
> ((trace-lambda baz (p) 32) (trace-lambda identity (x) x))
|(baz #<procedure>)
|32
32
> ((trace-lambda baz (p) (p 32)) (trace-lambda identity (x) x))
|(baz #<procedure>)
|(identity 32)
|32
32
> ((trace-lambda baz (p) (p (p 32))) (trace-lambda identity (x) x))
|(baz #<procedure>)
| (identity 32)
| 32
|(identity 32)
|32
32
> ((trace-lambda baz (p) (p (p (p 32)))) (trace-lambda identity (x) x))
|(baz #<procedure>)
| (identity 32)
| 32
| (identity 32)
| 32
|(identity 32)
|32
32
>
In this scenario, two traced versions of the identity procedure are applied in turn:
> ((lambda (p q) (p (q (p (q 32)))))
(trace-lambda foo (x) x)
(trace-lambda bar (y) y))
|(bar 32)
|32
|(foo 32)
|32
|(bar 32)
|32
|(foo 32)
|32
32
>
The final scenario uses the predefined procedure + that adds its arguments:
> (+ 2 3)
5
> (+ 1 0)
1
> (+ 10 0)
10
>
Two traced procedures that respectively add 1 and add 10 to their argument are applied in turn:
> ((lambda (p q) (p (q (p (q 0)))))
(trace-lambda 1+ (x) (+ 1 x))
(trace-lambda 10+ (y) (+ 10 y)))
|(10+ 0)
|10
|(1+ 10)
|11
|(10+ 11)
|21
|(1+ 21)
|22
22
>
Make sure you appreciate how and in which order procedures are called, what actual parameters they are passed, and what results they return.
A predicate is a procedure that yields a Boolean. For each of its types (number, Boolean, character, string, procedure, etc.), Scheme offers a type predicate, i.e., a unary procedure testing the type of its argument.
Here how values are tested for numbers:
> (number? 3)
#t
> (number? "hello world")
#f
>
Here how values are tested for integers:
> (integer? 3)
#t
> (integer? 3/4)
#f
>
Here how values are tested for rationals:
> (rational? 3/4)
#t
>
Here how values are tested for booleans:
> (boolean? #t)
#t
> (boolean? 3)
#f
>
Here how values are tested for characters:
> (char? #\f)
#t
> (char? #f)
#f
> (char? "foo")
#f
>
Here how values are tested for strings:
> (string? "bar")
#t
> (string? 3)
#f
> (string? #\c)
#f
>
Pablito: So in Scheme, characters and strings have distinct types?
Mimer: Yes they do. Well observed, Pablito.
Here how values are tested for procedures:
> (procedure? 32)
#f
> (procedure? number?)
#t
> (procedure? procedure?)
#t
> (procedure? (lambda (x) x))
#t
> (procedure? (trace-lambda identity (x) x))
#t
>
Pablito: Wow, did you see how procedure? was applied to itself just above?
Bong-sun: Yes. The result is #t since procedure? denotes a procedure.
Pablito: Right. Just before that, procedure? was applied to number?, which also denotes a procedure, so the result was also #t.
Anton: So if we applied number? to itself...
Alfrothul: ...the result would be #f since number? does not denote a number.
Halcyon: OK.
Scheme features numeric operations such as addition, subtraction, multiplication, division, exponentiation, equality, and comparison over integers, rationals, and reals.
Addition:
> (+ 10 20)
30
> (+ 2/5 1/5)
3/5
> (+ (+ 2/5 1/5) 2/5)
1
> (+ 10.0 20.5)
30.5
> (+ 10 20.5)
30.5
>
Subtraction:
> (- 10 20)
-10
>
Multiplication:
> (* 10 20)
200
>
Division:
> (/ 10 20)
1/2
>
Quotient:
> (quotient 14 4)
3
>
Remainder:
> (remainder 14 4)
2
>
Exponentiation:
> (expt 2 0)
1
> (expt 2 10)
1024
> (expt 10 3)
1000
>
Strictly less than:
> (< 10 20)
#t
>
Less than or equal to:
> (<= 10 20)
#t
> (<= 10 10)
#t
>
Equal to:
> (= 10 20)
#f
> (= 10 10)
#t
> (= 10 20)
#f
>
Greater than or equal to:
> (>= 10 10)
#t
> (>= 10 20)
#f
>
Strictly greater than:
> (> 10 20)
#f
>
Equal to zero:
> (zero? 0)
#t
> (zero? 10)
#f
>
Absolute value:
> (abs 10)
10
> (abs -10)
10
>
Maximum:
> (max 1 2)
2
> (max 2 1)
2
>
Minimum:
> (min 1 2)
1
> (min 2 1)
1
>
Several numeric procedures are variadic.
Addition:
> (+ 1 10)
11
> (+ 1 10 100)
111
> (+ 1 10 100 1000)
1111
>
Subtraction:
> (- 1111 100)
1011
> (- 1111 100 10)
1001
> (- 1111 100 10 1)
1000
>
Multiplication:
> (* 1 2)
2
> (* 1 2 3)
6
> (* 1 2 3 4)
24
> (* 1 2 3 4 5)
120
>
Equality:
> (= 1 1)
#t
> (= 1 1 1)
#t
> (= 1 1 1 2)
#f
>
Scheme features Boolean negation (its name is not), though this procedure is simple to define as a user-defined procedure:
(define not-as-a-user-defined-procedure
(lambda (v)
(if v
#f
#t)))
Here is Boolean negation in action:
> (not #t)
#f
> (not #f)
#t
> (not 32)
#f
>
> (not-as-a-user-defined-procedure #t)
#f
> (not-as-a-user-defined-procedure #f)
#t
> (not-as-a-user-defined-procedure 32)
#f
>
Food for thought:
The following procedure negates the negation of its argument:
(define not-not
(lambda (v)
(not (not v))))
Payment is never not a factor.
Define a procedure who-s-not-not-there that also negates the negation of its argument but does not use not. How does your procedure compare to not-not? (Try it on #t, #f, and 32.)
The following procedure negates the negation of its negated argument:
(define not-not-not
(lambda (v)
(not (not (not v)))))
No, I don’t know where he’s not.
Define a procedure who-s-not-not-not-there that also negates the negation of its negated argument but does not use not. How does your procedure compare to not-not-not?
Consider the four following definitions:
(define not-and
(lambda (b1 b2)
(not (and b1 b2))))
(define not-or
(lambda (b1 b2)
(not (or b1 b2))))
(define and-not-not
(lambda (b1 b2)
(and (not b1) (not b2))))
(define or-not-not
(lambda (b1 b2)
(or (not b1) (not b2))))
How many distinct functions are implemented by these dyadic procedures (i.e., procedures with two formal parameters) when they are applied to Boolean values?
Any thoughts about that?
Scheme features a procedure string with a non-fixed arity. Given a series of characters, it returns the corresponding string:
> (string)
""
> (string #\a)
"a"
> (string #\a #\b)
"ab"
> (string #\a #\b #\c)
"abc"
> (string #\h #\e #\l #\l #\o #\ #\w #\o #\r #\l #\d)
"hello world"
>
It is an error to apply string to values that are not characters.
Scheme features a procedure string-length that, given a string, returns its length:
> (string-length "hello world")
11
> (string-length "hello \" world")
13
> (string-length "\"")
1
> (string-length "")
0
>
It is an error to apply string-length to 0 argument, to more than one argument, and to a value that is not a string.
Scheme also features a procedure string-ref that, given a string and a natural number that can index this string, returns the corresponding character:
> (string-ref "abc" 0)
#\a
> (string-ref "abc" 1)
#\b
> (string-ref "abc" 2)
#\c
> (string-ref "abc" 3)
Exception in string-ref: 3 is not a valid index for "abc"
Type (debug) to enter the debugger.
> (string-ref "abc" -1)
Exception in string-ref: -1 is not a valid index for "abc"
Type (debug) to enter the debugger.
>
One can also concatenate strings in Scheme, using the predefined procedure string-append:
> (string-append "foo" "bar")
"foobar"
> (string-append "" "bar")
"bar"
> (string-append "foo" "")
"foo"
> (string-append "foo" "bar" "baz")
"foobarbaz"
> (string-append "foo")
"foo"
> (string-append)
""
>
Anton: There is something weird about string-length.
Alfrothul: Yes?
Anton: It is supposed to count the number of characters in a given string, right?
Alfrothul: Yes.
Anton: Then why does it returns 1 in the following example instead of 2? We can see that the string "\"" contains two characters, not one:
> (string-length "\"")
1
>
Alfrothul: That’s because the backslash is not a character in the string, it is an indication that the character that follows it is a character that is part of the string, not the indication that the string has ended.
Anton: Ah. Because I was also wondering why the string starts once but ends twice.
Alfrothul (suddenly looking preoccupied): Ah.
Dana (jumping in): Anton, are you familiar with air quotes?
Anton (mimicking two air quotes): You mean like this. I use them to quote a word or a sentence.
Dana: How would you quote the double quote sign?
Anton: I would mimick two air quotes and I would say “a double quote”.
Dana: And if you were writing that down, the result would be """.
Anton: Yes it would.
Dana: But that’s confusing.
Anton: Yes it is. Wait. To quote the double quote sign, I would mimick two air quotes and I would say “a double quote sign”.
Dana: Right. And you would do that because?
Anton: Because I want to distinguish betwen the double quote that I use to quote and the quote that I am quoting.
Dana: Excellent. That’s the rôle of the backslash in the string above: It is written "\"" to signify that this string contains one character, and this character is the character used to delimit strings. Look:
> (string-ref "\"" 0)
#\"
>
Anton: Thanks, Dana. So there isn’t anything wrong with string-length.
Dana: Yup.
Pablito: Er...
Dana: Yes, Pablito?
Pablito: The result of (string-ref "\"" 0)...
Dana: Yes, #\". What about it?
Pablito: Well, it contains \" with # in front of it. Does the backslash comes from the quote in the string?
Dana: No, it’s just the syntax for characters – #\ followed by the character.
Pablito: So the presence of the backslash is just a coincidence?
Dana: Yes, it is just a coincidence.
Pablito: Thanks.
Given two strings s1 and s2, can you think of a relation between
Implement a Scheme procedure that tests this relation.
Scheme features a generic equality predicate, equal?, as well as type-specific equality predicates such as = for numbers, boolean=? for Booleans, char=? for characters, and string=? for strings.
Here are some examples of generic equalities:
> (equal? 1 2)
#f
> (equal? 10 10)
#t
> (equal? #t #t)
#t
>
Here are some examples of numeric equalities:
> (= 33 44)
#f
> (= 33 33)
#t
> (= "33" "33")
Exception in =: "33" is not a number
Type (debug) to enter the debugger.
> (= 32/2 48/3)
#t
>
Here are some examples of boolean equalities:
> (boolean=? #t #t)
#t
>
Here are some examples of character equalities:
> (equal? #\x #\y)
#f
> (char=? #\x #\y)
#f
> (char=? #\space #\ )
#t
>
Here are some examples of string equalities:
> (equal? "foo" "bar")
#f
> (equal? "foo" "foo")
#t
> (string=? "foo" "foo")
#t
> (string=? #f 33)
Exception in string=?: #f is not a string
Type (debug) to enter the debugger.
> (equal? #f 33)
#f
>
Remark: Considering the naming convention for type-specific equality predicates, the name number=? would have been logical, but for simplicity, = was adopted.
Halcyon: I knew it, I knew it.
Bong-sun: What did you know, Halcyon?
Halcyon: The space character and #\space are the same, look:
> (char=? #\ #\space)
#t
>
Bong-sun: Indeed they are, Halcyon, indeed they are.
Consider the two following definitions (expt denotes the exponentiation procedure):
(define square-of-a-sum
(lambda (x y)
(expt (+ x y) 2)))
(define something-else
(lambda (x y)
(+ (expt x 2) (* 2 x y) (expt y 2))))
Each of square-of-a-sum and something-else denotes dyadic procedures. Assuming they are to be applied to integers only, are these two procedures equivalent? In other words, do they compute the same function? Or again: When applied to the same two integers, do they always return the same result?
N.B. The following predicate should prove handy:
(define compare
(lambda (x y)
(= (square-of-a-sum x y)
(something-else x y))))
Reminder: A unary function f has a fixed point whenever there exists an x such that f(x) = x.
The following predicate checks whether its second argument is a fixed point for its second argument, i.e., whether its first argument behaves like the identity procedure for its second argument:
(define identity-at-a-given-point?
(lambda (p x)
(equal? (p x) x)))
For example, the identity procedure passes this test:
> (identity-at-a-given-point? (lambda (x) x) 33)
#t
> (identity-at-a-given-point? (lambda (x) x) #f)
#t
>
And conversely, a constant procedure does not pass this test, except for its constant:
> (identity-at-a-given-point? (lambda (x) 42) 42)
#t
> (identity-at-a-given-point? (lambda (x) 42) 33)
#f
> (identity-at-a-given-point? (lambda (x) 42) #f)
#f
>
Which of the following procedures have fixed points?
Justify your answers.
Reminder: A unary function f is an involution whenever it is its own inverse, i.e., whenever for any x, f(f(x)) = x.
The following predicate checks whether its first argument is involutary for its second argument:
(define involutory-at-a-given-point?
(lambda (p x)
(equal? (p (p x)) x)))
For example, the identity procedure passes this test:
> (involutory-at-a-given-point? (lambda (x) x) 33)
#t
> (involutory-at-a-given-point? (lambda (x) x) #f)
#t
>
Which of the following procedures implements an involution, do you think?
Justify your answers.
Reminder: A unary function f is idempotent whenever for any x, f(f(x)) = f(x).
The following predicate checks whether its first argument is idempotent for its second argument:
(define idempotent-at-a-given-point?
(lambda (p x)
(equal? (p (p x)) (p x))))
For example, the identity procedure passes this test:
> (idempotent-at-a-given-point? (lambda (x) x) 33)
#t
> (idempotent-at-a-given-point? (lambda (x) x) #f)
#t
>
Which of the following procedures is idempotent, do you think?
Justify your answer.
Which Scheme procedure implements a function that is both involutory and indempotent?
Justify your answer.
Bong-sun: Aha!
Dana: Yes, Bong-sun.
Bong-sun (triumphantly): We now know how to raise errors.
Dana: Indeed we do. For example, we can evaluate a variable that has not been defined yet.
Bong-sun: Or we can apply a procedure to a wrong number of arguments.
Alfrothul: So we can. What of it?
Bong-sun: Well, we can now illustrate the error case when evaluating, say, an if-expression, look. Assuming that undefined-yet is a variable that has not been defined yet, here we go:
> undefined-yet
Exception: variable undefined-yet is not bound
Type (debug) to enter the debugger.
> (if undefined-yet 1 2)
Exception: variable undefined-yet is not bound
Type (debug) to enter the debugger.
>
Bong-sun: Yup. Evaluating this if-expression raises the same error as the one that was raised when evaluating its test.
Pablito: What about writing an expression whose evaluation diverges?
Bong-sun: That would be good, because we could illustrate the divergence case when evaluating, say, an if-expression.
The fourth wall: By some extraordinary coincidence, divergence is the topic of the next postlude. Please all proceed in an orderly fashion.
Bong-sun: Harrumph.
Alfrothul: Harrumph.
Dana: Right. How do we write an expression whose evaluation diverges?
Anton: Good question. We have no while loops.
Halcyon: And no recursion. Maybe we should just be patient and go home?
Dana: Well, in Week 02, we saw that self-reference induces infinite regressions.
Alfrothul: Right. Take the liar paradox, for example. He says “I am lying.”
Anton: So he is not lying.
Alfrothul: So he is lying.
Anton: So he is not lying.
Bong-sun: OK, OK, you can stop, we get the point – you reach a contradiction.
Dana: The simplest self-reference here is self-application.
Pablito: You mean like (x x), for some x?
Bong-sun: How about we lambda-abstract x:
(lambda (x) (x x))
Anton: OK, that’s simple. Now what do we do with this procedure?
Halcyon: The only thing we can do is to apply it.
Pablito: But to what?
Alfrothul (struck by inspiration): How about we apply it to itself, look:
((lambda (x) (x x)) (lambda (x) (x x)))
Bong-sun: Let me see. It’s an application, so we need to evaluate each of the sub-expressions – which are the same.
Dana: Evaluating (lambda (x) (x x)) yields a procedure that expects a procedure and then applies it to itself.
Alfrothul (animatedly): Applying this procedure to itself reduces to applying this procedure to itself.
Anton: Which reduces to applying this procedure to itself.
Alfrothul: Which reduces to applying this procedure to itself.
Anton: Which reduces to applying this procedure to itself.
Alfrothul: Which reduces to applying this procedure to itself.
Bong-sun: OK, OK, you can stop, we get the point.
Alfrothul: The point is that this evaluation does not terminate.
Bong-sun: OK, let’s try:
> ((lambda (x) (x x)) (lambda (x) (x x)))
Anton: Well, nothing happens.
Alfrothul: We can see nothing happening because evaluation is diverging.
Pablito: So what do we do now? Can we stop it from diverging?
Mimer: You need to go to the meta-level and send a signal to the Scheme process. Type C-c C-c.
Bong-sun: Trying:
C-c C-c
break>
Anton: Now what?
Mimer: We are now in the Chez Scheme debugger. You are welcome to type a question mark.
Bong-sun: Typing:
break> ?
Type e to exit interrupt handler and continue
r or q to reset scheme
a to abort scheme
n to enter new cafe
i to inspect current continuation
s to display statistics
break>
Mimer: At this point you can look at the Chez Scheme user’s manual but that’s going to be confusing because we don’t now about interrupt handlers, for example. So why don’t you just type r.
Bong-sun: Typing:
break> r
>
Mimer: You are back at the toplevel now.
Bong-sun: Checking:
> 1
1
>
Bong-sun: OK.
Anton: Wow.
Dana: Well, in mathematics, self-reference yields an infinite regression that we stop by characterizing it as a contradiction, and in computer science, self-reference yields an infinite computation that we stop by interrupting the process that implements the computation.
Bong-sun: Right. And we can now illustrate the divergence case when evaluating, say, an if-expression, look:
> (if ((lambda (x) (x x)) (lambda (x) (x x))) 1 2)
C-c C-c
break> r
>
Anton (respectfully): Happy now?
Bong-sun (ironically): Satisfied for now.
Alfrothul: Guys?
Halcyon (still adjusting his moustache): Yes?
Alfrothul: How about we trace the infinite computation?
Anton: Trace the infinite computation now?
Alfrothul: Yes, like this:
((trace-lambda start (x) (x x)) (trace-lambda chug (x) (x x)))
Bong-sun: Well, we will see one instance of start and then repeated occurrences of chug.
Halcyon: That sounds like a great idea. Let’s do it!
Mimer: You probably will need to type C-c C-c several times.
Pablito (candidly): And the exit procedure, what does it do?
Dana: Indeed the name exit denotes a procedure, and when we invoke the procedure, Chez Scheme stops.
Pablito: So to end Chez Scheme, we could write (exit) at the toplevel rather than ^D?
Dana: Yes.
Pablito: And we could apply the exit procedure anywhere in our programs, could we not?
Dana: Er... Yes.
Pablito: Then isn’t that a case we should consider when describing, e.g., how if-expressions are evaluated?
Dana: What do you mean, Pablito?
Pablito: Well, to evaluate an if-expression, we need to evaluate its test. And then we proceed by cases: either evaluating its test does not terminate, or it raises an error, or it yields a value.
Dana: Yes.
Pablito: Shouldn’t we also consider the case where the exit procedure was applied in the course of evaluating the test?
Dana: Well, if the exit procedure was applied, then the Scheme world has ceased to exist, so it doesn’t matter what happens in this world.
Pablito: OK... But this Scheme world, could we not just suspend it – you know, like in a computer game – and then resume it later?
Dana: I think this issue is out of scope, since we are studying the Scheme world.
Alfrothul: Right. But if this Scheme world was simulated in another Scheme world, this issue would not be out of scope, would it?
Mimer: You guys are going to enjoy contin^H^H^H^H^H – I mean please continue to be patient.
Loki: It’s hard not to make forward references, isn’t it, Mimer?
Mimer: You would know, Loki. You would know.
Simplified the description of how and-expressions and or-expressions are evaluated. [05 Sep 2025]
Added Interlude #0, adjusted the statement of Exercise 01, and expanded the postlude about divergence [31 Aug 2025]
Completed [30 Aug 2025]
Created [29 Aug 2025]