[Date Index]
[Thread Index]
[Author Index]
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**
| |