MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Flat, OneIdentity Again

  • To: mathgroup at smc.vnet.net
  • Subject: [mg21680] Re: [mg21637] Flat, OneIdentity Again
  • From: Hartmut Wolf <hwolf at debis.com>
  • Date: Fri, 21 Jan 2000 04:00:40 -0500 (EST)
  • Organization: debis Systemhaus
  • References: <200001180735.CAA20333@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Dear Ted,

yesterday I answered to your posting (my reply hasn't yet appeared in
the group), yet my feeling is, I possible was a little bit to harsh (and
was wrong in a certain point). I now wan't to correct this, and
hopefully, give some new insight to the problem.

What I did, is to implement a *model* of the semantics as described in
the _Mathematica_ documentation, and I show that this model -- which
also corresponds to our (naive?) expectations -- gives results different
from the _Mathematica_ implementation (see below).


Hartmut Wolf schrieb:
> 
> Ersek, Ted R schrieb:
> >
> > Thanks to all who answered my question on Flat and OneIdentity.
> > I have more strange behavior on this subject.
> >
> > At http://support.wolfram.com/Kernel/Symbols/System/Flat.html
> > it says in so many words ....
> > If (f) has the Flat attribute you better not have a definition like
> >   f[p_]:=p
> > because if you do, then an attempt to evaluate f[1,2] will not work and the
> > kernel will have to quit when the infinite iteration limit is exceeded.
> >
> > In addition I found that you can't even evaluate f[2] in the above case, and
> > it doesn't help if (f) also has the OneIdentity attribute!
> >
> > I wanted to understand just what the kernel is doing to exceed the iteration
> > limit when we try to evaluate f[1,2] or f[2] above.  The lines below offer
> > some clues, but also add to the mystery. I wonder if any of you have an
> > explanation.
> >
> > In[1]:=
> > ClearAll[f];
> > Attributes[f]={Flat};
> >
> > After the input above (f) has the Flat attribute and no definitions.
> > f[1,2] as f[f[1,2]].
> >
> > In[3]:=
> > f[1,2]/.f[p_]:>{p}
> > Out[3]=
> > {f[1,2]}
> >
> > The idea that the pattern matcher treats
> > f[1,2] as f[f[1,2]] is sort of verified
> > at Out[4] below.
> >
> > In[4]:=
> > MatchQ[f[1,2],f[_f]]
> > Out[4]=
> > True
> >
> > But if the pattern matcher treats f[1,2] as f[f[1,2]]
> > why doesn't MatchQ return True in Out[4] below ?
> >
> > In[5]:=
> > MatchQ[f[1,2],HoldPattern[f[f[_Integer,_Integer]]]]
> > Out[5]=
> > False
> >
> > Even stranger is the next line where the pattern is much more general!
> > Notice that is a triple blank inside (f).
> >
> > In[6]:=
> > MatchQ[f[1,2],HoldPattern[f[f[___]]]]
> > Out[6]=
> > False
> >
> > All the results above come out the same if (f) has the attributes Flat,
> > OneIdentity.
> >
> > I have a hunch what may be going on here. Perhaps this is a bug. Could it be
> > that the part of the pattern matcher that handles Flat is oblivious to
> > HoldPattern and checks for a match with the patterns f[_Integer,_Integer]
> > and  f[___]
> > when it should check for a match with f[f[_Integer,_Integer]] and  f[f[___]]
> >
> > respectively in the lines above?
> >
> > I did all this using Version 4.
> >
> > --------------------
> > Regards,
> > Ted Ersek
> >
> > On 12-18-99 Mathematica tips, tricks at
> > http://www.dot.net.au/~elisha/ersek/Tricks.html
> > had a major update
> 
> Hello Ted,
> 
> first, again a citation from The Book. In section 2.3.8 it says:
> 
> Notice that with flat functions such as Plus and Times, Mathematica
> automatically handles variable numbers of arguments, so you do not
> explicitly need to use double or triple blanks, as discussed in Section
> 2.3.7.
> 
> ...to me "you do not explicitly need to use" reads plain "don't"
> 
I refer to my answer <200001180735.CAA20354 at smc.vnet.net> to your first
posting 
"[mg21600] Flat, OneIdentity attributes"
<200001170343.WAA13401 at smc.vnet.net> where I had shown that double
blanks definitly are not equivalent to a single blank in case of
attribute Flat (without OneIdentity).


> Now to your obvservations I'd like to add:
> 
> In[1]:= ClearAll[f]; Attributes[f] = {Flat};
> 
> In[2]:= MatchQ[f[f[1, 2]], f[x : _f]]
> Out[2]= True
> 
> In[3]:= MatchQ[f[f[1, 2]], f[x : f[_]]]
> Out[3]= False
> 
> Something hard to digest! (It doesn't matter whether you use Blank[] or
> BlankSequence[], see quotation above.)
> 
> However
> 
> In[4]:= MatchQ[f[f[1, 2]], f[f[_]]]
> Out[4]= True
> 
> In[5]:= MatchQ[f[f[1, 2]], HoldPattern[f[f[_]]]]
> Out[5]= False
> 
> Now it is informative to trace these examples.
> 
> In[8]:= MatchQ[f[f[1, 2]], f[f[_]]] // Trace
> Out[8]=
> {{f[f[1, 2]], f[1, 2]}, {f[f[_]], f[_]}, MatchQ[f[1, 2], f[_]], True}
> 
> Things are brought to a 'normal form' first, and such f[f[_]] is
> converted to f[_] first, before matching begins.  Now the idea, that the
> pattern matcher converts the lhs (of MatchQ, ReplaceAll, etc.) to
> f[f[1,2]] and then uses the 'normal' matching algorithm is nowhere
> stated in The Book (being our *only* source of documentation). It's an
> idea we gain and might use as a catch rule, yet understood literally and
> procedurally this might be an illusion!
> 
What is wrong with this statement is, first, S. Wolfram states in his
book (4th ed. p.274):

Mathematica writes the expression in the form r[r[a, b], r[a, b]] to
match the pattern. 

In[17]:= r[a, b, a, b] /. r[x_, x_] -> rp[x]
Out[17]= rp[r[a, b]]

--end of quotation--

And second, we are used to respect the publications of Wolfram Inc. e.g.
at  http://support.wolfram.com/Kernel/Symbols/System/Flat.html as
autoritative.

There they write: ... For example, in matching the expression f[1,2,3],
the pattern matcher will look for matches among the expressions
f[1,2,3], or f[f[1,2],3], and so forth.

Yet my new results give more support to my speculation

> So the pattern matcher might very well use it's own procedures when he
> receives its input for a Flat function (in 'normal form'). And now the
> presence of the name x in f[x : f[_]]] as well as HoldPattern hinders
> the evaluator to generate the appropriate 'normal form' the pattern
> matcher needs to go throught its special Flat or Flat & OneIdentity
> algorithm.
> 
> Yet, Ted, this might be another illusion, and I'm telling fairy tales.
> 
This is something I regret and want to apologize.


Now here the new stuff:
----------------------------------------------
 
In[1]:= << DiscreteMath`Combinatorica`

I define a helper function which generates "the expressions f[1,2,3], or
f[f[1,2],3], and so forth" (see above)

In[2]:= Attributes[allGroupings] = {HoldAll};
In[3]:= 
allGroupings[expr_] := Module[{f, c},
    c = Join @@ Map[Permutations, Partitions[Length[expr]]]; 
    f[lst_, n_] := (res = {res, Hold[Take[lst, n]]}; Drop[lst, n]); 
    Block[{res = {}}, Fold[f, expr, #]; 
          Head[expr] @@ Flatten[res] // ReleaseHold] & /@ c]

In[4]:= Attributes[myReplaceList] = {HoldAllComplete};
In[5]:=
myReplaceList[expr_, rules_] := 
  If[MemberQ[myAttributes[Head[expr]], myFlat], 
    Join @@ ((ReplaceList[#, rules]) & /@ allGroupings[Flatten[expr]]), 
    ReplaceList[expr, rules]]
 
This function is my model and has to be compaired with the kernel
function ReplaceList!

We define f (for the model) and ff (for the build-in):

In[6]:= ClearAll[f]; myAttributes[f] = {myFlat};
In[7]:= ClearAll[ff]; Attributes[ff] = {Flat};
 
Just a test to show that it works:

In[8]:= ReplaceList[ff[1, 2, 3, 4, 5] , ff[x_, y_, z_] :> {x, y, z}]
Out[8]=
{{ff[1], ff[2], ff[3, 4, 5]}, {ff[1], ff[2, 3], ff[4, 5]}, {ff[1, 2],
ff[3], 
    ff[4, 5]}, {ff[1], ff[2, 3, 4], ff[5]}, {ff[1, 2], ff[3, 4], 
    ff[5]}, {ff[1, 2, 3], ff[4], ff[5]}}

In[9]:= myReplaceList[f[1, 2, 3, 4, 5] , f[x_, y_, z_] :> {x, y, z}] //
Sort
Out[9]=
{{f[1], f[2], f[3, 4, 5]}, {f[1], f[2, 3], f[4, 5]}, {f[1], f[2, 3, 4], 
    f[5]}, {f[1, 2], f[3], f[4, 5]}, {f[1, 2], f[3, 4], f[5]}, {f[1, 2,
3], 
    f[4], f[5]}}

(I beg your pardon, for not giving the output in the same order, but
certainly -- if we only wanted -- we could do so, at some cost. Yet this
is not the point here, as well as the fact, that I didn't treat "myFlat"
inside of the rules!)

We also redo the example as quoted from The Book: 

In[10]:= ff[a, b, a, b] /. ff[x_, x_] -> rp[x]
Out[10]= rp[ff[a, b]]

In[11]:= myReplaceList[f[a, b, a, b], f[x_, x_] -> rp[x]]
Out[11]= {rp[f[a, b]]}

So here we also get the same.

Now we run through a sequence of tests:
 
In[12]:= ReplaceList[ff[ff[1, 2]] , ff[x_] :> {x}]
Out[12]= {{ff[1, 2]}}

In[13]:= myReplaceList[f[f[1, 2]] , f[x_] :> {x}]
Out[13]= {{f[1, 2]}}

In[14]:= ReplaceList[ff[ff[1, 2]] , ff[x : _ff] :> {x}]
Out[14]= {{ff[1, 2]}}

In[15]:= myReplaceList[f[f[1, 2]] , f[x : _f] :> {x}]
Out[15]= {{f[1, 2]}}
 
In[16]:= ReplaceList[ff[ff[1, 2]] , ff[x : ff[__]] :> {x}]
Out[16]= {}

In[17]:= myReplaceList[f[f[1, 2]] , f[x : f[__]] :> {x}]
Out[17]= {{f[1, 2]}}

different behaviour here!
 
In[18]:= ReplaceList[ff[ff[1, 2]] , HoldPattern[ff[ff[__]]] -> "match!"]
Out[18]= {}

In[19]:= myReplaceList[f[f[1, 2]] , HoldPattern[f[f[__]]] -> "match!"]
Out[19]= {"match!"}

again different!
----------------------------------------------

I think, that the model corresponds more to our expectations as
suggested with the documentation. So let's say we have a "documentation"
error. Yet my greatest critique of The Book is that it is sometimes sort
of vague or evasive as e.g. on page 272:

"Whenever Mathematica encounters an orderless or commutative function
such as Plus or Times in a pattern, it effectively tests all the
possible orders of arguments to try and find a match."

What does "effectively" mean? The model shows there are cases where it
is not "effective". 

It is this vagueness, I really deplore.


Kind regards,  Hartmut


  • Prev by Date: Re: Flat, OneIdentity Again
  • Next by Date: lat,long to UTM coordinate conversion
  • Previous by thread: Re: Flat, OneIdentity Again
  • Next by thread: Re: Flat, OneIdentity Again