\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#249: Unification of Tcl's Parsing of Numbers}
\date{June 13, 2005}
\author{Kevin B. Kenny, David S. Cargo, Don Porter}
\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 \#249}&\textbf{Unification of Tcl's Parsing of Numbers}\\\hline
Author&

Kevin B. Kenny \tipmail{kennykb}{acm.org}
\par
David S. Cargo \tipmail{escargo}{skypoint.com}
\par
Don Porter \tipmail{dgp}{users.sf.net}
\\
Created&Monday, \(\text{13}^{\text{th}}\) June 2005\\
Type&Informative\\
State&Draft\\
Vote&No voting\\
Version&\tipversion$Revision: 1.9 $\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes to unify the recognition of all of Tcl's ``numeric'' objects into a single parser. The intended effect is to improve performance by eliminating a number of cases where a cached numeric representation may be discarded, and to restore (more accurately, to establish) the ``everything is a string'' principle in dealing with numbers.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

Tcl's handling of numbers has always been problematic and ambiguous. Even in the earliest releases of the \textbf{expr} command, there were issues with the unexpected demotion of floating point numbers to integers, causing subsequent divisions to be interpreted as integer division with incorrect results.

Another trouble spot has been the interpretation of constants with leading zeroes. When these are interpreted as integers, they are octal numbers. They can also be interpreted as floating point constants (at least with \textit{Tcl\_GetDoubleFromObj}), in which case they are decimal. Because of this ambiguity, the \textbf{expr} system cannot make effective use of the internal representation of a floating point number; it needs to refer back to the string to make sure that the number is not an octal integer to which \textit{Tcl\_GetDoubleFromObj} has been applied.

Even more confusing is the treatment of numbers that have leading zeroes but contain the digits 8 or 9. These are rejected by the \textbf{expr} parser as invalid octal but are accepted by \textit{Tcl\_GetDoubleFromObj}.

\section{Proposal}

This TIP proposes a strict ``everything is a string'' interpretation for strings as numeric values. The set of strings that can be interpreted as numbers shall be partitioned into disjoint subsets, with a single ``canonical'' representation for each.

This change will imply that a few C calls will break compatibility. In particular, \textit{Tcl\_GetDoubleFromObj} may leave an integer internal representation in the object, despite the documentation's assertion that the object will shimmer. Similarly, \textit{Tcl\_GetDoubleFromObj} will no longer interpret octal integers as decimal; this feature causes only surprise and consternation.

The \textit{Tcl\_ConvertToType} call will also no longer force conversion to a specific numeric type. Since it does not do so, it is not reasonable for extensions to use it on the numeric types. For this reason, the numeric types \textit{shall not be registered;} \textit{Tcl\_GetObjType} will fail when presented with one of their names.

When one of the conversion procedures \textit{Tcl\_GetIntFromObj}, \textit{Tcl\_GetWideIntFromObj}, \textit{Tcl\_GetBignumFromObj} (assuming the eventual approval of \cite{tip237}), or \textit{Tcl\_GetDoubleFromObj} is called, it will cast any pre-existing numeric internal representation that it finds to the appropriate return type (throwing an error if the number is too large to represent, or a double is used in an integer context). If the procedure finds no pre-existing numeric internal representation, it will extract the string representation, determine its canonical representation as a number, and store that.

The easiest way to visualize the specific sets of strings that are recognized as numbers is with a diagram of the state machine that implements them.

\begin{figure}[htbp]\begin{center}\leavevmode
\fbox{\tiny\url{249statemachine}}
\caption{State machine that recognizes numbers.}
\end{center}\end{figure}

In the diagram, ``Start'' represents the start state of the machine. The leading and trailing whitespace that is allowed for all numbers is not diagrammed, for clarity.

Intermediate states of the machine are represented by small ovals. Large rectangles represent final states, and are labeled with the type of number that will result. Note that any number can optionally begin with a '+' or '-' character, which will not be mentioned further. Each of the accepting states, however, merits further discussion.
\begin{enumerate}
\item{}
The string ``0'' shall always represent an integer of the smallest type available (\textbf{tclIntType}). It shall never represent a floating point value.
\setcounter{enumi}{1}
\item{}
A leading zero followed by a string of octal digits shall be interpreted as an octal integer. The integer shall be stored in the smallest of \textbf{tclIntType}, \textbf{tclWideIntType} and \textbf{tclBignumType} that will hold it. (Note that storing \textbf{tclBignumType} is possible without accepting \cite{tip237}, provided that the \textit{Tcl\_Get*FromObj} routines recognize it and convert its value as needed.) The interpretation as an octal integer shall hold even if the string is presented to \textit{Tcl\_GetDoubleFromObj}, which today interprets it as decimal.
\setcounter{enumi}{2}
\item{}
A leading zero, followed by the letter 'X' (case insensitive) and a string of hexadecimal digits shall be interpreted as a hexadecimal integer. Again, the smallest representation needed is chosen.
\setcounter{enumi}{3}
\item{}
A string of decimal digits beginning with a nonzero digit is interpreted as a decimal integer and stored in the smallest suitable internal representation.
\setcounter{enumi}{4}
\item{}
A string of digits beginning with a zero but containing the digits \textbf{8} or \textbf{9} is an error; it appears to be bad octal. It would be possible to allow this case in \textit{Tcl\_GetDoubleFromObj}, but it seems unwise, since the consequence would be that \textbf{string is double} would accept ``double'' strings that will fail in \textbf{expr}.
\setcounter{enumi}{5}
\item{}
A string consisting of a nonempty sequence of decimal digits and a single period (which may appear anywhere within the string) is a valid floating point constant in 'F' format, even if it begins with '0'. It is interpreted in decimal and stored in a \textbf{tclDoubleType}. If the input number is too small to represent, an appropriately signed zero is stored. If the input number is too large to represent, an appropriately signed infinity is stored.
\setcounter{enumi}{6}
\item{}
Floating point numbers in the usual 'E' format are accepted and interpreted in decimal. Once again, they are stored in \textbf{tclDoubleType} and are replaced with zero or infinity if they are too small or large.
\setcounter{enumi}{7}
\item{}
The constants, ``Inf'', and ``Infinity'' (perhaps with a leading signum) are interpreted as infinities. Infinity is represented as \textbf{tclDoubleType.}
\setcounter{enumi}{8}
\item{}
The constant ``NaN'' is the IEEE ``Not a Number'' value. It is specifically permitted in the parser so that \textbf{binary format q NaN} and similar calls can produce NaN on an external medium. The presence of NaN in expressions, or in \textit{Tcl\_GetDoubleFromObj}, signals an error. NaN is represented as \textbf{tclDoubleType}.
\setcounter{enumi}{9}
\item{}
IEEE floating point does not have a single unique NaN value, so a NaN may be augmented by a parenthesized string of hexadecimal digits, which will be stored in its least significant bits. It shall not be possible to construct signalling NaN by this route; only quiet NaN will be supported. NaN is represented as \textbf{tclDoubleType.}
\end{enumerate}

\section{Additions}

In addition to the base state machine detailed above, the state machine of the reference implementation contains additional states to parse integer values beginning with the \textbf{0b} or \textbf{0o} prefixes as originally proposed in \cite{tip114}. Getting these prefixes recognized in Tcl 8.5 is an important migration step to support migration to whatever version of Tcl drops the ``leading \textbf{0} implies octal format'' rule.

Also in addition, the parsing routine will accept a \textit{flags} value containing the flag bits below that exert finer control on the parsing. These extra controls were found to be required to permit the [scan] command to use the same parser.
\begin{itemize}
\item{}
\textbf{TCL\_PARSE\_INTEGER\_ONLY} -{}- accept only integer values; reject strings that denote floating point values (or accept only the leading portion of them that are integer values).
\item{}
\textbf{TCL\_PARSE\_SCAN\_PREFIXES} -{}- ignore the prefixes \textbf{0b} and \textbf{0o} that are not part of the [scan] command's vocabulary. Use only in combination with \textbf{TCL\_PARSE\_INTEGER\_ONLY}.
\item{}
\textbf{TCL\_PARSE\_OCTAL\_ONLY} --- parse only in the octal format, whether or not a prefix is present that would lead to octal parsing. Use only in combination with \textbf{TCL\_PARSE\_INTEGER\_ONLY}.
\item{}
\textbf{TCL\_PARSE\_HEXADECIMAL\_ONLY} --- parse only in the hexadecimal format, whether or not a prefix is present that would lead to hexadecimal parsing. Use only in combination with \textbf{TCL\_PARSE\_INTEGER\_ONLY}.
\item{}
\textbf{TCL\_PARSE\_DECIMAL\_ONLY} --- parse only in the decimal format, no matter whether a \textbf{0} prefix would normally force a different base.
\end{itemize}

\section{Incompatibilities}

The change described is sufficient to run the Tcl and Tk test suites with unwanted test results only in the detailed format of error messages for integer overflow and in the types returned by using the \textbf{testobj} command (not part of the usual distribution) to introspect them. Despite this reassurance, several potential incompatibilities are identified.

First, as mentioned above, C extensions will no longer have fine control over Tcl's built-in numeric types, because the types will not be registered and hence will be unavailable for use with \textit{Tcl\_ConvertToType.} This is actually a good thing, since it means that the rest of Tcl can assume that they are well-behaved, resulting in a considerable simplification. Most of the Tcl Core Team believes that \textit{Tcl\_ConvertToType} has no legitimate use in any case.

Second, it will no longer be correct to assume that \textit{Tcl\_Get*FromObj} will leave an internal representation of precisely the requested type. It is, in any case, a highly questionable practice for callers to assume a specific internal representation (with the possible exception of Tcl\_Set*Obj and Tcl\_New*Obj). There will no doubt be a few extensions that run afoul of this change, but they can be fixed easily in such a way that they will continue to compile and run on earlier versions of Tcl.

Third, \textit{Tcl\_GetDoubleFromObj} will be both more and less permissive than before. It will no longer accept constants with a leading zero and no decimal point or 'E' that are invalid octal numbers. On the other hand, it will accept constants that are too large to fit in a \textbf{Tcl\_WideInt}; somewhat surprisingly, \textbf{string repeat 9 50} cannot today be interpreted as a double. \textbf{string is double} will follow \textit{Tcl\_GetDoubleFromObj} in what it considers acceptable. Any string that is accepted as either an integer or a double by \textbf{expr} will be accepted in \textit{Tcl\_GetDoubleFromObj}, and only those strings will be accepted.

Fourth, the recognition of \textbf{0b} and \textbf{0o} as valid prefixes for integer values is a type of incompatibility.

\section{Reference Implementation}

See \cite{tip237} for more implementation details.

\section{Copyright}

Copyright (c) 2005 by Kevin B. Kenny. All rights reserved. 

This document may be distributed subject to the terms and conditions set forth in the Open Publication License, version 1.0 [\url{http://www.opencontent.org/openpub/}].

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\begin{thebibliography}{TIP \#2}
\addcontentsline{toc}{section}{References}
\bibitem[TIP \#114]{tip114}
Don Porter,
\emph{Eliminate Octal Parsing of Leading Zero Integer Strings},
on-line at \url{http://purl.org/tcl/tip/114.html}
\bibitem[TIP \#237]{tip237}
Kevin B. Kenny,
Don Porter,
\emph{Arbitrary-Precision Integers for Tcl},
on-line at \url{http://purl.org/tcl/tip/237.html}
\end{thebibliography}
\end{document}
