はじめに
今回の記事では、PASCAL言語*1のポインタについて解説していく。ポインタを通じて、ややこしい構造化プログラミングを理解しよう。
記事の注意点
- 初期段階のチャーチの提唱 (Church's Thesis)「計算可能=再帰的」は非構造化
- チャーチの定理 (Church's Theorim)「無矛盾=決定不能」は構造化
- 上記の注意点については一切質問や意見を受け付けない
Pascal言語のポインタ
Pascalのデータ型では、型のポインタ(pointer)と参照という考えが導入された。開発者のウィルトによれば*2、この二つの考えについて、記憶領域の大きさが初めから明らかではない再帰的構造に対して有効とした。その上で、この記憶領域の不明問題を解決するため、動的割り付け(動的アロケータ、dynamic allocator)について、ウィルトは次のように述べた（ただし、型Tはtype Tとしてすでに宣言されているものとする）。
データとデータに対する参照を記法的に明確に区別することが必要であり、その結果、その値がほかのデータへのポインタ（参照）であるようなデータ型が導入されなければならない。この目的のために我々が用いる記法は、次のようなものである：
type Tp = ↑T (4.4)
型宣言(4.4)は、型Tpの値は型Tのデータへのポインタであることを表している。したがって、(4.4)の矢印は "...へのポインタ" を表している。指されている要素の型がTpの宣言から明白であることは基本的に重要である。われわれはTpはTに束縛されているという。この束縛は高級言語におけるポインタを、アセンブラ語における番地から区別するものであり、記法上の冗長性を利用して、プログラム言語における安全性を増加させるための最も重要な機構の一つである。
さらに、ウィルトは続けて、
var p: Tp;
new(p);
というコードを書く。そうすれば、動的に「型Tの変数を実際に割り付け、この新しい変数を参照する型Tpのポインタを生成し、そしてこのポインタを変数pに代入」*3することができるとした。p↑と書くと、動的に割り付けられた型Tの変数を指す。
束縛に似たアイデアは、Simula67でもref(T) p;という「参照の制限」（ただし、変数pは参照型）として登場する。また、PascalとSimula67の参照はホーアのレコードクラスの考えに基づく。
改めて、それぞれ二つの言語のコードをまとめてみよう。
「Simula67 言語」（1967年リリース。1972年版の構造化プログラミング第三部を参照）
class T(); begin integer x; procedure y() begin...end; end
ref(T) p;
p :- new T();
p.x = 12;
p.y();
「Pascal 言語」（1970年リリース。コードは当時の規格）
type T = record x: integer; y: integer; end
type Tp = ↑T;
var p: Tp;
new(p);
p↑.x := 12;
p↑.y := 15;
このとき、p.x、あるいは、p↑.xはI×Iの直積型（カルテシアン積型）のダイクストラ選択（選出）である。
再帰データ型
もし、構造化プログラミングの第二部「データ構造化序論」でホーアが述べたように、データ型を集合とみなせるのであれば、再帰的であるようなTの濃度は無限であり、有限であるような装置の記憶容量では追いつかない。
そこで、ポインタ↑T（ここでは、ヴィルトの規格を無視してJIS規格を使う。例えば、↑の代わりに^を使う）を用いることにしよう。
Program Sample(output);
type Tp = ^T;
T = record
x: Tp;
end;
var p: Tp;
var q: Tp;
begin
New(p);
New(q);
p^.x := q;
Dispose(p);
Dispose(q);
end.
このとき、T型の変数pの中には同じくT型の変数qが入っているはずである。だが、TpとTは異なる型であるため、実際にはT型のxが示すものは、T型とは異なるTp型のqなのである。
さらに、記憶容量が空いていれば、新たにつぎ足すことができる。以下のように、Tp型のポインタ変数sを作っておき、qにつないでいこう。
var s: Tp;
New(s);
q↑.x = s;
この再帰データ型Tはwhile文など「ダイクストラ繰り返し」で操作するようになる。
これで構造化プログラミングの簡単な説明は終わりにする。読者の皆さんは賢いので容易に構造化の概念を理解できただろう。
