# Pointer Provenance

contributed by <`0xff07`> <`yungchuan`> <`p61402`>

# Prologue : Semantics

假設今天在微積分考卷上看到題目寫著：

$$
\int x\sin x dx =\ ?
$$

這時候我們該怎麼做這件事？這裡有個很直接的作法：

$$
\int x\sin x dx = \int x \sin x dx
$$

這件事當然是對的，但顯然跟預期不太一樣。這邊等號寫出來的意思，是「給定一個合法的數學式 A，找出一個等價於 A，且不含積分符號的數學式 B」。

而這個「找出來」的過程，建立在：

1. 「合法的數學式」：符號 $\int$、$x$、$\sin$、$d$ 依照某些我們認定的規則，構成一個合法的數學式。
2. 「等價」：認為哪些數學式之間，是等價的？比如：
$$
\int x\sin x dx
$$
跟
$$
- x \cos x + \sin x +C
$$
雖然是相異的表示法，但我們仍然將兩者劃上等號：
$$
\int x\sin x dx = - x \cos x + \sin x +C
$$

在怎麼樣的「討論情境」下，我們會把這兩個相異的表示式「劃上等號」？這個「討論情境」就是所謂 「語意」。「語意」是指「這個表示式能『推論』出哪些表示式？」「哪些合法的表示式，可以等價於另外哪些合法的表示式」。如離散數學中邏輯表的諸多推論規則，事實上也是一連串「一個合法的表示式，變成另外一個合法的表示式」的規則（而且同樣合法的表示式的集合也可以因為有不同語意，使得推論的合法性產生變化。比如命題邏輯有古典語意，與不承認排中律的直構邏輯）。因此是從一個表示式，推論到另外一個表示式的關鍵。

編譯器優化程式的過程也是類似的。只是對於編譯器而言，問題變成：「給定一個 C 語言程式, A。請找出另外一個等價的 C 語言程式 B ，且 B ...」。

其中的「...」中，是讓程式更優化的條件，比如「沒有 branch」「沒有 tail call recursion」等等。

在 C 語言當中，我們可以知道哪些字元的組合，能構成合法的 C 語言程式。因此在第 1. 的部分問題較小。但對於第 2. 個問題，我們在思考「兩個 C 語言程式等價」時，必須對這個程式中各個符號，有精確的定義。

但， C 語言規格書中對這些內容的定義，大多使用文字敘述，難以作為「是否合法」的明確規範，進而使得「推論出等價的程式」這件事變得困難。除了理解上的歧異之外，也使得編譯器進行優化的難度增大。

這篇文章中提到這個問題的其中一個部分：指標的語意。指標在 C 語言中，以一個數值表示所謂的「記憶體位址」。但兩個指標中的數值相等的時候，我們可以「認為」他們指向同一個物件嗎？如果可以，會有什麼後果？如果不行，那該怎麼樣提出適合的語意，使得他們的行為變得一致？

## Pointer as a Value

考慮以下程式：

#include <stdio.h>
#include <string.h> 
int y=2, x=1;
int main() {
  int *p = &x - 1;
  int *q = &y;
  printf("Addresses: p=%p q=%p\n",(void*)p,(void*)q);
  if (memcmp(&p, &q, sizeof(p)) == 0) {
    *p = 11;  // does this have undefined behaviour?
    printf("x=%d y=%d *p=%d *q=%d\n",x,y,*p,*q);
  }
}

問：p, q 有沒有 pointer aliasing 的問題？

有可能不會。但如果在記憶體中 `x` 與 `y` 剛好在 stack 中排在相臨的位址（比如計算機組織學過的那種 `push x, push y, sp -= 8` 那種排法），那麼 `p`, `q`的值在上述計算中就有可能是相同的。這時候該認定 p, q 指向相同的物件 `y` 嗎？還是有什麼依據去「認為」這兩個指標即使值相同，但仍然視為相異的指標？