Study Guide: Scheme

Instructions

This is the companion guide to Quiz 8 with links to past lectures, assignments, and handouts, as well as isomorphic quiz problems and additional practice problems to assist you in learning the concepts.

Assignments

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.

Pairs

Scheme has a simple data type for representing compound values, the pair. Any value can go in the first or second field of a pair and we can compose pairs together to create nested data types (like trees!) and lists.

scm> (cons 1 2)
(1 . 2)

What's going on here? cons creates a pair where 1 is the first and 2 is the second value of the pair. Scheme then needs to figure out how to display this pair back to the interpreter. Just like how the Python interpreter calls the __repr__ method to determine what to show to the user, Scheme follows a similar procedure to determine how to represent the pair structure.

In general, a pair is displayed in the following format.

scm> (cons 'first 'second)
(first . second)

The dot separates the two values in the pair. Nested pairs are also nested in their representation.

scm> (cons (cons 'first 'second) 'third)
((first . second) . third)

...except if the nesting happens in the second field, because the resulting structure is considered a list so we instead use a more streamlined notation.

scm> (cons 'first (cons 'second 'third))
(first second . third)

We can think of this as a simplification of the following representation.

(first . (second . third)) -> (first second . third)

We can also play around with how we compose pairs to get yet other examples.

scm> (cons (cons 'first 'second) (cons 'third 'fourth))
((first . second) third . fourth)

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.

(define (all-satisfies lst pred)
'YOUR-CODE-HERE
(if (null? lst) True (and (pred (car lst)) (all-satisfies (cdr lst) pred)))
) ;;; Tests (all-satisfies nil even?) ; expect True (all-satisfies '(2 4 6) even?) ; expect True (all-satisfies '(2 3 6) even?) ; expect False (all-satisfies '((1 2) (3 4 5) (6)) pair?) ; expect True

Medium

Q2: Interleave

Implement the function interleave, which takes a two lists as arguments. interleave will return a new list that interleaves the elements of the two lists, with list1 starting first. Refer to the tests for sample input/output.

(define (interleave list1 ist2)
  ; BEGIN SOLUTION
  (if (or (null? list1) (null? list2))
      (append list1 list2)
      (cons (car list1)
            (cons (car list2)
                  (interleave (cdr list1) (cdr list2))))))
  ; END SOLUTION

(interleave (list 1 3 5) (list 2 4 6))
; expect (1 2 3 4 5 6)

(interleave (list 1 3 5) nil)
; expect (1 3 5)

(interleave (list 1 3 5) (list 2 4))
; expect (1 2 3 4 5)

Q3: 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) (cadr s)) 1 0)))
) ;;; Tests ; no pairs (num-adjacent-matches '(1 2 3 4)) ; expect 0 ; one pair of 1's (num-adjacent-matches '(1 1 2 3)) ; expect 1 ; one pair of 1's, one pair of 2's (num-adjacent-matches '(1 1 2 2)) ; expect 2 ; three pairs of 1's (num-adjacent-matches '(1 1 1 1)) ; expect 3 (num-adjacent-matches '(6 6 6 1 6 1)) ; expect 2
(num-adjacent-matches '(6)) ; expect 0 (num-adjacent-matches '(6 1)) ; expect 0 (num-adjacent-matches '(6 1 6 1 6 1)) ; expect 0 (num-adjacent-matches '(6 6)) ; expect 1 (num-adjacent-matches '(6 6 6 1 6 1)) ; expect 2 (num-adjacent-matches '(0 1 6 6 6 1)) ; expect 2 (num-adjacent-matches '(4 4 3 3 2 2 1 1)) ; expect 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.

Q4: Split

Implement split-at, which takes a list lst and a positive number n as input and returns a pair new such that (car new) is the first n elements of lst and (cdr new) is the remaining elements of lst. If n is greater than the length of lst, (car new) should be lst and (cdr new) should be nil.

(define (split-at lst n)
'YOUR-CODE-HERE
(cond ((= n 0) (cons nil lst)) ((null? lst) (cons lst nil)) (else (let ((rec (split-at (cdr lst) (- n 1)))) (cons (cons (car lst) (car rec)) (cdr rec)))))
)

Use Ok to test your code:

python3 ok -q split-at