\begin{document}
%----------------------------------------------------------------------------------------
% Title
%----------------------------------------------------------------------------------------
\begin{frame}
\titlepage
\end{frame}
%----------------------------------------------------------------------------------------
% Revierw
%----------------------------------------------------------------------------------------
\begin{frame}
\frametitle{Обзор}
\tableofcontents
\end{frame}
%----------------------------------------------------------------------------------------
% Presentation
%----------------------------------------------------------------------------------------
\section{История}
\begin{frame}
\frametitle{Язык Рефал}
\begin{itemize}
\item[] Функциональный язык программирования, создан в 1966 году Валентином Турчиным.
\item[] Основные реализации: Рефал-2(1974), Рефал-5(1988), Рефал+(1990).
\end{itemize}
\end{frame}
\section{Объектные выражения}
\begin{frame}
\frametitle{Объектные выражения}
\begin{itemize}
\item[] Объектный терм - символ или объектное выражение в структурных скобках
\item[] Объектное выражение - последовательность объектных термов
\end{itemize}
\begin{center}
Примеры:
\end{center}
\begin{itemize}
\item[] 'John' 'Doe' 1589
\item[] 'John' ('Doe') 1589
\end{itemize}
\end{frame}
\section{Представление объектных выражений}
%-----------------------------------------------------------------------------%
\begin{frame}
\frametitle{Классическое представление}
\begin{figure}[H]
\centering
\begin{tikzpicture}[every node/.style={anchor=center,draw=black!60}]
\node [rectangle] (a) at (0cm,0cm) { a };
\node [rectangle] (lp_1) at (1cm,0cm) { ( };
\node [rectangle] (b) at (2cm,0cm) { b };
\node [rectangle] (lp_2) at (3cm,0cm) { ( };
\node [rectangle] (c) at (4cm,0cm) { c };
\node [rectangle] (rp_2) at (5cm,0cm) { ) };
\node [rectangle] (d) at (6cm,0cm) { d };
\node [rectangle] (rp_1) at (7cm,0cm) { ) };
\draw[latex'-latex'] (a) -- (lp_1);
\draw[latex'-latex'] (lp_1) -- (b);
\draw[latex'-latex'] (b) -- (lp_2);
\draw[latex'-latex'] (lp_2) -- (c);
\draw[latex'-latex'] (c) -- (rp_2);
\draw[latex'-latex'] (rp_2) -- (d);
\draw[latex'-latex'] (d) -- (rp_1);
\draw[latex'-latex'] (lp_1) -- ++(0, 1) -| (rp_1);
\draw[latex'-latex'] (lp_2) -- ++(0, .75) -| (rp_2);
\end{tikzpicture}
\caption{Классическое представление объектного выражения $a(b(c)d)$} \label{classic}
\end{figure}
\end{frame}
%-----------------------------------------------------------------------------%
\begin{frame}
\frametitle{Компромиссное списковое представление}
\begin{figure}[H]
\centering
\begin{tikzpicture}[every node/.style={anchor=center,draw=black!60}]
% level 0
\node [rectangle] (a) at (0cm,0cm) { a };
\node [rectangle] (star1_ptr) at (1cm,0cm) { $(*)$ };
\node [rectangle] (b) at (2cm,0cm) { b };
% level 1
\node [rectangle] (star1) at (1cm, -1cm) { $*$ };
\node [rectangle] (c) at (2cm,-1cm) { c };
\node [rectangle] (star2_ptr) at (3cm,-1cm) { $(*)$ };
\node [rectangle] (d) at (4cm,-1cm) { d };
% level 2
\node [rectangle] (star2) at (3cm,-2cm) { $*$ };
\node [rectangle] (e) at (4cm,-2cm) { e };
% level 0 draws
\draw[latex'-latex'] (a) -- (star1_ptr);
\draw[latex'-latex'] (star1_ptr) -- (b);
% level 1 draws
\draw[latex'-latex'] (star1) -- (c);
\draw[latex'-latex'] (c) -- (star2_ptr);
\draw[latex'-latex'] (star2_ptr) -- (d);
\draw[latex'-latex'] (star1) -- ++(0, -.5) -| (d);
% level 2 draws
\draw[latex'-latex'] (star2) -- (e);
\draw[latex'-latex'] (star2) -- ++(0, -.5) -| (e);
% 0-1 links
\draw[-open triangle 60] (star1_ptr) -- (star1);
% 1-2 links
\draw[-open triangle 60] (star2_ptr) -- (star2);
\end{tikzpicture}
\caption{Компромиссное представление объектного выражения $a(c(e)d)b$ на основе списков} \label{list_compromise}
\end{figure}
\end{frame}
%-----------------------------------------------------------------------------%
\begin{frame}
\frametitle{Модификация компромиссного спискового представления}
\begin{figure}[H]
\centering
\begin{tikzpicture}[every node/.style={anchor=center,draw=black!60}]
% level 0
\node [rectangle] (a) at (1cm,0cm) { a };
\node [rectangle] (star1_ptr) at (2cm,0cm) { $(*)$ };
\node [rectangle] (b) at (3cm,0cm) { b };
% level 1
\node [rectangle] (star1) at (1cm, -1cm) { $*$ };
\node [rectangle] (c) at (2cm,-1cm) { c };
\node [rectangle] (star2_ptr) at (3cm,-1cm) { $(*)$ };
\node [rectangle] (d) at (4cm,-1cm) { d };
% level 2
\node [rectangle] (star2) at (3cm,-2cm) { $*$ };
\node [rectangle] (e) at (4cm,-2cm) { e };
% level 0 draws
\draw[latex'-latex'] (a) -- (star1_ptr);
\draw[latex'-latex'] (star1_ptr) -- (b);
% level 1 draws
\draw[latex'-latex'] (star1) -- (c);
\draw[latex'-latex'] (c) -- (star2_ptr);
\draw[latex'-latex'] (star2_ptr) -- (d);
%\draw[latex'-latex'] (star1) -- ++(0, -1) -| (d);
% level 2 draws
\draw[latex'-latex'] (star2) -- (e);
%\draw[latex'-latex'] (star2) -- ++(0, -1) -| (e);
% 0-1 links
\draw[-open triangle 60] (star1_ptr) -- ++(0,-.5) -| (star1);
\draw[-open triangle 60] (star1_ptr) -- ++(0,-.5) -| (d);
% 1-2 links
\draw[-open triangle 60] (star2_ptr) -- ++(0,-.5) -| (star2);
\draw[-open triangle 60] (star2_ptr) -- ++(0,-.5) -| (e);
\end{tikzpicture}
\caption{Развитие компромиссного представления объектного выражения на основе списков для выражения $a(c(e)d)b$} \label{double_list_compromise}
\end{figure}
\end{frame}
%-----------------------------------------------------------------------------%
\begin{frame}
\frametitle{Векторное представление}
\begin{figure}[H]
\centering
\begin{tikzpicture}[every node/.style={anchor=center,draw=black!60}]
% level 0
\node [rectangle, minimum size=0.5cm] (v0) at (2cm,0cm) { };
\node [rectangle, minimum size=0.5cm] (v1) at (2.5cm,0cm) { };
\node [rectangle, minimum size=0.5cm] (v2) at (3cm,0cm) { };
\node [draw=none] (a) at (2cm,0cm) { a };
\node [draw=none] (star1_ptr) at (2.5cm,0cm) { $(*)$ };
\node [draw=none] (b) at (3cm,0cm) { b };
% level 1
\node [rectangle, minimum size=0.5cm] (u0) at (2cm,-2cm) { };
\node [rectangle, minimum size=0.5cm] (u1) at (2.5cm,-2cm) { };
\node [rectangle, minimum size=0.5cm] (u2) at (3cm,-2cm) { };
\node [draw=none] (c) at (2cm,-2cm) { c };
\node [draw=none] (star2_ptr) at (2.5cm,-2cm) { $(*)$ };
\node [draw=none] (d) at (3cm,-2cm) { d };
% level 2
\node [rectangle, minimum size=0.5cm] (w0) at (2.5cm,-4cm) { };
\node [draw=none] (e) at (2.5cm,-4cm) { e };
% 0-1 links
\draw[-open triangle 60] (star1_ptr) -- ++(0,-1) -| (c);
\draw[-open triangle 60] (star1_ptr) -- ++(0,-1) -| (d);
% 1-2 links
\draw[-open triangle 60] ([xshift=2cm]star2_ptr) -- ([xshift=2cm]e);
\draw[-open triangle 60] ([xshift=-2cm]star2_ptr) -- ([xshift=-2cm]e);
\end{tikzpicture}
\caption{Векторное представление выражения $a(c(e)d)b$} \label{vector}
\end{figure}
\end{frame}
%-----------------------------------------------------------------------------%
\begin{frame}
\frametitle{Верёвки (Ropes)}
\begin{figure}[H]
\centering
\begin{tikzpicture}[every node/.style={anchor=center,draw=black!60}]
%\node [rectangle] (root) at (2cm,0cm) { $25$ };
\node [rectangle] (f_node) at (0.5cm,-1cm) { $8$ };
\node [rectangle] (n_1) at (-1cm,-2cm) { $8: \textbf{John Doe}$ };
%\node [rectangle] (n_2) at (2cm,-2cm) { $\textbf{was born}$ };
%\node [rectangle] (n_3) at (3cm,-1cm) { $\textbf{in 1589}$ };
% 0-1 links
%\draw[-open triangle 60] (root) -- (f_node);
%\draw[-open triangle 60] (root) -- (n_3);
\draw[-open triangle 60] (f_node) -- (n_1);
%\draw[-open triangle 60] (f_node) -- (n_2);
\end{tikzpicture}
\caption{Строка $\textbf{'John Doe'}$} \label{rope_illustration}
\end{figure}
\end{frame}
%-----------------------------------------------------------------------------%
\begin{frame}
\frametitle{Верёвки (Ropes)}
\begin{figure}[H]
\centering
\begin{tikzpicture}[every node/.style={anchor=center,draw=black!60}]
%\node [rectangle] (root) at (2cm,0cm) { $25$ };
\node [rectangle] (f_node) at (0.5cm,-1cm) { $17$ };
\node [rectangle] (n_1) at (-1cm,-2cm) { $8: \textbf{John Doe}$ };
\node [rectangle] (n_2) at (2cm,-2cm) { $9: \textbf{ was born}$ };
%\node [rectangle] (n_3) at (3cm,-1cm) { $\textbf{in 1589}$ };
% 0-1 links
%\draw[-open triangle 60] (root) -- (f_node);
%\draw[-open triangle 60] (root) -- (n_3);
\draw[-open triangle 60] (f_node) -- (n_1);
\draw[-open triangle 60] (f_node) -- (n_2);
\end{tikzpicture}
\caption{Строка $\textbf{'John Doe' + ' was born'}$} \label{rope_illustration}
\end{figure}
\end{frame}
%-----------------------------------------------------------------------------%
\begin{frame}
\frametitle{Верёвки (Ropes)}
\begin{figure}[H]
\centering
\begin{tikzpicture}[every node/.style={anchor=center,draw=black!60}]
\node [rectangle] (root) at (2cm,0cm) { $25$ };
\node [rectangle] (f_node) at (0.5cm,-1cm) { $17$ };
\node [rectangle] (n_1) at (-1cm,-2cm) { $8: \textbf{John Doe }$ };
\node [rectangle] (n_2) at (2cm,-2cm) { $9: \textbf{ was born}$ };
\node [rectangle] (n_3) at (3cm,-1cm) { $8: \textbf{ in 1589}$ };
% 0-1 links
\draw[-open triangle 60] (root) -- (f_node);
\draw[-open triangle 60] (root) -- (n_3);
\draw[-open triangle 60] (f_node) -- (n_1);
\draw[-open triangle 60] (f_node) -- (n_2);
\end{tikzpicture}
\caption{Строка $\textbf{'John Doe was born' + ' in 1589'}$} \label{rope_illustration}
\end{figure}
\end{frame}
%-----------------------------------------------------------------------------%
\begin{frame}
\frametitle{Верёвочная модификация векторного представления}
\begin{figure}[H]
\centering
\begin{tikzpicture}[every node/.style={anchor=center,draw=black!60}]
% level -1
\node [rectangle, minimum size=0.5cm] (root0) at (3.5cm,0cm) { };
\node [draw=none] (root0_info) at (3.5cm,0cm) { $6$ };
% level 0
\node [rectangle, minimum size=0.5cm] (v0) at (2cm,-1cm) { };
\node [rectangle, minimum size=0.5cm] (v1) at (2.5cm,-1cm) { };
\node [rectangle, minimum size=0.5cm] (v2) at (3cm,-1cm) { };
\node [draw=none] (a) at (2cm, -1cm) { a };
\node [draw=none] (root1_ptr) at (2.5cm,-1cm) { $(*)$ };
\node [draw=none] (b) at (3cm,-1cm) { b };
\node [rectangle, minimum size=0.5cm] (v3) at (4cm,-1cm) { };
\node [rectangle, minimum size=0.5cm] (v4) at (4.5cm,-1cm) { };
\node [rectangle, minimum size=0.5cm] (v5) at (5cm,-1cm) { };
\node [draw=none] (c) at (4cm,-1cm) { c };
\node [draw=none] (d) at (4.5cm,-1cm) { d };
\node [draw=none] (e) at (5cm,-1cm) { e };
% level 1
\node [rectangle, minimum size=0.5cm] (root1) at (2.5cm,-2cm) { };
\node [draw=none] (root1_info) at (2.5cm,-2cm) { $3$ };
\node [rectangle, minimum size=0.5cm] (u0) at (2cm,-3cm) { };
\node [rectangle, minimum size=0.5cm] (u1) at (2.5cm,-3cm) { };
\node [rectangle, minimum size=0.5cm] (u2) at (3cm,-3cm) { };
\node [draw=none] (f) at (2cm,-3cm) { f };
\node [draw=none] (g) at (2.5cm,-3cm) { g };
\node [draw=none] (h) at (3cm,-3cm) { h };
%links
\draw[-open triangle 60] ([yshift=2cm]root0) -- (v1);
\draw[-open triangle 60] ([yshift=2cm]root0) -- (v4);
\draw[-open triangle 60] (v1) -- (root1);
\draw[-open triangle 60] (root1) -- (u1);
\end{tikzpicture}
\caption{Верёвочное представление выражения $a(fgh)bcde$} \label{vector}
\end{figure}
\end{frame}
%-----------------------------------------------------------------------------%
\section{Итоги}
\begin{frame}
\frametitle{Сравнение представлений}
\begin{itemize}
\item[] {Классическое - конкатенация за $\otop(1)$, копирование за $\otop(N)$, доступ к элементу - $\otop(N)$. Компромиссное понижает затраты на копирование, но оценки остаются теми же;}
\\
\item[] {Векторное - конкатенация за $\otop(N)$, копирование за $\otop(1)$, доступ за $\otop(1)$;}
\\
\item[] {Векторно-верёвочная модификация - конкатенация/копирование за $\otop(\log_2{N})$, доступ к произвольному элементу за $\otop(\log_2{N})$, можно улучшить практически до $\otop(1)$}
\end{itemize}
\end{frame}
\section{Второй этап}
\begin{frame}
\frametitle{Планы на второй этап}
\begin{itemize}
\item {Реализация верёвочного представления}
\item {Разработка библиотеки времени выполнения}
\end{itemize}
\end{frame}
\end{document}