CS 135

1 | Syllabus

Course Themes

• Design (creation)
• Abstraction (commonalities)
• Refinement (improvement)
• Syntax (expression)
• Communication

Using computers to solve data-related problems

2 | Functions

2.1 | Programming Language Design

What is Computation?

• Computer Program = set of instructions to complete a particular task
• Most tasks are mathematical

Ex: How many natural numbers divide 12 evenly?

cnt=0
for i in range (n):
	if n%i==0:
		cnt++

Imperative vs Functional Imperative: based on frequent changes to data:

• Examples: machine language, Java, C++, Turing, Visual Basic, Python
• C++, Java, Python are multi-paradigm languages now

Functional: Based on the computation of new values rather than the transformation of old ones

• Examples: Excel formulas, Lisp (Racket), ML, Haskell, Erlang, F#, Mathematica, XSLT, Clojure

Syntax, Semantics, and Ambiguity

1. Syntax: The way we’re allowed to say things
   1. ”This cake have too many sugar”
2. Semantics: What the program means
   1. ”Toronto is the capital of Canada”
3. Ambiguity: Valid programs have exactly one meaning
   1. ”Amir told Peter that he had a problem”

2.2 | DrRacket

Two Windows:

• Definitions (top) for writing programs
• Interactions (bottom) for texting, experimenting

2.3 | Values, Expressions, and Functions

Intro

• Functions are numbers or mathematical objects
  • 5, 4/9
• Expressions combine values with operators and functions
  • 5+2, $\sin (2\pi )$
• Functions generalize similar expressions
  • $f(x)=x^2=4x+2$ generalizes for all x

Values (numbers) in Racket

• Integers in Racket are unbounded
• Rational numbers in Racket are represented exactly: $2,3\frac{1}{7}$
• Irrational numbers are flagged as being inexact
  • (sqrt 2) = #i1.4142

Math functions consist of:

• the function name (eg. f)
• its parameters (eg. x,y)
• an algebraic expression using the parameters as placeholders for future values

Function Application

• Supplies arguments for parameters

Many Possible Substitutions

• Apply functions only to values (expressions simplified first)
• Always take the LEFTMOST choice

Parentheses Application

• Function Application: f(3)
• Ordering: g(1,2)
• Harmonization: infix operators (+,-) are treated like functions

Function Application in Racket

• g(1,3) becomes (g 1 3)
• g(g(1,3), f(3)) becomes (g (g 1 3) (f 3))
• (6-4) / (5+7) becomes /(-(6,4)), +(5,7))
• 3-2+4/5 becomes (+ (- 3 2) (/ 4 5)

Other Notes

• Racket supports fraction: (/ 4 5) = 4/5`

Ex 2: Transform each example into Racket

1. (+ 2 3)
2. (* 2 3)
3. (- 44 2)
4. (+ (* 3 4) 2)
5. (\ (+ 2 4) (- 5 1))
6. (* 3 (+ 1 (+ (/ 6 2) 5)))

Evaluating a Racket Expression

(* (-6 4) (+ 3 2)) -> ;; yields symbol indicates a substitution step
(* 2 (+ 3 2)) -> 
(* 2 5) -> 
10

Rule 1: Application of Built-in functions

Substitution Rule: (f v1 ... vn) -> v

• Where f is a built in function
• v1...vn are values
• v is the value of f(v1, ... vn)

Racket Expressions causing errors

1. * is infix notation, not pre\fix
2. unnecessary bracket
3. no second argument for +()
4. two functions at once
5. division by zero

2.4 | Documentation

Examples of functions: quotient, remainder, expt, gcd

2.5 | Defining Functions

A function consists of:

• A name
• A list of parameters
• A single body expression

define is a SPECIAL FORM:

• It looks like a Racket function, but not all of its arguments are evaluated
• It BINDS a name to an expression (which uses the parameters that follow the name)

Math	Racket
$f(x)=x^2$	(define (f x) (sqr x))
$g(x,y)=x+y$	(define (g x y) (+ x y))
$area(r)=\pi r^2$	(define(area r) (* pi (sqr r))

Ex: 6: Design a function that calculates a+2b

(define (add-twice a b)(+ a (+ b b)))

Applying user-defined functions (define (g x y) (+ x y)) (g 3 5) -> (+ 3 5)

All instances of a parameter are replaced in a single step (define (h x y)(+ x x x y)) (h 10 9) -> (+ 10 10 10 9)

Ex 7: Given the definitions

(define (foo x) (+ x 4) (define (bar a b) (+ a a b))

;; This is wrong - should go from L to R
(* (foo 0) (bar 5 (/ 8 (foo 0))))
-> (* (foo 0) (bar 5 (/ 8 (+ 0 4))))
-> (* (foo 0) (bar 5 (/ 8 4)))
-> (* (foo 0) (bar 5 2))
-> (* (foo 0) (+ 5 5 2))
-> (* (foo 0) 12)
-> (* (+ 0 4) 12)
-> (* 4 12)
-> 48

Rule 2: Application of user-defined functions

General Substitution Rule: (f v1 ... vn) 0> exp

Identifiers

• Can contain letters, numbers, chars
• Cannot contain spaces, brackets, quotes
• Must contain at least 1 non-number

Observations

• Changing names of parameters does not change the function
• Different functions may use the same parameter name
• Parameter order matters

Ex 8: Predict what each expression does

P1
(define x 4)
(define (f x)(* x x))
(f 3)
=> 9, second define overrides

P2 
(define (huh? huh?)(+ huh? 2))
(huh? 7) 
=> 9

P3
(define y 3)
(define (g x)(+ x y))
(g 5)
=> 8

2.6 | Constants and Helper Functions

Defining Constants (define k 3) define p (sqr k) k=3, p=9

Advantages of constants

• Useful values, reduce errors, easier to understand
• pi, e are built in

3 Rules of Racket Substitution

1. (f v1...vn) => v when f is built-in…
2. (f v1...vn) => exp' when (define (f x1..xn) exp) occurs to the left
3. id => val where (define id val) occurs to the left

Comments

(+ 6 7) ; inline comments
;; out of line comments

#|
multiline comments
NEVER USE "comment out with a box"
|#

Helper Functions

;; Find the distance from (cx, cy) to the closer of two locations,
;; (ax, ay) and (by, by)
(define (distance-to-closer cx cy ax ay bx by)
	(min (distance cx cy ax ay)
		(distance cx cy bx by)))

(define (distance x1 y1 x2 y2)
	(sqrt(+(sqr(-x2 x1)) (sqr(-y2 y1)))))

(distance-to-closer 0 0 3 4 5 6)

check-expect (check-expect (distance 0 0 3 4) 5) (check-expect expr-test expr-expected

• expr-test is a function
• expr-expected is the expected result

Scope

• Two kinds (for now): global and functional
• DrRacket can help identify scope

2.7 | Programming

Built-in functions

• ABSOLUTE: abs, sgn (sign)
• ROUNDING: ceiling, floor, round
• CHECKING: check-expect, check-within
• TRIG: cos, sin, tan
• DEF: define
• CONSTANTS: e, pi
• EXPONENTS: exp (e^x), expt, log, sqr, sqrt
• COMPARISON: max, min
• DIVISION: quotient, remainder, modulo

3 | Simple Data

3.1 | Booleans

In Math: $x<5$ is a constraint In Racket: $x<5$ is a boolean, it has T/F value

Predicates: a function which produces a bool - name usually ends with?

;; (can-vote? age) produces true if the person is voting age
(define (can-vote?) age)
	(>= age 18)

(check-expect (can-vote? 17) false)
(check-expect (can-vote? 20) true)

3.2 | Combining Predicates

;; (can-vote? age) produces true if the person is voting age
(define (can-vote-v2?) age citizen?)
	(and (>= age 18) citizen?)

(check-expect (can-vote-v2? 18 true) true)
(check-expect (can-vote? 18 false) false)

Operators

• Booleans: and, or, not
• Predicates:
  • number? integer?
  • positive? negative?
  • even? odd?
  • zero? exact?
  • boolean? false? (no purpose for true?)

Short-circuit evaluation

;; evaluating easy cases first
(and (odd? x) (> x 2) (prime? x))

;; steep line
(define (steep? dx dy)
	(or (= dx 0) ; avoid /0
		(>= (/ dy dx) 1)))
		
(define (not-steep? dx dy)
	(and (not (= dx 0)) ; avoid /0
		(< (/ dy dx) 1)))

RULES 4-6: Substitution rules for AND

1. (and false...) => false
2. (and true...) => (and ...)
3. (and) => true ; IMPORTANT

RULES 7-9: Substitution rules for OR

1. (or true...) => true
2. (or false...) => (or ...)
3. (or) => false

3.3 | Conditional Expressions

(cond [(q1) a1]
	[(q2) a2]
	[(q3) a3])

Cond Evaluation

• Evaluates top-down
• Once it finds a TRUE, returns it

No satisfied questions

• returns (cond)
• Error: all cond questions produced false

3.4 | else

(cond [(q1) a1]
	[(q2) a2]
	[else a3])

Rules 10-12: Substitution in cond expressions

1. (cond [false exp] ...) => (cond...)
2. (cond [true exp] ...) => exp
3. (cond [else exp]) => exp

3.5 | Simplifying conditional expressions

Nested Conditionals

• flatten them

3.6 | Testing conditional expressions

Testing and / or

• Think of all possible cases

3.7 | Example: Taxes

Tax-payable

3.8 | Other Data

Types of data

• Symbolic: (ymbol=? mysymbol 'blue)
• Characters
• Strings

4 | Design Recipe

4.1 | Communication

4.2 | Design Recipe

Purposes

1. Understand the problem
2. Write understandable code
3. Write tested code

Example of Design recipe

;; (e10 n) produce 1 followed by n zeros
;; Examples:
(check-expect (e10 2) 100)

design (e10 n)()

Components

1. Purpose
2. Examples
3. Contract (type of I/O)
4. Definition
5. Tests

4.3 | Example: Applying the Design Recipe

;; (sum-of-squares n1 n2) produces the sum of squares n1 and n2
;; Examples:
(check-expect (sum-of-squares 3 4) 25)

;; sum-of-squares Num Num -> Num
(define (sum-of-squares) n1 n2)
	(+ (sqr n1) (sqr n2)))

;; Tests
(check-ezpect (sum-ofs-squares 0 0) 0)

4.4 | Tests

(check-expect (sum-of-squares 3 4) 25)
(check-within (sqrt 2) 1.414 .001)
(check-error (/ 1 0) "/: division by zero")

4.5 | Contracts

Types:

• Num (Numbers)
• Int
• Nat (Naturals)
• Bool
• Char
• Str
• Sym (Symbols)
• Any

5 | Structures

5.1 | Compound data

;; Rectangles
(define-struct rect (top left width height color))

;; Examples
(define blue-rect (make-rect 3 1 3.5 2 'blue))

;; Contract
;; (rect-area r) produces the area of rectangle r.
(check-expect (rect-area blue-rect) 7)

;; Defintition
;; rect-area Rect -> Num (CONSUMES THE STRUCT RECT)
(define (rect-area r)...)

;; Helper
;; rect-move: Rect Num Num -> Rect
(define (rect-move r dx dy))
	(make-rect (+ (rect-top r) dy)
				(+ (rect-left r) dx)
				(rect-width r)
				(rect-height r)
				(rect-color r)))

5.2 | Formalities: Syntax and semantics

Rect CREATES 7 FUNCTIONS:

• Constructor: make-rect
• Selectors: rect-top, rect-left, rect-width, rect-height, rect-color
• Type Predicate: rect? (returns true if argument is rect)

(define-struct rect (top left width height color))
;; A Rect is a (make-rect Num Num NUm Num Sym)
;; Requries: width and height are non-negative

5.3 | Templates

Struct follows the same design recipe rules as a functions

5.4 | Nested Structures

(define-struct point (x y))
;; A Point is a (make-point Num Num)

(define-struct rect (topleft w h))
;; A rect is a (make-rect Point Num Num)
;; Requires: w, h >= 0

5.5 | Mixed Data

(define-struct circle (centre radius))
;; A Circle is a (make-circle Point Num)
;; Requires: radius >= 0

;; A shape is one of a Rect or Circle

6 | Lists

6.1 | Intro

Building Lists

;; define empty list
(define wish-list empty)
;; add one item
(cons "comic book" empty)
;; or
(define wish-list (cons "comic book" empty))
;; add an item
(cons "turtle" (cons "comic book" empty))
;; long list
(cons "bicycle")
	(cons "video game"
		(cons "play-doh"
			(cons "turtle"
				cons "comic book"
					empty)))))

Deconstructing Lists

;; cons: Any (listof Any) -> listof Any
;; first: (listof Any) -> Any
;; rest: (listof Any) -> listof Any

Predicates

• (empty? v)
• (cons? v) true if v is a cons value
• (list? v) true if v is a cons or empty

6.2 | Contracts

;; A (listof X) is one of 
;; * empty
;; * (cons X (listof X))

6.3 | Formalities

List value are

1. empty
2. (cons v list) NOTE: expressions like (+ 1 1) are not values

Substitution rules

1. first (cons a lst)) -> a
2. rest(cons a lst)) -> lst
3. (empty? empty) -> true
4. (empty? a) -> false
5. (cons? (cons a lst)) -> true

6.4 | Processing Lists

;; lon-template: (listof Num) -> Any
(define (lon-template lon)
	(cond
		[(empty? lon) ...]
		[(cons? lon) (...
						... (first lon))
						(lon-template (rest lon)))]))

;; lon-sum: (listof Num) -> Num
(define (lon-sum lon)
		(cond
			[(empty? lon) 0] ; 1 for multiplication, base case is important
			[(cons? lon) (+ (first lon))
								(lon-sum (rest lon)))]))

6.5 | Templates

6.6 | Patterns

6.7 | Lists from lists

6.8 | Design Recipe Refinements

6.9 | Strings

6.10 | Sorting

;; INSERTION SORT

;; (sort lon) sorts the elements of lon in non-decreasing order
;; Examples:
(check-expect (sort (cons 3 (cons 4 (cons 2 (cons 5 (cons 1 empty))))))
              (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 empty))))))

;; sort: (listof Num) -> (listof Num)
(define (sort lon)
  (cond [(empty? lon) empty]
        [else (insert (first lon) (sort (rest lon)))]))

;; (insert n slon) inserts the number n into the sorted list slon
;;     so that the resulting list is also sorted.
;; Example:
(check-expect (insert 3 (cons 1 (cons 4 (cons 5 empty))))
              (cons 1 (cons 3 (cons 4 (cons 5 empty)))))

;; insert: Num (listof Num) -> (listof Num)
;;   Requires: slon is sorted in non-decreasing order
(define (insert n slon)
  (cond [(empty? slon) (cons n empty)]
        [(<= n (first slon)) (cons n slon)]
        [else (cons (first slon) (insert n (rest slon)))]))

7 | Natural Numbers

7.1 | Review: Data definitions and Templates

7.2 | A Formal Definition of Natural Numbers

;; A NN is a 
;; * 0
;; * (add1 NN)

7.3 | Templates

;; NN-template: NN -> Any
(define (nn-template nn))
	(cond
		[(zero? nn) ...])
		[else (... 
				... nn)
					(NN-templtae (sub1 nn)))]))

Countdown

;; (countdown n) yields a list of NN, conunting down from n
(define (nn-template nn))
	(cond
		[(zero? nn) (cons 0 empty)])
		[else (cons nn (countdown (sub1 nn)))]))

;; (countdown n s) yields a list of NN, conunting down from n, stopping at s (inclusive)
(define (nn-template nn s))
	(cond
		[(= s nn) (cons s empty)])
		[else (cons nn (countdown (sub1 nn s)))]))

;; (countup nn) counts up from a negative to 0
(define (nn-template nn))
	(cond
		[(zero? nn) (cons 0 empty)])
		[else (cons nn (countup (add1 nn s)))]))

7.4 | Intervals

7.5 | Counting Up

8 | More Lists

8.1 | Fixed-length Lists

• (list x1 ... xn) produces a fixed-length list
• (first lst), (second lst) ... (eighth lst) produce the nth item

Contracts

• A SalaryRec is a (list Str Num)
• A Payroll is a (listof SalaryRec)

A Salary is a (list Str Num)

;; salary-template: Salary -> Any
(define (salary-template sal))
	(... (first sal)   ;; Name
		(second sal))) ;; Amount

;; A Payroll is a (listof Salary)
;; A payroll is a 
;; * empty
;; * (cons Salary Payroll)

;; payroll-template: Payroll -> Any
(define (payroll-template pr)
	(cond
		[(empty? pr) ...]
		[else (... (salary-template (first pr))
					(payroll-template (rest pr)))]))

Taxes

(define (income-tax amount)
	(* amount 0.20))

;; calc-taxes Payroll -> (listof (list Str Num))
(define (calc-taxes pr)
	(cond 
	[(empty? pr) empty]
	[else (cons (calc-taxes/salary (first pr))
		(calc-taxes (rest pr)))]))

;; calc-taes/Sal -> (list Str Num)
(define (salary-templaet sal)
	(list (frist sal)
		(income-tax (second sal))))

(calc-taxes (list (list "A" 10000)
				(list "B" 5000)
				(list "C" 15000)))

;; should be 2000, 1000, 3000

Different kinds of lists

• Flat lists (listof)
• List of lists
• Nested lists

Cons vs List

• Cons takes exactly two arguments
• List consumes any number of arguments

8.2 | Dictionaries

'' A Kvp/Key-value pair is a (list Num Str)

(define (kvp-key kvp)(first kvp))
(define (kvp-value kvp) (second kvp))

(define kvp-template kvp)
	(... (first kvp) ; key
		(second kvp))) ; value

(define (dict-template dict
	(cons
		[(empty? dict)...]
		[(cons? dict)(... (kvp-template (first dict))
						(dict-template (rest dict )))]))

8.3 | 2D Data

8.4 | Processing Two Lists

This	Produces
(cons (list 1 2) (list 3 4))	(list (list 1 2) 3 4) (a list of length 3)
(list (list 1 2) (list 3 4))	(list (list 1 2) (list 3 4)) (a list of length 2)
(append (list 1 2) (list 3 4))	(list 1 2 3 4) (a list of length 4)

8.5 | Processing a list and a number

9 | Patterns of Recursion

9.1 | Simple Recursion

SIMPLE = Arguments are either:

• Unchanged
• One step closer to the base condition

9.2 | Accumulative Recursion

ACCUMULATIVE = arguments are either

• Unchanged
• One step closer to the base case
• A partial answer (passed into an accumulator)

9.3 | Mutual Recursion

Using two or more function (functions on general trees in M13)

9.4 | Generative Recursion

Euclidean Algorithm

10 | Binary Trees

10.1 | Examples and vocabulary

10.2 | Binary Trees

Examples

• sum-keys
• count-nodes
• increment
• search-bt
• search-bt-path
• search-bt-path-v2

10.3 | Binary Search Trees

BST ordering property

• key is greater than every key in left
• key is less than every key in right

10.4 | Augmenting Trees

10.5 | Binary Arithmetic Expression Trees

11 | Mutual Recursion

11.1 | Mutual Recursion and Nats

hell nah

11.2 | Mutual Recursion and Lists

;; (mergesort lst) puts lst in increasing order
;; mergesort: (listof Num) -> (listof Num)
(define (mergesort lst)
  (cond [(empty? lst) empty]
        [(empty? (rest lst)) lst]
        [else (merge (mergesort (keep-alternates lst))
                     (mergesort (drop-alternates lst)))]))

;; Closed-box tests:
(check-expect (mergesort (list 4 7 3 0 1 9 5 2 6 8)) (list 0 1 2 3 4 5 6 7 8 9))

11.3 | Mutual Recursion and Trees

12 | General Trees

I started taking my notes in DrRacket files here

;; An Arithmetic Expression (AExp) is one of:
;; * Num
;; * OpNode

(define-struct opnode (op args))
;; An OpNode (operator node) is a
;; (make-opnode (anyof '* '+) (listofAExp))

;; (eval exp) evaluates exp
;; Examples:
(check-expect (eval 5) 5)
(check-expect (eval (make-opnode '+ (list 1 2 3 4))) 10)
(check-expect (eval (make-opnode '* (list 1 2 3 4))) 24)
(check-expect (eval (make-opnode '+ (list 1
                                          (make-opnode '* (list 2 3))
                                          3))) 10)

;; eval: AExp -> Num
(define (eval exp)
  (cond [(number? exp) exp]
        [(opnode? exp) (apply-op (opnode-op exp)
                                 (opnode-args exp))])) 

;; apply: (anyof '+ '*) (listof AExp) -> Num
(define (apply-op op args)
  (cond [(empty? args) (cond [(symbol=? op '+) 0]
                             [(symbol=? op '*) 1])]
        [(symbol=? op '+) (+ (eval (first args))
                             (apply-op op (rest args)))]
        [(symbol=? op '*) (* (eval (first args))
                             (apply-op op (rest args)))]))

13 | Local Definitions

;; HERON'S FORMULA
(define (t-area-v4 a b c)
	(local [(define s (/ (+ a b c) 2))]
		(sqrt (* s (- s a) (- s b) (- s c)))))

14 | Functions as Values

;; my-filter: (X -> Bool) (listof X) -> (listof X)
;; X indicates that the types must be the same
(define (my-filter pred? lst)
  (cond
    [(empty? lst) empty]
    [(pred? (first lst))
     (cons (first lst) (my-filter pred? (rest lst)))]
    [else (my-filter pred? (rest lst))]))

(define (is-double-digit? n)
  (or (and (< -100 n) (<= n -10))
      (and (<= 10 n) (< n 100))))

(my-filter is-double-digit? '(1 2 3 4 10 20 30 40 100 200 -10))

(define (make-is? t)
  (local
    [(define (is? s) (symbol=? s t))]
    is?))

;; (my-filter (make-is? 'a) '(a c d c a b b a))

;; (my-filter (lambda (s)(or (symbol=? s 'c)(symbol=? s 'a))) '(a c d c a b b a))

(define (funny-add a b)
  (* 2 (+ a b)))
;; (funny-add 2 3)

(define funny-add-2 (lambda (a b) (* 2 (+ a b))))
;; (funny-add-2 2 3)

(define make-adder
  (lambda (x)
    (lambda (y)
      (+ x y))))

;; ((make-adder 3) 4)

(define recip
  (lambda (x) (/ 1 x)))

;; (recip 2)

;; div-by-k? Nat -> (Num -> Bool)
(define (make-div-by-k? k)
  (local
    [(define (div-by-k? nn) (= (remainder nn k) 0))]
     div-by-k?))

;; count-factors: Nat -> Nat
(define (count-factors n)
  (local
    ;; cf/wrk: (listof (Nat -> Bool)) -> Nat
    [(define (cf/wrk lodbk)
       (cond
         [(empty? lodbk) 0]
         [((first lodbk) n) (+1 (cf/wrk (rest lodbk)))]
         [else (+ 0 (cf/wrk (rest lodbk)))]))]
  (cf/wrk (make-div-by-k? n))))

15 | Lambda

My favourite lamb!

16 | Functional Abstraction

;; MAPS: apply a function to every value

;; lst-map (X -> y) (listof X) -> (listof Y)
(define lst-map
  (λ (func lst) (cond
                  [(empty? lst) empty]
                  [(cons? lst) (cons (func (first lst))
                                     (lst-map func (rest lst)))])))

;; (map (λ (x) (cond 
;;               [(even? x) (add1 x)]
;;               [(odd? x) (sub1 x)])) (list 1 2 3 -4))

;; (map (λ (x) (list x (sqr x))) (list 1 2 3 -4))

;; FOLDR: applies a predicate to a list

;; lst-foldr (X Y -> Y) Y (listof X) -> Y
(define lst-foldr
  (λ (func base lst) (cond
                       [(empty? lst) base]
                       [(cons? lst) (func (first lst)
                                          (lst-foldr func base (rest lst)))])))

;; f: Int Bool -> Bool
(define (and-even? x y)
  (and (even? x) y))

;; (lst-foldr and-even? true (list 1 2 3 4))
;; (lst-foldr and-even? true (list 2 4 6 8))

;; (lst-foldr (λ (cur rror) (and (even? cur) rror)) true (list 1 2 3 4))
;; (foldr (λ (cur rror) (cond
;;                       [(< cur 5) (cons cur rror)]
;;                       [else rror])) empty (list 2 4 6 8))


;; (foldr (lambda (x rror) (+ x rror rror)) 1 (list 3 4 5))

;; lst-template: (listof Any) -> Any
(define lst-template-1
  (λ (lst)
    (cond
      [(empty? lst)...]
      [(cons? lst) (... (first lst)
                        (lst-template-1 (rest lst)))])))

;; lst-template-2: (listof Any) -> Any
(define lst-template-2
  (λ (lst)
    (local
      [(define lst-template-rec
         (λ (acc lst) (cond
                        [(empty? lst) acc]
                        [(cons? lst) (lst-template-rec
                                      (... (first lst) acc)
                                      (rest lst))])))]
      (lst-template-rec ... lst))))

;; FOLDL

;; foldl: () Y (listof X)
(define my-foldl
  (λ (func base lst)
    (local
      [(define my-foldl-wrk
         (λ (acc lst) (cond
                        [(empty? lst) acc]
                        [(cons? lst) (my-foldl-wrk
                                      (func (first lst) acc)
                                      (rest lst))])))]
      (my-foldl-wrk empty lst))))

;;(foldr cons empty (list 1 2 3 4 5 6))
;;(foldl cons empty (list 1 2 3 4 5 6))

;; BUILD LIST

;;(build-list 5 (lambda (x) (* 2 x)))

17 | Generative Recursion

(define (euclid-gcd n m)
  (cond [(zero? m) n]
        [else (euclid-gcd m (remainder n m))]))

;; (euclid-gcd 10 15)
;; (euclid-gcd 13 15)

(define (my-qsort lst)
  (cond
    [(empty? lst) empty]
    [(empty? (rest lst)) lst]
    [else
     (local
       [(define pivot (first lst))
        (define left (filter (λ (x) ( < x pivot)) (rest lst)))
        (define right (filter (λ (x) (<= pivot x)) (rest lst)))
        ]
       (append (my-qsort left) (list pivot) (my-qsort right))
       )]
    )
  )

(my-qsort (list 1 6 3 0 -5 1 5 98 -8))

18 | Graphs

;; A Vertex is a Sym

;; A Graph is a
;; * empty
;; (listof (list Sym (listof Sym))


(define g
  '((A (C D E))
    (B (E J))
    (C ())
    (D (F J))
    (E (K))
    (F (K H))
    (H ())
    (J (H))
    (K ()))) 

;; graph-template: Graph  -> Any
(define (graph-template g)
  (cond
    [(empty? g ).. ]
    [(cons? g) (... (... (first (first g)) ;; current vertex
                         (lov-template second (first g))) ;; current vertex out-neighbours
                    (graph-template (rest g)))]))

;; lov-template: (listof Vertex) -> Any
(define (lov-template lov)
  (cond
    [(empty? lov) ...]
    [(cons? lov) (... (first lov)
                      (lov-template (rest lov)))]))

;; neighbours: Vertex Graph -> (listof Vertex)
(define (neighbours v g)
  (cond
    [(symbol=? v (first (first g))) (second (first g))]
    [else (neighbours v (rest g))]))

(define-struct success (path))
(define-struct failure (visited))

;; (find-path orig dest g) finds path from orig to dest in g if it exists
;; find-path (Node Node Graph -> (anyof (ne-listof Node) false)
(define (find-path orig dest g)
  (cond [(symbol=? orig dest) (list dest)]
        [else (local [(define nbrs (neighbours orig g))
                      (define ?path (find-path/list nbrs dest g))]
                (cond [(false? ?path) false]
                      [else (cons orig ?path)]))]))

;; (find-path/list nbrs dest g) produces path from
;; an element of nbrs to dest in g, if it exists
;; find-path/list: (listof Node) Node Graph -> (anyof (ne-listof Bode) false)
(define (find-path/list nbrs dest g)
  (cond [(empty? nbrs) false]
        [else (local [(define ?path (find-path (first nbrs) dest g))]
                (cond [(false? ?path)
                       (find-path/list (rest nbrs) dest g)]
                      [else ?path]))]))

(find-path 'A 'E g)

;; find-path has a recursive nature
;; find-path: Vertex Vertex Graph -> (anyof false (listof Vertex))
(define (find-path-v2 orig dest visited g)
  (cond
    [(symbol=? orig dest) (make-success (list orig))]
    [else (local
            [(define result (find-path-v2/lov (neighbours orig g) dest (cons orig visited) g))]
            (cond
              [(failure? result) result]
              [else (make-success (cons orig (success-path result)))]))]))
                          
(define (find-path-v2/lov lov dest visited g)
  (cond
    [(empty? lov) (make-failure visited)]
    [(member? (first lov) visited) (find-path-v2/lov (rest lov) dest visited g)]
    [else (local
            [(define result (find-path (first lov) dest visited g))]
            {cond
              [(failure? result) (find-path-v2/lov (rest lov) dest visited g)]
              [else result]})]))

19 | Computing History

Mathematics + Engineering + Theory = Computing

Calculators

• Step reckoner (Leibniz): Basic operations
• Lookup table: trig calculations
• Slide rule: multiplication, division, exponents, logarithms
• Difference Engine (Charles Babbage): advanced mechanical calculator, never built
• Analytical Engine (Charles Babbage): same thing, but could be programmed, never built
  • Ada Lovelace was one of the first people to program it
• Tabulating Machine (Herman Hollerith): electro-mechanical (gears and mercury) addition
  • The company that made this machine eventually became IBM

Problem: Analog computers are too slow

• Voltage as data: quinary computer with 5 states, but was unstable
  • binary computer with 2 states was much more stable

Binary (Boolean) Algebra

• George Boole, The Laws of Thought, 1854, extending Aristotle’s logic with math

Crisis 1: How to control the flow of electricity?

• Switch: a human to opens or closes
• Relay: a control current opens or closes (maybe Gauss invented it)
• Electro-mechanical computers

Digital Programmable Computers:

• German computer: Z3, 1941
• American computer: Harvard Mark I, 1944
  • Grace Hopper (programmer) coined the term “bug” because bugs would crawl into the relays to nest because they were warm

Crisis 2: How do we make fully electronic computers with no relays?

• Vacuum tube allows for electrical control of electricity
• Colossus (1943), Alan Turing : first fully-electronic computer designed for inverting the Enigma

Foundational Crisis of Mathematics, 1900

• Mathematicians couldn’t describe their own axioms
• Complete: for any formula x, if x is true, then x is provable
  • Godel: Any axiom system powerful enough to describe arithmetic over the integers is not complete
• For any formula x, there are no proofs of both x and not x

Hilbert’s Entscheidungsproblem, 1928

• Does an algorithm exist that takes in a logic statement as input and produces yes if it’s valid?
• Alonzo Church said it’s not solvable when using lambda calculus (math approach)
  • This created functional programming
• Alan Turing said it’s not solvable when using a Turing machine (engineering approach)
  • This created imperative programming

Noam Chomsky’s Hierarchy

• Classifies formal languages from type 0 to type 3

Alan Turing

• Automatic Computing Engine

John von Neumann’s Von-Neumann Architecture

• Processing unit
• Control unit
• Memory for data and instructions
• Mass storage
• Input / Output

Crisis 3: Vacuum tubes break too easily

• Solution: Solid state semiconductors (transistors), 1947
• Three layers of silicon infused with metals that behave like a relay

Software

• Grace Hopper
  • Proposed the idea of high-level programming languages (1950) and compilers (1952)
  • FLOWMATIC for the UNIVAC 1 computer (1955)
• John McCarthy
  • Coined the term Artificial Intelligence
  • Invented LISP, 1958, a predecessor for Racket