\documentclass[11pt]{article}

\setlength{\textwidth}{6in}
\setlength{\oddsidemargin}{0.25in}
\setlength{\evensidemargin}{0.25in}
\setlength{\parskip}{5pt}

\input{defs}

\title{Normalization of Field and Probe Expressions}
\author{
 John Reppy \\
  University of Chicago \\
  {\small\tt{}jhr@cs.uchicago.edu} \\
}
\date{\today}

\newcommand{\Fnorm}[1]{\mathcal{F}\LDB{}#1\RDB{}}
\newcommand{\Pnorm}[1]{\mathcal{P}\LDB{}#1\RDB{}}

\begin{document}

\maketitle
\thispagestyle{empty}

\bibliographystyle{../common/alpha}
\bibliography{../common/strings-short,../common/manticore}

\section{Introduction}

This note describes the symbolic transformations that are applied to field and probe expressions in
the Diderot compiler.
The purpose of these transformations is to make the actual compilation of probe operations
more straightforward.
We describe these transformations using three simple expression languages.
The first corresponds to the Diderot surface-language syntax for field and probe expressions.
The second language has the property that derivative operations have been pushed down to the
convolution kernels, and the third language reduces probes to work on images.

\section{The formal model}

In the discussion below, we  use a number of notational conventions that are
summarized in the following table:
\begin{center}
  \begin{tabular}{cp{4in}}
    $V$ & an image \\
    $F$, $G$ & fields \\
    $h$ & a piecewise polynomial convolution kernel \\
    $s$ & a scalar \\
    $\vecx$ & a position in world space 
  \end{tabular}%
\end{center}%

The source language of field expressions is
\begin{displaymath}
  \begin{array}{rcll}
    F & ::= & V\circledast{}h & \text{convolution} \\
      & \mid & F+G & \text{addition} \\
      & \mid & s F & \text{scaling} \\
      & \mid & \nabla{}F & \text{differentiation}
  \end{array}%
\end{displaymath}%
We normalize these expressions by pushing the differentiation operators down to the
kernels, which results in the following language of field expressions:
\begin{displaymath}
  \begin{array}{rcll}
    \hat{F} & ::= & V\circledast{}h^k & \text{convolution with $k$th derivative of $h$} \\
      & \mid & \hat{F}+\hat{G } & \text{addition} \\
      & \mid & s \hat{F} & \text{scaling} \\
  \end{array}%
\end{displaymath}%
The normalization rules are as follows:
\begin{eqnarray*}
  \Fnorm{\nabla{}(V\circledast{}h^k)} & = & V\circledast{}h^{k+1} \\
  \Fnorm{\nabla{}(F+G)} & = & \Fnorm{\nabla{}F} + \Fnorm{\nabla{}G} \\
  \Fnorm{\nabla{}(s F)} & = & s \Fnorm{\nabla{}F}
\end{eqnarray*}%

The syntax of probe operations (after field normalization) is
\begin{displaymath}
  \hat{F}\mkw{@}\vecx
\end{displaymath}%
We normalize these expressions by pushing the probes down to the leaves
and rewriting them as probes into images with the following syntax
\begin{displaymath}
  V\mkw{@}_{h^k}\vecx
\end{displaymath}%
The normalization rules are as follows:
\begin{eqnarray*}
  \Pnorm{(V\circledast{}h^k)\mkw{@}\vecx} & = & V\mkw{@}_{h^k}\vecx \\
  \Pnorm{(F+G)\mkw{@}\vecx} & = & \Pnorm{F\mkw{@}\vecx} + \Pnorm{G\mkw{@}\vecx} \\
  \Pnorm{(s F)\mkw{@}\vecx} & = & s \Pnorm{F\mkw{@}\vecx}
\end{eqnarray*}%

\section{Implementation in the compiler}
These transformations are mostly implemented on the SimpleAST representation.

\end{document}