Trace of -{1} expression

Question

I'm trying to understand Trace. Usually it doesn't repeat but it adds {-1,-1} for his simple expression after having a correct result.

-{1}//Trace

{-1, {-1}, {-1, -1}, {-1}}

Why -{1}//Trace is longer than -Range[1]//Trace?

Answer 1

This is a good question for uncovering an important difference between listability and vectorization. Sometimes these terms are used interchangeably, but I would like to make a technical distinction. In both Listable and vectorized functions, the value of the function on a list is equal to values of the function on each element of the list. From the theoretical point of view of a function is defined by its values, there is no difference, but on practical grounds, there is a difference in how efficiently a function is computed. A function is vectorized if it treats a vector (or array) as if it were atomic. The ability to do this depends on the architecture of the CPU; it is implemented in Mathematica by packed arrays (see this technical note by Rob Knapp, this Q&A and this one). Generally speaking, when a packed array is passed to a function that is not vectorized, the array will be unpacked (search the site, or perhaps start here).

The difference one sees in the Trace of -{1} and -Range[1] is due to Range[n] being a packed array. For the most part, the difference between the listability and vectorization is invisible to the user. One sees it mainly speed, memory usage, and in this case the evaluation sequence exposed by Trace. One can also test whether a list is a packed array with Developer`PackedArrayQ. One can trace unpacking with On["Packing"]. Aside these tools, I do not think that it is possible for a user to define a function of the form f[...] :=... that is both Listable and vectorized; the user's only option is to write a non-Listable function in terms of built-in vectorized functions or use Compile (or perhaps write a LibraryFunction). In other words, if one sets SetAttributes[f, Listable], the listability attribute is applied first: f[{x1, x2,...}] becomes {f[x1], f[x2],...} before f is evaluated, which will unpack a packed array. But in the OP's example, with Times, which is Listable, this does not happen. It is similar with Plus and other vectorized functions. It must be that there are internal rules that are applied for such functions, shadows of which show up in Trace, but which are not explained in the documentation (AFAIK).

We can see the above in the OP's examples. One gets a more complete picture of the evaluation sequence with Trace[expr, TraceOriginal -> True] (TracePrint, mentioned by @J.M., also shows more). Even further, the differences are somewhat more convincing comparing the examples -{1, 2} and -Range[2]. But I deal with the OP's examples and let the reader explore the rest.

In -{1}, the Listable attribute is applied first, the first two steps of -{1} // Trace:

Times[-1, List[1]]
List[Times[-1, 1]]

In -Range[1], the vectorization can be seen in the transformation from the third to fourth step:

Times[-1, List[1]]
List[-1]]

What is invisible is that List[1], the result of Range[1] is a packed array, whereas List[1], the "result" of {1}, is not. This difference may be verified by executing the following:

{1} // Developer`PackedArrayQ
Range[1] // Developer`PackedArrayQ

One can see the same listability step applied if Range[1] is unpacked, which can be done with the function Developer`FromPackedArray:

-Developer`FromPackedArray@Range[1] // Trace

Addendum: Help with reading Trace output.

WReach's traceView2 is a wonderful function for presenting the evaluation sequence.

Here is another function for formatting Trace output. The output consists of nested lists corresponding to the depth of the evaluation stack. The following indicates each level by grouping and indenting its items.

Clear[fmt, ifmt];
fmt[x_] := Block[{fmt`step = 0}, ifmt[x]];
ifmt[s_List] := Row[
   {Style[RawBoxes@"{", SpanMaxSize -> Infinity],
    " ",
    Column[ifmt /@ s]}];
ifmt[x_] := Row@{Style[++fmt`step, Italic, "Label"], ". ", FullForm /@ x};

Op's examples:

-List[1] // Trace // fmt

-Range[1] // Trace // fmt

Trace[expr] omits some steps of the evaluation such as the Head of each expression. Trace[expr, TraceOriginal -> True] shows more.

Exercises.

Compare these with each other and with the ordinary trace above.

Trace[-List[1], TraceOriginal -> True] // fmt
Trace[-Range[1], TraceOriginal -> True] // fmt

Examine these (I think the difference between listability and vectorization is even more obvious):

Trace[-List[1, 2], TraceOriginal -> True] // fmt
Trace[-Range[2], TraceOriginal -> True] // fmt