CPSC 110: Systematic Program Design

Overview

CPSC 110 teaches Systematic Program Design (SPD) — a methodology for writing correct, well-structured programs using Racket (a dialect of Lisp/Scheme). The core insight: good programs are designed, not just written.

The Design Recipe

Every function follows the same 6-step process:

1. Signature — What types go in, what type comes out?
2. Purpose — One sentence: what does this function do?
3. Stub — A placeholder that matches the signature
4. Examples / Tests — Concrete input/output pairs (written before the body)
5. Template — Driven by the data definition of the input type
6. Body — Fill in the template using examples as a guide

This might seem slow, but it forces you to think about what a function does before how it does it.

Data Definitions

Data definitions describe the structure of information. Templates are derived from them automatically.

;; A TrafficLight is one of:
;; - "red"
;; - "yellow"
;; - "green"
;; Template:
(define (fn-for-traffic-light tl)
  (cond [(string=? tl "red") ...]
        [(string=? tl "yellow") ...]
        [(string=? tl "green") ...]))

Recursion

Recursive data definitions naturally lead to recursive functions:

;; A ListOfNumber is one of:
;; - empty
;; - (cons Number ListOfNumber)

(define (sum lon)
  (cond [(empty? lon) 0]
        [else (+ (first lon) (sum (rest lon)))]))

The template tells you where to put the recursive call — no need to think from scratch each time.

Higher-Order Functions

Functions that take other functions as arguments:

;; map: applies a function to every element
(map (lambda (x) (* x x)) (list 1 2 3 4))
;; => (list 1 4 9 16)

;; filter: keeps elements that satisfy a predicate
(filter odd? (list 1 2 3 4 5))
;; => (list 1 3 5)

;; foldr: reduces a list to a single value
(foldr + 0 (list 1 2 3))
;; => 6

Mutual Recursion

When two data types reference each other, the functions that process them call each other:

;; A FileSystem is one of:
;; - (make-file String)
;; - (make-dir String (listof FileSystem))

(define (process-fs fs)
  (cond [(file? fs) (process-file fs)]
        [(dir? fs) (process-dir fs)]))

(define (process-dir d)
  (... (dir-name d) (process-lofs (dir-contents d))))

(define (process-lofs lofs)
  (cond [(empty? lofs) ...]
        [else (... (process-fs (first lofs))
                   (process-lofs (rest lofs)))]))

Key Takeaways

• Design before you code. Tests before the body. Signature before tests.
• Data drives structure. The shape of your data determines the shape of your functions.
• Templates are not optional. They prevent you from staring at a blank screen.
• HOFs reduce repetition. map, filter, foldr handle 80% of list processing.

The design recipe generalizes beyond Racket — it's a mindset for tackling any programming problem systematically.