Re: Fast expanding macros /Was: How to declare recursive factorial function?

mpg wrote:

By the way, I've been thinking a moment about the following: given a macro
that works purely by expansion, in which cases is it possible to make it
deliver its result within two expansion steps, and how?
[...]

2. The macro is a test which expands either one or the other of its
arguments: one can use \romannumral0[...]\space where the [...] part
finally triggers an argument grabber like \@firstoftwo or so on.

There is plenty of stuff where expansion is not suppressed in
order to obtain arguments, values or whatever.
E.g., expansion takes place when looking for opening-braces or
key-words related to things like register-assignments or
\unexpanded or \scantokens, with those \if-comparisons, with
\csname, with \the, when gathering a numerical value, at some
places within alignments...

For some obscure reason I like \romannumeral.
This can also be used for argument-list-iterating.

Is there any other tricks like that?

For example, I thought a lot about the following problem. Given a list of,
say coma-separated items, and a purely expandable macro comparing two items
and returning the "greatest" (in some sense), it is possible to compute
the "maximum" of the list purely by expansion. But is it possible to make
the macro return a result in two expansion-steps? Assume it is not a list
of number, so we cannot use the a \number trick, and it has more than 9
elements, so I cannot see how to use argument grabbers. Is it still
possible? Any clue?

In order to keep iteration in progress, you can still use the
\romannumeral0<space>-trick - \romannumeral0<space> doesn't
deliver any token, but you can "fool" \romannumeral into
expanding a lot of stuff (e.g., some iterator-macro) and moving
around a few macro-arguments before finding that <space> at
the time when iteration should terminate.

E.g., create an iterator for the list which besides the list
takes some arguments used for action after recursion.
Let the iterator modify these arguments during iteration...

e.g. \iterate{foo}{elem1,elem2,...}
next step: \iterate{baz}{elem2,...}

....while not delivering any token "outside" the iterator's
"argument-grabbing-range".

At the end of the recursion, have the iterator return the
modified argument.

You can probably put such a thing behind \romannumeral0 and have
delivered a space at the end of the recursion, right before
having the iterator return the modified argument.
This yields expandability in two steps.

The following example defines a "generic macro" \loopcall which
can be used for iterating on argument-lists.

As an example it also delivers the macro \findlargestpositive
number which internally uses \loopcall.
It takes an argument-list consisting of numbers and delivers
the token which yields the largest value.

I think, the gist of the whole thing is probably the macro
\togglelargernumber - it "touches"/modifies the arguments
which will be passed to \loopcall in the next iteration.

But comma-list-parsing is poorly implemented (e.g., no lead-and-
trail-space-checking, also no check for a missing comma at the
end of the list.)

Actually I don't like comma-lists all too much any more and
prefer "argument-lists" wherever possible because with comma-
lists you always need to decide upon the treatment of "edge-
cases", e.g. consecutive commas, trailing-comma, leading-comma,
only blank-stuff between comma, how many levels of brace-
stripping, catcode-change of comma, ...

I assume, somebody might easily bring up a snippet of code which
does the same things within only a few lines...

If you are interested in such stuff, have a look at the
TeX pearl divers site at http://www-stary.gust.org.pl/pearls/
(-> Pearls 2005 -> David Kastrup: Iterating with roman numeral).

I also learned a lot when Robin Fairbairns pointed me to the
'Around the bend'-department at
http://www.ctan.org/tex-archive/info/aro-bend/.
There you find the text-files exercise.001 - exercise.018
and answer.001 - answer.018.


Sincerely

Ulrich


\documentclass{article}
\makeatletter
%
% A "reliable" expandable empty-test without e-TeX is feasible
% but it requires much more code. (The remaining code is
% without e-TeX.)
%
\newcommand\my@ifempty[1]{%
\expandafter\ifx\expandafter\relax\detokenize{#1}\relax
\expandafter\@firstoftwo
\else
\expandafter\@secondoftwo
\fi
}
%
% Auxiliary macros to \extractfirstargument:
%
\newcommand\switch[2]{{#2}{#1}}%
\@ifdefinable\@carbrace{%
\long\def\@carbrace#1#2\@nil{{#1}}%
}
\newcommand\@extractfirstargumentloop[4]{%
\expandafter\my@ifempty\expandafter{\@gobble#1}%
{\endcsname{#3}#1#4{#2}}%
{%
\expandafter\@extractfirstargumentloop
\expandafter{%
\@carbrace#1}{#2}{#3}{#4}%
}%
}
%
% \extractfirstargument{<List-Action>}%
% {<Empty-Action>}%
% {<Args>}%
% {{Elem1}{Elem2}..{ElemN}}
% yields in case Elem-List is not empty:
% <Action>{Elem1}<Args>{{Elem2}..{ElemN}}
% yields in case Elem-List is empty:
% <Empty-Action><Args>
%
\newcommand\extractfirstargument[4]{%
\csname @firstofone%
\my@ifempty{#4}%
{\endcsname{#2}#3}%
{%
\expandafter\expandafter
\expandafter \@extractfirstargumentloop
\expandafter\switch
\expandafter{%
\@gobble#4}{#4\@nil}{#1}{#3}%
}%
}
%
% Auxiliary macros to \commaextractfirstargument
%
\long\def\@gobblecomma#1,{}%
\@ifdefinable\@carbracecomma{%
\long\def\@carbracecomma#1,#2\@nil,{#1,}%
}
\@ifdefinable\@stripcomma{%
\long\def\@stripcomma#1,{#1}%
}
\newcommand\@commaextractfirstargumentloop[4]{%
\expandafter\my@ifempty\expandafter{\@gobblecomma#1}%
{\expandafter\expandafter
\expandafter \expandafter
\expandafter\expandafter
\expandafter \endcsname
\expandafter\expandafter
\expandafter \switch
\expandafter\expandafter
\expandafter {%
\expandafter\@gobble
\@stripcomma#1}{#3}#4{#2}%
}{%
\expandafter\@commaextractfirstargumentloop
\expandafter{\@carbracecomma#1}{#2}{#3}{#4}%
}%
}
%
% \commaextractfirstargument{<List-Action>}%
% {<Empty-Action>}%
% {<Args>}%
% {Elem1,Elem2,..ElemN,}
% % Obey the trailing comma!
% % No surrounding-space-treatment!
% yields in case Elem-List is not empty:
% <Action>{Elem1}<Args>{Elem2,..ElemN,}
% yields in case Elem-List is empty:
% <Empty-Action><Args>
%
\newcommand\commaextractfirstargument[4]{%
\csname @firstofone%
\my@ifempty{#4}%
{\endcsname{#2}#3}%
{%
\expandafter\expandafter
\expandafter \@commaextractfirstargumentloop
\expandafter\switch
\expandafter{%
\@gobblecomma#4}{.#4\@nil,}{#1}{#3}%
}%
}
%
% \loopcall{<List-Action>}%
% {<Empty-Action>}%
% {<Args>}%
% {{Elem1}{Elem2}..{ElemN}}
% performs in case Elem-List is not empty:
% <Action>{Elem1}<Args>{{Elem2}..{ElemN}}%
% performs in case Elem-List is not empty:
% <Empty-Action><Args>
% That means it delivers:
% <Action>{Elem1}<Args>
% <Action>{Elem2}<Args>
% ...
% <Action>{ElemN}<Args>
% <Empty-Action><Args>
%
\newcommand\loopcall[4]{%
\my@ifempty{#4}{%
\extractfirstargument{#1}{#2}{#3}{#4}%
}{%
\extractfirstargument{#1}{#2}{#3\loopcall{#1}{#2}{#3}}{#4}%
}%
}
%%
%%
\newcommand*\togglelargernumber{}
%
% <Action>'s first arg is the list-element
% <Action>'s second arg is whatever you pass as <Args>, e.g.
% keeps track of the largest number in the list.
% Define <Action> to modify the look of the 3rd Argument of the
% next call to \loopcall according to its own first argument:
%
% The gist is: You can do whatever you want with
% \loopcall's <Args>.
% You are not bound to numerical comparisons. Also you are not
% bound to only two forking-routes. You can stop iterating
% completely by gobbling the remaining list. You can switch to
% another iterator...
% You can even have more than 9 args in <Args> and call in an
% interim-step yet a few other macros in order to process them
% first...
%
\long\def\togglelargernumber#1#2\loopcall#3#4#5{%
\ifnum0#2>0#1
\expandafter\@firstoftwo
\else
\expandafter\@secondoftwo
\fi
{\loopcall{#3}{#4}{#2}}%
{\loopcall{#3}{#4}{#1}}%
}
%
\newcommand\printlargestnumber[1]{ #1}% space terminates
% % \romannumeral
\newcommand\findlargestpositivenumber[1]{%
\romannumeral0\loopcall{\togglelargernumber}%
{\printlargestnumber}%
{{}}%
{#1}%
}

\begin{document}

\edef\TESTxA{%
\findlargestpositivenumber{%
{0}{4}{16}{8}{4}{3}{55}{11}{27}{46}%
}%
}
\message{\string\TESTxA: \meaning\TESTxA^^J}

\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\TESTxB
\expandafter\expandafter\expandafter{%
\findlargestpositivenumber{%
{0}{4}{16}{8}{4}{3}{55}{11}{27}{46}%
}%
}
\message{\string\TESTxB: \meaning\TESTxB^^J}


\begingroup

\let\extractfirstargument=\commaextractfirstargument

\edef\TESTxC{%
\findlargestpositivenumber{0,4,16,8,4,3,55,11,27,46,}%
}
\message{\string\TESTxC: \meaning\TESTxC^^J}

\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\TESTxD
\expandafter\expandafter\expandafter{%
\findlargestpositivenumber{0,4,16,8,4,3,55,11,27,46,}%
}
\message{\string\TESTxD: \meaning\TESTxD^^J}

\endgroup

\let\@nil=\relax

\edef\TESTxE{%
\extractfirstargument{Action}{Empty}%
{{1}{2}{3}{4}{5}{6}}%
{\@nil\@nil{A}{B}{C}\@nil{D}{E}\@nil\@nil}%
}
\message{\string\TESTxE: \meaning\TESTxE^^J}

\edef\TESTxF{%
\extractfirstargument{Action}{Empty}%
{{1}{2}{3}{4}{5}{6}}%
{{A}{B}{C}{D}{E}}%
}
\message{\string\TESTxF: \meaning\TESTxF^^J}

\edef\TESTxG{%
\extractfirstargument{Action}{Empty}%
{{1}{2}{3}{4}{5}{6}}%
{{A}}%
}
\message{\string\TESTxG: \meaning\TESTxG^^J}

\edef\TESTxH{%
\extractfirstargument{Action}{Empty}%
{{1}{2}{3}{4}{5}{6}}%
{}%
}
\message{\string\TESTxH: \meaning\TESTxH^^J}

\newcommand\Action[7]{%
\message{^^J^^J1st:#1^^J2nd:#2^^J3rd:#3^^J4th:#4^^J%
5th:#5^^J6th:#6^^J7th:#7^^J}%
}%
\newcommand\EmptyAct[6]{%
\message{^^J^^JE-1st:#1^^JE-2nd:#2^^JE-3rd:#3^^JE-4th:#4^^J%
E-5th:#5^^JE-6th:#6^^J}%
}%
\loopcall{\Action}{\EmptyAct}%
{{1}{2}{3}{4}{5}{6}}%
{\@nil\@nil{A}{B}{C}{Blebb}{D}{E}\@nil}

\edef\TESTxI{%
\loopcall{Action}{Empty}%
{{1}{2}{3}{4}{5}{6}}%
{{{A}}{{B}}{{C}}\@nil{{D}}{{E}}\@nil\@nil}%
}
\message{\string\TESTxI: \meaning\TESTxI^^J}

\end{document}
.

Relevant Pages

  • Re: Listcomprehension-macro? Macros with args inside macro-name?
    ... without producing intermediary lists or anything. ... the current item from the iterator, r the current result and reducer ... like I said above: all and range return an iterator ... Not rewriting a set of macros, but simply wrapping it behind a macro. ...
    (comp.lang.lisp)
  • Re: Listcomprehension-macro? Macros with args inside macro-name?
    ... This has to be a macro right? ... lists, then I got range, which returns an iterator for the range. ... I think its applicative programming how it should not be used: ...
    (comp.lang.lisp)
  • Re: CASE with symbol evaluating to list?
    ... That constant evaluates as lists, ... macro doesn't recognize it as list designator. ... expanding to a proper list at compile time should do, ... The expansion of a symbol macro is subject to further macro ...
    (comp.lang.lisp)
  • Re: mutable list iterators - a proposal
    ... > Replacing items, which is by far the most common need, works fine. ... >> through which the iterator has already passed, ... The fact that lists don't ... def SetBottom: ...
    (comp.lang.python)
  • Re: Iterator Class?
    ... >> there is a significant performace penalty when using getfor long Lists. ... >> available albeit at a slight performance penalty compared to Iterator. ... Farsight Systems Corporation ...
    (comp.lang.java.programmer)