14
$\begingroup$

I'm trying to write an expression deconstructor or FullForm-capturer; might even call it a parser, maybe, but that might be too glorious a word.

I got some great ideas from "Head and everything but...", but have plunged headlong back into the fog of my own limited understanding again, which got even foggier when I tried to understand "...function arguments on a stack...". I'd be most grateful for ideas, advice, and more clarity.

Consider this example: a + b + c. We know its FullForm is Plus[a, b, c], and I can "capture" that FullForm in a List with something like

Cases[{a + b + c}, head_[args___] -> {head, args}]

which produces

{{Plus, a, b, c}}

Now I go get myself all drunk on recursion and think I can write

SetAttributes[capture, HoldAllComplete];
capture[expr_?AtomQ] := {Head@expr, expr};
capture[head_[args___]] := {head, capture /@ {args}};

so that something like capture[a + b + c] gives me fantastic detail

{Plus, {{Symbol, a}, {Symbol, b}, {Symbol, c}}}

or, in stunningly beautiful TraditionalForm

$\left\{\text{Plus},\left( \begin{array}{cc} \text{Symbol} & a \\ \text{Symbol} & b \\ \text{Symbol} & c \\ \end{array} \right)\right\}$

All is well till I try

capture[1 + 2 + 3] ~~> {Integer, 6}

OH NO, it's not Holding inside! What I want, of course, is

$\left\{\text{Plus},\left( \begin{array}{cc} \text{Integer} & 1 \\ \text{Integer} & 2 \\ \text{Integer} & 3 \\ \end{array} \right)\right\}$

My problem is revealed by traceView2, which I got from "... clearest way to represent ..."

Trace of offending call

We see that 1 + 2 + 3 arrives held to AtomQ, as expected, but greedy old evaluator grabs it right there and smooshes it into 6. Everywhere else in the trace, the same thing happens. I don't know an easy way to stop the evaluator inside my capture faction.

It has occurred to me to copy and adapt the code of traceView2 to my application, since it exploits Trace to get ahead of the evaluator, and I will proceed that way unless I receive a cool answer here. In my dreams I imagine something like

SetAttributes[capture, DudeReallyHoldAllCompleteEverywhere];

or

SetAttributes[capture, HoldAllComplete, Levels -> Infinity];
$\endgroup$
1
  • 1
    $\begingroup$ Oh, sorry, that's my made-up meta-notation for "produces". It's not part of Mathematica, it's my secret abbreviation for my descriptions of Mathematica. $\endgroup$
    – Reb.Cabin
    Mar 9, 2012 at 14:28

2 Answers 2

16
$\begingroup$

Ok, what you have here is some classic example of what is called "Evaluation leaks". So, first, the corrected code:

ClearAll[capture]
SetAttributes[capture, HoldAllComplete];
capture[expr_ /; AtomQ[Unevaluated[expr]]] := 
    {Head[Unevaluated[expr]], expr};
capture[head_[args___]] := {head, capture /@ Unevaluated[{args}]};

Now, you can inspect it and compare to your version, to see that you had three such "leaks": in the pattern-testing AtomQ (which does not hold its arguments), in the r.h.s. Head[expr], since Head also does not hold them, and, perhaps most importantly, in capture/@{args}, since Map does not hold its arguments either.

So, evaluation leaks are cases when some code which wasn't supposed to evaluate, actually does. Some most frequent situations which lead to evaluation leaks are either when the code is being passed to / anylized by a function which does not hold it properly, or when some parts of held code are extracted during destructuring (e.g. by Cases), not being wrapped in a holding wrapper head.

The standard thing to do to prevent the evaluation once is to wrap your code in Unevaluated, which I did above. To prevent evaluation in a persistent manner, we usually wrap an expression in Hold, HoldComplete, or perhaps some custom holding wrappers with Hold-attributes, but in such cases you have to take care to strip the holding wrapper when no longer needed.

Some more involved examples of parse-like functions which avoid evaluation leaks can be found in this answer (function depends) and also here (function parse). The problem of evaluation leaks is a very frequent one once you start working with pieces of unevaluated code, which is particularly common when writing parser-like functions, macros, and other metaprogramming-related functions. You can look at some references in my recent answer on metaprogramming, for some more links to code where prevention of evaluation leaks was essential.

$\endgroup$
7
  • $\begingroup$ Some slight confusion -- I notice you did NOT write capture[head_[args___]] := {Unevaluated[head], .... Indeed, I checked it out with f[x_]:=3;capture[f[42]g[a]] and I get {Times, {{f,{Integer,42}},{g,{Symbol,a}}} implying that, in the R.H.S. of capture[head_[args___]] := {head, ..., head is NOT evaluated. Why not? Doesn't List not Hold its arguments? I'm slightly confused. (I think an extra Unevaluated wrapper would be harmless documentation, wouldn't it?) $\endgroup$
    – Reb.Cabin
    Mar 9, 2012 at 1:15
  • 1
    $\begingroup$ @Reb.Cabin Well, head surely is evaluated, so, had you assigned say f=1, and you would have that evaluated. It is just that in these cases, head was a symbol not having a value, so it evaluated to itself. I left head to evaluate since I thought you wanted it that way. In fact, to cover also composite heads, the proper way would be this: capture[head_[args___]] := {capture[head], capture /@ Unevaluated[{args}]}. I am off to bed now, but feel free to edit my post and replace capture with this code, if you feel this better addresses your goals. Thanks for the accept b.t.w. $\endgroup$ Mar 9, 2012 at 1:24
  • $\begingroup$ very nice! you are really helping to clear my fog! $\endgroup$
    – Reb.Cabin
    Mar 9, 2012 at 1:29
  • $\begingroup$ @Reb.Cabin Glad I could help. I love this type of questions :) $\endgroup$ Mar 9, 2012 at 1:30
  • 1
    $\begingroup$ @Reb.Cabin An atom may be a symbol holding a value, in which case Unevaluated[expr] is not the same as expr. The question is then, what behavior you want. Perhaps, {Head[Unevaluated[expr]], expr} may be more confusing in this case, but {Head[expr], expr} may also be confusing. Try experimenting to see what I mean. Sorry, I am really not here already :) $\endgroup$ Mar 9, 2012 at 1:56
4
$\begingroup$

A very useful idiom for avoiding evaluation leaks is:

foo= Function[{expr, pattn, levels},  
  Extract[Unevaluated[expr], Position[Unevaluated[expr], pattn, levels], HoldComplete], {HoldAllComplete}]

This function foo finds parts of expr at specified levels that match pattn and most important it wraps them in HoldComplete before they get a chance to evaluate. Example usage:

foo[2*12/(Sqrt[6+3]+1), _Plus, {1,-1}]

{HoldComplete[Sqrt[6+3]+1], HoldComplete[6+3]}

EDIT An earlier version didn't work because I didn't have the first argument of Position wrapped in Unevaluated. That is fixed above and I had a chance to verify that it works.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.