use typename

[prop.git] / docs / refman.toc

\protect \contentsline {section}{\protect \numberline {1}Introduction}{4}
\protect \contentsline {subsection}{\protect \numberline {1.1}Availability}{4}
\protect \contentsline {subsection}{\protect \numberline {1.2}Organization of this Reference Manual}{4}
\protect \contentsline {section}{\protect \numberline {2}General Concepts}{5}
\protect \contentsline {subsection}{\protect \numberline {2.1}Syntactic Conventions}{5}
\protect \contentsline {subsection}{\protect \numberline {2.2}Basic syntactic classes}{5}
\protect \contentsline {subsection}{\protect \numberline {2.3}Literals}{5}
\protect \contentsline {subsection}{\protect \numberline {2.4}The {\bsf Prop}{} Language}{5}
\protect \contentsline {section}{\protect \numberline {3}Lexer and Parser Generation}{7}
\protect \contentsline {subsection}{\protect \numberline {3.1}Lexer Specification}{7}
\protect \contentsline {subsubsection}{\protect \numberline {3.1.1}Regular expressions}{7}
\protect \contentsline {subsubsection}{\protect \numberline {3.1.2}Lexeme}{8}
\protect \contentsline {subsubsection}{\protect \numberline {3.1.3}Lexeme class}{8}
\protect \contentsline {subsubsection}{\protect \numberline {3.1.4}Tokens}{9}
\protect \contentsline {subsubsection}{\protect \numberline {3.1.5}The {\protect \tt matchscan} statement}{9}
\protect \contentsline {subsubsection}{\protect \numberline {3.1.6}Class {\protect \tt LexerBuffer}}{11}
\protect \contentsline {subsubsection}{\protect \numberline {3.1.7}Class {\protect \tt IOLexerBuffer}}{12}
\protect \contentsline {subsubsection}{\protect \numberline {3.1.8}Class {\protect \tt IOLexerStack}}{12}
\protect \contentsline {subsection}{\protect \numberline {3.2}Parser Specification}{13}
\protect \contentsline {subsubsection}{\protect \numberline {3.2.1}Syntax class}{13}
\protect \contentsline {subsubsection}{\protect \numberline {3.2.2}Syntax declaration}{13}
\protect \contentsline {subsubsection}{\protect \numberline {3.2.3}Precedence}{14}
\protect \contentsline {subsubsection}{\protect \numberline {3.2.4}{\protect \tt expect:} $n$}{14}
\protect \contentsline {subsubsection}{\protect \numberline {3.2.5}Production rules}{15}
\protect \contentsline {subsubsection}{\protect \numberline {3.2.6}Parser report}{16}
\protect \contentsline {subsubsection}{\protect \numberline {3.2.7}Interfacing with the generated lexer}{16}
\protect \contentsline {subsection}{\protect \numberline {3.3}Debugging Parsers}{16}
\protect \contentsline {section}{\protect \numberline {4}Algebraic Datatypes and Pattern Matching}{17}
\protect \contentsline {subsection}{\protect \numberline {4.1}A quick tour of pattern matching}{17}
\protect \contentsline {subsubsection}{\protect \numberline {4.1.1}Pattern matching versus object-oriented style}{18}
\protect \contentsline {subsubsection}{\protect \numberline {4.1.2}More examples}{19}
\protect \contentsline {subsubsection}{\protect \numberline {4.1.3}Variants of match}{22}
\protect \contentsline {subsection}{\protect \numberline {4.2}Algebraic Datatypes}{23}
\protect \contentsline {subsubsection}{\protect \numberline {4.2.1}Instantiating a datatype}{25}
\protect \contentsline {subsection}{\protect \numberline {4.3}Pattern Matching}{25}
\protect \contentsline {paragraph}{Cost minimization}{26}
\protect \contentsline {paragraph}{Match all rules}{26}
\protect \contentsline {paragraph}{Repetition}{26}
\protect \contentsline {paragraph}{Pattern syntax}{26}
\protect \contentsline {subsection}{\protect \numberline {4.4}Refining a datatype}{27}
\protect \contentsline {subsection}{\protect \numberline {4.5}Memory management}{29}
\protect \contentsline {subsubsection}{\protect \numberline {4.5.1}Garbage collection}{29}
\protect \contentsline {subsubsection}{\protect \numberline {4.5.2}Persistence}{30}
\protect \contentsline {section}{\protect \numberline {5}Inference}{32}
\protect \contentsline {subsection}{\protect \numberline {5.1}An Example}{32}
\protect \contentsline {subsubsection}{\protect \numberline {5.1.1}Another example}{33}
\protect \contentsline {subsection}{\protect \numberline {5.2}Inference Class}{33}
\protect \contentsline {subsection}{\protect \numberline {5.3}Inference Rules}{34}
\protect \contentsline {section}{\protect \numberline {6}Tree Rewriting}{35}
\protect \contentsline {subsection}{\protect \numberline {6.1}A rewriting example}{35}
\protect \contentsline {subsubsection}{\protect \numberline {6.1.1}Conditional rewriting and actions}{36}
\protect \contentsline {subsection}{\protect \numberline {6.2}Rewrite class}{37}
\protect \contentsline {subsection}{\protect \numberline {6.3}Rewriting rules}{37}
\protect \contentsline {subsection}{\protect \numberline {6.4}Rewriting modifiers}{38}
\protect \contentsline {subsubsection}{\protect \numberline {6.4.1}Rewriting modifier example}{38}
\protect \contentsline {subsection}{\protect \numberline {6.5}The {\protect \tt rewrite} statement}{40}
\protect \contentsline {subsubsection}{\protect \numberline {6.5.1}Rewriting modes}{41}
\protect \contentsline {subsubsection}{\protect \numberline {6.5.2}State caching optimization}{41}
\protect \contentsline {subsubsection}{\protect \numberline {6.5.3}Specifying secondary indices}{42}
\protect \contentsline {subsubsection}{\protect \numberline {6.5.4}Using an internal index}{42}
\protect \contentsline {subsubsection}{\protect \numberline {6.5.5}Using an external index}{43}
\protect \contentsline {paragraph}{Class {\protect \tt RewriteCache}}{44}
\protect \contentsline {paragraph}{Class {\protect \tt GCRewriteCache}}{44}
\protect \contentsline {subsection}{\protect \numberline {6.6}Short circuiting rewrite paths with {\protect \tt cutrewrite}}{45}
\protect \contentsline {subsection}{\protect \numberline {6.7}Conditional failure with {\protect \tt failrewrite}}{46}
\protect \contentsline {subsection}{\protect \numberline {6.8}Confluence and termination}{46}
\protect \contentsline {subsection}{\protect \numberline {6.9}Debugging Tree Rewriting}{47}
\protect \contentsline {subsection}{\protect \numberline {6.10}Optimizing Tree Rewriting}{47}
\protect \contentsline {section}{\protect \numberline {7}User defined datatypes: Views}{49}
\protect \contentsline {subsection}{\protect \numberline {7.1}A first example}{49}
\protect \contentsline {subsection}{\protect \numberline {7.2}Another view example}{51}
\protect \contentsline {subsection}{\protect \numberline {7.3}Syntax of view definitions}{52}
\protect \contentsline {section}{\protect \numberline {8}Graph Types and Graph Rewriting}{54}
\protect \contentsline {subsection}{\protect \numberline {8.1}Graph Types}{54}
\protect \contentsline {subsection}{\protect \numberline {8.2}The Graph Interface}{54}
\protect \contentsline {subsection}{\protect \numberline {8.3}Set Formalisms}{54}
\protect \contentsline {subsection}{\protect \numberline {8.4}Graph Rewriting}{55}
\protect \contentsline {section}{\protect \numberline {9}Running the Translator}{56}
\protect \contentsline {subsection}{\protect \numberline {9.1}Options}{56}
\protect \contentsline {subsection}{\protect \numberline {9.2}Error Messages}{57}
\protect \contentsline {section}{\protect \numberline {A}Garbage Collection in the {\protect \sf Prop} Library}{63}
\protect \contentsline {subsection}{\protect \numberline {A.1}Introduction}{63}
\protect \contentsline {subsection}{\protect \numberline {A.2}The Framework}{63}
\protect \contentsline {subsection}{\protect \numberline {A.3}Our Framework}{63}
\protect \contentsline {subsection}{\protect \numberline {A.4}The Implementation}{64}
\protect \contentsline {subsection}{\protect \numberline {A.5}Architecture}{64}
\protect \contentsline {subsection}{\protect \numberline {A.6}The Programmatic Interface}{64}
\protect \contentsline {subsection}{\protect \numberline {A.7}Memory Allocation}{65}
\protect \contentsline {subsection}{\protect \numberline {A.8}The GC Protocol}{66}
\protect \contentsline {subsection}{\protect \numberline {A.9}Messages and Statistics}{66}
\protect \contentsline {subsection}{\protect \numberline {A.10}The Bartlett style mostly copying collector}{68}
\protect \contentsline {subsection}{\protect \numberline {A.11}The Mark Sweep collector}{68}
\protect \contentsline {subsection}{\protect \numberline {A.12}Finalization}{68}
\protect \contentsline {subsubsection}{\protect \numberline {A.12.1}Weak Pointers}{69}
\protect \contentsline {subsubsection}{\protect \numberline {A.12.2}The Heap Walker}{70}