ShermanBlog

Home Assignments Martin Blog Sherman Blog Resources Project Discussion Group

Tues March 29

Objects!

  • Picture of the whiteboard: https://goo.gl/photos/ftxzTKzUtGGo57Ng9
  • Objects are procedures that take a message, and return a procedure that will do the action the messaged asked for.
  • Objects utilize a closure created at constructor time for their stateful data
  • Constructor procedures create objects.
  • The object itself returns a method procedure, based on its internal state and the message.

Git!

  • Fast introduction to the git version control system
  • Github is a service that hosts git repositories and adds nifty features; git is a tool to do version control
  • You can fork repositories in github to make your own copy
  • You can clone a repository, usually from github to your own computer.
  • You do all the work on your computer, and commit it
    • you can then push that work up your copy on github
  • Branches are an alternate dimension of the project folder
    • good practice for branches:
      • the master branch should always represent the modern, stable, working project. Focus on stable and working.
      • make a new branch to work on a new feature or bug
      • merge into master only when feature is complete
      • a github pull request is based on a branch- so new changes to that branch will be reflected in the pull request.
  • The base atoms of git are changes and commits.
  • Distributed github cheat sheets and stickers.

Exam 1 Study List You should be able to do the following things:

  • create recursive-process procedures to operate on number series, lists, and lists-of-lists.
  • create iterative-process procedures to operate on number series, lists, and lists-of-lists.
  • evaluate and report upon the space and time performance of the above things.
  • perform substitution model expansions on expressions involving recursions, higher-order functions, and functional composition.
  • use data abstraction, including creating and using constructors and selectors.
  • define and use higher-order procedures such as map, filter, and accumulate (foldl).
  • draw box-and-pointer diagrams for list constructions.
  • from box-and-pointer diagrams, access specific list elements using car, cdr, and compound selectors.
  • convert between lambda expressions and let expressions.
  • construct and evaluate expressions that use a composition of functions.
  • create and use predicate functions.

Tues Mar 1

  • Handed out solutions for ps1-3b. DO NOT DISTRIBUTE BEYOND THE CURRENT CLASS
  • Introduced PS4, the symbolic differentiator
  • Introduced the final project, and FP1
  • sample exam from Prof. Holly Yanco (and solutions)

Thurs Feb 25

  • Equality testing:
    • = is for numbers only
    • eq? eqv? test if the object in space is the same thing (literals always count as the same object)
    • equal? tests if content and structure for sameness, recursively if necessary
  • Skill check for Exam 1:
    • make box-and-pointer diagrams
    • be able to figure out code to get certain values from structures based on diagrams
  • Diagrams for deep reverse:

Thurs Feb 17

  • Exam 1 - Thursday, March 3, 2016
  • Activity: Lists and HOPs
  • Lists, and custom recursive functions to do stuff to them
  • Standard Higher Order Procedures
    • Accumulate (we've done this before)
      • reduces a list down to a single value
      • operator must take 2 parameters, a left and right
      • returns a single value
      • classic example: sum a list (accumulate + lst)
      • more real example: find maximum of a list (accumulate (lambda (a b) (if (> a b) a b)) lst)
    • Map
      • Transforms each item of a list through the operation, putting results in a new list
      • operator must take 1 parameter
      • returns a list of equal length as the input list
      • classic example: double everything (map (lambda (n) (* 2 n)) lst)
      • fun example: turn every item into a 1: (map (lambda (item) 1) lst)
    • Filter
      • Selects certain items from the list to be passed on to the result lists, others are ignored
      • operator must take 1 parameter, the item to test
      • operator must return #t or #f, where #t signals to include in the output list
      • returns a list of length <= original list
      • classic example: keep only odd numbers (filter odd? lst)
      • better example: keep only numbers evenly divisible by 3 (filter (lambda (num) (= (remainder num 3) 0)) lst)

Thurs Feb 11

  • Introduced homework ps2c- procedural abstraction, abstraction barriers, point to line to rectangle
  • Class activity: lambda, let, and environments
    • Biggest trick in part 3 - what frame does the square procedure point to?
    • Did part 1 solo, then pair-share, then instructor review
    • Did part 2 in pair-share
    • Part 3 divided into teams and tackled as small groups

Tues Feb 9

  • Reviewed
    • lambda's scope by means of parameters
    • let's scope by means of binding list
    • how the patterns match up- let and lambda do the same thing!
  • Environment Diagrams
    • Rules:
      • Whenever a procedure is evaluated a new frame is created for it.
        • When the new frame is created, the parameters' values are copied in as bindings
        • New frame copies the parent pointer of the procedure object
        • Frame will have the same parent as the procedure object
      • When lambda is evaluated it creates a new "procedure object"
        • Procedure object left circle: parameters and body
        • Procedure object right circle: pointer to parent frame - the frame where the lambda was evaluated
  • Environment diagram- Final Example of the Day
(define (make-inc n) (lambda (m) (+ m n)))
(define ++ (make-inc 1))
(++ 9)

Thurs Feb 4

  • Tail Recursion only works for ITERATIVE PROCESSES
  • Review cons, car, cdr
  • (2.1) Data abstraction and abstraction barriers
    • Pairs
    • Example: rational numbers (2.1.1)
  • lambda's body only is evaluated when that procedure is RUN
  • Accumulate - our first fully-fledged HOP
    • sum a list
    • find the biggest in a list

Tue Feb 2

  • Scope
    • Procedures are their own scope
      • Procedures look in their own scope for bindings first, and if they can't find it they look up to their parent's scope
      • This scope chain is the environment
      • Procedures get their context from their environment.
    • Bindings can be named by define, or by the name of parameters coming into the procedure
  • let
    • Let makes a local scope bubble
    • Let is really lambda, packaged with syntactic sugar for convenience
    • Let nicely lets you list names/expressions to bind in that scope
  • Higher Order Procedures
    • In scheme, procedures are "first class," meaning they can be passed as parameters and/or returned.
    • a "fully fledged" HOP can both accept procedures as parameters and return a procedure
    • Some procedures will take another procedure as a parameter.
    • Some procedures will return a procedure
    • Some procedures will do both.
  • Lists
    • cons- creates a new scheme type: a cons cell
      • cons cells have two values, one is the car one is the cdr
      • cons is the special form to create cons cells
      • car can extract the left-side value from a cons cell
      • cdr can extract the right-side value from a cons cell
    • If the cdr of a cons cell is another cons cell, you can make a list!

(cons 1 (cons 2 (cons 3 '()))) makes a list (list 1 2 3) makes the same list, much easier '(1 2 3) same list, even shorter-hand

Meeting 3: Thu Jan 26

  • "Hi, I'm Mark!"
  • In the past you've talked about recursive procedures, which is a procedure that calls itself
  • But there's so much more than that!
  • A recursive procedure may have different processes: recursive or iterative
    • Recursive Process
      • Has deferred operations: calculations that must wait for the next recursive call to finish (see factorial example above)
    • Iterative Process
      • No deferred operations. No expression ever has to wait for the recursion.
      • Often uses a helper function.
      • Captures the entire state of the calculation with arguments.
        • quick test: could you pause the recursion and not lose anything?
  • Tail Recursion
    • If the recursive call is in "tail position," Scheme will optimize it to not waste memory space.
    • Tail position means the last expression in the function. Yes, that includes the conditionals of if and cons

Meeting 2: Thu Jan 21

  • Dante is in class (if only the dry erase markers would cooperate...)
  • Zipping in 7-zip: Using 7-zip to create a tar.gz file for Bottlenose
  • Racket basics:
    • Prefix "+ 1 2" vs. infix "1 + 2" notation and parenthesis.
    • lambda vs. no lambda in definitions:
      • (define square (lambda (n) (* n n))
      • (define (square n) (* n n))
    • DrRacket:
      • The top section is for definitions
      • The bottom section is for interactions
      • Hit the "Run >" button whenever you change your definitions!
      • In the interactions window "ctrl + up arrow" will cycle through your previously entered interactions.
  • Substitution Model
    • A simple model for procedure applications, not necessarily how the interpreter actually works.
    • definitions:
      • (define (square x) (* x x))
      • (define (sum-of-squares x y) (+ (square x) (square y)))
      • (define (f a) (sum-of-squares (+ a 1) (* a 2)))
    • substitute to solve: (f 5)
      • Retrieve the body of "f":
        • (sum-of-squares (+ a 1) (* a 2))
      • Replace the formal parameter "a" by the argument "5":
        • (sum-of-squares (+ 5 1) (* 5 2))
        • (sum-of-squares 6 10)
      • Retrieve the body of "sum-of-squares" and replace the parameters with arguments:
        • (+ (square 6) (square 10))
      • Retrieve the body of "square" and replace the parameters with arguments:
        • (+ (* 6 6) (+ 10 10))
      • Solve:
        • (+ 36 100)
        • 136
  • cond (conditional)
    • Syntactic sugar for nested if
      • syntax: (if <predicate> <consequent> <alternative>)
      • "if <predicate> is true, do <consequent>. Otherwise, do <alternative>"
    • Predicate: a procedure that always returns #t (true) of #f (false)
      • (= a b)
      • (< a b)
      • (> a b)
      • (and <e1> ... <en>)
        • example: (define (and-example n) (and (> x 5) (< x 10)))
      • (or <e1> ... <en>)
        • example: (define (>= x y) (or (> x y) (= x y)))
      • (not <e>)
        • example: (define (>= x y) (not (< x y)))
    • else
      • A special symbol that can be used in place of the predicate in the final clause of a cond. It always evaluates to #t.
      • example: (define (abs x) (cond ((< x 0) (- x)) (else x)))
  • Recursion
    • When the evaluation of a rule involves invoking the rule itself.
    • example: factorial (n!)
      • (fact 4)
      • (* 4 (fact 3))
      • (* 4 (* 3 (fact 2)))
      • (* 4 (* 3 (* 2 (fact 1))))
      • (* 4 (* 3 (* 2 1)))
      • (* 4 (* 3 2))
      • (* 4 6)
      • 24
  • HOMEWORK:
    • ps1 due at 11:59pm on Monday, January 25.
    • Reading: 1.1 - 1.1.16 & 1.3.2

Meeting 1: Tue Jan 19

  • welcome
  • course website shortlink is bit.ly/oplspr16
  • “What is OPL?” poll:
    • individually write down three things that you think this course is about
    • pair with someone nearby and discuss
    • one of you submits: either:
      • via web at pollev.com/fredm
      • via texting FREDM to 37607, followed by your response