Recent Changes - Search:
OPLspr14 /

LectureBlog

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

  • Exam 2

Meeting 31: Wed Apr 9

  • review for exam 2

Meeting 30: Mon Apr 7

  • more streams

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
Attach:delayed-evaluation.pdf
Attach:streams.pdf
  • PS9 is assigned

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

  • exams will be returned Friday
  • rational numbers
  • memq—finding an item as a member of a list 
     (define (memq item x)
  (cond ((null? x) false)
        ((eq? item (car x)) x)
        (else (memq item (cdr x)))))

    (memq 'apple '(pear banana prune)) is #f
    (memq 'apple '(x (apple sauce) y apple pear)) is '(apple pear)
  • symbolic differentiation

Meeting 15: Mon Feb 24

Meeting 14: Fri Feb 21

  • Exam 1

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)))
?
  • eq?, equal?, and = (and also, eqv?) (see http://groups.csail.mit.edu/mac/ftpdir/scheme-7.4/doc-html/scheme_4.html)
  • how do we solve iterative exponentiation-producing function? :
    ;; Recursive process
(define (expnt n)
  (if (= n 1)
      (lambda (x) x)
      (lambda (x) (* x ((expnt (- n 1)) x)))))

;; fill in the below procedure
;Iterative process 
(define (expnt-iter n)
  ;(define (expnt-help next sum base)
  ; (if (eq? next 0)
  ;      1
  ;      (expnt-help (dec next) (* sum base) base)  <--- 
  ;                                I get lost trying to draw out this recursion.
  ;      ))
  ;(expnt-help 2 0 5))

    Attach:expnt.rkt
  • trees—summing up leaves; counting the leaves Attach:tree.rkt

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.”
From Programming Languages: Application and Interpretation, Shriram Krishnamurthi, section 20.4, pp. 216 of PDF.
  • 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 ifs

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