[The addendum was not included in the original post but added in my
archives later ---mjd]

Date: 25 Oct 1993 16:36:43 -0400 (EDT)
From: Michael Downes <MJD@MATH.AMS.ORG>
Subject: Around the Bend #12, answer
To: info-tex@shsu.edu
X-ListName: TeX-Related Network Discussion List <INFO-TeX@SHSU.edu>

Exercise 12 asked "How many commands are there in plain TeX that can
be used to define a new (i.e., previously undefined) control
sequence?". This exercise has latent ambiguities. The parenthetical
remark "(i.e., previously undefined)" was intended as a hint towards
the most comprehensive possible answer.

There are three main criteria that could be used for `new' status of a
control sequence:

(1) If executed, the control sequence causes an `Undefined control
sequence' error.

(2) The control sequence is \ifx-equivalent to \relax when constructed
with \csname...\endcsname. This is the basis of the LaTeX
\@ifundefined test.

(3) The control sequence has not yet been entered into the hash table.

Criterion (3) doesn't work for one-character control sequences (\a,
\0, \:) since they have space reserved for them separate from the
hash table whether or not they are defined in any sense.

Criterion (2) obviously gives a spurious true result if applied to
\relax or to something like LaTeX's \protect command that spends much
of its time being equivalent to \relax.

Criterion (1) therefore seems best. Notice that control sequences can
enter into the hash table without becoming defined anywhere along the
way, so a control sequence can be `old' by criterion (3) but still
new by criterion (1). In all of the following examples the control
sequence \foo will get added to the hash table but remain undefined.

  \def\x{\foo}
  \toks0{\foo}
  \string\foo
  \noexpand\foo
  \gobble\foo (assuming \def\gobble#1{})
  \uppercase{\iffalse\foo\fi}
  \show\foo
  \meaning\foo

Two notable cases where tokenization, but not hash-table-ization, of
\foo occurs are in an \ifx comparison or on the false branch of an \if:

  \ifx\foo\something...
  \iffalse\foo\fi

(TeXbook, Appendix D, p384).

The straightforward answer to Exercise 12 is to count up the various
kinds of def'ing and let'ing functions:

Primitive:          Nonprimitive:

\def                \newcount
\edef               \newdimen
\gdef               \newskip
\xdef               \newmuskip
\let                \newfam
\futurelet          \newwrite
\chardef            \newread
\mathchardef        \newbox
\countdef           \newtoks
\dimendef           \newinsert
\skipdef            \newlanguage
\muskipdef          \newif
\toksdef            \newhelp
\font               
\read
\csname

The reason for including \csname? After \csname foobar\endcsname,
\foobar is no longer undefined; the change in its status is
indistinguishable from the change effected by the statement
\let\foobar\relax. \endcsname is not counted separately because
\csname and \endcsname can only be used together.

So: 16 primitive, 13 non-primitive make 29 total. But to those should
be added two more, since the statement of the Exercise didn't exclude
`private' macros: (i) the internal function \alloc@ of plain.tex
that is shared by all the \newxxx macros (except for \newif and
\newhelp), and (ii) the internal function \@if used by \newif.

That brings the total to 31.

Beyond that there can be added another, less obvious, class of
commands, if we paraphrase the exercise as follows:

  Find all commands such that executing command \xxx, with its normal
  arguments (if any), causes at least one control sequence to pass
  from undefined status to defined status, where undefined status
  means that executing the control sequence would generate the error
  `Undefined control sequence'.

For example, the first use of \loop causes \body and \next to become
defined. As it turns out, there are many of these in plain TeX:

User functions:

\loop, \t, \smash, \vfootnote, \settabs, \phantom,
\vphantom, \hphantom, \footnote, \multispan, \longleftarrow,
\longrightarrow, \mathstrut, \longmapsto, \matrix, \pmatrix; ' or \rq
(math mode only)

Internal functions: \iterate, \relbar, \sett@b, \s@tt@b, \prim@s,
\ph@nt, \fo@t, \f@@t, \pr@m@s, \pr@@@s, \s@tcols

Adding these 18 user functions and 11 internal functions to the
previously cited 31 gives a total of 60 functions available in
plain.tex that satisfy a strict interpretation of the exercise
statement.

Credit for the best answer goes to Dan Luecking, who found 29 of the
primary 31, and did not miss the other two (\csname, \@if) by
overlooking them but by considering them and believing they didn't
satisfy the requirements.

My own score in that part was 28: I overlooked \read, \alloc@, and
\@if until Luecking and Peter Schmitt brought them to my notice.

Ian Collier also submitted a good answer, including identification of
the secondary class of functions that define scratch macros as a side
effect.

========================================================================

Notes:

\iterate, \settabs, \sett@b, \s@tt@b, \t, \prim@s, \ph@nt, \smash,
\vfootnote, \fo@t, \f@@t all define \next.

\loop defines \body.

\pr@m@s defines \nxt.

\prim@s is called by active ' (mathcode "8000) and by \pr@@@s.
\iterate is called by \loop.
\sett@b is called by \settabs.
\s@tt@b is *conditionally* called by \sett@b.
\smash is called by \relbar.
\ph@nt is called by \phantom, \vphantom, and \hphantom.
\vfootnote is called by \footnote.
\fo@t is called by \vfootnote.
\f@@t is *conditionally* called by \fo@t.

Active ' is produced by \rq if used in math mode.
\pr@@@s is called by \pr@m@s.
\loop is called by \multispan and \s@tcols.
\relbar is called by \longleftarrow and \longrightarrow.
\vphantom is called by \mathstrut.

\pr@m@s is called by \prim@s.
\s@tcols is *conditionally* called by \sett@b
\longrightarrow is called by \longmapsto.
\mathstrut is called by \matrix.

\matrix is called by \pmatrix.

\prim@s won't necessarily define \next because it does a futurelet
which will leave \next undefined if the next thing happens to be an
undefined control sequence (rather unlikely, however).

\vfootnote and \settabs also do a \futurelet but it is followed by
another macro that ensures that \next does not end up undefined.

Michael Downes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
mjd@math.ams.org (Internet) ASCII 32--54,55--126: !"#$%&'()*+,-./0123456
789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Addendum: From comp.text.tex
===========================================================================
Archive-Date: Wed, 29 Sep 1993 13:21:40 CST
From: cet1@cus.cam.ac.uk (Chris Thompson)
Subject: Re: Managing Large LaTeX Files. How ??
Date: Wed, 29 Sep 1993 16:36:23 GMT
To: tex-news@SHSU.EDU

In article <93265.121206SPIT@EVALUN11.BITNET>, Werenfried Spit <SPIT@EVALUN11.BITNET>
writes:
|> In article <1993Sep20.130331.16568@vax.oxford.ac.uk>, kaye@vax.oxford.ac.uk
|> (Richard Kaye) says:
|> >Has anyone else had save stack overflow when LaTeX read the .aux files?
|> >
|> >[Will a TeX guru please explain it to me?  I thought \global\def's could not
|> >cause save stack overflow until I found this problem.  If it's a general
|> >problem, it seems a bit silly that LaTeX should try to input so much
|> >information in this way.]
|> >
|> >I fixed it so that the data was read {\it outside} the group (as part of one
|> 
|> Could someone explain it to me too? I'm even more puzzled after I tried
|> out Richards solution and played a bit with it. When you put in
|> your input file directly after the \documentstyle command the line
|>  \input \jobname.aux
|> LaTeX reads the aux file without its memory getting overflowed; then
|> at \begin{document} it reads the aux file again (as expected), but
|> the memory doesn't overflow this time either. (If you leave out the
|> \input \jobname.aux LaTeX only reads the aux file during \begin{document}
|> and then chokes on an exceedence of the save size.)

This was a hard one to track down. I could claim that it was all my fault...

The entries on the save stack are not the result of the \global\@namedef,
which as suggested above never needs to use such a thing. They come from
the earlier \@ifundefined call in \newlabel.

Change #337 in tex82.bug numbering, applied in TeX 2.9, changed the implicit
setting of an undefined control sequence referenced via \csname...\endcsname
to \relax (TeXbook, page 213) from being (sort of) global to being local to
the current group. Don made this change as a direct result of my posting to
TeXhax (year 1987, digest 103) pointing out that the TeXbook didn't correctly
describe what happened.

The change was a potent source of new bugs, because TeX was not originally
designed to cope with token expansion have side-effects of modifying the
save stack (see in particular change #371 in tex82.bug). I have more than
once wondered whether I should have kept quiet about the whole business...

In an ideal world, the problem wouldn't arise because the implicit setting
to \relax wouldn't occur at all (IMNSHO). But everything (especially LaTeX)
relies on it now, so it's (far) too late to change it. Something to be got
right in the next incarnation.

Chris Thompson
Cambridge University Computing Service
Internet: cet1@phx.cam.ac.uk
JANET:    cet1@uk.ac.cam.phx