Is there a generally agreed short notation for “a points to b”

Question

Is there a conventional symbol for "points to" or "is a pointer to". I've been using a short right arrow; for example "a is a pointer to b" would be (approximately)

a -> b 

but I wonder whether a short double right arrow would be better:

a => b

Best of all would be to know, and use, a universally-accepted standard symbol, if there is one?

Answer 1

The problem with your question is that pointers and pointers semantics may vary significantly from language to language. Even your question is ambiguous. So you are asking a question about notation, i.e., about syntax, which is largely a matter of arbitrary convention, but it is not even clear what is the semantics intended by your question.

You apparently use as synonyms "a points to b", "a is a pointer to b", "a -> b". But I am not sure what is the meaning and context. Does it assert that a is actually pointing to b (descriptive meaning) or does it modify the data so that a is now pointing to b (imperative meaning). Then what is b, or what can b be. Is it the location of some value, or is it the value of whatever is pointed by a. Is it intended to be part of a programming language syntax, or of the metalanguage used to discuss about programs.

If you have a -> b and c -> b, does it imply that a = c. Furthermore, if a and c are pointers, what is the meaning of a = c? See for example "shallow and deep equality".

Actually all this is often an issue of designation of container and content. A pointer is a designation for a container (a memory location, for example), and the content of that container may vary. But the content may also include container designation.

One major problem is that notations are often ambiguous as they often do not clearly distinguish between container and content, often implicitly casting one into the other.

If you consider a variable, say an integer variable x in some programmning language, this variable is actually a container where you can change the content (which is supposed to be an integer). But, within the scope of its declaration, x will always be the same container. An integer variable is actually a pointer constant: a location designator.

Then, can you write x -> 3 to indicate that x denotes a pointer constant toward a location containing the value 3?

Or is the arrow supposed to point on the right to whatever container is "designated" by the expression on the left. But if you have a pointer constant (i.e. a pointer value) on the left, what is the meaning of the notation.

Now, you can have pointer variables, which may contain a container. They can appear through explicit declaration, or via other mechanism such as parameter passing by reference.

When sharing a meal with other people, you can ask for the bottle or for the wine. It will mean the same. But in programming context, more precision may be needed.

So my first reaction to your question is: Could you be more precise about the semantics you intend to express, before you suggest agreeing on a standard notation?

Another minor point is that, while asking your question, you seem to suggest that a double shafted arrow => would be better than a single shafted on ->. But you do not give any hint as to why it might be better. This makes me uneasy, especially wen I am not even sure of what you want to talk about, and in what context.

Since this is supposed to be an answer rather than further questions, I would suggest that the lack of a standard may well come from the fact that programming languages vary significantly in their use of pointers, and on the semantics attached to various constructs using pointers. We can hardly standardize notation when what is to be denoted is not itself standardized.

Hence, our only recourse is to choose for ourselves a notation that is intuitive and consistent in its intended context, and define it precisely together with the associated semantics. I insist on consistency since there are many things you may want to do with pointers, and it is important that the notations for each remain intuitive, and that they combine naturally and consistently. The issue of equality is an example.

Answer 2

No. There is no standard, accepted notation. Different papers tend to use different notations. So, choose one that is suitable for your needs and define it before using it.

Here are some examples of notations I've seen used, in different contexts:

• I've seen some papers on points-to analysis use $\text{pt}(v)$ to refer to the set of objects that $v$ might point to. This allows you to write $b \in \text{pt}(a)$ if you want to say that $a$ points to $b$. This is convenient in that domain, because points-to analysis is a "may" analysis: for each variable $v$, it keeps track of all the objects that $v$ could potentially point to (along some feasible path of the program).

• As another notation, in some papers I've seen people draw heap graphs, where each vertex represents a variable and each edge represents a points-to relationship.

• As yet another notation, I've seen people use notation like $a \mapsto b$ to indicate that $a$ points to $b$.

• Steensgaard's seminal paper on points-to analysis used a notation like $A \vdash x : \text{ref}(\alpha)$ to mean, very roughly, that $x$ points to $\alpha$, more or less. Warning: this is not really an accurate statement of what that notation means. (Actually, $\alpha$ is a type -- see the original paper for details, before trying to use notation like this.)

There are probably many others as well.

My advice is to know your audience, choose a notation that will work well for your purposes, and use that. You might read other papers that are working in a similar area and see what notation they use, and try to use something similar if it is suitable for your needs, in hopes of choosing something familiar to your audience. But whatever you do, define your notation before first use, as there is no absolute accepted standard here.