\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#185: Null Handling}
\date{April 08, 2004}
\author{John H. Harris}
\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 \#185}&\textbf{Null Handling}\\\hline
Author&

John H. Harris \tipmail{JHHarris}{valley.net}
\\
Created&Thursday, \(\text{8}^{\text{th}}\) April 2004\\
Type&Project\\
Tcl Version&\(8.6\)\\
State&Rejected\\
Vote&Done\\
Version&\tipversion$Revision: 1.8 $\\
Keywords&Tcl, absent value\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

Tcl lacks the ability to handle \textit{nulls}, data with missing or unknown values. In this TIP I suggest a means for representing and propagating nulls, and command modifications for manipulating them.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

Tcl deals with strings, the universal medium for representing data. It lacks, however, the intrinsic ability to represent \textit{missing} data, or \textit{nulls}. A null datum (or just ``null'') is very different from an empty string. A database may represent Prince's last name as "`` -{}- his name is know and it is an empty string, but if a respondent forgets to give his weight on a questionnaire, he is not weightless; his weight is not ''"; it is unknown, or \textit{null}. Nulls are common in real-world data, particularly data obtained from interviews or questionnaires. Because of this, most modern database engines and statistics tools recognize nulls. A large fraction of the applications we are writing are client programs to such databases, though the user is not always aware of it.

The programmer can use whatever is provided with the database application program interface (API) he is using, but most Tcl APIs provide none, probably because Tcl itself lacks nulls.

A Tcl programmer writing an interface to a database must improvise something to deal with nulls. If the data representation domain does not include an empty string, as for an integer or date, then an empty string may suffice, but arbitrary-string data is common, so something fancier is often needed.

For example, here is an approach I used in a current project built on SQLite [1]. I prepend each nonnull string with an apostrophe. Thus, nulls are universally represented by an empty string. I accomplish this using the \textit{coalesce()} function provided by SQLite, e.g., if I want
\begingroup\small\begin{verbatim}
  select id, name from persons
\end{verbatim}
\endgroup

I must ask for
\begingroup\small\begin{verbatim}
  select id, coalesce(''||name,'') as name from persons
\end{verbatim}
\endgroup

I wrote a layer that automates this ugly mess. To keep it simple (and because SQLite is untyped) it prepends \textit{all} fields with an apostrophe, even ones that do not need it. I deal with the apostrophes later -{}- testing for nullness is easy, but the apostrophe gets in the way for most other I/O and processing.

This is more than you wanted to know about my personal problems, but you can be sure this kind of thing is happening over and over with hundreds of programmers and applications.

Now let us imagine how it might be simplified, assuming Tcl null support and a revamped SQLite API:
\begingroup\small\begin{verbatim}
  set result [ db eval {select id, name from person}
  foreach -null <unknown> { id name } $result {
     puts "$id: $name" }
\end{verbatim}
\endgroup

I will explain more later, but basically, the database returns null information on \textit{every} query, so there is no fancy SQL code. The \textbf{-null} option tells \textbf{foreach} how to represent a null when it assigns \textit{id} and \textit{name}.

\section{Specification}

It would be nice if null handling could be added to, or with, a single command suite. If we could just extend, say, the \textbf{dict} command, these objects would be ideal media for database APIs. Unfortunately, it seems impossible to implement any change with out involving Tcl's string implementation, list syntax, and command interpreter.

\subsection{Representing Nulls}

Not all commands will understand nulls. We will speak of null-smart and null-dumb commands. All commands follow these rules:
\begin{enumerate}
\item{}
Nulls represent a lack of information.
\setcounter{enumi}{1}
\item{}
An empty string is not null.
\setcounter{enumi}{2}
\item{}
Nulls can not be made ``unnull'', merely by being processed. This is equivalent to creating information out of thin air. Substituting a nonnull value for a null must programmed explicitly.
\setcounter{enumi}{3}
\item{}
For null-smart commands, nulls propagate. A null combined with any nonnull is null. Appending a null to a string, or substituting a null into a string nulls the entire string.
\setcounter{enumi}{4}
\item{}
Logical comparisons with nulls with respect to magnitude or identity evaluate to null (i.e., \textit{unknown}).
\setcounter{enumi}{5}
\item{}
Null-dumb commands must treat nulls as empty strings.
\end{enumerate}

\subsubsection{Strings Objects}

An empty string is not a null. We have the further constraint that we must be able to handle any arbitrary binary string, including null (in the sense of 0x00) bytes. Clearly the implementation must be augmented; we must add a null flag. In implementation, null strings would probably have their string part set to an empty string, to accommodate null-dumb commands, as in rule 6 above. Thus, dumb commands can simply ignore the null flag.

\subsubsection{List Syntax}

It is easy to add a null flag to the string class. To be of any use, however, we need to pass a null string to commands, which means embedding nulls in lists. We can indicate this much in the same way the \textit{\{expand\}\{\}} syntax \cite{tip157} works, by exploiting otherwise illegal list syntax. I propose using \textbf{\{null\}!} as null representation for lists. (Perhaps new syntax could be a rider on the \textit{\{expand\}\{\}} rule. I fear that increasing the number of rules could scuttle this TIP.) At present this syntax (like \{expand\}\{\}) produces an ``extra characters after close-brace'' error.

Note that the string ``\{null\}!'' is \textit{not} interpreted as a null string, instead it is a nonnull string that is also a well-formed list with one null element.

\subsubsection{Interpreter Behavior}

If the command interpreter encounters the word ``\{null\}!'' in a list, this element is replaced by a null string in the array of strings passed to the command.

When the Tcl command interpreter encounters a word that contains a variable substitution, if the variable contains a null, the interpreter will behave as if the entire word were replaced with ``\{null\}!'', and pass a null string to the command in its place.

Command substitutions behave the same way when a command returns a null.

\subsection{Manipulating Nulls}

We need not be decided how commands should respond to nulls all at once. Indeed, it would be better to let this evolve as we gain experience with this new dimension of data. At first we will need at least some basic support to create, copy and test nulls.

\subsubsection{The String Command}

The simplest approach is simply to test for nullness. The obvious candidate for this test would be an addition to the \textit{string is} command suite:
\begingroup\small\begin{verbatim}
  if { [ string is null $s ] } {
     error {Missing data for s.} }
\end{verbatim}
\endgroup

The string command could also be used to generate nulls:
\begingroup\small\begin{verbatim}
  set null [ string null ]
\end{verbatim}
\endgroup

\subsubsection{The Set Command}

We can use \textit{set} to create a variable that contains a null string:
\begingroup\small\begin{verbatim}
   % set s {null}!
\end{verbatim}
\endgroup

Now \textit{s} exists and has its null flag set. This is such a natural syntax that it probably make \textit{string null} unnecessary.

We can retrieve a null value with \textit{set} -{}- suppose \textit{puts} is dumb and sees the null as an empty string:
\begingroup\small\begin{verbatim}
  % puts "s equals [ set s ]"
\end{verbatim}
\endgroup

\textbf{Set} returns a null. In this case, the null is in a command substitution, and it nulls the entire string being passed to \textbf{puts}, which, being null-dumb, outputs an empty string and newline. This may be unsatisfactory. We would rather substitute a nonnull, perhaps an empty string, or ``\tiplangle{}NULL\tiprangle{}''.

When and what to substitute is an ad hoc programming choice, so should be an option. Here is the \textit{set} command with an option that tells how to represent a null:
\begingroup\small\begin{verbatim}
  % set s {null}!
  % set -null <NULL> s
  <NULL>
  % set -null huh? s
  huh?
\end{verbatim}
\endgroup

The default value for this option is a null, so \textbf{[set s]} can be used as a direct substitution for \textbf{\$s}, as you would expect.

While we must allow for the worst case of representing a null amidst the set of arbitrary binary strings, in practical data this seldom occurs. When it does, we must resort to an explicit test and conditional execution, but more often there is some gap in the domain of valid data that can be used to represent a null. We have already seen the example of using and empty string for a null integer or date. For other data types there are better choices. The programmer knows these gaps and can choose a string that fits in the gap and is also easily understood by humans or other software.

The \textbf{-null} option should have the same meaning when applied to any null-smart command: if the return value is a null, change it to the option value.

The set command can use a similar option to assign a null. This time the option \textbf{-nullify} tells what value, by exact match, should be replaced by a null.
\begingroup\small\begin{verbatim}
  % set s NULL
  NULL
  % set -nullify NULL t $s
  % puts '[ set -null Void t ]'
  'Void'
\end{verbatim}
\endgroup

Notice that string \textit{s} above is \textit{not} a null, it is the string ``NULL''. The second command translates it to a true null, and the third translates it to ``Void''.

The \textbf{-nullify} option provides a way of assigning a null to a variable that is independent of list syntax:
\begingroup\small\begin{verbatim}
  % set -nullify {} s {}
\end{verbatim}
\endgroup

The \textbf{-nullify} option should have the same meaning when applied to any null-smart command: if an argument value is an exact match to the options value, change it to a null.

\subsubsection{List Commands}

Most smart commands can just test the null flag of their arguments and take appropriate action. A few commands, such as \textbf{lindex}, \textbf{lset}, \textbf{join}, and \textbf{split} must understand list null syntax. Consider the string:
\begingroup\small\begin{verbatim}
  % set s {a {b0 {null}! b2} c}
\end{verbatim}
\endgroup

This string represents a list whose second element is a list containing a null. We expect this behavior:
\begingroup\small\begin{verbatim}
  % lindex -null ~ $s 1 1 
  ~
  % lset -nullify {} s 1 2 {}
  a {b0 {null}! {null}!} c
  % lindex -null NUL $s 1 2
  NUL
\end{verbatim}
\endgroup

\textbf{Join} creates a string from a list and must understand \textbf{-null}. Notice that the second command below returns null, by rule 4.
\begingroup\small\begin{verbatim}
  % join -null void {a {null}!}
  a void
  % join {a {null}!}
\end{verbatim}
\endgroup

\textbf{Split} creates a list from a string and must understand \textbf{-nullify}:
\begingroup\small\begin{verbatim}
  % split {a {null}!}
  a {{null}!}
  % split -nullify NULL {a NULL}
  a {null}!
\end{verbatim}
\endgroup

\subsubsection{Expr and Control-flow Commands}

Nulls can be tested using \textbf{string is null}, but testing occurs so often in practice that we need to have \textbf{expr} and the control commands behave properly, allowing three-valued logic -{}- true, false, and null. (In this context, a logic value of null is often called ``unknown''.) \textbf{Expr} should recognise the \textbf{-null} option. These examples illustrate typical three-valued logic tautologies:
\begingroup\small\begin{verbatim}
  % set u {null}!
  % expr -null unk { $u }
  unk
  % expr -null unk { $u && 1 }
  1
  % expr -null unk { $u && 0 }
  unk
  % expr -null unk { $u || 0 }
  0
  % expr -null unk { $u == $u }
  unk
  % expr -null unk { $u != 1 }
  unk
  % expr -null unk { $u eq {} }
  unk
  % expr -null unk { $u > 0 }
  unk
\end{verbatim}
\endgroup

Notice that, logic expressions containing nulls may may have nonnull results. This my seem like a violation of rule 5, but actually is is just a special kind of lazy logic. \textbf{Expr} can simply ignore the null term because it is tautologously irrelevant.

The control commands \textbf{if}, \textbf{while}, and \textbf{for} all throw errors if the expression evaluates to null.

We can also use nulls to represent undefined mathematical results, or \textit{NaN}s (not a number), in the terminology of IEEE 754 floating point arithmetic [2]. This allows Tcl to give the programmer access to hardware features that are currently hidden. To do this we need a \textbf{-nocomplain} option:
\begingroup\small\begin{verbatim}
  % expr -nocomplain -null nan { log(-1) }
  nan
\end{verbatim}
\endgroup

We can use the \textbf{-null} option to assign a usable value if \textit{a} goes to zero:
\begingroup\small\begin{verbatim}
  % set INF 1e16
  % set x [ expr -nocomplain -null $INF { 5 / $a } ]
\end{verbatim}
\endgroup

Nulls can propagate sensibly through a computation and give a useful result when, without them, the same expression would have throw an exception. Again, suppose \textit{a} goes to zero:
\begingroup\small\begin{verbatim}
  % expr -nocomplain -null unk { $x / $a > 0.54 || $c < 0.042 }
  1
\end{verbatim}
\endgroup

\subsubsection{Other Basic Commands}

We need not make all commands null-smart immediately. Old commands can treat nulls as empty strings and function as before. They may be less useful than they could be, but nothing need break, because old code contains nothing that would introduce nulls in the first place. It is up to the programmer who decides to use Tcl's null facility to be aware of which commands respond intelligently to nulls. Perhaps a greater danger is that, once nulls are introduced, evolving commands may break applications that use nulls. Because of this, it would be wise to choose the initial set of null-smart commands with care.

I propose modifying the following commands, if necessary, to respond to nulls appropriately: \textbf{lset}, \textbf{foreach}, \textbf{format}, the list commands, \textbf{return}, \textbf{set}, \textbf{subst}, \textbf{string}, \textbf{switch}. Except as noted below, this means recognizing the \textbf{-null} option.

Now let us discuss the modifications needed for these commands.
\begin{description}
\item[String command suite]
Except for \textbf{string is} commands, all \textbf{string} subcommands should return null if any argument is null, simply because the commands are meaningless when applied to a null string.

Note that a null string is not unequal to any given string. Batman may or may not be Bruce Wayne -{}- his identity is unknown. Similarly, two null strings are neither equal nor unequal to each other. Batman may or may not be the same guy as the Lone Ranger.
\item[String is]
 Except for \textbf{string is null}, all \textbf{string is} subcommands return 0 with a null argument.
\item[Switch]
The switch command should recognize the \textbf{-null} option. Having a switch leg that matches null is easy to imagine:
\begingroup\small\begin{verbatim}
  switch $s {
     a { do this }
     b { do that }
     {null}! { punt } }
\end{verbatim}
\endgroup

but by rule 5 it would never execute -{}- nothing matches a null. Instead, use \textbf{-null}:
\begingroup\small\begin{verbatim}
  switch -null NULL $s {
     a { do this }
     b { do that }
     NULL { punt } }
\end{verbatim}
\endgroup

If you must match any other nonnull string separately from nulls, use \textbf{-glob} and catch the null with \textit{default}:
\begingroup\small\begin{verbatim}
  switch -glob -null NULL -- $s {
     a { do this }
     b { do that }
     * { any other nonnull }
     default { punt } }
\end{verbatim}
\endgroup
\item[Foreach]
 The \textbf{Foreach} command recognizes both \textbf{-null} and \textbf{-nullify}.
\item[Format]
The \textbf{format} command should understand the \textbf{-null} option.
\item[The list commands]
In general, all the list commands treat nulls as distinct elements. Nulls never disappear from a list. \textbf{llength} includes them in the count. Commands that convert lists to or from strings (\textbf{lappend}, \textbf{lindex}, \textbf{linsert}, \textbf{list}, \textbf{lset}, \textbf{split}, \textbf{join}) should understand the \textbf{-null} option. Those that stay in the list domain (\textbf{concat}, \textbf{lrange}) should not.
\item[lsort]
If a list contains a null it cannot be sorted -{}- \textbf{lsort} returns a null string. With the \textbf{-null} option, it can be sorted after substituting the \textbf{-null} option value.
\end{description}

\section{Issues and Extensions}

In this section we discuss design issues that are either debatable or not entirely resolved.
\begin{itemize}
\item{}
Null attributes. It is common practice in statistics to have several distinct kinds of null. In the SAS language, a null datum can be represented by a period, '.', or a period followed by a letter, '.a'. Different codes represent different reasons for the null, e.g., .a = ``no response'', .b = ``doubly-entry error'', .c = ``out of range''.

Another use of a null attribute would be to have a value carry its string representation.

I think both these ideas are of dubious value and violate rule 1, but if, in the future, we want to add this functionality, it could be added with the syntax \{null\}\{\}, where the second set of braces contain the attribute information.
\item{}
Choice of symbol.

\{null\}! or NULL, void, nan, unk, unknown, \{\}!, 
\item{}
SQL inconsistencies. The various implementations of SQL are inconsistent in their treatment of nulls. This is well documented on both the SQLite [1] and MySQL [3] web sites. I prefer a conservative, consistent mathematical interpretation. The \textbf{-null} and \textbf{-nullify} options go a long way toward simulating the inconsistencies of other systems, if necessary.
\end{itemize}

\section{Discussion}

\section{References}
\begin{description}
\item[[[1]]]
SQLite
\item[[[2]]]
IEEE Floating point
\item[[[3]]]
MySQL
\end{description}

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\begin{thebibliography}{TIP \#1}
\addcontentsline{toc}{section}{References}
\bibitem[TIP \#157]{tip157}
Kevin B. Kenny,
Peter Spjuth,
Donal K. Fellows,
Don Porter,
\emph{Argument Expansion with Leading \{expand\}},
on-line at \url{http://purl.org/tcl/tip/157.html}
\end{thebibliography}
\end{document}
