Recent Changes - Search:
ECG Home

GitHub

People

Publications

Calendar

Projects

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

HOWTOs

edit SideBar

LectureBlog

Home Assignments Lecture Blog Resources Project Discussion Group

Meeting 25 – Tue Dec 1

The Metacircular Evaluator!

  • eval-apply loop
  • eval as a big cond statement, testing special forms and then finally using apply for the default case of applying a procedure to its args
  • need for env context for eval
  • apply and its way of constructing args as a list, often recursing into more evals
  • how primitive procedures are implemented – populating the-global-environment with bindings, so ultimately they are just variable lookups
  • defining a symbol, which extends the environment
  • running the MC evaluator in Scheme (demo)
  • don't say (uml:define 'foo 5) – the quote confuses it – just do (uml:define foo 5)
  • looking at the environment objects in printed form (lists of symbols and the things they are bound to)
  • PS10 handed out

Meeting 24 – Tue Nov 24

  • went over FPProp
  • list of topics from the semester:
    • objects/state/closures
    • abstraction "barriers" / layers (everyone should do this)
    • map / filter / reduce (aka accumulate)
    • streams
    • recursion
      • tail recursion
      • iteration using recursion (looping over a state variable)
    • symbolic differentiation (more broadly -- symbolic processing)
    • data types, tagged data, data-directed programming
    • functions and composition of functions

Meeting 23 – Thu Nov 19

  • how to do real-part of a complex number
  • type coercion

Meeting 22 – Tue Nov 17

  • apply-generic and the type system

Meeting 21 – Thu Nov 12

  • intro to final projects

Meeting 20 – Tue Nov 10

  • more mapreduce

Meeting 19 – Thu Nov 5

Meeting 18 – Tue Nov 3

  • mapreduce ii presented by fred
  • working through the lab exercises

Meeting 17 – Thu Oct 29

  • mapreduce i presentation

Meeting 16 – Tue Oct 27

  • oCaml presentation

Meeting 15 – Thu Oct 22

  • hand back PS4 answers and Quiz 1 answers
  • PS6 due
  • PS6 FPE1 due next Thurs (not Tue)
  • streams & PS7
    • streams are delayed lists
    • stream-enumerate-interval, stream-map, stream-filter
    • cons-stream, stream-car, stream-cdr
    • delay and force
    • infinite streams: ones, integers, integers in terms of ones
    • “memo-ization” with memo-proc

Meeting 14 – Tue Oct 20

Meeting 13 – Thu Oct 15

  • environment diagrams, balance
  • make-speaker and starting to do ask

Meeting 12 – Tue Oct 13

  • quiz 1

Meeting 11 – Thu Oct 8

  • count-leaves as accumulation
  • quiz review
  • discussed exercise 2.58b, on parsing with precedence. did not solve it.

Meeting 10 – Tue Oct 6

  • Quiz 1 is Tue Oct 13
  • symbolic differentiation PS

Meeting 9 – Thu Oct 1

Henderson Picture Language!

  • vectors and segments
  • frames
  • the four painters: number->painter, segments->painter, load-painter, procedure->painter
  • transform-painter and shrink-to-upper-right
  • rotate90 with transform-painter and frames
  • beside and above
  • up-split recursion

Meeting 8 – Tue Sep 29

  • count-leaves
  • sum-odd-squares and even-fibs
  • signal-flow diagrams for the two procedures
  • enumerate-interval and enumerate-tree (aka, flatten-tree)
  • accumulate (aka, reduce)
  • redoing sum-odd-squares and even-fibs as accumulations
  • do list-fib-squares and product-of-squares-of-odd-elements as accumulations
  • examples from class

Meeting 7 – Thu Sep 24

  • Church numerals
  • map and filter
  • trees are lists of lists
  • scale-tree
  • pair? and list?

Meeting 6 – Tue Sep 22

Lists!

  • length
  • iterative length
  • list-ref or nth (iterative and recursive are the same!)
  • append and reverse (spent lots of time on these; also looked at things like (append '(1 2) 3))
  • idea of “cdr'ing down” a list
  • quote suppresses evaluation; (list 1 2 3) is equivalent to '(1 2 3)
  • scale-list
  • box-and-pointer diagrams for the above and things like:
    (cons 1 (cons 2 3))
    (list 1 (cons 2 3))
    (cons '(1 2) 3)
    (append '(1 2) 3)
  • code from today: Attach:append-reverse.ss
  • next: map, filter, and trees
  • for next time through: append and reverse are complex; do scale-list first

Meeting 5 – Thu Sep 17

  • data abstraction / abstraction barrier, as applies to make-rat, numer, and denom
  • implementation of add-rat
  • cons, car, and cdr primitives and their use in the rat system
  • with Scheme you're constantly creating cons cells and letting them evaporate; it's offensive to some but also freeing and powerful
  • how the rat system points in the direction of OO programming (constructors and selectors), but doesn't fully get there because the "methods" are not bundled with the data structures
  • Scheme is not type-safe; if you care about type, build a type system (we will do that)
  • procedure-closure and dispatch method of building cons/car/cdr
  • mathematical definition of closure (vs. functional closure)
  • box-and-pointer diagrams
  • definition of nil as (define nil '())
  • nested lists
  • immutability of cons cells in PLT 4.x; separate, parallel implementation of mutable pairs (mcons, mcar, and mcdr)
  • using mutability to create a circular list
  • live buffer history

Meeting 4 – Tue Sep 15

  • internal procedure definitions with sqrt-iter (pp. 29–30) and lexical scoping
  • procedures as arguments, using pi-sum example (pp. 57–58)
  • lambda as let, motivated by f(x, y) example (pp 63–64)
rewrite this using lambda's

Meeting 3 – Thu Sep 10

  • first problem from PS2 in class (iterative and recursive processes for inc and dec)
  • fibonacci and its recursive and iterative forms
  • exponential growth (in space) based on golden ratio
  • 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

Meeting 2 – Tue Sep 8

  • SchemeRulesOfEvaluation
  • 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”
  • 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) vs. lazy evaluation with normal order
  • recursive procedures generating recursive processes (fact) or iterative processes (fact-iter)
  • tail-call optimization implements iterative recursions without building stack frames
  • showing the debugger by clicking on the nested stop-sign

Meeting 1 – Thu Sep 3

  • the 2 types of prog lang classes
  • history of this class
  • why we are studying these ideas: they are present in modern lang's
  • the recursive evaluation rule
  • define special form
  • lambda special form
right-click and view to enlarge
Edit - History - Print - Recent Changes - Search
Page last modified on December 03, 2009, at 12:18 PM