【プログラミング言語】命令型言語・手続き型言語を理解する Part1

# まずはノイマン型コンピュータを理解する
### ノイマン型コンピュータとは
ハンガリー出身の数学者であるジョン・フォン・ノイマン（John von Neumann）によって提唱された、コンピュータの基本構成（アーキテクチャ）のことを指す。特徴的なのは、逐次処理方式によって処理が行われることであるが、これは命令型言語の基となっている考え方である。
![Neumann](https://github.com/user-attachments/assets/57ccab1d-03af-4a36-89d4-5c250b13a947)
このコンピュータの基本的な動作は、アセンブリ言語によって記述することができる。（`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文とジャンプ分を用いて構成されているとき、そのプログラムは構造化されていない`非構造的`なプログラムに位置づけされる。

以下に非構造的なプログラムを掲載する。そのプログラムを構造化したプログラムも共に掲載する。

```unstructural.c
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;
}
```
```structural.c
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`のように変数への型の指定を必要としない言語を`動的型付け言語`と呼ぶ。動的型付け言語では、プログラマーが型宣言をしていないが、実行時には勝手に型付けが行われている。

```sample.c
void main() {
  printf("%d", 1 + 'c');  // 100
  printf("%c", 1 + 'c');  // d
}
```
```sample.java
public static void main(String[] args) {
  System.out.printlnz(1 + 'c');  // 100
}
```
```sample.py
print(1 + 'c')  #TypeError
```
```sample.js
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`のメモリに割り当てられているの？

このメモリの割り当ては`リトルエンディアン方式`に則って行われているからである。
#### リトルエンディアン方式とは？
リトルエンディアン方式について図解したものを以下に掲載する。リトルエンディアン方式とは、簡単に「最後のバイトからデータを並べていく」やり方を指す。
![計算機言語-2](https://github.com/user-attachments/assets/6b682e39-5dc5-4b5c-ae6e-7c5b025ce24f)
## ポインタ型
ポインタの良い例として、計算モデルRAMの間接アドレス指定の概念を持ち出す。
#### 計算モデルRAMの間接アドレス指定
```
命令        挙動             メモリ
-------------------------------------------------------
load *1     c(0)←c(c(1))    c(0) [   ] // 8が格納される
                            c(1) [ 2 ]
                            c(2) [ 8 ]
```
#### 【疑問】なぜポインタが重要になってくるのか？

巨大なメモリ領域をを要する変数の実行効率改善のため。よく、メールでPDFファイルを転送するとき、サイズが大きすぎて送れないことが発生する。そのとき、DropBoxを間接的に挟み、そこでファイルのURLを作成すれば、そのURLを送るだけでファイルの転送が可能となる。これがポインタの重要な働き。

```sample.c
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言語を通じて学ぶ
#### アドレス演算子 &
変数のアドレスを取得したいときに用いるのが`アドレス演算子`であり`&`と書かれる。
```sample.c
double a;
double *p;

p = &a; // aのアドレスを保持する
```
#### 間接演算子 *
保持しているアドレスの内容（値）を参照したいときに用いるのが`間接演算子`であり`*`と書かれる。
```sample.c
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つのコードを比較することで理解する。
```char.c
#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ずつ増えている
```

```int.c
#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バイト先のアドレスを指す。

#### ポインタを使った間接的な右辺値操作
```sample.c
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
```

#### ポインタを用いたコード例
```point.c
#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`が加算されていることに注意。