\documentclass[a4paper]{article}
\usepackage[T2A]{fontenc}
\usepackage[koi8-r]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{url}
\newcommand\city[1]{\begin{center}#1\end{center}}
\newcommand\project[1]{\begin{center}#1\end{center}}
\newcommand\organization[1]{\begin{center}#1\end{center}}

\begin{document}

\title{Подход к переносимой реализации языка XQuery}
\author{Паращенко Олег}
\maketitle
\project{Protva XQuery}
\city{Санкт-Петербург}
\organization{Санкт-Петербургский Государственный Университет}
\begin{abstract}
XQuery, язык запросов XML, можно рассматривать как обобщённый интерфейс к древовидным данным. В работе обосновывается идея создания переносимой системы XQuery, которая может обрабатывать любые деревья, и предлагается реализация с помощью виртуальной машины.
\end{abstract}

% =========================================================

\section{Зачем обычным приложениям XQuery}

Один из подходов к обработке XML\cite{xml}~--- это представление его в виде дерева, для навигации по которому используется XPath\cite{xpath}. На основе XPath созданы языки для преобразования XML: XSLT\cite{xsl} и XQuery\cite{xquery}. XSLT является языком шаблонов, а XQuery можно представить как значительно расширенный XPath.

XML можно рассматривать как внешнее текстовое представление древовидных структур, а связанные с XML стандарты~--- как способы обработки таких данных. Такой подход может оказаться полезным для некоторых видов программ, например,
\begin{itemize}
\item для текстовых процессоров и
\item компиляторов и интерпретаторов.
\end{itemize}

В подобных приложениях важную роль играют сложные запросы к деревьям, например:
\begin{itemize}
\item найти все заголовки, не помеченные как удалённые, и создать из них оглавление;
\item найти присваивания вместо сравнений в блоках условий команд if, for, while и им подобных.
\end{itemize}

Прямолинейная реализация таких приложений зачастую сложна, а код оказывается более низкого уровня чем решаемая задача. В качестве альтернативы предлагается использовать встроенный XQuery, что должно упростить написание программ.

% =========================================================

\section{Подход к реализации}

Основная проблема при разработке системы XQuery~--- это большой объём работ, поэтому не стоит писать XQuery каждый раз заново. Лучше создать переносимую реализацию и портировать её в приложения с минимальными затратами.

Для этого предлагается разработать виртуальную машину для обработки деревьев и систему XQuery на её основе. Если какому-либо приложению потребуется поддержка XQuery, то достаточно будет реализовать эту машину.

Чтобы упростить разработку, код пишется и отлаживается на языке Common Lisp, а затем транслируется в ассемблер виртуальной машины. За основу взята система CL-XML\cite{clxml}. James Anderson, её автор, проделал большую работу, так что CL-XML уже обрабатывает все примеры из спецификации XQuery.

CL-XML переводит XQuery во внутреннее промежуточное представление в виде абстрактного синтаксического дерева (AST). Этот формат можно использовать для высокоуровневой оптимизации запросов.

Большая часть языковых конструкций Common Lisp реализована с помощью макросов. Если взять CL-XML и раскрыть все макросы, то получится программа, состоящая из примитивов. Набор полученных конструкций является черновой версией виртуальной машины.

Реализация диалекта минимального Lisp (или Scheme) не составляет сложности, так как является хорошо изученной задачей \cite{schemecomp}.

Отдельный интерес представляет трансляция нашей виртуальной машины на LLVM\cite{llvm}~--- промежуточное представление и набор инструментов для оптимизации программ. Благодаря LLVM и высокоуровневой оптимизации, код вычисления XQuery может быть эффективнее вручную написанного аналога.

% =========================================================

\section{Статус}

Проект находится в начальной стадии. Пока только готов план работ, проведены первые эксперименты и подобраны инструменты для реализации. Промежуточные отчёты будут выкладываться на странице проекта Protva XQuery\cite{protva}, код будет распространяться по лицензии LGPL.

На конференции будут представлены черновая версия виртуальной машины и первые результаты.

Первой вехой проекта будет добавление поддержки XQuery в XSLT-процессор xsltproc\cite{xsltproc}.

% =========================================================

\begin{thebibliography}{99}

\bibitem{protva} Проект Protva XQuery \url{http://xmlhack.ru/protva/}

\bibitem{xml} Extensible Markup Language (XML) \url{http://www.w3.org/XML/}

\bibitem{xpath} XML Path Language (XPath) \url{http://www.w3.org/TR/xpath}

\bibitem{xsl} The Extensible Stylesheet Language Family (XSL) \url{http://www.w3.org/Style/XSL/}

\bibitem{xquery} XML Query (XQuery) \url{http://www.w3.org/XML/Query}

\bibitem{clxml} CL-XML: Common Lisp support for XML \url{http://cl-xml.org/}

\bibitem{schemecomp} Scheme Compiler Technology/Implementation Techniques and Optimi\-zation \url{http://library.readscheme.org/page8.html}

\bibitem{llvm} The LLVM Compiler Infrastructure Project. \url{http://llvm.cs.uiuc.edu/}

\bibitem{xsltproc} The XSLT C library for Gnome \url{http://xmlsoft.org/XSLT/}

\end{thebibliography}

\end{document}