23

Given a token list such as \a\b\c or {ab}c, I define the first item to be what \@gobble would get as its argument (recall the definition \long\def\@gobble#1{}). It is not hard to devise a macro which extracts the first item from a token list, and, for instance, wraps it in eTeX's \unexpanded:

\begingroup
  \catcode`@=11
  \long\gdef\firstofmany#1{\@firstofmany#1\@marker}
  \long\gdef\@firstofmany#1#2\@marker{\unexpanded{#1}}
\endgroup
\message{"\firstofmany{\a\b\c}"} % => "\a "
\message{"\firstofmany{ { ab} c}"} % => " ab"

However, this macro fails if the token list contains the marker, which I chose to be \@marker. Is it possible to write a variant of this macro which would work for an arbitrary token list? (I don't care what token lists consisting only of spaces, which thus have no first item, produce.)

EDIT: I should have made it clearer that the solution is not to produce a less common delimiter. I would like a \firstofmany function which does not choke on any part of its own definition (and definitions of auxiliaries too, of course).

0

10 Answers 10

3

With the availability of the \expanded primitive a much faster alternative can be used, which is just as stable as the version provided by @BrunoLeFloch.

It also uses an unbalanced closing brace as the right delimiter, but since it uses the \expanded primitive, it doesn't have to make sure that a macro is always left of the input to be safe in an f-type expansion.

\begingroup
  \catcode`@=11
  \long\gdef\firstofmany#1%
    {%
      \expanded{\iffalse{\fi\firstofmany@aux#1{}}}%
    }
  \long\gdef\firstofmany@aux#1%
    {%
      \unexpanded{#1}%
      \expandafter\firstofmany@gobble\expandafter{\iffalse}\fi
    }
  \long\gdef\firstofmany@gobble#1{}
\endgroup

\long\def\test#1%
  {\message{|\unexpanded\expandafter{\romannumeral-`q#1}|}}

\test{\firstofmany{ a bc}}
\test{\firstofmany{ {a\a} bc}}
\test{\firstofmany{ {a\a} abc abc abc}}
\test{\firstofmany{ }}

\csname stop\endcsname
\csname bye\endcsname

To get the same behaviour as the code in Bruno's answer, one can put another \unexpanded around it like this:

\begingroup
  \catcode`@=11
  \long\gdef\firstofmany#1%
    {%
      \unexpanded\expanded{{\iffalse{\fi\firstofmany@aux#1{}}}}%
    }
  \long\gdef\firstofmany@aux#1%
    {%
      \unexpanded{#1}%
      \expandafter\firstofmany@gobble\expandafter{\iffalse}\fi
    }
  \long\gdef\firstofmany@gobble#1{}
\endgroup

\long\def\test#1%
  {\message{|\unexpanded\expandafter{\romannumeral-`q#1}|}}

\test{\firstofmany{ a bc}}
\test{\firstofmany{ {a\a} bc}}
\test{\firstofmany{ {a\a} abc abc abc}}
\test{\firstofmany{ }}

\csname stop\endcsname
\csname bye\endcsname
2
  • Nice indeed. We could use that I guess in LaTeX3's \tl_head:n when the primitive \expanded is available (I think we still support some older engines without \expanded support). I'll let you decide whether to open an issue about that. Aug 19, 2020 at 12:32
  • 2
    @BrunoLeFloch already part of my PR :) I'm doing a \cs_if_exist:NTF \tex_expanded:D and fallback to your code if it isn't.
    – Skillmon
    Aug 19, 2020 at 12:35
22

If you allow some pdftex primitives I think you can do this, which uses the entire input list as marker.

\begingroup
  \catcode`@=11
  \long\gdef\firstofmany#1{%
    \@fom{\unexpanded{[#1]}}#1{[#1]}}

  \long\gdef\@fom#1#2{%
   \unexpanded{#2}%
   \@gobbleto{#1}}

\gdef\@gobbleto#1#2{%
  \ifnum\pdfstrcmp{\unexpanded{#2}}{#1}=\z@
  \expandafter\@gobbletwo
  \else
  \fi
  \@gobbleto{#1}}

\gdef\@gobbletwo#1#2{}

\endgroup



\message{"\firstofmany{\a\b\c}"} % => "\a "
\message{"\firstofmany{ { ab} c}"} % => " ab"


\bye
6
  • In my use case (l3check for LaTeX3), \pdfstrcmp is available, so this works. I'll probably make that a bit faster by first removing stuff until a marker (in most cases, that's enough), then applying your technique. It would have been nice to get a pure TeX or eTeX solution, because the LuaTeX \pdf@strcmp (provided by Heiko) is 10x slower than pdfTeX's. Sep 3, 2012 at 1:23
  • @DavidCarlisle: Please is the \else in the solution playing any role?
    – Ahmed Musa
    Sep 3, 2012 at 4:06
  • 1
    @AhmedMusa The \else has no purpose here, you can omit it. Sep 3, 2012 at 5:02
  • 3
    @DavidCarlisle Nice trick. \@gobbleto and \@gobbletwo need \long to support \par inside the arbitrary token list. Sep 3, 2012 at 5:04
  • @AhmedMusa \else had the purpose of me not having finished designing the code by the time I started the \if :-) Sep 3, 2012 at 9:12
11

EDIT: Much much shorter. What was I thinking before? Or am I sleepy now? :-)

Strip the left brace using \string and \gobble, get the first item, put the brace back in.

\catcode`@=11
\def\@gobble#1{}

\def\firstofmany{\expandafter\expandafter\expandafter
                 \fom@getfirst\expandafter\@gobble\string}
\def\fom@getfirst#1{\unexpanded{#1}\fom@gobble}
\def\fom@gobble{\expandafter\expandafter\expandafter
                     \expandafter\expandafter\expandafter
                     \expandafter\@gobble\iftrue\expandafter{\else}\fi}

\message{"\firstofmany{\a\b\c}"}

\bye

Proper treatement of initial groups is missing here, though (they are found, but the braces are not written out).


I think I may have found a pure eTeX solution. I have attacked it with everything I could think of and it seems to work... except in the case of a blank list (error) and lists starting with space (space is ignored). But these were mentioned above as unimportant anyway.

I don't know about speed improvement, though --- I'm no expert, but the thing is quite complicated...

Before giving the code, a conceptual overview.

  1. The list is detokenized. (Thus, eTeX only.)

  2. In the detokenized version, the outer groups of braces are counted. (This part could be optimized by using the TeX's macro argument parsing mechanism. But at this stage, I was implementing for clarity, not speed.) The assumption is that { and } (and only these) have catcode 1 and 2, but this could be easily generalized, I believe.

    The number of outer groups is carried around as a list of *s of the appropriate length.

    Ok, this was the easy part :-)

  3. The idea is to dismantle the group using \string: the opening brace is stringified and then gobbled. The problem, however, is how to expand the \string and \gobble. Our *-based "counter" is in the way... (By the way, it seems to me completely impossible to pass the counter around (as part of argument lists) after the degrouped list, because we don't want to use a fixed delimiter.)

    Part of the solution is \let*\expandafter. We need to expand two macros after the *-counter, so we will walk through the stars twice, so 1/4 of them will remain. But when we "multiply" the counter by four, all is well. :-)

  4. After the group is dismantled, we have easy access to the first item. True, we need to be a bit careful with first items that are groups etc, but all in all, this part is more tedious that innovative.

  5. The only remaining part of magic is the gobbling. We alternate between gobbling the outer groups and the tokens between them. Since we know how many outer groups there are, we know when to stop, so we don't meet the now-lonely right brace (we eventually provide him a partner, of course).

    We gobble the tokens between outer groups using the \def\gobble...#{ trick (TeXbook p.204).

\catcode`@=11

\def\afterfi#1#2\fi{\fi#1}
% use \onefi etc after these
\def\afterfifi#1#2#3\fi#4\fi{#1#2}
\def\afterfififi#1#2#3\fi#4\fi#5\fi{#1#2}
\def\afterfifififi#1#2#3\fi#4\fi#5\fi#6\fi{#1#2}
\def\onefi{\fi}
\def\twofi{\fi\fi}
\def\threefi{\fi\fi\fi}
\def\fourfi{\fi\fi\fi\fi}
\def\gobble#1{}

\def\openingbrace{\iftrue{\else}\fi}
\def\closingbrace{\iffalse{\else}\fi}

% Detokenize (while preserving the original)
\long\def\firstofmany#1{%
  \expandafter\fom@countfirstlevelgroups\detokenize{#1}de{}{}{#1}%
}

\catcode`*=13  % we'll be counting stars
\def\if@zero\if#1#2/{%   % zero test
  \ifx#1/%
    \afterfi{\if@zero@yes}%
  \else
    \afterfi{\if@zero@no}%
  \fi
}
\def\if@zero@yes{\iftrue}
\def\if@zero@no/{\iffalse}

{\catcode`(=1 \catcode`)=2 (\catcode`{=12 \catcode`}=12

\xdef\detok@openingbrace({)%

% Count the number of outer brace pairs
%
% Note 1: This macro is very non-optimized... it should use TeX's macro
% argument parsing mechanism to search for { and }, and shouldn't use
% all these \afterfi-s, I used this approach just for clarity.
%
% Note 2: This macro expects precisely { and } to be of catcode 1 and 2.
% This could be fixed, but it's not worth the effort at this point.
%
% Args: #1#2 = detokenized, #3 = n, #4 = depth
% --> letters are safe delimiters, because \detokenize produces `other's
% We save the very first token for later (#5 below).
\gdef\fom@countfirstlevelgroups#1#2e#3#4(%  
  \fom@countfirstlevelgroups@#1#2e(#3)(#4)#1% 
)
\gdef\fom@countfirstlevelgroups@#1#2e#3#4#5(% 
  \ifx#1d% end of detokenized string
    \afterfifififi(\onefi)(\fom@removeopeningbrace#5(#3))%
  \else
    \ifx#1{% { found ==> increase depth
      \if@zero\if#4//% { found at zero depth ==> increase n 
        \afterfifififi(\threefi)(\fom@countfirstlevelgroups@#2e(#3*)(#4*)#5)%
      \else
        \afterfifififi(\threefi)(\fom@countfirstlevelgroups@#2e(#3)(#4*)#5)%
      \fi
    \else
      \ifx#1}% } found => decrease depth
        \afterfififi(\threefi)(\fom@cflg@decreasedepth#2e(#3)[#4]#5)%
      \else % neither { not } found ==> go to next char
        \afterfififi(\threefi)(\fom@countfirstlevelgroups@#2e(#3)(#4)#5)%
      \fi
    \fi
  \fi
)
\gdef\fom@cflg@decreasedepth#1e#2[#3#4]#5(%
  \fom@countfirstlevelgroups@#1e(#2)(#4)#5)

)}  % back to normal braces

% Remove the initial brace.
% *s are quadrapled to expand first \string (followed by }, we know)
% and \gobble, thus destroying the group; we will be left with the
% original number of *s
\let*\expandafter
\def\fom@removeopeningbrace#1#2{% #2=***** (n), #1=the first *token*
  \expandafter\expandafter\expandafter\fom@adddummy
  \expandafter\expandafter\expandafter#1%
  #2#2#2#2\expandafter\expandafter\expandafter e%
  \expandafter\gobble\string
}

% Insert a dummy group (and a *) after the first item. We will
% start gobbling by gobbling to a group and this would fail if there
% were none.  This needs to be done before checking for group below,
% so that we have enough *s.
\long\def\fom@adddummy#1#2e#3{%
  \fom@checkforgroup#1#2*e{#3}{}%
}

% Group as the first item requires special attention.  (Note: space
% would need it as well, but space never get here anyway: it
% dissapears when \fom@countfirstlevelgroups is expanded.)
% #1 = the first token of the detokenized first item (will be now
% finally discarded)
% #2#3 = *s (if we will find an opening brace, one * will be removed)
\def\fom@checkforgroup#1#2#3e{%
  \if\detok@openingbrace#1%
    \afterfi{\fom@havegroup#3e}%
  \else
    \afterfi{\fom@getfirstitem#2#3e}%
  \fi
}
% Put extra braces around the first item which is a group.
\long\def\fom@havegroup#1e#2{\fom@getfirstitem#1e{{#2}}}

% Get the first item, then call the gobblers: insert two markers
% instead of one, the gobblers need them.
\long\def\fom@getfirstitem#1e#2{%
  \unexpanded{#2}%
  \fom@gobbletogroup#1*ef{}%
}

% Gobble: we know how many groups we have (as many as *s), so we
% can gobble by alternating \fom@gobbletogroup...#3#{...}
% and \fom@gobblegroup...#3{...}
% #1#2=*s, #3=toks before group; but first check if there are any
% *s left!
\def\fom@gobbletogroup#1#2f{%
  \ifx#1e%
    \afterfi\fom@finish
  \else
    \afterfi{\fom@gobbletogroup@#1#2f}%
  \fi
}
\long\def\fom@gobbletogroup@#1#2f#3#{%
  \fom@gobblegroup#1#2f%
}

% #1#2=*s, #3=the group
\def\fom@gobblegroup#1#2f{%
  \ifx#1e%
    \afterfi\fom@finish
  \else
    \afterfi{\fom@gobblegroup@#1#2f}%
  \fi
}
\long\def\fom@gobblegroup@#1#2f#3{%
  \fom@gobbletogroup#2f%
}

\def\fom@finish{%
  \iftrue\expandafter\fom@finish@\expandafter{\else}\fi
}
\long\def\fom@finish@#1{}

% TEST:
\message{"\firstofmany{#1\fom@gobblegroup{\par #1  # @@@ef

aa}a**aa{first} l{ine{%
\fom@gobblegroup\fi\fi
}s}econd line} efef "}

\bye
7
  • Drat, I was just beginning to dream up a similar approach :-)
    – Joseph Wright
    Sep 3, 2012 at 19:40
  • The long one or the short one? :-) Sep 3, 2012 at 19:52
  • 1
    The short one :-) Next step: get the team to use this for LaTeX3 (\tl_head:n).
    – Joseph Wright
    Sep 3, 2012 at 19:55
  • 1
    It can actually be made a bit more efficient, by starting with \long\def\firstofmany#1{\expandafter\fom@getfirst\iffalse{\fi#1{}}} and dropping some \expandafters in \fom@gobble (you only need three at the start).
    – Joseph Wright
    Sep 3, 2012 at 20:05
  • Cool! And the change in \firstofmany also deals with the empty list! Sep 3, 2012 at 20:17
9

I understand I am rather late to the party, but I would like to make a somewhat shorter suggestion than the currently extant ones. Idea: Contrive to put braces around the tail end of the list and then just \@gobble the whole thing. It fully expands to the first item, but there is an extraneous \iffalse{\fi at the beginning. Of course, there is no notion in TeX of expanding "partway", so I'm not sure whether this is an issue in practice. In any case, since it is at the beginning it can be excised in various ways :)

\documentclass{article}
\makeatletter
\def\firstofmany#1{\iffalse{\fi%
 \@firstofmany#1}%
}
\def\@firstofmany#1{%
    \unexpanded{#1}\expandafter\@gobble\expandafter{\iffalse}\fi
}
%\def\@gobble#1{}

\def\dotest#1{\edef\@dotest{\firstofmany{#1}}\meaning\@dotest.}
\makeatother
\begin{document}
\tt
\dotest{abcde}

\dotest{{ab}cde}

\dotest{ { ab}cde}

\dotest{\a\b\c}
\end{document}

enter image description here

4
  • This is similar in spirit to @SašoŽivanović's "short" solution. It indeed follows all the requirements I set, but the common drawback with Sašo's approach is that this \firstofmany cannot be expanded correctly in an expansion context, it can only work in an \edef or similar. Sep 4, 2012 at 21:51
  • @Bruno: You're right, I didn't understand the "short" solution until after posting, so I missed the similarity. Your objection wrt "f-expandability" means that attempting to "expand completely" this macro just by iterating expansion of the first token will stabilize after a while, but the stable output will not be the same as the actual full expansion because of stuff after the \unexpanded{#1}?
    – Ryan Reich
    Sep 4, 2012 at 22:30
  • There are four types of expandabilities. (1) expandable primitives expand completely to their result when hit with one \expandafter, thus you can get the result and feed it to another function with \expandafter\function\expandafter{\someprimitive...}. (2) the best a macro can do is to expand in two steps, for instance \def\eval#1{\the\numexpr#1\relax}; then it is still possible to get the result and use it as a macro argument (just replace each \expandafter by three). Sep 4, 2012 at 22:41
  • (f) the macro takes an unknown number of steps, e.g. \def\reverse#1{\rev#1.\rev\rev\revend.}\def\rev#1#2\rev#3#4.{#3#2\rev#3#4.#1}\def\revend#1..{} reverses a list of letters with a variable number of expansions. You can still access the result with \expandafter\function\expandafter{\romannumeral-'q\reverse{abcd}}. (replace ' with a backtick.) but it's harder. (x) Finally, a macro might only be safe within an \edef, \xdef, \message and similar non-expandable functions: for instance \def\foo#1{\iffalse{\fi #1\iffalse}\fi}. Then it is impossible to access the result expandably. Sep 4, 2012 at 22:52
7

A delimiter seems to be necessary, as you don't know how many items you have to discard. A way out might be to insert a delimiter which is very unlikely to appear in a real world document:

\begingroup
  \catcode`@=11
  \edef\funny{\detokenize{&${}$&}}
  \long\xdef\firstofmany#1{\noexpand\@firstofmany#1\funny}
  \edef\x{\long\gdef\noexpand\@firstofmany##1##2\funny}\x{\unexpanded{#1}}
\endgroup
\message{"\firstofmany{\a\b\c}"} % => "\a "
\message{"\firstofmany{ { ab} c}"} % => " ab"

Just make \funny as complicated as you can. The empty token list or a list consisting only of spaces would give an error, I'm afraid.

5
  • Why so much fuss on \@marker and not on \@firstofmany? What makes the clash so outstandingly bad? Sep 3, 2012 at 0:17
  • @StephanLehmke Nothing bad; but a real world token list might contain them.
    – egreg
    Sep 3, 2012 at 0:21
  • 3
    One of the main disadvantages of assuming there is a safe token that can be used as the marker is that you can not manipulate code using the marker Sep 3, 2012 at 0:22
  • @DavidCarlisle Ah, so it's a problem of self-reference. I begin to understand... Sep 3, 2012 at 0:35
  • @DavidCarlisle Precisely. I should have made that aspect clearer. The goal is to implement some checking tool for LaTeX3 code. In particular the tool shouldn't choke on its own source, so using a fixed delimiter is not good. Sep 3, 2012 at 1:16
7

EDIT (2022): This question (and answers) should really be thought of as historical: by now there is a well established function \tl_head:n in expl3 with all the expected properties.

Unless we build a delimiter that is specifically tailored to the input, as in David Carlisle's approach (he uses the token list itself as a delimiter since it is too long to appear within itself), the only safe delimiter is an end-group character token (normally } with TeX's usual catcodes), because unmatched explicit end-group tokens cannot appear in the list of tokens given to \firstofmany. This trailing } can be inserted by expanding \iffalse {\fi #1} from the left, as noted in a couple of answers.

The hard part comes about when trying to insert the corresponding left brace to remove trailing tokens. Several answers simply insert \expandafter\@gobble{\iffalse }\fi after the first item. This has the large drawback that the whole result is not obtained when hitting the \firstofmany function with some \expandafter chains on the left, which means in particular that its result can only be used directly within an \edef or similar expansion, and that it cannot be expanded to be given to another expandable function directly.

My approach is to remove all tokens (except the first item) until a given (mostly arbitrary) marker, then test if the full token list with that part removed only consists in the first item. If it does, then we are done, the token list has only one item, and we leave that as a result. Otherwise, we repeat: keep the first item, remove everything else until the marker, check if what remains is a single item.

It turns out I want blank token lists to give an empty result, which is equivalent to asking for the first item in #1{}. If the argument of \fom@test consists in (optional) spaces, followed by an item, then that is left in the input stream, to be taken as the argument to \unexpanded (it turns out that the item always ends up braced). Otherwise, we call \fom@grab to remove until abc (we know that this marker is present because the initial argument of \fom@test ends with abc), which then calls \fom@test again. The key thing to note is that the leading item is always kept after our functions in the input stream, which means that expanding from the left ("f-expanding") works correctly.

\begingroup
  \catcode`@=11
  \long\gdef\firstofmany#1{\unexpanded
    \iffalse{\fi \fom@grab #1{}abc}}
  \long\gdef\fom@test#1{%
    \ifcat$\detokenize\expandafter{\fom@gobble#1}$%
      \expandafter\fom@i
    \else
      \expandafter\fom@ii
    \fi
    {#1}% #1 is {first item}
    {\iffalse{\fi \fom@grab #1}}%
  }
  \long\gdef\fom@grab#1#2abc%
    {\expandafter\fom@test\expandafter{\iffalse}\fi{#1}}
  \long\gdef\fom@gobble#1{}
  \long\gdef\fom@i#1#2{#1}
  \long\gdef\fom@ii#1#2{#2}
\endgroup

\long\def\test#1%
  {\message{|\unexpanded\expandafter{\romannumeral-`q#1}|}}

\test{\firstofmany{ a bc}}
\test{\firstofmany{ {a\a} bc}}
\test{\firstofmany{ {a\a} abc abc abc}}
\test{\firstofmany{ }}

\csname stop\endcsname
\csname bye\endcsname
\endinput

As an added bonus, this function only requires two steps of expansion to yield its result (similar to many of Heiko Oberdiek's beautiful macros). It is a little bit slower than the naive approach that forbids a specific marker from appearing in the token list.

As Sašo Živanović made me realize, this solution also avoids a common issue: many definitions of \firstofmany fail in the case \halign{#\cr a\firstofmany{b&}\cr}. I got lucky: since the user's token list only appears within braces (sometimes \iffalse{\fi), TeX's alignment mechanism doesn't see it.

Ulrich Diez suggests the following variant which avoids using \iffalse{\fi...} constructions hence is probably easier to understand.

\begingroup
  \catcode`@=11
  \long\gdef\firstofmany#1{\unexpanded\expandafter\fom@test\expandafter{\fom@grab #1{}abc}}
  \long\gdef\fom@test#1{%
    \ifcat$\detokenize\expandafter{\fom@gobble#1}$%
      \expandafter\fom@i
    \else
      \expandafter\fom@ii
    \fi
    {#1}%  #1 is the first item wrapped in braces and after \unexpanded-driven
        %  expansion it forms <left brace>, <balanced text> and <right brace>
        %  of \unexpanded's <general text>.
    {\expandafter\fom@test\expandafter{\fom@grab #1}}%
  }
  \long\gdef\fom@grab#1#2abc{{#1}}
  \long\gdef\fom@gobble#1{}
  \long\gdef\fom@i#1#2{#1}
  \long\gdef\fom@ii#1#2{#2}
\endgroup
8
  • Ingenious! Could you please explain what's wrong with &? Sep 5, 2012 at 12:07
  • @SašoŽivanović Let's work with \long\def\firstofmany#1{\fom#1{}\fom}\long\def\fom#1#2\fom{#1}. Then \halign{#\cr \firstofmany{a...&...}\cr} works fine, but \halign{#\cr a... \firstofmany{b...&...} \cr} fails with a "forbidden \endtemplate". Why? Within a tabular, any & starts a new cell when scanned, unless it appears within braces. In the argument of \firstofmany, & is within braces, thus no cell is built. But for \fom, the & is not protected, TeX builds a cell by inserting \endtemplate, which is \outer: \fom can't see through that. Sep 5, 2012 at 13:27
  • In the first case, \fom gets expanded before the preamble of the cell is inserted: in that mode, TeX doesn't care about &. The details are messy: in a cell, TeX first fully expands tokens (except protected macros) until finding a non-blank token: in that phase, & are ignored. In fact, thinking about it again, the code I gave here should work without trouble, because any potential & always appear within braces (\iffalse {\fi...\iffalse}\fi counts). Sep 5, 2012 at 13:54
  • I also believe your solution is unproblematic, or at least I can't get the "forbidden \endtemplate" error you describe above. I have also tested how \fom behaves when & is the first item, also ok... Sep 5, 2012 at 14:23
  • @SašoŽivanović Thanks. I'll update my answer accordingly. Sep 5, 2012 at 14:58
3
\documentclass[12pt]{article}

\begingroup
\catcode`@=11 \lccode`\&=0 \catcode`&=8
\lowercase{\endgroup
  \long\gdef\firstofmany#1{\@firstofmany#1&&}
  \long\gdef\@firstofmany#1#2&&{\unexpanded{#1}}
}

\begingroup
\lccode`\&=0 \catcode`&=7
\message{"\firstofmany{\a\b&\c}"} % => "\a "
\message{"\firstofmany{ { ab} c}"} % => " ab"
\endgroup

\begin{document}
x
\end{document}
1
  • This is not robust enough for my needs: you are only changing the delimiter to something less likely. In fact, since my application is to implement some checking tool for TeX (well, probably only well-behaved LaTeX3) code, it should in particular be able to check its own definition, which contains the marker. Sep 3, 2012 at 1:14
2

Regarding the (asymptotic) time complexity. For theoretical interest only, because of huge constant factor.


First, a review of the existing answers. Skip this section if you already know.

  • Answer by Skillmon

    (this is the approach used in expl3 if \expanded is available.)

    • Key point: expand \expanded{\unexpanded{ ⟨the head⟩ } \expandafter } ⟨something that expand once to a "{"⟩ to allow removing the tail, or something like that I think.
    • Time complexity: linear in (number of tokens in the whole token list).
    • Requires \expanded.
  • Answer by Sašo Živanović, first approach // answer by Ryan Reich

    • Key point: same as Skillmon's answer, but does not use \expanded, so...
    • Issue: only works in x-expansion context, not f-expansion context.
    • Time complexity: linear in (number of tokens in the whole token list).
  • Answer by Bruno Le Floch // answer by Ulrich Diez.

    (this is the approach used in expl3 if \expanded is not available.)

    • Key point: already explained there.
    • Time complexity: (number of tokens in the whole token list) × (number of occurrences of the delimiter).
  • Answer by Sašo Živanović, second approach

    • Key point: (roughly speaking) count the number of braced groups, then remove exactly that many.
    • Time complexity: (number of tokens in the head) × (number of items in the whole list) -- if I computed correctly.
    • Issue: assumes that all { and } in the detokenized list are explicit braces and nothing else are.
  • Answer by David Carlisle

    • Key point: use the detokenized original token list as the input marker; when it's seen as the item after the head we know that the tail is over.
    • Time complexity: (detokenized length of the whole token list) × (number of items of the whole token list).

Answers that is not completely general or does not handle multiple-token ⟨head⟩ are not considered.


I'll post 2 approaches. Each is (asymptotically, worst case) better than all of the existing solutions that doesn't use \expanded, for some range of parameter values.

Currently there's no implementation, but the idea should work, and I am relatively sure that the (asymptotic) time complexity is computed correctly.

Approach 1

Time complexity: (number of tokens in the head) × (number of occurrences of the delimiter) + (number of tokens in the whole token list) × log(number of occurrences of the delimiter).

The idea is to count the number of delimiters first, then apply Bruno's approach.

(if you use unary and nested \romannumeral, you don't have to deal with the fact that the number representation of a number X has log(X) digits so takes that long to copy around.)

Counting the number of delimiters (we call this A) is easy as long as we know of some other delimiter B that does not appear in the token list.

However this is a circular problem, since we don't have any token known to be not in the token list yet. Instead:

Assume that there are N A delimiters, and we know some number X ≥ N, we can count the exact number of delimiters A in time (number of tokens in the whole token list) + X by

  • appending X A tokens to the end of the token list (take linear time)
  • remove X leading items delimited by A (take linear time. this part can be implemented)
  • then count the number of remaining items. This can be done in linear time using the simple algorithm, and B is known to not appear here.

We can repeatedly double X each time, so it only takes log(number of occurrences of A) iterations until there's some working value of X, and such a value is linear in (number of occurrences of A).

Remark, we can check if we hit a "wrong B" or not similar to Bruno's answer -- add a brace, grab the rest, check if it's empty -- which also takes linear time. Overall testing each value of X takes (number of tokens in the whole token list) time.

After knowing

Approach 2

Time complexity: (number of tokens in the head)2 × log(number of tokens in the head) + (number of tokens in the whole token list). (probably.)

The idea is

  • insert a \expandafter between each token of the head
  • put \expandafter ⟨braced head with \expandafter inserted between each token⟩ \expandafter { \iffalse } \fi in the input stream before the ⟨tail⟩ }.
  • expand once.
  • now we have ⟨braced head⟩ { ⟨tail⟩ }, it's easy to remove the tail.

In order to preserve the char code of { and } tokens, it's necessary to


(side note, I also think about using a \notexpanded: ⟨some outer token⟩ as the delimiter; but I can't find out some way to put this after the whole token list)

0

Joseph Wright

Regarding using \romannumeral, since #1 can be only one token, what of this?

\def\@firstofmany#1{%
  \expandafter\expandafter\expandafter\stopromans
  \expandafter\expandafter\expandafter\unexpanded
  \expandafter\expandafter\expandafter
  {\expandafter\expandafter\expandafter#1\expandafter\expandafter
  \expandafter}\expandafter\@gobble\expandafter{\iffalse}\fi
} 

Note: from Ryan's solution.

7
  • I do love that trick :) I actually had to read source2e.pdf to see how they implemented tabular in order to learn it.
    – Ryan Reich
    Sep 4, 2012 at 18:50
  • #1 could be braced in the input, so more than one token :-(
    – Joseph Wright
    Sep 4, 2012 at 18:59
  • re:@Joseph The terminology is perhaps confusing. A "token list" is not actually a list of actual tokens, but rather a list of "macro tokens": blobs that would be absorbed as a single argument to a macro.
    – Ryan Reich
    Sep 4, 2012 at 19:29
  • @RyanReich { is a perfectly fine token, and {\ab #} d contains 6 tokens, including two braces, one macro parameter character, and one space. There are two ways to see a token list: as a list of TeX tokens, or as a list of items, and the above list would have two of those: \ab # and d, ignoring spaces between items, and removing surrounding braces. In the case of \tl_head:n, or as I called it here \firstofmany, we are interested in getting the first item, because the first token may not be a balanced text. Sep 4, 2012 at 21:56
  • @Ahmed, unfortunately, no, I am considering arbitrary lists of tokens (arbitrary parameterless macros), so #1 can be any number of tokens. Do you know how I could make this clearer in my question? Sep 4, 2012 at 21:58
0

Here is a variant of the code of Bruno Le Floch which does without brace-hacking:

The result is delivered by triggering two expansion-steps on \firstofmany:

\begingroup
  \catcode`@=11
  \long\gdef\firstofmany#1{\unexpanded\expandafter\fom@test\expandafter{\fom@grab #1{}abc}}
  \long\gdef\fom@test#1{%
    \ifcat$\detokenize\expandafter{\fom@gobble#1}$%
      \expandafter\fom@i
    \else
      \expandafter\fom@ii
    \fi
    {#1}%  #1 is first item wrapped in braces and after \unexpanded-driven 
        %  expansion forms <left brace>, <balanced text> and <right brace> 
        %  of \unexpanded's <general text>
    {\expandafter\fom@test\expandafter{\fom@grab #1}}%
  }
  \long\gdef\fom@grab#1#2abc{{#1}}
  \long\gdef\fom@gobble#1{}
  \long\gdef\fom@i#1#2{#1}
  \long\gdef\fom@ii#1#2{#2}
\endgroup

\long\def\test#1%
   {\message{|\unexpanded\expandafter\expandafter\expandafter{#1}|}}

\test{\firstofmany{ a bc}}
\test{\firstofmany{ {a\a} bc}}
\test{\firstofmany{ {a\a} abc abc abc}}
\test{\firstofmany{ }}
\test{\firstofmany{ { }Where is the space gone?}} 

\csname stop\endcsname
\csname bye\endcsname
\endinput

Here is another variant—as delimiter instead of abc a frozen-\relax is used (frozen-\relax neither can be affected by \uppercase/\lowercase nor can be (re)defined in terms of \outer) and expansion is driven by \romannumeral instead of \unexpanded's expansion while scanning for the ⟨left brace⟩ of \unexpanded's ⟨general text⟩.

As the loop is driven by \romannumeral-expansion, you obtain the result by triggering two expansion-steps.

You can, e.g., do

\unexpanded\expandafter\expandafter\expandafter{\ExtractFirstArg{{first}more stuff}}

for obtaining something like \unexpanded{first}.



As with the code of Bruno Le Floch the gist of the mechanism is:

Append a sequence {}⟨Delimiter⟩ to the argument passed by the user, then recursively apply a "removal-macro" with parameter text #1#2⟨Delimiter⟩ which delivers {#1} until only a single non-delimited argument is left.
(In the example below, the removal-macro is called \UD@RemoveTillFrozenrelax and the ⟨Delimiter⟩ is a frozen-\relax.)

{} before ⟨Delimiter⟩ for ensuring that the removal-macro finds a non-delimited argument even in case of the argument passed by the user being empty or blank (blank = consisting of explicit space tokens only). )


If the user passes, e.g., the sequence

{1}{2}{3}, then after appending you have the sequence
{1}{2}{3}{}⟨Delimiter⟩.

Applying the removal-macro with its first non-delimited and its second delimited argument yields that the removal macro's first argument will be 1 and the removal-macro's second argument will be {2}{3}{}. When the removal-macro delivers its first argument wrapped in curly braces, you have the sequence {1} - the condition of there being only a single non-delimited argument is now fulfilled.


If the user passes, e.g., the sequence

{1}{2}{3}⟨Delimiter⟩{4}, then after appending you have the sequence
{1}{2}{3}⟨Delimiter⟩{4}{}⟨Delimiter⟩.

Applying the removal-macro with its first non-delimited and its second delimited argument yields that the removal-macro's first argument will be 1 and the removal-macro's second argument will be {2}{3}. When the removal-macro delivers its first argument wrapped in curly braces, you have the sequence {1}{4}{}⟨Delimiter⟩ - the condition of there being only a single non-delimited argument is not fulfilled yet, thus do another iteration with the removal-macro:
Applying the removal-macro with its first non-delimited and its second delimited argument yields that the removal-macro's first argument will be 1 and the removal-macro's second argument will be {4}{}. When the removal-macro delivers its first argument wrapped in curly braces, you have the sequence {1} - the condition of there being only a single non-delimited argument is now fulfilled.


If the user passes an empty argument, then after appending you have the sequence
{}⟨Delimiter⟩.

Applying the removal-macro with its first non-delimited and its second delimited argument yields that {} will be taken for the removal-macro's first argument and therefore the removal-macro's first argument will be empty. The removal-macro's second argument will be empty, too, because there are no other tokens before ⟨Delimiter⟩. When the removal-macro delivers its first argument wrapped in curly braces, you have the sequence {} - the condition of there being only a single non-delimited argument is now fulfilled.


As this mechanism is based on macros it cannot be applied for accessing the first item of a token-list that contains tokens defined in terms of \outer.

This mechanism extracts single/unbalanced \if/\else/\fi in case such things form the first item of the token-list in question.

Every user-provided argument is wrapped between curly braces while the expansion-cascade is running, thus this mechanism should also work out when extracting & and the like inside alignments/tabular-environments etc.

Using this mechanism, you cannot distinguish by "looking" at the result of \ExtractFirstArg the case of the argument passed by the user being empty or blank (blank = consisting of explicit space-tokens only) from the case of the argument passed by the user having a first component which is an empty argument.

I.e., the results of \ExtractFirstArg{} and \ExtractFirstArg{ } will be the same as the result of, e.g., \ExtractFirstArg{{}More stuff}: In all these cases \ExtractFirstArg will not return any token at all.

But you can easily distinguish these cases by checking the emptiness/blankness of the argument passed by the user before applying \ExtractFirstArg to it.

For checking the emptiness of an argument you can, e.g., use the \UD@CheckWhetherNull-macro of the example below.

For checking the "emptiness or blankness" of an argument you can, e.g., use the same macro when doing something which takes into account that TeX discards space-tokens that precede non-delimited arguments—just do something like:

\expandafter\UD@CheckWhetherNull\expandafter{\@firstoftwo#1{}.}%
{<#1 is empty or blank (blank = consists only of explicit space-tokens).>}%
{<#1 is not empty and not blank (but consists of something else than only explicit space-tokens).>}%

For checking the "blankness" put the pieces together:

\UD@CheckWhetherNull{#1}{%
  <#1 is not blank (but empty).>
}{%
   \expandafter\UD@CheckWhetherNull\expandafter{\@firstoftwo#1{}.}%
   {<#1 is blank (blank = consists only of explicit space-tokens).>}%
   {<#1 is not blank and not empty (and consists of something else than only explicit space-tokens).>}%
}%


\makeatletter
%%=============================================================================
%% Paraphernalia:
%%    \UD@firstoftwo, \UD@secondoftwo, \UD@Exchange, \UD@PassFirstToSecond,
%%    \UD@stopromannumeral, \UD@CheckWhetherNull, \UD@ExtractFirstArg,
%%    \UD@TrimLeadingTokens, \UD@TrimTrailingTokens
%%=============================================================================
\newcommand\UD@firstoftwo[2]{#1}%
\newcommand\UD@secondoftwo[2]{#2}%
\newcommand\UD@Exchange[2]{#2#1}%
\newcommand\UD@PassFirstToSecond[2]{#2{#1}}%
\@ifdefinable\UD@stopromannumeral{\chardef\UD@stopromannumeral=`\^^00}%
%%-----------------------------------------------------------------------------
%% Check whether argument is empty:
%%.............................................................................
%% \UD@CheckWhetherNull{<Argument which is to be checked>}%
%%                     {<Tokens to be delivered in case that argument
%%                       which is to be checked is empty>}%
%%                     {<Tokens to be delivered in case that argument
%%                       which is to be checked is not empty>}%
%%
%% The gist of this macro comes from Robert R. Schneck's \ifempty-macro:
%% <https://groups.google.com/forum/#!original/comp.text.tex/kuOEIQIrElc/lUg37FmhA74J>
\newcommand\UD@CheckWhetherNull[1]{%
  \romannumeral\expandafter\UD@secondoftwo\string{\expandafter
  \UD@secondoftwo\expandafter{\expandafter{\string#1}\expandafter
  \UD@secondoftwo\string}\expandafter\UD@firstoftwo\expandafter{\expandafter
  \UD@secondoftwo\string}\expandafter\UD@stopromannumeral\UD@secondoftwo}{%
  \expandafter\UD@stopromannumeral\UD@firstoftwo}%
}%
%%-----------------------------------------------------------------------------
%% Extract first inner undelimited argument:
%%
%%   \ExtractFirstArg{ABCDE} yields  {A}
%%
%%   \ExtractFirstArg{{AB}CDE} yields  {AB}
%%
%% Due to \romannumeral-expansion the result is delivered after two 
%% expansion-steps/after "hitting" \ExtractFirstArg with \expandafter
%% twice.
%%
%% \ExtractFirstArg's argument must not be blank.
%%
%% Use frozen-\relax as delimiter for speeding things up.
%% I chose frozen-\relax because David Carlisle pointed out in
%% <https://tex.stackexchange.com/a/578877>
%% that frozen-\relax cannot be (re)defined in terms of \outer and cannot be
%% affected by \uppercase/\lowercase.
%%
%% \ExtractFirstArg's argument may contain frozen-\relax:
%% The only effect is that internally more iterations are needed for
%% obtaining the result.
%%
%%.............................................................................
\@ifdefinable\UD@RemoveTillFrozenrelax{%
  \expandafter\expandafter\expandafter\UD@Exchange
  \expandafter\expandafter\expandafter{%
  \expandafter\expandafter\ifnum0=0\fi}%
  {\long\def\UD@RemoveTillFrozenrelax#1#2}{{#1}}%
}%
\expandafter\UD@PassFirstToSecond\expandafter{%
  \romannumeral\expandafter
  \UD@PassFirstToSecond\expandafter{\romannumeral
    \expandafter\expandafter\expandafter\UD@Exchange
    \expandafter\expandafter\expandafter{%
    \expandafter\expandafter\ifnum0=0\fi}{\UD@stopromannumeral#1{}}%
  }{%
    \UD@stopromannumeral\romannumeral\UD@ExtractFirstArgLoop
  }%
}{%
  \newcommand\ExtractFirstArg[1]%
}%
\newcommand\UD@ExtractFirstArgLoop[1]{%
  \expandafter\UD@CheckWhetherNull\expandafter{\UD@firstoftwo{}#1}%
  {\expandafter\UD@firstoftwo\expandafter{\expandafter\UD@stopromannumeral\UD@secondoftwo{}#1}{}}%
  {\expandafter\UD@ExtractFirstArgLoop\expandafter{\UD@RemoveTillFrozenrelax#1}}%
}%
\makeatother

\documentclass{article}

\parindent=0ex
\parskip=.5\baselineskip
\topsep=0ex
\partopsep=0ex
\pagestyle{empty}

\makeatletter
% A loop for replacing \FOO by frozen-\relax:
\@ifdefinable\ReplaceFOOByFrozenRelax{%
  \long\def\ReplaceFOOByFrozenRelax#1#{%
    \romannumeral\@ReplaceFOOByFrozenRelax{#1}%
  }%
}%
\newcommand\@ReplaceFOOByFrozenRelax[2]{%
  \ReplaceFOOByFrozenRelaxLoop{#2}{#1}%
}%
\newcommand\ReplaceFOOByFrozenRelaxLoop[2]{%
  \expandafter\UD@CheckWhetherNull\expandafter{\UD@gobbletoFOO#1\FOO}{%
    \UD@stopromannumeral#2{#1}%
  }{%
    \expandafter\expandafter\expandafter\ReplaceFOOByFrozenRelaxLoop
    \expandafter\expandafter\expandafter{%
       \expandafter\UD@firstoftwo\expandafter{\expandafter}\UD@replaceFOO{{}}#1%
    }{#2}%
  }%
}%
\@ifdefinable\UD@gobbletoFOO{\long\def\UD@gobbletoFOO#1\FOO{}}%
\begingroup
\def\UD@replaceFOO#1{%
  \endgroup
  \@ifdefinable\UD@replaceFOO{\long\def\UD@replaceFOO##1\FOO{##1#1}}%
}%
\expandafter\expandafter\expandafter\UD@replaceFOO
\expandafter\expandafter\expandafter{%
\expandafter\expandafter\ifnum0=0\fi}%
\makeatother

\begin{document}

\enlargethispage{2in}%
\null\kern-1.5in

Test 1: \verb|\ExtractFirstArg{ABCDE}|
yields:
\ExtractFirstArg{ABCDE}

Test 2: \verb|\ExtractFirstArg{{AB}CDE}|
yields:
\ExtractFirstArg{{AB}CDE}

The argument can contain frozen-\verb|\relax| although it is used as delimiter in some place,
this just increases the amount of iterations:

Test 3: 
\begin{verbatim}
\ReplaceFOOByFrozenRelax\ExtractFirstArg{AB\FOO C\FOO DE}
\end{verbatim}
yields:
\ReplaceFOOByFrozenRelax\ExtractFirstArg{AB\FOO C\FOO DE}

Test 4: 
\begin{verbatim}
\ReplaceFOOByFrozenRelax\ExtractFirstArg{{AB}\FOO C\FOO DE}
\end{verbatim}
yields:
\ReplaceFOOByFrozenRelax\ExtractFirstArg{{AB}\FOO C\FOO DE}

The result is delivered by triggering two expansion-steps:

Test 5: 
\begin{verbatim}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\temp
\expandafter\expandafter\expandafter{%
  \ExtractFirstArg{ABCDE}%
}
\end{verbatim}
yields:
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\temp
\expandafter\expandafter\expandafter{%
  \ExtractFirstArg{ABCDE}%
}
\texttt{\string\temp: \meaning\temp}%

Test 6:
\begin{verbatim}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\temp
\expandafter\expandafter\expandafter{%
  \ExtractFirstArg{{AB}CDE}%
}
\end{verbatim}
yields:
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\temp
\expandafter\expandafter\expandafter{%
  \ExtractFirstArg{{AB}CDE}%
}
\texttt{\string\temp: \meaning\temp}%

\makeatletter
Test 7:
\begin{verbatim}
\expandafter\def\expandafter\temp\expandafter{\romannumeral
  \ReplaceFOOByFrozenRelax\expandafter\expandafter\expandafter\UD@stopromannumeral
  \ExtractFirstArg{{AB}C\FOO D\FOO E}%
}
\end{verbatim}
yields:
\expandafter\def\expandafter\temp\expandafter{\romannumeral
  \ReplaceFOOByFrozenRelax\expandafter\expandafter\expandafter\UD@stopromannumeral
  \ExtractFirstArg{{AB}C\FOO D\FOO E}%
}
\texttt{\string\temp: \meaning\temp}%

Test 8:
\begin{verbatim}
\expandafter\def\expandafter\temp\expandafter{\romannumeral
  \ReplaceFOOByFrozenRelax\expandafter\expandafter\expandafter\UD@stopromannumeral
  \ExtractFirstArg{\FOO{AB}C\FOO D\FOO E}%
}
\end{verbatim}
yields:
\expandafter\def\expandafter\temp\expandafter{\romannumeral
  \ReplaceFOOByFrozenRelax\expandafter\expandafter\expandafter\UD@stopromannumeral
  \ExtractFirstArg{\FOO{AB}C\FOO D\FOO E}%
}
\texttt{\string\temp: \meaning\temp}%
\makeatother

Test 9:
\begin{verbatim}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\temp
\expandafter\expandafter\expandafter{%
  \ExtractFirstArg{}%
}
\end{verbatim}
yields:
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\temp
\expandafter\expandafter\expandafter{%
  \ExtractFirstArg{}%
}
\texttt{\string\temp: \meaning\temp}%

\end{document}

enter image description here

1
  • This seems like essentially the same approach as my answer: deal with the possibility that the user's token list contains the delimiter by repeatedly discarding tokens until that delimiter in a loop, until there is nothing left. It's the approach implemented in LaTeX3's \tl_head:n. Aug 19, 2020 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.