\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#341: Multiple 'dict filter' Patterns}
\date{November 27, 2008}
\author{Lars Hellström}
\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 \#341}&\textbf{Multiple 'dict filter' Patterns}\\\hline
Author&

Lars Hellström \tipmail{Lars.Hellstrom}{residenset.net}
\\
Created&Thursday, \(\text{27}^{\text{th}}\) November 2008\\
Type&Project\\
Tcl Version&\(8.6\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.5 $\\
Keywords&Tcl, set intersection\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

The \textbf{key} and \textbf{value} forms of \textbf{dict filter} are generalised to allow an arbitrary number of patterns.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Specification}

The two \textbf{dict filter} command forms

\begin{quote}
\textbf{dict filter} \textit{dictionary} \textbf{key} \textit{pattern}
\end{quote}

\begin{quote}
\textbf{dict filter} \textit{dictionary} \textbf{value} \textit{pattern}
\end{quote}

are generalised to

\begin{quote}
\textbf{dict filter} \textit{dictionary} \textbf{key} ?\textit{pattern} ...?
\end{quote}

\begin{quote}
\textbf{dict filter} \textit{dictionary} \textbf{value} ?\textit{pattern} ...?
\end{quote}

and the results are the sub-dictionaries of those keys and values respectively which match at least one of the patterns.

\section{Rationale}

Although there are \textbf{dict} subcommands which allow deleting some keys from a dictionary (\textbf{dict remove}) and inserting some keys into a dictionary (\textbf{dict replace}), there is no direct way of requesting the sub-dictionary which only has keys from a given list; if we think of only the set of keys in the dictionary, then we have subcommands for set minus and set union, but none for set intersection. A situation where this would be useful is that the option dictionary for a high-level procedure can contain options meant to be passed on to lower level commands, and it is necessary to extract the subdictionary of options that the lower level command would accept (since passing one which is not supported would cause it to throw an error).

There is of course already the \textbf{dict filter} command, which indeed returns a subdictionary of an existing dictionary, but its \textbf{key} form only accepts one \textbf{string match} pattern and therefore cannot be used to e.g. select all three of -foo, -bar, and -baz (it could select both -bar and -baz through the pattern -ba[rz], but that's neither common nor particularly readable). However, in many instances where this kind of pattern is used (notably \textbf{glob}, \textbf{namespace export}, and \textbf{switch}), it is possible to give several such patterns and have it interpreted as the union of the patterns. Were that the case with \textbf{dict filter}, the ``-foo, -bar, and -baz'' problem could be solved as easily as
\begingroup\small\begin{verbatim}
  dict filter $opts key -foo -bar -baz
\end{verbatim}
\endgroup

which is comparable to
\begingroup\small\begin{verbatim}
  dict remove $opts -foo -bar -baz
  dict replace $opts -foo 1 -bar off -baz 42
\end{verbatim}
\endgroup

and much nicer than the \textbf{script} counterpart
\begingroup\small\begin{verbatim}
  dict filter $opts script {key val} {
     ::tcl::mathop::in $key {-foo -bar -baz}
  }
\end{verbatim}
\endgroup

If the \textbf{key} form is generalised like this, then it seems appropriate to also generalise the \textbf{value} form in the same way to keep the symmetry, even though I have no immediate use-case for that feature.

Since it is generally good to Do Nothing Gracefully, the command syntax is also generalised to allow the case of no patterns at all.

\section{Rejected Alternatives}

A more direct way of meeting the motivating need would be a command \textbf{dict select} with the same syntax as \textbf{dict remove} (no pattern matching) but logic reversed. This would however be so close to \textbf{dict filter} ... \textbf{key} that extending the syntax of the latter seemed more appropriate.

An alternative to allowing multiple patterns with \textbf{dict filter} could be to allow a regular expression pattern, since the union of two regular languages is again a regular language. Any syntax that could be picked for that would however on one hand already be rather close to
\begingroup\small\begin{verbatim}
  dict filter $opts script {key val} {regexp $RE $key}
\end{verbatim}
\endgroup

and on the other it would be rather difficult to read, as the regular expression corresponding to ``-foo or -bar or -baz'' is
\begingroup\small\begin{verbatim}
  ^(-foo|-bar|-baz)$
\end{verbatim}
\endgroup

which it is tempting but incorrect to simplify to ``-foo\tipbar{}-bar\tipbar{}-baz''.

\section{Implementation Notes}

An implementation exists (it's a very trivial to modify \textbf{dict filter} ... \textbf{value} to work this way: just add an inner loop over the list of patterns); see SF path \#2370575. [\url{https://sourceforge.net/support/tracker.php?aid=2370575}]

What might be tricky is the case of \textbf{dict filter} ... \textbf{key}, since this currently has an optimisation for the case of a pattern without glob metacharacters that would be very desirable to keep for the motivating use-case of selecting specific keys from a dictionary. The natural way to do that would be to make the loop over patterns the outer loop and the loop over dictionary entries the inner loop, which is only entered if the current pattern contains metacharacters. Such an optimisation would however have the script-level-visible consequence of having the keys show up in the order of the patterns rather than the order of the original dictionary, so it may be a good idea to also explicitly specify that \textbf{dict filter} does not guarantee keys in the result to be in the same order as in the input dictionary.

Indeed, a \textbf{dict filter} ... \textbf{key} that reorders keys according to its pattern arguments could sometimes be useful in interactive situations, as a way of getting selected keys up from in a dictionary:
\begingroup\small\begin{verbatim}
  set D {-baz 0 -bar 1 -foo 2}
  dict filter $D key -foo -bar *
\end{verbatim}
\endgroup

On the other hand, this effect can mostly be obtained through use of \textbf{dict merge} already:
\begingroup\small\begin{verbatim}
  dict merge {-foo x -bar x} $D
\end{verbatim}
\endgroup

\section{Copyright}

This document has been placed in the public domain. 

\section{Colophon}

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