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: rightclick 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/umloplspr16/WtX5Ia4BRx0/1uvjjmiQBAAJ)
streamref
: 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
streammap
(map a proc to a single stream), addstreams
, and streammapgeneral
(map and combine across multiple streams),
 defining streams implicitly; e.g. the integers:
(define ones (consstream 1 ones))
(define integers
(consstream 1 (addstreams ones integers)))
(define fibs
(consstream
0
(consstream 1 (addstreams (streamcdr fibs) fibs))))
 inclass exercises: Attach:streams.pdf
 Sieve of Eratosthenes (a thirdcentury B.C. Alexandrian Greek philosopher):
(define (sieve stream)
(consstream
(streamcar stream)
(sieve (streamfilter
(lambda (x)
(not (divisible? x (streamcar stream))))
(streamcdr stream)))))
(define primes (sieve (integersstartingfrom 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: infinitelyscrolling 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 closureobject) called a “thunk”
 the thunk consists of a procedure application with parameters and a environmentchain in which to eval the params
delay
creates the thunk
 it can be cashed in with
force
 streams are delayed lists. New primitives:
consstream
, streamcar
, streamcdr
, theemptystream
, and emptystream?
consstream
uses cons
to combine the first param with a promise made from the second
streamcar
is car
streamcdr
does a force
on the cdr
 examples:
enumerateinterval
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
streamenumerateinterval
and use streamfilter
and it's efficient
 “memoization” is caching the computed result in the forcedpromise 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 (numsstartingat z)
(consstream z
(numsstartingat (+ z 1))))
(define nats (numsstartingat 1))
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 mceval 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 mceval 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 mceval 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 mceval
Meeting 29: Fri Apr 1
 FP4 Project Proposal due noon Wed Apr 6
 new material: the metacircular evaluator (implementing scheme in scheme)
 the evalapply loop (and yinyang symbol)
 many systems have interpreters embedded in them
 inclass exercise: Attach:standardornot.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
 nonencapsulated, writeonly, and fullyimplemented “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
 typetag and contents procedures for unpacking a tagged data type
 concluded with a walkthrough of the applygeneric procedure
 system can't add/sub/mul/div disparate types!
 also discussed dotsyntax for making procs of arbitrary num of args:
variable after the dot is bound to a list of such args (e.g. in applygeneric procedure)
 understanding how
applygeneric
can add objects of same type
 book discusses three ways of organizing type systems:
 generic operations with explicit dispatch,
 datadirected (the
applygeneric
system we're using), and
 messagepassing.

Explicit dispatch 

Datadirected 

Messagepassing 
 Ex. 2.77, about adding complex number selectors to the complex number type (problem p2 in the PS).
 Ex. 2.78, about updating schemenumber 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
).
Meeting 25: Wed Mar 23
 PS5 now due Sun Mar 27
 inclass exercise: Attach:typesysrect.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
Meeting 19: Wed Mar 2
 you may bring 1 sheet of handwritten notes on 8.5x11" paper to exam (turn in with exam)
 inclass 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)
 inclass 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
emptylist is not a pair
make sure to use null?
to test for emptylist
Meeting 16: Wed Feb 24
 inclass exercises: nth, length, and last
 a tree is a list of lists (where each sublist may itself contain sublists)
 trees:
countleaves
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 righttoleft
examples using +
and *
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
 inclass 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)
 inclass 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 inclass 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)
 inclass exercises: cons, car, cdr, and lists
 example: geomsquare abstraction
Meeting 10: Wed Feb 10
 PS2c due Sun Feb 14; PS3a due Tue Feb 16
 full method for drawing environments including doublecircle 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 higherorder procedures (procedures as parameters), and parameterizing sumsofseries (or productsofseries)
 firstorder 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 firstclass 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 termtransformation functions as parameters of a generalpurpose 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:substmodelfactorial.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:
sumofsquares
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.”
 Introduction to recursion: factorial definition (defined in terms of itself)
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 inclass 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 procedureobject), apply it to values of remaining things (evaluate them before applying the procedureobject 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 symbolname that binds to an objectvalue 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; bodyexpression) and creates a procedureobject
Also uses special eval rules