MathGroup Archive 1995

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

Search the Archive

Re: Crossreference, code documentation

  • To: mathgroup at christensen.cybernetics.net
  • Subject: [mg1665] Re: Crossreference, code documentation
  • From: wagner at bullwinkle.cs.Colorado.EDU (Dave Wagner)
  • Date: Tue, 11 Jul 1995 04:17:14 -0400
  • Organization: University of Colorado, Boulder

In article <3ti1v0$klt at news0.cybernetics.net>,
Count Dracula  <lk3a at kelvin.seas.virginia.edu> wrote:
>
>In Message-ID: <3tahhp$6bb at news0.cybernetics.net> 
>wagner at bullwinkle.cs.Colorado.EDU (Dave Wagner) writes:
>
>> This function finds all symbols in an
>> expression without allowing anything to evaluate:
>> 
(snip)
>
>This functionality is more simply achieved, without resorting to
>recursion, by the function  findsym  :
>
>  SetAttributes[{findsym, WrapAll}, HoldAll]
>
>  findsym[expr_] := Union[ Cases[Level[WrapAll[expr], {0, Infinity}, Heads -> True],
>                          Hold[x_Symbol] :> HoldForm[x]] ]
> 
>  WrapAll[expr_] := First[Map[ Hold, Hold[expr], Infinity, Heads -> True ]]

Well, now that the gauntlet has been thrown down... :-)

The use of Level is really clever; I never would have thought of it.
However, now that I'm spurred on to find a better solution, I came up
with this one, which isn't as fast as Levent's but is, I think,
very easy to understand:

    SetAttributes[FindSymbols2, HoldFirst];
    SetAttributes[myHold, HoldAll];
    FindSymbols2[expr_] :=
	Union[ Cases[ Flatten[
		    myHold[expr] //. f_[x___] :> myHold[f,x] /; f=!=myHold
	    ], x_Symbol->HoldForm[x]]
	]

The ReplaceAll followed by Flatten does the job of Levent's combination
of Map and Level; the rest is essentially identical to his function.
The reason for using the myHold function rather than Hold is so that
the function will find occurrences of Hold within expr.

I find this function to be about half as fast as Levent's:

In[72]:=
    test := findsym[P[{x, f[f[g[a], b], b, h[c], f]}] + 
	Sin[x + Pi y] Log[c] Exp[I x + u]/(9 Integrate[Pi x, {x, 0, 2}])]

In[73]:=
    Timing[test]
Out[73]=
    {0.0166667 Second, {a, b, c, Exp, f, g, h, I, 
       Integrate, List, Log, P, Pi, Plus, Power, Sin, 
       Times, u, x, y}}

In[76]:=
    test2 := FindSymbols2[P[{x, f[f[g[a], b], b, h[c], f]}] + 
	Sin[x + Pi y] Log[c] Exp[I x + u]/(9 Integrate[x Pi, {x, 0, 2}])]

In[77]:=
    Timing[test2]
Out[77]=
    {0.0333333 Second, {a, b, c, Exp, f, g, h, I, 
       Integrate, List, Log, P, Pi, Plus, Power, Sin, 
       Times, u, x, y}}

I should remark at this point that the original function was an
example of using recursion and of operating on Held expressions.
At that point in the book, the reader has not yet been exposed to
rule-based programming.  However, now I think I'll revisit the
problem in the rule-based chapter to present the second solution.

Speaking of rule-based solutions to the problem, Jason Harris suggested
this to me:

goodSymb @ a_Symbol := True /; "System`" != Context @ a 
goodSymb @ other___ := False

FindSymbols3[expr_]:=
  Block[{ symbs = {} },
    MapAll[findAux,expr,Heads -> True]//.
      {findAux @ a_?goodSymb @ args___ :> addIt /; AppendTo[symbs, HoldForm @ a],
       findAux @ a_?goodSymb           :> addIt /; AppendTo[symbs, HoldForm @ a],
       findAux @ other___              :> other};
    Union @ Flatten @ symbs]

Jason's solution is a bit slower than mine, but it illustrates an
interesting technique, namely, building up a list of results as a
*side-effect* of applying a rule.  In retrospect, I think that I like
the idea of building up the result in-place and then using Cases to
extract the relevant parts much better.

Note also that Jason filters out System-defined symbols using the goodSymb
predicate.  I thought that this might be slowing things down, but replacing
_?goodSymb with _Symbol seemed to have no effect.  However, the result returned
by his function (so modified) is subtly different from Levent's and mine:

FindSymbols4[expr_]:=
  Block[{ symbs = {} },
    MapAll[findAux,expr,Heads -> True]//.
      {findAux @ a_Symbol @ args___ :> addIt /; AppendTo[symbs, HoldForm @ a],
       findAux @ a_Symbol           :> addIt /; AppendTo[symbs, HoldForm @ a],
       findAux @ other___              :> other};
    Union @ Flatten @ symbs]

In[102]:=
    test4 := FindSymbols4[P[{x, f[f[g[a], b], b, h[c], f]}] + 
	Sin[x + Pi y] Log[c] Exp[I x + u]/(9 Integrate[x Pi, {x, 0, 2}])]

In[103]:=
    Timing[test4]
Out[103]=
    {0.133333 Second, {a, b, c, Complex, E, f, g, h, 
       List, Log, P, Pi, Plus, Power, Rational, Sin, 
       Times, u, x, y}}

Note that Jason's modified function picks out Complex and Rational, but
the other two functions pick out I.  Also, Jason's function picks out E,
whereas the other two pick out Exp.  I haven't yet broken things down
step-by-step to figure out why.

As some of you may have guessed by now, my secret agenda is to post my
entire book to this newsgroup 10 lines at a time, thus getting a
near-infinite amount of free reviewing! :-)

		Dave Wagner
		Principia Consulting
		(303) 786-8371
		dbwagner at princon.com
		http://www.princon.com/princon


  • Prev by Date: Re: I'm looking for an algorithm: Cartesian Product
  • Next by Date: Re: rhs of SetDelayed
  • Previous by thread: Re: Re: Crossreference, code documentation
  • Next by thread: Re: Crossreference, code documentation