Advantages and disadvantages of fully expandable macros

Question

As I currently understand them, fully-expandable macros are analogous to pure/effect-free functions in functional programming. Correspondingly, things that are not expandable, such as \def, are effectful computations -- they can't be "evaluated" inside an \edef, for example. Effect-free functions are generally beneficial (think immutable objects in OOP), and I would expect this to carry over to fully-expandable TeX macros.

However, writing fully-expandable macros seems to be tricky in many cases (see, for example, Tricks to make macros expandable). Moreover, the documentation of the xparse package seems to suggest that fully-expandable macros are usually not desirable:

There are very rare occasion when it may be useful to create functions using a fully-expandable argument grabber. [...] This facility should only be used when absolutely necessary; if you do not understand when this might be, do not use these functions!

So, when should I use fully-expandable macros? What are the advantages and disadvantages of fully-expandable macros?

Answer 1

I think it is best not to compare the expandable/not expandable distinction to concepts from other languages. The main issues relating to expansion are really particular (some would say peculiar) to the execution model of TeX.

TeX has two main modes of operation. All assignments and boxing operations happen (in "the stomach" in The TeXBook terminology) as non-expandable operations. Macro expansion happens before that but unlike (say) the macro expansion of the C pre-processor, macro expansion and non-expandable operations are necessarily intertwined.

It is probably worth noting that the question as posed is not well defined.

TeX tokens are either expandable or non-expandable but "fully expandable" is a grey area full of traps into which the unwary may fall.

Any token defined by \def (or \newcommand etc) is by definition expandable.

A character token such as a is by definition non-expandable.

\def is a non-expandable token.

So if you define

\def\zza{}
\def\zzb{a}
\def\zzc{\def\zze{}}
\def\zzd{\ifmmode a \else b\fi}

then each of these is expandable, with expansion <nothing> a \def\zze{} \ifmmode a \else b\fi respectively.

However which of these is fully expandable ?

Clearly \zza is. But if the definition of "fully expandable" means may be expanded repeatedly leaving no unexpandable tokens then the only fully expandable tokens will all expand to nothing.

So most preople would class \zzb as fully expandable, even though it expands to a which is not expandable.

So a better (or at least more accurate) term than "fully expandable" is "safe in an expansion-only context". Inside \edef and \write and when TeX is looking for a number or dimension, and a few other places, TeX only does expansion and does not do any assignment or other non-expandable operations.

 \edef\yyb{\zzb}

is of course safe, it is the same as \def\yyb{a}. So \yyb is safe in an expansion-only context.

\edef\yyc{\zzc}

is not safe, it is the same as

\edef\yyc{\def\zze{}}

Now \def doesn't expand but in an expansion-only context the token just stays inert it does not make a definition so TeX then tries to expand \zze which typically is not yet defined so this leads to an error, or if \zze has a definition then this will be expanded which is almost always unwanted behaviour. This is the basic cause of the infamous "fragile command in a moving argument" errors in LaTeX.

So \zzc is not safe in an expansion-only context. If it had been defined by the e-TeX construct

\protected\def\zzc{\def\zze{}}

Then in an expansion-only construct protected tokens are made non-expandable so

\edef\yyc{\zzc}

would then be safe, and the same as \def\yyc{\zzc} So a protected command is safe in an expansion-only context but since this safety comes by making the token temporarily non-expandable it probably isn't accurate to say it is "fully expandable".

\edef\yyd{\zzd}

is

\edef\yyd{\ifmmode a \else b\fi}

which is

\def\yyd{b}

or \def\yyd{a} if the definition is happening inside $...$ (or an equation display). Similarly it will expand to b at the start of an array cell as the expansion will happen while TeX is expanding looking for \omit (\multicolumn) and so before it has inserted the $ to put the array cell in to math mode. Again a protected definition to limit expansion is what is required here.

So sometimes it is good to make things expandable as it keeps more options open.

\def\testa#1#2#3{%
  \ifnum#1=0
  \def\next{#2}%
  \else
  \def\next{#3}%
  \fi
  \next}

\def\firstoftwo#1#2{#1}
\def\secondoftwo#1#2{#2}

\def\testb#1{%
  \ifnum#1=0
  \expandafter\firstoftwo
  \else
  \expandafter\secondoftwo
  \fi}

both \testa{n}{yes}{no} and \testb{n}{yes}{no} will exectute yes if n is 0 and no otherwise but \testb works by expansion and so is safe in an expansion-only context (if its arguments are safe). The \testa version relies on the internal non-expandable operation of \def\next. (Plain TeX and LaTeX2.09 use many tests using \def\next, LaTeX2e changed them to the expandable form where possible.)

For a numeric test it is easy to use the expandable form, but if you want to test if two "strings" are equal by far the easiest way is to go

\def\testc#1#2{%
  \def\tempa{#1}\def\tempb{#2}%
  \ifx\tempa\tempb
  \expandafter\firstoftwo
  \else
  \expandafter\secondoftwo
  \fi}

but now even though we have used the \expandafter\firstoftwo construct, the test relies on two non-expandable definitions. If you really need to test in an expandable way you can find some questions on this site but any answer is typically full of special conditions and cases where it doesn't work and relies on some kind of slow token by token loop through the two arguments testing if they are equal. In 99% of the cases this complication is just not needed and the non-expandable test is sufficient. If you are trying to define a consistent set of tests (as in the ifthen package \ifthenelse for example, then if you resign yourself to the fact that some tests are necessarily non-expandable then you may choose to make them all non-expandable so they behave in a consistent way.

So the answer is:

It all depends....

Answer 2

While TeX is Turing complete, this says nothing about whether a particular operation can be carried out expandably. Thus the first issue with aiming when considering if something can be coded expandably is whether it is even possible. As discussed in Why isn't everything expandable?, some operations are not expandable as the underlying primitives are not. Obvious cases include assignments, grouping and any form of typesetting in boxes. This means that for example it is not possible to measure the typeset width of material in an expandable manner, and so you can't do what you might aim for with something like

\newdimen\mydim
\mydim\wd\hbox{foo}%

even though this seems 'logical', and instead have to take an approach equivalent to

\newdimen\mydim
\newbox\mybox
\setbox\mybox=\hbox{foo}%
\mydim\wd\mybox

(This shows up more clearly when you start wanting to do more complex expressions.)

The second issue, alluded to in the xparse manual, is that there are often limitations to expandable methods which do not show up in non-expandable ones. A case that is particularly noticeable is looking ahead for optional arguments. In a non-expandable manner, this is done using \futurelet (an assignment, and so not expandable). To do the same expandably, you have to grab an argument. That method is not as robust, as if we have

\foo{[} ...

then \futurelet will detect {, while argument grabbing will see [. Assuming we are looking for a LaTeX-like optional argument, the expandable test will be 'wrong'. So expandable code here is more limited in terms of what it can deal with.

Writing expandable code is often much more tricky than the non-expandable case. You cannot save anything other than by leaving it in the input stream in an known way, which can be very hard to keep a track of. This can also have performance implications, as for a complex operation you may need to keep track of an awful lot of stuff.

A related issue here is that there are two types of expandability. Within a \edef, TeX will keep expanding tokens until only non-expandable ones remain. In this case, you can add 'output' tokens to the front of the input stream and have TeX continue to process the rest of the operation. On the other hand, you can do an expandable expansion using \romannumeral-`\q, However, this stops on the first non-expandable token. So if you want to write a function which works inside this 'full' expansion you have to watch the output tokens very carefully. (The LaTeX3 expl3 language differentiates between these two forms of expansion as x- and f-type, respectively, and the documentation indicates whether expandable functions will work properly inside f-type situations.)

This might make you wonder why you'd write expandable functions. As the question notes, there are advantages. The most obvious is that they can be used inside assignments, such as setting dimensions. Bruno Le Floch has written an expandable FPU for LaTeX3, which would be a great example of this. TeX also expands tokens in some other contexts, most obviously at the start of a table (\halign) cell to look for \omit or \noalign, and there you need to use expandable methods if you want to deal (easily) with escaping from alignment. (There are other approaches to this!)

When TeX writes to files, it carries out full expansion. This may or may not be desirable with a given macro. For example, a lot of LaTeX macros are writing without expansion to the .aux file as it's the 'wrong' time to expand.

In general, with the exception of programming layers (where you do want expandability if possible), creating expandable macros is not usually a priority, hence the statement in xparse. Broadly, I would look to create expandable functions when I know that one is needed.

Answer 3

Perhaps the two main applications are:

• when the macro will be used inside \csname...\endcsname
• when having the current value at the time of an \edef, mark, etc., is necessary.

Answer 4

Some other points, which I think is not mentioned or only briefly mentioned in other answers.

Only fully-expandable functions can conveniently "return result" as argument to another functions.

Imagine you have a function \increaseone{5} that when executed typeset 6.

Now imagine you want to call \dosomethingwith{\increaseone{5}} and you want it to be the same as \dosomethingwith{6}. This is only possible^(*) when \increaseone is fully expandable (and \dosomethingwith fully expands its argument).

If that's not the case, you'd usually need to store them into temporary "variables" manually e.g.

\increaseone[store-to=\tmp]{5}
\dosomethingwith{\tmp}

Consequently, for programming convenience^(†), people tend to try to make functions that "return results" expandable (⋆-type functions in expl3), if it doesn't make the performance significantly worse (when it does, they try to make it ✩-type expandable at least).

^(*) Technically it's also possible for the outer function and the inner function to "agree" on some "intermediate" location to pass the result i.e. the inner function stores the result there, then the outer function reads the result from it. See functional package for an example of that approach.

^(†) and only for programming convenience. Everything you can do with fully expandable macros, you can make an unexpandable macro set an intermediate "variable" (or use a callback, etc.) like the method above. Unless you're using some library that provides an "API" that only accepts fully expandable functions, that is.

(some other case where expandability is more convenient)

Consider the tabular environment for example.

\begin{tabular}{|c|c|}
    \int_step_inline:nn {5} {
        #1 & #1 \\
    }
\end{tabular}

This code will print an extra cell, like this. (assume you set the correct catcode)

The reason is that in the low-level tabular is implemented in terms of halign which uses some complicated logic to determine whether or not there is a cell, and if there's something unexpandable it determines there is.

For example the following code produces the same output

\begin{tabular}{|c|c|}
    1 & 1 \\
    2 & 2 \\
    3 & 3 \\
    4 & 4 \\
    5 & 5 \\
    \relax
\end{tabular}

Reference: Completely expandable loop macro that also works in tabular

Note that, again, expandability is not required, just more convenient. Using the expandable \int_step_function:nN would fix this, but the code can also be rewritten without expandability like this

\tl_set:Nn \__content_to_be_executed {}
\int_step_inline:nn {5} {
    \tl_put_right:Nn \__content_to_be_executed { #1 & #1 \\ }
}

\begin{tabular}{|c|c|}
    \__content_to_be_executed
\end{tabular}

It's the reader's exercise to figure out how to eliminate the added asymptotic complexity.

Changes in LuaTeX.

First, there's the new primitive \immediateassignment, which eliminates all the slowness caused by expansion-only programming as mentioned above.

Then, there's \directlua which is expandable, and allow you to use Lua to store it things. (although both Lua and TeX uses hash table, using Lua hash table has the advantage of not needing to have a "common unique prefix/suffix" for each table, thus speed up the hashing/retrieval. And more convenient programming, of course. + it's faster to handle unbalanced token list in Lua, as you need intermediate representation in TeX + TeX string hashing function has some issues, see above)

There are a few things that can only be done unexpandably. (more examples.)

• Parsing optional argument is mentioned above as one. You can't distinguish \function {[} something ] and \function [ something ] expandably. _{(to be fair, if you assume that the following token is either a { or a [ then you can stringify it, but the general question remains)}

• Some others worth mentioning is distinguishing between some other-catcode character (e.g. !) from its active-catcode version that is \let to its other-catcode. (e.g. \let <active token !> = <other token !> _{other than defining macro that use the fork pattern for each 256 characters}

  (because expansion-only mode is a peculiarity in TeX, such limitations are also peculiarities in TeX. See LuaTeX below.)

• Generate a character token with given charcode/catcode combination. _{again, other than defining macro for each of the 256 characters, or use some XeTeX/LuaTeX primitive.}

• Anything that involves typesetting. You can't "get the width of the character a" without setting a box, which is unexpandable.

(side note unrelated to this question, there are some things cannot be done unexpandably as well. For example

• check if the following token already has catcode frozen (this one as far as I know still cannot be done in LuaTeX)
• implement peek_analysis_map_inline function completely reliably (this one can be done in LuaTeX)

for example with a program like this

%! TEX program = lualatex
\documentclass{article}
\begin{document}

\ExplSyntaxOn

\begingroup
\catcode`\_=12
\global\let\underscoreCatcodeOther _
\endgroup

\let \c \c_group_begin_token

\peek_analysis_map_inline:n { \tl_show:n { #1 } } \c_group_begin_token \underscoreCatcodeOther


\ExplSyntaxOff

\end{document}

\peek_analysis_map_inline:n will mistake that the following token is \c.

)

Expansion-only programming is slower. (more details.)

This is because in expansion-only programming, the memory model is somewhat similar to a stack machine^(‡) (there's only one input stream for you to push data to and pop data from. So you have to "skip" through the "front" of the "stack" to access the data below, and that is slow)

For instance, it's possible to reverse all items in a token list (which consists of all braced groups) in time O(n) using toks registers (or use control sequences indexed with numbers with some performance caveat), but to the best of my knowledge, it's only possible _{(without LuaTeX)} to do that in O(n√n) expandably, or O(n log n) assuming \expanded is available. The expl3 implementation of \tl_reverse_items:n has time complexity O(n²).

^(‡) Technically, there are a few other tricks to store data in other places as well e.g. when you do \number 12345\<some expandable things> the 12345 is "stored" before the expandable things, or when you do \expandafter \somecontrolsequence \<some expandable things>, and you can pack a detokenized token list into a control sequence etc.. Nevertheless most of the time this is not possible.

Even with \expanded included, you have a "stack" and a "another stack of places to push tokens to", nevertheless the memory model is still limited and not as powerful as tok registers.

What "fully expandable" means. (clarification.)

This only "makes sense" for "functions" that are expected to "return result".

For example if a function is supposed to typeset something or set some global variable, it isn't really necessary^(§) for it to be fully expandable, as there's no desired "result" to get from its full expansion. As such it's usually protected.

However, functions that compute some value e.g. addition etc. should usually be expandable. If it somehow cannot be implemented expandably, usually there's a function to store it to some "variable" to be retrieved later.

conditional/mapping functions is usually the difficult part here. For expandable conditional, you expect (pseudocode) \edef \a { \ifsomething 1 \else 2 \fi } to assign either 1 or 2 to "variable" \a, but this only holds when \ifsomething is expandable.

Otherwise you need \ifsomething \edef \a {1} \else \edef \a {2} \fi (again, pseudocode).

^(§) apart from LuaTeX this cannot be implement expandably anyway.

---

Side note.

Some side remark on the memory model of expansion-only programming (briefly mentioned above, section 4 "Expansion-only programming is slower"), TeX slowness, and how the engine could be made to interpret TeX faster.

First, we know that when something like this happens...

\def \a #1 {\b {#1}}
\def \b #1 {\c {#1}}
\def \c #1 {\d {#1}}

each function call requires re-scanning, which takes time linear in the number of tokens in #1.

So, currently it's not possible to implement modifiable random-access memory in O(1) or O(log N) time per operation (ignoring the possibility of setting control sequences to \relax or expl3 "flags")

In theory it's possible for TeX to keep track of the } matches each { to quickly speed-up to that point (and the dangling } on the input stream, if any), but there are a few complications...

• In order to save memory, TeX token lists are keep track internally as a linked list, and the same ⟨replacement text⟩ might be reused multiple times in multiple places. So the same } might be matched to multiple different { tokens.
• In the progress of scanning, it's necessary to check if there's any \outer token in the braced group. As such, every time some token changes its \outer status (hopefully rare), the whole input stream (the part that is tokenized at least) needs to be rescanned to determine whether there's an \outer token inside a braced group.
• Similar for tokens that is produced after a \noexpand. Argument-scanning should revert them to normal tokens.
• Similar for \par. (although this one might be easier because it's matched by token instead of by meaning? Not sure.)
• For brace hacks, the implementation needs to be careful to correctly match the { within the reinserted tokens. (this part may not be very hard, as the list of dangling } are kept)

Other than that, if there's some TeX implementation that makes argument scanning O(1) in non-corner cases, something like a random-access memory could be implemented in expandable TeX programming with only O(log N) overhead (where N is the number of "memory cells") by maintaining e.g. a balanced binary tree.

Such an implementation would probably speed up existing code, although I'm not sure by how much because much of the existing code are optimized with the assumption that argument scanning takes O(N); besides there's a constant-time overhead of needing to keep track of brace balancing..

I'm not sure if it's possible to make argument scanning O(1) in all cases or not, but it seems possible without the complication of \outer and \noexpand tokens, at least.

Side note, I believe that if instead of reusing the same memory cell over and over (back then, memory was very limited), they're actually copied, the time complexity would remain the same^(*) but TeX would run faster because of memory locality. Of course, there would exist some corner case code that takes exponentially more memory than the old implementation.

^(*): I think so with the current implementation. If the implementation uses smart argument grabbing, some careful consideration is needed.