Is expression in Mathematica well defined?

Question

According to Mathematica, everything is an expression. So an atom is also an expression. But in other parts of documentation, they say that an expression is of form Head[e1,e2,..]. This is a contradiction since an atom does not have that form. Confused.

To express more clearly what I mean look at the following statements.

1. An atom is an expression.

2. All expressions have the form Head[e1,e2,..]

3. Expressions of type Head[e1,e2,..] have parts

4. An atom does not have parts.

These 4 statements are contradictory.

If 2. would say that Some expressions have the form Head[e1,e2,..], then there would not be a problem. Then we could say that some expressions are atomic (like number 7) and some (like Plus[2,3] are nested (or molecular or whatever is the right word).

In that case I would express the whole situation as follows:

We should distinguish between two types of expressions: atomic expressions and nested expressions.

An expression is a tree structure. An atom is leaf ( a node with no children) while nested expressions have also branches (a node with children).

Mathematica comes with a bunch of primitive elements. About a dozen atoms (like numbers, strings, etc) and several thousends of built in functions (like Plus, Plot, Module, etc).

The main purpose of nested expressions is to COMBINE atoms and other nested expressions into new expressions. Since an argument of a nested expression can itself be an expression it gives us enormous combinatorial power to build new expressions (that themselves can behave like built in functions, inside our session, or otherwise taking proper care to put them into packages that can be imported).

Answer 1

John Doty's answer says it very well:

Even atoms have heads, they just aren't normally displayed, even in FullForm.

I'll also respond to OP's comment:

J.M.: Look at e.g. AtomQ[Rational[1, 2]] or AtomQ[Complex[1, 3]]

OP: In your example you use Rational and Complex, but the same does not work for Integer, Real, String and Symbol. For instance AtomQ[Integer[3]] gives false, and Integer[3] does not evaluate to 3, but Rational[1,2] does evaluate to 1/2. Still confused.

I think the issue is that certain 'atomic heads' act as constructors. This is certainly true for things like Graph and Association, and appears to be true for Complex and Rational as well. Such constructors take certain inputs and turn them into atoms

Complex[1,2] // AtomQ  (* True -- proper input converted to atom *)
Complex[a,b] // AtomQ  (* False -- improper input not converted *)

It should be emphasized that an expression which has an 'atomic head' is not necessarily an atom.

As JM implicitly notes in a comment, Symbol acts as a constructor, but it expects a string -- e.g., Symbol["x"].

Your comment boils down to the fact that Integer, Real, and String do not act as constructors. This is presumably because it's sufficiently nice to input these objects already, though I agree that it doesn't seem entirely consistent.

_{Slight aside: Note that while Rational[1,2] appears to evaluate to 1/2, its FullForm remains Rational[1,2] (as opposed to something involving Times).}

---

References: WReach's answer discussing pitfals of Association acting both as an atomic head and a constructor.

Answer 2

Even atoms have heads, they just aren't normally displayed, even in FullForm.

Head[1]
(* Integer *)
Head[Symbol]
(* Symbol *)

Answer 3

As @jjc385 nicely writes, the confusing part is, that some atomic heads serve as constructors. In the end the main feature of any atomic expression is, that while it may well be of the form $h[e_1, e_2]$ (e.g. the case with Rational[ 1, 2 ]), we can only extract the head and we cannot replace its parts (cf. Tutorial "Basic Objects: Atomic Objects", where special selectors are given to extract parts of atoms, e.g. IntegerDigits.)

So note:

Rational[ 1, 2 ][[2]]

Part specification is longer than depth of object.

expr[ 1, 2 ][[2]]

2

Rational[ 1, 2 ] /. Rational -> Complex 

$\frac{1}{2}$

expr[ 1, 2 ] /. expr-> Complex

$1 + 2i$

a = Rational[ 1, 2];
FullForm[ a ] /. Rational -> Complex

Rational[ 1, 2 ]

b = expr[ 1, 2 ];
FullForm[ b ] /. expr-> Complex

Complex[ 1, 2 ]

But since the constructors have to be evaluated before we get an atomic expression, we can do:

HoldForm[ Rational[1, 2] ] /. Rational -> Complex  // ReleaseHold

$1 + 2i$

Update

With more elaborate atomic expressions like Association the above given indications for an atomic expression (e.g. no extraction of parts) are blurred:

assoc = Association[ "1" -> e1, "2" -> e2 ]; AtomQ @ assoc

True

But now:

assoc[[1]]

e1

So here Part is a valid selector for the atomic expression Association. It may thus be indivisibility which is the more general attribute for an atomic expression?

Partition[ h[ e1, e2], {1} ]

h[ h[e1], h[e2] ]

Partition[ assoc, {1} ]

The expression [...] cannot be partitioned.

TL;DR

It seems, that atomic expressions may sometimes (especially with later releases of Mathematica) be of the form $h[e_1, e_2, ...]$ and so have parts, but the subcomponents ($e_1, e_2, \ldots$) generally cannot be extracted by using functions like Part or subdivided using functions like Partition. Instead extraction and subdivision then have to be handled by dedicated selectors.

Answer 4

"Everything is an expression."¹. "Expressions can be written in the form h[e1,e2,…]. The object h is known generically as the head of the expression. The ei are termed the elements of the expression. Both the head and the elements may themselves be expressions"², meaning that "all expressions—whatever they may represent—ultimately have a uniform tree-like structure"³ whose internal nodes are heads and external nodes (a.k.a. leaves) are atomic objects.

In more details, "all expressions in the Wolfram Language are ultimately made up from a small number of basic or atomic types of objects" (Symbol, String, Integer, Real, Rational, Complex).⁴ "These objects have heads that are symbols that can be thought of as "tagging" their types. The objects contain "raw data", which can usually be accessed only by functions specific to the particular type of object. You can extract the head of the object using Head, but you cannot directly extract any of its other parts."⁴ The elements of an atomic object (the raw data) are "stored directly as a pattern of bits in computer memory."⁵

In addition to bolding some text above, to answer your question directly, I would add that an atomic object is an indivisible expression (in our expressionism formalism) whose elements consist of raw data tagged by the head of the expression enabling higher level heads to interpret and manipulate the mentioned raw data. In this formalism, heads are symbolic representations of computation.

References

1. Everything Is an Expression
2. Basic Objects > Expresion
3. Expression Structure
4. Basic Objects > Atomic Objects
5. Basic Internal Architecture