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

Exam 1 was Fri Mar 4 Exam 2 will be Wed Apr 13

Recorded lectures link:

To view images larger: right-click and open in new tab.

Meeting 37: Fri Apr 22

  • Exam 2 returned (with answer key)
  • Project demo slots assigned
  • Project Milestone Release 2 is due tonight (see
  • stream-ref: walk down a stream a specified number of times, forcing the cdr that many times and then returning the car (in other words, picking out the nth item)
  • showing the stream in the REPL: forcing causes memoization
  • stream-map (map a proc to a single stream), add-streams, and stream-map-general (map and combine across multiple streams),
  • defining streams implicitly; e.g. the integers:
(define ones (cons-stream 1 ones))
(define integers
  (cons-stream 1 (add-streams ones integers)))
  • Fibonacci numbers:
(define fibs
    (cons-stream 1 (add-streams (stream-cdr fibs) fibs))))
  • in-class exercises: Attach:streams.pdf
  • Sieve of Eratosthenes (a third-century B.C. Alexandrian Greek philosopher):
(define (sieve stream)
    (stream-car stream)
    (sieve (stream-filter
             (lambda (x)
               (not (divisible? x (stream-car stream))))
             (stream-cdr stream)))))
(define primes (sieve (integers-starting-from 2)))

Meeting 36: Wed Apr 20
introduction to streams

  • lazy evaluation is good: only do work when someone cares about the result
  • all your life you've been doing “strict” or “eager” evaluation
  • practical example of lazy programming: infinitely-scrolling web pages. Only grab the info when the user actually wants it displayed
  • another example: network loading of media objects. Start playing the movie or audio while the rest of it loads
  • lazy programming paradigm lets you cleanly separate out the generator (e.g. network stream) from the consumer (codec that actually creates the video image or audio)
  • thus allows elegance of expression of computational idea and efficiency of execution
  • key concept: wrapping deferred computation in a promise or “IOU” (a closure-object) called a “thunk”
  • the thunk consists of a procedure application with parameters and a environment-chain in which to eval the params
  • delay creates the thunk
  • it can be cashed in with force
  • streams are delayed lists. New primitives: cons-stream, stream-car, stream-cdr, the-empty-stream, and empty-stream?
  • cons-stream uses cons to combine the first param with a promise made from the second
  • stream-car is car
  • stream-cdr does a force on the cdr
  • examples: enumerate-interval recursive procedure to generate list of numbers, then using filter to yield primes. This is inefficient because we generate (and carry around) a huge quantity of numbers that will fail the prime? test. Without lazy, we would write code that generates one number at a time and immediately tests it (the consumer), interleaving these two functions.
  • with lazy, we can write stream-enumerate-interval and use stream-filter and it's efficient
  • “memo-ization” is caching the computed result in the forced-promise object for later reuse. This is necessary for efficiency (otherwise expensive computations will be redone frequently)
  • an infinite stream of the natural numbers, using a recursion that never terminates:
(define (nums-starting-at z)
  (cons-stream z
               (nums-starting-at (+ z 1))))

(define nats (nums-starting-at 1))
  • display-stream

Meeting 35: Fri Apr 15 Mark covers most of the lecture

  • What is a special form?
    • a feature that doesn't follow the regular procedure evaluation rules
  • How do we make a special form?
    • It needs to be added to eval's dispatch table (the big cond)
  • So let's talk about for
    • Read the damn spec.
    • Read it again. I'll wait.
  • for is a special form
    • so it will be implemented as a tagged list, with a tag, and a row mc-eval that knows how to dispatch to the procedure to execute it.
    • the first parameter is a list of properties- the counter variable, the start value, and the stop value, known as <var>, <exp1>, <exp2>
    • Also takes a body, which is an expression that mc-eval can evaluate directly.
    • You will need the counter variable to be accessible from inside the body, which means the current value of the counter must be accessible as a variable look up in the mc-eval evaluation.

Meeting 34: Wed Apr 13

  • Exam 2 administered

'Meeting 33: Mon Apr 11

  • more metacircular evaluator

Meeting 32: Fri Apr 8

  • introduction to metacircular evaluator

Meeting 31: Wed Apr 6

Meeting 30: Mon Apr 4

  • objects, closures and environments
  • brief intro to mc-eval

Meeting 29: Fri Apr 1

  • FP4 Project Proposal due noon Wed Apr 6
  • new material: the meta-circular evaluator (implementing scheme in scheme)
  • the eval-apply loop (and yin-yang symbol)
  • many systems have interpreters embedded in them
  • in-class exercise: Attach:standard-or-not.pdf

Meeting 28: Wed Mar 30

  • Mark Sherman guest lecture on GitHub

Meeting 27: Mon Mar 28

  • there are 5 weeks to go
  • core curriculum content is:
    • objects, environments, and closures
    • streams
    • the metacircular evaluator
  • in parallel to this, you will be working on projects
    • FP4 Proposal due next Mon (Apr 4)
    • checkpoint 1 Wed Apr 13
    • checkpoint 2 Wed Apr 20
    • final projects Wed Apr 27 and Fri Apr 29
  • on Wed, we will go over how to use GitHub collaboratively (and set up rest of project work)
  • today: closures/objects & environment diagrams
  • begin statement
  • the evil (but necessary for state modification) set! statement
  • non-encapsulated, write-only, and fully-implemented “bank balance” closures Attach:mar28.rkt

Meeting 26: Fri Mar 25

  • discussion of PS5 type systems:
  • rectangular and polar representations of complex numbers
  • constructors, accessors, and selectors for these
  • either rectangular or polar underlying representation may be used
  • type-tag and contents procedures for unpacking a tagged data type
  • concluded with a walk-through of the apply-generic procedure
  • system can't add/sub/mul/div disparate types!
  • also discussed dot-syntax for making procs of arbitrary num of args:
variable after the dot is bound to a list of such args (e.g. in apply-generic procedure)
  • understanding how apply-generic can add objects of same type
  • book discusses three ways of organizing type systems:
    • generic operations with explicit dispatch,
    • data-directed (the apply-generic system we're using), and
    • message-passing.
Explicit dispatch
  • Ex. 2.77, about adding complex number selectors to the complex number type (problem p2 in the PS).
  • Ex. 2.78, about updating scheme-number to use Scheme's underlying numerics (problem p3 in the PS).
  • Ex. 2.79, about defining an equality predicate (problem p4 in the PS).
  • Type coercion — Section 2.5.2, “Combining Data of Different Types”
Ex. 2.81, about type coercion (p5.rkt).
Important note: See for put-coercion, get-coercion, and other updates to the starter code.

Meeting 25: Wed Mar 23

  • PS5 now due Sun Mar 27
  • in-class exercise: Attach:type-sys-rect.pdf
  • understanding how the constructor for the complex number type works

Meeting 24: Mon Mar 21

Meeting 23: Fri Mar 11

Meeting 22: Wed Mar 9

Meeting 21: Mon Mar 7

  • guest lecturer Mark Sherman
  • FP1 discussed and assigned

Meeting 20: Fri Mar 4

  • Exam 1

Meeting 19: Wed Mar 2

  • you may bring 1 sheet of hand-written notes on 8.5x11" paper to exam (turn in with exam)
  • in-class exercises: eq? eqv? equal?
  • writing a definition of eq?
  • memq and member

Meeting 18: Mon Feb 29

  • solutions for PS1 through PS3b handed out—do not distribute beyond classmates this semester
  • sample exam from Prof. Holly Yanco (and solutions)
  • FP1 posted; will be due latter half of next week
  • PS4 on symbolic differentiator due Tue Mar 8
  • History of Computer Algebra Systems (wikipedia)
  • in-class exercise: review of differentiation
  • introduction to recursive expression evaluation (Attach:deriv.rkt)

Meeting 17: Fri Feb 26

  • PS3c and PS3d due Tue Mar 1
  • challenge problem 1: write last – returns the last item of a list
  • challenge problem 2: write flatten – takes a tree and returns list of just the leaves
  • next problem set is expression evaluator
  • final projects starting week after next
  • (pair? '()) is #f; (null? '()) is #t
empty-list is not a pair
make sure to use null? to test for empty-list

Meeting 16: Wed Feb 24

  • in-class exercises: nth, length, and last
  • a tree is a list of lists (where each sublist may itself contain sublists)
  • trees: count-leaves

Meeting 15: Mon Feb 22

  • cons of an element plus a list makes a longer list
  • writing length (recursively and iteratively)
  • what happens if you cons two lists together?
  • writing append (concatenate two lists into one longer list)

Meeting 14: Fri Feb 19

  • PS3a due Thu Feb 25
  • definitions for map and filter
  • fold (aka accumulate and reduce)
recursively unpacks list, applying operation to successive pairs from right-to-left
examples using + and *
  • definition:
(define (accumulate op initial sequence)
  (if (null? sequence)
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))
  • in-class exercises: accumulate, reduce, fold
  • substitution model for computing (accumulate + 0 '(1 2 3))
  • accumulate using lists: use it to filter a list for even numbers!

Meeting 13: Wed Feb 17

  • we are at the 1/3rd mark of the semester, and the pace will be picking up
  • map / filter / accumulate: the powerful abstractions of functional programming
(“reduce” and ”fold” are synonyms for accumulate)
  • in-class exercises: map and filter
  • PS3b will be out later today; plan 4 to 8 hours working on it

Meeting 12: Tue Feb 16

  • Exam 1 is Fri Mar 4
  • PS3a due Thu Feb 18
  • continuing in-class exercises: cons, car, cdr, and lists
  • recursive and iterative procedures to process numeric lists

Meeting 11: Fri Feb 12

  • no class Monday (Tuesday instead)
  • PS2c now due Mon Feb 15; PS3a due Thu Feb 18
  • bundling objects together: cons, car, and cdr
  • making lists with cons
  • making lists with list
  • building abstractions with data (intro to chapter 2)
  • in-class exercises: cons, car, cdr, and lists
  • example: geom-square abstraction

Meeting 10: Wed Feb 10

  • PS2c due Sun Feb 14; PS3a due Tue Feb 16
  • full method for drawing environments including double-circle representation of procedures
(from Section 3.2 of the text)

Meeting 9: Mon Feb 8

The three links above jump right to the beginning of each conversation in the YouTube video.

Meeting 8: Fri Feb 5

  • continuing discussion of higher-order procedures (procedures as parameters), and parameterizing sums-of-series (or products-of-series)
  • first-order functions: procedures as return values of other procedures
    • with constants as params
    • accepting a procedure as a param and producing a new procedure
  • environment frame and procedures diagram from last 10 mins of lecture (“closures”):

Meeting 7: Wed Feb 3

  • PS2a was due last night – nearly everyone completed it
if you didn't, come to my office hours and catch up
  • we're working on PS2b now (due Tue Feb 9)
  • higher order procedures -- using (sum term a next b))
  • iterative form also

Meeting 6: Mon Feb 1

  • office hours posted for Fred and Yang
  • PS2a is due Tue Feb 2
  • higher order procedures (HOPs): procedures as arguments
procedure as first-class object: the language supports using procedures in all ways as other objects; i.e.: as arguments, return values, and being bound to from a variable (symbol) name.
  • Attach:sequences.pdf
  • abstracting combiner, successor, and term-transformation functions as parameters of a general-purpose numeric sequence function

Meeting 5: Fri Jan 29

recursive recursion creates a chain of environment frames
iterative recursion reuses the bindings in the existing frame
  • you need state variables to accomplish iterative recursion

Meeting 4: Wed Jan 27

  • any PS1 questions?
  • make sure to check the autograde result before considering yourself done
  • Intro to the Substitution Model of evaluation
  • Using the substitution model to carry out (fact 5) Attach:subst-model-factorial.pdf
  • Recursive definition vs. recursive process
  • Recursive vs. iterative factorial (including helper functions)

Meeting 3: Mon Jan 25

  • you should not put statements into the .rkt source code; e.g. the following will fail:
     ;; exercise 1: procedure to square its argument
     ;; make sure to use the lambda formulation
     (define square (lambda (n) (* n n))
     (square 25)
instead, evaluate statements in the REPL
  • finishing worksheet:
    • predicates
    • if expr
    • booleans
  • alternate use of define for procedure construction
  • compound procedures: sum-of-squares and "(f a)" from text
  • Substitution Model for procedure application: “To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.”
    • do it for (f 5)
  • Introduction to recursion: factorial definition (defined in terms of itself)
    • base case
    • recursive case
  • cond is as described in the book
  • PS1 is due Tuesday before midnight

Meeting 2: Fri Jan 22

  • introduction to Bottlenose and PS0 (due Sunday before midnight)
  • OPL in-class exercises pdf
basic expressions
What is (square) ?
big discussion of symbols:

Meeting 1: Wed Jan 20

  • 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:
  • discussion of course goals
  • introduction to Scheme
  • atoms: numbers (integers; rational nums), procedures
  • lists
  • standard evaluation rule: eval first thing (which must yield a procedure-object), apply it to values of remaining things (evaluate them before applying the procedure-object to them)
  • eval of + is a procedure object
  • eval of (+ 2 3) is 5
  • eval of (+) is 0 (additive identity); eval of (*) is 1
  • define creates a symbol-name that binds to an object-value in an environment
Must have special eval rule because symbol can't be evaluated if it doesn't exist yet
  • lambda takes two params (list of args; body-expression) and creates a procedure-object
Also uses special eval rules
Edit - History - Print - Recent Changes - Search
Page last modified on April 22, 2016, at 03:38 PM