1.3-scheme_highorder.tex

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

% пример за правило на Хорнер и ляво натрупване
\newboolfalse{horner}

% извеждане на Y комбинатора
\newboolfalse{ycomb}

% компилация по части
\newbooltrue{parts}

% взели ли сме вече наредени двойки?
\newbooltrue{pairs}

\ifbool{parts}{
    \newbool{part1}
    \newbool{part2}
    \IfEndWith*{\JobName}{part1}{\booltrue{part1}}{
      \IfEndWith*{\JobName}{part1-trans}{\booltrue{part1}}{
        \IfEndWith*{\JobName}{part2}{\booltrue{part2}}{
          \IfEndWith*{\JobName}{part2-trans}{\booltrue{part2}}{
            \IfEndWith*{\JobName}{-trans}{}{
              % в общия случай пускаме компилация на частите
              \BeamerswitchSpawn{-part1}
              \BeamerswitchSpawn{-part1-trans}
              \BeamerswitchSpawn{-part2}
              \BeamerswitchSpawn{-part2-trans}}
            % приключваме с текущата обработка, частите вече са компилирани
            \stop}}}}}{
    % включване и на двете части
    \newbooltrue{part1}
    \newbooltrue{part2}
  }

\title{Функции от по-висок ред\ifbool{parts}{ -- част \ifbool{part1}{1}{}\ifbool{part2}{2}{}}{}}

\date{\ifbool{part1}{16 октомври 2024 г.}{23 октомври 2024 г.}}

\lstset{language=Scheme}

\newcommand<>{\upper}[1]{{\textcolor#2{red}{#1}}}
\newcommand<>{\term}[1]{{\textcolor#2{green}{#1}}}
\newcommand<>{\nextf}[1]{{\textcolor#2{blue}{#1}}}
\newcommand{\pnx}{x^n + 2x^{n-1} + \ldots + (n-2)x^3 + (n-1)x^2 + nx + (n+1)}
\newcommand{\pnxh}{\!\!\!\Bigg(\!\bigg(\!\Big(\ldots\big((x + 2)x + 3\big)x + \ldots\Big)x + (n-1)\bigg)x + n\Bigg)x + (n+1)}


\begin{document}

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

\section{Функциите като параметри}

\begin{frame}<\switch{part1}>[fragile]
  \frametitle{Подаване на функции като параметри}

  В Scheme функциите са „първокласни“ стойности.\\[2ex]
  \pause
  \textbf{Примери:}
  \begin{itemize}[<+->]
  \item \lst{(define (fixed-point? f x) (= (f x) x))}
  \item \evalstop{(fixed-point? sin 0)}{\#t}
  \item \evalstop{(fixed-point? exp 1)}{\#f}
  \item \evalstoerrp{(fixed-point? expt 0)}
  \item \alt<17>{\lst{(define (branch p? f g x) ((if (p? x) f g) x))}}
    {\lst{(define (branch p? f g x) (if (p? x) (f x) (g x)))}}
  \item \evalstop{(branch odd? exp fact 4)}{24}
  \item \lst{(define (id x) x)}
  \item \evalstop{(branch number? log id \"1\")}{\"1\"}
  \item \evalstop{(branch string? number? procedure? symbol?)}{\#t}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{part1}>
  \frametitle{Функции от по-висок ред}

  \begin{definition}
    Функция, която приема функция за параметър или връща функция като резултат се нарича \emph{функция от по-висок ред}.
  \end{definition}
  \pause
  \begin{itemize}[<+->]
  \item \tt{fixed-point?} и \tt{branch} са функции от по-висок ред
  \item \alert{Примери за математически функции от по-висок ред?}
  \item Всички функции в $\lambda$-смятането са от по-висок ред!
  \end{itemize}
\end{frame}

\begin{frame}<\switch{part1}>[fragile]
  \frametitle{Задачи за сумиране}

  \textbf{Задача:} Да се пресметнат следните суми:
  \begin{enumerate}
  \item $k^2 + (k+1)^2 + \ldots + 100^2$ за $k \leq 100$
  \item $\int_a^b f(x)dx \approx \Delta x\big[f(a) + f(a+\Delta x) + f(a+2\Delta x) + \ldots + f(b)\big]$
  \item $x + e^x + e^{e^x} + e^{e^{e^x}} + \ldots$ докато поредното събираемо е $\leq 10^{1000}$
  \end{enumerate}
  \pause
\begin{lstlisting}
(define (sum1 k)
  (if (> k @\upper<5->{100}@) 0 (+ @\term<6->{(* k k)}@ (sum1 @\nextf<7->{(+ k 1)}@))))
\end{lstlisting}
   \pause
\begin{lstlisting}
(define (sum2 a b f dx)
  (if (> a @\upper<5->{b}@) 0 (+ @\term<6->{(* dx (f a))}@ (sum2 @\nextf<7->{(+ a dx)}@ b f dx))))
\end{lstlisting}
   \pause
\begin{lstlisting}
(define (sum3 x)
  (if (> x @\upper<5->{(expt 10 1000)}@) 0 (+ @\term<6->{x}@ (sum3 @\nextf<7->{(exp x)}@))))
\end{lstlisting}
\end{frame}

\begin{frame}<\switch{part1}>[fragile]
  \frametitle{Обобщена функция за сумиране}
  Да се напише функция от по-висок ред \tt{sum}, която пресмята сумата:
  \begin{equation*}
    \sum_{\substack{i=a \\i \rightarrow next(i)}}^b term(i).
  \end{equation*}
  \pause
\begin{lstlisting}
(define (sum a @\upper{b} \term{term} \nextf{next}@)
  (if (> a @\upper{b}@) 0 (+ @\term{(term a)}@ (sum @\nextf{(next a)} \upper{b} \term{term} \nextf{next}@))))
\end{lstlisting}
\end{frame}

\begin{frame}<\switch{part1}>[fragile]
  \frametitle{Приложения на \tt{sum}}

  \begin{fixedarea}
    Решение на задачите за суми чрез \tt{sum}:\\
    \begin{tabular}[t]{p{.26\textwidth}p{.66\textwidth}}
      \[\sum_{i=k}^{100} i^2\]%
      &%
        \onslide<2->
\begin{tabularlstlisting}
(define (square x) (* x x))
(define (1+ x) (+ x 1))
(define (sum1 k) (sum k 100 square 1+))
\end{tabularlstlisting}\\[-4ex]
      \only<3->{%
      \[\only<5->{\Delta x\,}\sum_{\substack{i=a\\i\rightarrow i + \Delta x}}^b
      \only<-4>{\Delta x\,}f(i)\]}
      &%
        \onslide<4->%
\begin{tabularlstlisting}
(define (sum2 a b f dx)
  @\only<4>{(define (term x) (* dx (f x)))}@
  (define (next x) (+ x dx))
  @\only<5->{(* dx }@(sum a b @\alt<4>{term}f@ next))@\only<5->)@
\end{tabularlstlisting}\\[-3ex]
      \only<6->{%
      \[\sum_{\substack{i=x\\i\rightarrow e^i}}^{10^{1000}} i\]}
      &
        \onslide<7->
\begin{tabularlstlisting}
(define (sum3 x)
  (sum x (expt 10 1000) id exp))
\end{tabularlstlisting}
    \end{tabular}
  \end{fixedarea}
\end{frame}

\begin{frame}<\switch{part1}>[fragile]
  \frametitle{Обобщена функция за произведение}

  Да се напише функция от по-висок ред \tt{product}, която пресмята:
  \begin{equation*}
    \prod_{\substack{i=a \\i \rightarrow next(i)}}^b term(i).
  \end{equation*}
  \pause
  \newcommand{\fb}{\altbox<4>}
\begin{lstlisting}
(define (prod a @\upper{b}@ @\term{term}@ @\nextf{next}@)
  (if (> a @\upper{b}@) @\fb1@ (@\fb*@ @\term{(term a)}@ (prod @\nextf{(next a)}@ @\upper{b}@ @\term{term}@ @\nextf{next}@))))
\end{lstlisting}
\pause
\begin{lstlisting}
(define (sum a @\upper{b}@ @\term{term}@ @\nextf{next}@)
  (if (> a @\upper{b}@) @\fb0@ (@\fb+@ @\term{(term a)}@ (sum @\nextf{(next a)}@ @\upper{b}@ @\term{term}@ @\nextf{next}@))))
\end{lstlisting}
\end{frame}

\section{\tt{accumulate}}

\subsection{Дясно натрупване}

\begin{frame}<\switch{part1}>[fragile]
  \frametitle{Обобщена функция за натрупване}

  Да се напише функция, която пресмята
  \begin{equation*}
    term(a) \oplus \bigg(term\big(next(a)\big) \oplus \Big(\ldots \oplus \big(term(b) \oplus \bot\big) \ldots\Big)\bigg),
  \end{equation*}
  където $\oplus$ е двуместна операция,\\
  а $\bot$ е нейната „нулева стойност“, т.е. $x\oplus\bot = x$.
  \pause
  \small
\begin{lstlisting}
(define (accumulate op nv a b term next)
  (if (> a b) nv
      (op (term a) (accumulate op nv (next a) b term next))))
\end{lstlisting}
  \pause
\begin{lstlisting}
(define (sum a b term next) (accumulate + 0 a b term next))
(define (product a b term next) (accumulate * 1 a b term next))
\end{lstlisting}
\end{frame}

\subsection{Пример: правило на Хорнер}

\begin{frame}<\switchand{part1}{horner}>[fragile]
  \frametitle{Задача: пресмятане на полином}

  Да се пресметне стойността на полинома
  \begin{eqnarray*}
  P_n(x) &=& \pnx\\
\pause   &=& \sum_{i=0}^n (n+1-i)x^i
  \end{eqnarray*}
  \pause
  \textbf{Решение №1:}
\begin{lstlisting}
(define (p n x)
  @\only<7->{(define (term i) (* (- (1+ n) i) (expt x i)))}@
  (accumulate @\rvl+ \rvl0 \rvl0 \rvl{n} \rvl{term} \rvl{1+}@))
\end{lstlisting}
  \vspace{1ex}
  \onslide<+->
  \alert{Можем ли да решим задачата без да извикваме \tt{expt} на всяка стъпка?}
\end{frame}

\begin{frame}<\switchand{part1}{horner}>[fragile]
  \frametitle{Правило на Хорнер}

  \begin{eqnarray*}
    P_n(x) &=& \pnx\\
           &=& \pnxh
  \end{eqnarray*}
  \pause
  \alert{Можем ли да сметнем с \tt{accumulate}?}\\
  \pause
  \textbf{Идея:} Да използваме операцията $u \oplus v := ux + v$.\\
  \pause
  \alert{Коя е „нулевата стойност“  $\bot$?}\\[1ex]
  \pause
  \textbf{Решение №2:}
\begin{lstlisting}
(define (p n x)
  (define (op u v) (+ (* u x) v))
  (accumulate op 0 1 (1+ n) id 1+))
\end{lstlisting}
  \pause
  \alert{Не смята правилно!}
\end{frame}

\begin{frame}<\switchand{part1}{horner}>[fragile]
  \frametitle{Правило на Хорнер}

Всъщност пресметнахме:
\begin{equation*}
  Q_n(x) = x + 2x + 3x + \ldots + nx + (n+1)x= \frac{(n+1)(n+2)}2x.
\end{equation*}
  \pause
  \textbf{Идея:} Да използваме операцията $u \oplus v := u + vx$.\\[2ex]
  \pause
  \textbf{Решение №3:}
\begin{lstlisting}
(define (p n x)
  (define (op u v) (+ u (* v x)))
  (accumulate op 0 1 (1+ n) id 1+))
\end{lstlisting}
  \pause
  \alert{Пак не смята правилно!!!}
\end{frame}

\begin{frame}<\switchand{part1}{horner}>
  \frametitle{Ляво и дясно натрупване}

  Всъщност пресметнахме:
  \begin{eqnarray*}
    R_n(x) &=& 1+x\bigg(2+x\Big(\ldots+x\Big((n-1)+x(n+x(n+1))\Big)\ldots\Big)\bigg)\\
          &=&  (n+1)x^n + nx^{n-1} + (n-1)x^{n-2} + \ldots + 3x^2 + 2x + 1
  \end{eqnarray*}
  вместо
  \begin{eqnarray*}
    P_n(x) &=& \pnxh\\
    &=& \pnx.
  \end{eqnarray*}
  \pause
  \alert{За неасоциативни операции $\oplus$ има значение в какъв ред са скобите!}
\end{frame}

\subsection{Ляво натрупване}

\begin{frame}<\switchand{part1}{horner}>[fragile]
  \frametitle{Обобщена функция за ляво натрупване}

  Да се напише функция, която пресмята \textbf{ляво натрупване}:
  \begin{equation*}
    \bigg(\ldots\Big(\big(\bot \oplus term(a)\big) \oplus term(next(a))\Big) \oplus \ldots\bigg) \oplus term(b)
  \end{equation*}
  \pause
  \small
\begin{lstlisting}
(define (accumulate-i op nv a b term next)
  (if (> a b) nv
      (accumulate-i op (op nv (term a)) (next a) b term next)))
\end{lstlisting}
  \pause
  \begin{itemize}
  \item \tt{accumulate} --- дясно натрупване, рекурсивен процес
  \item \tt{accumulate-i} --- ляво натрупване, итеративен процес
  \end{itemize}
\end{frame}

\begin{frame}<\switchand{part1}{horner}>[fragile]
  \frametitle{Правило на Хорнер}

  \begin{eqnarray*}
    P_n(x) &=& \pnx\\
    &=& \pnxh
  \end{eqnarray*}
  \textbf{Идея:} използваме \tt{accumulate-i} и $u \oplus v := ux + v$.\\[2ex]
  \pause
  \textbf{Решение №4:}
\begin{lstlisting}
(define (p n x)
  (define (op u v) (+ (* u x) v))
  (accumulate-i op 0 1 (1+ n) id 1+))
\end{lstlisting}
\end{frame}

\section{\tt{lambda}}

\begin{frame}<\switch{part1}>[fragile]
  \frametitle{Анонимни функции}

  Можем да конструираме параметрите на функциите от по-висок ред „на място“, без да им даваме имена!\\[1ex]
  \pause
  \begin{itemize}[<+->]
  \item \tta{(lambda (}\{<параметър>\}\tta) <тяло>\tta)
  \item Оценява се до функционален обект със съответните параметри и тяло
  \item \alert{Анонимната функция пази указател към средата, в която е оценена}
  \item Примери:
    \begin{itemize}
    \item \evalsto{(lambda (x) (+ x 3))}{\#<procedure>}
    \item \evalsto{((lambda (x) (+ x 3)) 5)}8
    \item
        \lst{(define (}<име> <параметри>\tt) <тяло>\tt)\\
        \eqv\\
        \lst{(define }<име> \tt{(lambda (}<параметри>\tt) <тяло>\tt{))}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{part1}>[fragile]
  \frametitle{Примери}

\begin{lstlisting}
(define (integral a b f dx)
   (* dx (accumulate + 0 a b f (lambda (x) (+ x dx)))))
\end{lstlisting}
\ifbool{horner}{
\pause
\begin{lstlisting}
(define (p n x)
   (accumulate-i (lambda (u v) (+ (* u x) v)) 0
                 1 (+ n 1) id (lambda (i) (+ i 1))))
\end{lstlisting}
}{}
\pause
\textbf{Задача:} Как можем да реализираме с accumulate:
\begin{itemize}[<+->]
\item $n!$
\item $x^n$
\item $\sum_{i=0}^n \frac{x^i}{i!}$
\item $\exists x\in[a;b]\; p(x)$
\end{itemize}
\end{frame}

\section{Функциите като върнат резултат}

\begin{frame}<\switch{part2}>
  \frametitle{Функции, които връщат функции}

  Да разгледаме функция, която прилага дадена функция два пъти над аргумент.
  \begin{itemize}[<+->]
  \item \lst{(define (twice f x) (f (f x)))}
  \item \evalstop{(twice square 3)}{81}
  \item \lst{(define (twice f) (lambda (x) (f (f x))))}
  \item \evalstoerrp{(twice square 3)}
  \item \evalstop{(twice square)}{\#<procedure>}
  \item \evalsto{((twice square) 3)}{81}
  \item \evalstop{((twice (twice square)) 2)}{65536}
  \end{itemize}
\end{frame}

\begin{frame}<switch{part2}>
  \frametitle{Примери}

  \begin{itemize}[<+->]
  \item \lst{(define (n+ n) (lambda (i) (+ i n)))}
  \item \lst{(define 1+ (n+ 1))}
  \item \evalsto{(1+ 7)}8
  \item \lst{(define 5+ (n+ 5))}
  \item \evalsto{(5+ 7)}{12}
  \item \lst{(define (compose f g) (lambda (x) (f (g x))))}
  \item \evalstop{((compose square 1+) 3)}{16}
  \item \evalstop{((compose 1+ square) 3)}{10}
  \item \evalstop{((compose 1+ (compose square (n+ 2))) 3)}{26}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{part2}>
  \frametitle{Оценка на \tt{lambda}}

  \sizeboth\scriptsize
  \begin{fixedarea}
    \begin{columns}[T,onlytextwidth]
      \begin{column}{.5\textwidth}
        \evalchain{
          "\lst{(define (n+ n)}\\[0pt]\hskip2ex\lst{(lambda (i) (+ i n)))}"[env=E,align=left] -!-
          "\lst{(define 1+ (n+ 1))}"[env=E] ->
          % понеже низовете съвпадат е необходимо да се посочи изрично различно име за съответните възли
          {[name=oneplus] "\lst{(lambda (i) (+ i n))}"[env=E_1]} -!-
          "\lst{(define 5+ (n+ 5))}"[env=E] ->
          {[name=fiveplus] "\lst{(lambda (i) (+ i n))}"[env=E_2]}
        }
        \vspace{2ex}
        \begin{columns}[T]
          \begin{column}{12em}
            \evalchain{
              "\lst{(1+ 7)}"[env=E] ->
              % понеже низовете съвпадат е необходимо да се посочи изрично различно име за съответните възли
              {[name=first]  "\lst{(+ i n)}"[env=E_3]} ->
              "8";
            }
          \end{column}
          \begin{column}{12em}
            \evalchain{
              "\lst{(5+ 7)}"[env=E] ->
              {[name=second] "\lst{(+ i n)}"[env=E_4]} ->
              "12";
            }
          \end{column}
        \end{columns}
      \end{column}
      \begin{column}{.5\textwidth}
        \begin{tikzpicture}
          \envir{E}{
            \kf{n+}n{($\lambda$(i) (+ i n))}E
            \only<3->{\kf{1+}i{(+ i n)}{E_1}}
            \only<5->{\kf{5+}i{(+ i n)}{E_2}}
          }
          \childenvir[2- ]{below left =1em and -5em}E{E_1}{\kv n1}
          \childenvir[4- ]{below right=1em and -5em}E{E_2}{\kv n5}
          \childenvir[7- ]{below=1em}{E_1}{E_3}{\kv i7}
          \childenvir[10-]{below=1em}{E_2}{E_4}{\kv i7}
        \end{tikzpicture}
      \end{column}
    \end{columns}
  \end{fixedarea}
\end{frame}

\begin{frame}<\switch{part2}>[fragile]
  \frametitle{Намиране на производна}

  \begin{equation*}
    f'(x) \alt<1>{= \lim_{\Delta x\to 0} \frac{f(x+\Delta x) - f(x)}{\Delta x}}{\approx\frac{f(x+\Delta x) - f(x)}{\Delta x}\;\text{ за малки }\Delta x}
  \end{equation*}
  \pause\pause
\begin{lstlisting}
(define (derive f dx)
  (lambda (x) (/ (- (f (+ x dx)) (f x)) dx)))
\end{lstlisting}
  \pause
  \begin{itemize}[<+->]
  \item \lst{(define 2* (derive square 0.01))}
  \item \evalsto{(2* 5)}{10.009999999999764}
  \item \evalsto{((derive square 0.0000001) 5)}{10.000000116860974}
  \item \evalstopnl{((derive (derive (lambda (x) (* x x x)) 0.001) 0.001) 3)}{18.006000004788802}
  \end{itemize}
\end{frame}

\begin{frame}<\switch{part2}>[fragile]
  \frametitle{Повторено прилагане}

  Да се намери $n$-кратното прилагане на дадена едноместна функция.
  \begin{equation*}
    f^n(x) = \underbrace{f(f(f(\ldots(f}_n(x))\ldots)))
  \end{equation*}
  \pause
  \vspace{-.5ex}
  \textbf{Решение №1:} $f^0(x) = x, f^n(x) = f(f^{n-1}(x))$ \pause
\begin{lstlisting}
(define (repeated f n)
  (lambda (x) (if (= n 0) x (f ((repeated f (- n 1)) x)))))
\end{lstlisting}
  \pause
  \textbf{Решение №2:} $f^0 = id, f^n = f\circ f^{n-1}$ \pause
\begin{lstlisting}
(define (repeated f n)
  (if (= n 0) id (compose f (repeated f (- n 1)))))
\end{lstlisting}
  \pause
  \textbf{Решение №3:} $f^n = \underbrace{f \circ f \circ \ldots \circ f}_n \circ  id$ \pause
\vspace{-.3ex}
\begin{lstlisting}
(define (repeated f n)
  (@\rvl{accumulate} \rvl{compose} \rvl{id} \rvl1 \rvl{n} \rvl{(lambda (i) f)} \rvl{1+}@))
\end{lstlisting}
\end{frame}

\begin{frame}<\switch{part2}>[fragile]
  \frametitle{$n$-та производна}

  \small
  \begin{fixedarea}
  Да се намери $n$-та производна на дадена едноместна функция.\\[1.5ex]
  \pause
  \textbf{Решение №1:} $f^{(0)} = f, f^{(n)} = (f^{(n-1)})'$\pause
\begin{lstlisting}
(define (derive-n f n dx)
  (if (= n 0) f (derive (derive-n f (- n 1) dx) dx)))
\end{lstlisting}
  \pause
  \vspace{-.5ex}
  \textbf{Решение №2:} $f^{(n)} = f\overbrace{''''{}^{\ldots}{}''}^n$\pause
\begin{lstlisting}
(define (derive-n f n dx)
  @\only<7->((\rvl{repeated} \rvl{(lambda (f) (derive f dx))} n)\only<7->{ f)})@
\end{lstlisting}
\pause
\textbf{Решение №3:} $^{(n)} = \underbrace{{}'{}^\circ{}'{}^{\circ\ldots\circ}{}'}_n$
\vspace{-.5ex}
\begin{lstlisting}
(define (derive-n f n dx)
  (@(\rvl{accumulate} \rvl{compose} \rvl{id} \rvl1 \rvl{n} \rvl{\\
\hskip 15ex(lambda (i) (lambda (f) (derive f dx)))} \rvl{1+}) f))@
\end{lstlisting}
\end{fixedarea}
\end{frame}

\section{All you need is \texorpdfstring{$\lambda$}{λ}}

\begin{frame}<\switch{part2}>
  \frametitle{All you need is $\lambda$ \only<2->{--- \tt{let}}}

  Специалната форма \tt{lambda} е достатъчна за реализацията на (почти) всички конструкции в Scheme!\\[1ex]
  \pause
  Симулация на \tt{let}:
  \begin{tabular}{c}
    \lst{(let ((}<символ> <израз>\tt{))} <тяло>\tt)\\
    \eqv\\
    \lst{((lambda (}<символ>\tt) <тяло>\tt) <израз>\tt)
  \end{tabular}\\[2ex]
  \pause
  \begin{center}
    \begin{tabular}{r@{}l}
      \lst{(let (}&\tt(<символ$_1$> <израз$_1$>\tt)\\
                 &\tt(<символ$_2$> <израз$_2$>\tt)\\
                 &\ldots\\
                 &\tt(<символ$_n$> <израз$_n$>\tt)\lst{)}\\
                 &<тяло>\lst{)}\\
      \multicolumn 2c{\eqv}\\
      \lst{((lambda (}&<символ$_1$> \ldots <символ$_n$>\tt) <тяло>\tt)\\
                 &<израз$_1$> \ldots <израз$_n$>\tt)
    \end{tabular}
  \end{center}
\end{frame}

\begin{frame}<\switch{part2}>[fragile]
  \frametitle{All you need is $\lambda$ --- булева логика}

Симулация на булеви стойности и \lst{if}:
\begin{lstlisting}
(define #t (lambda (x y) x))
(define #f (lambda (x y) y))
(define (lambda-if b x y) @\only<3->(\alert<2>{(b x y)}\only<3->)@)
\end{lstlisting}
\onslide<4->
\textbf{Примери:}
\small
\begin{itemize}[<+->]
\item \evalsto{(lambda-if \#t (lambda () (+ 3 5)) (lambda () (/ 4 0)))}8
\item \evalsto{(lambda-if \#f (lambda () +) (lambda () \"abc\"))}{\"abc\"}
\item \lst{(define (not b) (lambda (x y) (b y x)))}
\end{itemize}
\end{frame}

\begin{frame}<\switch{part2}>[fragile]
  \frametitle{All you need is $\lambda$ --- числа}

  Симулация на естествени числа (\emph{нумерали на Чърч})\\
  \textbf{Идея:} представяне на числото $n$ като $\lambda{}f,x \;\;f^n(x)$\\[2ex]
  \pause
  \begin{itemize}[<+->]
  \item \lst{(define c3 (lambda (f x) (f (f (f x)))))}
  \item \lst{(define c5 (lambda (f x) (f (f (f (f (f x)))))))}
  \item \lst{(define c1+ (lambda (a) (lambda (f x) (f (a f x)))))}
  \item \lst{(define c+ (lambda (a b) (lambda (f x) (a f (b f x)))))}
  \end{itemize}
\end{frame}

\begin{frame}<\switchand{part2}{pairs}>[fragile]
  \frametitle{All you need is $\lambda$ --- наредени двойки}

  Можем да симулираме \tt{cons}, \tt{car} и \tt{cdr} чрез \tt{lambda}!\\[2ex]
  \pause
  \textbf{Вариант №1:}
\begin{lstlisting}
(define (lcons x y) (lambda (p) (if p x y)))
(define (lcar z) (z #t))
(define (lcdr z) (z #f))
\end{lstlisting}
  \pause
  \textbf{Вариант №2:}
\begin{lstlisting}
(define (lcons x y) (lambda (p) (p x y)))
(define (lcar z) (z (lambda (x y) x)))
(define (lcdr z) (z (lambda (x y) y)))
\end{lstlisting}
\end{frame}


\begin{frame}<\switchand{part2}{ycomb}>[fragile]
  \frametitle{All you need is $\lambda$ --- рекурсия}

  Рекурсивна дефиниция:
\begin{lstlisting}
(define f (gamma f))
\end{lstlisting}%
  \pause
  \textbf{Пример:}\\[-2ex]
  \begin{fixedarea}[.36]%
    \begin{onlyenv}<+ |trans:0>%
\begin{lstlisting}
(define (fact n)
  (if (= n 0) 1 (* n (fact (- n 1)))))
\end{lstlisting}%
    \end{onlyenv}%
    \begin{onlyenv}<+ |trans:0>%
\begin{lstlisting}
(define fact
  (lambda (n)
    (if (= n 0) 1 (* n (fact (- n 1))))))
\end{lstlisting}%
    \end{onlyenv}%
    \begin{onlyenv}<+ |trans:0>%
\begin{lstlisting}
(define (fact n) ((gamma fact) n))
(define (gamma f)
  (lambda (n)
    (if (= n 0) 1 (* n (f (- n 1))))))
\end{lstlisting}%
    \end{onlyenv}%
    \begin{onlyenv}<+->%
\begin{lstlisting}
(define (fact n) ((gamma fact) n))
(define gamma
  (lambda (f)
    (lambda (n)
      (if (= n 0) 1 (* n (f (- n 1)))))))
\end{lstlisting}%
    \end{onlyenv}%
  \end{fixedarea}
  \vspace{1ex}
  \onslide<+->
  \lst{fact} е най-малка неподвижна точка на оператора \lst{gamma}.\\[1ex]
  \onslide<+->
  Търсим \lst{fact} такова, че \lst{(fact n)} = \lst{((gamma fact) n)} = \lst{((gamma (gamma fact)) n)} = \lst{((gamma (gamma (gamma fact))) n)} = \ldots
\end{frame}

\begin{frame}<\switchand{part2}{ycomb}>[fragile]
  \frametitle{All you need is $\lambda$ --- намиране на неподвижна точка}
  \textbf{Идея №1:} \lst{(define fact (((repeated gamma ?) 'empty))}\\
  \pause
  \textbf{Проблем №1:} Не знаем колко пъти да повторим \tt{gamma}\ldots\\[2ex]
  \pause
  \textbf{Идея №2:} Да повтаряме \tt{gamma} безкрайно!
  \begin{lstlisting}
    (define (gamma-inf) (lambda (n) ((gamma (gamma-inf)) n)))
    (define fact (gamma-inf))\end{lstlisting}%
  \pause
  \textbf{Проблем №2:} \lst{gamma-inf} отново използва рекурсия\ldots\\[2ex]
  \pause
  \textbf{Идея №3:} Да подменим рекурсивното извикване с параметър:
  \begin{lstlisting}
    (define (gamma-inf me) (lambda (n) ((gamma (me me)) n)))\end{lstlisting}%
  \pause
  \textbf{Идея №4:} Да подадем \tt{gamma-inf} като параметър на себе си!
  \pause
  \begin{lstlisting}
    (define fact (gamma-inf gamma-inf))\end{lstlisting}
\end{frame}

\begin{frame}<\switchand{part2}{ycomb}>[fragile]
  \frametitle{All you need is $\lambda$ --- комбинатор \tt Y}
  \begin{fixedarea}
  Да напишем функция, която намира неподвижната точка на произволен оператор \tt{gamma}:
  \begin{lstlisting}
(define (Y gamma)
  (define (gamma-inf me) (lambda (n) ((gamma (me me)) n)))
  (gamma-inf gamma-inf))
\end{lstlisting}
\pause
  А сега само с $\lambda$:\\
  \begin{onlyenv}<+ |trans:0>%
\begin{lstlisting}
(define Y
  (lambda (gamma)
    ((lambda (gamma-inf) (gamma-inf gamma-inf))
     (lambda (me) (lambda (n) ((gamma (me me)) n))))))
   \end{lstlisting}%
    \end{onlyenv}%
    \begin{onlyenv}<+->%
\begin{lstlisting}
(define Y
  (lambda (gamma)
    ((lambda (me) (lambda (n) ((gamma (me me)) n)))
     (lambda (me) (lambda (n) ((gamma (me me)) n))))))
\end{lstlisting}%
    \end{onlyenv}
\onslide<+->
  \tt Y се нарича комбинатор за намиране на най-малка неподвижна точка (fixpoint combinator).
\end{fixedarea}
\end{frame}

\end{document}