18
$\begingroup$

Can we say Head[x] and x[[0]] are identical ?

In mathematica manual I could find : 'The head is the part with index 0'

whose

But I am not sure whether Head[x] are x[[0]] are really interchangeable in any case

Is there a case results are different ?

$\endgroup$
5
  • 9
    $\begingroup$ Often the same but not always: Head[SparseArray[{1, 2}]] vs. SparseArray[{1, 2}][[0]]. $\endgroup$
    – Michael E2
    Mar 21, 2021 at 0:47
  • 1
    $\begingroup$ @MichaelE2 Great example! However, I tend to believe that this behavior was not intended by the developers. At least, I cannot find any reasons other then an "accident" why they implemented it this way. I also used to think of Head[x] == x[[0]] to be an "axiom" of Mathematica, at least for standard language expressions. And "Properties&Relations" on Head state that "The head is the part with index 0" and "Head[e,f] is effectively equivalent to Extract[e,0,f]". $\endgroup$ Mar 21, 2021 at 9:42
  • 1
    $\begingroup$ SparseArrays are atomic and the head is basically a wrapper for a complex data structure more on the "C-side" of Mathematica. So standard language behavior has to be emulated. I think something went wrong there. $\endgroup$ Mar 21, 2021 at 9:42
  • 5
    $\begingroup$ @Henrik Array-like atomic expressions often overload Part. SymmetrizedArray also gives different results for the head and part 0, and different from SparseArray for reasons I can’t fathom. The sparse array behavior seems rational to me: With respect to Part, SparseArray should behave like List, even part 0; Head should always give the head of an expression. I think the docs on Head are simply outdated. It used to be that way, but then they introduced composite atomic expressions like SparseArray, which I don’t like but the programmers on this site say is a great improvement. $\endgroup$
    – Michael E2
    Mar 21, 2021 at 12:38
  • 1
    $\begingroup$ @MichaelE2 I only saw your comment after posting my answer. But you are not alone in not liking the business of atomic expressions. $\endgroup$ Mar 21, 2021 at 13:09

1 Answer 1

17
$\begingroup$

Preamble

The biggest problem with Head seems to be that it plays two distinct, although related, roles in the language:

  • The 0 - th element of an expression
  • The type of an expression

Both expressions and types in WL have their own issues.

Types and expressions

Simple type model

First of all, while WL is a dynamic untyped language, types certainly exist and do play a role. On the surface, the standard distinction between primitive and composite types in many mainstream languages gets translated into the distinction between atomic and normal expressions in WL.

Standard atomic types would include Integer, Real, Complex, String, and Symbol. In the oversimplified model of WL types, all other types are composite. Given the generality of expressions, the type is identified with the head of an expression, which purely structurally is a symbol used as a container for elements, for normal expressions:

head[e1, ..., en]

and has the part index 0.

Atomic built-in primitive types

Already here we start seeing a problem, since for example, atomic integer doesn't seem to have parts. Still, the convention has been made, that they have the zero'th part, so that this general mapping still holds:

(* 1[[0]] *)

(* Integer *)

So already at this point, there is a clash between types and structural representation of expressions. And since one can always use Part to structurally deconstruct expressions, we may conclude that Head has more to do with the notion of expression type, than simply being a short-cut for Part[expr, 0].

Atomic composite objects

There are, however, more complex cases. WL has a number of built-in types, which are essentially composite - but yet made atomic (in the sense of AtomQ predicate) by the language. These include Graph, Association, SparseArray, ByteArray and a number of others.

The problem with these is that their FullForm may suggest the behavior of various structural operations (such as Part, Length, Map, etc.) very different from the actual behaviors of these functions, that make sense for these objects. As I mentioned in my other answer to a somewhat related question, this discrepancy is, in a way, a breakdown of the "everything is an expression" principle in its direct interpretation.

The possible breaking of the mapping Head -> expr[[0]] is an instance of this general discrepancy - there is no good reason why a type of an expression (whatever is understood by it) should always be its 0th element - except by a convention. However, in most cases the designers of WL have been careful not to break this rule.

Problems with subtyping

While the notion of type in WL isn't very well defined, and in fact Head of an expression is probably the most general way to define its type universally, the situation is even worse for subtyping.

The problem is most prominent with lists. There are several built-in objects in WL, which are lists or should behave like lists in many cases. Some of them are:

  • Normal Lists (head List)
  • Packed arrays (numerical lists with optimized storage and API)
  • Sparse arrays (lists with optimized storage format, head SparseArray)
  • Byte arrays (essentially, lists of bytes, head ByteArray)

Here is a problem then: since the convention says, that Head should be always identical to expr[[0]], then someone could, to test for a list, use code like the following:

If[expr[[0]] === List, 
    ...
]

If one now wants the sub-types of a list (such as packed arrays, sparse arrays, byte arrays, etc) to work with such code automatically, one is forced to impose semantics which leads to this:

SparseArray[{1, 2}][[0]]
ByteArray[{1, 2, 3}][[0]]

(* 
   List

   List 
*)

Which now breaks the identity Head[expr] === expr[[0]] for these expressions / types.

In other words, keeping the identity for main type and insisting that subtyping just works, one necessarily breaks the identity for subtypes - apparently because there is no formal way to define types and subtypes in WL, which would allow the language to have something like instanceof operator.

Given that historically Lists appeared first, together with this identity as a general rule, one can't afford to break the code like the above If statement - it could have been in many places even by the time PackedArrays arrived, not to mention later additions like SparseArray, ByteArray etc.

Summary

The function Head is WL's way to define / determine a type of a given WL expression.

The key identity

Head[expr] === expr[[0]] 

holds for the majority of WL expressions, even though it is the most natural for normal expressions only, while for atomic objects it holds mostly by convention.

However, the key identity above is at odds with some deeper aspects of types, which are relevant for WL even though WL is not a strongly typed language. In particular, there seems to be no way to keep both this identity and make subtyping work. This seems to really be the problem of WL design, where subtyping (and other slightly deeper aspects of types) have not been taken into account seriously enough, and in particular, the design path that would reconcile subtyping / types and WL expressions, wasn't found.

$\endgroup$
4
  • 2
    $\begingroup$ Thank you Leonid for sharing your insights (+1). However, I do not share your opinion that subtyping is not possible without breaking Head[expr] === expr[[0]] . For example, VectorQ, MatrixQ, and TensorQ all work with List, SparseArray, and SymmetrizedArray. So it would have been easy to devise a function like ListlikeQ. That is subtyping can be done by creating a new head and by hardcoding the answers to several Q-like functions. $\endgroup$ Mar 21, 2021 at 14:24
  • $\begingroup$ @HenrikSchumacher Right, predicates like these alleviate the problem to some extent, but this is not true subtyping. In my book, this is at best the poor man's subtyping. The true subtyping would require formal general notions of type and subtype, as well as mechanism to define new types as subtypes of other types, in the core language. Even in the case of lists that I was discussing, I think that the decision to break the identity was made totally consciously as the least evil, so that subtyping keeps working. The need to define a bunch of Q - predicates to me is a lack of real subtyping. $\endgroup$ Mar 21, 2021 at 14:29
  • $\begingroup$ @HenrikSchumacher But I think the problem of subtyping is a specific case of a general problem of types in WL - they have no formal grounds / support, there is no built-in way to create new types / ADTs (there are recipes how to emulate it, but it's not the same thing). I think that originally the designers of WL thought that the general notion of expressions is enough for all this, but this is where I disagree with the design of WL as a general-purpose PL, as opposed to a computer algebra system. $\endgroup$ Mar 21, 2021 at 14:33
  • $\begingroup$ @HenrikSchumacher Perhaps, what I really wanted to say is that as long as we interpret Head[expr] as a definition of expression type, the identity Head[expr] === expr[[0]] is too strict and kind of meaningless, being just a heritage of the initial design where it was believed that the "everything is an expression" principle can work in its direct interpretation (the times where there were no atomic composite objects and other complications). $\endgroup$ Mar 21, 2021 at 14:48

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.