# MartinBlog

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

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 https://groups.google.com/d/msg/uml-opl-spr16/WtX5Ia4BRx0/1uvjjmiQBAAJ)
• `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
• Fibonacci numbers:
```(define fibs
(cons-stream
0
(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)
(cons-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 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

'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.
• 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 https://groups.google.com/d/msg/uml-opl-spr16/btzce4oU3as/1TSB1XrvIQAJ 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)
initial
(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 `bit.ly/oplspr16`
• “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