% -*- Mode: Tex -*-

%\input /home/welg/6001mac.tex
%\input /homes/welg/6001/6001mac.tex
%\input /zu/scheme/6001ARCHIVE/fall89/6001mac.tex
\input ./6001mac.tex

{\obeyspaces\gdef {\ }}


\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}

\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\def\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\setlength{\textheight}{9.2in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Wednesday, May 6}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 1. Student Presentation}

Summarize the main points of the lecture of May 7. Take a position on
what you think the future role of computer assisted surgery will be in
medicine, and whether you think computers should be used to aid
surgeons in delicate surgery such as neurosurgery.

\vskip .08in

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 2. Memory}

Memory consists of many cells.  Each cell stores the following: A
number and a tag.  For now, we have three tags: 
\\ ``N'' -- Number
\\ ``P'' -- Pointer to another cell 
\\ ``E'' -- NULL

\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|}
& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
the-cars & N3 & N4 & P0 & N3 & N5 & P2 & N2 & N3 & P1 & N4 & \\
\hline 
the-cdrs & E0 & E0 & P4 & P5 & P0 & P6 & P5 & P3 & P3 & N5 & \\
\hline
\end{tabular}

Using this implementation of cons cells, {\tt (cons A B)} does this:
\begin{enumerate}
\vspace{-0.1in}
\item Look for the next FREE location
\vspace{-0.1in}
\item Store A at the-cars[i]
\vspace{-0.1in}
\item Store B at the-cdrs[i]
\vspace{-0.1in}
\item Return $P_i$, a pointer to the new cons cell.
\end{enumerate}

Using the memory block above, draw the box-and-pointer diagram
starting from {\tt P5}.

\vspace{1.7in}


Note that not everything sitting in memory is useful.  For example,
consider what occurs when the following is evaluated
{\tt (define foo (map square (list 1 2 3)))}.

\begin{enumerate}
\vspace{-0.1in}
\item Build the list (1 2 3)
\vspace{-0.1in}
\item Build the list (1 4 9)
\vspace{-0.1in}
\item Define foo to be the latter list
\end{enumerate}

There are no pointers to the list (1 2 3) anymore.  It cannot be
accessed.  It is {\it garbage}.  The memory should be recycled.

{\Large\bf 3. Garbage Collection}

Does our computer have infinite memory?  No.  But we can create the
illusion of infinite memory using Garbage Collection.  Consider the
following four procedure.  When applied, will Scheme run out of memory
or go into an infinite loop?

\begin{tabular}{|p{3in}|p{1in}|p{1in}|}
\hline
Procedure & Out of Mem? & Infinite Loop?  \\
\hline
\beginlisp
(define (foo) (foo))
\null
\endlisp & &
\\
\hline
\beginlisp
(define (foo) 
  (let ((x (cons 1 2)))
    (foo)))
\null
\endlisp & &
\\
\hline
\beginlisp
(define (foo z) 
  (let ((x (cons 1 2)))
    (foo x)))
\null
\endlisp & &
\\
\hline
\beginlisp
(define (foo z) 
  (let ((x (cons 1 z)))
    (foo x)))
\null
\endlisp & &
\\
\hline
\end{tabular}

{\bf What's Garbage?} Garbage is anything that cannot have any
influence on the future computation.  Everything else we need to keep
around.  We define the {\bf Root Set} to be the set of all pointers in
the machine registers and stack.  The cells we might need are defined
as those cells that can be reached by a succesion of {\tt car} and
{\tt cdr} operations starting from the root set.

{\Large\bf 3. Reference Count}

Here's the main idea to reference counting:

\begin{enumerate}
\vspace{-0.1in}
\item Attach a counter to each pair in memory.
\vspace{-0.1in}
\item When a new pointer is connected to that pair, increment the counter.
\vspace{-0.1in}
\item When a pointer is removed, decrement the counter.
\vspace{-0.1in}
\item Any cell with 0 counter is garbage.
\end{enumerate}

Consider the following example, and draw the box-and-pointer diagrams
below, keeping a ``reference counter'' with each cell.

\beginlisp
(define a (list 1 2 3))
(set-cdr! a 4)
(set-cdr! a a)
(set! a 1)
\endlisp

\vspace{1.9in}

Reference Counting can't handle circular data structures!

\newpage 

{\Large\bf 3. Stop and Copy}

Here's the main idea to Stop and Copy:

\begin{enumerate}
\vspace{-0.1in}
\item Split memory in half (Working memory and Copy memory).
\vspace{-0.1in}
\item Keep a {\tt free} pointer to the free part of memory.
\vspace{-0.1in}
\item When Memory runs out, stop computation and begin garbage collection.
\vspace{-0.1in}
\begin{enumerate}
\item Place {\tt scan} and {\tt free} pointers at the start of the
Copy memory.
\item Copy the Root Set over to copy memory, incrementing {\tt free}.
In each location that's copied over, put the ``Broken Heart'' token in
the {\tt car} and the forwarding address in the {\tt cdr}.
\item Starting at the {\tt scan} pointer, check the {\tt car} and the
{\tt cdr}.  If either is a pointer, look at the location in Working
memory.  If it's already been copied (i.e. it has a ``Broken Heart''),
update the reference.  Otherwise, copy the location and put the
``Broken Heart'' in the old location.
\item Repeat until {\tt scan} = {\tt free}. 
\item Swap the roles of the Working and Copy memory.
\end{enumerate}
\end{enumerate}

The register machine code for this algorithm is in the text.

For example, let's perform stop-and-copy on the following with {\bf
Root Set} = \{ P5 \}: 

\renewcommand{\arraystretch}{1.8}
\begin{tabular}{p{0.7in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|}
{\bf Working} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
the-cars & N3 & N4 & P0 & N3 & N5 & P2 & N2 & N3 & P1 & N4 & \\
\hline 
the-cdrs & E0 & E0 & P4 & P5 & P0 & P6 & P5 & P3 & P3 & N5 & \\
\hline
\end{tabular}

\vspace{0.8in}

\begin{tabular}{p{0.7in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|}
{\bf Copy} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
the-cars &  &  &  &  &  &  &  &  &  &  & \\
\hline 
the-cdrs &  &  &  &  &  &  &  &  &  &  & \\
\hline
\end{tabular}

\vspace{0.8in}

This method sounds expensive, because half of memory is idle except
when using the Garbage Collector.  However, it goes just about as fast
as possible.  It only examines valid locations.  Most memory is
garbage, and never even gets looked at.  We see a very common tradeoff
here: Pay a lot of space, get a lot of time.

\newpage

{\Large\bf 3. Mark - Sweep}

Here's the main idea to Mark-Sweep:

\begin{enumerate}
\vspace{-0.1in}
\item Add a Mark Bit to each location in memory.
\vspace{-0.1in}
\item Keep a {\bf free} pointer to the head of the free list.
\vspace{-0.1in}
\item When Memory runs out, stop computation, clear the Mark Bits
and begin garbage collection. 
\item {\bf Mark}
\vspace{-0.1in}
\begin{enumerate}
\item Start at the root and follow the accessible structure (keeping a
stack of where you still need to go).
\item Mark every cell you visit.
\item Stop when you see a marked cell, so you don't go into a cycle.
\end{enumerate}
\item {\bf Sweep}
\vspace{-0.1in}
\begin{enumerate}
\item Start at the end of memory, and build a new free list.
\item If a cell is unmarked, then it's garbage, so hook it into the
free list.
\end{enumerate}
\end{enumerate}

For example, let's perform Mark-Sweep on the following with {\bf Root
Set} = \{ P5 \}:

\renewcommand{\arraystretch}{1.8}
\begin{tabular}{p{0.7in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|p{0.25in}|}
{\bf Memory} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
the-cars & N3 & N4 & P0 & N3 & N5 & P2 & N2 & N3 & P1 & N4 & P5 \\
\hline 
the-cdrs & E0 & E0 & P4 & P5 & P0 & P6 & P5 & P3 & P3 & N5 & N7 \\
\hline
marks & & & & & & & & & & & \\
\hline 
\end{tabular}

\vspace{0.2in}

{\bf Stack:}

\vspace{0.2in}

{\bf Free Pointer:}

\vspace{0.4in}

This method is a good deal more compact than stop-and-copy.  However,
it also always looks through all of memory, so it is fairly slow.

In this example, we needed a stack to keep track of where we still
need to explore.  This can actually be done without a stack by keeping
track of recursive calls using the data structures in memory
themselves.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

