[tex-k] bug in Bernshtein trick in Appendix D of The METAFONTbook

[胡亚捷 (Hu Yajie)]

The last trick in Appendix D of The METAFONTbook (page 299) exhibits the
following macros that make `1/2[a,b,c,d]' expand to `.125a+.375b+.375c+.125d':

def lbrack = hide(delimiters []) lookahead [ enddef;
let [[[ = [; let ]]] = ]; let [ = lbrack;
def lookahead(text t) =
 hide(let [ = lbrack;
  for u=t, hide(n_ := 0; let switch_ = first_): switch_ u; endfor)       % (1)
 if n_<3: [[[t]]] else: Bernshtein n_ fi enddef;                         % (2)
def first_ primary u =
 if numeric u: numeric u_[[[]]]; store_ u
 elseif pair u: pair u_[[[]]]; store_ u fi;
 let switch_ = store_ enddef;
def store_ primary u = u_[[[incr n_]]] := u enddef;
primarydef t Bernshtein nn =
 begingroup for n=nn downto 2:
  for k=1 upto n-1: u_[[[k]]]:=t[[[u_[[[k]]],u_[[[k+1]]] ]]];
  endfor endfor u_[[[1]]] endgroup enddef;                               % (3)

These macros work by making `[' check how many expressions occur between it
and the matching `]': If there are three or more, it triggers the `Bernshtein'
macro to handle the new syntax, otherwise it reinserts the expressions between
primitive brackets so that old code will still work.

Did you see the bug? (1) To determine how many comma-separated expressions
occur between the brackets, the macro evaluates the list with a for loop.
(The switch_ macro takes care of the counting.) (2) And if there are fewer
than three expressions, the macro reinserts the list between
primitive brackets which will evaluate them again. This means that any
side effect intended to take place once will take place twice. For example,
the definition of `flex' in plain METAFONT says `z_[incr n_]':

def flex(text t) =           % t is a list of pairs
 hide(n_:=0; for z=t: z_[incr n_]:=z; endfor
  dz_:=z_[n_]-z_1)
 z_1 for k=2 upto n_-1: ...z_[k]{dz_} endfor ...z_[n_] enddef;
newinternal n_; pair z_[],dz_;

which fails with the new macros even with the naming conflict of `n_' solved:

*draw flex((42,130),(60,123),(76,124));
>> xpart z_1
! Undefined x coordinate has been replaced by 0.
<to be read again>
                   ..
...->..
       tension.atleast1..
<for(2)> ...
            z_[(EXPR0)]{dz_} ENDFOR
flex->...1)z_1for.k=2upto.n_-1:...z_[k]{dz_}endfor
                                                  ...z_[n_]
<*> draw flex((42,130),(60,123),(76,124))
                                         ;
?

Asking the machine to `showvariable z_' reveals that the key points that should
have been stored in z_1, z_2, and z_3 are being stored in z_2, z_4, and z_6,
so it is clear that the new macros caused `incr n_' to be evaluated twice.

How to fix the problem? Since the first scan of expressions (1) evaluates and
stores them in the array u_[[[]]], you can just retrieve the values instead of
evaluating the expressions again when reinserting primitive brackets: Change
line (2) to

 if n_=0: [[[]]] elseif n_=1: [[[u_[[[1]]] ]]]
 elseif n_=2: [[[u_[[[1]]],u_[[[2]]] ]]] else: Bernshtein n_ fi enddef; % (2')

(as well as renaming `n_' to avoid conflict) and `flex' will be working fine.

------------------------------------------------------------------------------

Here is another `bug': If you try to `show' a Bernshtein polynomial with an
interpolation value between 0 and 1, the macros work pretty well:

*show 1/2[a,b,c,d];
>> 0.125d+0.375c+0.375b+0.125a

But you get a surprise if you plug in, for example, t=2:

*show 2[a,b,c,d];
>> u_1

because the private variables u_[[[]]] are not cleared after `Bernshtein' has
done its calculation:

*showdependencies;
d = 0.125u_1-0.75u_2+1.5u_3+0.125a
c = 0.25u_1-1.5u_2+2u_3+0.25a
b = 0.5u_1-2u_2+2u_3+0.5a
u_4 = 0.125u_1-0.75u_2+1.5u_3+0.125a

(If you rewrite these equations you'll find that u_1 equals -a+6b-12c+8d,
which is indeed 2[a,b,c,d].) No problem, let's change line (3) of the program
so that private variables u_[[[]]] are destroyed before u_[[[1]]] is returned:

  endfor endfor clear_ u_[[[1]]] endgroup enddef;
def clear_ primary u = let u_ = \; u enddef;                            % (3')

(The effect of `let u_ = \' is similar to `numeric u_[[[]]]'.) But then we get
another surprise:

*show 2[a,b,c,d];
>> %CAPSULE4460

because we're using a macro to `move out' the result from u_[[[1]]] before
destroying the whole array. And if we use a variable to move out u_[[[1]]],
the machine will just respond with the name of that variable:

  endfor endfor uu_ := u_[[[1]]]; let u_ = \; uu_ endgroup enddef;     % (3'')

*show 2[a,b,c,d];
>> uu_

So how can we make METAFONT display the result of the Bernshtein polynomial
explicitly, instead of burying it in a flood of dependencies? The trick is to
compute the coefficients first and build the polynomial from an expression.
Change the definition of `Bernshtein' to:

primarydef t Bernshtein nn = begingroup c_[[[1]]] := 1;
 for n=1 upto nn-1: c_[[[n+1]]] := t*c_[[[n]]];
  for k=n downto 2: c_[[[k]]] := t[[[c_[[[k]]], c_[[[k-1]]] ]]];
  endfor c_[[[1]]] := (1-t)*c_[[[1]]]; endfor
 for n=1 upto nn: +c_[[[n]]]*u_[[[n]]] endfor endgroup enddef;

When t=1/2 and nn=4, the first loop computes the coefficients

n       c_[[[1]]]   c_[[[2]]]   c_[[[3]]]   c_[[[4]]]
0       1
1       0.5         0.5
2       0.25        0.5         0.25
3       0.125       0.375       0.375       0.125

and the second loop builds the expression `0.125*a+0.375*b+0.375*c+0.125*d'
from these coefficients and the stored variables. Let's try to `show'
the t=2 case with our new macro:

*show 2[a,b,c,d];
>> 8d-12c+6b-a

And lo, it works! You can also store it in a variable:

*x=2[a,b,c,d];

*showdependencies;
c=0.66667d+0.5b-0.08333a-0.08333x
u_4=d
u_3=0.66667d+0.5b-0.08333a-0.08333x
u_2=b
u_1=a
*a=b=d=0; c=1; show x;
>> -12
*

Note that we can extract the exact coefficient -12 with the improved macro.
By contrast, the old macro gives -11.99854 with the same input and -12.00073
if the u_[[[]]] array is immediately cleared after the use of `Bernshtein'.

------------------------------------------------------------------------------

By the way, the index entry `values, disappearance of' lacks the page numbers
83, 177--178, 218, and 239. The last three are important because they reveal
other ways to discard values (namely `vardef', `let', and capsules). If I were
unaware of them, I would probably have said `numeric u_[[[]]]' instead of the
elegant `let u_=\' in the first experiment above.