This is a study guide with links to past lectures, assignments, and handouts, as well as additional practice problems to assist you in learning the concepts.
Important: For solutions to these assignments once they have been released, see the main website
Computer science is not just about writing programs, but also understanding how they behave. We learned in the first week of class about the Python programming language and its expressive syntax. We saw how we could pose questions to the Python interpreter and how we could define functions that teach Python how to solve more and more complex problems.
Underlying all of the evaluation rules, we also learned about several different programming paradigms in Python by composing functions together, creating compound values and data abstractions with lists and dictionaries, and modeling those data abstractions using object-oriented programming.
But these aren't the only programming paradigms that exist and Python isn't the only language that we use to solve problems. We learn about Scheme to help answer both of these questions: what are the ways of thinking that transfer between languages, and how a computer understands programs.
Scheme is like Python in some ways and unlike it in others. Like Python, Scheme is an interpreted language so we can always ask questions in the interpreter.
scm> 1 1 scm> #t #t scm> 'symbol symbol
Like Python, Scheme has a similar set of familiar data types like numbers, booleans, strings, and an unfamiliar type, symbols. There are also call expressions, which evaluate using the same evaluation procedure as in Python.
scm> (+ 1 2) 3 scm> (not #t) #f
An expression enclosed in parentheses is called a combination, but not all combinations are call expressions!
scm> (if (= 1 2) (/ 1 0) #f) #f
Some combinations, like the
if special form, look like call expressions, but
have very unique logic. If
if were a call expression, we would the operator
and each operand, which isn't what happens here. Instead, the
if special form
follows its own set of evaluation rules by first evaluating the condition and
then chooses the corresponding consequent based on the truth value of the
Code-writing in Scheme follows the same overarching problem-solving strategy we've been honing all semester long, just with additional rules. Scheme encourages us to write programs in a functional style by composing together several small programs, each solving a single problem, but which combine to solve a larger problem. Think of this as yet another form of abstraction, except now at the scale of how we organize programs as a whole!
Practically-speaking, there are a couple of restrictions we need to be cognizant of when writing Scheme programs as they'll require us to change the way we solve problems.
One part will require us to grapple with how we come up with algorithms, or step-by-step solutions.
- Scheme data types are (mostly) immutable. The values of compound data types like pairs can't be easily changed.
- Scheme does not support iteration. We use recursion and helper procedures instead.
The other will affect how we convert the algorithm or idea into code.
- Scheme prefers a composition of function calls. Scheme syntax is all
expressions, which means that even special forms like
ifcan be nested and composed in useful ways. (Remember that in Python, we can't drop an
ifblock statement in the middle of a function call!)
scm> (define x 1) x scm> (+ 1 (if (= x 1) 1 2)) 2
We'll usually define several small procedures. The procedures we define tend to have a well-defined domain and range, and their behavior can be explained in simple words.
We might, for example, want to remove all the duplicate values in a list. Based on the algorithm restrictions, we know we can't mutate the original list, so our only other option is to return a new list containing the unique values. We can use recursion to traverse down the list, checking each item to see whether or not it's a unique value. From here, the idea can vary in two directions depending on whether we want to filter the remaining values, or check backwards and add to our growing list of unique values if it's not already there.
Q1: All Satisfies
Implement a function
(all-satisfies lst pred) that returns
True if all of
the elements in
(define (all-satisfies lst pred) ; BEGIN SOLUTION (if (null? lst) True (and (pred (car lst)) (all-satisfies (cdr lst) pred))) ; END SOLUTION ) ;;; Tests (expect (all-satisfies nil even?) #t) (expect (all-satisfies '(2 4 6) even?) #t) (expect (all-satisfies '(2 3 6) even?) #f) (expect (all-satisfies '((1 2) (3 4 5) (6)) pair?) #t)
num-adjacent-matches, which takes as input a list of
s and returns the number of adjacent elements that are equal.
(define (num-adjacent-matches s)'YOUR-CODE-HERE(if (or (null? s) (null? (cdr s))) 0 (+ (num-adjacent-matches (cdr s)) (if (= (car s)(car (cdr s))) 1 0)))) ;;; Tests ; no pairs (expect (num-adjacent-matches '(1 2 3 4)) 0) ; one pair of 1's (expect (num-adjacent-matches '(1 1 2 3)) 1) ; one pair of 1's, one pair of 2's (expect (num-adjacent-matches '(1 1 2 2)) 2) ; three pairs of 1's (expect (num-adjacent-matches '(1 1 1 1)) 3) (expect (num-adjacent-matches '(6 6 6 1 6 1)) 2) (expect (num-adjacent-matches '(6)) 0) (expect (num-adjacent-matches '(6 1)) 0) (expect (num-adjacent-matches '(6 1 6 1 6 1)) 0) (expect (num-adjacent-matches '(6 6)) 1) (expect (num-adjacent-matches '(6 6 6 1 6 1)) 2) (expect (num-adjacent-matches '(0 1 6 6 6 1)) 2) (expect (num-adjacent-matches '(4 4 3 3 2 2 1 1)) 4)
Our base cases are when our input list
s is too short to have any adjacent
matches. We call
num-adjacent-matches recursively on
(cdr s) to count the
adjacent matches in the rest of the list
s, then add 0 or 1 depending on
whether the first and second elements of
s are equal.