## LATEX-L@LISTSERV.UNI-HEIDELBERG.DE

#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Proportional Font

Subject:

Re: Church booleans

From:

Date:

Wed, 19 Oct 2011 23:42:21 +0200

Content-Type:

multipart/mixed

Parts/Attachments:

 text/plain (142 lines) multipart/appledouble (142 lines) , application/applefile (142 lines) , churchbool.dtx (1 lines)
 Bruno Le Floch skrev 2011-10-19 18.16: >> A better formatting would be >> >> \bool_if:nTF { >> \bool_pred:n{\l_my_first_bool}&& ( >> \bool_pred:n{\l_my_second_bool}&& >> ! \bool_pred:n{\l_my_third_bool} >> ) >> } > > Still unreadable in my view, because the \bool_pred:n add no > information, and are just there to make TeX happy. Since we can avoid > them altogether, let's do it. We can also avoid these corny infix expressions altogether... ;-) > \bool_if:nTF > { > \l_my_first_bool > && ( > \l_my_second_bool > && ! \l_my_third_bool > ) > } > >> :) But maybe the problem is that&&, (, ), !, and || do not really stand out >> from the background of braces and backslashes (far less than against the >> background of alphanumeric identifiers you'd encounter in C)? Fortanish >> .AND., .OR., and .NOT. would be more eye-catching, but the parentheses are >> probably a lost cause readability-wise. > > I find&& and || to be more visible than AND and OR in fact (probably > a matter of syntax highlighting in the editor). I find it unlikely that an editor with syntax highlighting for LaTeX would assign special highlighting to || and !, unless someone has specially reconfigured it to do so. >> Well, it depends on the parsing scheme one uses. If instead going for >> delimited-argument style subformula grabbing, then it wouldn't matter how >> many tokens an expression terminal (predicate) consists of, and as a >> side-effect operation priority becomes straightforward (the operation you >> split at first gets the lowest priority). What would be tricky for this >> approach is the handling of parentheses, since in that case there are two >> distinct possibilities for "the next token of interest here", but I think it >> is doable (first split on one, then try to split on the second, and treat >> the combination of the outcomes as a case). > > The other problem with this approach is that my working copy with > Church booleans is now catcode agnostic, while delimited arguments > would require one particular catcode. You are right on the other > arguments for that approach. Catcodes for ADNORT and () don't tend to change much. >> I believe one could preferably structure the whole thing as an expand-only >> rewrite of infix boolean expression to Church-style compositions of >> booleans. It probably wouldn't be good at catching certain syntax errors, >> though. > > That's a pretty big change. I need some time to ponder it. (And in any > case, changes won't happen before a few weeks from now.) Well, changes could as a matter of fact happen tonight already, since I had just completed my implementation of it when I received your mail. See attached file (I hope it gets through). I've probably picked strange names for some macros, but I think the post-colon parts are acceptable. Here's an example: \if_bool_expr:nTF{     ( NOT \l_my_first_bool OR \IfFileExists{latex.ltx} )     AND \l_my_second_bool }{Evaluates~to~true.}{Evaluates~to~false.} This works. And it's done using macros. *Nothing* but macros. >> Consider a command whose role is similar to that of the 2e \makelabel: A >> user-definable command which gets its argument(s) from more basic levels of >> LaTeX, and is supposed to do something in a configurable way. ((In the >> future all such commands should be template keys, you say? Why, yes, it may >> well be. Template instances will often be defined with \ExplSyntaxOff, I >> think.)) Suppose further that one of these arguments is a boolean. ((Poor >> design? Well, such things will happen; it's an open system.)) Now, if said >> boolean is a Church boolean (effectively \use_i:nn or \use_ii:nn), then it >> can be used directly to select between two pieces of code, e.g. like >> >> \def\makesomething#1#2{% Assuming \ExplSyntaxOff >> % #1 is some text >> % #2 is the boolean >> #1% >> #2{ \thetheorem}{}% >> .\ % >> } > > What about \let \ifthenelse \bool_if:nTF ? That doesn't assume > anything about the internals, and allows precisely what you describe > (and is slightly more general, since the user can now use boolean > expressions). I'm not particularly fond of that. In particular, requiring the use of a command that does fancy expression parsing just for the sake of even using a boolean seems highly wasteful. >>> We could provide \bool_and:nn etc. (or some variation thereof). One >>> problem is where to stop: here you've used the three argument variant >>> \add:nnn, but we should then provide a four argument variant, etc. >> >> Even if you include everything up to the nine argument forms, you'll end up >> with fewer macros in total than for the alternative. ;-) > > True with the current code, I think, but my new code doesn't need two > separate branches, so that statement becomes false :). Then it _is_ > true that 18 cs is not that much. However, > > \bool_if:nTF > { > \bool_and:nnnnnnn % n? > \l_i_bool > \l_ii_bool > \l_iii_bool > \l_iv_bool > \l_v_bool > \l_vi_bool > \l_vii_bool > \l_viii_bool > } Provided that the booleans are really Church booleans, that \bool_if:nTF serves no purpose. > is not exactly obvious to update if a boolean is added. The&& version > is simple: add "&& \l_last_bool". Anyone writing expressions with that many clauses deserve a little difficulty in updating them; usually, it is a sign that one is making things far too complicated, and should rethink one's approach to the problem. :-) Lars Hellström % % \iffalse %<*driver> \documentclass{ltxdoc} \catcode\_=12 \begin{document} \DocInput{churchbool.dtx} \end{document} % % \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? % % \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 |\@[log in to unmask] % \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 } } } % % \end{macrocode} % \end{macro}\end{macro} % % \begin{macrocode} %<2e>\ExplSyntaxOff % \end{macrocode} % % % \section{Tests} % % \begin{macrocode} %<*tests> %<*2e> \documentclass{article} \begin{document} \ExplSyntaxOn % % \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} % % % \end{macrocode} % \endinput`