Recent Changes - Search:
ECG Home






Fall 2017

Older Courses

Spring 2017

Fall 2016

Spring 2016

Fall 2015

Spring 2015

Fall 2014

Spring 2014

Fall 2013

Spring 2013

Fall 2012

Spring 2012

Fall 2011

Spring 2011

Fall 2010

Spring 2010

Fall 2009

Spring 2009

Fall 2008

Spring 2008

Fall 2007


edit SideBar


Home Assignments Martin Blog Sherman Blog Resources Project Discussion Group

Tues March 29


  • Picture of the whiteboard:
  • 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.


  • 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
    • 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
  • “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
      • via texting FREDM to 37607, followed by your response
Edit - History - Print - Recent Changes - Search
Page last modified on March 29, 2016, at 09:20 PM