# LectureBlog

Home Assignments Lecture Blog Resources Project Discussion Group

**All lectures may be reviewed using the Echo360 system:http://echo360.uml.edu/martin2014/orgprogrammingspring.html**

*Note: Right-click on any image to open it in hi-res.*

**Meeting 39: Wed Apr 30**

**Meeting 38: Mon Apr 28**

- derived expressions;
`cond`

and`let`

- started thinking through
`dotimes`

**Meeting 37: Fri Apr 25**

- more meta-circular evaluator:

`lambda`

, primitive vs. compound procedure representation,
`apply`

, `extend-environment`

, `eval-sequence`

- examples of new control structures:
`dotimes`

,`until`

- next time: derived expressions:
`cond`

and`let`

- PS10 extended until Sun May 4

**Meeting 36: Wed Apr 23**

- Final project presentations, part 2: http://bit.ly/oplspr14
- Exam 2 handed back

**Meeting 35: Fri Apr 18**

- Final project presentations, part 1: http://bit.ly/oplspr14

**Meeting 34: Wed Apr 16**

- Exam 2 back Friday
- more meta-circular evaluator

**Meeting 33: Mon Apr 14**

- FPP Final Project Proposal discussed; presentations in class on Fri Apr 18
- PS10 Meta-circular evaluator introduced

**Meeting 32: Fri Apr 11**

- Exam 2

**Meeting 31: Wed Apr 9**

- review for exam 2

**Meeting 30: Mon Apr 7**

- more streams

**Meeting 29: Fri Apr 4**

`stream-enumerate-interval`

,`stream-filter`

,`stream-accum`

- promises/thunks which are forced
- lazy evaluation—forcing only happens when someone needs the result
- time/space benefits—and complexities, because things are created as evaluation unfolds
- memo-ization—how it's done, why it matters
- space usage of
`stream-sum-primes`

—memoization of output of`filter-stream`

occurs, but all objects generated during`stream-enumerate-interval`

aren't saved - Attach:stream-examples.rkt

**Meeting 28: Wed Apr 2**

**Exam 2 is Fri Apr 11**- FPE1
- Streams

- PS9 is assigned

**Meeting 27: Mon Mar 31**

- environment diagram of adventure game stuff

**Meeting 26: Fri Mar 28**

- Simple object-orientation in Scheme:

Attach:oo-notes.pdf

Attach:simple-oo-broken.rkt Attach:simple-oo-broken.rkt.pdf

Attach:simple-oo.rkt Attach:simple-oo.rkt.pdf

**Meeting 25: Wed Mar 26**

- Mark Sherman guest lecture on environment diagrams, part 2

**Meeting 24: Mon Mar 24**

- Mark Sherman guest lecture on environment diagrams, part 1

**Meeting 23: Fri Mar 14**

**Meeting 22: Wed Mar 12**

**Meeting 21: Mon Mar 10**

- discussion of PS7 type system material:
- 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)

**Meeting 20: Fri Mar 7**

**Meeting 19: Wed Mar 5**

- Store Credit problem—how to do the doubly-nested recursion
- Went through all of http://courses.cs.washington.edu/courses/cse341/12au/racket/basics.html
- rest of the semester will be:

type systems

object-orientation adventure game(and environments)

streams

metacircular evaluator

Plus—your final project

**Meeting 18: Mon Mar 3**

- discussion of codejam problems; specifically how to solve Numbers (3 + √5)^n.
- it's OK to look at answers and even explanations of strategies; you should be thinking to do to it with recursion, map/filter, and other Scheme approaches.
`eq?`

,`eqv?`

, and`equal?`

- symbols are the same object even when created separately (if they're in the same environment)

**Meeting 17: Fri Feb 28**

- exams returned; let's go over them
- new OPL Mantra:
*Do not violate the abstraction barrier.* - let's figure out what's going on with PS6
- a numerics package: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-17.html#%_sec_2.4
- generics: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-18.html#%_sec_2.5
- Scheme code for number system and generic types

**Meeting 16: Wed Feb 26**

- exams will be returned Friday
- rational numbers
`memq`

—finding an item as a member of a list(define (memq item x) (cond ((null? x) false) ((eq? item (car x)) x) (else (memq item (cdr x)))))

`(memq 'apple '(pear banana prune))`

is`#f`

`(memq 'apple '(x (apple sauce) y apple pear))`

is`'(apple pear)`

- symbolic differentiation

**Meeting 15: Mon Feb 24**

- PS5 assigned; due next Monday
- PS4 cdDB answers
- Let's talk about
`let`

(and`let*`

and`lambda`

):

**Meeting 14: Fri Feb 21**

- Exam 1

**Meeting 13: Wed Feb 19**

- exam review
`bucket`

- Attach:ps3.rkt-passwd.pdf

**Meeting 12: Tue Feb 18**

- Back to
`accumulate`

aka`reduce`

:(define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence)))))

- That's also known as
`fold-right`

, since it starts combining from the end of the sequence and works from right-to-left.

Let's look at`fold-left`

:(define (fold-left op initial sequence) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter initial sequence))

- Why does this matter? What are each of these things...
(fold-right / 1 (list 1 2 3)) (fold-left / 1 (list 1 2 3)) (fold-right list nil (list 1 2 3)) (fold-left list nil (list 1 2 3))

**Meeting 11: Fri Feb 14**

- PS1 and PS2 answers handed out (hard copy);

please ask any questions before Weds if you want something clarified before exam. - Trees again:
(define (add-leaves t) (cond ((null? t) 0) ((leaf? t) t) (else (+ (add-leaves (car t)) (add-leaves (cdr t))))))

- Re-write as
`count-leaves`

- Abstract to
`tree-manip`

:(define (tree-manip tree init leaf accum) (cond ((null? tree) init) ((not (pair? tree)) (leaf tree)) (else (accum (tree-manip (car tree) init leaf accum) (tree-manip (cdr tree) init leaf accum)))))

Let's do sum-trees and count-leaves with this.

**Meeting 10: Wed Feb 12**

- PS4 assigned
- how can you produce
`'(1 . (2 3) 4)`

`'(1 . ((2 3) 4)))`

`eq?`

,`equal?`

, and`=`

(and also,`eqv?`

) (see http://groups.csail.mit.edu/mac/ftpdir/scheme-7.4/doc-html/scheme_4.html)- how do we solve iterative exponentiation-producing function? :
;; Recursive process (define (expnt n) (if (= n 1) (lambda (x) x) (lambda (x) (* x ((expnt (- n 1)) x))))) ;; fill in the below procedure ;Iterative process (define (expnt-iter n) ;(define (expnt-help next sum base) ; (if (eq? next 0) ; 1 ; (expnt-help (dec next) (* sum base) base) <--- ; I get lost trying to draw out this recursion. ; )) ;(expnt-help 2 0 5))

Attach:expnt.rkt - trees—summing up leaves; counting the leaves Attach:tree.rkt

**Meeting 9: Mon Feb 10**

`scale-list`

generalized to`map-list`

`filter`

a list`accumulate`

(or`reduce`

) over a list- Attach:map-filter-reduce.rkt

**Meeting 8: Fri Feb 7**

**EXAM 1 IS FRI FEB 21**- PS2 time invested poll
- 25% of you have not turned in PS2.
- The assignments are difficult
- Many people will need 6 to 8 hours/week to complete them
- If you don't do the homeworks, you will fail the class

- PS3 is assigned; due Wed Feb 12
- let's write a bunch of list operation procedures:
`nth`

we did this last time, we'll go over it again`scale-list`

scale each item in a list by a constant factor`add-lists`

add together items from two lists pairwise, producing a third list`append-list`

e.g.,`(append-list '(1 2 3) '(4 5 6))`

should produce`'(1 2 3 4 5 6)`

`reverse-list`

e.g.,`(reverse-list '(1 2 3))`

should produce`'(3 2 1)`

`map-list`

e.g.,`(map-list (lambda (x) (+ x 3)) '(1 2 3))`

should produce`'(4 5 6)`

- Attach:reverse-lst.rkt Δ Attach:append-lists.rkt Attach:add-lists.rkt Δ

**No Meeting 7: Wed Feb 5**

- snowday
- see email sent to group: https://groups.google.com/forum/#!topic/91301-s14/Kq4EerN1NaU

**Meeting 6: Mon Feb 3**

`sum-integers`

,`sum-cubes`

,`pi-sum`

- 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)
- Attach:pi-sum.rkt Attach:nth-and-defining-lists-with-lambda.rkt

**Meeting 5, Fri Jan 31**

- tree recursion with (e.g.)
`fib`

:

(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))

- 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.

*PLAI,*pp 41–42

`make-add-n`

, a function that returns a function that adds`n`

to its input`make-scale`

, a function that returns a function that scales its input- Attach:make-expnt.rkt
- Closure: A closure is a first-class function with free variables that are bound in the lexical environment. (Thanks, Wikipedia.)

**Meeting 4, Wed Jan 29**

- PS2 assigned; due next Wed
- OPL Mantras:
`define`

and evaluation - Back to the recursive-process and iterative-process versions of factorial (both are recursive definitions):

(define (fact n) (if (= n 1) 1 (* n (fact (- n 1))))) (define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))

- When the tail call optimization can be made:

*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*.”

*Programming Languages: Application and Interpretation*, Shriram Krishnamurthi, section 20.4, pp. 216 of PDF.

- calculation of
*e*recursively:

`(e 5)`

should compute *1/0! + 1/1! + 1/2! + 1/3! + 1/4! + 1/5!*

**Meeting 3, Mon Jan 27**

- Scheme Rules of Evaluation
- the Eval/Apply loop (from the yin-yang cycle)
- predicate—a procedure that produces a boolean result
`define`

is a special form—creates a binding in an environment`define`

as syntactic sugar for procedure creation- substitution model for procedure evaluation
`cond`

transformed into nested`if`

s

**Meeting 2, Wed Jan 24**

- number types in Scheme—int, infinite int, rational, float
- predicates—end in
`?`

; return`#t`

or`#f`

`if`

and`cond`

- recursions that run out of memory
- tail recursion
- iterative process vs. recursive process (with
`fact`

)

**Meeting 1, Wed Jan 22**

- introductions
- what is this class?
- demo of Racket—creating a procedure and applying it
- demo of autograder