まずはノイマン型コンピュータを理解する
ノイマン型コンピュータとは
ハンガリー出身の数学者であるジョン・フォン・ノイマン（John von Neumann）によって提唱された、コンピュータの基本構成（アーキテクチャ）のことを指す。特徴的なのは、逐次処理方式によって処理が行われることであるが、これは命令型言語の基となっている考え方である。
このコンピュータの基本的な動作は、アセンブリ言語によって記述することができる。（load，store，addなど）ノイマン型コンピュータの論理的な計算モデルとしてRAMが知られている。
制御構造（if()，for()など）
while文のEBNF
＜while文＞ ::= while (＜式＞) ＜文＞ ;
for文のEBNF
＜for文＞ ::= for (＜式＞1; ＜式＞2; ＜式＞3) ＜文＞ ;
for文と等価なwhile文
＜式＞1;
while (＜式＞2) {
＜文＞;
＜式＞3;
}
＜式＞1;＜式＞3;を俗に"式文"と呼ぶ。
ジャンプ文
break文とcontinue文（ジャンプ文）の使用例
while (＜式＞1) {
if (＜式＞2) break; //脱ループ
if (＜式＞3) continue; //続ループ
}
構造化と非構造化
プログラム中の全てのループ処理が繰り返し文（for文やwhile文）で構成されているとき、そのプログラムは構造化されているといえる。反対に、ループ処理がif文とジャンプ分を用いて構成されているとき、そのプログラムは構造化されていない非構造的なプログラムに位置づけされる。
以下に非構造的なプログラムを掲載する。そのプログラムを構造化したプログラムも共に掲載する。
void sort(int array[], int size) {
int i = 1;
LOOP_I:
int j = i;
int current = array[i];
LOOP_J:
if (array[j - 1] <= current)
goto NEXT;
array[j] = array[j - 1];
if (--j)
goto LOOP_J;
NEXT:
array[j] = current;
if (++i != size)
goto LOOP_I;
}
void sort (int array[], int size) {
/*LOOP_Iに相当*/
for (int i = 1; i < size; ++i) {
int current = array[i];
int j = i;
/*LOOP_Jに相当*/
while ((j > 0) && array[j - 1] > current>) {
array[j] = array[j - 1];
--j;
}
array[j] = current;
}
}
以上二つのプログラムはどちらも挿入ソートを示している。非構造プログラムは低水準である、機械語等の振る舞いに近い。構造化プログラムを書くことを意識していきたい。
データ構造
動的型付け言語と静的型付け言語
C言語やJavaのように各変数に型を指定しなければならない（int型など）言語を静的型付け言語と呼び、反対にPythonやJavascriptのように変数への型の指定を必要としない言語を動的型付け言語と呼ぶ。動的型付け言語では、プログラマーが型宣言をしていないが、実行時には勝手に型付けが行われている。
void main() {
printf("%d", 1 + 'c'); // 100
printf("%c", 1 + 'c'); // d
}
public static void main(String[] args) {
System.out.printlnz(1 + 'c'); // 100
}
print(1 + 'c') #TypeError
console.log(1 + 'c'); // 1c
cはASCⅡコードで99に相当する。pythonでは文字は文字列として扱われASCⅡコードに直接変換されることはない。したがって、TypeError: unsupported operand type(s) for +: 'int' and 'str'が出力されてしまう。また、JavaScriptでは暗黙的に数値を文字列に変換する。
配列型
配列型のメモリの割り当て
int a[3] = {5, 65535, 10}としたときのメモリ割り当ては以下の通り。
[ ... 05 00 FF FF 0A 00 A5 F8 ... ] // メモリ領域
a[0] a[1] a[2] // 対応する配列要素
【疑問】 なぜ、a[0] = 5が05 00のメモリに割り当てられているの？
このメモリの割り当てはリトルエンディアン方式に則って行われているからである。
リトルエンディアン方式とは？
リトルエンディアン方式について図解したものを以下に掲載する。リトルエンディアン方式とは、簡単に「最後のバイトからデータを並べていく」やり方を指す。
ポインタ型
ポインタの良い例として、計算モデルRAMの間接アドレス指定の概念を持ち出す。
計算モデルRAMの間接アドレス指定
命令 挙動 メモリ
-------------------------------------------------------
load *1 c(0)←c(c(1)) c(0) [ ] // 8が格納される
c(1) [ 2 ]
c(2) [ 8 ]
【疑問】なぜポインタが重要になってくるのか？
巨大なメモリ領域をを要する変数の実行効率改善のため。よく、メールでPDFファイルを転送するとき、サイズが大きすぎて送れないことが発生する。そのとき、DropBoxを間接的に挟み、そこでファイルのURLを作成すれば、そのURLを送るだけでファイルの転送が可能となる。これがポインタの重要な働き。
printf("%zu %zu %zu %zu\n", // 4 2 8 8
sizeof(int), // int型のサイズは4バイト
sizeof(short), // short型のサイズは2バイト
sizeof(int*), // int型ポインタサイズは8バイト
sizeof(short*)); // short型ポインタサイズは8バイト
上のコード結果からもわかるように、型のサイズに依らずアドレスのサイズは常に一定である。（PDFファイルのサイズに関わらず、URLの長さは変わらない）
ポインタ型についてC言語を通じて学ぶ
アドレス演算子 &
変数のアドレスを取得したいときに用いるのがアドレス演算子であり&と書かれる。
double a;
double *p;
p = &a; // aのアドレスを保持する
間接演算子 *
保持しているアドレスの内容（値）を参照したいときに用いるのが間接演算子であり*と書かれる。
int a = 5;
int *p;
p = &a; // aのアドレスを保持する
*p = 20; // aのアドレスの内容を20に書き換える
printf("a: %d\n", *p); // 20
printf("a: %d\n", a); // この場合も20
ポインタ型のインクリメント
ポインタ型の変数のインクリメントはどのように実行されるのか、以下の2つのコードを比較することで理解する。
#include <stdio.h>
int main(void)
{
char c = 'a';
char *p = &c;
for (int i = 0; i < 3; i++) {
printf("ADDRESS: %p\n", p + i);
}
return 0;
}
char.cの実行結果
ADDRESS: 0x7fff10f7379b
ADDRESS: 0x7fff10f7379c // 1ずつ増えている
ADDRESS: 0x7fff10f7379d // 1ずつ増えている
#include <stdio.h>
int main(void)
{
int a = 10;
int *p = &a;
for (int i = 0; i < 3; i++) {
printf("ADDRESS: %p\n", p + i);
}
}
int.cの実行結果
ADDRESS: 0x7ffce971ede8
ADDRESS: 0x7ffce971edec // 4ずつ増えている
ADDRESS: 0x7ffce971edf0 // 4ずつ増えている
char型は1ずつ増え、int型は4ずつ増えている。これは各型のサイズに依って決定している。ポインタとはそもそもアドレスを指すものである。
・char型はサイズが1バイトであるため、ポインタをインクリメントして次のアドレスを指すとき、隣の1バイトのアドレスを指す。
・int型はサイズが4バイトであるため、ポインタをインクリメントして次のアドレスを指すとき、4バイト先のアドレスを指す。
ポインタを使った間接的な右辺値操作
int x = 7;
int *p = &x; /* int *p;
p = &x; */
*p = *p + 1; // *pはxのアドレスの内容を参照しているため、x = x + 1 と等価
printf("%d\n", x); // 8
printf("%d\n", *p); // 8
ポインタを用いたコード例
#include <stdio.h>
int main() {
int array[3] = {1, 2, 3};
for (int i = 0; i < 3; i++) {
printf("%d %x\n", array[i], &array[i]);
}
printf("\n");
int *p = array;
int offset = 1;
printf("%d %x\n", *(p+offset), p+offset);
*(p+offset) += 5;
printf("%d %x\n", *(p+offset), p+offset);
p++;
printf("%d %x\n", *p, p);
}
point.cの実行結果
1 ffffcc24 // array[0]の右辺値とアドレス
2 ffffcc28 // array[1]の右辺値とアドレス
3 ffffcc2c // array[2]の右辺値とアドレス
2 ffffcc28 // array[1]の右辺値とアドレス
7 ffffcc28 // array[1]の右辺値とアドレス
7 ffffcc28 // array[1]の右辺値とアドレス
上のコードの注意点
・int *p = array;
→このとき、arrayはarray配列の先頭アドレスを示している。したがって、int *p = &array[0];と書いても、意味は同じである。
・*(p+offset) += 5;
→これは先頭アドレスの次のアドレスの内容、すなわちarray[1]の内容2に5を加算している。したがって、右辺値に変化はあるが、アドレスに変化はない。
・最後のp++
→pに1を加算しているため、pの初期値のarray[0]のアドレスをインクリメントしているのと同値。このとき、先で述べたように、int型であるから、アドレスは4バイト先を指していることがわかる。array[1]の内容を*pで参照した際に、一つ前のコードで5が加算されていることに注意。