CS 1102: Accelerated Introduction to Program Design

24 August 2022
- Introduction
- Expressions
  - The #i means the number is an approximation of the exact value
- Evaluation
  - To evaluate a primitive call
    - Reduce operands to values
    - Apply primitive to the values
- Strings and Images
  - Racket uses zero-based indexing
- Constant Definitions
  - Readability & changeability
  - To form a constant definition
    - (define <name> <expression>)
    - Evaluate expression, obtain value, bind value to name
- Function Definitions
  - DRY principle
  - To form a function definition
    - (define (<function name> <parameter(s) name>…) <function body>)
  - To form a function call expression
    - (<function name> <operands>…)
  - To evaluate a function call
    - Reduce operands to values
    - Replace function call by its body and replace every occurrence of paraments by corresponding arguments
  - Fun: One important result in computer science says that if you have a language with just functions, you can write any program in any language, but that’s just troublesome to code in → Lambda calculus
- Booleans and if Expressions
  - Predicates: primitives/functions that produce a boolean value
  - To form an if expression
    - (if <predicate> <affirmative> <negative>)
  - To evaluate an if expression
    - Evaluate predicate
    - If predicate returns true, replace entire expression with true answer expression, if false, do otherwise
    - If predicate returns a value other than true or false, errors
  - To form and expression
    - (and <expr1> <expr2>…)
    - all <exprn> must produce boolean
  - To evaluate and expression
    - Evaluate <exprn> one at a time
    - If an <exprn> produces false immediately produce false
    - If all <exprn> produce true then produce true
- Using the Stepper
  - Shows step-by-step evaluation of expressions
- Full Speed How-to—Design-Function (HtDF) Recipe
  - Signature, purpose, stub
  - Examples (wrapped in check-expect)
  - Inventory - template & constants
  - Code body
  - Test and debug
- Discovering Primitives
25 August 2022
- Slow Motion HtDF Recipe
  - Signature: Type … -> Type
  - Purpose: 1 line description of output in terms of input
  - Stub: a function defintion that has correct function name, has correct number of parameters, produces output of the correct type
  - Examples/tests: illustrate function’s behavior
  - Template: function outline
- HtDF: area
- HtDF: image area
- HtDF: image tall
  - Tests should have complete code coverage (given the tests, how much of the code is executed)
- cond expressions
  - To form cond expression
    - (cond [<question> <answer>] … [else <else case>])
- data definitions
  - A new part of HtDF recipe
  - Describe how information is represented as data
  - HtDD
    - (Possible) structure definition
    - Type comment: defines a new type name and shows how to form data of that type
    - Interpretation: describes the correspondence between information and data
    - Examples of that data type
    - Template for a one-argument function operating on data of this type
  - #; comments out the whole expression or function definition that follows
- atomic non-distinct data definitions
  - atomic data can’t be taken apart into pieces that are meaningfully part of the same problem domain
- define-struct
  - To form a structure definition
    - (define-struct <structure name> <field names>)
  - Declares 3 or more definitions: constructor, selector(s), predicate
    - constructor: make-<structure name>
    - selectors: <structure name>-<field name>
    - predicate: <structure name>?
- compound data definitions
26 August 2022
- Introduction to arbitrary sized data
  - Used to represent an unknown amount of information
- List mechanisms
  - cons: a two-argument constructor
  - first: selects the first element of a list
  - rest: consumes a list with at least one element and produces the list after the first element
  - empty?: produces true if the argument is the empty list
- First list data definition
  - List is one of: empty or (cons <data type> List)
- First function operating on a list
- Revising list template
  - Well-formed self-reference data definition:
    - At least one base case
    - At least one self-reference case
  - Test cases should include base and self-reference cases
  - Should have a natural recursion for self-reference case in the template
- Designing with lists
- Positions in list templates
- Reference rule #1
29 August 2022
- Reference rule #2
- Reference rule #3
- Function composition
  - The tests for the composed do not have to test its components exhaustively, their individual tests will do, but they do need to exercise the combination of functions
- List of images
- Helpers on a list
  - A natural helper is when a template contains a call to a template function for data of a different type. Called when what you are doing involves 2 or more procedures, should not use when you’re just accessing a single function
  - Signature can’t say everything about input. In those cases, we can write an assumption as part of the function design
- Domain knowledge shift
  - In bigger programs, the tests would be in a separate file, and testing constants would go in that file as well
  - When there is a domain knowledge shift (one kind of a problem involves another kind), use a helper
30 August 2022
- Helper wrapup
- pair programming
31 August 2022
- Interactive programs
- The big bang mechanism - (big-bang <initial world state>
  
  (on-tick next-worldstate) ; WorldState -> WorldState
  
  (to-draw render-worldstate) ; WorldState -> Image
  
  (on-key handle-key-fn) ; KeyEvent -> Image
  
  (stop-when stop-fn)) ;
Analysis
- How to Design Worlds recipe
  - Domain analysis
    - Sketch program scenarios
    - Identify constant information
    - Identify changing information
    - Identify big-bang options
  - Build the actual program
    - Constants (based on 1, 2 above)
    - Data definitions (based on 1, 3 above)
      - Things that vary must be contained within worldstate (struct is an option)
    - Functions
      - main first (based on 1, 2 and 1, 3 above)
      - wish list entries for big-bang handlers
    - Work through wish list until done
Program Through main Function
Works through the wish list
Improving a World Program - Add SPEED
Improving a World Program - Add key handler
- KeyEvent is a Racket primitive and a large enumeration
- The fule for functions that operate on an enumeration is to test every case of the enumeration
- For large ones, we will do white-box testing - base the tests on our knowledge of how the function is coded, not just what it is supposed to do
1 September 2022
- HtDW with compound data and a first helper function
  - Helper functions is for
    - Unit testing
    - Documentation
    - Code readability and traceability
- List abbreviations
  - (list <args>), (append <list1> <list2>)
- Mutually recursive
  - Arbitrary-size in two dimensions require two cycles in the type reference graph
  - While self-reference allows each element to have an arbitrary amount of sub-elements, mutual reference allows the tree to have arbitrary depth
- Templating mutual recursion
  - Just reduce everything to primitive in templates
5 September 2022
- Mutual recursion part 1
  - When designing functions for mutually referential types, you design one for each type
- Mutual recursion part 2
- Backtracking search
  - Make a note to add parameters to natural recursive calls if functions need more than one
  - Basically DFS but immediately prunes invalid branches
6 September 2022
- Introduction to local
  - Local expressions allow us to have definitions, functions and constants that are only available in a portion of the program
- Intuitions about local - Local definitions only exist inside the local expression - To form a local expression - (local [<local definitions> …]
  
  <body expressions>)
Lexical scoping
- Scope contours: draw boxes around definitions. Reference to values inside the boxes will point to the values defined in the [nearest enclosing] box
Optional: Local evaluation rules
- To evaluate local expression
  - Renaming
    - Rename definitions and all references to definitions in the local’s body expression, the new name must be globally unique
  - Lifting
    - Lift renamed definitions out of the local, into top-level scope (not just up one level, it’s all the way up!)
  - Replace entire local with renamed body
Local encapsulation
- In industrial-strength languages, encapsulated functions can still be unit tested
- Good candidates for encapsulation
  - Two or more functions that work together (or one function with helpers)
  - The rest of the program only wants to call one
- Refactoring: changing a program’s code/structure without changing the program’s behavior
- Unit test: A software development process in which the smallest testable parts of an application, called units, are individually and independently scrutinized for proper operation
- Encapsulation allows multiple programmers to work on huge programs without having conflicting names
Avoid recomputation
- Use local to avoid recomputation, especially in recursive functions because exponential growth problems are nasty
- Wrap the closest enclosing expression that has recomputation with a local expression and give the value a local name
8 September 2022
- Local abstraction
- Abstraction from examples, part #1
  - Identify two highly repetitive expressions
  - Introduce a new function
    - Around one copy of repetitive code with a more general name
    - Add parameters for points of variance
    - Use parameters in POV
  - Replace specific expressions with calls to abstract function and pass varying values
- Abstraction from examples, part #2
  - A higher-order function can
    - consume one or more functions
    - produce a function
  - map and filter functions (map applies the function passed in to all elements in list, filter applies the predicate passed in)
  - When abstracting functions, work the HtDF recipe backwards (Body → tests/examples → Purpose → Signature)
- Abstraction from examples, part #3
  - Look in function body to determine abstract function’s signature
  - Higher-order function signature example
    - map2: (X → Y) (listof X) → (listof Y)
    - filter2 (X → Boolean) (listof X) → (listof X)
  - No need ListOfX data definition anymore, just (listof X)
  - Use of type parameters ensure type consistency
11 September 2022
- Built-in abstract functions
  - map, filter
  - map only accepts one-argument functions → closures
  - (foldr <combinator> <base case result> <listof X>) → fills in the template for (listof X)
  - identity → returns the input
  - (build-list n fn) → builds a list up to n - 1 with fn applied to every element
  - (andmap fn lox) → produces true if fn produces true for every element in lox
  - (ormap fn lox) → produces true if fn produces true for any element in lox
  - Base case test isn’t needed when using built-in abstract functions because they have been thoroughly tested
- Closures
  - If you find it easy to design local functions, you do not have to follow the recipe. Otherwise if you find it hard, just do it top-level
  - Closure: the value passed into a top-level function can be accessed by local functions and definitions
- Abstract fold functions
  - Fold function: an abstract function for the (listof X) type, based directly on the template(s)
  - Convention: put function arguments first in parameters
- Lambda
  - To form a lambda expression
    - (lambda (<parameter> …) (<function body>))
12 September 2022
- Context preserving accumulators
  - Context information about how far we are is lost in the structural recursion template → need a way to preserve that
- Context preserving accumulators part 2
  - Structural recursion template
  - Wrapping function in the outer function, local and trampoline
  - Adding additional accumulator parameter
  - After that, remember to
    - initialize accumulator in trampoline
    - use accumulator value
- Exercise: skip n
- Exercise: skip n, part 2
- O notation
  - How time scales to some input variables
    - Different steps get added
    - Drop constants
    - Different inputs → different variables
    - Drop non-dominant terms
- Quicksort
  - Take a pivot point in the list and move all smaller terms to the left, and all bigger terms to the right
  - Terms on the left never get compared against the terms on the right, they just get compared to the pivot once → Quick
  - log(N) complexity
  - Tree recursion solution: append two filtered halves, > and <= with pivot sandwiched in between
  - How to choose pivot point
    - Choose the middle point in the list (statistically, that number is the median of the list)
    - Swap the middle term with the last number in list
    - Two pointers: one for comparing terms against pivot, and one for the next number in the list that is larger than the pivot (the endpoint of the swap)
    - Starting from index 0, advance pointer 1 if number is larger than pivot. If meets a term that is smaller than pivot, swap it with pointer 2 (index 0), and increment pointer 2 to the next term (the next number that is larger than pivot)
    - The last thing to do is swap pivot with pointer 2
- Computational complexity
  - P(olynomial time): a class that includes all problems that can be solved by a reasonably fast program (rubiks)
  - NP: a class that includes problems that given a correct solution, you can at least check it in a reasonable amount of time (sudoku)
  - Quickly recognize correct solutions vs. a quick way to find them
  - Polynomial time: S = f(N) → a polynomial function, not exponential
  - Non-deterministic Polynomial time: given an infinite amount of computers, it takes Polynomial time to check all possible answers simultaneously
13 September 2022
- Generative recursion — intro
  - Structural recursion: start with a piece of data and each recursive call takes a sub-piece of the data
  - Generative recursion: on each recursive call, generate new data for it to operate on
- Genrec — fractals
  - Fractals: images that have a recursive structure
- Genrec — termination arguments
  - Collatz conjecture: number series, if n is even, divide by 2, else times 3 add 1 → always end at 1
  - Also called hailstone because that’s what it looks like when graphed
  - Three part termination argument
    - Base case: when does the function stop?
    - Reduction step: What is the argument to the function in the next recursive call?
    - Argument that repeats application of reduction step will eventually reach the base case
      - This is sometimes too hard to prove (Collatz)
- Sudoku terminology
15 September 2022
- Sudoku data definition
  - (list-ref <list> <index>) → get value at index of list
  - (take <list> <index>) → returns a list [0, index] of original list, including
  - (drop <list> <index> → returns the list after the element at index
- Search intuition
  - General: Take an initial board → Generate a tree of all possible boards → Look for a solution ⇒ Generative recursion problem
  - Steps
    - Take a small portion of the board
    - Fill in the first empty square with [1, 9] → 9 branches
    - Prune invalid boards (check if unique in the portion’s units)
    - Along each branch, we either
      - come to a board with no valid next boards → produce false
      - come to a full & valid board → GOAL!
  - Technical: Generate an arbitrary-arity tree & backtracking search
- Template blending
  - Backtracking search: When the test for base case fails, produces false, for recursive calls, try first child, if successful, produce that, else try rest of the children. Wrap try in local for performance
- Sudoku wish list
- Making wish list come true #1
18 September 2022
- Making wish list come true #2
- Making wish list come true #3
- Minimax - A way of solving games, commonly zero sum (one player wins, the other loses, e.g: tic-tac-toe, chess,…) - Perfect information: player knows the results of all previous moves. There is one best way to play for each player - Simple, discrete states for representation

Game state

Game state represented as tree

Depth first search
Depth m with b legal moves O(b^m)
Space complexity (memory) O(bm)
Impractical for most games, but basis of other algorithms
For more than 2 players-game, utility vectors instead of values
Alpha-Beta pruning
- Do not need to explore all nodes

minimax

20 September 2022
- Tail recursion
  - The context of the pending computation is stored in the stack, a limited and expensive part of the computer memory → try not to use it unless need to
  - Tail position: an expression in a position where its result is the result of the enclosing function
  - A recursive call not in the tail position causes a build-up in context
- Tail recursion, part 2 - foldl is the tail recursive abstract fold function for the lists - Make a function tail recursive using accumulator - template according to accumulator recipe - delete part of template wrapping around recursive call - computation that would have been around recursive call moves to be in accumulator argument position -

Tail recursion

(everything after the comic is optional)
- Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.
List of accounts
BST — intro

Sorting

Account BST

Time complexity of BSTs: O(logn)
- On each recursive call, the list gets smaller by 1/2
BST — data definition
21/09/2022
- BST — search
- AVL trees
  - A special kind of BST where the difference in the height of the left subtree and the right subtree is never greater than 1 → more balanced BSTs → O(logn) instead of O(n) time for searching, inserting, and deleting
  - Insert into AVLs → use LL, LR, RR, RL rules with rotations
  - Worst case scenarios, have to do 2 rotations at each node times the tree height, still O(logn)
- Mutable variables
  - Mutable variables are surprisingly complex, overusing them can make programs difficult to run on parallel or multi-core hardware
  - (set! <variable> <expression>) → mutates variable to have the value of expression
  - (begin <expression> <expression> …) → Evaluates expressions from left to right. The value of the begin expression is the value of the last expression
- The danger of mutating variables
25/09/2022
- Worklist accumulators, part 1
- Worklist accumulators, part 2
- Worklist accumulators, part 3
  - Lost context accumulator: accumulators in recursive functions that change in the course of function calls
26/09/2022
- Worklist accumulators, part 4
  - In mutually recursive functions w/ accumulators, usually only one of the functions provides new values for each accumulator
- Worklist accumulators, part 5
  - To traverse an arbitrary-arity tree, we need a worklist accumulator
  - Depth-first traversal: go all the way down the leftmost branch to the end and then go across
  - Breadth-first traversal: travel a whole level of nodes before going down another level
  - Tail recursive traversal of an arbitrary-arity tree
    - Two accumulators
      - One keeps track of the result so far
      - One keeps track of all the children nodes we have seen but not visited (visited their parents) → worklist accumulator
- Worklist accumulators, part 6
- Worklist accumulators, part 7
  - Worklists use less stack space, lets you search nodes in whatever order you want (priority queue), enables A* search
- Graphs — introduction
  - Two ways graphs are different from arbitrary-arity trees
    - Can have cycles
    - Can have multiple arrows going to a single node
  - Acyclic graph: maintains only property 2
  - Directed: arrows go in only one direction
29/09/2022
- Graphs — constructing cyclic data
  - (shared [(<name> <expression>) …] <expression>) → construct cyclic data structures
- Graphs — construct cyclic data pt 2
- Graphs — templating
  - Template
    - Structural recursion (arbitrary-arity tree-like type comment)
    - Encapsulate w/ local (two functions operating on an arbitrary-arity tree)
    - Tail-recursive w/ worklist (operating on a large graph requires a lot of computation, tail-recursive with the arbitrary-arity tree would be nice to have worklist)
    - Context-preserving accumulator (visited nodes)
- More mutable variables
  - General SWE principle: If something needs not to change might change, make a local copy of it
29/09/22
- Graphs — HtDF example
- Macro: background
  - Used to build languages
  - Macros extend a language by specifying how to compile a new feature into existing features
  - Is itself implemented in the programming language, not an external tool
  - Macro hygiene
    - Each expansion stage gets its own variables
    - Thus variables are safe to use in macros
- What are macros
10/05/22
- Intro to macros
  - (define-syntax <macro name> (syntax-rules (<other keywords>) [(<macro expression>) (<expression>)] …))
  - (define-syntax-rule <macro name and parameters> <macro expression>)
  - A macro is an operation performed on the source code of a program before evaluation → Source code transformation
  - Evaluation procedure of a macro call expression
    - Evaluate the operator sub-expression, which evaluates to a macro
    - Call the macro procedure on the operand expressions without evaluating them first
    - Evaluate the expression returned from the macro procedure
  - Unline functions (values → values), macros take in expressions and outputs expressions
- Macro hygiene
  - Secretly renames local variables in macros with fresh names to avoid collision
  - Looks up variables used in macros where the macro is defined
- Intro to recursive macros
- Recursive macros
  - Macros can be recursive, but the base case must be one of the multiple patterns, not buried within one of the output patterns (this leads to infinite expansion since expressions do not get evaluated after there are none of the patterns left)
- Functions evaluate all operands first
- A thunk is a function that returns a zero-argument function that returns thunk’s argument
- Macros don’t evaluate their operands
10/24/22
- Data as code, code as data
- Modules: “cons”
- Modules: “memoization”