% -*- Mode: Tex -*-

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

\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, April Fools}

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

{\Large\bf 1. Student Presentation}

Write a predicate equal-streams? which takes two streams as input and
says whether they look the same, i.e. have the same number of elements
and each corresponding pair is the same.

\vskip .1in

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

{\Large\bf 2. Delayed Evaluation and Streams}

Today, we're going to be lazy.  We're not going to do any work until
we're forced to.  Let's review the definition of our lazy evaluation
constructs:

\beginlisp
(delay s)  <==>  (lambda () s)          * Note misprint in lecture notes
(define (force obj) (obj))
\null
(cons-stream x y)  <==>  (cons x (delay y))
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
\endlisp
     
Let's take a closer look at how {\tt pos-ints} is defined and
evaluated using streams:

\beginlisp
(define ones (cons-stream 1 ones))
\null
(define (add-streams s t)
  (cons-stream
     (+ (stream-car s) (stream-car t))
     (add-streams (stream-cdr s) (stream-cdr t))))
\null
(define pos-ints (cons-stream 1 (add-streams ones pos-ints)))
\endlisp

Draw the environment diagram for the above and following expressions:

\beginlisp
(define foo (stream-cdr pos-ints))
\endlisp

\vskip 0.1in

\begin{tabular}{|p{6.3in}|}
\hline 
\beginlisp
\null 
\null 
\null 
\null 
\null 
\null 
\null
\null 
\null 
\null 
\null 
\null
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null
\endlisp \\
\hline
\end{tabular}

\newpage
{\Large\bf 3. Streams and Countable Sets}

A set has a countable number of elements if the elements can be placed
in a stream in any order such that every element is reachable in the
stream.  Let's look at and build a few infinite streams of countable
sets.  Consider the following definitions:

\beginlisp
(define ones (cons-stream 1 ones))
\null
(define (add-streams s t) (stream-map + s t))
\null
(define pos-ints (cons-stream 1 (add-streams ones pos-ints)))
\null
(print-stream pos-ints)
;Value: (1 2 3 4 5 6 7 8 9 10 ...)
\null
(define neg-ints (stream-map (lambda (x) (- x)) pos-ints))
\null
(print-stream neg-ints)
;Value: (-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ...)
\endlisp

Are the positive integers countable?  Are the negative integers
countable?  How about all the integers?  Well, can we put them into a
stream?   

Let's define stream-append that looks very similar to append.  Maybe
this will help us define a stream of the integers.

\beginlisp
(define (stream-append s t)
%   (if (empty-stream? s)
%       t
%       (cons-stream (stream-car s)
%                    (stream-append (stream-cdr s) t)))
\null
\null
\null
\null
)
\endlisp

Now, how can we define a stream with all the integers?

\beginlisp
(define ints
%  (cons-stream 0 (stream-append pos-ints neg-ints))
\null
)
\endlisp

Umm....  Something looks wrong there...  How can we append anything
onto an infinite stream?  What's the right way to do this (remember,
order doesn't really matter, as long as every element is reachable in
the stream)?

How can we capture this two-way infinite sequence into a stream? \\
{\tt ..., -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, ... }

\beginlisp
% (define (interleave s t)
%   (if (empty-stream? s)
%       t
%       (cons-stream (stream-car s)
%                    (interleave s (stream-cdr t)))))
% \null
% (define ints
%   (cons-stream 0
%                (interleave pos-ints neg-ints)))
% \null
% (print-stream ints)
% ;Value: (0 1 -1 2 -2 3 -3 4 -4 5 ...)
\null
\null
\null
\null
\null
\null
\null
\null
\endlisp

Since we've built a stream of all the integers, we know that the
set of all integers is a countable set.

\newpage
What about the set of all pairs of positive integers:
$\{ \langle x,y \rangle \; | \; x, y \in Positive Integers \}$?  
How can we capture this infinite-way infinite sequence into a stream? 

\begin{center}
\begin{tabular}{c|cccccc}
  & 1 & 2 & 3 & 4 & 5 & \ldots \\
\hline
1 & 
$\langle 1,1 \rangle $ &
$\langle 1,2 \rangle $ & 
$\langle 1,3 \rangle $ &
$\langle 1,4 \rangle $ &
$\langle 1,5 \rangle $ & \ldots\\
2 &
$\langle 2,1 \rangle $ &
$\langle 2,2 \rangle $ & 
$\langle 2,3 \rangle $ &
$\langle 2,4 \rangle $ &
$\langle 2,5 \rangle $ & \ldots \\
3 &
$\langle 3,1 \rangle $ &
$\langle 3,2 \rangle $ & 
$\langle 3,3 \rangle $ &
$\langle 3,4 \rangle $ &
$\langle 3,5 \rangle $ & \ldots \\
4 & 
$\langle 4,1 \rangle $ &
$\langle 4,2 \rangle $ & 
$\langle 4,3 \rangle $ &
$\langle 4,4 \rangle $ &
$\langle 4,5 \rangle $ & \ldots \\
5 &
$\langle 5,1 \rangle $ &
$\langle 5,2 \rangle $ & 
$\langle 5,3 \rangle $ &
$\langle 5,4 \rangle $ &
$\langle 5,5 \rangle $ & \ldots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
\end{tabular}
\end{center}

Let's define a procedure {\tt pairs} that takes two infinite streams
and returns a stream of all possible pairs of elements of the two
streams.  

\beginlisp
(define (pairs s t)
  (cons-stream 
     (list (stream-car s) (stream-car t))
     (interleave 
%        (stream-map 
%          (lambda (x) (list (stream-car s) x))
%          (stream-cdr t))
%        (pairs (stream-cdr s) t))
\null
\null
\null
\null
\null
     ))
\null
(define pos-int-pairs (pairs pos-ints pos-ints))
(print-stream pos-int-pairs)
;Value: ((1 1) (1 2) (2 1) (1 3) (2 2) (1 4) (3 1) (1 5) (2 3) (1 6) ...)
\endlisp

\vskip 0.1in

What about other sets ... are they countable?
Can you represent all the elements in an infinite stream?

\begin{itemize} 
\item Set of all integer pairs (instead of pos-int-pairs)
\item Set of all rational numbers
\item Set of all real numbers between 0 and 1
\item Set of all Scheme programs
\end{itemize}

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

\end{document}
