% 
% \iffalse
%<*driver>
\documentclass{ltxdoc}
\catcode`\_=12
\begin{document}
\DocInput{churchbool.dtx}
\end{document}
%</driver>
% \fi
% 
% 
% \title{Church boolean implementations}
% \author{Lars Hellstr\"om}
% \maketitle
% 
% \section{Preliminaries}
% 
% Since I'll probably be working within a \LaTeXe\ system when 
% developing the following, I'll need to provide the \LaTeX3 commands 
% I'll use separately.
% 
%    \begin{macrocode}
%<*2e>
\def\ExplSyntaxOn{%
   \catcode  126=10 \relax % tilde is a space char.
   \catcode   32=9  \relax % space is ignored
   \catcode    9=9  \relax % tab also ignored
   \endlinechar =32 \relax % endline is space
   \catcode   95=11 \relax % underscore letter
   \catcode   58=11 \relax % colon letter
}
\def\ExplSyntaxOff{%
   \catcode  126=13 \relax % tilde is active.
   \catcode   32=10 \relax % space is space
   \catcode    9=10 \relax % tab also space
   \endlinechar =13 \relax % endline is ^^M
   \catcode   95=8  \relax % underscore is subscript
   \catcode   58=12 \relax % colon is other
}
\ExplSyntaxOn
\def\cs_new:Npn{\long\def} % Fake: Ignores checking new status
\def\cs_set_eq:NN #1 { \let #1=~ }
\def\q_stop{\string\q_stop} % Isn't this a much safer way to
\def\q_mark{\string\q_mark} % construct a quark?
%</2e>
%    \end{macrocode}
% 
% 
% 
% \section{The real stuff}
% 
%    \begin{macrocode}
%<*code>
%    \end{macrocode}
% 
% \subsection{The booleans themselves}
% 
% The rules of the game are that a ``boolean'', in wide sense, is 
% anything with an overall syntax of |:TF|, i.e.,
% \begin{quote}
%   \meta{boolean}\marg{true code}\marg{false code}
% \end{quote}
% will eventually end up as either \meta{true code} or \meta{false 
% code}, depending on what value the boolean ``evaluates to''.
% 
% \begin{macro}{\if_true:TF}
% \begin{macro}{\if_false:TF}
%   The constant boolean values are therefore identical to the 
%   classical helper macros |\@firstoftwo| and |\@secondoftwo|.
%    \begin{macrocode}
\cs_new:Npn \if_true:TF #1 #2 { #1 }
\cs_new:Npn \if_false:TF #1 #2 { #2 }
%    \end{macrocode}
% \end{macro}\end{macro}
% 
% \begin{macro}{\if_and:nnTF}
% \begin{macro}{\if_or:nnTF}
% \begin{macro}{\if_not:nTF}
%   The nice thing about Church booleans is that boolean expressions 
%   in terms of them can be computed purely using macro expansion.
%   Concretely,
%   \begin{quote}
%     |\if_and:nnTF|\marg{b1}\marg{b2}\marg{true code}\marg{false code}
%   \end{quote}
%   expands to \meta{true code} iff both \meta{b1} and \meta{b1} 
%   evaluate to true, and expands to \meta{false code} otherwise;
%   \begin{quote}
%     |\if_or:nnTF|\marg{b1}\marg{b2}\marg{true code}\marg{false code}
%   \end{quote}
%   expands to \meta{false code} iff both \meta{b1} and \meta{b1} 
%   evaluate to false, and expands to \meta{true code} otherwise;
%   \begin{quote}
%     |\if_not:nTF|\marg{b1}\marg{true code}\marg{false code}
%   \end{quote}
%   expands to \meta{false code} iff \meta{b1} evaluate to true, and 
%   expands to \meta{true code} otherwise.
%   
%   All evaluation is short-curcuit, i.e., if the result is known 
%   from evaluating \meta{b1} alone, then \meta{b2} will not be 
%   evaluated.
%    \begin{macrocode}
\cs_new:Npn \if_and:nnTF #1 #2 { #1 {#2} {\if_false:TF} }
\cs_new:Npn \if_or:nnTF #1 #2 { #1 {\if_true:TF} {#2} }
\cs_new:Npn \if_not:nnTF #1 { #1 {\if_false:TF} {\if_true:TF} }
%    \end{macrocode}
% \end{macro}\end{macro}\end{macro}
% 
% \begin{macro}{\if_and:nnnTF}
% \begin{macro}{\if_or:nnnTF}
%   Higher arity conjunctions can be constructed by nesting the 
%   binary ones, but also in a single step.
%    \begin{macrocode}
\cs_new:Npn \if_and:nnnTF #1 #2 #3 { 
   #1 {#2 {#3} {\if_false:TF} } {\if_false:TF} 
}
\cs_new:Npn \if_or:nnnTF #1 #2 #3 { 
   #1 {\if_true:TF} {#2 {\if_true:TF} {#3} } 
}
%    \end{macrocode}
%   Note in particular that the arguments don't need to be copied. 
%   Exclusive or, should one wish to implement it, is not quite so 
%   nice.
% \end{macro}\end{macro}
% 
% 
% \subsection{Church booleans as variables}
% 
% Since Church booleans aren't ordinary values, but rather functions, 
% one might feel uncertain as to how feasible it is to store such a 
% boolean value in a variable; getting this wrong could instead end 
% up storing the expression for a boolean, and cause it to be 
% reevaluated each time used. However, the solution is extremely 
% simple.
% 
% \begin{macro}{\bool_set:Nn}
%   The effect of
%   \begin{quote}
%     |\bool_set:Nn|\marg{cs}\marg{boolean}
%   \end{quote}
%   is to evaluate the \meta{boolean} and set the control sequence 
%   \meta{cs} to either |\if_true:TF| or |\if_false:TF| accordingly.
%    \begin{macrocode}
\cs_new:Npn \bool_set:Nn #1 #2 { 
   #2 { \cs_set_eq:NN #1 \if_true:TF } { \cs_set_eq:NN #1 \if_false:TF }
}
%    \end{macrocode}
% \end{macro}
% 
% 
% \subsection{Infix expressions of Church booleans}
% 
% Although Church booleans are most at home within a prefix notation, 
% it turns out to also be possible to form infix expressions of them, 
% within a suitable parsing framework. The boolean expression syntax 
% supported here is
% \begin{description}
%   \def\makelabel#1{\meta{#1}~\ensuremath{\longleftarrow}}
%   \item[expression]
%     \meta{term} $\mid$ \meta{term} |OR| \meta{expression}
%   \item[term]
%     \meta{factor} $\mid$ \meta{factor} |AND| \meta{term}
%   \item[factor]
%     \meta{terminal} $\mid$ |NOT| \meta{factor}
%   \item[terminal]
%     \meta{Church boolean} $\mid$ |(| \meta{expression} |)|
% \end{description}
% (Note the parentheses in the last branch.)
% 
% The unexpected contrapositive of the above syntax specification is 
% that anything which is part of something put forth as an 
% \meta{expression} and which is not part of an |AND|, |OR|, |NOT|, 
% |(|, or |)| will be assumed to be part of \meta{Church boolean}. 
% Typos may therefore lead to highly surprising results\dots
% 
% 
% \subsubsection{Detecting reserved words}
% 
% The ``reserved words'' in an expression are |AND|, |OR|, |NOT|, 
% |(|, and |)|. For each of these, it is necessary to have a test for 
% whether that word occurs in a token sequence (not counting 
% occurrencies between braces). These tests are based on standard 
% exploits of trickeries made possible by \TeX's rules for matching 
% delimited and undelimited arguments.
% 
% \begin{macro}{\if_AND_in:nTF}
%   This macro is a Church boolean if used as
%   \begin{quote}
%     |\if_AND_in:nTF|\marg{expression fragment}
%   \end{quote}
%   It evaluates to true (purely by expansion) iff the three token 
%   sequence |AND| occurs unbraced in the \meta{expression fragment}.
%    \begin{macrocode}
\cs_new:Npn \if_AND_in:nTF #1 {
   \if_AND_in_helper:w #1 AND \q_mark \if_true:TF \q_mark \if_false:TF
     \q_stop
}
\cs_new:Npn \if_AND_in_helper:w #1 AND #2 #3 \q_mark #4 #5 \q_stop {#4}
%    \end{macrocode}
%   The way it works is that if there is an |AND| in the 
%   \meta{expression fragment}, then in the expansion of 
%   |\if_AND_in_helper:w|, |#1| will consist of everything up to that 
%   |AND|, so |#2#3| will consist of everything up to the first 
%   |\q_mark|, and hence |#4| will be the |\if_true:TF|. If on the other 
%   hand there is no |AND|, then |#1| will consist of the whole 
%   \meta{expression fragment}, |#2| will be the first |\q_mark|, and 
%   |#4| therefore what follows after the second |\q_mark|, namely 
%   |\if_false:TF|.
% \end{macro}
% 
% \begin{macro}{\if_OR_in:nTF}
% \begin{macro}{\if_NOT_in:nTF}
% \begin{macro}{\if_lparen_in:nTF}
% \begin{macro}{\if_rparen_in:nTF}
%   The remaining reserved words are detected in exactly the same way.
%    \begin{macrocode}
\cs_new:Npn \if_OR_in:nTF #1 {
   \if_OR_in_helper:w #1 OR \q_mark \if_true:TF \q_mark \if_false:TF
     \q_stop
}
\cs_new:Npn \if_OR_in_helper:w #1 OR #2 #3 \q_mark #4 #5 \q_stop {#4}
\cs_new:Npn \if_NOT_in:nTF #1 {
   \if_NOT_in_helper:w #1 NOT \q_mark \if_true:TF \q_mark \if_false:TF
     \q_stop
}
\cs_new:Npn \if_NOT_in_helper:w #1 NOT #2 #3 \q_mark #4 #5 \q_stop {#4}
\cs_new:Npn \if_lparen_in:nTF #1 {
   \if_lparen_in_helper:w #1 ( \q_mark \if_true:TF \q_mark \if_false:TF
     \q_stop
}
\cs_new:Npn \if_lparen_in_helper:w #1 ( #2 #3 \q_mark #4 #5 \q_stop {#4}
\cs_new:Npn \if_rparen_in:nTF #1 {
   \if_rparen_in_helper:w #1 ) \q_mark \if_true:TF \q_mark \if_false:TF
     \q_stop
}
\cs_new:Npn \if_rparen_in_helper:w #1 ) #2 #3 \q_mark #4 #5 \q_stop {#4}
%    \end{macrocode}
% \end{macro}\end{macro}\end{macro}\end{macro}
% 
% 
% 
% \subsubsection{Parsing parenthesis-free expressions}
% 
% For starters, we will consider parsing expressions without 
% parentheses. The syntax relevant for this is thus:
% \begin{description}
%   \def\makelabel#1{\meta{#1}~\ensuremath{\longleftarrow}}
%   \item[nopar-expression]
%     \meta{nopar-term} $\mid$ 
%     \meta{nopar-term} |OR| \meta{nopar-expression}
%   \item[nopar-term]
%     \meta{nopar-factor} $\mid$ 
%     \meta{nopar-factor} |AND| \meta{nopar-term}
%   \item[nopar-factor]
%     \meta{Church boolean} $\mid$ |NOT| \meta{nopar-factor}
% \end{description}
% A straightforward technique for this is to check if the thing we're 
% parsing contains the reserved word at this level, and if so split 
% at that word and parse the parts separately, or else reparse the 
% thing as the next simpler thing. This will lead to subexpressions 
% being parsed lazily, which is probably a good thing.
% 
% \begin{macro}{\if_noparexpr:nTF}
%   To illustrate this technique, here is the top level parser for 
%   \meta{nopar-expression}s. Its job is to turn
%   \begin{quote}
%     |\if_noparexpr:nTF{|\meta{nopar-term}| OR |^^A
%     \meta{nopar-expression}|}|
%   \end{quote}
%   into
%   \begin{quote}
%     |\if_or:nnTF{ \if_noparterm:nTF|\marg{nopar-term} |}{|
%     |\if_noparexpr:nTF|\marg{nopar-expression} |}|
%   \end{quote}
%   and
%   \begin{quote}
%     |\if_noparexpr:nTF|\marg{nopar-term}
%   \end{quote}
%   into
%   \begin{quote}
%     |\if_noparterm:nTF|\marg{nopar-term}
%   \end{quote}
%   From this description, the implementation is next to obvious.
%    \begin{macrocode}
\cs_new:Npn \if_noparexpr:nTF #1 {
   \if_OR_in:nTF{#1}{
      \if_noparexpr_split:w #1\q_stop
   }{
      \if_noparterm:nTF{#1}
   }
}
\cs_new:Npn \if_noparexpr_split:w #1 OR #2 \q_stop {
   \if_or:nnTF{ \if_noparterm:nTF{#1} }{ \if_noparexpr:nTF{#2} }
}
%    \end{macrocode}
%   For slightly larger speed (and reducing the number of tokens), one 
%   could preexpand the |\if_or:nnTF|, making the above instead
%\begin{verbatim}
% \cs_new:Npn \if_noparexpr_split:w #1 OR #2 \q_stop {
%    \if_noparterm:nTF{#1} \if_true:TF { \if_noparexpr:nTF{#2} }
%    
% }
%\end{verbatim}
% \end{macro}
% 
% \begin{macro}{\if_noparterm:nTF}
%   With the above in mind, the following definition of a macro for 
%   doing terms should hold no surprises.
%    \begin{macrocode}
\cs_new:Npn \if_noparterm:nTF #1 {
   \if_AND_in:nTF{#1}{
      \if_noparterm_split:w #1\q_stop
   }{
      \if_noparfactor:nTF{#1}
   }
}
\cs_new:Npn \if_noparterm_split:w #1 AND #2 \q_stop {
   \if_and:nnTF{ \if_noparfactor:nTF{#1} }{ \if_noparterm:nTF{#2} }
}
%    \end{macrocode}
% \end{macro}
% 
% \begin{macro}{\if_noparfactor:nTF}
%   For handling |NOT|, we actually do this kind of preexpansion, 
%   since it is so extremely easy. A point of doing this is that it 
%   simplifies a comparison with a parser that would eliminate double 
%   negations before evaluating the terminal boolean; that turns out 
%   to be an unnecessary complication, since even working out whether 
%   we have parsed an even or odd number of |NOT|s in this 
%   \meta{nopar-factor} amounts to at least as much work as the 
%   negations that the above would construct from the whole thing.
%    \begin{macrocode}
\cs_new:Npn \if_noparfactor:nTF #1 {
   \if_NOT_in:nTF{#1}{
      \if_noparfactor_split:w #1\q_stop
   }{
      #1
%    \end{macrocode}
%   Inserting a |\use_i:n| in front of that |#1|, while \emph{not} 
%   wrapping the |#1| in braces, should have the effect of gobbling 
%   all spaces in front of the terminal booleans in an expression. 
%   Spaces following them are gobbled already by some |\if_true:TF| 
%   or |\if_false:TF|.
%    \begin{macrocode}
   }
}
\cs_new:Npn \if_noparfactor_split:w #1 NOT #2 \q_stop {
   #2 \if_false:TF \if_true:TF
}
%    \end{macrocode}
% \end{macro}
% 
% 
% \subsubsection{Parsing general expressions}
% 
% The idea used for parsing general expressions is to replace 
% parentheses not containing another parenthesis with a 
% |\if_noparexpr:nTF| call, since that is a \meta{Church boolean} and 
% thus syntactically valid at that point; this process is repeated 
% until no parentheses remain, at which point we have a 
% \meta{nopar-expression}.
% 
% \begin{macro}{\if_bool_expr:nTF}
%   When locating a parenthesis to convert, it is convenient to start 
%   with the end of it, as the first right parenthesis in an 
%   \meta{expression} always closes a parenthesis not containing 
%   another parenthesis.
%    \begin{macrocode}
\cs_new:Npn \if_bool_expr:nTF #1 {
  \if_rparen_in:nTF {#1} {
     \bool_first_rparen_split:w #1 \q_stop
  }{
     \if_noparexpr:nTF{#1}
  }
}
%    \end{macrocode}
% \end{macro}
% 
% \begin{macro}{\first_rparen_split:w}
%   After finding the right parenthesis, one must look for a matching 
%   left parenthesis.
%    \begin{macrocode}
\cs_new:Npn \bool_first_rparen_split:w #1 ) #2 \q_stop {
   \if_lparen_in:nTF { #1 } {
      \bool_first_lparen_split:w #1 \q_stop {#2}
   }{
%    \end{macrocode}
%   The case that there isn't a left parenthesis is an error that 
%   we actually can detect! The only problem is what to do about it, 
%   since we may be in expand-only land here. One way of raising an 
%   error is to refer to an undefined but readably named control 
%   sequence.
%    \begin{macrocode}
      \use:c{No~matching~left~parenthesis~in~boolean~expression!}
%    \end{macrocode}
%   It may in this situation be tempting to throw away both the |T| 
%   and |F| arguments up ahead, but in the presence of surrounding 
%   macros (e.g.~a |\if_not:nTF|) that can just as well lead to both 
%   the eventual \meta{true-code} and ditto \meta{false-code} being 
%   executed, as well as a jumble of bizarre errors. Just picking one 
%   branch can still lead to further errors, but hopefully not 
%   dramatically many of them.
%    \begin{macrocode}
      \if_false:TF
   }
}
%    \end{macrocode}
% \end{macro}
% 
% \begin{macro}{\bool_first_lparen_split:w}
% \begin{macro}{\bool_last_lparen_split:w}
%   The matching left parenthesis we're looking for is the last one 
%   before the previously detected right parenthesis. \TeX\ macros can 
%   only pick out the first occurrence of a token however, so in order 
%   to find the last one it becomes necessary to do some looping by 
%   means of tail recursion. To that end, this macro has the call 
%   syntax
%   \begin{quote}
%     |\bool_last_lparen_split:w| \meta{fragment} |\q_stop|
%     \marg{prefix} \marg{suffix}
%   \end{quote}
%   with the token sequence
%   \begin{quote}
%     \meta{prefix}|(|\meta{fragment}|)|\meta{suffix}
%   \end{quote}
%   an invariant of the loop. Material is however being moved from 
%   \meta{fragment} to \meta{prefix}.
%   
%    \begin{macrocode}
\cs_new:Npn \bool_last_lparen_split:w #1 ( #2 \q_stop #3 #4 {
   \if_lparen_in:nTF { #2 } {
      \bool_last_lparen_split:w #2 \q_stop {#3(#1} {#4}
   }{
%    \end{macrocode}
%   When there are no more left parentheses in |#2|, then it will be 
%   precisely the \meta{nopar-expression} that the first right 
%   parenthesis ended, so we can now convert it to an 
%   |\if_noparexpr:nTF|. Note that that will still be inserted into 
%   an |\if_bool_expr:nTF|; it will mutate itself to an 
%   |\if_noparexpr:nTF| in due time, when there are no parentheses 
%   left in it.
%    \begin{macrocode}
      \if_bool_expr:nTF{ #3 ( #1 \if_noparexpr:nTF{#2} #4 }
   }
}
%    \end{macrocode}
%   
%   There is, however, a complication for the first iteration, in 
%   that the \meta{fragment} at that point is not preceded by a left 
%   parenthesis. Hence we need a separate iteration macro at that 
%   point, with the slightly simpler syntax
%   \begin{quote}
%     |\bool_first_lparen_split:w| \meta{fragment} |\q_stop|
%     \marg{suffix}
%   \end{quote}
%   such that it is
%   \begin{quote}
%     \meta{fragment}|)|\meta{suffix}
%   \end{quote}
%   that is equal to the above invariant token sequence.
%   
%    \begin{macrocode}
\cs_new:Npn \bool_first_lparen_split:w #1 ( #2 \q_stop #3 {
   \if_lparen_in:nTF { #2 } {
      \bool_last_lparen_split:w #2 \q_stop {#1} {#3}
   }{
      \if_bool_expr:nTF{ #1 \if_noparexpr:nTF{#2} #3 }
   }
}
%</code>
%    \end{macrocode}
% \end{macro}\end{macro}
% 
%    \begin{macrocode}
%<2e>\ExplSyntaxOff
%    \end{macrocode}
% 
% 
% \section{Tests}
% 
%    \begin{macrocode}
%<*tests>
%<*2e>
\documentclass{article}
\begin{document}
\ExplSyntaxOn
%</2e>
%    \end{macrocode}
% 
% First the expression that was mentioned on \LaTeX-L.
%    \begin{macrocode}
\bool_set:Nn\l_my_first_bool{\if_true:TF}
\bool_set:Nn\l_my_second_bool{\if_true:TF}
\bool_set:Nn\l_my_third_bool{\if_false:TF}
Should~evaluate~to~true.~
\if_bool_expr:nTF
   { \l_my_first_bool AND ( \l_my_second_bool AND NOT \l_my_third_bool ) }
   {Evaluates~to~true.}
   {Evaluates~to~false.}
\par
\bool_set:Nn\l_my_third_bool{\if_true:TF}
Should~evaluate~to~false.~
\if_bool_expr:nTF
   { \l_my_first_bool AND ( \l_my_second_bool AND NOT \l_my_third_bool ) }
   {Evaluates~to~true.}
   {Evaluates~to~false.}
\par
%    \end{macrocode}
% 
% Next an expression meant to exercise all twists and turns of the 
% commands, also demonstrating that nonexpandable tests are supported.
%    \begin{macrocode}
Should~evaluate~to~true.~
\if_bool_expr:nTF{
   ((( NOT \l_my_first_bool OR \IfFileExists{latex.ltx} )))
   AND \l_my_second_bool
}{Evaluates~to~true.}{Evaluates~to~false.}
\par
%    \end{macrocode}
%    \begin{macrocode}
%<*2e>
\ExplSyntaxOff
\end{document}
%</2e>
%</tests>
%    \end{macrocode}
% 
\endinput