1.7-scheme_streams.tex

\documentclass[alsotrans,beameroptions={aspectratio=169}]{beamerswitch}
\usepackage{fprog}

% вариадични функции
\newboolfalse{variadic}

\title{Потоци}

\date{6 ноември 2024 г.}

\lstset{language=Scheme}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\section{Отложени операции}

\begin{frame}
  \frametitle{Отложени операции}

  \begin{itemize}[<+->]
  \item Има случаи на тежки операции, които могат да отнемат много време за изпълнение
  \item Удобно е да имаме механизъм да \alert{подготвяме} операциите и да ги \alert{изпълняваме} само при нужда
  \end{itemize}
  \onslide<+->
  \begin{definition}[Обещание]
    Функция, която ще изчисли и върне някаква стойност в бъдещ момент от изпълнението на програмата.
    \onslide<+->
    Нарича се още \emph{promise} и \emph{отложена операция}.
  \end{definition}
  \onslide<+->
  Изчислението на дадено обещание може да стане
  \begin{itemize}[<+->]
  \item паралелно с изпълнението на основната програма \textbf{(асинхронно)}
  \item при поискване от основната програма \textbf{(синхронно)}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Примитивни операции \tt{force} и \tt{delay}}

  \begin{itemize}[<+->]
  \item \tta{(delay} <израз>\tta)
  \item връща \alert{обещание} за оценяването на <израз> \visible<5->{\alert{(специална форма)}}
  \item \tta{(force} <обещание>\tta)
  \item форсира изчислението на <обещание> и връща оценката на <израз> \visible<5->{\alert{(примитивна функция)}}
    \pause
  \item \textbf{Примери:}
    \begin{itemize}
    \item \lst{(define bigpromise (delay (fact 30000)))}
    \item \lst{(force bigpromise)}$\;\xrightarrow{\hspace*{3cm}}\;$\tt{2759537246...}
    \item \lst{(define error (delay (car '())))}
    \item \evalstoerr{(force error)}
    \item \lst{(define undefined (delay (+ a 3)))}
    \item \lst{(define a 5)}
    \item \evalstop{(force undefined)}8
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{All you need is $\lambda$ --- \tt{force} и \tt{delay}}

  \begin{itemize}
  \item \lst{(delay }<израз>\tt) \eqv \lst{(lambda () }<израз>\tt)
  \item \lst{(force }<обещание>\tt) \eqv \tt(<обещание>\tt)\pause
  \item \alert{Не съвсем!} \pause
    \begin{itemize}[<.->]
    \item \lst{(define bigpromise (delay (fact 30000)))}
    \item \lst{(force bigpromise)}$\;\xrightarrow{\hspace*{3cm}}\;$\tt{2759537246...}
    \item \lst{(force bigpromise)}$\;\rightarrow\;$\tt{2759537246...} \pause
    \item Обещанията в Scheme имат страничен ефект: „мемоизират“ вече изчислената стойност
    \end{itemize}
  \end{itemize}
\end{frame}

\section{Потоци}

\begin{frame}
  \frametitle{Потоци в Scheme}

  \begin{definition}[Поток]
    Списък, чиито елементи се изчисляват отложено. \\
    \pause
    По-точно: Поток е празен списък \tt{()} или двойка \tt{(h . t)}, където
    \begin{itemize}
    \item \tt h --- е произволен елемент (глава на потока)
    \item \tt t --- е \alert{обещание} за поток (опашка на потока)
    \end{itemize}
  \end{definition}
  \pause
  В R$^5$RS няма вградени примитиви за работа с поток, но можем да си ги дефинираме.
  \pause
  \begin{itemize}[<+->]
  \item \lst{(define the-empty-stream '())}
  \item \lst{(define (cons-stream h t) (cons h (delay t)))}
  \item \lst{(define head car)}
  \item \lst{(define (tail s) (force (cdr s)))}
  \item \lst{(define empty-stream? null?)}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Примери}

  \begin{itemize}[<+->]
  \item \lst{(define s (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))}
  \item \evalsto{(head s)}1
  \item \evalsto{(tail s)}{(2 . \#<promise>)}
  \item \evalsto{(head (tail s))}2
  \item \evalsto{(head (tail (tail s)))}3
  \item \evalstoerrs{\tt{(define s2 (cons-stream 3 (cons-stream b the-empty-stream)))}}
  \item<+-| alert@+>Защо?
  \item \tt{cons-stream} трябва да оценява \alert<.>{само първия си аргумент}!
  \item \tt{cons-stream} трябва да е \alert<.>{специална форма}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Дефиниране на специални форми}

  \begin{itemize}[<+->]
  \item \tta{(define-syntax} <символ>\\
    \hspace{2.5em}\tta{(syntax-rules ()} \{\tta(<шаблон> <тяло>\tta)\}\tta{))}
  \item дефинира специална форма <символ> така, че всяко срещане на <шаблон> се замества с <тяло>
  \item \tt{define-syntax} има и други, по-сложни форми
  \item Повечето специални форми на Scheme могат да се дефинират с \tt{define-syntax} (за справка: R$^5$RS)
  \end{itemize}
  \onslide<+->
  \textbf{Примери:}
  \onslide<+->
\begin{lstlisting}
(define-syntax delay
  (syntax-rules () ((delay x) (lambda () x))))
\end{lstlisting}
  \onslide<+->
\begin{lstlisting}
(define-syntax cons-stream
  (syntax-rules () ((cons-stream h t) (cons h (delay t)))))
\end{lstlisting}
\end{frame}

\section{Операции над потоци}

\begin{frame}[fragile]
  \frametitle{Конструиране и деконструиране на потоци}

  \textbf{Задача.} Да се построи поток от целите числа в интервала $[a; b]$.\\
  \pause
  \textbf{Решение:}
\begin{lstlisting}
(define (enum a b)
  (if (> a b) the-empty-stream
      (cons-stream a (enum (+ a 1) b))))
\end{lstlisting}
  \pause
  \textbf{Задача.} Да се намерят първите n елемента на даден поток.\\
  \pause
  \textbf{Решение:}
\begin{lstlisting}
(define (take n s)
  (if (or (empty-stream? s) (= n 0)) '()
      (cons (head s) (take (- n 1) (tail s)))))
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Приложение на потоци}

  \small
  \textbf{Задача.} Да се намери първата позиция в поток, на която има елемент с дадено свойство.\\
  \pause
  \textbf{Решение.}
\begin{lstlisting}
(define (find-stream p? s)
  (cond ((empty-stream? s) #f)
        ((p? (head s)) s)
        (else (find-stream p? (tail s)))))
\end{lstlisting}
  \pause
  \textbf{Задача.} Да се намери второто по големина просто число след 10000 със сума на цифрите кратна на 5.\\
  \pause
  \textbf{Решение.}
\begin{lstlisting}
(define (prime-5? n) (and (prime? n)
                          (= (remainder (sum-digits n) 5) 0)))
(define second-prime-5
  (head (find-stream prime-5?
          (tail (find-stream prime-5?
                  (enum 10000 100000)))))
\end{lstlisting}
\end{frame}

\section{Безкрайни потоци}

\begin{frame}[fragile]
  \frametitle{Безкрайни потоци}

  Отлагането на операции позволява създаването на \alert{безкрайни потоци}!\\[1em]
  \pause
  Примери:
\begin{lstlisting}
(define (from n) (cons-stream n (from (+ n 1))))
(define nats (from 0))
\end{lstlisting}
  \pause
  \textbf{Задача.} Да се генерира потокът от числата на Фибоначи.\\
  \pause
  \textbf{Решение:}
\begin{lstlisting}
(define (generate-fibs a b)
  (cons-stream a (generate-fibs b (+ a b))))
(define fibs (generate-fibs 0 1))
\end{lstlisting}
  \pause
  \begin{itemize}
  \item Функциите \tt{from} и \tt{generate-fibs} наричаме \alert{генератори}
  \item Казваме, че потоците \tt{nats} и \tt{fibs} са \alert{индиректно дефинирани}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Функции от по-висок ред за потоци}

  \textbf{Трансформиране (\tt{map})}
\begin{lstlisting}
(define (map-stream f s) (cons-stream (f (head s))
                           (map-stream f (tail s))))
\end{lstlisting}
  \pause
  \textbf{Филтриране (\tt{filter})}
\begin{lstlisting}
(define (filter-stream p? s)
  (if (p? (head s))
    (cons-stream (head s) (filter-stream p? (tail s)))
    (filter-stream p? (tail s))))
\end{lstlisting}
  \pause
  \textbf{Комбиниране (\tt{zip})}
\begin{lstlisting}
(define (zip-streams op s1 s2)
  (cons-stream (op (head s1) (head s2))
               (zip-streams op (tail s1) (tail s2))))
\end{lstlisting}
\end{frame}

\begin{frame}<\switch{variadic}>[fragile]
  \frametitle{\tt{map-stream} с произволен брой параметри}

  Стандартната функция \lst{map} за списъци позволява комбиниране на произволен брой $n$ списъци с $n$-аргументна функция.\\
  \pause
  Можем да реализираме \lst{map-stream} аналогично да комбинира произволен брой потоци:\\
  \pause
\begin{lstlisting}
(define (map-stream f . streams)
  (cons-stream (apply f (map head streams))
               (apply map-stream f (map tail streams))))
\end{lstlisting}
  \pause
  \textbf{Примери:}
  \begin{itemize}[<+->]
  \item \evalsto{(map-stream + nats ones)}{1 2 3 4 ...}
    \begin{itemize}
    \item еквивалентно на \lst{zip-streams}
    \end{itemize}
  \item \evalsto{(map-stream list nats (map-stream + nats nats fibs))}{(0 0) (1 3) (2 5) (3 8) ...}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Директна дефиниция на потоци}

  Можем да дефиниране на потоци с \alert{директна рекурсия}!
  \pause
\begin{lstlisting}
(define ones (cons-stream 1 ones))
\end{lstlisting}
  \pause
  Построяване на \tt{nats}:\hspace{8em}
  \begin{tabular}{*8c}
    \multirow2*+ & 0 & 1 & 2 & 3 & 4 & 5 & \ldots\\
                 & 1 & 1 & 1 & 1 & 1 & 1 & \ldots\\
    \hline
                 & 1 & 2 & 3 & 4 & 5 & 6 & \ldots
  \end{tabular}\\[-2ex]\pause
  \begin{fixedarea}[.135]
    \begin{onlyenv}<-4>
\begin{lstlisting}
(define nats (cons-stream 0 (map-stream 1+ nats)))
\end{lstlisting}
    \end{onlyenv}
    \begin{onlyenv}<5-| trans:0>
\begin{lstlisting}
(define nats (cons-stream 0 (@\ifbool{variadic}{map-stream}{zip-streams}@ + ones nats)))
\end{lstlisting}
    \end{onlyenv}
  \end{fixedarea}
  \vspace{-1ex}\pause\pause
  Построяване на \tt{fibs}:\hspace{8em}
  \begin{tabular}{*8c}
    \multirow2*+ & 0 & 1 & 1 & 2 & 3 & 5 & \ldots\\
                 & 1 & 1 & 2 & 3 & 5 & 8 & \ldots\\
    \hline
                 & 1 & 2 & 3 & 5 & 8 & 13 & \ldots
  \end{tabular}
  \pause
\begin{lstlisting}
(define fibs (cons-stream 0
               (cons-stream 1
                 (@\ifbool{variadic}{map-stream}{zip-streams}@ + fibs (tail fibs)))))
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Решето на Ератостен}

  \pause
  Алгоритъм за намиране на прости числа
  \pause
  \begin{itemize}
  \item Започваме със списък от последователни цели числа
  \item Докато не стигнем до края на списъка, повтаряме:
    \begin{itemize}
    \item Намираме следващото незадраскано число $p$, то е просто
    \item Задраскваме всички следващи числа, които се делят на $p$
    \end{itemize}
  \end{itemize}
  \pause
  Ще реализираме решетото над потенциално безкраен поток от числа:
  \pause
\begin{lstlisting}
(define (nondivisor d) (lambda (n) (> (remainder n d) 0)))@\pause@

(define (sieve stream)
  (cons-stream (head stream)
               (sieve (filter-stream (nondivisor (head stream)) (tail stream)))))@\pause@

(define primes (sieve (from 2)))
\end{lstlisting}
\end{frame}
\end{document}