\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#111: Dictionary Values and Manipulators}
\date{October 05, 2002}
\author{Donal K. Fellows, David S. Cargo}
\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 \#111}&\textbf{Dictionary Values and Manipulators}\\\hline
Author&

Donal K. Fellows \tipmail{donal.k.fellows}{man.ac.uk}
\par
David S. Cargo \tipmail{dcargo}{marix.com}
\\
Created&Saturday, \(\text{5}^{\text{th}}\) October 2002\\
Type&Project\\
Tcl Version&\(8.5\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.12 $\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes adding a standard value format (and supporting commands) to Tcl that implements a value-to-value mapping, just as Tcl's list values can be regarded as implementing a number-to-value mapping.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

What is a dictionary? It is a translation from arbitrary values to arbitrary values, often also known as an associative map. Many computer languages, especially higher-level ones, have them as part of the language or the standard library. It would be nice to have them in Tcl too.

Now, I realise that Tcl already contains arrays which provide dictionary functionality, but they are not quite the same thing. Tcl's arrays are collections of variables indexable by name, and not collections of values. This has some far-reaching implications; it is possible to set traces on individual elements of the array, but it is not possible to pass the array by value. However, one of the main concerns is the sheer cost of arrays in terms of memory space; aside from the hash table used as the core of the implementation (and the representations of the keys and values, of course) there is a substantial overhead for each array to support traces on the array as a whole, plus a similar overhead \textit{per element} that stems from the fact that elements are variables in their own right. By contrast, a dictionary value should be a lot more frugal.

\section{Value Syntax and Semantics}

Naturally, it is desirable for dictionary values to have human-readable forms that are similar to those that currently exist. I propose using \textit{key value key value ...} form with list-style quoting for keys and values that contain characters that are significant to Tcl, which should be immediately familiar to users of the \textbf{array get} and \textbf{array set} commands. No special interpretation will be placed on the amount of whitespace separating keys and values, just as with lists (indeed, any list with an even number of elements can be regarded as a dictionary.) For example, the following value represents a mapping from selected languages to a possible program to invoke to compile them:
\begingroup\small\begin{verbatim}
	C gcc C++ g++ FORTRAN f77 Java javac
\end{verbatim}
\endgroup

Empty dictionaries are those that contain no mappings from keys to values. Any representation of an empty list will also be a representation of an empty dictionary. There is no upper bound on the number of items that a dictionary may hold.

It should be specially noted that dictionary values have copy-on-write semantics just like lists. This means that if I hand a dictionary value into a procedure as an argument, and that procedure updates the variable containing that value, the value as seen by the caller will not have changed. This is in complete contrast with arrays which cannot (currently) be passed by value other than through using \textbf{array get} to convert the array to a list form and \textbf{array set} to convert back again.

This specification does not state what order the keys and values are listed in. That depends on the implementation.

\section{Command Syntax and Semantics}

I propose that all operations that work with dictionary values (where not done through adaptations of existing commands) will go through the \textbf{dict} command. The alternatives are ``array'' which is already in use, ``dictionary'' which is rather long for what I believe will be a fairly commonly used command, ``alist'' (association list) which is probably too easy to confuse with existing commands, and ``map'' which is probably better reserved for future use as something for applying an operation to a list (or other collection of values), ``hash'' (which is perhaps too common), and ``table'' (which is used for this type of data structure in the Icon programming language).

Most subcommands operate on either a dictionary value (\textit{exists}, \textit{for}, \textit{get}, \textit{info}, \textit{keys}, \textit{remove}, \textit{replace}, \textit{size}, and \textit{values}), or on a variable containing a dictionary value (\textit{append}, \textit{incr}, \textit{lappend}, \textit{set}, and \textit{unset}).

Proposed subcommands:
\begin{description}
\item[dict create]
Make a dictionary.

\textbf{dict create} ?\textit{key1 value1 key2 value2 ...}?

This will create a new dictionary from the given keys and values and return it as the result. The command will take an even number of arbitrary strings (or other objects, naturally) and will use the first, third, fifth, etc. as keys and the second, fourth, sixth, etc. as values. From the point of view of string representations, this command will behave the same as the \textbf{list} command with an even number of arguments. There is no restriction on the possible representations of keys or values. It is legal to call this command with no arguments at all, which creates an empty dictionary.
\item[dict get]
Get value for given key.

\textbf{dict get} \textit{dictionaryValue} ?\textit{key ...}?

Given a dictionary value (first argument) and a key (second argument), this will retrieve the value for that key. Where several keys are supplied, the behaviour of the command shall be as if the result of \textbf{dict get} \textit{dictVal key} was passed as the first argument to \textit{'dict get} with the remaining arguments as second (and possibly subsequent) arguments. This facilitates lookups in nested dictionaries. For example, the following two commands are equivalent:
\begingroup\small\begin{verbatim}
	dict get $dict foo bar spong
	dict get [dict get [dict get $dict foo] bar] spong
\end{verbatim}
\endgroup

If no keys are provided, dict would return a list containing pairs of elements in a manner similar to \textbf{array get}. That is, the first element of each pair would be the key and the second element would be the value for that key.

It is an error to attempt to retrieve a value for a key that is not present in the dictionary.
\item[dict replace]
Create a new dictionary that is a copy of an old one except with some values different or some extra key/value pairs added.

\textbf{dict replace} \textit{dictionaryValue} ?\textit{key value ...}?

This is very much the analogue of \textbf{lreplace}, taking a dictionary value as its first argument and then a list of key/value pairs. The result of the command is a new dictionary value that is a copy of the supplied dictionary other than that whenever a key is one of those supplied to this command, the returned dictionary will map that key to the associated value. It is legal for this command to be called with no key/value pairs, but illegal for this command to be called with a key but no value.
\item[dict remove]
Create a new dictionary that is a copy of an old one except without the key/value mappings whose keys are listed.

\textbf{dict remove} \textit{dictionaryValue} ?\textit{key key ...}?

This operation does what \textbf{dict replace} can't do; removes keys and values. The result of the command is a new dictionary value that does not contain mappings for any of the keys listed; it is not an error if either there are no keys listed, or if any of the listed keys does not exist in the supplied dictionary.
\item[dict set]
Set value for given key in a dictionary in a variable.

\textbf{dict set} \textit{dictionaryVar key} ?\textit{key ...}? \textit{value}

This operation takes the name of a variable containing a dictionary value and places an updated dictionary value in that variable containing a mapping from the given key to the given value. In a manner analogous to \textbf{lset}, where multiple keys are present, they do indexing into nested dictionaries.
\item[dict unset]
Remove association for given key in a dictionary in a variable.

\textbf{dict unset} \textit{dictionaryVar key} ?\textit{key ...}?

This operation takes the name of a variable containing a dictionary value and places an updated dictionary value in that variable that does not contain a mapping for the given key. Where multiple keys are present, this describes a path through nested dictionaries to the mapping to remove. At least one key must be specified.
\item[dict keys]
List all keys (with optional criteria matching) in dictionary.

\textbf{dict keys} \textit{dictionaryValue} ?\textit{globPattern}?

Return a list of all keys in the given dictionary value. If a pattern is supplied, only those keys that match it (according to the rules of \textbf{string match}) will be returned. The returned keys will be in an arbitrary implementation-specific order.
\item[dict values]
List all values (with optional criteria matching) in the dictionary.

\textbf{dict values} \textit{dictionaryValue} ?\textit{globPattern}?

Return a list of all values in the given dictionary value. If a pattern is supplied, only those values that match it (according to the rules of \textbf{string match}) will be returned. The returned keys will be in an arbitrary implementation-specific order, though where no pattern is supplied the \textit{i}th key returned by \textbf{dict keys} will be the key for the \textit{i}th value returned by \textbf{dict values} applied to the same dictionary value.
\item[dict for]
Iterate across all key/value mappings in the dictionary.

\textbf{dict for} \{\textit{keyVar valueVar}\} \textit{dictionaryValue body}

This takes three arguments, the first a pair of variable names (for the key and value respectively of each mapping in the dictionary), the second the dictionary value to iterate across, and the third a script to be evaluated for each mapping with the key and value variables set appropriately (in the manner of \textbf{foreach}.) The result of the command is an empty string. If any evaluation of the body generates a \textit{TCL\_BREAK} result, no further pairs from the dictionary will be iterated over and the \textbf{dict for} command will terminate successfully immediately. If any evaluation of the body generates a \textit{TCL\_CONTINUE} result, this shall be treated exactly like a normal \textit{TCL\_OK} result.
\item[dict filter]
Create a new dictionary from an old one containing just a selection of key/value pairs.

\textbf{dict filter} \textit{dictionaryValue} \textbf{key} \textit{globPattern}

\textbf{dict filter} \textit{dictionaryValue} \textbf{value} \textit{globPattern}

\textbf{dict filter} \textit{dictionaryValue} \textbf{script} \{\textit{keyVar valueVar}\} \textit{script}

This takes a dictionary value and returns a new dictionary that contains just those key/value pairs that match the specified rule. Three rules are outlined above. The \textbf{key} rule only matches those key/value pairs whose keys match the given glob-style pattern. The \textbf{value} rule only matches those key/value pairs whose values match the given glob-style pattern. The \textbf{script} rule tests for matching by assigning the key to the \textit{keyVar} and the value to the \textit{valueVar}, and then evaluating the given script which should return a boolean value (with the key/value pair only being included in the result of the \textbf{dict filter} when a true value is returned.)
\item[dict append]
Append a string to the value for a particular key in the dictionary.

\textbf{dict append} \textit{dictionaryVar key} ?\textit{string ...}?

This appends the given string (or strings) to the value that the given key maps to in the dictionary value contained in the given variable, writing the resulting dictionary value back to that variable. Non-existent keys are treated as if they map to an empty string.
\item[dict incr]
Increment the value for a particular key in the dictionary.

\textbf{dict incr} \textit{dictionaryVar key} ?\textit{increment}?

This adds the given increment value (an integer that defaults to 1 if not specified) to the value that the given key maps to in the dictionary value contained in the given variable, writing the resulting dictionary value back to that variable. Non-existent keys are treated as if they map to 0. It is an error to increment a value for an existing key if that value is not an integer.
\item[dict lappend]
Append an item to the list-value for a particular key in the dictionary.

\textbf{dict lappend} \textit{dictionaryVar key} ?\textit{item ...}?

This appends the given items to the list value that the given key maps to in the dictionary value contained in the given variable, writing the resulting dictionary value back to that variable. Non-existent keys are treated as if they map to an empty list, and it is legal for there to be no items to append to the list. It is an error for the value that the key maps to to not be representable as a list.
\item[dict exists]
Test whether a mapping exists for a key.

\textbf{dict exists} \textit{dictionaryValue key} ?\textit{key ...}?

This returns a boolean value indicating whether the given key (or path of keys through a set of nested dictionaries) exists in the given dictionary value. This returns a true value exactly when \textbf{dict get} on that path will succeed.
\item[dict size]
Get the number of key/value mappings in a dictionary.

\textbf{dict size} \textit{dictionaryValue}

This returns the size of the dictionary, which will be exactly half the value that \textbf{llength} \textit{dictionaryValue} would return. It is an error to apply this command to a non-dictionary value.
\item[dict info]
Get implementation-specific information about the dictionary value.

\textbf{dict info} \textit{dictionaryValue}

This returns information (intended for display to people) about the given dictionary though the format of this data is dependent on the implementation of the dictionary. For dictionaries that are implemented by hash tables, it is expected that this will return the string produced by \textit{Tcl\_HashStats()}.
\end{description}

\section{Other Related Changes}

There are a few other commands that change:
\begin{itemize}
\item{}
\textbf{array set} will take a dictionary instead of (or as well as) a list as its final argument.
\item{}
\textbf{array get} will return a dictionary.
\item{}
\textbf{string map} will take a dictionary instead of (or as well as) a list as its map argument.
\end{itemize}

Naturally, dictionary handling will form its own maintenance area. \cite{tip16} and \cite{tip24} will be updated as necessary.

\section{C API}

There will be a new public structure and a few new public functions to allow C-level access to dictionary values:

The new structure (called \textit{Tcl\_DictSearch}) will be there to allow for searches (i.e. traversals) of a dictionary. This TIP does not specify the fields of the structure; the declaration is just to allow for allocation of these structures on the C stack.

Many public API functions are capable of generating error messages; these generally indicate some type-conversion failure. Sharing constraint violations (where applicable) cause panics as they indicate basic programming errors which should not be causable by scripts. The public API functions are:

\begin{quote}
Tcl\_Obj *\textbf{Tcl\_NewDictObj}(void);
\end{quote}

\begin{quote}
Tcl\_Obj *\textbf{Tcl\_DbNewDictObj}(CONST char *\textit{file}, int \textit{line});
\end{quote}

These functions (in non-debug and debug versions) create a new dictionary object and return it.

\begin{quote}
int \textbf{Tcl\_DictObjPut}(Tcl\_Interp *\textit{interp}, Tcl\_Obj *\textit{dictPtr}, Tcl\_Obj *\textit{keyPtr}, Tcl\_Obj *\textit{valuePtr});
\end{quote}

This function inserts a new key/value pair into a dictionary, or updates a key/value pair already in the dictionary. The dictionary object must be unshared. Note that both the key and value objects will have their reference count increased. The return value is a normal TCL\_OK/TCL\_ERROR result, with the \textit{interp} for error reporting.

\begin{quote}
int \textbf{Tcl\_DictObjGet}(Tcl\_Interp *\textit{interp}, Tcl\_Obj *\textit{dictPtr}, Tcl\_Obj *\textit{keyPtr}, Tcl\_Obj **\textit{valuePtrPtr});
\end{quote}

This function looks up the value for a key in a dictionary. The variable pointed to by the \textit{valuePtrPtr} argument is updated to contain a reference to the value, or a NULL if there is no mapping for the key in the dictionary. No reference counts are manipulated by this function. The return value is a normal TCL\_OK/TCL\_ERROR result, with the \textit{interp} for error reporting.

\begin{quote}
int \textbf{Tcl\_DictObjRemove}(Tcl\_Interp *\textit{interp}, Tcl\_Obj *\textit{dictPtr}, Tcl\_Obj *\textit{keyPtr});
\end{quote}

This function removes the key/value pair with the given key from the dictionary. It is not an error if the key is not present in the dictionary. The dictionary must be unshared. The return value is a normal TCL\_OK/TCL\_ERROR result, with the \textit{interp} for error reporting.

\begin{quote}
int \textbf{Tcl\_DictObjSize}(Tcl\_Interp *\textit{interp}, Tcl\_Obj *\textit{dictPtr}, int *\textit{sizePtr});
\end{quote}

This function updates the integer variable pointed to by \textit{sizePtr} with the number of key/value pairs in the dictionary. The return value is a normal TCL\_OK/TCL\_ERROR result, with the \textit{interp} for error reporting.

\begin{quote}
int \textbf{Tcl\_DictObjFirst}(Tcl\_Interp *\textit{interp}, Tcl\_Obj *\textit{dictPtr}, Tcl\_DictSearch *\textit{searchPtr}, Tcl\_Obj **\textit{keyPtrPtr}, Tcl\_Obj **\textit{valuePtrPtr}, int *\textit{donePtr});
\end{quote}

This function starts a search of (i.e. iteration over) the given dictionary, using the structure pointed to by \textit{searchPtr} as context. The return value is a normal TCL\_OK/TCL\_ERROR result, with the \textit{interp} for error reporting. Three variables are updated to indicate what was found; \textit{keyPtrPtr} is used for reporting the key of a key/value pair and \textit{valuePtrPtr} is used for reporting the corresponding value. Finally, \textit{donePtr} is used for indicating whether the search has found all the values; if the variable it points to is set to 1 there are no key/value pairs in the dictionary (i.e. the variables pointed to by \textit{keyPtrPtr} and \textit{valuePtrPtr} were not updated), but if the variable is set to 0, a key/value pair was found and \textit{Tcl\_DictObjNext()} should be called to discover whether that was the last value or if there are further ones in the dictionary. Note that if this function indicates that the search is not done but the calling code wishes to extract no further values from the dictionary, \textit{Tcl\_DictObjDone()} \textit{must} be called to release the internal locks on the representation of the value.

\begin{quote}
void \textbf{Tcl\_DictObjNext}(Tcl\_DictSearch *\textit{searchPtr}, Tcl\_Obj **\textit{keyPtrPtr}, Tcl\_Obj **\textit{valuePtrPtr}, int *\textit{donePtr});
\end{quote}

This function gets the next key/value pair from the search of a dictionary, using the search referenced by \textit{searchPtr}. The meaning of the \textit{keyPtrPtr}, \textit{valuePtrPtr} and \textit{donePtr} variables is much the same as in \textit{Tcl\_DictObjFirst()}, along with the restriction that if the function indicates that the search is not done but the calling code wishes to extract no further values from the dictionary, \textit{Tcl\_DictObjDone()} \textit{must} be called to release the internal locks on the representation of the value.

\begin{quote}
void \textbf{Tcl\_DictObjDone}(Tcl\_DictSearch *\textit{searchPtr});
\end{quote}

This function terminates a search of a dictionary before all the values in the dictionary have been iterated over, releasing the internal locks on the dictionary representation.

\begin{quote}
int \textbf{Tcl\_DictObjPutKeyList}(Tcl\_Interp *\textit{interp}, Tcl\_Obj *\textit{dictPtr}, int \textit{keyc}, Tcl\_Obj *CONST *\textit{keyv}, Tcl\_Obj *\textit{valuePtr});
\end{quote}

This function is a variant on \textit{Tcl\_DictObjPut()} that takes a list of keys so as to work with nested dictionaries.

\begin{quote}
int \textbf{Tcl\_DictObjRemoveKeyList}(Tcl\_Interp *\textit{interp}, Tcl\_Obj *\textit{dictPtr}, int \textit{keyc}, Tcl\_Obj *CONST *\textit{keyv});
\end{quote}

This function is a variant on \textit{Tcl\_DictObjRemove()} that takes a list of keys so as to work with nested dictionaries.

\section{Examples}

Counting the number of unique words in a file and the number of times each word occurs:
\begingroup\small\begin{verbatim}
set f [open someFile.txt]
set contents [read $f]
close $f
foreach word [regexp -all -inline {\w+} $contents] {
   dict incr count $word
}
puts "There are [dict size $count] unique words."
foreach word [lsort -dictionary [dict keys $count]] {
   puts "${word}: [dict get $count $word] occurrences"
}
\end{verbatim}
\endgroup

A localisable \textbf{string toupper} implementation:
\begingroup\small\begin{verbatim}
set capital [dict create C [dict create]]
foreach c {abcdefghijklmnopqrstuvwxyz} {
   dict set capital C $c [string toupper $c]
}
dict set capital en [dict get $capital C]
# ... and so on for other supported languages ...
set upperCase [string map [dict get $capital $env(LANG)] $string
\end{verbatim}
\endgroup

\section{Copyright}

This document has been placed in the public domain.

\vspace{3ex}\hrule\vspace{1.5ex}

\section{Appendices}

\textit{These appendices are not formally part of the proposal and exist merely to help understanding.}

\subsection{Implementation Notes}

Implement using hash tables (of course.) Need efficient ways to convert to/from lists, perhaps making lists know what's going on underneath the covers?

\subsection{Future Directions}

Alternate implementations of mappings, like trees or disk-backed databases?

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\begin{thebibliography}{TIP \#2}
\addcontentsline{toc}{section}{References}
\bibitem[TIP \#16]{tip16}
Don Porter,
Daniel Steffen,
\emph{Tcl Functional Areas for Maintainer Assignments},
on-line at \url{http://purl.org/tcl/tip/16.html}
\bibitem[TIP \#24]{tip24}
Don Porter,
Donal K. Fellows,
Kevin B. Kenny,
Jeff Hobbs,
Pavel Goran,
Daniel A. Steffen,
miguel sofer,
\emph{Tcl Maintainer Assignments},
on-line at \url{http://purl.org/tcl/tip/24.html}
\end{thebibliography}
\end{document}
