\documentclass[DI,slideColor,pdf,colorBG]{prosper}

\usepackage[latin1]{inputenc}
\usepackage{graphicx}

\usepackage{epic}
\usepackage{eepic}
\usepackage{ecltree}

\showVersiontrue

%%------------------------------------------------------------------%%

\title{Directory Attribute Grammars}

\author{Alberto Manuel Simões, José João Almeida, Pedro Ranguel
  Henriques} 

\email{albie@alfarrabio.di.uminho.pt, jj@di.uminho.pt,
  prh@di.uminho.pt }

\institution{Departamento de Informática\\Universidade do Minho}

\DefaultTransition{Glitter}

%%------------------------------------------------------------------%%

\begin{document}

\maketitle

%%------------------------------------------------------------------%%

\begin{slide}{Motivation}

\begin{itemize}
\item The most easy way to store and organize files is using the
  filesystem;
\item Filesystems are flexible, but can quickly become chaotic;
\item We need some formal document to define the filesystem structure;
\item The process of makefile creation on each directory is a hard
  task;
\end{itemize}
\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Goals}

\begin{itemize}
\item Define a formalism to specify what can be found in the filesystem;
\item Include in that declarative formalism a description of
  transformations we want to perform to files;
\item Develop a tool to interpret the previous specification,
  executing the desired transformations.
\end{itemize}
\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Approach}

\begin{itemize}
\item While formalizing the filesystem structure, we found:
  
  $$\hbox{directory} \rightarrow \hbox{file}^\star\quad
  \hbox{directory}^\star$$

\item We can define logical types over directories and files;

\item We know that files can have different types:
  
  $$\hbox{\texttt{.xml}; \texttt{.html}; \texttt{.gif};
    \texttt{.jpg};}$$
  


\end{itemize}
\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Filesystem to Grammars}
  Looking to the filesystem structure, we can define:
  \begin{itemize}
  \item files are terminal symbols;
  \item directories are non-terminal symbols --- they can contain more
    non-terminal symbols (directories) and terminal symbols (files);
  \item the root directory is the axiom;
  \item the structure of each directory is described by productions,
    or derivation rules;
  \end{itemize}
\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Grammars with attributes}

\begin{itemize}
\item All the information related to files and directories
  (\textit{type, time stamp}) is represented by attributes
  associated with that symbol;
\item Semantic equations associated to the productions define how to
  propagate attribute values over the tree and how to compute the
  value of derived attributes;
\item Translation rules specify how some attributes can be transformed
  onto another attributes;
\item Attribute values will be stored as new files in the filesystem.
\end{itemize}
\end{slide}

%%------------------------------------------------------------------%%

\part{An Example}

\begin{slide}{Photo-Album}

We want to collect photos from around the world, and structure them:
\begin{itemize}
\item we will use one directory for each continent;
\item directories inside continents are for each country;
\item countries will have photos (image files) and an XML legend file;
\end{itemize}
\end{slide}

%%------------------------------------------------------------------%%
\begin{slide}{The Directory Structure}

\setlength{\GapWidth}{3mm}
\setlength{\GapDepth}{5mm}
\begin{center}
\begin{bundle}{Album}

  \chunk{
    \begin{bundle}{Europe}
      \chunk{
        \begin{bundle}{Portugal}
          \chunk{XML}
          \chunk{$\hbox{JPG}_1$}
          \chunk{$\hbox{JPG}_2$}
        \end{bundle}
      }
      \chunk{
        \begin{bundle}{France}
          \chunk{XML}
          \chunk{$\hbox{JPG}_1$}
        \end{bundle}
      }
    \end{bundle}
  }

  \chunk{
    \begin{bundle}{Asia}
      \chunk{
        \begin{bundle}{Korea}
          \chunk{XML}
          \chunk{$\hbox{JPG}_1$}
          \chunk{$\hbox{JPG}_2$}
        \end{bundle}
      }
    \end{bundle}
  }


\end{bundle}
\end{center}

\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{What we Want}
  
  The processor should:
\begin{itemize}
\item for each Continent, create a HTML file with a country index. The
  country names will be taken from each country directory name;
\item for each Country, create a HTML file with a thumbnail and a
  legend for each photo we have;
\end{itemize}

\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Symbol types}
  
  From the directory structure and objectives, we can get the
  following symbol types:
  \begin{itemize}
\item Non-terminal symbols:
  \begin{itemize}
  \item \textbf{\textsf{Continent}} $\rightarrow$ top directories;
  \item \textbf{\textsf{Country}} $\rightarrow$ Each country directory;
  \end{itemize}
\item Terminal symbols:
  \begin{itemize}
  \item \textbf{\textsf{Photo}} $\rightarrow$ Photographs (.jpg or .gif);
  \item \textbf{\textsf{XML}} $\rightarrow$ The legend file;
  \end{itemize}
\end{itemize}
\end{slide}

%%------------------------------------------------------------------%%
\begin{slide}{Lexer}
  As in normal grammars, we need a lexer. In this case, it should take
  a file (or directory) name and return a string with it's
  type.\\[2mm]
  This can be done using only the full path name, or making it
  depend on the directory contents.\\[2mm]
  In this example, file types are obtained from filename extensions. \\[2mm]
  For directories, we will check if they have, or not, subdirectories.
\end{slide}

%%------------------------------------------------------------------%%
\begin{slide}{\texttt{typeof} function}

{\small
\begin{verbatim}
sub typeof {
    my $file = shift;
    if (-d $file) {
       my @dirs = `ls -l $file|grep ^d`;
       return (@dirs)?"Continent":"Country";
    } else {
       if ($file =~ m!\.(jpg|gif)$!i) 
                        { return "Photo" }
       elsif ($file =~ m!\.xml$!i)
                        { return "XML"   }
       else             { return "ERROR" }
}   }
\end{verbatim} %$
}
\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{The grammar}
  
  The grammar definition uses a slight different syntax from the
  standard grammars. We use a left hand side, an arrow and the right
  hand side. For each right hand side symbol we can associate a
  quantifier.\\[1cm]

\begin{verbatim}
   Continent ---> Country*;

   Country   ---> Photo* XML;
\end{verbatim}

\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Full grammar}
  As in \texttt{yacc} we need to define terminal tokens, in
  \textsf{DAG} we need to define a rule for each one:\\[7mm]

\begin{verbatim}
   Continent ---> Country*;

   Country   ---> Photo* XML;

   Photo;

   XML;
\end{verbatim}
\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Attribute filenames}
  
  As attributes are new files, they should have a special name:

\begin{center}
\begin{tabular}{|r|l|l|}
\hline
Attribute &  &   \\
 name    &  for a file &  for a directory \\
\hline\hline
foo & \verb!_foo_name! & \verb!name/_foo_! \\
.bar & \verb!__name.bar! & \verb!name/__.bar!\\
foo.bar & \verb!_foo_name.bar! & \verb!name/_foo_.bar!\\
!foo & \verb!_name/foo! & \verb!name/_/foo! \\
\hline
\end{tabular}
\end{center}
\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Creating a Thumbnail}
{\small
\begin{verbatim}
Continent ---> Country*;

Country ---> Photo* XML;

Photo;
::TN do{ `convert -geometry '150x150>'
               '$ME->{_}' '$ME->{TN}'` }

XML;
\end{verbatim} }
  

  Brother attribute precedence can be specified!

\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Creating Thumbnail Index File}
{\footnotesize
\begin{verbatim}
Continent ---> Country*;

Country ---> Photo* XML;
::index.html ={
 join("\n", map{ "<br><a href='".
        get_legend($XML->{_},$_->{_}).
        "'><img src='$_->{TN}'></a>" } @Photo);

Photo;
::TN do{ `convert -geometry '150x150>'
               '$ME->{_}' '$ME->{TN}'` }

XML;
\end{verbatim} } %$
\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Creating the Country Index}
{\footnotesize
\begin{verbatim}
Continent ---> Country*;
::index.html ={ join("", 
  map{ "<br><a href='$_->{'index.html'}'>$_->{_}</a>" } 
  @Country) }

Country ---> Photo* XML;
::index.html ={
  join("\n", map{ "<br><a href='".
         get_legend($XML->{_},$_->{_}).
         "'><img src='$_->{TN}'></a>" } @Photo);
...
\end{verbatim} %$
} 
%Photo;
%::TN do{ `convert -geometry '150x150>' '$ME->{_}' '$ME->{TN}'` }
%
%XML;
%\end{verbatim} }
\end{slide}

%%------------------------------------------------------------------%%

\part{A real example}

\begin{slide}{People's Museum}
  
  The ``People's Museum'' (Museu da Pessoa) is a project born here in
  Brazil. About two years ago, we, at Portugal, started a new pole of
  the museum.\\[5mm]
  To generate web pages, we use \textsf{DAG}. The projects are
  structurally processed, generating pages for each one, and for each
  interview inside it.

\end{slide}

%%------------------------------------------------------------------%%
\begin{slide}{The Real Directory Structure}

\setlength{\GapWidth}{3mm}
\setlength{\GapDepth}{5mm}
\begin{center}
\begin{bundle}{Museum}
  \chunk{
    \begin{bundle}{Project A}
      \chunk{
        \begin{bundle}{Interview A}
          \chunk{XML}
          \chunk{
            \begin{bundle}{Album}
              \chunk{$\hbox{JPG}_1$}
              \chunk{$\hbox{JPG}_2$}
            \end{bundle}
          }
        \end{bundle}
      }
      \chunk{
        \begin{bundle}{Interview B}
          \chunk{$\hbox{XML}_1$}
          \chunk{$\hbox{XML}_2$}
        \end{bundle}
      }
    \end{bundle}
  }
  \chunk{
    \begin{bundle}{Project B}
      \chunk{
        \begin{bundle}{Interview C}
          \chunk{XML}
          \chunk{
            \begin{bundle}{Album}
              \chunk{GIF}
              \chunk{JPG}
            \end{bundle}
          }
        \end{bundle}
      }
    \end{bundle}
  }

\end{bundle}
\end{center}

\end{slide}
%%------------------------------------------------------------------%%
\begin{slide}{}
\vskip -2cm
\hskip 1cm
\includegraphics[scale=.23]{mp.eps}
\end{slide}

%%------------------------------------------------------------------%%



\begin{slide}{A real grammar}
  
  Rules for processing are (without the terminal ones):

{\footnotesize
\begin{verbatim}

PROJ ---> PROJ* Interview* Album* Synopsis? XML* 

Interview  ---> XML* Album? SOM? HTML*;

ALBUM ---> GIF* JPG* Photos?;

\end{verbatim} }
\end{slide}

%%------------------------------------------------------------------%%
\begin{slide}{Real attribute samples}
\includegraphics[scale=.23]{mp1.eps}
\includegraphics[scale=.23]{mp2.eps}
\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Real Measures}

\begin{center}
\begin{tabular}{|r|l|}
 \hline
  Tree size &  283 Mbytes \cr
    Decorated tree size &534 Mbytes \cr
 \hline
   XML files &  267 files\cr
           DOC files & 178 files\cr
   GIF and JPG files & $3 + 521 = 524$ files\cr
          HTML files & 14 files\cr
 \hline
\end{tabular}
\end{center}

\end{slide}
%%------------------------------------------------------------------%%
\begin{slide}{Real Measures (cont)}

\begin{center}
\begin{tabular}{|r|l|}
\hline
 HTML attributes &  1 745 files\cr
  JPG attributes &  1 056 files\cr
  EPS attributes &  533   files\cr
   PS attributes &  223 files\cr
 Total attributes & 4 926 files\cr
 \hline
 Traverse the tree & 2 minutes \cr
 Add a simple project & 6 minutes \cr
 Tree build from scratch & 2:30 hours \cr
 \hline
\end{tabular}
\end{center}
\end{slide}
%%------------------------------------------------------------------%%

\part{Concluding...}

\begin{slide}{Future Work}

\begin{itemize}
\item Logging facilities;
  \begin{itemize}
  \item Fatal errors \& Warnings;
  \item Structure verification;
  \end{itemize}
\item \texttt{typeof} function generator;
\item Non-persistent attributes;
\end{itemize}

\end{slide}

%%------------------------------------------------------------------%%

\begin{slide}{Conclusion}

\begin{itemize}
\item Filesystem structure can be checked;
\item Structural filesystem processing is usefull;
\item Quicker than traditional methods;
\item Some work needed on Perl interface;
\end{itemize}

\end{slide}

%%------------------------------------------------------------------%%

\part{Questions \& Answers}

\end{document}
