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
- implementation of
dotimes
- FPFlyer and FPCode
- info about final
- course evals
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
Meeting 35: Fri Apr 18
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
Meeting 31: Wed Apr 9
Meeting 30: Mon Apr 7
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
Meeting 27: Mon Mar 31
- environment diagram of adventure game stuff
Meeting 26: Fri Mar 28
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
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
Meeting 16: Wed Feb 26
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
Meeting 13: Wed Feb 19
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)
or—'(1 . ((2 3) 4)))
?
Meeting 9: Mon Feb 10
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
Meeting 6: Mon Feb 3
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.
From 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:
“An invocation of 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.”
- calculation of e recursively:
e.g., (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