• View
• Edit
• History
• Print

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”

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

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)

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

• written notes from the class

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

• Attach:feb5.rkt

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

• introduction to Bottlenose and PS0 (due Sunday before midnight)
• OPL in-class exercises pdf

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