# MartinBlog

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: http://echo360.uml.edu/martin201516/orgofprogramminglang.html

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*n*^{th}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 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 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>
- READ THE SPEC

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

- project presentations: https://docs.google.com/presentation/d/1EqE432gl3Narx8a2vZQKvchEmoYqMkzR3SrHFr5LiAg/present

**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:

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

Data-directed |

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”

`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**

- Mark Sherman guest lecture
- Exam 1 handed back -- see info at https://groups.google.com/d/msg/uml-opl-spr16/0Jtkau6LmKA/PKQPacTYHwAJ
- Exam 1 was reviewed in detail -- https://echoess.uml.edu:8443/ess/echo/presentation/f23462ed-2b7f-437b-954c-7d837ed3b3ca

**Meeting 23: Fri Mar 11**

- diving into the type systems code
- in-class exercise: Attach:type-sys-exercises.pdf

**Meeting 22: Wed Mar 9**

- introduction to type systems
- in-class exercises: Attach:type-systems-intro.pdf
- intro to hash tables Attach:mar9.rkt

**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`

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

)

`+`

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

- 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

- in-class exercises: lambda, let, and environments (problem 1 only)

**Meeting 9: Mon Feb 8**

- PS2b due tomorrow before midnight
- PS2c due Sun Feb 14; PS3a due Tue Feb 16
- procedures as return values
- discussion of SICP exercise 1.41 in PS2b (double procedure). I got a little lost in the ((double double) inc) example. Fortunately Rob figured it out for us.
- “local variables” using
`let`

and the let / lambda equivalency. This is the part you want to watch to set up the six associated problems in the current PS. See also pages 85 - 88 of the SICP PDF (file pages 113-116).

*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

- 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

- Attach:sequences.pdf
- abstracting combiner, successor, and term-transformation functions as parameters of a general-purpose numeric sequence function

**Meeting 5: Fri Jan 29**

- PS2a is due Tue Feb 2
- PS2b is posted and will be due Tue Feb 9
- recursive recursion vs. iterative recursion; Attach:jan29.rkt
- tail recursion
- Attach:iterative-fib.pdf
- “An environment is a place where symbols are bound to values.”

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

- 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)`

- do it for
- 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**

`(square)`

?
**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:
- via web at pollev.com/fredm

- 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

`lambda`

takes two params (list of args; body-expression) and creates a procedure-object