\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#309: Expose the Expression Parsing}
\date{January 07, 2008}
\author{Arjen Markus}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#309}&\textbf{Expose the Expression Parsing}\\\hline
Author&

Arjen Markus \tipmail{arjen.markus}{wldelft.nl}
\\
Created&Monday, \(\text{7}^{\text{th}}\) January 2008\\
Type&Project\\
Tcl Version&\(8.7\)\\
State&Draft\\
Vote&Pending\\
Version&\tipversion$Revision: 1.2 $\\
Keywords&expr, parse\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes a new command to expose the parsing of expressions by the \textbf{expr} command. This will make it much easier to implement alternative number systems, such as complex numbers, or to implement symbolic algebra.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

The \textbf{expr} command uses the traditional infix notation for arithmetical expressions. Tcl itself uses a prefix notation. While it is quite easy to create a set of procedures to do complex number arithmetic, using them means the use of prefix notation, for example:

A polynomial expression like \textit{1 + i*z**2} could become:
\begingroup\small\begin{verbatim}
 [add [complex 1 0] [mult [complex 0 1] $z $z]
\end{verbatim}
\endgroup

(where [complex] is used to make sure the constants are complex).

People used to the infix notation will find this a very clumsy, if not error-prone way of working.

Basic symbolic algebra, like the determination of a derivative (useful for certain numerical algorithms) is much easier when working with the prefix notation:
\begingroup\small\begin{verbatim}
 deriv [add $expr1 $expr2] --> add [deriv $expr1] [deriv $expr2]
\end{verbatim}
\endgroup

This calls for an easy way to convert an infix notation to Tcl's prefix notation.

\section{Proposal}

Introduce a new command, tentatively called s-expr, as this is the traditional term used in LISP for expressions in the prefix notation, that converts a given infix expression into an equivalent prefix expression.

The rules are simple:
\begin{itemize}
\item{}
Any valid \textbf{expr} expression can be converted. Invalid expressions result in the same error messages as if they were meant for \textbf{expr}.
\item{}
The symbolic name for the command is simply the same as the string that represents the operation.
\item{}
Operations have the same precedence as for \textbf{expr}. This TIP does not include a mechanism for introducing new operations.
\item{}
Functions are translated into a command of the same name (no particular namespace) and the list of comma-separated arguments is converted into an ordinary sequence of arguments.
\item{}
Errors that result from the evaluation of the expression are handled by the particular implementation of the operations and functions.
\item{}
The resulting string can then be used by \textbf{eval} or \textbf{uplevel} to run the set of commands in the right order.
\end{itemize}

\section{Implementation Notes}

There is no implementation of this command yet, but here is a sketch:
\begin{itemize}
\item{}
Let the \textbf{expr} parser construct a parse tree from the command.
\item{}
Let a new function convert the parse tree into a string holding the prefix expression and pass that to the interpreter as the result of [s-expr].
\end{itemize}

This limits the sort of expressions (in particular ``constants'' as understood by the specific arithmetic system) to expressions that can be parsed by the \textbf{expr} parser, but as this now handles lists, as a consequence of the \textbf{in} and \textbf{ni} operations, this does not seem a severe limitation.

The advantage of this approach is that much of the hard work is already done and that compatibility with the \textbf{expr} command is ensured.

\section{Copyright}

This document is placed in the public domain

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\end{document}
