Home Assignments Lecture Blog Resources Project Discussion Group

All white board photos are hi-res; right-click and open in a new tab to view them.

Final Grade Distribution

  • 19 students on a 100-pt scale. B is centered at 77. Standard deviation is ~14; so A is centered at 91; C is centered at 63; D is centered at ~50.

Meeting 38: Wed May 4

Meeting 37: Mon May 2

  • while implementation
  • FPFlyer and FPCode
  • garbage collection:
    • (1) find data objects in a program that cannot be accessed in the future;
    • (2) reclaim the resources used by those objects. (cite: wikipedia)
  • stop-and-copy
  • mark-and-sweep
  • incremental methods

Meeting 36: Thu Apr 28

  • Echo360 lecture capture
  • Quiz 2 returned and discussed; average was 22 and stddev was 5.7
  • PS7 (Mapreduce) returned
  • Quick discussion of final project writeups (more next Monday)
  • Course evaluations completed
  • more on the metacircular evaluator (aka, baby Scheme)
  • how list-of-values enforces order of evaluation of operands
  • how let->lambda works (the other derived expressions example)

Meeting 35: Wed Apr 27

  • Echo360 lecture capture
  • more on the metacircular evaluator (aka, baby Scheme)
  • how to test that uml:and short-circuits (so you can test your implementation of uml:or)
  • derived expressions: cond->if

Meeting 34: Mon Apr 25

  • Echo360 lecture capture
  • more on the metacircular evaluator (aka, baby Scheme)
  • how baby-Scheme primitives are stored in the global environment
  • how mc-apply is used to evaluate a simple expression like (uml:+ 3 5)
  • constructing a procedure with uml:lambda
  • that the procedure representation includes 4 things: the tag procedure, a list of params, a list of the body, and the environment in which it was created
  • applying a compound/user procedure: that extend-environment creates a new frame where the bindings for the procedure parameters are stored
  • special forms uml:or and uml:and: how the short-circuiting is implemented
  • please do the first homework problem, implementing uml:or, before Wednesday

Meeting 33: Fri Apr 22

  • Quiz 2 administered

Meeting 32: Wed Apr 20

Meeting 31: Fri Apr 15

Meeting 30: Wed Apr 13

Meeting 29: Mon Apr 11

  • Echo360 lecture capture
  • went over Adventure Game problem set in detail -- we discussed what needs to be done for each problem.

Meeting 28: Fri Apr 8

  • adjusting homework due dates
    • PS7 due Mon Apr 11
    • PS8 due Wed Apr 13
    • FPE3 due Fri Apr 15
  • quiz 2 will be on Fri April 22, and will cover:
    • map filter reduce/accumulate
    • eq? eqv? equal? =
    • streams
    • modifying state (e.g., set!)
    • environment diagrams
    • mapreduce
  • (make-balance) environment diagram problem (see whiteboard photo below)
  • looked at http://www.cs.uml.edu/ecg/pub/uploads/OPLspr11/environment-diagrams.pdf
  • list of 6 fundamental object types in adventure game
  • PS walkthrough

Meeting 27: Wed Apr 6

  • big environment diagram of make-speaker and how ask extracts the lambda
  • inheritance in speaker vs. lecturer
  • initial walkthrough of adventure game PS code
  • made list of 6 fundamental object types

Meeting 26: Mon Apr 4

  • mapreduce fail
  • started OO

Meeting 25: Fri Apr 1

  • feedback on FPE1 turnins
  • three FPE1 demos
  • guidance for FPE2 -- see revised PS7
  • MR problem set
  • PS7 must be completed by Monday

Meeting 24: Wed Mar 30

  • mapreduce lecture 2 notes
  • inputs to mapper are KV pairs where keys are filename and vals are lines of input file (one line per KV pair)
  • MR example: find names of plays in which Shakespeare uses word 'forsooth'
  • MR example: wordcount (recap)
  • MR example: wordcount, but then find word with highest frequency
    • reduce stream of kvp words/counts with max fcn -- but this will perform reduction all on one computer
    • split up and tag pairs with first letter of word -- then can use ~26 processes for reduction
    • still have to go through that stream and pick out the highest count

Meeting 23: Mon Mar 28

Meeting 22: Fri Mar 25

  • environment diagrams and state
  • the balance and make-withdraw examples from SICP

Meeting 21: Wed Mar 23

Meeting 20: Mon Mar 21

  • Echo360 lecture capture (sorry no computer feed)
  • PS6 Final Project Exploration 1 discussion
  • streams are delayed lists
  • stream primitives: cons-stream, stream-car, stream-cdr
  • creating a stream of integers: stream-enumerate-interval
  • walking down a stream: stream-ref
  • transforming a stream: stream-map
  • filtering a stream: stream-filter
  • displaying a stream: stream-for-each and display-stream
  • memo-ization

Meeting 19: Fri Mar 11

Meeting 18: Wed Mar 9

  • Quiz 1

Meeting 17: Mon Mar 7
QUIZ REVIEW: you should be able to do...

  • convert cons-cell/list data structures among (a) Racket code to construct them, (b) their printed form, and (c) their equivalent box-and-pointer diagrams.
  • carry out expression evaluation, including in-line function construction (lambda) and application.
  • in recursive procedure definitions, be able to analyze and explain whether their evaluation will cause a recursive process or an iterative process.
  • when feasible, convert various traversal algorithms between iterative and recursive forms.
  • evaluate given recursive algorithms for their space and time complexity.
  • construct recursive and/or iterative procedures to perform list and tree traversals, including mappings and accumulations.
  • be able to use append when appropriate; e.g., to flatten a tree into a list, or to join two lists and make one longer one (rather than a list of two sublists).
  • construct and evaluate the performance of functions that perform mapping and accumulation.
  • demonstrate applications of higher-order functions: e.g., functions that evaluate to functions; functions that accept functions as parameters.
  • convert back and forth between expressions using let (which create bindings in a new, “more local” environment), and their equivalent using lambda.
  • demonstrate the use of functions to hold state as in closures; e.g., implementing equivalents for cons, car, and cdr using function construction (e.g., with lambda).

Meeting 16: Fri Mar 4

Meeting 15: Wed Mar 2

  • dotted-tail notation, and using it for expanded make-sum's (Attach:deriv-w-dotted.rkt)
  • four types of equality: =, equal?, eqv?, and eq?

Meeting 14: Mon Feb 28

Meeting 13: Fri Feb 25

  • Echo 360 lecture capture
  • PS4 is assigned
  • using transform-painter to rotate and mirror
  • superpose to put images on top of one another
  • beside and below, implemented using transform-painter and superpose
  • recursive images, using simplified right-split and then more complex example from problem set
  • demonstration of how to upload images to the wiki as part of PS4 assignment

Meeting 12: Wed Feb 23

  • Echo 360 lecture capture
  • Henderson picture language stuff
  • the four kinds of painters
  • vectors and segments
  • frames
  • transform-painter, which has as parameters the three vectors of a frame, and produces a procedure that accepts a painter-procedure and produces another one
  • Attach:painter-stuff.rkt

Meeting 11: Fri Feb 18

what is (fold-right / 1 (list 1 2 3)) ?
what is (fold-left / 1 (list 1 2 3) ?
  • enumerate->filter->map->accumulate signal flow concept (re: sum-odd-squares and list of even fib's)
  • enumerate-interval:
    (define (enumerate-interval low high)
      (if (> low high)
          (cons low (enumerate-interval (+ low 1) high))))
  • enumerate-tree (flatten) we did last time
    (define (sum-odd-squares tree)
      (accumulate +
                  (map square
                       (filter odd?
                               (enumerate-tree tree)))))

    (define (even-fibs n)
      (accumulate cons
                  (filter even?
                          (map fib
                               (enumerate-interval 0 n)))))

Meeting 10: Wed Feb 16

    (define (count-leaves x)
      (cond ((null? x) 0)  
            ((not (pair? x)) 1)
            (else (+ (count-leaves (car x))
                     (count-leaves (cdr x))))))
  • scale-tree
    (define (scale-tree tree factor)
      (cond ((null? tree) nil)
            ((not (pair? tree)) (* tree factor))
            (else (cons (scale-tree (car tree) factor)
                        (scale-tree (cdr tree) factor)))))
  • another implementation of scale-tree, using map:
    (define (scale-tree tree factor)
      (map (lambda (sub-tree)
             (if (pair? sub-tree)
                 (scale-tree sub-tree factor)
                 (* sub-tree factor)))
  • enumerate-tree (aka, flatten)
    (define (enumerate-tree tree)
      (cond ((null? tree) nil)
            ((not (pair? tree)) (list tree))
            (else (append (enumerate-tree (car tree))
                          (enumerate-tree (cdr tree))))))

Meeting 9: Mon Feb 14

  • length of a list (recursive and iterative forms)
  • cons'ing something to the head of a list keeps it a list (e.g., (cons 3 (list 4 5)) is '(3 4 5))
  • list makes things into lists, so (list (list 3 4) (list 5 6)) is '((3 4) (5 6))
  • append takes two lists and makes them into one longer list. E.g., (append (list 3 4) (list 5 6)) is '(3 4 5 6)
    • what happens with (append 3 4) ?
    • what happens with (append (list 3 4) 5) ?
    • draw the result of (append (list 3 4) 5)
  • append copies the input lists and make a new list (prove it)
  • Exercise 2.33:
    (define (append seq1 seq2)
      (accumulate cons <??> <??>))
    (define (length sequence)
      (accumulate <??> 0 sequence))

Meeting 8: Fri Feb 11

  • data abstraction:
    • an abstraction for cartesian coordinates (points)
      • using list as constructor and car and cadr as accessors
    • a rational number package
  • gcd function
  • abstraction barrier hierarchy
  • let as syntactic sugar for creating a new environment with additional bindings (like locals, but also different)
  • another try at cons/car/cdr with lambdas and message-passing
  • go over PS3 (Exercise 2.4)
  • Attach:meeting8.rkt -- example of recasting let as a lambda

Meeting 7: Wed Feb 9

  • map, filter, reduce
  • review: cons, car, cdr, list, quote
  • review: nth item of a list (iterative recursive procedure)
  • more things to do with lists: scale-list, incr-list, square-list
  • abstract this: map with arguments list and map-fcn
  • rebuilding a list testing for even?
  • abstracting this: filter with arguments list and predicate?
  • sum-list, prod-list
  • abstracting this: reduce with arguments list, binary-op, final-term
  • Attach:meeting7.rkt
  • PS3

Meeting 6: Mon Feb 7

  • OPL Mantras: define, Scheme evaluation rules, and closures
  • pairs; cons, car, cdr
  • lists and the list primitive
  • nth procedure for “cdr'ing down” a list
  • Scheme's nil is '()
  • box and pointer diagrams
  • quote and the quote character; quote is a special form
  • implementing pairs with procedures and closures
  • Attach:meeting6.rkt example code (from class)

Meeting 5: Fri Feb 4

  • Review of iterative recursion (using state variable) vs. recursive recursion, using fact as example.
  • when the tail call optimization can be made:
“An invocation of g in a procedure f is a tail call if, in the control path that leads to the invocation of g, the value of f is determined by the invocation of g.”
From Programming Languages: Application and Interpretation, Shriram Krishnamurthi, section 20.4, pp. 216 of PDF.
  • a taxonomy of functions:
    • first-order Functions are not values in the language. They can only be defined in a designated portion of the program, where they must be given names for use in the remainder of the program.
    • higher-order Functions can return other functions as values.
    • first-class Functions are values with all the rights of other values. In particular, they can be supplied as the value of arguments to functions, returned by functions as answers, and stored in data structures.
From PLAI (ibid.), pp 41–42
  • Closure: A closure is a first-class function with free variables that are bound in the lexical environment. (Thanks, Wikipedia.)
  • make-scale, a function that returns a function that scales its input
  • expnt in recursive implementation.

Meeting 4: Mon Jan 31

  • “normal” evaluation model (as compared to applicative order / the substitution model)
  • recursive procedures generating recursive processes (fact) or iterative processes (fact-iter)
  • tail-call optimization implements iterative recursions without building stack frames

Meeting 3: Fri Jan 28

  • more special forms: if, cond, and, or, and not. These don't necessarily obey the standard evaluation rule of “ eval all subexprs, then apply operator”
  • predicate is an expression that evaluates to true (#t) or false (#f)
  • “Scheme-isms”: use hyphen to separate multiple words in a symbol name (not underscore); use question-mark at the end of a symbol name to indicate a predicate
  • comment character is a semi-colon
  • structure of the if primitive: ( if <predicate> <if-true-consequent-expr> <if-false-consequent-expr> )
  • cond as syntactic sugar for nested ifs
  • define a procedure as syntactic sugar for binding a symbol to a proc object created with lambda
  • substitution model to illustrate applicative order (how Scheme works)
  • showing the debugger by clicking on the nested stop-sign
  • don't do the problem with the stepper tool—they've changed it and it's not relevant for our purposes now

Meeting 2: Wed Jan 26

  • please join the newsgroup (< half the class has joined so far)
  • PS1 handed out
  • Scheme rules of evaluation
  • primitive operators: + - * /; numbers
  • basic rule of evaluation
  • eval/apply cycle
  • define and the environment to bindings from symbols to values
  • lambda to create procedures
  • define used to bind a symbol name to a newly-created procedure
  • applying an anonymous procedure
  • special form of define for creating procedures

Meeting 1: Mon Jan 24

  • syllabus discussed
  • discussion of PL issues
  • course design with main features and grading weights (homeworks and projects are important)