Home Assignments Lecture Blog Resources Project Discussion Group

Exam 1 is Mon Oct 20
Exam 2 is Mon Nov 17
Final is Wed Dec 17 at 8a

Echo360 lecture recordings are at

Whiteboard photos are at

Final Exam Results
85 points were available. Mean was ~54. 73 students sat the exam.


Below is distribution of people's work on the problem sets. Max 1000.

Study notes for Final exam: Attach:opl-body-of-knowledge-fall2014.txt

Meeting 40, Wed Dec 10

  • Project demos, part 2, in 3rd Floor Elevator Lobby

Meeting 39, Mon Dec 8

  • Project demos, part 1, in 3rd Floor Elevator Lobby

Meeting 38, Fri Dec 5
About projects and presentations/demos

  • please have your Project stubbed in by Sunday night
  • all project web pages are due 8a Monday morning
  • project demonstrations will be held in CS Dept 3rd Floor Elevator Lobby
  • bring your laptop running your code to your presentation (if neither partner has a laptop—arrange to share one with a classmate)
  • bring one printed copy of your web page to your demo
    • prepare to present your project in about 3 minutes
  • attendance at your presentation is mandatory
  • attendance at demonstrations on the day you're not presenting is optional

About final exam

  • there will be check-boxes to replace Exam 1 and/or Exam 2 scores with score on Final
  • you may bring 3 sheets of double-sided handwritten notes to the final
  • partial credit will be awarded on most if not all problems
  • all Exam 1 and Exam 2 material, plus:

Today's material

  • procedure application for compound procedures
  • let->combination

Course evaluations

Meeting 37, Wed Dec 3

Meeting 36, Mon Dec 1

Meeting 35, Mon Nov 24

Meeting 34, Fri Nov 21

Meeting 33, Wed Nov 19

  • introducing streams (Section 3.5 of book)
  • after class, PS8 was posted, due Wed 11/26

Meeting 32, Mon Nov 17

  • Exam 2 administered

Meeting 31, Fri Nov 14

  • Exam stuff
    • PS5 and PS6 solutions will be mailed to newsgroup
    • They are password-protected and the password will be given in lecture
    • You are allowed one 8.5x11" page of handwritten notes (double-sided OK)
  • OPL Final project proposal presentations

Meeting 30, Wed Nov 12
Exam 2 review:

  • equivalence of let and lambda; that let is syntactic sugar for lambda (Section 1.3.2, “Using let to create local variables”)
    • You should be able to translate from let expressions to their equivalent lambda expressions
    • and vice-versa
    • and for nested let's / lambda's.
  • equality testing via eq? (same object), eqv? (individual items having same value, tested with = for numbers or eq? for other things), and equal? (recursively testing structures using eqv?)
    • numeric equality (= operator) is defined as:
      “An inexact number is numerically equal to an exact number when the exact coercion of the inexact number is the exact number. Also, 0.0 and -0.0 are numerically equal, but +nan.0 is not numerically equal to itself.”
    • symbols are eq? to themselves; i.e., (eq? 'foo 'foo) is #t.
    • there is only one empty list; i.e., (eq? '() '()) is #t.
    • given various objects, you should be able to say whether they are eq?, eqv?, and/or equal? to each other.
  • the symbolic differentiation problem set—how it works
  • the type systems problem set—how it works

Meeting 29, Mon Nov 10

Meeting 28, Fri Nov 7

  • discussion of simple-oo code
  • super brief into to adventure game PS

Meeting 27, Wed Nov 5

  • Exam 1 handed back; average was ~22. Results are compressed at the high end—max score was 36, but 6 extra credit points were available
  • went over fold problem
  • continuing discussion of environments/frames, procedure creation, and closures

Meeting 26, Mon Nov 3

Meeting 25, Fri Oct 31

  • “Type Systems - The Good, Bad and Ugly” by Paul Snively and Amanda Laucher

Meeting 24, Wed Oct 29 Continuing discussion of type systems.

  • 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
  • Type coercion — Section 2.5.2, “Combining Data of Different Types”
  • Let's understand Ex. 2.81, about type coercion (p5.rkt).
Important note: You have to copy in the new version of the apply-generic procedure, and create global bindings (define put-coercion put) and (define get-coercion get).
  • Towers of types.

Meeting 23, Mon Oct 27 Continuing discussion of type systems.

  • Let's understand Ex. 2.77, about adding complex number selectors to the complex number type (problem p2 in the PS).
  • Let's understand Ex. 2.78, about updating scheme-number to use Scheme's underlying numerics (problem p3 in the PS).
  • Let's understand Ex. 2.79, about defining an equality predicate (problem p4 in the PS).

Meeting 22, Fri Oct 24

  • Section 2.4 of text, “Multiple Representations for Abstract Data”
  • adding and multiplying complex numbers—use rectangular form for add/subtract; polar form for multiply/divide

Meeting 21, Wed Oct 22

Meeting 20, Mon Oct 20

  • Exam 1 administered

Meeting 19, Fri Oct 17

  • about FPE1—see my newsgroup post and discussion in class of sample work
  • deep-reverse
  • blues-sale
  • PS4 and anything else for exam

Meeting 18, Wed Oct 15

  • PS2 PS3 PS4 answers presented

Meeting 17, Fri Oct 10

Meeting 16, Wed Oct 8

Meeting 15, Mon Oct 6

  • bucket -- operation changes depending on what the operand is -- see solution at 19:00 mark of the lecture recording.
  • flip functions and function composition
  • cdDB -- restock and others

Meeting 14, Fri Oct 3

  • examples of using cdDB:
(load "freds-db.rkt")
(map title cdDB)
(titles-in-stock cdDB)
(titles-by "The Beatles" cdDB)
(copies-in-stock "Revolver" "The Beatles" cdDB)
(set! cdDB (restock "Revolver" 10 cdDB))
(copies-in-stock "Revolver" "The Beatles" cdDB)
(carry-cd? "The White Album" "The Beatles" cdDB)
(carry-cd? "Help!" "The Beatles" cdDB)
(blues-sale cdDB)
  • accumulate, foldr, and reduce are synonyms
  • they take a list, a binary operator, and an initial value and pairwise apply the binary op to the head of the list and the recursive result
  • let's look at foldl
  • some things you can do with accumulation/reduction/folding
    • sum up the numbers in a list
    • make a product of all #s in a list
    • summarize all of the even numbers in a list
    • rebuild a list in new ways (using cons as the binary op)
  • tree-manip is like a tree version of fold

Meeting 13, Wed Oct 1

  • data abstraction, constructors and selectors
“Data abstraction is a methodology that enables us to isolate how a compound data object is used from the details of how it is constructed from more primitive data objects.”
  • do not violate the abstraction barrier
    • in other words, use selectors to pick apart compound objects and constructors to build them back up again
    • cons, list and the like should only be in constructors
    • car, cadr etc. should only be in selectors
  • first is a synonym for car, second for cadr, etc.
  • point and line abstractions; midpoint function
  • building point objects using lambdas/message-passing
  • look at CDDB problem in PS

Meeting 12, Mon Sep 29

Meeting 11, Fri Sep 26

  • let is lambda, and closures

Meeting 10, Wed Sep 24

  • three cons/list, printed form, and box-and-pointer test items
  • recap of recursion: base case, recursive case, invariants
  • recap of append
  • map filter accumulate
  • lambda and closures and let

Meeting 9, Mon Sep 22

  • PS3a extended until Friday
  • we left off with scale-list
  • let's look at properties of recursion:
    • base case
    • recursive case
    • invariants — what's always true
    • state variable(s) (with iterative recursions)
  • length -- recursive and iterative
  • last
  • append

Meeting 8, Fri Sep 19

  • introducing our 2nd TA: Peng Hou. Office hours: Mon 2p to 3:30p.
  • TAs are grading PS2 now
  • please give yourself more than one session to complete homework
  • please try your best to solve problems before looking up answers
  • recursive and iterative sum-nat (simulated test problems)
  • list primitives: cons, car, cdr, list, and null?
  • What is (cons 1 (list 2 3 4)) versus (cons (list 1 2 3) 4) ?
  • sum-list
  • scale-list

Meeting 7, Wed Sep 17

  • Fred's office hours: W 2p in Olsen 208, R 2p in Olney 524, F 1p in Olsen 308 (1 hr each). Please confirm before coming if possible.
  • issues with PS2?
  • let's do exercise 1.11 together
  • lists -- cons, car, and cdr
  • making a list with list
  • summing up a list
  • scaling a list
  • Assignment 3 is posted; due next Weds https://grader.cs.uml.edu/assignments/385

Meeting 6, Mon Sep 15

  • two versions of expt
  • what is tail recursion?
“One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ‘looping constructs’ such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar. ”
  • which expt is tail-recursive?
  • sum-integers and sum-cubes
  • let's abstract that

Meeting 5, Fri Sep 12

  • polls on evaluation questions (these are sample test questions)
  • let's look at Eric's recursive square example:
 (define (square-r n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (square-r (- n 1))
                 (- n 1)))))
Does it generate a recursive process?
  • Re-write it to generate an iterative process.
  • passing functions to functions

Meeting 4, Wed Sep 10

  • Exam 1 is Mon Oct 20; Exam 2 is Mon Nov 17
  • more on iterative vs. recursive processes and substitution model
    • reviewing substitution model for two versions of factorial
    • exercise 1.9 in class
  • demo of Racket development and testing best-practices
  • go over PS1 (volunteers?)
  • PS2 Iteration vs. Recursion and Higher Order Procedures assigned, due Wed 9/15

Meeting 3, Mon Sep 8

  • fire alarm
  • TA: Yen-Fu ("Edward") Luo, edwardluoopl@gmail.com. Office hours: Tue/Thu 12:30p – 2:00p.
  • what is a predicate?
Definition: “A procedure (or function) that returns true or false.”
by convention, the name of a predicate ends with a question-mark — e.g., even?, odd?, symbol?
  • numeric predicates: =, <, >
  • how to use cond
  • cond is syntactic sugar for nested if's
(define (die n)
  (cond ( (= (remainder n 3) 1) 'a )
        ( (= (remainder n 3) 2) 'wizard-type )
        (else 'sorry-youre-dead)))
  • and and or exist, and have special evaluation rules (they short-circuit)
AND short-circuit [no longer evaluates the remaining] as soon as it encounters a false, and OR as soon as it finds one that's true.
  • not inverts boolean value. Normal evaluation rules apply. Even though it's a procedure that produces a true/false output, it's not considered a predicate because it's not answering a question about its input.
  • discussion of symbols—
    • naming is done all lower-case with dashes as word separators
    • symbol? tests if a thing is a symbol
    • symbols are fundamental objects, like numbers and procedures and booleans
    • procedures can return symbols
  • more on iterative vs. recursive processes
    • reviewing substitution model for two versions of factorial
  • PS1 Introduction to Scheme is due Wed 9/8

Meeting 2, Fri Sep 5

  • introducing our TA: Yen-Fu Luo !
  • use group for discussion — presently, 62/81 have joined
  • Bottlenose — you must proactively request account — 60/81 are onboard
  • class policies
  • Scheme numbers — exact (ints, rats, arbitrarily large ints) and inexact (floats)
  • returning to expressions — (= 3 3), (define foo 3), (lambda (n) (* n n)
  • if expr — often used w/o side effects, meaning, it returns a value and doesn't “do stuff”
  • our first recursion: factorial (recursive process)
  • our second recursion: factorial (iterative process)
  • PS1 Introduction to Scheme due Wednesday
What is the value of (lambda (n) (* n n))?
What is the value of (define foo 3)?

Meeting 1, Wed Sep 3

  • what is OPL (discussion)?
  • introduction to Scheme
    • everything is an expression
    • some basic data types: numbers, symbols, booleans (there are also strings)
    • (+ 3 4) means apply the + procedure to params 3 and 4
    • + is a procedure
    • we can bind stuff to symbols, e.g. (define foo 3)
    • we can make procedures, e.g. (lambda (n) (+ n 1)) increments its arg
    • we can create a procedure and immediately apply it, e.g. ((lambda (n) (+ n 1)) 3) is 4
    • we can name procedures by binding symbols to them, e.g. (define inc (lambda (n) (+ n 1))
    • if is an expression; e.g. (if #f 3 4) is 4
  • notes from lecture:
Evaluation rules of scheme:

evaluate the first thing, apply to the values of the rest of them.


DEFINE take the second thing as the name of a symbol, and bind it to the
value of the third thing.

LAMBDA -- take a list of params and an expression, and create a procedure
object with these two things.

ENVIRONMENT -- place where symbols are bound to objects

datatypes --- numbers, bools