What is this definition of orthogonality in programming language trying to convey?

Question

My book Sebasta's Concepts of Programming Language (Chapter 1) states:

Orthogonality in a programming language means that a relatively small set of primitive constructs can be combined in a relatively small number of ways to build the control and data structures of the language. Furthermore, every possible combination of primitives is legal and meaningful. For example, consider data types. Suppose a language has four primitive data types (integer, float, double, and character) and two type operators (array and pointer). If the two type operators can be applied to themselves and the four primitive data types, a large number of data structures can be defined.

This explanation feels too contrived, can someone boil it down for me? What does "type operators can be applied to themselves" mean and how does that lead to a large number of data structures? I am not sure I undestand the first sentence as well.

Answer 1

There's an iceberg of concepts here.

By "type operators", the author roughly means the methods by which arrays or pointers are created. By "applying type operators to themselves", the author basically means that pointers can be created which point to pointers, and arrays can be created which contain arrays.

The notion of "type operators" only really makes sense if you're thinking in terms of an algebra of types.

For example, int * int means a structure consisting of a pair of ints (or equivalently said, an array of ints of length 2) - the star is the multiplication operator, but its operands are type literals, rather than variables, meaning that we are operating on the constraints which types impose, rather than upon the values which a variable contains.

And int + char means (roughly) a variant containing either an int or a char. The reason the addition operator is used is because if you created a table of all possible values a variable with this type can hold, then that table would consist of all possible int values plus all possible char values. The variable will be assigned with one value from amongst these combined possibilities.

Becoming more complicated, something like (int * (int * char)) could mean a structure containing an int, and a sub-structure containing an int and a char.

Also, people familiar with SQL might understand these operators as being (respectively) like 'cross join' and 'union all', as applied to tables of possible values associated with each type literal, although I'm not sure how soundly this analogy will be perceived.

Answer 2

double
array of floats
pointer to character
array of pointers to arrays of integers
array of array of pointers to pointers to double
...