1.4-scheme_lists.tex

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

\title{Списъци}

\date{16--23 октомври 2024 г.}
\lstset{language=Scheme}

% взели ли сме вече функции връщащи функции?
\newboolfalse{highorder}

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

\begin{document}

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

\section{Наредени двойки}

\begin{frame}
  \frametitle{Наредени двойки}

  \begin{columns}[t,onlytextwidth]
    \begin{column}{.5\textwidth}
      \vspace{2ex}
      \begin{center}
        \tt{(A . B)}
      \end{center}
    \end{column}
    \begin{column}{.5\textwidth}
      \begin{center}
        \begin{tikzpicture}
          \pointcellxx cAB
        \end{tikzpicture}
      \end{center}
    \end{column}
  \end{columns}
  \pause
  \vspace{2ex}
  \begin{itemize}[<+->]
  \item \tta{(cons} <израз$_1$> <израз$_2$>\tta)
  \item Наредена двойка от оценките на <израз$_1$> и <израз$_2$>
  \item \tta{(car} <израз>\tta)
  \item \textbf{Първият} компонент на двойката, която е оценката на <израз>
  \item \tta{(cdr} <израз>\tta)
  \item \textbf{Вторият} компонент на двойката, която е оценката на <израз>
  \item \tta{(pair?}   <израз>\tta)
  \item Проверява дали оценката на <израз> е наредена двойка
  \end{itemize}
\end{frame}

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

  \begin{columns}[T,onlytextwidth]
    \begin{column}{.6\textwidth}
      \evalchainx{
        "(cons (cons 2 3) (cons 8 13))" -> "((2 . 3) . (8 . 13))"
      }
      \vspace{8ex}
      \onslide<3->{
        \evalchainx{
          "(cons 3 (cons (cons 13 21) 8))" -> "(3 . ((13 . 21) . 8))"
        }
      }
    \end{column}
    \begin{column}{.4\textwidth}
      \onslide<2->{
        \begin{tikzpicture}
          \pointcell a

          \pointcellxx[below=2ex of a]b23
          \draw[ptr] (adata) to (bdata);

          \pointcellxx[right=2em of a]c8{13}
          \draw[ptr] (anext) to (c);
        \end{tikzpicture}\\[3ex]
      }
      \onslide<4>{
        \begin{tikzpicture}
          \pointcellx b3

          \pointcell[below=2ex of anext.south east]b
          \draw[ptr] (anext) to (bdata);

          \val[right=2em of b]v8
          \draw[ptr] (bnext) to (v);

          \pointcellxx[below=2ex of bdata.south east]c{13}{21}
          \draw[ptr] (bdata) to (cdata);
        \end{tikzpicture}
      }
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{S-изрази}

  \begin{definition}
    S-израз наричаме:
    \begin{itemize}
    \item атоми (булеви, числа, знаци, символи, низове, функции)
    \item наредени двойки \tt{(S$_1$ . S$_2$)}, където \tt{S$_1$} и \tt{S$_2$} са S-изрази
    \end{itemize}
  \end{definition}
  \vspace{2ex}
  \pause
  \alert{S-изразите са най-общият тип данни в Scheme.}\\[2ex]
  С тяхна помощ могат да се дефинират произволно сложни структури от данни.
\end{frame}

\begin{frame}<\switch{highorder}>[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}

\section{Списъци}

\begin{frame}
  \frametitle{Списъци в Scheme}

  \begin{definition}
    \begin{enumerate}
    \item Празният списък \tt{()} е списък
    \item \tt{(h . t)} е списък ако \tt t е списък
      \begin{itemize}
      \item \tt h --- глава на списъка
      \item \tt t --- опашка на списъка
      \end{itemize}
    \end{enumerate}
  \end{definition}
  \vspace{4ex}
  \pause
  \begin{tikzpicture}
    \pointcellx{a1}{a_1}
    \nextcellx{a2}{a_2}{a1}
    \nextdots{a2}
    \dotsnextcellx{an}{a_n}
    \nullptr{annext}
  \end{tikzpicture}\\[3ex]
  \tt{($a_1$ . ($a_2$ . ( \ldots ( $a_n$ . () ) ) ) ) \eqv\ ($a_1$ $a_2$ \ldots\ $a_n$)}
\end{frame}

\begin{frame}
  \frametitle{Вградени функции за списъци}

  \begin{itemize}[<+->]
  \item \tta{(null?} <израз>\tta) --- дали <израз> е празният списък \tt{()}
  \item \tta{(list?} <израз>\tta) --- дали <израз> е списък
    \begin{itemize}
    \item \scriptsize \lst{(define (list? l) (or (null? l) (and (pair? l) (list? (cdr l)))))}
    \end{itemize}
  \item \tta{(list} \{<израз>\}\tta) --- построява списък с елементи <израз>
  \item \tt{(list} <израз$_1$> <израз$_2$> \ldots <израз$_n$>\tt) \eqv\\
    \tt{(cons} <израз$_1$>\tt{ (cons} <израз$_2$> \ldots\tt{ (cons} <израз$_n$>\tt{ '()))))}
  \item \tt{(cons} <глава> <опашка>\tt) --- списък с <глава> и <опашка>
  \item \tt{(car} <списък>\tt) --- главата на <списък>
  \item \tt{(cdr} <списък>\tt) --- опашката на <списък>
  \item \alert{\tt{()} не е наредена двойка!}
  \item \evalstoerr{(car '())},\hskip 1em \evalstoerr{(cdr '())}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Съкратени форми на \tt{car} и \tt{cdr}}

  Нека $l = (a_1\,a_2\,a_3\,\ldots\,a_n)$.
  \begin{itemize}[<+->]
  \item \evalstos{\tt{(car l)}}{$a_1$}
  \item \evalstos{\tt{(cdr l)}}{$(a_2\,a_3\,...\,a_n)$}
  \item \evalstwop{(car (cdr l))}{$a_2$}{(cadr l)}
  \item \evalstwop{(cdr (cdr l))}{$(a_3\,...\,a_n)$}{(cddr l)}
  \item \evalstwop{(car (cdr (cdr l)))}{$a_3$}{(caddr l)}
  \item имаме съкратени форми за до 4 последователни прилагания на \tt{car} и \tt{cdr}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Форми на равенство в Scheme}

  \begin{itemize}[<+->]
  \item \tta{(eq?} <израз$_1$> <израз$_2$>\tta) --- връща \tt{\#t} точно тогава, когато оценките на <израз$_1$> <израз$_2$> заемат едно и също място в паметта
  \item \tta{(eqv?} <израз$_1$> <израз$_2$>\tta) --- връща \tt{\#t} точно тогава, когато оценките на <израз$_1$> и <израз$_2$> заемат едно и също място в паметта или са едни и същи по стойност \textbf{атоми} (без функции), дори и да заемат различно място в паметта
    \begin{itemize}
    \item Ако \tt{(eq?} <израз$_1$> <израз$_2$>\tt),\\
      то със сигурност \tt{(eqv?} <израз$_1$> <израз$_2$>\tt)
    \end{itemize}
  \item \tta{(equal?} <израз$_1$> <израз$_2$>\tta) --- връща \tt{\#t} точно тогава, когато оценките на <израз$_1$> и <израз$_2$> са едни и същи по стойност \textbf{атоми или наредени двойки}, чиито компоненти са равни в смисъла на \tt{equal?}
    \begin{itemize}
    \item В частност, \tt{equal?} проверява за равенство на списъци
    \item Ако \tt{(eqv?} <израз$_1$> <израз$_2$>\tt),\\
      то със сигурност \tt{(equal?} <израз$_1$> <израз$_2$>\tt)
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Вградени функции за списъци}
  \small
  \begin{itemize}[<+->]
  \item \tta{(length} <списък>\tta) --- връща дължината на <списък>
  \item \tta{(append} \{<списък>\}\tta) --- конкатенира всички <списък>
  \item \tta{(reverse} <списък>\tta) --- елементите на <списък> в обратен ред
  \item \tta{(list-tail} <списък> n\tta) --- елементите на <списък> без първите n
  \item \tta{(list-ref} <списък> n\tta) --- n-ти елемент на <списък> (от 0)
  \item \tta{(member} <елемент> <списък>\tta) --- проверява дали <елемент> се среща в <списък>
    \begin{itemize}
    \item По-точно, връща <списък> от първото срещане на <елемент> нататък, ако го има
    \item Връща \tt{\#f}, ако <елемент> го няма в <списък>
    \item Сравнението на елементи става с \tt{equal?}
    \end{itemize}
  \item \tta{(memv} <елемент> <списък>\tta) --- като \tt{member}, но сравнява с \tt{eqv?}
  \item \tta{(memq} <елемент> <списък>\tta) --- като \tt{member}, но сравнява с \tt{eq?}
  \end{itemize}
\end{frame}

\subsection{Рекурсия над списъци}

\begin{frame}
  \frametitle{Обхождане на списъци}

  При обхождане на \tt l:
  \begin{itemize}
  \item Ако \tt l е празен, връщаме базова стойност \textbf{(дъно)}
  \item Иначе, комбинираме главата \tt{(car l)} с резултата от рекурсивното извикване над опашката \tt{(cdr l)} \textbf{(стъпка)}
  \end{itemize}
  \pause
  \vspace{4ex}
  \textbf{Примери:} \tt{length}, \tt{list-tail}, \tt{list-ref}, \tt{member}, \tt{memqv}, \tt{memq}
\end{frame}

\begin{frame}
  \frametitle{Конструиране на списъци}

  Използваме рекурсия по даден параметър (напр. число, списък...)
  \begin{itemize}
  \item На дъното връщаме фиксиран списък (например \tt{()})
  \item На стъпката построяваме с \tt{cons} списък със съответната глава, а опашката строим чрез рекурсивно извикване на същата функция
  \end{itemize}
  \pause
  \vspace{4ex}
  \textbf{Примери:} \tt{from-to}, \tt{collect}, \tt{append}, \tt{reverse}
\end{frame}

\section{Функции от по-висок ред за списъци}

\begin{frame}[label=map,fragile]
  \frametitle{Изобразяване на списък (\tt{map})}

  Да се дефинира функция \tta{(map} <функция> <списък>\tta), която връща нов списък съставен от елементите на <списък>, върху всеки от които е приложена <функция>.\\
  \pause
  \begin{center}
    \begin{tikzpicture}
      \matrix [widearray,row sep=8ex] {
        |(a1)| a_1 \& |(a2)| a_2 \& \ldots \& |(an)| a_n \\
        |(fa1)| f(a_1) \& |(fa2)| f(a_2) \&  \ldots \& |(fan)| f(a_n) \\
      };
      \graph[transform] {
        a1 -> fa1;
        a2 -> fa2;
        an -> fan; };
      \node[ellipse,draw,fill=diagramblue,below=3.5ex of a2.east,minimum width=13em] {$f$};
    \end{tikzpicture}
  \end{center}
  \pause
\begin{lstlisting}
(define (map f l)
        (if (null? l) '()
            (cons (f (car l)) (map f (cdr l)))))
\end{lstlisting}
\end{frame}

\begin{frame}[fragile,label=mapex]
  \frametitle{Изобразяване на списък (\tt{map}) --- примери}

\begin{lstlisting}
(define (map f l)
        (if (null? l) '()
            (cons (f (car l)) (map f (cdr l)))))
\end{lstlisting}

  \small
  \begin{itemize}[<+->]
  \item \evalstop{(map square '(1 2 3))}{(1 4 9)}
  \item \evalstop{(map cadr '((a b c) (d e f) (g h i)))}{(b e h)}
  \item \evalstop{(map (lambda (f) (f 2)) (list square 1+ odd?))}{(4 3 \#f)}
  \ifbool{highorder}{\item \evalstop{(map (lambda (f) (f 2)) (map twice (list square 1+ boolean?)))}{(16 4 \#t)}}{}
  \end{itemize}
\end{frame}

\begin{frame}[fragile,label=filter]
  \frametitle{Филтриране на списък (\tt{filter})}

  Да се дефинира функция \tta{(filter} <условие> <списък>\tta), която връща само тези от елементите на <списък>, които удовлетворяват <условие>.
\pause
  \begin{center}
    \begin{tikzpicture}
      \matrix [widearray,row sep=7ex,nodes in empty cells=false] {
        |(a1)| a_1 \& |(dots1)| \ldots \& |(ai)| a_i \& |(dots2)| \ldots \& |(aj)| a_j \& |(dots3)| \ldots \& |(ak)| a_k \& |(dots4)| \ldots \& |(an)| a_n \\
        \&\& |(pa1)| a_1 \& |(pai)| a_i \&|(pak)| a_k\& |(pdots)| \ldots \\
      };
      \graph[transform] {
        a1.south -> pa1.north;
        ai.south -> pai.north;
        ak.south -> pak.north;
        dots1.south --[shorten >=5ex] pa1.north east;
        dots2.south --[shorten >=3ex] pai.north east;
        aj.south --[shorten >=3ex] pak.north west;
        dots3.south --[shorten >=5ex] pak.north west;
        dots4.south --[shorten >=6ex] pdots.north;
        an.south --[shorten >=9ex] pdots.north east;
      };
      \node[trapezium,
      trapezium angle=98,
      trapezium stretches=true,
      right,
      draw,
      fill=diagramblue,
      below=2ex of aj,
      minimum width=25em,
      minimum height=3ex] {$p$};
    \end{tikzpicture}
  \end{center}
\pause
\small
\begin{lstlisting}
(define (filter p? l)
   (cond ((null? l) l)
         ((p? (car l)) (cons (car l) (filter p? (cdr l))))
         (else (filter p? (cdr l)))))
\end{lstlisting}
\end{frame}

\begin{frame}[fragile,label=filterex]
  \frametitle{Филтриране на списък (\tt{filter})}
  \begin{fixedarea}
\begin{lstlisting}
(define (filter p? l)
   (cond ((null? l) l)
         ((p? (car l)) (cons (car l) (filter p? (cdr l))))
         (else (filter p? (cdr l)))))
\end{lstlisting}
    \begin{itemize}[<+->]
    \item \evalstop{(filter odd? '(1 2 3 4 5))}{(1 3 5)}
    \item \evalstop{(filter pair? '((a b) c () d (e)))}{((a b) (e))}
    \item \evalstopnl{(map (lambda (x) (filter even? x)) '((1 2 3) (4 5 6) (7 8 9)))}{((2) (4 6) (8))}
    \item \evalstopnl{(map (lambda (x) (map (lambda (f) (filter f x)) (list negative? zero? positive?))) '((-2 1 0) (1 4 -1) (0 0 1)))}{(((-2) (0) (1)) ((-1) () (1 4)) (() (0 0) (1)))}
    \end{itemize}
  \end{fixedarea}
\end{frame}

\begin{frame}[fragile,label=foldr]
  \frametitle{Дясно свиване (\tt{foldr})}

  Да се дефинира функция, която по даден списък $l = (a_1\,a_2\,a_3\,\ldots\,a_n)$ пресмята:
  \begin{equation*}
    a_1 \oplus \Big(a_2 \oplus \big(\ldots \oplus (a_n \oplus \bot) \ldots\big)\Big),
  \end{equation*}\\[-1ex]
  \pause
  \begin{columns}[T,onlytextwidth]
    \begin{column}{.25\textwidth}
      \begin{forest} for tree={edge=<-}
        [$\oplus$ [$a_1$]
        [$\oplus$ [$a_2$]
        [$\vdots$ [,phantom]
        [$\oplus$ [$a_n$] [$\bot$]]]]]
      \end{forest}
    \end{column}
    \pause
    \begin{column}{.75\textwidth}
\begin{lstlisting}
(define (foldr op nv l)
        (if (null? l) nv
            (op (car l) (foldr op nv (cdr l)))))
\end{lstlisting}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}[fragile,label=foldrex]
  \frametitle{Дясно свиване (\tt{foldr}) --- примери}

\begin{lstlisting}
(define (foldr op nv l)
        (if (null? l) nv
            (op (car l) (foldr op nv (cdr l)))))
\end{lstlisting}
  \small
  \begin{itemize}[<+->]
  \item \evalstop{(foldr * 1 (from-to 1 5))}{120}
  \item \evalstop{(foldr + 0 (map square (filter odd? (from-to 1 5))))}{35}
  \item \evalstop{(foldr cons '() '(1 5 10))}{(1 5 10)}
  \item \evalstop{(foldr list '() '(1 5 10))}{(1 (5 (10 ()))}
  \item \evalstop{(foldr append '() '((a b) (c d) (e f)))}{(a b c d e f)}
  \item \tt{map}, \tt{filter} и \tt{accumulate} могат да се реализират чрез \tt{foldr}
  \end{itemize}
\end{frame}

\begin{frame}[fragile,label=foldl]
  \frametitle{Ляво свиване (\tt{foldl})}

  Да се дефинира функция, която по даден списък $l = (a_1\,a_2\,a_3\,\ldots\,a_n)$ пресмята:
  \begin{equation*}
    \Big(\ldots\big((\bot \oplus a_1) \oplus a_2\big) \oplus \ldots\Big) \oplus a_n
  \end{equation*}\\[-1ex]
  \pause
  \begin{columns}[T,onlytextwidth]
    \begin{column}{.3\textwidth}
      \begin{forest} for tree={edge=<-}
        [$\oplus$
          [$\vdots$
            [$\oplus$
              [$\oplus$ [$\bot$] [$a_1$]]
              [$a_2$]]
            [,phantom]]
          [$a_n$]]
      \end{forest}
    \end{column}
    \pause
    \begin{column}{.7\textwidth}
\begin{lstlisting}
(define (foldl op nv l)
  (if (null? l) nv
      (foldl op (op nv (car l)) (cdr l))))
\end{lstlisting}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}[fragile,label=foldlex]
  \frametitle{Ляво свиване (\tt{foldl}) --- примери}

\begin{lstlisting}
(define (foldl op nv l)
  (if (null? l) nv
      (foldl op (op nv (car l)) (cdr l))))
\end{lstlisting}
  \pause
  \small
  \begin{itemize}[<+->]
  \item \evalstop{(foldl * 1 (from-to 1 5))}{120}
  \item \evalstop{(foldl cons '() '(1 5 10))}{(((() . 1) . 5) . 10)}
  \item \evalstos{\tt{(foldl }\rvl{\lst{(lambda (x y) (cons y x))}} \lst{ '() '(1 5 10))}}{\tt{(10 5 1)}}
  \item \evalstop{(foldl list '() '(1 5 10))}{(((() 1) 5) 10)}
  \item \evalstop{(foldl append '() '((a b) (c d) (e f)))}{(a b c d e f)}
  \item \tt{foldr} генерира линеен рекурсивен процес, а \tt{foldl} --- линеен итеративен
  \end{itemize}
\end{frame}

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

  В R$^5$RS е дефинирана само функцията \tt{map}.\\
  В Racket са дефинирани функциите \tt{map}, \tt{filter}, \tt{foldr}, \tt{foldl}\\[2ex]
  \pause
  \alert{Внимание: \tt{foldl} в Racket е дефинирана по различен начин!}\\[2ex]
  \begin{columns}[T,onlytextwidth]
    \small
    \begin{column}{.5\textwidth}
      \tt{foldl} от лекции\\[2ex]
\begin{lstlisting}
(define (foldl op nv l)
  (if (null? l) nv
      (foldl op @\alert{(op nv (car l))}@
             (cdr l))))
\end{lstlisting}
      \begin{equation*}
        \Big(\ldots\big((\bot \oplus a_1) \oplus a_2\big) \oplus \ldots\Big) \oplus a_n
      \end{equation*}
    \end{column}
    \begin{column}{.5\textwidth}
      \tt{foldl} в Racket\\[2ex]
\begin{lstlisting}
(define (foldl op nv l)
  (if (null? l) nv
      (foldl op @\alert{(op (car l) nv)}@
             (cdr l))))
\end{lstlisting}
      \begin{equation*}
        a_n \oplus \Big(\ldots \big(a_2 \oplus (a_1 \oplus \bot)\big)\ldots\Big),
      \end{equation*}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Свиване на непразен списък (\tt{foldr1, foldl1})}

  \textbf{Задача.} Да се намери максималният елемент на списък.\\
  \pause
  \lst{(define (maximum l) (foldr max}\tt{ \alt<2>?{(car l)} l))}\\[2ex]
  \pause\pause
  Можем ли да пропуснем нулевата стойност за непразен списък?\\[2ex]
  \begin{tabular}{ll}
    \pause
      $a_1 \oplus \big(\ldots \oplus (a_{n-1} \oplus a_n) \ldots\big)$
    & \pause
\begin{lstlisting}
(define (foldr1 op l)
  (if (null? (cdr l)) (car l)
      (op (car l)
          (foldr1 op (cdr l)))))
\end{lstlisting}\\[6ex]
    \pause
    $\big(\ldots\big((a_1 \oplus a_2) \oplus \ldots\big) \oplus a_n$
    & \pause
\begin{lstlisting}
(define (foldl1 op l)
  (foldl op (car l) (cdr l)))
\end{lstlisting}
  \end{tabular}
\end{frame}

\section{Вариадични функции}

\begin{frame}<\switch{variadic}>
  \frametitle{Вариадични функции ---  приемащи произволен брой аргументи}

  \begin{itemize}[<+->]
  \item \tta{(lambda} <списък> <тяло>\tta)
  \item създава функция с <тяло>, която получава <списък> от параметри
  \item \tta{(lambda (}\{<параметър>\}$^+$ \tta. <списък>\tta) <тяло>\tta)
  \item създава функция с <тяло>, която получава няколко задължителни <параметър> и <списък> от опционални параметри
  \item \tta{(define (}<функция> \tta. <списък>\tta) <тяло>\tta)
  \item еквивалентно на \\
    \lst{(define} <функция> \tt{(lambda }<списък> <тяло>\tt{))}
  \item \tta{(define (}<функция> \{<параметър>\}$^+$ \tta. <списък>\tta) <тяло>\tta)
  \item еквивалентно на \\
    \lst{(define} <функция> \lst{(lambda (}\{<параметър>\}$^+$ \tt. <списък>\tt) <тяло>\tt{))}
  \end{itemize}
\end{frame}

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

  \begin{itemize}[<+->]
  \item \lst{(define (maximum x . l) (foldl1 max (cons x l)))}
  \item \evalstop{(maximum 7 3 10 2)}{10}
  \item \evalstop{(maximum 100)}{100}
  \item \evalstoerrp{(maximum)}
  \item \lst{(define (g x y . l) (append x l y l))}
  \item \evalstop{(g '(1 2 3) '(4 5 6))}{(1 2 3 4 5 6)}
  \item \evalstop{(g '(1 2 3) '(4 5 6) 7 8)}{(1 2 3 7 8 4 5 6 7 8)}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Прилагане на функция над списък от параметри (\tt{apply})}

  \begin{itemize}[<+->]
  \item \tta{(apply} <функция> <списък>\tta)
  \item прилага <функция> над <списък> от параметри
  \item \textbf{Примери:}
  \item \evalsto{(apply + '(1 2 3 4 5))}{15}
  \item \evalstop{(apply append '((1 2) (3 4) (5 6)))}{(1 2 3 4 5 6)}
  \item \evalstop{(apply list '(1 2 3 4))}{(1 2 3 4)}
  \end{itemize}
\ifbool{variadic}{
\onslide<+->
\small
\begin{lstlisting}
(define (append . l)
   (cond ((null? l) '())
         ((null? (car l)) (apply append (cdr l)))
         (else (cons (caar l)
                     (apply append (cons (cdar l) (cdr l)))))))
\end{lstlisting}
  }{}
\end{frame}


\begin{frame}<\switch{variadic}>[fragile]
  \frametitle{Вариадичен \lst{map}}

  \begin{itemize}[<+->]
  \item Функцията \lst{map} може да се използва с произволен брой списъци!
  \item \tta{(map} <$n$-местна функция> $l_1 \ldots l_n$\tta)
  \item Конструира нов списък, като прилага <$n$-местна функция> над съответните поредни елементи на списъците $l_1, \ldots, l_n$\\
    \onslide<+->
    \begin{tikzpicture}[comb/.style={circle,minimum size=1.5em}]
    \scriptsize
       \matrix [widearray,nodes in empty cells=false] {
        |(a1)| a_1 \& |(a2)| a_2 \& \ldots \& |(ak)| a_k \&\& |(b1)| b_1 \& |(b2)| b_2 \& \ldots \& |(bk)| b_k\\[12ex]
        \&\&|(pab1)[comb]| f \& |(pab2)[comb]| f \&  \& |(pabk)[comb]| f \\[2ex]
        \&\&|(fab1)| c_1 \& |(fab2)| c_2 \& \ldots \& |(fabk)| c_k\\
      };
      \graph[transform] {
        pab1 -> fab1;
        pab2 -> fab2;
        pabk -> fabk;
        a1.south ->[bl] pab1;
        a2.south ->[bl] pab2;
        ak.south ->[bl] pabk;
        b1.south ->[br] pab1;
        b2.south ->[br] pab2;
        bk.south ->[br] pabk;
      };
    \end{tikzpicture}
  \item \evalstop{(map + '(1 2 3) '(4 5 6))}{(5 7 9)}
  \item \evalstop{(map list '(1 2 3) '(4 5 6))}{((1 4) (2 5) (3 6))}
  \item \small \evalstop{(map foldr (list * +) '(1 0) '((1 2 3) (4 5 6)))}{(6 15)}
\end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Оценяване на списък като комбинация (\tt{eval})}

  \begin{itemize}[<+->]
  \item \tta{(eval} <S-израз> <среда>\tta)
  \item връща оценката на <S-израз> в <среда>
  \item \tta{(interaction-environment)} --- текущата среда, в която оценяваме
  \item \lst{(define (evali x) (eval x (interaction-environment)))}
  \item \textbf{Примери:}
  \item \lst{(define a 2)}
  \item \evalsto a2
  \item \evalsto{(evali a)}2
  \item \evalstop{(evali 'a)}2
  \item \evalstop{(evali ''a)}a
  \item \evalstop{(evali (evali ''a))}2
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Примери за \tt{eval}}

  \begin{itemize}[<+->]
  \item \evalstop{(evali (list '+ 5 7 'a))}{14}
  \item \evalstoerrp{(evali (list 'define b 5))}
  \item \lst{(evali (list 'define 'b 5))} \eqv\ \lst{(define b 5)}
  \item \evalsto{b}5
  \item {\small \evalstop{(evali (list 'if (list '< 2 5) (list 'quote 'a) 'b))}a}
  \item \lst{(define (apply f l) (evali (cons f l)))}
  \end{itemize}
  \onslide<+->
  \alert{Програмите на Scheme могат да се разглеждат като данни!}
\end{frame}

\end{document}