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.
(:youtube p9BileX32Rc:)

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”):
(:youtube tUj9UtP_4As:)

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