path: root/Master/texmf-dist/source/latex/expl3/l3prg.dtx

% \iffalse
%% File: l3prg.dtx Copyright (C) 2005-2011 LaTeX3 project
%%
%% It may be distributed and/or modified under the conditions of the
%% LaTeX Project Public License (LPPL), either version 1.3c of this
%% license or (at your option) any later version.  The latest version
%% of this license is in the file
%%
%%    http://www.latex-project.org/lppl.txt
%%
%% This file is part of the ``expl3 bundle'' (The Work in LPPL)
%% and all files in that bundle must be distributed together.
%%
%% The released version of this bundle is available from CTAN.
%%
%% -----------------------------------------------------------------------
%%
%% The development version of the bundle can be found at
%%
%%    http://www.latex-project.org/svnroot/experimental/trunk/
%%
%% for those people who are interested.
%%
%%%%%%%%%%%
%% NOTE: %%
%%%%%%%%%%%
%%
%%   Snapshots taken from the repository represent work in progress and may
%%   not work or may contain conflicting material!  We therefore ask
%%   people _not_ to put them into distributions, archives, etc. without
%%   prior consultation with the LaTeX Project Team.
%%
%% -----------------------------------------------------------------------
%
%<*driver|package>
\RequirePackage{l3names}
%</driver|package>
%\fi
\GetIdInfo$Id: l3prg.dtx 2178 2011-03-06 09:03:44Z mittelba $
       {L3 Experimental control structures}
%\iffalse
%<*driver>
%\fi
\ProvidesFile{\filename.\filenameext}
  [\filedate\space v\fileversion\space\filedescription]
%\iffalse
\documentclass[full]{l3doc}
\begin{document}
\DocInput{l3prg.dtx}
\end{document}
%</driver>
% \fi
%
%
% \title{The \textsf{l3prg} package\thanks{This file
%         has version number \fileversion, last
%         revised \filedate.}\\
% Program control structures}
% \author{\Team}
% \date{\filedate}
% \maketitle
%
% \begin{documentation}
%
%  \section{Conditionals and logical operations}
%
%  Conditional processing in \LaTeX3 is defined as something that
%  performs a series of tests, possibly involving assignments and
%  calling other functions that do not read further ahead in the input
%  stream. After processing the input, a \emph{state} is returned. The
%  typical states returned are \meta{true} and \meta{false} but other
%  states are possible, say an \meta{error} state for erroneous
%  input, e.g., text as input in a function comparing integers.
%
%  
%
%  \LaTeX3 has two primary forms of conditional flow processing based
%  on these states. One type is predicate functions that turn the
%  returned state into a boolean \meta{true} or \meta{false}. For
%  example, the function "\cs_if_free_p:N" checks whether the control
%  sequence given as its argument is free and then returns the boolean
%  \meta{true} or \meta{false} values to be used in testing with
%  "\if_predicate:w" or in functions to be described below.  The other type
%  is the kind of functions choosing a particular argument from the
%  input stream based on the result of the testing as in
%  "\cs_if_free:NTF" which also takes one argument (the "N") and then
%  executes either \meta{true} or \meta{false} depending on the
%  result. Important to note here is that the arguments are executed
%  after exiting the underlying "\if...\fi:" structure
%
%
%
%
%
%
%
% \section{Defining a set of conditional functions}
%
% \begin{function}{ \prg_return_true:  |
%                   \prg_return_false: }
% These functions exit conditional processing when used in
% conjunction with the generating functions listed below.
% \end{function}
%
%  \begin{function}{%
%                   \prg_set_conditional:Nnn  |
%                   \prg_set_conditional:Npnn |
%                   \prg_new_conditional:Nnn  |
%                   \prg_new_conditional:Npnn |
%                   \prg_set_protected_conditional:Nnn  |
%                   \prg_set_protected_conditional:Npnn |
%                   \prg_new_protected_conditional:Nnn  |
%                   \prg_new_protected_conditional:Npnn |
%                   \prg_set_eq_conditional:NNn |
%                   \prg_new_eq_conditional:NNn
%  }
%  \begin{syntax}
%     "\prg_set_conditional:Nnn"  <test> <conds> <code>
%     "\prg_set_conditional:Npnn" <test> <param> <conds> <code>
%  \end{syntax}
%  This defines a conditional \meta{base function} which upon
%  evaluation using |\prg_return_true:| and |\prg_return_false:| to
%  finish branches,
%  returns a state. Currently the states are either \meta{true} or
%  \meta{false} although this can change as more states may be
%  introduced, say an \meta{error} state. \meta{conds} is a comma
%  separated list possibly consisting of |p| for denoting a predicate function
%  returning the boolean \meta{true} or \meta{false} values and |TF|,
%  |T| and |F| for the functions that act on the tokens following in
%  the input stream.  The |:Nnn| form implicitly determines the number
%  of arguments from the function being defined whereas the |:Npnn|
%  form expects a primitive parameter text.
%
%  An example can easily clarify matters here:
% \begin{verbatim}
% \prg_set_conditional:Nnn \foo_if_bar:NN {p,TF,T} {
%   \if_meaning:w \l_tmpa_tl #1
%     \prg_return_true:
%   \else:
%     \if_meaning:w \l_tmpa_tl #2
%       \prg_return_true:
%     \else:
%       \prg_return_false:
%     \fi:
%   \fi:
% }
% \end{verbatim}
%  This defines the function |\foo_if_bar_p:NN|, |\foo_if_bar:NNTF|,
%  |\foo_if_bar:NNT| but not |\foo_if_bar:NNF| (because "F" is missing from
%  the \meta{conds} list). The return statements
%  take care of resolving the remaining |\else:| and |\fi:| before
%  returning the state. There must be a return statement for each
%  branch, failing to do so will result in an error if that branch is
%  executed.
%  \end{function}
%
%
%
%
%
%  \section{The boolean data type}
%
%  This section describes a boolean data type which is closely
%  connected to conditional processing as sometimes you want to
%  execute some code depending on the value of a switch
%  (e.g.,~draft/final) and other times you perhaps want to use it as a
%  predicate function in an "\if_predicate:w" test. The problem of the
%  primitive "\if_false:" and "\if_true:" tokens is that it is not
%  always safe to pass them around as they may interfere with scanning
%  for termination of primitive conditional processing. Therefore, we
%  employ two canonical booleans: "\c_true_bool" or
%  "\c_false_bool". Besides preventing problems as described above, it
%  also allows us to implement a simple boolean parser supporting the
%  logical operations And, Or, Not, etc.\ which can then be used on
%  both the boolean type and predicate functions.
%
%  All conditonal "\bool_" functions are expandable and expect the
%  input to also be fully expandable (which will generally mean being
%  constructed from predicate functions, possibly nested).
%
%  \begin{function}{%
%                   \bool_new:N |
%                   \bool_new:c |
%  }
%  \begin{syntax}
%     "\bool_new:N" <bool> 
%  \end{syntax}
%  Define a new boolean variable. The initial value is <false>. A
%  boolean is actually just either "\c_true_bool" or "\c_false_bool".
%  \end{function}
%
%  \begin{function}{%
%                   \bool_set_true:N |
%                   \bool_set_true:c |
%                   \bool_set_false:N |
%                   \bool_set_false:c |
%                   \bool_gset_true:N |
%                   \bool_gset_true:c |
%                   \bool_gset_false:N |
%                   \bool_gset_false:c |
%  }
%  \begin{syntax}
%     "\bool_gset_false:N" <bool>
%  \end{syntax}
%  Set <bool> either <true> or <false>. We can also do this globally.
%  \end{function}
%
%
%  \begin{function}{%
%                   \bool_set_eq:NN |
%                   \bool_set_eq:Nc |
%                   \bool_set_eq:cN |
%                   \bool_set_eq:cc |
%                   \bool_gset_eq:NN |
%                   \bool_gset_eq:Nc |
%                   \bool_gset_eq:cN |
%                   \bool_gset_eq:cc |
%
%  }
%  \begin{syntax}
%     "\bool_set_eq:NN" <bool1> <bool2>
%  \end{syntax}
%  Set <bool1> equal to the value of <bool2>.
%  \end{function}
%
%  \begin{function}{ \bool_if:N / (pTF) |
%                    \bool_if:c / (pTF) }
%  \begin{syntax}
%     "\bool_if:NTF" <bool> \Arg{true} \Arg{false}   \\
%     "\bool_if_p:N" <bool>
%  \end{syntax}
%  Test the truth value of <bool> and execute the \m{true} or
%  \m{false} code. "\bool_if_p:N" is a predicate function for use in
%  "\if_predicate:w" tests or "\bool_if:nTF"-type functions described below.
%  \end{function}
%
%  \begin{function}{%
%                   \bool_while_do:Nn |
%                   \bool_while_do:cn |
%                   \bool_until_do:Nn |
%                   \bool_until_do:cn |
%                   \bool_do_while:Nn |
%                   \bool_do_while:cn |
%                   \bool_do_until:Nn |
%                   \bool_do_until:cn |
%
%  }
%  \begin{syntax}
%     "\bool_while_do:Nn" <bool> \Arg{code}  \\
%     "\bool_until_do:Nn" <bool> \Arg{code}  \\
%  \end{syntax}
%  The `while' versions execute <code> as long as the boolean is
%  true and the `until' versions execute <code> as long as the
%  boolean is false. The "while_do" functions execute the body after
%  testing the boolean and the "do_while" functions executes the body
%  first and then tests the boolean.
%  \end{function}
%
%
%
% \section{Boolean expressions}
%
% As we have a boolean datatype and predicate functions returning
% boolean \meta{true} or \meta{false} values, it seems only fitting
% that we also provide a parser for \meta{boolean expressions}.
%
% A boolean expression is an expression which given input in the form
% of predicate functions and boolean variables, return boolean
% \meta{true} or \meta{false}. It supports the logical operations And,
% Or and Not as the well-known infix operators "&&", "||" and "!". In
% addition to this, parentheses can be used to isolate
% sub-expressions. For example,
% \begin{verbatim}
%     \int_compare_p:n {1=1} &&
%     (
%       \int_compare_p:n {2=3} ||
%       \int_compare_p:n {4=4} ||
%       \int_compare_p:n {1=\error} % is skipped
%     ) &&
%     !(\int_compare_p:n {2=4}) 
% \end{verbatim}
% is a valid boolean expression. Note that minimal evaluation is
% carried out whenever possible so that whenever a truth value cannot
% be changed anymore, the remainding tests within the current group
% are skipped.
%
%  \begin{function}{ \bool_if:n / (pTF) }
%  \begin{syntax}
%    "\bool_if:nTF" \Arg{boolean expression} \Arg{true}
%    \Arg{false}
%  \end{syntax}
%  The functions evaluate the truth value of \m{boolean expression}
%  where each predicate is separated by \verb+&&+ or \verb+||+
%  denoting logical `And' and `Or' functions. "(" and ")" denote
%  grouping of sub-expressions while "!" is used to as a prefix to
%  either negate a single expression or a group. Hence
% \begin{verbatim}
%   \bool_if_p:n{
%     \int_compare_p:n {1=1} &&
%     (
%       \int_compare_p:n {2=3} ||
%       \int_compare_p:n {4=4} ||
%       \int_compare_p:n {1=\error} % is skipped
%     ) &&
%     !(\int_compare_p:n {2=4}) 
%   }
% \end{verbatim}
%  from above returns \meta{true}.
%
%  Logical operators take higher precedence the later in the predicate they
%  appear. ``<x> "||" <y> "&&" <z>'' is interpreted as the equivalent of
%  ``<x> \textsc{or} [~<y> \textsc{and} <z>~]'' (but now we have grouping
%  you shouldn't write this sort of thing, anyway).
%  \end{function}
%
%
%
%  \begin{function}{ \bool_not_p:n / (EXP) }
%  \begin{syntax}
%     "\bool_not_p:n" \Arg{boolean expression}
%  \end{syntax}
%  Longhand for writing "!("\meta{boolean expression}")" within a boolean
%  expression. Might not stick around.
%  \end{function}
%
%  \begin{function}{ \bool_xor_p:nn / (EXP) }
%  \begin{syntax}
%     "\bool_xor_p:nn" \Arg{boolean expression} \Arg{boolean expression}
%  \end{syntax}
%  Implements an `exclusive or' operation between two boolean
%  expressions. There is no infix operation for this.
%  \end{function}
%
% \begin{function}{\bool_set:Nn |\bool_set:cn |\bool_gset:Nn |\bool_gset:cn}
% \begin{syntax}
% "\bool_set:Nn" <bool> \Arg{boolean expression}
% \end{syntax}
% Sets <bool> to the logical outcome of evaluating <boolean expression>.
% \end{function}
%
%
%  \section{Case switches}
%
%
%  \begin{function}{ \prg_case_int:nnn / (EXP) }
%  \begin{syntax}
%    "\prg_case_int:nnn" \Arg{integer expr} "{" 
%    ~~\Arg{integer expr 1} \Arg{code 1}\\
%    ~~\Arg{integer expr 2} \Arg{code 2}\\
%    ~~\dots\\
%    ~~\Arg{integer expr\,$\sb n$} \Arg{code\,$\sb n$}\\
%    "}" \Arg{else case} 
%  \end{syntax}
%  This function evaluates the first \meta{integer expr} and then compares it
%  to the values found in the list. Thus the expression
% \begin{verbatim}
% \prg_case_int:nnn{2*5}{
%   {5}{Small}  {4+6}{Medium}  {-2*10}{Negative}
% }{Other}
% \end{verbatim}
%  evaluates first the term to look for and then tries to find this
%  value in the list of values. If the value is found, the code on its
%  right is executed after removing the remainder of the list. If the
%  value is not found, the \meta{else case} is executed. The example
%  above will return ``Medium''.
%
% The function is expandable and is written in such a way that
% \texttt{f} style expansion can take place cleanly, i.e., no tokens
% from within the function are left over.
%  \end{function}
%
%  \begin{function}{ \prg_case_dim:nnn / (EXP) }
%  \begin{syntax}
%    "\prg_case_int:nnn" \Arg{dim expr} "{"\\
%    ~~\Arg{dim expr 1} \Arg{code 1}\\
%    ~~\Arg{dim expr 2} \Arg{code 2}\\
%    ~~"..."\\
%    ~~\Arg{dim expr\,$\sb n$} \Arg{code\,$\sb n$}\\
%    "}" \Arg{else case} 
%  \end{syntax}
%  This function works just like |\prg_case_int:nnn| except it works
%  for \meta{dim} registers.
%  \end{function}
%
%  \begin{function}{ \prg_case_str:nnn / (EXP) }
%  \begin{syntax}
%    "\prg_case_str:nnn" \Arg{string} "{" \\
%    ~~\Arg{string 1} \Arg{code 1}\\
%    ~~\Arg{string 2} \Arg{code 2}\\
%    ~~"..."\\
%    ~~\Arg{string\,$\sb n$} \Arg{code,$\sb n$}\\
%    "}" \Arg{else case} 
%  \end{syntax}
%  This function works just like |\prg_case_int:nnn| except it
%  compares strings. Each string is evaluated fully using \texttt{x}
%  style expansion.
%
% The function is expandable\footnote{Provided you use pdfTeX v1.30 or
% later} and is written in such a way that
% \texttt{f} style expansion can take place cleanly, i.e., no tokens
% from within the function are left over.
%  \end{function}
%
%  \begin{function}{ \prg_case_tl:Nnn / (EXP) }
%  \begin{syntax}
%    "\prg_case_tl:Nnn" <tl var.> "{" 
%    ~~<tl var.\ 1> \Arg{code 1}  <tl var.\ 2> \Arg{code 2} "..." <tl var.\,$\sb n$> \Arg{code\,$\sb n$}\\
%    "}" \Arg{else case} 
%  \end{syntax}
%  This function works just like |\prg_case_int:nnn| except it
%  compares token list variables. 
%
% The function is expandable\footnote{Provided you use pdfTeX v1.30 or
% later} and is written in such a way that
% \texttt{f} style expansion can take place cleanly, i.e., no tokens
% from within the function are left over.
%  \end{function}
% 
%  \section{Generic loops}
%
%
%  \begin{function}{ \bool_while_do:nn |
%                    \bool_until_do:nn |
%                    \bool_do_while:nn |
%                    \bool_do_until:nn }
%  \begin{syntax}
%     "\bool_while_do:nn" \Arg{boolean expression} \Arg{code}  \\
%     "\bool_until_do:nn" \Arg{boolean expression} \Arg{code}
%  \end{syntax}
%  The `while' versions execute the code as long as <boolean
%  expression> is true and the `until' versions execute <code> as long
%  as <boolean expression> is false. The "while_do" functions execute
%  the body after testing the boolean and the "do_while" functions
%  executes the body first and then tests the boolean.
%  \end{function}
%
% \section{Choosing modes}
%
% \begin{function}{ \mode_if_vertical: / (pTF) }
% \begin{syntax}
%   "\mode_if_vertical:TF" \Arg{true code} \Arg{false code}
% \end{syntax}
% Determines if \TeX{} is in vertical mode or not and executes either
% <true code> or <false code> accordingly.
% \end{function}
%
% \begin{function}{ \mode_if_horizontal: / (pTF) }
% \begin{syntax}
%   "\mode_if_horizontal:TF" \Arg{true code} \Arg{false code}
% \end{syntax}
% Determines if \TeX{} is in horizontal mode or not and executes either
% <true code> or <false code> accordingly.
% \end{function}
%
%
% \begin{function}{ \mode_if_inner: / (pTF) }
% \begin{syntax}
%   "\mode_if_inner:TF" \Arg{true code} \Arg{false code}
% \end{syntax}
% Determines if \TeX{} is in inner mode or not and executes either
% <true code> or <false code> accordingly.
% \end{function}
%
% \begin{function}{ \mode_if_math: / (pTF) }
% \begin{syntax}
%   "\mode_if_math:TF" \Arg{true code} \Arg{false code}
% \end{syntax}
% Determines if \TeX{} is in math mode or not and executes either
% <true code> or <false code> accordingly.
% \begin{texnote}
% This version will choose the right branch even at the beginning of
% an alignment cell.
% \end{texnote}
% \end{function}
%
%
% \section{Alignment safe grouping and scanning}
%
% \begin{function}{\scan_align_safe_stop:}
% \begin{syntax}
%   "\scan_align_safe_stop:"
% \end{syntax}
% This function gets \TeX{} on the right track inside an alignment
% cell but without destroying any kerning.
% \end{function}
%
%
% \begin{function}{\group_align_safe_begin:|
%                  \group_align_safe_end:}
% \begin{syntax}
%   "\group_align_safe_begin:" <...> "\group_align_safe_end:"
% \end{syntax}
% Encloses <...> inside a group but is safe inside an alignment cell.
% See the implementation of |\peek_token_generic:NNTF| for an
% application.
% \end{function}
%
%
% \section{Producing $n$ copies}
% 
% There are often several different requirements for producing
% multiple copies of something. Sometimes one might want to produce a
% number of identical copies of a sequence of tokens whereas at other
% times the goal is to simulate a for loop as known from most real
% programming languages.
%
% \begin{function}{\prg_replicate:nn / (EXP) }
% \begin{syntax}
%   "\prg_replicate:nn" \Arg{number} \Arg{arg}
% \end{syntax}
% Creates <number> copies of <arg>. Note that it is expandable.
% \end{function}
%
%
% \begin{function}{\prg_stepwise_function:nnnN / (EXP) }
% \begin{syntax}
%   "\prg_stepwise_function:nnnN" \Arg{start} \Arg{step}
%   \Arg{end} <function>
% \end{syntax}
% This function performs <action> once for each step starting at
% <start> and ending once <end> is passed. <function> is placed
% directly in front of a brace group holding the current number so it
% should usually be a function taking one argument.
% \end{function}
%
% \begin{function}{\prg_stepwise_inline:nnnn}
% \begin{syntax}
%   "\prg_stepwise_inline:nnnn" \Arg{start} \Arg{step} \Arg{end}
%   \Arg{action}
% \end{syntax}
% Same as |\prg_stepwise_function:nnnN| except here <action> is
% performed each time with |##1| as a placeholder for the number
% currently being tested. This function is not expandable and it is
% nestable.
% \end{function}
%
% \begin{function}{\prg_stepwise_variable:nnnNn}
% \begin{syntax}
%   "\prg_stepwise_variable:nnnn" \Arg{start} \Arg{step} \Arg{end}
%   <temp-var> \Arg{action}
% \end{syntax}
% Same as |\prg_stepwise_inline:nnnn| except here the current value is
% stored in <temp-var> and the programmer can use it in <action>. This
% function is not expandable.
% \end{function}
%
% \section{Sorting}
%
%
%  \begin{function}{
%                   \prg_quicksort:n |
%  }
%  \begin{syntax}
%    "\prg_quicksort:n" "{" \Arg{item~1} \Arg{item~2} \dots \Arg{item~n} "}"
%  \end{syntax}
%  Performs a Quicksort on the token list. The comparisons are
%  performed by the function |\prg_quicksort_compare:nnTF| which is up
%  to the programmer to define. When the sorting process is over, all
%  items are given as argument to the function
%  |\prg_quicksort_function:n| which the programmer also controls.
%  \end{function}
%
%  \begin{function}{
%                   \prg_quicksort_function:n |
%                   \prg_quicksort_compare:nnTF
%  }
%  \begin{syntax}
%    "\prg_quicksort_function:n" \Arg{element} \\
%    "\prg_quicksort_compare:nnTF" \Arg{element 1} \Arg{element 2}\\
%  \end{syntax}
%  The two functions the programmer must define before calling
%  |\prg_quicksort:n|. As an example we could define
% \begin{quote}
% |\cs_set_nopar:Npn\prg_quicksort_function:n #1{{#1}}|\\
% |\cs_set_nopar:Npn\prg_quicksort_compare:nnTF #1#2#3#4 {\int_compare:nNnTF{#1}>{#2}}|
% \end{quote}
% Then the function call
% \begin{quote}
% |\prg_quicksort:n {876234520}|
% \end{quote}
% would return |{0}{2}{2}{3}{4}{5}{6}{7}{8}|. An alternative example
% where one sorts a list of words, |\prg_quicksort_compare:nnTF| could
% be defined as
% \begin{quote}
% |\cs_set_nopar:Npn\prg_quicksort_compare:nnTF #1#2 {|\\
% |  \int_compare:nNnTF{\tl_compare:nn{#1}{#2}}>\c_zero }|
% \end{quote}
% 
%  \end{function}
%  
%  \subsection{Variable type and scope}
%  
%\begin{function}{\prg_variable_get_scope:N / (EXP) }
%   \begin{syntax}
%     "\prg_variable_get_scope:N" <variable>
%   \end{syntax}
%   Returns the scope (\texttt{g} for global, blank otherwise) for the
%   <variable>.
%\end{function}
%
%\begin{function}{\prg_variable_get_type:N / (EXP) }
%   \begin{syntax}
%     "\prg_variable_get_type:N" <variable>
%   \end{syntax}
%   Returns the type of <variable> (\texttt{tl}, \texttt{int}, etc.)
%\end{function}
%
%\subsection{Mapping to variables}
%
%\begin{function}{ \prg_new_map_functions:Nn } 
%  \begin{syntax}
%    \cs{prg_new_map_functions:Nn} \meta{token} \Arg{name}
%  \end{syntax}
%  Creates a family of mapping functions which can be applied to 
%  a token list, dividing the list up at each occurance of the
%  \meta{token}. The functions defined will be
%  \begin{itemize}
%    \item \cs{\meta{name}_map_function:NN}
%    \item \cs{\meta{name}_map_function:nN}
%    \item \cs{\meta{name}_map_inline:Nn}
%    \item \cs{\meta{name}_map_inline:nn}
%    \item \cs{\meta{name}_map_break:}
%  \end{itemize}
%  Of these, the \texttt{inline} functions are not expandable but
%  the other functions can be used in expansion contexts. The use of
%  each function is best illustrated by the \cs{clist_map_\ldots} 
%  family defined by \LaTeX3 itself for mapping to comma-separated
%  lists. An error will be raised if the \meta{name} has already been
%  used to generate a family of mapping functions. All of the
%  definitions are created globally.
%\end{function}
%
%\begin{function}{ \prg_set_map_functions:Nn } 
%  \begin{syntax}
%    \cs{prg_set_map_functions:Nn} \meta{token} \Arg{name}
%  \end{syntax}
%  Creates a family of mapping functions which can be applied to 
%  a token list, dividing the list up at each occurance of the
%  \meta{token}. The functions defined will be
%  \begin{itemize}
%    \item \cs{\meta{name}_map_function:NN}
%    \item \cs{\meta{name}_map_function:nN}
%    \item \cs{\meta{name}_map_inline:Nn}
%    \item \cs{\meta{name}_map_inline:nn}
%    \item \cs{\meta{name}_map_break:}
%  \end{itemize}
%  Of these, the \texttt{inline} functions are not expandable but
%  the other functions can be used in expansion contexts. The use of
%  each function is best illustrated by the \cs{clist_map_\ldots} 
%  family defined by \LaTeX3 itself for mapping to comma-separated
%  lists. Any existing defintions for the \meta{name} will be 
%  overwritten. All of the definitions are created globally.
%\end{function}
%
% \end{documentation}
%
% \begin{implementation}
%
% \section{\pkg{l3prg} implementation}
%
% \TestFiles{m3prg001.lvt,m3prg002.lvt,m3prg003.lvt}
%
% \subsection{Variables}
%
% \begin{function}{ \l_tmpa_bool | \g_tmpa_bool }
% Reserved booleans.
% \end{function}
%
% \begin{variable}{\g_prg_inline_level_int}
% Global variable to track the nesting of the stepwise inline loop. 
% \end{variable}
%
% \subsection{Module code}
%
%    We start by ensuring that the required packages are loaded.
%    \begin{macrocode}
%<*package>
\ProvidesExplPackage
  {\filename}{\filedate}{\fileversion}{\filedescription}
\package_check_loaded_expl:
%</package>
%<*initex|package>
%    \end{macrocode}
%    
% \begin{macro}{\prg_return_true:}
% \TestMissing{This function is implicitly tested with all other conditionals!}
% \begin{macro}{\prg_return_false:}
% \TestMissing{This function is also implicitly tested with all other conditionals!}
% \begin{macro}{
%   \prg_set_conditional:Npnn,
%   \prg_new_conditional:Npnn,
%   \prg_set_protected_conditional:Npnn,
%   \prg_new_protected_conditional:Npnn
%}
% \begin{macro}{
%   \prg_set_conditional:Nnn,
%   \prg_new_conditional:Nnn,
%   \prg_set_protected_conditional:Nnn,
%  \prg_new_protected_conditional:Nnn
%}
% \begin{macro}{
%   \prg_set_eq_conditional:NNn,
%   \prg_new_eq_conditional:NNn
%}
% These are all defined in \pkg{l3basics}, as they are needed ``early''.
% This is just a reminder that that is the case!
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro} 
% \end{macro} 
%
%  \newpage ^^A because the previous macro margin block is really big!
%  \subsection{Choosing modes}
%
%  \begin{macro}[pTF]{\mode_if_vertical:}
%  \UnitTested
%    For testing vertical mode. Strikes me here on the bus with David,
%    that as long as we are just talking about returning true and
%    false states, we can just use the primitive conditionals for this
%    and gobbling the |\c_zero| in the input stream. However this
%    requires knowledge of the implementation so we keep things nice
%    and clean and use the return statements.
%    \begin{macrocode}
\prg_set_conditional:Npnn \mode_if_vertical: {p,TF,T,F}{
  \if_mode_vertical: \prg_return_true: \else: \prg_return_false: \fi:
}
%    \end{macrocode}
%  \end{macro}
%
%  \begin{macro}[pTF]{\mode_if_horizontal:}
%  \UnitTested
%  For testing horizontal mode.
%    \begin{macrocode}
\prg_set_conditional:Npnn \mode_if_horizontal: {p,TF,T,F}{
  \if_mode_horizontal: \prg_return_true: \else: \prg_return_false: \fi:
}
%    \end{macrocode}
%  \end{macro}
%
%  \begin{macro}[pTF]{\mode_if_inner:}
%  \UnitTested
%  For testing inner mode.
%    \begin{macrocode}
\prg_set_conditional:Npnn \mode_if_inner: {p,TF,T,F}{
  \if_mode_inner: \prg_return_true: \else: \prg_return_false: \fi:
}
%    \end{macrocode}
%  \end{macro}
%
%  \begin{macro}[pTF]{\mode_if_math:}
%  \UnitTested
%  For testing math mode. Uses the kern-save |\scan_align_safe_stop:|.
%    \begin{macrocode}
\prg_set_conditional:Npnn \mode_if_math: {p,TF,T,F}{
  \scan_align_safe_stop: \if_mode_math:
    \prg_return_true: \else: \prg_return_false: \fi:
}
%    \end{macrocode}
%  \end{macro}
%
% \paragraph{Alignment safe grouping and scanning}
%
%
%  \begin{macro}{\group_align_safe_begin:,\group_align_safe_end:}
%  \TeX's alignment structures present many problems. As Knuth says
%  himself in \emph{\TeX : The Program}: ``It's sort of a miracle
%  whenever |\halign| or |\valign| work, [\ldots]'' One problem relates
%  to commands that internally issues a |\cr| but also peek ahead for
%  the next character for use in, say, an optional argument. If the
%  next token happens to be a |&| with category code~4 we will get some
%  sort of weird error message because the underlying
%  |\tex_futurelet:D| will store the token at the end of the alignment
%  template. This could be a |&|$\sb4$ giving a message like
%  |! Misplaced \cr.| or even worse: it could be the |\endtemplate|
%  token causing even more trouble! To solve this we have to open a
%  special group so that \TeX{} still thinks it's on safe ground but at
%  the same time we don't want to introduce any brace group that may
%  find its way to the output. The following functions help with this
%  by using code documented only in Appendix~D of
%  \emph{The \TeX book}\dots
%    \begin{macrocode}
\cs_new_nopar:Npn \group_align_safe_begin: {
  \if_false:{\fi:\if_num:w`}=\c_zero\fi:}
\cs_new_nopar:Npn \group_align_safe_end:   {\if_num:w`{=\c_zero}\fi:}
%    \end{macrocode}
%  \end{macro}
%
%
%  \begin{macro}{\scan_align_safe_stop:}
%  When \TeX{} is in the beginning of an align cell (right after the
%  |\cr|) it is in a somewhat strange mode as it is looking ahead to
%  find an |\tex_omit:D| or |\tex_noalign:D| and hasn't looked at the
%  preamble yet. Thus an |\tex_ifmmode:D| test will always fail unless
%  we insert |\scan_stop:| to stop \TeX's scanning ahead. On the other
%  hand we don't want to insert a |\scan_stop:| every time as that will
%  destroy kerning between letters\footnote{Unless we enforce an extra
%  pass with an appropriate value of \texttt{\string\pretolerance}.}
%  Unfortunately there is no way to detect if we're in the beginning of
%  an alignment cell as they have different characteristics depending
%  on column number etc. However we \emph{can} detect if we're in an
%  alignment cell by checking the current group type and we can also
%  check if the previous node was a character or ligature. What is done
%  here is that |\scan_stop:| is only inserted iff a)~we're in the
%  outer part of an alignment cell and b)~the last node \emph{wasn't} a
%  char node or a ligature node.
%    \begin{macrocode}
\cs_new_nopar:Npn \scan_align_safe_stop: {
  \int_compare:nNnT \etex_currentgrouptype:D = \c_six
  {
    \int_compare:nNnF \etex_lastnodetype:D = \c_zero
    {
      \int_compare:nNnF \etex_lastnodetype:D = \c_seven
        \scan_stop:
    }
  }
}
%    \end{macrocode}
%  \end{macro}
%
% \subsection{Producing $n$ copies}
% 
% \begin{macro}{\prg_replicate:nn}
% \UnitTested
% \begin{macro}[aux]{\prg_replicate_aux:N,\prg_replicate_first_aux:N}
% This function uses a cascading csname technique by David Kastrup
% (who else :-)
% 
% The idea is to make the input "25" result in first adding five, and
% then 20 copies of the code to be replicated. The technique uses
% cascading csnames which means that we start building several csnames
% so we end up with a list of functions to be called in reverse
% order. This is important here (and other places) because it means
% that we can for instance make the function that inserts five copies
% of something to also hand down ten to the next function in
% line. This is exactly what happens here: in the example with "25"
% then the next function is the one that inserts two copies but it
% sees the ten copies handed down by the previous function. In order
% to avoid the last function to insert say, 100 copies of the original
% argument just to gobble them again we define separate functions to
% be inserted first. Finally we must ensure that the cascade comes to
% a peaceful end so we make it so that the original csname \TeX{} is
% creating is simply "\prg_do_nothing:" expanding to nothing.
%
% This function has one flaw though: Since it constantly passes down
% ten copies of its previous argument it will severely affect the main
% memory once you start demanding hundreds of thousands of copies. Now
% I don't think this is a real limitation for any ordinary use. An
% alternative approach is to create a string of "m"'s with
% "\int_to_roman:w" which can be done with just four macros but that
% method has its own problems since it can exhaust the string
% pool. Also, it is considerably slower than what we use here so the
% few extra csnames are well spent I would say.
%    \begin{macrocode}
\cs_new_nopar:Npn \prg_replicate:nn #1{
  \cs:w prg_do_nothing: 
  \exp_after:wN\prg_replicate_first_aux:N
  \tex_romannumeral:D -`\q \int_eval:n{#1} \cs_end: 
  \cs_end: 
}
\cs_new_nopar:Npn \prg_replicate_aux:N#1{
  \cs:w prg_replicate_#1:n\prg_replicate_aux:N
}
\cs_new_nopar:Npn \prg_replicate_first_aux:N#1{
  \cs:w prg_replicate_first_#1:n\prg_replicate_aux:N
}
%    \end{macrocode}
% \end{macro}
%
% Then comes all the functions that do the hard work of inserting all
% the copies.
%    \begin{macrocode}
\cs_new_nopar:Npn      \prg_replicate_ :n #1{}% no, this is not a typo!
\cs_new:cpn {prg_replicate_0:n}#1{\cs_end:{#1#1#1#1#1#1#1#1#1#1}}
\cs_new:cpn {prg_replicate_1:n}#1{\cs_end:{#1#1#1#1#1#1#1#1#1#1}#1}
\cs_new:cpn {prg_replicate_2:n}#1{\cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1}
\cs_new:cpn {prg_replicate_3:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1}
\cs_new:cpn {prg_replicate_4:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1}
\cs_new:cpn {prg_replicate_5:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1#1}
\cs_new:cpn {prg_replicate_6:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1#1#1}
\cs_new:cpn {prg_replicate_7:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1#1#1#1}
\cs_new:cpn {prg_replicate_8:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1#1#1#1#1}
\cs_new:cpn {prg_replicate_9:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1#1#1#1#1#1}
%    \end{macrocode}
%    Users shouldn't ask for something to be replicated once or even
%    not at all but\dots
%    \begin{macrocode}
\cs_new:cpn {prg_replicate_first_-:n}#1{\cs_end: \ERROR }
\cs_new:cpn {prg_replicate_first_0:n}#1{\cs_end: }
\cs_new:cpn {prg_replicate_first_1:n}#1{\cs_end: #1}
\cs_new:cpn {prg_replicate_first_2:n}#1{\cs_end: #1#1}
\cs_new:cpn {prg_replicate_first_3:n}#1{\cs_end: #1#1#1}
\cs_new:cpn {prg_replicate_first_4:n}#1{\cs_end: #1#1#1#1}
\cs_new:cpn {prg_replicate_first_5:n}#1{\cs_end: #1#1#1#1#1}
\cs_new:cpn {prg_replicate_first_6:n}#1{\cs_end: #1#1#1#1#1#1}
\cs_new:cpn {prg_replicate_first_7:n}#1{\cs_end: #1#1#1#1#1#1#1}
\cs_new:cpn {prg_replicate_first_8:n}#1{\cs_end: #1#1#1#1#1#1#1#1}
\cs_new:cpn {prg_replicate_first_9:n}#1{\cs_end: #1#1#1#1#1#1#1#1#1}
%    \end{macrocode} 
% \end{macro}
%
%
%
%
% \begin{macro}{\prg_stepwise_function:nnnN}
% \UnitTested
% \begin{macro}[aux]{\prg_stepwise_function_incr:nnnN,
%                    \prg_stepwise_function_decr:nnnN}
%   A stepwise function. Firstly we check the direction of the steps
%   |#2| since that will depend on which test we should use. If the
%   step is positive we use a greater than test, otherwise a less than
%   test.  If the test comes out true exit, otherwise perform |#4|,
%   add the step to |#1| and try again with this new value of |#1|.
%    \begin{macrocode}
\cs_new:Npn \prg_stepwise_function:nnnN #1#2{
  \int_compare:nNnTF{#2}<\c_zero
  {\exp_args:Nf\prg_stepwise_function_decr:nnnN }
  {\exp_args:Nf\prg_stepwise_function_incr:nnnN }
  {\int_eval:n{#1}}{#2}
}
\cs_new:Npn \prg_stepwise_function_incr:nnnN #1#2#3#4{
  \int_compare:nNnF {#1}>{#3}
  {
    #4{#1}
    \exp_args:Nf \prg_stepwise_function_incr:nnnN 
    {\int_eval:n{#1 + #2}} 
    {#2}{#3}{#4}
  }
}
\cs_new:Npn \prg_stepwise_function_decr:nnnN #1#2#3#4{
  \int_compare:nNnF {#1}<{#3}
  {
    #4{#1}
    \exp_args:Nf \prg_stepwise_function_decr:nnnN 
    {\int_eval:n{#1 + #2}} 
    {#2}{#3}{#4}
  }
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\prg_stepwise_inline:nnnn}
% \UnitTested
% \begin{variable}{\g_prg_inline_level_int}
% \begin{macro}[aux]{\prg_stepwise_inline_decr:nnnn,
%                    \prg_stepwise_inline_incr:nnnn}
%   This function uses the same approach as for instance
%   |\clist_map_inline:Nn| to allow arbitrary nesting. First construct
%   the special function and then call an auxiliary one which just
%   carries the newly constructed csname. Must make assignments global
%   when we maintain our own stack.
%    \begin{macrocode}
\cs_new_protected:Npn\prg_stepwise_inline:nnnn #1#2#3#4{
  \int_gincr:N \g_prg_inline_level_int
  \cs_gset_nopar:cpn{prg_stepwise_inline_\int_use:N\g_prg_inline_level_int :n}##1{#4}
  \int_compare:nNnTF {#2}<\c_zero
  {\exp_args:Ncf \prg_stepwise_inline_decr:Nnnn }
  {\exp_args:Ncf \prg_stepwise_inline_incr:Nnnn }
  {prg_stepwise_inline_\int_use:N\g_prg_inline_level_int :n} 
  {\int_eval:n{#1}} {#2} {#3}
  \int_gdecr:N \g_prg_inline_level_int
}
\cs_new:Npn \prg_stepwise_inline_incr:Nnnn #1#2#3#4{
  \int_compare:nNnF {#2}>{#4}
  {
    #1{#2}
    \exp_args:NNf \prg_stepwise_inline_incr:Nnnn #1
    {\int_eval:n{#2 + #3}} {#3}{#4}
  }
}
\cs_new:Npn \prg_stepwise_inline_decr:Nnnn #1#2#3#4{
  \int_compare:nNnF {#2}<{#4}
  {
    #1{#2}
    \exp_args:NNf \prg_stepwise_inline_decr:Nnnn #1
    {\int_eval:n{#2 + #3}} {#3}{#4}
  }
}
%    \end{macrocode}
% \end{macro}
% \end{variable}
% \end{macro}
%
% \begin{macro}{\prg_stepwise_variable:nnnNn}
% \UnitTested
% \begin{macro}[aux]{\prg_stepwise_variable_decr:nnnNn,
%                    \prg_stepwise_variable_incr:nnnNn}
%   Almost the same as above. Just store the value in |#4| and execute
%   |#5|.
%    \begin{macrocode}
\cs_new_protected:Npn \prg_stepwise_variable:nnnNn #1#2 {
  \int_compare:nNnTF {#2}<\c_zero
  {\exp_args:Nf\prg_stepwise_variable_decr:nnnNn}
  {\exp_args:Nf\prg_stepwise_variable_incr:nnnNn}
  {\int_eval:n{#1}}{#2}
}
\cs_new_protected:Npn \prg_stepwise_variable_incr:nnnNn #1#2#3#4#5 {
  \int_compare:nNnF {#1}>{#3}
  {
    \cs_set_nopar:Npn #4{#1} #5
    \exp_args:Nf \prg_stepwise_variable_incr:nnnNn
    {\int_eval:n{#1 + #2}}{#2}{#3}#4{#5}
  }
}
\cs_new_protected:Npn \prg_stepwise_variable_decr:nnnNn #1#2#3#4#5 {
  \int_compare:nNnF {#1}<{#3}
  {
    \cs_set_nopar:Npn #4{#1} #5
    \exp_args:Nf \prg_stepwise_variable_decr:nnnNn
    {\int_eval:n{#1 + #2}}{#2}{#3}#4{#5}
  }
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
%
% \subsection{Booleans}
%  For normal booleans we set them to either "\c_true_bool" or "\c_false_bool"
%  and then use "\if_bool:N" to choose the right branch. The functions
%  return either the TF, T, or F case \emph{after} ending the |\if_bool:N|.
%  We only define the |N| versions here as the |c| versions can easily
%  be constructed with the expansion module.
%
%  \begin{macro}{\bool_new:N,\bool_new:c,
%                \bool_set_true:N,\bool_set_true:c,
%                \bool_set_false:N,\bool_set_false:c,
%                \bool_gset_true:N,\bool_gset_true:c,
%                \bool_gset_false:N,\bool_gset_false:c}
% \UnitTested
%  Defining and setting a boolean is easy.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \bool_new:N #1   { \cs_new_eq:NN #1 \c_false_bool }
\cs_new_protected_nopar:Npn \bool_new:c #1   { \cs_new_eq:cN {#1} \c_false_bool }
\cs_new_protected_nopar:Npn \bool_set_true:N   #1 { \cs_set_eq:NN  #1 \c_true_bool }
\cs_new_protected_nopar:Npn \bool_set_true:c   #1 { \cs_set_eq:cN  {#1} \c_true_bool }
\cs_new_protected_nopar:Npn \bool_set_false:N  #1 { \cs_set_eq:NN  #1 \c_false_bool }
\cs_new_protected_nopar:Npn \bool_set_false:c  #1 { \cs_set_eq:cN  {#1} \c_false_bool }
\cs_new_protected_nopar:Npn \bool_gset_true:N   #1 { \cs_gset_eq:NN  #1 \c_true_bool }
\cs_new_protected_nopar:Npn \bool_gset_true:c   #1 { \cs_gset_eq:cN  {#1} \c_true_bool }
\cs_new_protected_nopar:Npn \bool_gset_false:N  #1 { \cs_gset_eq:NN  #1 \c_false_bool }
\cs_new_protected_nopar:Npn \bool_gset_false:c  #1 { \cs_gset_eq:cN  {#1} \c_false_bool }
%    \end{macrocode}
%  \end{macro}
%
%  \begin{macro}{\bool_set_eq:NN,
%                \bool_set_eq:Nc,
%                \bool_set_eq:cN,
%                \bool_set_eq:cc,
%                \bool_gset_eq:NN,
%                \bool_gset_eq:Nc,
%                \bool_gset_eq:cN,
%                \bool_gset_eq:cc}
% \UnitTested
%  Setting a boolean to another is also pretty easy.
%    \begin{macrocode}
\cs_new_eq:NN \bool_set_eq:NN \cs_set_eq:NN
\cs_new_eq:NN \bool_set_eq:Nc \cs_set_eq:Nc
\cs_new_eq:NN \bool_set_eq:cN \cs_set_eq:cN
\cs_new_eq:NN \bool_set_eq:cc \cs_set_eq:cc
\cs_new_eq:NN \bool_gset_eq:NN \cs_gset_eq:NN
\cs_new_eq:NN \bool_gset_eq:Nc \cs_gset_eq:Nc
\cs_new_eq:NN \bool_gset_eq:cN \cs_gset_eq:cN
\cs_new_eq:NN \bool_gset_eq:cc \cs_gset_eq:cc
%    \end{macrocode}
%  \end{macro}
%
%  \begin{variable}{\l_tmpa_bool,\g_tmpa_bool}
%  A few booleans just if you need them.
%    \begin{macrocode}
\bool_new:N \l_tmpa_bool
\bool_new:N \g_tmpa_bool
%    \end{macrocode}
%  \end{variable}
%
%  \begin{macro}[pTF]{\bool_if:N,\bool_if:c}
% \UnitTested
%  Straight forward here. We could optimize here if we wanted to as
%  the boolean can just be input directly.
%    \begin{macrocode}
\prg_set_conditional:Npnn \bool_if:N #1 {p,TF,T,F}{
  \if_bool:N #1 \prg_return_true: \else: \prg_return_false: \fi:
}
\cs_generate_variant:Nn \bool_if_p:N {c}
\cs_generate_variant:Nn \bool_if:NTF {c}
\cs_generate_variant:Nn \bool_if:NT {c}
\cs_generate_variant:Nn \bool_if:NF {c}
%    \end{macrocode}
%  \end{macro}
%
%
%
% \begin{macro}{\bool_while_do:Nn,\bool_while_do:cn,
%               \bool_until_do:Nn,\bool_until_do:cn}
% \UnitTested
% \UnitTested
%  A "while" loop where the boolean is tested before executing the
%  statement. The `while' version executes the code as long as the
%  boolean is true; the `until' version executes the code as
%  long as the boolean is false.
%    \begin{macrocode}
\cs_new:Npn \bool_while_do:Nn #1 #2 {
  \bool_if:NT #1 {#2 \bool_while_do:Nn #1 {#2}}
}
\cs_generate_variant:Nn \bool_while_do:Nn {c}
%    \end{macrocode}
%    
%    \begin{macrocode}
\cs_new:Npn \bool_until_do:Nn #1 #2 {
  \bool_if:NF #1 {#2 \bool_until_do:Nn #1 {#2}}
}
\cs_generate_variant:Nn \bool_until_do:Nn {c}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\bool_do_while:Nn,\bool_do_while:cn,
%               \bool_do_until:Nn,\bool_do_until:cn}
% \UnitTested
% \UnitTested
%  A "do-while" loop where the body is performed at least once and the
%  boolean is tested after executing the body. Otherwise identical to
%  the above functions.
%    \begin{macrocode}
\cs_new:Npn \bool_do_while:Nn #1 #2 {
  #2 \bool_if:NT #1 {\bool_do_while:Nn #1 {#2}}
}
\cs_generate_variant:Nn \bool_do_while:Nn {c}
%    \end{macrocode}
%    
%    \begin{macrocode}
\cs_new:Npn \bool_do_until:Nn #1 #2 {
  #2 \bool_if:NF #1 {\bool_do_until:Nn #1 {#2}}
}
\cs_generate_variant:Nn \bool_do_until:Nn {c}
%    \end{macrocode}
% \end{macro}
%
%
%
% \subsection{Parsing boolean expressions}
%
%  \begin{macro}[pTF]{\bool_if:n}
%  \UnitTested
%  \begin{macro}[aux]{\bool_get_next:N, \bool_cleanup:N, \bool_choose:NN,
%                     \bool_!:w,
%                     \bool_Not:w,
%                     \bool_Not:w,
%                     \bool_(:w,
%                     \bool_p:w,
%                     \bool_8_1:w,
%                     \bool_I_1:w,
%                     \bool_8_0:w,
%                     \bool_I_0:w,
%                     \bool_)_0:w,
%                     \bool_)_1:w,
%                     \bool_S_0:w,
%                     \bool_S_1:w}
%
%    Evaluating the truth value of a list of predicates is done using
%    an input syntax somewhat similar to the one found in other
%    programming languages with "(" and ")" for grouping, "!" for
%    logical `Not', "&&" for logical `And' and "||" for logical
%    "Or". We shall use the terms Not, And, Or, Open and Close for
%    these operations.
% 
%   Any expression is terminated by a Close operation. Evaluation
%   happens from left to right in the following manner using a GetNext
%   function:
%   \begin{itemize}
%   \item If an Open is seen, start evaluating a new expression using
%   the Eval function and
%   call GetNext again.
%   \item If a Not is seen, insert a negating function (if-even in
%   this case) and call GetNext.
%   \item If none of the above, start evaluating a new expression by
%   reinserting the token found (this is supposed to be a predicate
%   function) in front of Eval.
%   \end{itemize}
%   The Eval function then contains a post-processing operation which
%   grabs the instruction following the predicate. This is either And,
%   Or or Close. In each case the truth value is used to determine
%   where to go next. The following situations can arise:
%    \begin{description}
%    \item[\meta{true}And] Current truth value is true, logical And
%      seen, continue with GetNext to examine truth value of next
%      boolean (sub-)expression.
%    \item[\meta{false}And] Current truth value is false, logical And
%      seen, stop evaluating the predicates within this sub-expression
%      and break to the nearest Close. Then return \meta{false}.
%    \item[\meta{true}Or] Current truth value is true, logical Or
%      seen, stop evaluating the predicates within this sub-expression
%      and break to the nearest Close. Then return \meta{true}.
%    \item[\meta{false}Or] Current truth value is false, logical Or
%      seen, continue with GetNext to examine truth value of next
%      boolean (sub-)expression.
%    \item[\meta{true}Close] Current truth value is true, Close
%      seen, return \meta{true}.
%    \item[\meta{false}Close] Current truth value is false, Close
%      seen, return \meta{false}.
%    \end{description}
%    We introduce an additional Stop operation with the following
%    semantics:
%    \begin{description}
%    \item[\meta{true}Stop] Current truth value is true, return
%      \meta{true}.
%    \item[\meta{false}Stop] Current truth value is false, return
%      \meta{false}.
%    \end{description}
%    The reasons for this follow below.
%
%    Now for how these works in practice. The canonical true and false
%    values have numerical values 1 and 0 respectively. We evaluate
%    this using the primitive "\tex_number:D" operation. First we
%    issue a "\group_align_safe_begin:" as we are using "&&" as syntax
%    shorthand for the And operation and we need to hide it for \TeX.
%    We also need to finish this special group before finally
%    returning a "\c_true_bool" or "\c_false_bool" as there might
%    otherwise be something left in front in the input stream. For
%    this we call the Stop operation, denoted simply by a "S"
%    following the last Close operation.
%    \begin{macrocode}
\cs_new:Npn \bool_if_p:n #1{
  \group_align_safe_begin: 
  \bool_get_next:N ( #1 )S
}
%    \end{macrocode}
% The GetNext operation. We make it a switch: If not a "!" or "(", we
% assume it is a predicate.
%    \begin{macrocode}
\cs_new:Npn \bool_get_next:N #1{
  \use:c {
    bool_ 
    \if_meaning:w !#1 ! \else: \if_meaning:w (#1 ( \else: p \fi: \fi:
    :w 
  } #1
}
%    \end{macrocode}
% This variant gets called when a \textsc{not} has just been entered.
% It (eventually) results in a reveral of the logic of the directly following
% material.
%    \begin{macrocode}
\cs_new:Npn \bool_get_not_next:N #1{
  \use:c {
    bool_not_
    \if_meaning:w !#1 ! \else: \if_meaning:w (#1 ( \else: p \fi: \fi:
    :w
  } #1
}
%    \end{macrocode}
% We need these later on to nullify the unity operation |!!|.
%    \begin{macrocode}
\cs_new:Npn \bool_get_next:NN #1#2{
  \bool_get_next:N #2
}
\cs_new:Npn \bool_get_not_next:NN #1#2{
  \bool_get_not_next:N #2
}
%    \end{macrocode}
% The Not operation. Discard the token read and reverse the truth
% value of the next expression if there
% are brackets; otherwise
% if we're coming up to a |!| then we don't need to reverse anything
% (but we then want to continue scanning ahead in case some fool has written
% |!!(...)|);
% otherwise we have a boolean that we can reverse here and now.
%    \begin{macrocode}
\cs_new:cpn { bool_!:w } #1#2 {
  \if_meaning:w ( #2
    \exp_after:wN \bool_Not:w
  \else:
    \if_meaning:w ! #2
      \exp_after:wN \exp_after:wN \exp_after:wN \bool_get_next:NN
    \else:
      \exp_after:wN \exp_after:wN \exp_after:wN \bool_Not:N
    \fi:
  \fi:
  #2
}
%    \end{macrocode}
% Variant called when already inside a \textsc{not}.
% Essentially the opposite of the above.
%    \begin{macrocode}
\cs_new:cpn { bool_not_!:w } #1#2 {
  \if_meaning:w ( #2
    \exp_after:wN \bool_not_Not:w
  \else:
    \if_meaning:w ! #2
      \exp_after:wN \exp_after:wN \exp_after:wN \bool_get_not_next:NN
    \else:
      \exp_after:wN \exp_after:wN \exp_after:wN \bool_not_Not:N
    \fi:
  \fi:
  #2
}
%    \end{macrocode}
% These occur when processing |!(...)|. The idea is to use a variant
% of |\bool_get_next:N| that finishes its parsing with a logic reveral.
% Of course, the double logic reversal gets us back to where we started.
%    \begin{macrocode}
\cs_new:Npn \bool_Not:w {
  \exp_after:wN \tex_number:D \bool_get_not_next:N
}
\cs_new:Npn \bool_not_Not:w {
  \exp_after:wN \tex_number:D \bool_get_next:N
}
%    \end{macrocode}
% These occur when processing |!<bool>| and can be evaluated directly.
%    \begin{macrocode}
\cs_new:Npn \bool_Not:N #1 {
  \exp_after:wN \bool_p:w
  \if_meaning:w #1 \c_true_bool
    \c_false_bool
  \else:
    \c_true_bool
  \fi:
}
\cs_new:Npn \bool_not_Not:N #1 {
  \exp_after:wN \bool_p:w
  \if_meaning:w #1 \c_true_bool
    \c_true_bool
  \else:
    \c_false_bool
  \fi:
}
%    \end{macrocode}
% The Open operation. Discard the token read and start a
% sub-expression.
% |\bool_get_next:N| continues building up the logical expressions as usual;
% |\bool_not_cleanup:N| is what reverses the logic if we're inside |!(...)|.
%    \begin{macrocode}
\cs_new:cpn {bool_(:w}#1{
  \exp_after:wN  \bool_cleanup:N \tex_number:D \bool_get_next:N
}
\cs_new:cpn {bool_not_(:w}#1{
  \exp_after:wN  \bool_not_cleanup:N \tex_number:D \bool_get_next:N
}
%    \end{macrocode}
% Otherwise just evaluate the predicate and look for And, Or or Close
% afterward.
%    \begin{macrocode}
\cs_new:cpn {bool_p:w}{\exp_after:wN  \bool_cleanup:N \tex_number:D  }
\cs_new:cpn {bool_not_p:w}{\exp_after:wN  \bool_not_cleanup:N \tex_number:D  }
%    \end{macrocode}
% This cleanup function can be omitted once predicates return their
% true/false booleans outside the conditionals.
%    \begin{macrocode}
\cs_new_nopar:Npn \bool_cleanup:N #1{
  \exp_after:wN \bool_choose:NN \exp_after:wN #1
  \int_to_roman:w-`\q
}
\cs_new_nopar:Npn \bool_not_cleanup:N #1{
  \exp_after:wN \bool_not_choose:NN \exp_after:wN #1
  \int_to_roman:w-`\q
}
%    \end{macrocode}
% Branching the six way switch.
% Reversals should be reasonably straightforward.
% When programming this, however, I got things around the wrong way a few times.
% (Will's hacks onto Morten's code, that is.)
%    \begin{macrocode}
\cs_new_nopar:Npn \bool_choose:NN #1#2{  \use:c{bool_#2_#1:w} }
\cs_new_nopar:Npn \bool_not_choose:NN #1#2{  \use:c{bool_not_#2_#1:w} }
%    \end{macrocode}
% Continues scanning. Must remove the second "&" or "|".
%    \begin{macrocode}
\cs_new_nopar:cpn{bool_&_1:w}&{\bool_get_next:N}
\cs_new_nopar:cpn{bool_|_0:w}|{\bool_get_next:N}
\cs_new_nopar:cpn{bool_not_&_0:w}&{\bool_get_next:N}
\cs_new_nopar:cpn{bool_not_|_1:w}|{\bool_get_next:N}
%    \end{macrocode}
% Closing a group is just about returning the result. The Stop
% operation is similar except it closes the special alignment group
% before returning the boolean.
%    \begin{macrocode}
\cs_new_nopar:cpn{bool_)_0:w}{ \c_false_bool }
\cs_new_nopar:cpn{bool_)_1:w}{ \c_true_bool }
\cs_new_nopar:cpn{bool_not_)_0:w}{ \c_true_bool }
\cs_new_nopar:cpn{bool_not_)_1:w}{ \c_false_bool }
\cs_new_nopar:cpn{bool_S_0:w}{\group_align_safe_end: \c_false_bool }
\cs_new_nopar:cpn{bool_S_1:w}{\group_align_safe_end: \c_true_bool }
%    \end{macrocode}
% When the truth value has already been decided, we have to throw away
% the remainder of the current group as we are doing minimal
% evaluation. This is slightly tricky as there are no braces so we
% have to play match the "()" manually.
%    \begin{macrocode}
\cs_new:cpn{bool_&_0:w}&{\bool_eval_skip_to_end:Nw \c_false_bool}
\cs_new:cpn{bool_|_1:w}|{\bool_eval_skip_to_end:Nw \c_true_bool}
\cs_new:cpn{bool_not_&_1:w}&{\bool_eval_skip_to_end:Nw \c_false_bool}
\cs_new:cpn{bool_not_|_0:w}|{\bool_eval_skip_to_end:Nw \c_true_bool}
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%
% \begin{macro}[aux]{\bool_eval_skip_to_end:Nw,
%     \bool_eval_skip_to_end_aux:Nw,\bool_eval_skip_to_end_auxii:Nw}
% There is always at least one ")" waiting, namely the outer
% one. However, we are facing the problem that there may be more than
% one that need to be finished off and we have to detect the correct
% number of them. Here is a complicated example showing how this is
% done. After evaluating the following, we realize we must skip
% everything after the first And. Note the extra Close at the end.
% \begin{quote}
%   |\c_false_bool  && ((abc) && xyz) && ((xyz) && (def)))|
% \end{quote}
% First read up to the first Close. This gives us the list we first
% read up until the first right parenthesis so we are looking at the
% token list
% \begin{quote}
%   |((abc|
% \end{quote}
% This contains two Open markers so we must remove two groups. Since
% no evaluation of the contents is to be carried out, it doesn't
% matter how we remove the groups as long as we wind up with the
% correct result. We therefore first remove a "()" pair and what
% preceded the Open -- but leave the contents as it may contain Open
% tokens itself -- leaving
% \begin{quote}
%   |(abc && xyz) && ((xyz) && (def)))|
% \end{quote}
% Another round of this gives us
% \begin{quote}
%   |(abc && xyz|
% \end{quote}
% which still contains an Open so we remove another "()" pair, giving us
% \begin{quote}
%   |abc && xyz && ((xyz) && (def)))|
% \end{quote}
% Again we read up to a Close and again find Open tokens:
% \begin{quote}
%   |abc && xyz && ((xyz|
% \end{quote}
% Further reduction gives us
% \begin{quote}
%   |(xyz && (def)))|
% \end{quote}
% and then
% \begin{quote}
%   |(xyz && (def|
% \end{quote}
% with reduction to
% \begin{quote}
%   |xyz && (def))|
% \end{quote}
% and ultimately we arrive at no Open tokens being skipped and we can
% finally close the group nicely.
%
% This whole operation could be made a lot simpler if we were allowed
% to do simple pattern matching. With a new enough pdf\TeX\ one can do
% that sort of thing to test for existence of particular tokens.
%    \begin{macrocode}
\cs_new:Npn \bool_eval_skip_to_end:Nw #1#2){
  \bool_eval_skip_to_end_aux:Nw #1 #2(\q_no_value\q_stop{#2}
}
%    \end{macrocode}
% If no right parenthesis, then |#3| is no_value and we are done, return
% the boolean |#1|.  If there is, we need to grab a () pair and then
% recurse
%    \begin{macrocode}
\cs_new:Npn \bool_eval_skip_to_end_aux:Nw #1#2(#3#4\q_stop#5{
  \quark_if_no_value:NTF #3
  { #1 }
  { \bool_eval_skip_to_end_auxii:Nw #1 #5 }
}
%    \end{macrocode}
% keep the boolean, throw away anything up to the ( as it is
% irrelevant, remove a () pair but remember to reinsert |#3| as it may
% contain ( tokens!
%    \begin{macrocode}
\cs_new:Npn \bool_eval_skip_to_end_auxii:Nw #1#2(#3){ 
  \bool_eval_skip_to_end:Nw #1#3 )
}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\bool_set:Nn,\bool_set:cn,\bool_gset:Nn,\bool_gset:cn}
% This function evaluates a boolean expression and assigns the first
% argument the meaning "\c_true_bool" or "\c_false_bool". 
%    \begin{macrocode}
\cs_new:Npn \bool_set:Nn #1#2 {\tex_chardef:D #1 = \bool_if_p:n {#2}}
\cs_new:Npn \bool_gset:Nn #1#2 {
  \tex_global:D \tex_chardef:D #1 =  \bool_if_p:n {#2} 
}
\cs_generate_variant:Nn \bool_set:Nn {c}
\cs_generate_variant:Nn \bool_gset:Nn {c}
%    \end{macrocode}
% \end{macro}
%
%  \begin{macro}{\bool_not_p:n}
% \UnitTested
% The "not" variant just reverses the outcome of |\bool_if_p:n|. Can
% be optimized but this is nice and simple and according to the
% implementation plan. Not even particularly useful to have it when
% the infix notation is easier to use.
%    \begin{macrocode}
\cs_new:Npn \bool_not_p:n #1{ \bool_if_p:n{!(#1)} }
%    \end{macrocode}
%  \end{macro}
%
%  \begin{macro}{\bool_xor_p:nn}
% \UnitTested
%    Exclusive or. If the boolean expressions have same truth value,
%    return false, otherwise return true.
%    \begin{macrocode}
\cs_new:Npn \bool_xor_p:nn #1#2 {
  \int_compare:nNnTF {\bool_if_p:n { #1 }} = {\bool_if_p:n { #2 }}
  {\c_false_bool}{\c_true_bool} 
}
%    \end{macrocode}
%  \end{macro}
%
%    \begin{macrocode}
\prg_set_conditional:Npnn \bool_if:n  #1 {TF,T,F}{
  \if_predicate:w \bool_if_p:n{#1}
    \prg_return_true: \else: \prg_return_false: \fi:  
}
%    \end{macrocode}
%
% \begin{macro}{\bool_while_do:nn,\bool_do_while:nn}
% \UnitTested
% \begin{macro}{\bool_until_do:nn,\bool_do_until:nn}
% \begin{arguments}
% \item Predicate test
% \item Code to execute
% \end{arguments}
%    \begin{macrocode}
\cs_new:Npn \bool_while_do:nn #1#2 {
  \bool_if:nT {#1} { #2 \bool_while_do:nn {#1}{#2} }
}
\cs_new:Npn \bool_until_do:nn #1#2 {
  \bool_if:nF {#1} { #2 \bool_until_do:nn {#1}{#2} }
}
\cs_new:Npn \bool_do_while:nn #1#2 {
  #2 \bool_if:nT {#1} { \bool_do_while:nn {#1}{#2} }
}
\cs_new:Npn \bool_do_until:nn #1#2 {
  #2 \bool_if:nF {#1} { \bool_do_until:nn {#1}{#2} }
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsection{Case switch}
%
% \begin{macro}{\prg_case_int:nnn}
% \UnitTested
% \begin{macro}[aux]{\prg_case_int_aux:nnn}
%   This case switch is in reality quite simple. It takes three arguments:
%   \begin{enumerate}
%   \item An integer expression you wish to find.
%   \item A list of pairs of \Arg{integer expr} \Arg{code}. 
%   The list can be as long as is desired
%   and \meta{integer expr} can be negative.
%   \item The code to be executed if the value wasn't found.
%   \end{enumerate}
%   We don't need the else case here yet, so leave it dangling in the
%   input stream. 
%    \begin{macrocode}
\cs_new:Npn \prg_case_int:nnn #1 #2 {
%    \end{macrocode}
% We will be parsing on |#1| for each step so we might as well
% evaluate it first in case it is complicated. 
%    \begin{macrocode}
  \exp_args:Nf \prg_case_int_aux:nnn { \int_eval:n{#1}} #2
%    \end{macrocode}
% The \texttt{?} below is just so there are enough arguments when we
% reach the end. And it made you look.~\texttt{;-)}
%    \begin{macrocode}
  \q_recursion_tail ? \q_recursion_stop 
}
\cs_new:Npn \prg_case_int_aux:nnn #1#2#3{
%    \end{macrocode}
% If we reach the end, return the else case. We just remove braces.
%    \begin{macrocode}
  \quark_if_recursion_tail_stop_do:nn{#2}{\use:n}
%    \end{macrocode}
% Otherwise we compare (which evaluates |#2| for us)
%    \begin{macrocode}
  \int_compare:nNnTF{#1}={#2}
%    \end{macrocode}
% If true, we want to remove the remainder of the list, the else case
% and then execute the code specified. |\prg_end_case:nw {#3}| does
% just that in one go. This means |f| style expansion works the way
% one wants it to work.
%    \begin{macrocode}
  { \prg_end_case:nw {#3} }
  { \prg_case_int_aux:nnn {#1}}
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\prg_case_dim:nnn}
% \UnitTested
% \begin{macro}[aux]{\prg_case_dim_aux:nnn}
%   Same as |\prg_case_dim:nnn| except it is for \meta{dim} registers.
%    \begin{macrocode}
\cs_new:Npn \prg_case_dim:nnn #1 #2 {
  \exp_args:No \prg_case_dim_aux:nnn {\dim_eval:n{#1}} #2
  \q_recursion_tail ? \q_recursion_stop 
}
\cs_new:Npn \prg_case_dim_aux:nnn #1#2#3{
  \quark_if_recursion_tail_stop_do:nn{#2}{\use:n}
  \dim_compare:nNnTF{#1}={#2}
  { \prg_end_case:nw {#3} }
  { \prg_case_dim_aux:nnn {#1}}
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\prg_case_str:nnn}
% \UnitTested
% \begin{macro}[aux]{\prg_case_str_aux:nnn}
%   Same as |\prg_case_dim:nnn| except it is for strings.
%    \begin{macrocode}
\cs_new:Npn \prg_case_str:nnn #1 #2 {
  \prg_case_str_aux:nnn {#1} #2
  \q_recursion_tail ? \q_recursion_stop 
}
\cs_new:Npn \prg_case_str_aux:nnn #1#2#3{
  \quark_if_recursion_tail_stop_do:nn{#2}{\use:n}
  \str_if_eq:xxTF{#1}{#2}
  { \prg_end_case:nw {#3} }
  { \prg_case_str_aux:nnn {#1}}
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\prg_case_tl:Nnn}
% \UnitTested
% \begin{macro}[aux]{\prg_case_tl_aux:NNn}
%   Same as |\prg_case_dim:nnn| except it is for token list variables.
%    \begin{macrocode}
\cs_new:Npn \prg_case_tl:Nnn #1 #2 {
  \prg_case_tl_aux:NNn #1 #2
  \q_recursion_tail ? \q_recursion_stop 
}
\cs_new:Npn \prg_case_tl_aux:NNn #1#2#3{
  \quark_if_recursion_tail_stop_do:Nn #2{\use:n}
  \tl_if_eq:NNTF #1 #2
  {  \prg_end_case:nw {#3} }
  { \prg_case_tl_aux:NNn #1}
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
%
% \begin{macro}[aux]{\prg_end_case:nw}
%   Ending a case switch is always performed the same way so we
%   optimize for this. |#1| is the code to execute, |#2| the
%   remainder, and |#3| the dangling else case.
%    \begin{macrocode}
\cs_new:Npn \prg_end_case:nw #1#2\q_recursion_stop#3{#1}
%    \end{macrocode}
% \end{macro}

%
% \subsection{Sorting}
%
%
% \begin{macro}[aux]{\prg_define_quicksort:nnn}
%   |#1| is the name, |#2| and |#3| are the tokens enclosing the
%   argument. For the somewhat strange \meta{clist} type which doesn't
%   enclose the items but uses a separator we define it by hand
%   afterwards. When doing the first pass, the algorithm wraps all
%   elements in braces and then uses a generic quicksort which works
%   on token lists.
%
%   As an example
%   \begin{quote}
%   |\prg_define_quicksort:nnn{seq}{\seq_elt:w}{\seq_elt_end:w}|  
%   \end{quote}
%   defines the user function |\seq_quicksort:n| and furthermore
%   expects to use the two functions |\seq_quicksort_compare:nnTF|
%   which compares the items and |\seq_quicksort_function:n| which is
%   placed before each sorted item. It is up to the programmer to
%   define these functions when needed. For the |seq| type a sequence
%   is a token list variable, so one additionally has to define
%   \begin{quote}
%     |\cs_set_nopar:Npn \seq_quicksort:N{\exp_args:No\seq_quicksort:n}|
%   \end{quote}
%
%
%   For details on the implementation see ``Sorting in \TeX's Mouth''
%   by Bernd Raichle. Firstly we define the function for parsing the
%   initial list and then the braced list afterwards.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \prg_define_quicksort:nnn #1#2#3 {
  \cs_set:cpx{#1_quicksort:n}##1{
    \exp_not:c{#1_quicksort_start_partition:w} ##1
    \exp_not:n{#2\q_nil#3\q_stop}
  }
  \cs_set:cpx{#1_quicksort_braced:n}##1{
    \exp_not:c{#1_quicksort_start_partition_braced:n} ##1
    \exp_not:N\q_nil\exp_not:N\q_stop
  }
  \cs_set:cpx {#1_quicksort_start_partition:w} #2 ##1 #3{
    \exp_not:N \quark_if_nil:nT {##1}\exp_not:N \use_none_delimit_by_q_stop:w
    \exp_not:c{#1_quicksort_do_partition_i:nnnw} {##1}{}{} 
  }
  \cs_set:cpx {#1_quicksort_start_partition_braced:n} ##1 {
    \exp_not:N \quark_if_nil:nT {##1}\exp_not:N \use_none_delimit_by_q_stop:w
    \exp_not:c{#1_quicksort_do_partition_i_braced:nnnn} {##1}{}{} 
  }
%    \end{macrocode}
% Now for doing the partitions.
%    \begin{macrocode}
  \cs_set:cpx {#1_quicksort_do_partition_i:nnnw} ##1##2##3 #2 ##4 #3 {
    \exp_not:N \quark_if_nil:nTF {##4} \exp_not:c {#1_do_quicksort_braced:nnnnw}
    {
      \exp_not:c{#1_quicksort_compare:nnTF}{##1}{##4}
      \exp_not:c{#1_quicksort_partition_greater_ii:nnnn}
      \exp_not:c{#1_quicksort_partition_less_ii:nnnn}
    }
    {##1}{##2}{##3}{##4}
  }
  \cs_set:cpx {#1_quicksort_do_partition_i_braced:nnnn} ##1##2##3##4 {
    \exp_not:N \quark_if_nil:nTF {##4} \exp_not:c {#1_do_quicksort_braced:nnnnw}
    {
      \exp_not:c{#1_quicksort_compare:nnTF}{##1}{##4}
      \exp_not:c{#1_quicksort_partition_greater_ii_braced:nnnn}
      \exp_not:c{#1_quicksort_partition_less_ii_braced:nnnn}
    }
    {##1}{##2}{##3}{##4}
  }
  \cs_set:cpx {#1_quicksort_do_partition_ii:nnnw} ##1##2##3 #2 ##4 #3 {
    \exp_not:N \quark_if_nil:nTF {##4} \exp_not:c {#1_do_quicksort_braced:nnnnw}
    {
      \exp_not:c{#1_quicksort_compare:nnTF}{##4}{##1}
      \exp_not:c{#1_quicksort_partition_less_i:nnnn}
      \exp_not:c{#1_quicksort_partition_greater_i:nnnn}
    }
    {##1}{##2}{##3}{##4}
  }
  \cs_set:cpx {#1_quicksort_do_partition_ii_braced:nnnn} ##1##2##3##4 {
    \exp_not:N \quark_if_nil:nTF {##4} \exp_not:c {#1_do_quicksort_braced:nnnnw}
    {
      \exp_not:c{#1_quicksort_compare:nnTF}{##4}{##1}
      \exp_not:c{#1_quicksort_partition_less_i_braced:nnnn}
      \exp_not:c{#1_quicksort_partition_greater_i_braced:nnnn}
    }
    {##1}{##2}{##3}{##4}
  }
%    \end{macrocode}
% This part of the code handles the two branches in each
% sorting. Again we will also have to do it braced.
%    \begin{macrocode}
  \cs_set:cpx {#1_quicksort_partition_less_i:nnnn} ##1##2##3##4{
    \exp_not:c{#1_quicksort_do_partition_i:nnnw}{##1}{##2}{{##4}##3}}
  \cs_set:cpx {#1_quicksort_partition_less_ii:nnnn} ##1##2##3##4{
    \exp_not:c{#1_quicksort_do_partition_ii:nnnw}{##1}{##2}{##3{##4}}}
  \cs_set:cpx {#1_quicksort_partition_greater_i:nnnn} ##1##2##3##4{
    \exp_not:c{#1_quicksort_do_partition_i:nnnw}{##1}{{##4}##2}{##3}}
  \cs_set:cpx {#1_quicksort_partition_greater_ii:nnnn} ##1##2##3##4{
    \exp_not:c{#1_quicksort_do_partition_ii:nnnw}{##1}{##2{##4}}{##3}}
  \cs_set:cpx {#1_quicksort_partition_less_i_braced:nnnn} ##1##2##3##4{
    \exp_not:c{#1_quicksort_do_partition_i_braced:nnnn}{##1}{##2}{{##4}##3}}
  \cs_set:cpx {#1_quicksort_partition_less_ii_braced:nnnn} ##1##2##3##4{
    \exp_not:c{#1_quicksort_do_partition_ii_braced:nnnn}{##1}{##2}{##3{##4}}}
  \cs_set:cpx {#1_quicksort_partition_greater_i_braced:nnnn} ##1##2##3##4{
    \exp_not:c{#1_quicksort_do_partition_i_braced:nnnn}{##1}{{##4}##2}{##3}}
  \cs_set:cpx {#1_quicksort_partition_greater_ii_braced:nnnn} ##1##2##3##4{
    \exp_not:c{#1_quicksort_do_partition_ii_braced:nnnn}{##1}{##2{##4}}{##3}}
%    \end{macrocode}
% Finally, the big kahuna! This is where the sub-lists are sorted.
%    \begin{macrocode}
  \cs_set:cpx {#1_do_quicksort_braced:nnnnw} ##1##2##3##4\q_stop {
    \exp_not:c{#1_quicksort_braced:n}{##2}
    \exp_not:c{#1_quicksort_function:n}{##1}
    \exp_not:c{#1_quicksort_braced:n}{##3}
  }
}
%    \end{macrocode}
% \end{macro}
%
%
% \begin{macro}{\prg_quicksort:n}
% \UnitTested
%   A simple version. Sorts a list of tokens, uses the function
%   |\prg_quicksort_compare:nnTF| to compare items, and places the
%   function |\prg_quicksort_function:n| in front of each of them.
%    \begin{macrocode}
\prg_define_quicksort:nnn {prg}{}{}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\prg_quicksort_function:n}
% \UnitTested
% \begin{macro}{\prg_quicksort_compare:nnTF}
% \UnitTested
%    \begin{macrocode}
\cs_set:Npn \prg_quicksort_function:n {\ERROR}
\cs_set:Npn \prg_quicksort_compare:nnTF {\ERROR}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% 
%\subsection{Variable type and scope}
%
%
%\begin{macro}{\prg_variable_get_scope:N}
%\begin{macro}[aux]{\prg_variable_get_scope_aux:w}
%\begin{macro}{\prg_variable_get_type:N}
%\begin{macro}[aux]{\prg_variable_get_type:w}
% Expandable functions to find the type of a variable, and to 
% return \texttt{g} if the variable is global. The trick for 
% \cs{prg_variable_get_scope:N} is the same as that in 
% \cs{cs_split_function:NN}, but it can be simplified as the
% requirements here are less complex.
%    \begin{macrocode}
\group_begin:
  \tex_lccode:D `\& = `\g \tex_relax:D
  \tex_catcode:D `\& = \c_twelve \tex_relax:D
\tl_to_lowercase:n {
  \group_end:
  \cs_new_nopar:Npn \prg_variable_get_scope:N #1 {
    \exp_last_unbraced:Nf \prg_variable_get_scope_aux:w
    { \cs_to_str:N #1 \exp_stop_f: \q_stop }
  }
  \cs_new_nopar:Npn \prg_variable_get_scope_aux:w #1#2 \q_stop {
    \token_if_eq_meaning:NNT & #1 {g}
  }
}
\group_begin:
  \tex_lccode:D `\& = `\_ \tex_relax:D
  \tex_catcode:D `\& = \c_twelve \tex_relax:D
\tl_to_lowercase:n {
  \group_end:
  \cs_new_nopar:Npn \prg_variable_get_type:N #1 {
    \exp_after:wN \p;rg_variable_get_type_aux:w 
      \token_to_str:N #1 & a \q_stop 
  }
  \cs_new_nopar:Npn \prg_variable_get_type_aux:w #1 & #2#3 \q_stop {
    \token_if_eq_meaning:NNTF a #2 {
      #1
    }{
      \prg_variable_get_type_aux:w #2#3 \q_stop
    }
  }
}
%    \end{macrocode}
%\end{macro}
%\end{macro}
%\end{macro}
%\end{macro} 
%
%\subsection{Mapping to variables}
%
%\begin{macro}{\prg_new_map_functions:Nn}
%\begin{macro}{\prg_set_map_functions:Nn}
% The idea here is to generate all of the various mapping functions 
% in one go. Everything is done with expansion so that the performance
% hit is taken at definition time and not at point of use.  The inline
% version uses a counter as this keeps things nestable, and global to
% avoid problems with, for example, table cells.
%    \begin{macrocode}
\cs_new_protected:Npn \prg_new_map_functions:Nn #1#2 {
  \cs_if_free:cTF { #2 _map_function:NN }
    { \prg_set_map_functions:Nn #1 {#2} }
    {
      \msg_kernel_error:nnx { code } { csname-already-defined }
        { \token_to_str:c { #2 _map_function:NN } }
    }
}
\cs_new_protected:Npn \prg_set_map_functions:Nn #1#2 {
  \cs_gset_nopar:cpx { #2 _map_function:NN } ##1##2
    { 
      \exp_not:N \tl_if_empty:NF ##1
         {
           \exp_not:N \exp_after:wN
           \exp_not:c { #2 _map_function_aux:Nw }
           \exp_not:N \exp_after:wN ##2 ##1
           \exp_not:n { #1 \q_recursion_tail #1 \q_recursion_stop }
         }  
    }
  \cs_gset:cpx { #2 _map_function:nN } ##1##2
    { 
      \exp_not:N \tl_if_blank:nF {##1}
        {
          \exp_not:c { #2 _map_function_aux:Nw } ##2 ##1
            \exp_not:n { #1 \q_recursion_tail #1 \q_recursion_stop }
        }
    }  
  \cs_gset:cpx { #2 _map_function_aux:Nw } ##1##2 #1
    {
      \exp_not:N \quark_if_recursion_tail_stop:n {##2}
      ##1 {##2}
      \exp_not:c { #2 _map_function_aux:Nw } ##1
    }
  \cs_if_free:cT { g_ #2 _map_inline_int }
    { \int_new:c { g_ #2 _map_inline_int } }
  \cs_gset_protected_nopar:cpx { #2 _map_inline:Nn } ##1##2
    {
      \exp_not:N \tl_if_empty:NF ##1
        {
          \exp_not:N \int_gincr:N \exp_not:c { g_ #2 _map_inline_int }
          \cs_gset:cpn 
            { 
              #2 _map_inline_ 
              \exp_not:N \int_use:N \exp_not:c { g_ #2 _map_inline_int }
              :n 
            } 
            ####1 {##2}
          \exp_not:N \exp_last_unbraced:NcV
            \exp_not:c { #2 _map_function_aux:Nw }  
            { 
              #2 _map_inline_ 
              \exp_not:N \int_use:N \exp_not:c { g_ #2 _map_inline_int }
              :n 
            }
            ##1 \exp_not:n { #1 \q_recursion_tail #1 \q_recursion_stop }
          \exp_not:N \int_gdecr:N \exp_not:c { g_ #2 _map_inline_int }
        }
    }
  \cs_gset_protected:cpx { #2 _map_inline:nn } ##1##2 
    {
      \exp_not:N \tl_if_empty:nF {##1}
        {
          \exp_not:N \int_gincr:N \exp_not:c { g_ #2 _map_inline_int }
          \cs_gset:cpn 
            { 
              #2 _map_inline_ 
              \exp_not:N \int_use:N \exp_not:c { g_ #2 _map_inline_int }
              :n 
            } 
            ####1 {##2}
          \exp_not:N \exp_args:Nc
            \exp_not:c { #2 _map_function_aux:Nw }  
            { 
              #2 _map_inline_ 
              \exp_not:N \int_use:N \exp_not:c { g_ #2 _map_inline_int }
              :n 
            }
            ##1 \exp_not:n { #1 \q_recursion_tail #1 \q_recursion_stop }
          \exp_not:N \int_gdecr:N \exp_not:c { g_ #2 _map_inline_int }
        }
    }
  \cs_gset_eq:cN { #2 _map_break: } 
    \use_none_delimit_by_q_recursion_stop:w
}
%    \end{macrocode}
%\end{macro}
%\end{macro}
%
%  That's it (for now).
%    \begin{macrocode}
%</initex|package>
%    \end{macrocode}
%
%    \begin{macrocode}
%<*showmemory>
\showMemUsage
%</showmemory>
%    \end{macrocode}
%
% \end{implementation}
% \PrintIndex
%
% \endinput