Home Assignments Lecture Blog Resources Project Discussion Group
Meeting 25 – Tue Dec 1
The Metacircular Evaluator!
- eval-apply loop
eval
as a big cond statement, testing special forms and then finally using apply
for the default case of applying a procedure to its args
- need for env context for eval
apply
and its way of constructing args as a list, often recursing into more eval
s
- how primitive procedures are implemented – populating
the-global-environment
with bindings, so ultimately they are just variable lookups
- defining a symbol, which extends the environment
- running the MC evaluator in Scheme (demo)
- don't say
(uml:define 'foo 5)
– the quote confuses it – just do (uml:define foo 5)
- looking at the environment objects in printed form (lists of symbols and the things they are bound to)
- PS10 handed out
Meeting 24 – Tue Nov 24
- went over FPProp
- list of topics from the semester:
- objects/state/closures
- abstraction "barriers" / layers (everyone should do this)
- map / filter / reduce (aka accumulate)
- streams
- recursion
- tail recursion
- iteration using recursion (looping over a state variable)
- symbolic differentiation (more broadly -- symbolic processing)
- data types, tagged data, data-directed programming
- functions and composition of functions
Meeting 23 – Thu Nov 19
- how to do
real-part
of a complex number
- type coercion
Meeting 22 – Tue Nov 17
apply-generic
and the type system
Meeting 21 – Thu Nov 12
Meeting 20 – Tue Nov 10
Meeting 19 – Thu Nov 5
Meeting 18 – Tue Nov 3
- mapreduce ii presented by fred
- working through the lab exercises
Meeting 17 – Thu Oct 29
Meeting 16 – Tue Oct 27
Meeting 15 – Thu Oct 22
- hand back PS4 answers and Quiz 1 answers
- PS6 due
- PS6 FPE1 due next Thurs (not Tue)
- streams & PS7
- streams are delayed lists
stream-enumerate-interval
, stream-map
, stream-filter
cons-stream
, stream-car
, stream-cdr
delay
and force
- infinite streams:
ones
, integers
, integers
in terms of ones
- “memo-ization” with
memo-proc
Meeting 14 – Tue Oct 20
Meeting 13 – Thu Oct 15
- environment diagrams,
balance
make-speaker
and starting to do ask
Meeting 12 – Tue Oct 13
Meeting 11 – Thu Oct 8
count-leaves
as accumulation
- quiz review
- discussed exercise 2.58b, on parsing with precedence. did not solve it.
Meeting 10 – Tue Oct 6
- Quiz 1 is Tue Oct 13
- symbolic differentiation PS
Meeting 9 – Thu Oct 1
Henderson Picture Language!
- vectors and segments
- frames
- the four painters:
number->painter
, segments->painter
, load-painter
, procedure->painter
transform-painter
and shrink-to-upper-right
rotate90
with transform-painter
and frames
beside
and above
up-split
recursion
Meeting 8 – Tue Sep 29
count-leaves
sum-odd-squares
and even-fibs
- signal-flow diagrams for the two procedures
enumerate-interval
and enumerate-tree
(aka, flatten-tree
)
accumulate
(aka, reduce
)
- redoing
sum-odd-squares
and even-fibs
as accumulations
- do
list-fib-squares
and product-of-squares-of-odd-elements
as accumulations
- examples from class
Meeting 7 – Thu Sep 24
- Church numerals
map
and filter
- trees are lists of lists
scale-tree
pair?
and list?
Meeting 6 – Tue Sep 22
Lists!
length
- iterative length
list-ref
or nth
(iterative and recursive are the same!)
append
and reverse
(spent lots of time on these; also looked at things like (append '(1 2) 3))
- idea of “cdr'ing down” a list
quote
suppresses evaluation; (list 1 2 3)
is equivalent to '(1 2 3)
scale-list
- box-and-pointer diagrams for the above and things like:
(cons 1 (cons 2 3))
(list 1 (cons 2 3))
(cons '(1 2) 3)
(append '(1 2) 3)
- code from today: Attach:append-reverse.ss
- next:
map
, filter
, and trees
- for next time through:
append
and reverse
are complex; do scale-list
first
Meeting 5 – Thu Sep 17
- data abstraction / abstraction barrier, as applies to
make-rat
, numer
, and denom
- implementation of
add-rat
cons
, car
, and cdr
primitives and their use in the rat system
- with Scheme you're constantly creating cons cells and letting them evaporate; it's offensive to some but also freeing and powerful
- how the rat system points in the direction of OO programming (constructors and selectors), but doesn't fully get there because the "methods" are not bundled with the data structures
- Scheme is not type-safe; if you care about type, build a type system (we will do that)
- procedure-closure and dispatch method of building cons/car/cdr
- mathematical definition of closure (vs. functional closure)
- box-and-pointer diagrams
- definition of
nil
as (define nil '())
- nested lists
- immutability of cons cells in PLT 4.x; separate, parallel implementation of mutable pairs (
mcons
, mcar
, and mcdr
)
- using mutability to create a circular list
- live buffer history
Meeting 4 – Tue Sep 15
- internal procedure definitions with
sqrt-iter
(pp. 29–30) and lexical scoping
- procedures as arguments, using
pi-sum
example (pp. 57–58)
lambda
as let
, motivated by f(x, y) example (pp 63–64)
rewrite this using lambda's
Meeting 3 – Thu Sep 10
- first problem from PS2 in class (iterative and recursive processes for
inc
and dec
)
- fibonacci and its recursive and iterative forms
- exponential growth (in space) based on golden ratio
- 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.”
- 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 (ibid.), pp 41–42
Meeting 2 – Tue Sep 8
- SchemeRulesOfEvaluation
- more special forms:
if
, cond
, and
, or
, and not
. These don't necessarily obey the standard evaluation rule of “ eval all subexprs, then apply operator”
cond
as syntactic sugar for nested if
s
define
a procedure as syntactic sugar for binding a symbol to a proc object created with lambda
- substitution model to illustrate applicative order (how Scheme works) vs. lazy evaluation with normal order
- recursive procedures generating recursive processes (
fact
) or iterative processes (fact-iter
)
- tail-call optimization implements iterative recursions without building stack frames
- showing the debugger by clicking on the nested stop-sign
Meeting 1 – Thu Sep 3
- the 2 types of prog lang classes
- history of this class
- why we are studying these ideas: they are present in modern lang's
- the recursive evaluation rule
define
special form
lambda
special form
right-click and view to enlarge