xkcd.
com/297/
Module 01: Introduction
Introduction to Computer Science 1
University of Waterloo
Fall 2025
1
Computer science is not programming
"Computer science is no more about
computers than astronomy is about
telescopes."
Edsger Dijkstra (?)
…But we will use programming as a concrete medium in which to explore the
nature of computation.
2
Themes
• Communication: Code must be understandable by the computer, by you,
and by other people
• Design: The meeting place of problem solving insight and practical,
methodical skills.
• Abstraction: Identify recurring patterns in the computations we do, and
invent tools to capture those patterns.
• Syntax and semantics: Rigorous rules that tell us which programs are legal
and what they do when you run them.
3
Racket
• A pure functional programming
language
• Stripped-down syntax
• Unfamiliar to most students taking the
course
• Really good for teaching and learning
4
The Language of Mathematics
5
6
The Language of Mathematics
We all learned to write in a non-native language called Mathematics, whether we
thought about it that way or not.
• Values: 0, −37, 3.14159, 7/8, (6,4)…
5 2
• Expressions: 5 + 3 , log2 (2 ⋅ 8), (90 − 32) , …
9 100 − 5
2
• De nitions: a = 13, π = 3.14159…, f(x) = x − x − 1…
• Evaluation rules: f(a − 1) = ?
7
fi
The Language of Mathematics
We all learned to write in a non-native language called Mathematics, whether we
thought about it that way or not.
• Values: 0, −37, 3.14159, 7/8, (6,4)…
5 2
• Expressions: 5 + 3 , log2 (2 ⋅ 8), (90 − 32) , …
9 100 − 5
2
• De nitions: a = 13, π = 3.14159…, f(x) = x − x − 1…
• Evaluation rules: f(a − 1) = 131
8
fi
More Terminology
a = 13
2
f(x) = x − x − 1
f(a − 1)
9
More Terminology
Identi er
a = 13
2
f(x) = x − x − 1
f(a − 1)
10
fi
More Terminology
Parameter
a = 13 Body
2
f(x) = x − x − 1
f(a − 1) Argument
11
Racket Values
Racket lets us describe a large universe of values. For now, we'll work with
di erent kinds of numbers:
• Natural numbers: 0, 1, 13, 587, 76293845769238745692837645982376549,
…
• Integers: -1, -874, -876598273645982376598372651111110, …
• Rational numbers: -3/2, 355/113, 1273654.823746592957842, …
• Inexact numbers: #i1.4142135623730951, …
Every Racket value is in its simplest form.
12
ff
Built-In Racket Functions
• In Mathematics, | ⋅ | denotes the absolute value function: | 4 | = 4,
| − 8 | = 8, etc.
• Racket has a built-in function called abs; but how do we apply it?
13
Function Application Syntax
Every Racket function application follows the same pattern:
• An open parenthesis (
• An identi er (the name of the function)
• Some whitespace (spaces, tabs, newlines)
• An argument (an expression producing a value passed to the function)
• Any additional arguments, separated by more whitespace
• A closing parenthesis )
14
fi
Racket Arithmetic
• The standard arithmetic operators (+, -, *, /) are built in to Racket
• But they're just functions like any other!
• Additional notes:
• The - function works with a single argument ("unary negation")
• The + and * functions accept two or more arguments
• (The - and / functions do also, but these can be more confusing)
15
• In Mathematics, we use operator precedence (PEMDAS, BODMAS, etc.) and
parentheses to resolve ambiguity
5 ⋅ 6 + 7 ≠ 5 ⋅ (6 + 7)
5 ⋅ 6 + 7 = (5 ⋅ 6) + 7
• Racket's syntax is unambiguous by design. There are no precedence rules,
and extra parentheses are never needed (in fact, they're illegal!)
5⋅6+7 (+ (* 5 6) 7)
16
Useful Math Functions
• add1, sub1
• quotient, remainder
• abs
• sqr, sqrt
• expt
See the Racket documentation for more!
17
Errors
If the following lines are entered into DrRacket's Interactions Window, what
happens?
• (* (5) 3)
• (8 * 7)
• (* + 3 5 2)
• (+ (* 3 2)
• (/ 25 (- 6 6))
18
Constants
• Math contains a number of agreed-upon constants: π, e, etc.
• These are useful in programming, and therefore built in to Racket: pi, e.
• Named constants: identi ers that are permanently bound to values
• Of course, in math we can invent new constants as needed:
−11
G = 6.6743 × 10
• Can we do something similar in Racket?
19
fi
Constant Definitions
• We use the de ne special form to create new constants in Racket:
(de ne cs115-grade 100)
(de ne current-in ation-rate 7.6)
(de ne avogadro 6.02214e23)
• Once de ned, these behave like any other named constants.
20
fi
fi
fi
fi
fi
fl
Constant Definition Grammar
Every constant de nition has this general form:
(define id exp)
21
fi
Constant Definition Grammar
Every constant de nition follows this syntax:
(define id exp)
Write this exactly
as shown
22
fi
Constant Definition Grammar
Every constant de nition follows this syntax:
Replace this with a
Racket identi er
(define id exp)
Replace this with a
Racket expression
23
fi
fi
Benefits of Constants
• A constant can have a shorter and/or more memorable name that its
associated value
• Code with named constants is often easier to read, leading to better
communication
• A named constant captures a potentially complicated expression or number
in a single place in a program, making it easy to x or update later.
24
fi
Function Definitions
• In math, we can invent new functions whenever we need them:
2
f(x) = x − x − 1
• What's the equivalent in Racket?
25
Function Definitions
2
f(x) = x − x − 1
(de ne (f x) (- (- (sqr x) x) 1))
26
fi
Function Definitions
2
f(x) = x − x − 1
"Here comes a de nition"
(de ne (f x) (- (- (sqr x) x) 1))
27
fi
fi
Function Definitions
2
f(x) = x − x − 1
Function name Parameter name
(de ne (f x) (- (- (sqr x) x) 1))
28
fi
Function Definitions
2
f(x) = x − x − 1
(de ne (f x) (- (- (sqr x) x) 1))
29
fi
Function Definitions
2
f(x) = x − x − 1
(de ne (f x) (- (- (sqr x) x) 1))
30
fi
Function Definitions
2
f(x) = x − x − 1
Function body
(de ne (f x) (- (- (sqr x) x) 1))
31
fi
Example: Multiple Parameters
2 2
c= a + b − 2ab cos γ
De ne a function sas that consumes a, b, and γ, and produces the value of c .
32
fi
Function Definition Grammar
Every function de nition has this general form:
(define (id1 id2 … idk) exp)
33
fi
Function Definition Grammar
Every function de nition has this general form:
Body expression
(define (id1 id2 … idk) exp)
Function name One or more
parameter names
34
fi
Scope
• Every identi er has
• A binding occurrence: the location in the program where that identi er
comes into being
• Zero or more bound occurrences: locations that refer back to a given
binding occurrence
• The scope of an identi er is the region of a program where the identi er's
binding occurrence is in e ect
35
fi
fi
ff
fi
fi
Kinds of Scopes
• As far as we know, scopes come in
two varieties:
• Global scope: constants and
functions introduced using de ne
(including built-in names)
36
fi
Kinds of Scopes
• As far as we know, scopes come in
two varieties:
• Global scope: constants and
functions introduced using de ne
(including built-in names)
37
fi
Kinds of Scopes
• As far as we know, scopes come in
two varieties:
• Global scope: constants and
functions introduced using de ne
(including built-in names)
38
fi
Kinds of Scopes
• As far as we know, scopes come in (define (geometric r n)
two varieties:
(/ (sub1 (expt r n))
• Global scope: constants and (sub1 r)))
functions introduced using de ne
(including built-in names)
• Function scope: The parameter
names and body of a function
de nition
39
fi
fi
Kinds of Scopes
• As far as we know, scopes come in (define (geometric r n)
two varieties:
(/ (sub1 (expt r n))
• Global scope: constants and (sub1 r)))
functions introduced using de ne
(including built-in names)
• Function scope: The parameter
names and body of a function
de nition
40
fi
fi
Scope Commandments
1. No identi er may be bound more 2. Function scope may temporarily
than once in a given scope. override global scope
(de ne a 1) (de ne a 1)
(de ne a 3) (de ne (test a)
(* a 4))
Use the "Check Syntax" tool in DrRacket to explore scopes!
41
fi
fi
fi
fi
fi
Scope Trials
Jury members, are these programs valid or invalid?
1. (de ne (test1 x y) (* x 4)) 5. (de ne (func x x) (+ x (sqr x)))
(de ne (test2 x y) (* y 3))
6. (de ne a (- b 5))
2. (de ne b 17)
(de ne name 12)
(de ne (name y) (add1 (sqr y)))
7. (de ne (g a) (+ a p))
3.
(de ne p 13)
(de ne (s t) (+ t 3))
(de ne (t s) (+ s 4))
8.
4. (de ne (z z) (* 5 z 5))
42
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
Semantics of Mathematics
a = 13
2
f(x) = x − x − 1
f(a − 1) = ?
What steps do we take when evaluating a bit of mathematics?
43
Semantics of Racket Programs
• A Racket program is a sequence of de nitions and expressions.
• The meaning of a program is the sequence of values produced by evaluating
its de nitions and expressions.
• A semantic model is a systematic method for determining the meaning of
any legal program.
• We'd like to give a semantic model that's more abstract and more reliable
than "run the program".
44
fi
fi
Semantics via Substitution
• Substitution rule: replace a carefully chosen expression in a program with
something slightly simpler
• After a substitution, the whole program is one step closer to being as simple
as possible
• Our semantic model consists of applying substitution rules in a prescribed
order until we can't any more
45
Simplifying Definitions
• Function de nition: don't do anything!
• Constant de nition: simplify the de ning expression until it's reduced to a
value
(de ne const (* (+ (sqr 5) (sqr 7)) -13))
…
…
…
(de ne const -962)
46
fi
fi
fi
fi
fi
Simplifying Expressions
So far, we've encountered a few di erent types of expressions:
• Literal values
• Identi ers (names of constants)
• Function applications (of built-in or user-de ned functions)
47
fi
ff
fi
Simplifying Literal Values
A literal value is already as simple as possible: no simpli cation needed!
48
fi
Simplifying Constant Names
Use a substitution rule we'll call small-sub: replace the constant name by the
value associated with that constant.
(de ne jenny 8675309) (de ne jenny 8675309)
jenny 8675309
49
fi
fi
Simplifying Function Applications
The grammar of a function application is (id exp1 … expk)
Before we can simplify the application as a whole, we must rst simplify all of
the exps, from left to right
• Find the rst expi that isn't a value, if one exists
• Apply one substitution step to it
When we can't simplify arguments any longer, we'll have an expression of the
form (id val1 … valk)
What we do next depends on the kind of function we're applying…
50
fi
fi
Simplifying Built-In Functions
How do we simplify an expression like this one?
(+ 5 7 8)
The + function is built in, and we don't know how it works. The best we can do
with a built-in function is to write down the answer in one step:
20
We call this the as-if-by-magic rule.
51
Simplifying User-Defined Functions
With a user-de ned function, we have a lot more information: the function body
(de ne (f x) (- (- (sqr x) x) 1))
(f 13)
We replace the application by the body of the function, in which every
occurrence of a parameter name is replaced by its corresponding argument
value.
52
fi
fi
Simplifying User-Defined Functions
With a user-de ned function, we have a lot more information: the function body
(de ne (f x) (- (- (sqr x) x) 1))
(f 13)
We replace the application by the body of the function,
f in which every
occurrence of a parameter
x name is replaced by its 13c.
53
fi
fi
Simplifying User-Defined Functions
With a user-de ned function, we have a lot more information: the function body
(de ne (f x) (- (- (sqr x) x) 1))
(f 13)
We replace the application by the body of the function,
f in which every
occurrence of a parameter
x name is replaced by its 13c.
(- (- (sqr 13) 13) 1)
This is the big-sub rule.
54
fi
fi
Multiple Parameters
If a user-de ned function consumes multiple parameters, big-sub replaces them
all at once.
(de ne (f a b c) (* (+ a b) c))
(f 1 2 3)
(* (+ 1 2) 3)
55
fi
fi
Tracing
• We trace a program by simplifying it repeatedly until we obtain a nal value or
encounter an error.
• Often we assume that some initial de nitions have been fully evaluated
already. We don't re-write those de nitions in every step.
56
fi
fi
fi
Tracing Example
Assume that the following de nitions have been fully evaluated:
(de ne a 13)
(de ne (f x) (- (- (sqr x) x) 1))
Complete each step of the trace of the following expression:
(f (- a 1))
57
fi
fi
fi
Another Example
Assume that the following de nitions have been fully evaluated:
(de ne a (* 3 4))
(de ne b (+ a 11))
(de ne (f x y) (+ x a y b))
Complete each step of the trace of the following expression:
(f (+ a b) 1)
58
fi
fi
fi
fi
Tracing Errors
If a built-in function can't complete, or no valid substitution rule is available, the
trace stops with an error.
(+ (/ 5 (- 3 3)) (* 8 9) 7)
(de ne a 7)
(+ a (quux a))
59
fi