Study Guide: Scheme

Instructions

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.

Assignments

Important: For solutions to these assignments once they have been released, see the main website

Handouts

Lectures

Readings

Guides

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

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 condition.

Problem-Solving

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 if can be nested and composed in useful ways. (Remember that in Python, we can't drop an if block 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.

Practice Problems

Easy

Q1: All Satisfies

Implement a function (all-satisfies lst pred) that returns True if all of the elements in lst satisfy pred.

Run in 61A Code

Medium

Q2: Matching

Implement num-adjacent-matches, which takes as input a list of numbers 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.