6.1 Topics

• modules instead of includes. Includes are text "in place". Modules are properly encapsulate code that exports an interface. See the new implementation of the streams module.

• mutable state with set!. We glossed over it with the 'object' example.
• mutable pairs with mcons, mcdr, mcar, set-mcdr!, set-mcar!
• implementing a queue data structure
• implementing your own delay and force with mutable pairs.

• tail recursion elimination

• introduction to continuations

6.2 Flipped Work

1. If you program in Python, you know about generators. A generator is a function that produces a sequence one element at a time. That is, it doesn't generate the next element in the sequence until called to do so. Instead it generates the current element, and then saves sufficient state to resume its computation when (or if) asked.
   You can think of a generator as a weak form of stream, one that forgets the elements that have been consumed so far. One way to implement this is to have the generator be a reference into the stream. Every time you invoke the generator you get the current reference element, and the generator advances to the next element of the stream. Generator use would be something like this:

   ; create a generator g on stream s
(define g (make-gen s))
; access first two elements generated by s
(+ (g) (g))


   You want to make sure that your generator g does not fetch anything from the stream until g is invoked, otherwise for finite streams you could run off the end before you intended.

2. You can think of the pair created by cons and mcons as representing edges between vertices in a graph. If v1 and v2 are vertices, then (cons v1 v2) is the edge from v1 to v2. For example, this list of edges

   ( cons(v2 v1) cons(v1 v4) cons(v4 v3) cons(v3 v4) cons(v3 v1) )

   defines the graph:
   
   
   Write a function (dfs g root) which does a depth-first traversal of the graph g, starting at vertex root, and returns a list of the vertices visited.

3. Write the functions
   q-from-list that takes a list and creates the queue with the same elements initially,
   q-to-list that takes a queue and creates a list containing the current elements of the queue.

4. Turn the new queue code into a module so that only the interface is exported.

5. Look at Section 10 - Continuations continued of the Course Notes.

6.3 Sample Solutions to Flipped Work

6.4 Formative Quiz

6. Week 4 - Jan 27 CMPUT 325 Schedule / Version 2.31 2014-04-04