Fundamentals of CS 1

Notes/tools for Northeastern's intro to CS class.

Background

Northeastern's computer science faculty decided at some point to rewrite their introductory CS classes, to have a focus on designing programs over just writing code. The course is taught in Racket, or more specifically, the "Teaching Languages", which are subsets of Racket that limit certain language features and promote test-driven development.

Notes

Design Recipe

• Functions
  1. Write a signature
  2. Write a purpose statement
  3. Write at least 2 tests*
  4. Write the code

Tests have to cover every edge case -- common ones include the empty list, empty string, negative numbers or zero, etc. If the data type is an enumeration or union, the tests should cover each enumeration value or subtype.

It is not possible to test functions that call big-bang with the tools we have, because the return value is affected by user input. The functions which handle events from big-bang should be tested like any other function. Functions which call random should be checked with check-random, and functions which may return inexact numbers have check-within tests.

• Data 0. Complete this step above the function if you use a type that isn't well-known (not needed for String, Int, PositiveReal, Boolean, etc.)
  1. Write a data definition stating the type name and what data it can hold
  2. Write an interpretation statement for the type
  3. Write some constants that have the type (these are used later for testing)
  4. Write a template that branches, deconstructs, and/or recurses through this type of data, calling templates when encountering other designed types

Example:

; A Side is one of:
; - "left"
; - "center"
; - "right"
; and represents the horizontal position of one thing relative to another

(define SIDE-LEFT "left")
(define SIDE-CENTER "center")
(define SIDE-RIGHT "right")

(define (side-temp side)
  (...
    (cond
      [(string=? side SIDE-LEFT) ...]
      [(string=? side SIDE-CENTER) ...]
      [(string=? side SIDE-RIGHT) ...])))

(define-struct weight [side mass])
; A Weight is a (make-weight Side NonNegativeReal)
; and represents a weight on a see-saw
; - the side of the see-saw it is on
; - its mass in kilograms

(define WEIGHT-0 (make-weight SIDE-RIGHT 0.0))
(define WEIGHT-1 (make-weight SIDE-LEFT 1.0))
(define WEIGHT-2 (make-weight SIDE-CENTER 2.0))
(define WEIGHT-3 (make-weight SIDE-RIGHT 3.0))

(define (weight-temp w)
  (... (side-temp (weight-side w))
   ... (weight-mass w)))

; A SeeSaw is one of:
; - empty
; - (cons Weight SeeSaw)
; and represents either a see-saw with one or more weights

(define SEESAW-0 empty)
(define SEESAW-1 (cons WEIGHT-1 SEESAW-0))
(define SEESAW-2 (cons WEIGHT-2 SEESAW-1))
(define SEESAW-3 (cons WEIGHT-3 SEESAW-2))

(define (seesaw-temp lst)
  (...
    (cond
      [(empty? los) ...]
      [(cons? los)
        (...
          (weight-temp (first lst))
          (seesaw-temp (rest lst)))])))

Following the Design Recipe

If the template calls another template, it indicates that the function using the template needs another function to do work on the other data type. Other indicators are long and nested parts of the function, repeated selectors, and if statements deciding between similar recursive calls.

(define ACCEL-GRAVITY 9.8)
; seesaw-torque : SeeSaw PosNumber -> Number
; Determines the torque in newton-meters on a see-saw with the given length in meters
(check-expect (seesaw-torque SEESAW-0 2) 0)
(check-expect (seesaw-torque SEESAW-1 2) 9.8)
(check-expect (seesaw-torque SEESAW-2 2) 9.8)
(check-expect (seesaw-torque SEESAW-3 2) -19.6)
; bad example
; (define (seesaw-torque lst len)
;   (cond
;     [(empty? los) 0]
;     [(cons? los)
;      (+
;       (*
;         len
;         -1
;         (cond
;           [(string=? (weight-side (first lst)) SIDE-LEFT) -0.5]
;           [(string=? (weight-side (first lst)) SIDE-CENTER) 0]
;           [(string=? (weight-side (first lst)) SIDE-RIGHT) 0.5])
;         ACCEL-GRAVITY
;         (weight-mass (first lst)))
;       (seesaw-torque (rest lst) len))]))

Note: inlining an if returning 0 or 1 can be OK, but it's always preferred to use helper functions.

; same tests
(define (seesaw-torque lst len)
  (cond
    [(empty? los) 0]
    [(cons? los)
     (+
      (weight-torque (first lst) len)
      (seesaw-torque (rest lst) len))]))

; weight-torque : Weight PosNumber -> Number
; Returns the torque that this weight would exert on a see-saw with the given length
; in meters. The fulcrum of the see-saw is at its center, and gravity is 9.8 m/s^2.
; Weights on the left will generate positive, counter-clockwise torque
(check-expect (weight-torque WEIGHT-0) 0)
(check-expect (weight-torque WEIGHT-1) 9.8)
(check-expect (weight-torque WEIGHT-2) 0)
(check-expect (weight-torque WEIGHT-3) -29.4)
(define (weight-torque w len)
  (*
    len
    -1 (dist-to-center (weight-side w))
    ACCEL-GRAVITY
    (weight-mass w)))

; dist-to-center : Side -> Number
; Returns the distance of the given side to the center position.
(check-expect (dist-to-center SIDE-LEFT) -0.5)
(check-expect (dist-to-center SIDE-CENTER) 0)
(check-expect (dist-to-center SIDE-RIGHT) 0.5)
(define (dist-to-center side)
  (cond
    [(string=? side SIDE-LEFT) -0.5]
    [(string=? side SIDE-CENTER) 0]
    [(string=? side SIDE-RIGHT) 0.5]))

List Abstractions

;;; (length (build-list n ??)) === n
; (X) NatNum [NatNum -> X] -> [List-of X]
; constructs a list by applying f to 0, 1, ..., (sub1 n)
; (build-list n f) == (list (f 0) ... (f (- n 1)))
(define (build-list n f) ...)

;;; (length (filter p lx)) <= (length lx)
; (X) [X -> Boolean] [List-of X] -> [List-of X]
; produces a list from those items on lx for which p holds
(define (filter p lx) ...)

;;; elements are identical, but have known ordering in (sort lx)
; (X) [List-of X] [X X -> Boolean] -> [List-of X]
; produces a version of lx that is sorted according to cmp
(define (sort lx cmp) ...)

;;; (length (map f lx)) === (length lx)
; (X Y) [X -> Y] [List-of X] -> [List-of Y]
; constructs a list by applying f to each item on lx
; (map f (list x-1 ... x-n)) == (list (f x-1) ... (f x-n))
(define (map f lx) ...)

;;; For all
; (X) [X -> Boolean] [List-of X] -> Boolean
; determines whether p holds for every item on lx
; (andmap p (list x-1 ... x-n)) == (and (p x-1) ... (p x-n))
(define (andmap p lx) ...)

;;; There exists
; (X) [X -> Boolean] [List-of X] -> Boolean
; determines whether p holds for at least one item on lx
; (ormap p (list x-1 ... x-n)) == (or (p x-1) ... (p x-n))
(define (ormap p lx) ...)

; (X Y) [X Y -> Y] Y [List-of X] -> Y
; applies f from right to left to each item in lx and b
; (foldr f b (list x-1 ... x-n)) == (f x-1 ... (f x-n b))
(define (foldr f b lx) ...)

; (X Y) [X Y -> Y] Y [List-of X] -> Y
; applies f from left to right to each item in lx and b
; (foldl f b (list x-1 ... x-n)) == (f x-n ... (f x-1 b))
(define (foldl f b lx) ...)

; factorial : NonNegInt -> PosInt
; Returns n! by generating the range [1..n] as a list, and
; folding with the function `*`
(check-expect (factorial 0) 1)
(check-expect (factorial 1) 1)
(check-expect (factorial 3) 6)
(check-expect (factorial 6) 720)
(define (factorial n)
  (foldr
    * 1
    (build-list n add1)))

Local, Lambda

A local scope can allow you to define a function that references a function argument without requiring that argument as input. Using lambda or λ (Ctrl+\) also creates a function in the local scope.

; usd-to-euro : [List-of Number] Number -> [List-of Number]
; Converts all the currency values in the given list from USD to EUR,
; using the given number as the EUR/USD rate

(check-expect (usd-to-euro empty 1.1) empty)
(check-expect (usd-to-euro (list 2 4 6) 1.5) (list 3 6 9))

(define (usd-to-euro lon rate)
  (local [; multiply-by-rate : Number -> Number
          ; Multiplies the given number by `rate`, which is passed in to `usd-to-euro`
          (define (multiply-by-rate x)
            (* x rate))]
    (map multiply-by-rate lon)))

; alternatively
(define (usd-to-euro/v2 lon rate)
  (map
    (λ (x) (* x rate))
    lon))

Multiple complex inputs

Determine which type of processing the function will do:

1. Sequential - apply one template and then the other
2. Parallel - determine all situations via "joint" templates
3. Cross - use template for one, with template for other as inner call

(define (list-temp loa)
  (...
   (cond
     [(empty? loa) ...]
     [(cons? loa)
      (...
       (first loa)
       (list-temp (rest loa)))])))

;;; Sequential
; append-lists : [List-of Any] [List-of Any] -> [List-of Any]
; Reimplements `append`. The template for the second list is replaced
; with `l2`.
(check-expect (append-lists empty (list 1 2)) (list 1 2))
(check-expect (append-lists (list 1 2) empty) (list 1 2))
(check-expect (append-lists (list "a") (list 1 2)) (list "a" 1 2))
(define (append-lists l1 l2)
  (cond
    [(empty? l1) l2]
    [(cons? l1)
     (cons
      (first l1)
      (append-lists (rest l1) l2))]))


; A Nat is one of:
; - 0
; - (add1 Nat)
; and represents a natural number
(define (nat-temp n)
  (...
  (cond
    [(zero? n) ...]
    [(positive? n)
     (...
      (nat-temp (sub1 n)))])))

;;; Parallel (example use case was my-list-ref)
(define (list-nat-temp loa n)
  (...
   (cond
     [(and (empty? loa) (zero? n)) ...]
     [(and (empty? loa) (positive? n))
      (...
       n
       (list-nat-temp loa (sub1 n)))]
     [(and (cons? loa) (zero? n))
      (...
       (first loa)
       (list-nat-temp (rest loa) n))]
     [(and (cons? loa) (positive? n))
      (...
       (first loa)
       n
       (list-nat-temp (rest loa) (sub1 n)))])))

;;; Cross
; intersect : (X) [List-of X] [List-of X] [X X -> Boolean] -> [List-of X]
; returns the subset of the two lists that are common given an equality relation,
; in the order that they appear in the first list
(check-expect (intersect (list 1 2 3) (list 4 5 6) =) empty)
(check-expect (intersect (list 1 2 1) (list 4 1 6) =) (list 1 1))
(check-expect (intersect (list "a" "b") (list "c" "a") string=?) (list "a"))
(define (intersect l1 l2 same?)
  (cond
    [(empty? l1) empty]
    [(cons? l1)
     (if (list-contains? l2 (first l1) same?)
         (cons
          (first l1)
          (intersect (rest l1) l2 same?))
         (intersect (rest l1) l2 same?))]))

; list-contains? : (X) [List-of X] X [X X -> Boolean] -> Boolean
; returns true if the given list contains the given element, according to the
; equality relation
(check-expect (list-contains? (list 1 2) 1 =) true)
(check-expect (list-contains? (list 4 5 6) 1 =) false)
(define (list-contains? lox el same?)
  (ormap
   (λ (current-el) (same? el current-el))
   lox))

Linter

A tool which checks that after every signature, there is a purpose statement, ≥2 tests which call the function named in the signature, and a function definition with the same name. It also checks that there are no function definitions without a signature, in top-level or local scopes. View the source

If your code generates many warnings under one function design, make sure your signatures have spaces surrounding the arrow. Number -> Number denotes 1 input and 1 output, but Number-> Number is read as two types called Number-> and Number.