
%\documentclass[9pt,xcolor=dvipsnames,unknownkeysallowed]{beamer}
\documentclass[handout,9pt,xcolor=dvipsnames,unknownkeysallowed]{beamer}

\input{../Common/common}


\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing}



\title % (optional, use only with long paper titles)
{02157 Functional Programming}

\subtitle
{Lecture : Tail-recursive functions} % (optional)

\date {MRH 13/11/2024}% (optional)


\begin{document}

\begin{frame}
  \titlepage


\end{frame}




\begin{frame}{Overview}


Part I:
\begin{itemize}

\item Memory management: the stack and the heap

\medskip

\item<2-> Iterative (tail-recursive) functions is a simple technique to deal
with efficiency in certain situations, for example, in order 
\begin{itemize}
\item to avoid evaluations with a huge amount of {\redbrown
pending operations}, e.g.
\[\blue 7 {\redbrown +} (6 {\redbrown +} (5 \cdots {\redbrown +} f\ 2 \cdots ) ) \]

\medskip

\item<2-> to avoid inadequate use of \texttt{@} in recursive
declarations.
\end{itemize}

\medskip

\item<3-> Iterative functions with {\redbrown accumulating parameters} correspond to while-loops

\end{itemize}

\pause[4]
\bigskip

Part II: Continuation-based tail recursion


\end{frame}

\begin{frame}[fragile]\frametitle{Three factorial functions}
	
\begin{alltt}\blue 
// using "plain" recursion
let rec fact = function
               | 0 -> 1
               | n -> n * fact(n-1)

// using "tail" recursion: "fact n = factA(n,1)"
let rec factA(n,m) = match n with  
                     | 0 -> m
                     | _ -> factA(n-1,n*m) 

// using imperative features (while, assignment) 
let factW n = let ni = ref n
              let r  = ref 1
              while ni.Value>0 do
                 r.Value <- r.Value * ni.Value ; 
                 ni.Value <- ni.Value-1
              r.Value	
\end{alltt}
\end{frame}

\begin{frame}[fragile]
	\frametitle{Three factorial functions: Benchmarks}

\begin{itemize}
\item 13th Gen Intel(R) Core(TM) i7-1365U 1.80 GHz\\ 
x64-based processor, Windows 
\item Native code is generated using CLI:\\
dotnet publish -r win-x64 -c Release
\end{itemize}

\bigskip

Extract from benchmark report: 

\begin{alltt}\blue 
1.000000 computations of fact 16 are repeated 100 times. 
            Mean = 15,13 ms.  ...

1.000000 computations of factA(16,1) are repeated 100 times. 
           {\darkgreen Mean = 6,89 ms.}  ...

1.000000 computations of factW 16 are repeated 100 times. 
            Mean = 26,63 ms.  ... 
\end{alltt}

\pause 
\medskip 
\ \hfill {Program is uploaded to Learn}

\end{frame}

\begin{frame}[fragile]\frametitle{Two reversal functions with benchmarks}
	
\begin{alltt}\blue 
let rec naiveRev = function
                   | []    -> []
                   | x::xs -> naiveRev xs @ [x]

// "tail-recursive" function: revA(xs,[]) = naiveRev xs 
let rec revA = function
               | ([], ys)    -> ys
               | (x::xs, ys) -> revA(xs, x::ys)
\end{alltt}

Extract from benchmark report:
\begin{alltt}\blue
naive reverse of a list of size{\redbrown 5.000}
are repeated 100 times. 
                         Mean = 88,72 ms.  ... 

             
tail-recursive reverse of a list of size{\redbrown 500.000} 
are repeated 100 times. 
                        {\darkgreen Mean = 24,29 ms.}  ... 	
\end{alltt}

\end{frame}

\begin{frame}[fragile]
\frametitle{An example: Factorial function (I)}

Consider the following declaration:
\begin{alltt}
let rec fact = 
   function
   | 0 -> 1
   | n -> n * fact(n-1);;
\ett{val fact : int -> int}
\end{alltt}

\begin{itemize}
\item What {\redbrown resources} are needed to compute
$\mathtt{fact}(N)$?
\end{itemize}

\bigskip

\pause
Considerations:
\begin{itemize}
\item {\redbrown Computation time}: number of individual
computation steps. \item<3-> {\redbrown Space}: the maximal memory
needed during the computation to represent expressions and
bindings.
\end{itemize}

\end{frame}


\begin{frame}[fragile]
\frametitle{An example: Factorial function (II)}
Evaluation:
\[
\begin{array}{ll}
     & \verb/fact/(N) \\
\lto & \left(\verb/n * fact(n-1)/\ ,\ [\verb/n/ \mapsto N ]\right) \\
\lto & N * \verb/fact/(N-1) \\
\lto & N * \left(\verb/n * fact(n-1)/\ ,\ [\verb/n/ \mapsto N-1]\right) \\
\lto & N * ((N - 1) * \verb/fact/(N-2)) \\
 \vdots & \\
\lto & {\redbrown N * ((N -1) * ((N-2) * ( \cdots  (4 * (3 * (2 * 1))) \cdots ))) }\\
\lto & N * ((N-1) * ((N-2) * ( \cdots (4 * (3 * 2))  \cdots ))) \\
 \vdots & \\
\lto & N!
\end{array}
\]

\pause

Time and space demands: {\darkgreen proportional to $N$} \hfill
{\redbrown Is this satisfactory?}

\end{frame}

\begin{frame}[fragile]
\frametitle{Another example: Naive reversal (I)}

\begin{alltt}
let rec naiveRev = 
   function
   | []    -> []
   | x::xs -> naiveRev xs @ [x];;
\ett{val naiveRev : 'a list -> 'a list}
\end{alltt}

\medskip
\pause

Evaluation of $\verb-naiveRev-\, \verb/[/x_1, x_2, \ldots,
x_n\verb/]/$:
\[ \begin{array}{cl}
 & \verb-naiveRev-\, \verb/[/x_1, x_2, \ldots, x_n\verb/]/\\
\lto & \verb-naiveRev-\, \verb/[/x_2, \ldots, x_n\verb/]/ \verb-@- \verb/[/x_1\verb/]/ \\
\lto & (\verb-naiveRev-\, \verb/[/x_3, \ldots, x_n\verb/]/ \verb-@- \verb/[/x_2\verb/]/) \verb-@- \verb/[/x_1\verb/]/ \\
 \vdots &  \\
\lto  & (( \cdots ( ( \verb/[/\, \verb/]/ \verb-@-
\verb/[/x_n\verb/]/) \verb-@- \verb/[/x_{n-1}\verb/]/) \verb-@-
\cdots \verb-@- \verb/[/x_2\verb/]/ ) \verb-@- \verb/[/x_1\verb/]/
)
\end{array}
\]


Space demands: {\darkgreen proportional to $n$}
\hfill {\redbrown satisfactory}\\

\medskip
\pause

Time demands: {\darkgreen proportional to $n^2$} \hfill {\redbrown
not satisfactory}
\end{frame}


\begin{frame}[fragile]
\frametitle{Examples: Accumulating parameters}

{\redbrown Efficient} solutions are obtained by using
{\em\darkgreen more general functions}:
\[\blue
\begin{array}{lll}
\verb-factA-(n,{\darkgreen m}) & = & n! \cdot {\darkgreen m},\ \mbox{for $n\geq 0$}\\
\verb-revA-(\verb/[/x_1, \ldots, x_n\verb/]/, \mathit{\darkgreen
ys}) & = & \verb/[/x_n, \ldots, x_1\verb/]/\, \verb-@-
\mathit{\darkgreen ys}
\end{array}
\]
We have:
\[\blue
\begin{array}{lll}
n! & = & \verb-factA-(n,1)\\
\verb-rev-\, \verb/[/x_1, \ldots, x_n\verb/]/ & = &
\verb-revA-(\verb/[/x_1, \ldots, x_n\verb/]/, \verb/[/\,
\verb/]/)
\end{array}
\]

\pause

$\darkgreen m$ and $\darkgreen \mathit{ys}$ are called
{\em\darkgreen accumulating parameters}. They are used to hold the
temporary result during the evaluation.
\end{frame}


\begin{frame}[fragile]
\frametitle{Declaration of \texttt{factA}}
Property:  $\verb-factA-(n,{\darkgreen m}) = n! \cdot {\darkgreen m}$,\ \mbox{for $n\geq 0$}

\medskip

\begin{alltt}
let rec factA = 
   function
   | (0,m) -> m
   | (n,m) -> factA(n-1,n*m);;
\end{alltt}

An evaluation:
\[
\begin{array}{ll}
     & \verb/factA(5,1)/ \\
%\lto & (\verb/factA(n,m)/ ,\
%         [\verb/n/ \mapsto 5, \verb/m/ \mapsto 1 ] ) \\
\lto & (\verb/factA(n-1,n*m)/\! , \
         [\verb/n/ \mapsto 5, \verb/m/ \mapsto 1 ] ) \\
\lto & {\redbrown \verb/factA(4,5)/} \\
%\lto & (\verb/factA(n,m)/ ,\
%         [\verb/n/ \mapsto 4, \verb/m/ \mapsto 5 ] ) \\
\lto & (\verb/factA(n-1,n*m)/\! ,\
         [\verb/n/ \mapsto 4, \verb/m/ \mapsto 5 ] ) \\
\lto & {\redbrown \verb/factA(3,20)/} \\
\lto & \ldots  \\
\lto & \verb/factA(0,120)/ \lto  (\verb/m/ ,\
         [\verb/m/ \mapsto 120 ] )
\lto  120
\end{array}
\]
\medskip

Space demand: {\darkgreen constant}.

\medskip

Time demands: {\darkgreen proportional to $n$}
\end{frame}

\begin{frame}[fragile]
\frametitle{Declaration of \texttt{revA}}

Property: $\verb-revA-(\verb/[/x_1, \ldots, x_n\verb/]/, \mathit{\darkgreen
ys})  =  \verb/[/x_n, \ldots, x_1\verb/]/\, \verb-@-
\mathit{\darkgreen ys}$

\medskip

\begin{alltt}
let rec revA = 
   function
   | ([], ys)    -> ys
   | (x::xs, ys) -> revA(xs, x::ys);;
\end{alltt}

An evaluation:
\[
\begin{array}{ll}
     & \verb/revA([1,2,3],[])/ \\
\lto & \verb/revA([2,3],1::[])/ \\
%\lto & \verb/revA([2,3],[1])/ \\
\lto  & \verb/revA([3],2::[1])/ \\
\lto & \verb/revA([3],[2,1])/ \\
\lto  & \verb/revA([],3::[2,1])/ \\
\lto & \verb/revA([],[3,2,1])/ \\
\lto & \verb/[3,2,1]/
\end{array}
\]

\medskip

Space and time demands:\\
\qquad \qquad {\darkgreen proportional to $n$ (the length of the
first list)}
\end{frame}


\begin{frame}{Iterative (tail-recursive) functions (I)}

The declarations of \texttt{factA} and \texttt{revA} are
{\em\darkgreen tail-recursive functions}

\begin{itemize}
\item<2-> the recursive call is the {\em\darkgreen last function
application} to be evaluated in the body of the declaration e.g.
$\blue facA(3,20)$ and $\blue revA([3],[2,1])$

\item<3-> only {\em\redbrown one set} of bindings for argument
identifiers is needed during the evaluation
\end{itemize}


\end{frame}



\begin{frame}[fragile]
\frametitle{Example}

\begin{alltt}
let rec factA = 
   function
   | (0,m) -> m
   | (n,m) ->{\darkgreen factA(n-1,n*m)}
             {\redbrown (* recursive "tail-call" *)}
\end{alltt}


%\fromFrame{2}{
\begin{itemize}
\item only one set of bindings for argument identifiers is needed
during the evaluation
\end{itemize}
%\vspace*{-3mm}
\[
\begin{array}{ll}
     & \verb/factA(5,1)/ \\
\lto & (\verb/factA(n,m)/ ,\
         {\blue [\verb/n/ \mapsto 5, \verb/m/ \mapsto 1 ]} ) \\
\lto & (\verb/factA(n-1,n*m)/\! , \
         {\blue [\verb/n/ \mapsto 5, \verb/m/ \mapsto 1 ]} ) \\
\lto & \verb/factA(4,5)/ \\
\lto & (\verb/factA(n,m)/ ,\
         {\blue [\verb/n/ \mapsto 4, \verb/m/ \mapsto 5 ]} ) \\
\lto & (\verb/factA(n-1,n*m)/\! ,\
         {\blue [\verb/n/ \mapsto 4, \verb/m/ \mapsto 5 ]} ) \\
%\lto & \verb/factA(3,20)/ \\
\lto & \ldots  \\
\lto & \verb/factA(0,120)/ \lto  (\verb/m/ ,\
         {\blue [ \verb/m/ \mapsto 120 ]} )
\lto  120
\end{array}
\]

\end{frame}




\begin{frame}[fragile]
\frametitle{Concrete resource measurements: factorial functions}

%Use the toggle \verb-#time- in the interactive environment:

\begin{alltt}\blue
let xs16 = List.init 1000000 (fun i -> 16);;
\ett{val xs16 : int list = [16; 16; 16; 16; 16; ...]}

\redbrown{#time};; // a toggle in the interactive environment
\blue
for i in xs16 do let _ = fact i in ();;
\ett{Real: 00:00:00.051, CPU: 00:00:00.046, ...}

for i in xs16 do let _ = factA(i,1) in ();;
\ett{Real: 00:00:00.024, CPU: 00:00:00.031, ... }
\end{alltt}
\onslide<2->
The performance gain of \texttt{factA} is much better than the indicated factor 2
because the \texttt{for} construct alone uses about 12 ms:
\begin{alltt}\blue
for i in xs16 do let _ = () in ();;
\ett{Real: 00:00:00.012, CPU: 00:00:00.015, ... }
\end{alltt}

\medskip

\onslide<1->
\begin{center}
Real: time elapsed by the execution. \quad
CPU: time spent by all cores.
\end{center}

\ \hfill {\darkgreen Timing measured on an old system}
\end{frame}

\begin{frame}[fragile]
\frametitle{Concrete resource measurements: reverse functions}

\begin{alltt}\blue
let xs20000 = [1 .. 20000];;

naiveRev xs20000;;
\ett{Real:{\redbrown 00:00:07.624}, CPU: 00:00:07.597,}
\ett{GC gen0:{\redbrown 825}, gen1:{\redbrown 253}, gen2: 0}
\ett{val it : int list = [20000; 19999; 19998; ...]}

revA(xs20000,[]);;
\ett{Real:{\darkgreen 00:00:00.001}, CPU: 00:00:00.000, }
\ett{GC gen0: 0, gen1: 0, gen2: 0}
\ett{val it : int list = [20000; 19999; 19998; ...]}
\end{alltt}

\begin{itemize}
\item<2-> The naive version takes {\redbrown 7.624 seconds} - the iterative just {\darkgreen 1 ms}.

\item<3-> The use of append (\texttt{@}) has been reduced to a use of cons (\texttt{::}).
This has a dramatic effect of the garbage collection:
\begin{itemize}
\item No object is reclaimed when \texttt{revA} is used
\item {\redbrown{825+253}} obsolete objects were reclaimed using the naive version
\end{itemize}
\end{itemize}
\pause[3]
\ \hfill {\redbrown Measured on the computer used in 2012}

\medskip
\pause[4]
\begin{center}
Let's look at memory management
\end{center}
\end{frame}

\begin{frame}[fragile]
\frametitle{Memory management: stack and heap}
\begin{itemize}
\item Primitive values are allocated on the stack
\item Composite values are allocated on the heap
\end{itemize}

\begin{alltt}
let xs = [5;6;7];;
let ys = 3::4::xs;;
let zs = xs @ ys;;
let n = 27;;
\end{alltt}

\pause

\begin{tikzpicture}

%\draw (4,3.75) node{\conscell{5}};
\draw (3.5,3.5) rectangle +(1,0.5); \draw (4,3.5) -- (4, 4); \draw (3.75,3.75) node{$5$};
%\draw (6,3.75) node{\conscell{6}};
\draw (5.5,3.5) rectangle +(1,0.5); \draw (6,3.5) -- (6, 4); \draw (5.75,3.75) node{$6$};
%\draw (8,3.75) node{\conscellLast{7}};
\draw (7.5,3.5) rectangle +(1,0.5); \draw (8,3.5) -- (8, 4); \draw (7.75,3.75) node{$7$}; \draw (8.25,3.75) node{$\times$};

\draw[->] (4.25,3.75) -- (5.5,3.75); \draw[->] (6.25,3.75) -- (7.5,3.75);


%\draw (4,2.50) node{\conscell{3}};
\draw (3.5,2.25) rectangle +(1,0.5); \draw (4,2.25) -- (4, 2.75); \draw (3.75,2.5) node{$3$};

%\draw (6,2.50) node{\conscell{4}};
\draw (5.5,2.25) rectangle +(1,0.5); \draw (6,2.25) -- (6, 2.75); \draw (5.75,2.5) node{$4$};

\draw[->] (4.25,2.5) -- (5.5,2.5);

\draw[->,rounded corners=8pt] (6.25,2.5) .. controls (6.25,3) .. (5,3) -- (3.2,3) .. controls (2.75,3.0) and (2.75,3.6)  .. (3.2,3.6) -- (3.5,3.6) ;

\draw (3.5,1) rectangle +(1,0.5); \draw (4,1) -- (4, 1.5); \draw (3.75,1.25) node{$5$};
\draw (5.5,1) rectangle +(1,0.5); \draw (6,1) -- (6, 1.5); \draw (5.75,1.25) node{$6$};
\draw (7.5,1) rectangle +(1,0.5); \draw (8,1) -- (8, 1.5); \draw (7.75,1.25) node{$7$};

\draw[->] (4.25,1.25) -- (5.5,1.25); \draw[->] (6.25,1.25) -- (7.5,1.25);

\draw[->,rounded corners=8pt] (8.25,1.25) .. controls (8.25,1.75) .. (5,1.75) -- (3.2,1.75) .. controls (2.75,1.75) and (2.75,2.35)  .. (3.2,2.35) -- (3.5,2.35) ;

\draw[->] (1.25,2.75) .. controls (2.5,3.85) .. (3.5,3.85);

\draw[->] (1.25,2.25) .. controls (2.5,2.6) .. (3.5,2.6);

\draw[->] (1.25,1.75) .. controls (2.5,1.25) .. (3.5,1.25);

%\draw[->] (1.25,1.25) .. controls (2.5,0) .. (3.5,0.0);

\draw [decorate,decoration={brace,amplitude=10pt},yshift=4pt,xshift=0pt]
(0.5,4.2) -- (1.85,4.2) node [black,midway,yshift=0.7cm]
{stack};

\draw [decorate,decoration={brace,amplitude=10pt},yshift=4pt,xshift=0pt]
(2.7,4.2) -- (8.75,4.2) node [black,midway,yshift=0.7cm]
{heap};

\draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt]
(0.5,1) -- (0.5,3) node [black,midway,xshift=-1.3cm]
{stack frame};


\draw (1.25,1.25) node{$\mathtt{27}$};
\draw (0.65,1.25) node{$\mathtt{n}$};
\draw (0.65,1.75) node{$\mathtt{zs}$};
\draw (0.65,2.25) node{$\mathtt{ys}$};
\draw (0.65,2.75) node{$\mathtt{xs}$};

\draw (1,1) -- (1,3) -- (1.5,3) -- (1.5,1) -- cycle;;
{\foreach \x in {0.5,1,1.5}
 { \draw[dashed] (1,1+\x) --  (1.5,1+\x); }} ;

\end{tikzpicture}
\end{frame}

\begin{frame}{Observations}

No {\darkgreen unnecessary copying} is done:
\begin{enumerate}
\item The linked lists for $\mathit{ys}$ is not copied when building a linked list for $y::\mathit{ys}$.
\item Fresh cons cells are made for the elements of $\mathit{xs}$ only when building a linked list for
$\mathit{xs}\, \texttt{@}\, \mathit{ys}$.
\end{enumerate}

\medskip

\begin{center}\redbrown
since a list is a functional (immutable) data structure
\end{center}

\bigskip
\pause
The running time of \texttt{@} is linear in the length of its first argument.

\end{frame}

\begin{frame}[fragile]
\frametitle{Operations on stack and heap}

Example:
\begin{alltt}
let zs = let xs = [1;2]
         let ys = [3;4]
         xs@ys;;
\end{alltt}

\medskip

Initial stack and heap prior to the evaluation of the local declarations:

\begin{tikzpicture}

\draw [decorate,decoration={brace,amplitude=8pt},yshift=4pt,xshift=0pt]
(0.5,1.8) -- (1.85,1.8) node [black,midway,yshift=0.7cm]
{stack};

\draw [decorate,decoration={brace,amplitude=10pt},yshift=4pt,xshift=0pt]
(2.7,1.8) -- (6.75,1.8) node [black,midway,yshift=0.7cm]
{heap};

\draw [decorate,decoration={brace,amplitude=4pt},xshift=-3pt,yshift=0pt]
(0.5,1.0) -- (0.5,1.5) node [black,midway,xshift=-.6cm]
{$\mathrm{sf}_0$};

\draw (0.65,1.25) node{$\mathtt{zs}$}; \draw (1.25,1.25) node{$?$};

\draw (1,1) -- (1,1.5) -- (1.5,1.5) -- (1.5,1) -- cycle;;

\end{tikzpicture}

\end{frame}

\begin{frame}[fragile]
\frametitle{Operations on stack: Push}

Example:
\begin{alltt}
let zs = let xs = [1;2]
         let ys = [3;4]
         xs@ys;;
\end{alltt}


Evaluation of the local declarations initiated by {\blue pushing} a new stack frame onto the stack:

\medskip

\begin{tikzpicture}
\draw [decorate,decoration={brace,amplitude=8pt},yshift=4pt,xshift=0pt]
(0.5,3) -- (1.85,3) node [black,midway,yshift=0.7cm]
{stack};

\draw [decorate,decoration={brace,amplitude=10pt},yshift=4pt,xshift=0pt]
(2.7,3) -- (6.75,3) node [black,midway,yshift=0.7cm]
{heap};

\draw [decorate,decoration={brace,amplitude=4pt},xshift=-3pt,yshift=0pt]
(-0.2,1.0) -- (-0.2,1.5) node [black,midway,xshift=-.6cm]
{$\mathrm{sf}_0$};

\draw [decorate,decoration={brace,amplitude=6pt},xshift=-2pt,yshift=0pt]
(-0.2,1.6) -- (-0.2,2.9) node [black,midway,xshift=-.5cm]
{$\mathrm{sf}_1$};


\draw (0.65,2.75) node{$\mathtt{xs}$};  %\draw (1.25,2.75) node{$2$};
\draw (0.65,2.25) node{$\mathtt{ys}$};
%\draw (0.3,1.75) node{``$\mathtt{xs} \texttt{@} \texttt{ys}$''};
\draw (0.37,1.75) node{$\textit{result}$};

\draw (0.65,1.25) node{$\mathtt{zs}$}; \draw (1.25,1.25) node{$?$};

\draw (1,1) -- (1,1.5) -- (1.5,1.5) -- (1.5,1) -- cycle;

\draw (1,1.5) -- (1,3) -- (1.5,3) -- (1.5,1.5) -- cycle;

{\foreach \x in {0.5,1}
 { \draw[dashed] (1,1.5+\x) --  (1.5,1.5+\x); }} ;

\draw[->] (1.25,2.75) -- (3.5,2.75); \draw[->] (4.25,2.75) -- (5.5,2.75);
\draw (3.5,2.5) rectangle +(1,0.5); \draw (4,2.5) -- (4, 3.0); \draw (3.75,2.75) node{$1$};
\draw (5.5,2.5) rectangle +(1,0.5); \draw (6,2.5) -- (6, 3.0); \draw (5.75,2.75) node{$2$}; \draw (6.25,2.75) node{$\times$};
\draw[->] (1.25,2.25) -- (3.5,2); \draw[->] (4.25,2) -- (5.5,2);
\draw (3.5,1.75) rectangle +(1,0.5); \draw (4,1.75) -- (4, 2.25); \draw (3.75,2) node{$3$};
\draw (5.5,1.75) rectangle +(1,0.5); \draw (6,1.75) -- (6, 2.25); \draw (5.75,2) node{$4$}; \draw (6.25,2) node{$\times$};

\draw[->] (1.25,1.75) -- (3.5,1.25); \draw[->] (4.25,1.25) -- (5.5,1.25);
\draw (3.5,1) rectangle +(1,0.5); \draw (4,1) -- (4, 1.5); \draw (3.75,1.25) node{$1$};
\draw (5.5,1) rectangle +(1,0.5); \draw (6,1) -- (6, 1.5); \draw (5.75,1.25) node{$2$};

\draw[->,rounded corners=8pt] (6.25,1.25) .. controls (6.25,1.65) .. (4.5,1.65) -- (3,1.65) .. controls (2.6,1.65) and (2.6,1.85)  .. (3,1.85) -- (3.5,1.85);

\end{tikzpicture}

\bigskip

The auxiliary entry {\redbrown result} refers to the value of the \verb:let:-expression.

\end{frame}

\begin{frame}[fragile]
\frametitle{Operations on stack: Pop}

Example:
\begin{alltt}
let zs = let xs = [1;2]
         let ys = [3;4]
         xs@ys;;
\end{alltt}


The top stack frame is {\blue popped} from the stack when the evaluation of the \verb:let:-expression is completed:

\medskip

\begin{center}
\begin{tikzpicture}

\draw [decorate,decoration={brace,amplitude=8pt},yshift=4pt,xshift=0pt]
(0.5,3) -- (1.85,3) node [black,midway,yshift=0.7cm]
{stack};

\draw [decorate,decoration={brace,amplitude=10pt},yshift=4pt,xshift=0pt]
(2.7,3) -- (6.75,3) node [black,midway,yshift=0.7cm]
{heap};

\draw [decorate,decoration={brace,amplitude=4pt},xshift=-3pt,yshift=0pt]
(0.4,1.0) -- (0.4,1.5) node [black,midway,xshift=-.6cm]
{$\mathrm{sf}_0$};

\draw (0.65,1.25) node{$\mathtt{zs}$}; %\draw (1.25,1.25) node{$?$};

\draw (1,1) -- (1,1.5) -- (1.5,1.5) -- (1.5,1) -- cycle;

\draw (3.37,3) node{$\dag$};\draw (5.37,3) node{$\dag$};

\draw[->] (4.25,2.75) -- (5.5,2.75);
\draw (3.5,2.5) rectangle +(1,0.5); \draw (4,2.5) -- (4, 3.0); \draw (3.75,2.75) node{$1$};
\draw (5.5,2.5) rectangle +(1,0.5); \draw (6,2.5) -- (6, 3.0); \draw (5.75,2.75) node{$2$}; \draw (6.25,2.75) node{$\times$};

\draw[->] (4.25,2) -- (5.5,2);
\draw (3.5,1.75) rectangle +(1,0.5); \draw (4,1.75) -- (4, 2.25); \draw (3.75,2) node{$3$};
\draw (5.5,1.75) rectangle +(1,0.5); \draw (6,1.75) -- (6, 2.25); \draw (5.75,2) node{$4$}; \draw (6.25,2) node{$\times$};

\draw[->] (1.25,1.25) -- (3.5,1.25); \draw[->] (4.25,1.25) -- (5.5,1.25);
\draw (3.5,1) rectangle +(1,0.5); \draw (4,1) -- (4, 1.5); \draw (3.75,1.25) node{$1$};
\draw (5.5,1) rectangle +(1,0.5); \draw (6,1) -- (6, 1.5); \draw (5.75,1.25) node{$2$};

\draw[->,rounded corners=8pt] (6.25,1.25) .. controls (6.25,1.65) .. (4.5,1.65) -- (3,1.65) .. controls (2.6,1.65) and (2.6,1.85)  .. (3,1.85) -- (3.5,1.85);

\end{tikzpicture}
\end{center}

\bigskip

The resulting heap contains two {\redbrown obsolete} cells marked with  '$\dag$'
\end{frame}

\begin{frame}[fragile]
\frametitle{Operations on the heap: Garbage collection}

The memory management system uses a {\em garbage collector} to reclaim obsolete cells in the heap behind the scene.

\bigskip

The garbage collector manages the heap as partitioned  into three groups or
{\em generations}: \texttt{gen0}, \texttt{gen1} and \texttt{gen2}, according to their
age. The objects in \texttt{gen0} are the youngest while the objects in \texttt{gen2}
are the oldest.

\bigskip
\pause

The typical situation is that objects die young and the garbage collector is designed for
that situation.

\bigskip
Example:
\begin{alltt}\blue
naiveRev xs20000;;
\ett{Real: 00:00:07.624, CPU: 00:00:07.597,}
\ett{GC gen0:{\redbrown 825}, gen1:{\redbrown 253}, gen2: 0}
\ett{val it : int list = [20000; 19999; 19998; ...]}
\end{alltt}



\end{frame}

\begin{frame}[fragile]
\frametitle{The limits of the stack and the heap}

The stack is big:
\begin{alltt}\blue
let rec bigList n = if n=0 then [] else 1::bigList(n-1);;
bigList 120000;;
\ett{val it : int list = [1; 1; 1; 1; 1; 1; 1; 1;...]}
bigList 130000;;
\ett{Process is terminated due to StackOverflowException.}
\end{alltt}
More than $\darkgreen 1.2 \cdot 10^5$ stack frames are pushed in recursive calls.

\pause
\bigskip
The heap is much bigger:
\begin{alltt}\blue
let rec bigListA n xs = if n=0 then xs
                        else bigListA (n-1) (1::xs);;
let xsVeryBig = bigListA 12000000 [];;
\ett{val xsVeryBig : int list = [1; 1; 1; 1; 1; 1;...]}
let xsTooBig = bigListA 13000000 [];;
\ett{System.OutOfMemoryException: ...}
\end{alltt}
A list with more than $\darkgreen 1.2 \cdot 10^7$ elements can be created.

\pause
\bigskip
The iterative \verb-bigListA- function does not exhaust the stack. {\redbrown WHY?}

\end{frame}



\begin{frame}[fragile]
\frametitle{Iterative (tail-recursive) functions (II)}

Tail-recursive functions are also called {\darkgreen\em iterative
functions}.
\begin{itemize}
\item The function {\redbrown $f(n,m) = (n-1,n*m)$} is iterated
during evaluations for \texttt{factA}.

\item<2-> The function {\blue $g(x::xs,ys) = (xs, x::ys)$} is
iterated during evaluations for \texttt{revA}.
\end{itemize}

\pause[3]

The correspondence between tail-recursive functions and while
loops is established in the textbook.

\medskip

\pause[4]

An example: {\blue
\begin{alltt}
let factW n =
    let ni = ref n
    let r  = ref 1
    while !ni>0 do
         r := !r * !ni ; ni := !ni-1
    !r;;
\end{alltt}
}
\end{frame}

\begin{frame}[fragile]
	\frametitle{Iteration vs While loops}
	
	Iterative functions are executed efficiently:
	\begin{alltt}\blue
		#time;;
		
		for i in 1 .. 1000000 do let _ = factA(16,1) in ();;
		\ett{Real: 00:00:00.024, CPU: 00:00:00.031, }
		\ett{GC gen0: 0, gen1: 0, gen2: 0}
		\ett{val it : unit = ()}
		
		for i in 1 .. 1000000 do let _ = factW 16 in ();;
		\ett{Real: 00:00:00.048, CPU: 00:00:00.046, }
		\ett{GC gen0: 9, gen1: 0, gen2: 0}
		\ett{val it : unit = ()}
	\end{alltt}
	
	\bigskip
	
	\begin{itemize}
		\item<2-> the tail-recursive function actually is faster than the imperative while-loop based version
	\end{itemize}
\end{frame}




\begin{frame}
\begin{center}\Large\darkgreen Characterizing tail-recursive functions syntactically
	\end{center}	


\end{frame}

\begin{frame}[fragile]\frametitle{Tail position - briefly}



Consider expressions of the form:
\begin{alltt}\blue 
	if \( e\sb{a} \) then \( e\sb{1} \) else \( e\sb{2} \)
	
	\( e\sb{1} e\sb{a} \)
	
	fun \( x \to e\sb{1} \) 
	
	let \( x = e\sb{a} \) in \( e\sb{1} \) 
	
	match \( e\sb{a} \) with  | \( pat\sb{1} \to e\sb{1} \) ... | \( pat\sb{n} \to e\sb{n} \)
	
	\( e\sb{a} + e\sb{b} \)
	
	\( primitive \)
\end{alltt}

\pause

\begin{itemize}
	\item $\blue e_1, \ldots, e_n$ and $\blue primitive$ are in {\redbrown tail position}, where $\blue primitive$ is a variable or a constant.
	\item  $\blue e_a$ and $\blue e_b$ are not in tail position	
	\item patterns are ``binders'' like $\blue \verb|fun|\ x \to \ldots$ and not in tail position.
	
\end{itemize}

\medskip

\pause
Complete definition includes sub-expressions

\end{frame}

\begin{frame}[fragile]\frametitle{Tail calls and tail recursion}  

\begin{itemize}
\item A function call in tail position is said to be a {\redbrown tail call}
\end{itemize}

\medskip

Calls to $\blue \mathrm{f}$ are tail calls (calls to $\blue \mathrm{g, h}$ are not) in:

\begin{alltt}\blue 
f (3+4)

if x>0 then f(g(9)) else g 1 + h 6

fun x -> f (x+1)

match g(a+b) with 
| []     -> f a
| x::xs	 -> g(x)::h xs 

let x = g y in f(if x=0 the g z else g 2)
\end{alltt}

\bigskip
\pause


%Lesson from last lecture:
\begin{itemize}\redbrown 
\item Tail calls can be implemented without adding a new stack frame
\end{itemize} 

\pause
\bigskip

\begin{itemize}
\item A {\redbrown tail recursive function} is a recursive function where every recursive call is a tail call
\end{itemize}
\end{frame}

\begin{frame}[fragile]\frametitle{A simple example}

The function {\blue fact} is not tail recursive:
\begin{alltt}\blue 
let rec fact = 
   function
   | 0 -> 1
   | n -> n * fact(n-1)
\end{alltt}
\begin{itemize}
\item The recursive call is not a tail call in {\blue \verb|n * fact(n-1)|}
\end{itemize}

\bigskip
\pause

But  {\blue factA} is tail recursive:
\begin{alltt}\blue 
let rec factA = 
   function
   | (0,m) -> m
   | (n,m) -> factA(n-1,n*m) 
\end{alltt}

\begin{itemize}
\item  The recursive call is a tail call in\\
\qquad {\blue \verb|(n,m) -> factA(n-1,n*m)|}
\end{itemize}


\end{frame}


\begin{frame}{Part 1: Summary}

\begin{itemize}
	
	\item Memory management: the stack and the heap
	
	\medskip
	
	\item<2-> Iterative (tail-recursive) functions is a simple technique to deal
	with efficiency in certain situations, for example, in order 
	\begin{itemize}
		\item to avoid evaluations with a huge amount of {\redbrown
			pending operations}, e.g.
		\[\blue 7 {\redbrown +} (6 {\redbrown +} (5 \cdots {\redbrown +} f\ 2 \cdots ) ) \]
		
		\medskip
		
		\item<2-> to avoid inadequate use of \texttt{@} in recursive
		declarations.
	\end{itemize}
	
	\medskip
	
	\item<3-> Iterative functions with {\redbrown accumulating parameters} correspond to while-loops
	
\end{itemize}

\pause[4]
\bigskip

\begin{center}
	\darkgreen A simple and useful technique to consider when bottlenecks are spotted
\end{center}

\end{frame}


\begin{frame}
\begin{center}
	\Large\darkgreen Part II\\
	Continuation-based tail recursion
\end{center}
\end{frame}

\begin{frame}[fragile]
\frametitle{Limitation of accumulating parameters} 
Tail-recursive versions of recursive functions {\redbrown CANNOT} be obtained using accumulating parameters in all cases. 

\medskip
Consider for example:
\begin{alltt}\blue
type BinTree<'a> = | Leaf
                   | Node of BinTree<'a>*'a*BinTree<'a>
	
let rec count = function
                | Leaf          -> 0
                | Node(tl,n,tr) -> count tl + count tr + 1
\end{alltt}

\bigskip
\pause

A counting function:
\begin{alltt}\redbrown
countA: int -> BinTree<'a> -> int
\end{alltt}
using an accumulating parameter will {\redbrown not be tail-recursive} due to the expression
containing recursive calls on the left and right sub-trees. (Ex. 9.8)
\end{frame}



\begin{frame}[fragile]
\frametitle{Continuations}

{\blue Continuation}: A representation of the ``rest'' of the computation.

\medskip
\pause

{\darkgreen Every} functional program can automatically be turned into a program where every call is a tail call using continuations.

\medskip
\pause

We take an example-based approach. Consider
\begin{alltt}\blue
let rec sum xs = match xs with
                 | []      -> 0
                 | x::tail ->{\redbrown let v =} sum tail
                             {\redbrown x+v} 	
\end{alltt}

\pause

The continuation-based version of $\blue \verb|sum|$ has a continuation
\begin{alltt}\darkgreen
k: int -> int
\end{alltt}
as an extra argument. Determines what happens with the result.

\pause
\medskip

\begin{alltt}\blue
let rec sumC xs {\darkgreen k} = 
   match xs with
   | []      ->{\darkgreen k} 0
   | x::tail -> sumC tail{\redbrown (fun v ->{\darkgreen k}(x+v))}
\end{alltt}

\pause
\medskip
\begin{itemize}
\item all calls of $\blue \verb|sumC|$ and $\darkgreen \verb|k|$ are tail calls
\item can be implemented without adding a new stack frame	
\end{itemize}


\end{frame}

\begin{frame}[fragile]
\frametitle{An evaluation}

\[\blue
\begin{array}{ll}
&      \verb-sumC [1;2;3] id-\\
\lto &  \verb!sumC [2;3] (fun v -> id(1+v))!\\
\lto &  \verb!sumC [3] (fun w -> (fun v -> id(1+v))(2+w))!\\
\lto &  \verb!sumC [] (fun u -> (fun w -> (fun v -> id(1+v))(2+w))(3+u))!\\
\lto &  \verb!(fun u -> (fun w -> (fun v -> id(1+v))(2+w))(3+u)) 0!\\
\lto &  \verb!(fun w -> (fun v -> id(1+v))(2+w)) 3!\\
\lto &  \verb!(fun v -> id(1+v)) 5!\\
\lto &   \verb!id 6!\\
\lto &   \verb!6!\\
\end{array}
\]
\pause

Notice:
\begin{itemize}
\item {\redbrown Closures} are allocated in the heap.
\item Just one stack frame is needed due to tail calls.
\item Stack is traded for heap.
\end{itemize}
\end{frame}



\begin{frame}[fragile]
\frametitle{A more efficient way}

Consider the following version using an accumulating parameter:
\begin{alltt}\blue
let rec sumA xs n = match xs with
                    | []      -> n
                    | x::tail -> sumA tail (x+n)
\end{alltt}

\medskip

\begin{itemize}
\item uses constant space and is much more efficient than
\end{itemize}


\begin{alltt}\blue
let rec sumC xs k = match xs with
                    | []     -> k 0
                    | x::tail-> sumC tail (fun v -> k(x+v))
\end{alltt}

Some relationships between {\blue \verb-sum-}, {\blue \verb-sumA-} and {\blue \verb|sumC|}:

\pause


\[\blue
\begin{array}{ll}
1. &  \mathtt{sum}\ \mathit{xs}\ = \mathtt{sumC}\ \mathit{xs}\ \mathit{id}\\
2. &  \mathtt{sumA}\ \mathit{xs}\ 0 = \mathtt{sumC}\ \mathit{xs}\ \mathtt{id}
\end{array}
\]

\pause
\medskip

Proof: Structural induction over lists\\
Validation: Use property-based testing



\end{frame}





\begin{frame}[fragile]
\frametitle{Continuations: Another example}

\begin{alltt}\blue
let rec bigList n = if n=0 then [] else 1::bigList(n-1);;
\end{alltt}

The continuation-based version of \texttt{bigList} has a continuation
\begin{alltt}\redbrown
k: int list -> int list
\end{alltt}
as argument:
\begin{alltt}\blue
let rec bigListC n k =
   if n=0 then k []
   else bigListC (n-1) (fun res -> k(1::res));;
\ett{val bigListC : int -> (int list -> 'a) -> 'a}
\end{alltt}

\medskip
\begin{itemize}
\item<2-> Base case: ``feed'' the result into the continuation \texttt{\blue k}.
\medskip
\item<3-> Recursive case: The continuation after processing \texttt{\blue (n-1)} is the function of the result \texttt{\blue res} that
\begin{itemize}
\item<4-> builds the list \texttt{\blue 1::res} and

\item<4-> feeds that list into the continuation \texttt{\blue k}.
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Observations}

\begin{itemize}
\item \texttt{\blue bigListC} is a tail-recursive function, and
\item<2-> the calls of \texttt{\blue k} are tail calls in the base case of \texttt{\blue bigListC} and in
the continuation:
\texttt{\blue fun res -> k(1::res)}.
\end{itemize}

\pause[3]
\bigskip

The stack will hence neither grow due to the evaluation of recursive
calls of \texttt{\blue bigListC} nor due to calls of the continuations
that have been built in the heap:
\begin{alltt}\blue
bigListC 16000000 id;;
\ett{Real: 00:00:08.586, CPU: 00:00:08.314,}
\ett{GC gen0: 80, gen1: 60, gen2: 3}
\ett{val it : int list = [1;\;1;\;1;\;1;\;1;...]}
\end{alltt}
\begin{itemize}
\item Slower than \texttt{\blue bigList}
\item Can generate longer lists than \texttt{\blue bigList}
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Towards a tail-recursive count version}
Remember:	
\begin{alltt}\blue
let rec count t = match t with
                  | Leaf          -> 0
                  | Node(tl,n,tr) -> let v1 = count tl
                                     let v2 = count tr
                                     1+v1+v2 
\end{alltt}

\pause
\bigskip

For a continuation- based version $\blue\verb|countC|\ t\ k$:
\medskip

\begin{itemize}
\item<2-> $\blue k$ is the top-level continuation
\medskip

\item<2-> $\blue k$ is the continuation used for the base case:  $\blue k\ 0$
\medskip

\item<3-> The continuation {\darkgreen k2} for the second recursive call is
\begin{alltt}\blue
fun v2 -> k(1+v1+v2)
\end{alltt}
\medskip

\item<4-> The continuation {\darkgreen k1} for the first recursive call  is
\begin{alltt}\blue
fun v1 -> countC tr{\darkgreen k2}
\end{alltt}
\end{itemize}
\medskip
\pause[5]

Hence, the recursive case is:
\begin{alltt}\blue
countC tl (fun v1 -> countC tr (fun v2 -> k(1+v1+v2)))
\end{alltt}


\end{frame}

\begin{frame}[fragile]
\frametitle{A tail-recursive count}
Putting the pieces together:
\begin{alltt}\blue
let rec countC t k =
  match t with
  | Leaf          -> k 0
  | Node(tl,n,tr) ->
     countC tl (fun vl -> countC tr (fun vr -> k(1+vl+vr)))
\end{alltt}

\pause
\bigskip

\begin{itemize}
\item Both calls of \texttt{\blue countC} are tail calls
\item The two calls of \texttt{\blue k} are tail calls
\end{itemize}
Hence, the stack will not grow when evaluating $\blue\mathtt{\blue countC}\ t\ k$; but the heap will.

\bigskip
\pause

\begin{itemize}
\item \texttt{\blue countC} can handle bigger trees than \texttt{\blue count}
\item \texttt{\blue count} is faster
\end{itemize}

\end{frame}

\begin{frame}{Part II: Summary}

On continuations
\begin{itemize}


\item a technique to turn arbitrary recursive functions into tail-recursive ones.

\item trade stack for heap



\end{itemize}

\end{frame}



\end{document}

    
