# Fully robust way to access the first item in a token list (expandably)

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).

-

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

-
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. – Bruno Le Floch Sep 3 '12 at 1:23
@DavidCarlisle: Please is the \else in the solution playing any role? – Ahmed Musa Sep 3 '12 at 4:06
@AhmedMusa The \else has no purpose here, you can omit it. – Heiko Oberdiek Sep 3 '12 at 5:02
@DavidCarlisle Nice trick. \@gobbleto and \@gobbletwo need \long to support \par inside the arbitrary token list. – Heiko Oberdiek Sep 3 '12 at 5:04
@AhmedMusa \else had the purpose of me not having finished designing the code by the time I started the \if :-) – David Carlisle Sep 3 '12 at 9:12

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#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.
\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
% #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

-
Drat, I was just beginning to dream up a similar approach :-) – Joseph Wright Sep 3 '12 at 19:40
The long one or the short one? :-) – Sašo Živanović Sep 3 '12 at 19:52
The short one :-) Next step: get the team to use this for LaTeX3 (\tl_head:n). – Joseph Wright Sep 3 '12 at 19:55
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 '12 at 20:05
Cool! And the change in \firstofmany also deals with the empty list! – Sašo Živanović Sep 3 '12 at 20:17

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}


-
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. – Bruno Le Floch Sep 4 '12 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 '12 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). – Bruno Le Floch Sep 4 '12 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}\d‌​ef\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. – Bruno Le Floch Sep 4 '12 at 22:52

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.

-
Why so much fuss on \@marker and not on \@firstofmany? What makes the clash so outstandingly bad? – Stephan Lehmke Sep 3 '12 at 0:17
@StephanLehmke Nothing bad; but a real world token list might contain them. – egreg Sep 3 '12 at 0:21
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 – David Carlisle Sep 3 '12 at 0:22
@DavidCarlisle Ah, so it's a problem of self-reference. I begin to understand... – Stephan Lehmke Sep 3 '12 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. – Bruno Le Floch Sep 3 '12 at 1:16

Unless we build a delimiter that is specifically taylored 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.

(EDIT: the code was wrong.)

\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.

EDIT2: 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.

-
Ingenious! Could you please explain what's wrong with &? – Sašo Živanović Sep 5 '12 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. – Bruno Le Floch Sep 5 '12 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). – Bruno Le Floch Sep 5 '12 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... – Sašo Živanović Sep 5 '12 at 14:23
@SašoŽivanović Thanks. I'll update my answer accordingly. – Bruno Le Floch Sep 5 '12 at 14:58
\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}

-
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. – Bruno Le Floch Sep 3 '12 at 1:14

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.

-
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 '12 at 18:50
#1 could be braced in the input, so more than one token :-( – Joseph Wright Sep 4 '12 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 '12 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. – Bruno Le Floch Sep 4 '12 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? – Bruno Le Floch Sep 4 '12 at 21:58