コンテンツにスキップ

命令型言語#

パラダイム

教科書4章

講義2回分

序論#

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 40, 'rankSpacing': 40, 'padding': 5}}}%%
graph TD
  classDef focus stroke-width:4px
  パラダイム --> 命令型;
  パラダイム --> 宣言型;
  命令型 -->|ほぼ同義| 手続き型;
  命令型 --> オブジェクト指向;
  宣言型 --> 関数型;
  宣言型 --> 論理型;
  命令型:::focus;
  手続き型:::focus;
本ページでは命令型言語（imperative language）について解説する．

プログラミング言語の基本構成要素は機械的操作・制御構造・データ構造の3つである．機械的操作によってCPUへの命令を与え，制御構造によって機械的操作の繰り返しや条件分岐を実現し，データ構造によって操作対象のデータを構造化する．

命令型言語においては機械的操作とは代入文の実行である．

再掲：命令型言語の特徴（特徴と分類） 

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 50, 'padding': 5}}}%%
graph LR
    メモリ -- load --> CPU
    CPU -- store --> メモリ
このload→any process→storeの操作を抽象化すると，右辺に式を持つ代入文とみなせる．

命令型言語はこのような代入文の繰り返しによって，メモリ上の変数の値を動的に変化させ計算を行う点に特徴がある．

本ページでは命令型言語における残り2つの構成要素である，制御構造とデータ構造について解説する．C言語の経験を持つ読者が想像しやすいように，あらかじめ3つの構成要素の具体例を示しておく．

  • 機械的操作：i = 0; c = 'a'; n = i + 10;
  • 制御構造　：if() for() while() continue; break;
  • データ構造：int i; char c; long arr[10]; int *p; struct {...}

さらに，本ページではプログラムの一部を部品化する手続き（関数），およびデータを格納するメモリについて解説する．なお説明題材には命令型言語の代表としてC言語を用いるが，JavaやPythonなどの他の命令型言語にも共通する内容である．

制御構造#

命令型言語における文はEBNF（拡張BNF）(1)を用いて次のように定義される．<>で囲まれた要素は非終端記号であり，文末の;はEBNFとしての区切り文字である点に注意せよ．

  1. BNFの詳細はプログラミング言語の構文を参照せよ．
命令型言語における文のEBNF
         // 機械的操作  制御構造
         //    ↓         ↓
<文>　　 ::= <代入文> | <制御文> | <複文> | <式文> ;

<代入文> ::= <変数> = <式> ";" ; // 本講義では省略
<制御文> ::= <条件文> | <繰り返し文> | <ジャンプ文> ;
<複文>　 ::= { <文>* } // (1)!
<式文>　 ::= <式> ";" ;
  1. <文>*は文の0個以上の並びである．

文はプログラミング言語の必須構成要素の2つ，機械的操作と制御構造を内包する．

C言語の簡単なプログラムを題材として文を考える．特徴と分類で扱った\(\sum_{n=1}^{50} n^2\)の題材と同じである．

題材プログラム
{                            // 　　　　  　　　  　　　　　　  <複文>
    sum = 0;                 // <代入文>  　　　  　　　　　　  　|
    i = 1;                   // <代入文>  　　　  　　　　　　  　|
    while (i <= 50)          // 　　　　  　　　  <繰り返し文>  　|
    {                        // 　　　　  <複文>  　　　|　　　 　|
        square = i * i;      // <代入文>  　|　　 　　　|　　　 　|
        sum = sum + square;  // <代入文>  　|　　 　　　|　　　 　|
        i = i + 1;           // <代入文>  　|　　 　　　|　　　 　|
    }                        // 　　　　  <複文>  <繰り返し文>  　|
}                            // 　　　　  　　　  　　　　　　  <複文>

以下の点を確認せよ．

  • プログラムは文で構成されていること
  • 制御文（この場合while文）を除けば，文は上から逐次的に実行されること
  • 機械的操作は代入文であり，制御構造（while文）によりその実行順序を制御していること

以降は<制御文>を構成する3つの文，<条件文> <繰り返し文> <ジャンプ文>について説明する．

条件文#

<制御文>の一つである<条件文>の代表例はif文とifelse文である．

if文とif-else文のEBNF
<if文>     ::= if (<式>) <文> ;
<ifelse文> ::= if (<式>) <文>1 else <文>2 ;

<if文>は<式>が真のときは<文>を実行し，偽のときは何も実行しない．<ifelse文>は<式>が真のときは<文>1を実行し，偽のときは<文>2を実行する．

繰り返し文#

<繰り返し文>の一例はwhile文である．

while文のEBNF
<while文> ::= while (<式>) <文> ;

<while文>は<式>が真の間のみ<文>を繰り返し実行する．

C言語の<繰り返し文>はwhile文のほかに，for文が存在する．

for文のEBNF
<for文> ::= for (<式>1";" <式>2";" <式>3) <文> ;

for文はwhile文に変換可能である．

for文と等価なwhile文
<式>1;
while (<式>2) {
    <文>;
    <式>3;
}
回数指定のループは繰り返し処理の典型パターンである．これを一文にまとめたものがfor文だといえる．for文として表現可能な場合は，while文ではなくfor文を積極的に利用すべきである．

なおfor文の中で<式>1と<式>3は式ではなく文だと感じるかもしれない．例えば，for(i = 0; i < 10; i++)において，i = 0とi++は文に見える．C言語においては式は文の一種であり，これを式文と呼ぶ．

式文のEBNF
<文>　 ::= <代入文> | <制御文> | <複文> | <式文> ;
...
<式文> ::= <式> ";" ;

以下のように記述しても構文エラーは発生しない．

式文の利用
int i = 0;
10;  // 式文（この場合，実行結果には一切影響しないがエラーは発生しない）

Note

for文における繰り返し回数の制御変数iは誘導変数（induction variable）と呼ばれる．数学から由来している．特段の理由がない限りfor文ではiという変数名を用いるべきである．プログラマの共通認識，すなわち文化なためである．

ジャンプ文#

最後の<制御文>である<ジャンプ文>を説明する．C言語の<ジャンプ文>は，goto文，break文，continue文の3つである．break文とcontinue文はループの中でのみ使用できる．

ジャンプ文のEBNF
<ジャンプ文> ::= goto <ラベル>";" | break";" | continue";" ;
break文とcontinue文の一例
while (<式>) {
    if (<式>) break;     // ループを抜ける
    if (<式>) continue;  // ループの先頭に戻る
}

break文とcontinue文は特殊なgoto文であり，以下のプログラムと等価である．

上の例題をgoto文で置き換え
START:
while (<式>) {
    if (<式>) goto END;    // breakと等価
    if (<式>) goto START;  // continueと等価
}
END:

goto文有害論#

プログラム中の全てのループが繰り返し文（for文やwhile文）によってのみ作られるとき，プログラムは構造化（well-structured）されているという．これまでに述べてきた題材は全て構造化されていた．逆に，if文とジャンプ文を用いて繰り返し構造を作る場合を構造化されていないという．

構造化されていないプログラムの一例を以下に示す．処理自体はこれまでの題材\(\sum_{n=1}^{50} n^2\)と等価な内容である．

構造化されていないプログラム
    int i, sum = 0;
L:  if (i < 50) {       // if文を使って繰り返す
        i++;
        sum += i * i;
        goto L;         // 繰り返しのための強制ジャンプ
    }
    printf("%d", sum);  // 42925

Quiz

次の非構造的なC言語プログラムdo_something()の処理内容を考えよ．

非構造的なC言語プログラム 👎
void do_something(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;
}
Answer

do_something()は挿入ソートである．構造化すると以下のプログラムと等価である．

構造化された挿入ソート 👍
void do_something_structured(int array[], int size) {
    for (int i = 1; i < size; ++i) {
        int current = array[i];
        int j = i;
        while ((j > 0) && (array[j - 1] > current)) {
            array[j] = array[j - 1];
            --j;
        }
        array[j] = current;
    }
}

goto文を多用した非構造プログラムは可読性が低く，特に実行経路のトレースが難しい．goto文では「逐次的に実行する」という命令言語の原則を破壊する．

非構造プログラムは低水準であり，アセンブリや機械語の振る舞いに近い．

構造化されたプログラムは読みやすく，その意図がつかみ取りやすい．このようなプログラムの作り方を構造化プログラミング（structured programming）と呼び，強く推奨されている．

構造化プログラミングはE.W.Dijkstraによって提唱された概念である．goto文による構造の破壊や可読性の低下に気づいたDijkstraは，1968年に "Goto Statement Considered Harmful" という論文の中でgoto文有害論を展開した．

Edsger W. Dijkstra

©1

Note

"X considered harmful" はコンピュータサイエンス分野のおける有名なフレーズであり，様々な論文や記事で用いられている．その起源はDijkstraの "Goto Statement Considered Harmful" である．

continue文とbreak文もジャンプ命令の一種ではあるが，その利用は推奨される．「全てのループが繰り返し文のみで構成される」という構造化プログラミングの原則に違反しないためである．また，いずれも用途が限定的（ループ内でのみ利用可能）であり，その意図も明白(1)なため可読性の低下には繋がりにくい．

  1. continue文の意図は文字通りループ継続，break文の意図はループ脱出．

C言語はノイマン型コンピュータの基本動作，すなわち機械語に強く影響を受けて設計されており，無条件のジャンプ命令（goto文）を持つ．他方，goto文有害論が広まった後に生まれた命令型言語の多くはgoto文を設けていない．例えばJavaではgotoという文字が予約語に含まれているが，一切意味を持たない．誤ってgoto文を記述するとコンパイルエラーとなる．また変数名としても利用できない．

Note

ジャンプ命令自体はプログラムの必須要素であるという点に注意せよ．低水準の機械語ではジャンプを多用するが，高級言語においては無条件ジャンプを排除すべきという話である．

goto文有害論からは次の学びが得られる．すなわち高級言語とは，低水準の機械語命令列を隠蔽化し人の思考レベルまで抽象化した言語である．この抽象度が人の思考に近いほど人にとって理解しやすい言語となる．

データ構造#

プログラミング言語の構成要素の3つ目であるデータ構造について解説する．プログラミング言語は多種多様なデータ構造の構築方法を提供する必要がある．ここでは基本データ型と配列型，ポインタ型の3つを中心に説明する．

データを格納する変数はどのような種類（型）のデータを格納するかを宣言する必要がある．この変数の型を持つプログラミング言語を型付き言語（typed language）と呼ぶ．現在のほとんどの命令型言語は型付き言語である．

Note

PythonやJavaScriptは型宣言を必要としない．

Pythonは型宣言不要
i = 0    # 型宣言なしで利用できる
c = 'a'  # 型宣言なし

print(type(i))  # <class 'int'>
print(type(c))  # <class 'str'>

一見すると型付き言語ではないように見えるが，プログラム実行時に型を確定している．このような言語を動的型付け言語と呼ぶ．C言語やJavaなどは静的型付け言語であり，プログラマが型を明示的に指定する．

型が存在することで確保すべき対象データのメモリサイズを確定できる．C言語の型のサイズは処理系に依存するが，多くの場合int型は2バイトか4バイトである(1)．JavaScriptのNumber型は8バイトである．

  1. 3年前期の情報科学実験Bで用いるArduinoは2バイト（-32,768～32,767）である．

また型が存在することでデータ操作の検証を行うことも可能になる．言語によってはint + charという操作はコンパイルエラーが発生する．

Quiz

次のint + charの実行結果はどうなるか？

C言語プログラム
void main() {
    printf("%d ", 1 + 'c');
    printf("%c ", 1 + 'c');
}

Javaプログラム
public static void main(String[] args) {
    System.out.println(1 + 'c');
}
Pythonプログラム
print(1 + 'c')
Answer

C言語：100 d

Java：100

Python：TypeError: unsupported operand type(s) for +: 'int' and 'str'

Quiz

次のint + charの実行結果はどうなるか？

JavaScriptプログラム
console.log(1 + 'c');

Answer

JavaScript：1c

変な言語である．以下のような動画もある．

基本データ型#

基本データ型は単一の値を持つ型であり，整数や文字列，真偽値などが存在する．C言語における基本データ型は文字型char，整数型int，long，unsigned int，実数型float，doubleなどである．

C言語における基本データ型
int i;       // 宣言
i = 5;       // 利用（代入）
x = i + 1;   // 利用（参照）

配列型#

配列型は複数の要素を持つ型である．配列型が持つ要素集合は同じ型である．

C言語における配列
int a[10];      // 宣言
a[0] = 5;       // 利用（代入）
x = a[0] + 1;   // 利用（参照）

配列型の要素はメモリ上の連続した領域に割り当てられる．例えば，int型2バイトの処理系においてint a[3] = {5, 65535, 10}としたときのメモリの内容は次のとおりとなる(1)．

  1. メモリ領域の中身はリトルエンディアンで表記している点に注意せよ．2バイトの値をメモリの前方から値を格納している．5 → 1010 0000
配列型のメモリの割り当て
     a[0]  a[1]  a[2]                // 配列要素
      ↓     ↓     ↓
[ ... 05 00 FF FF 0A 00 A5 F8 ... ]  // メモリ領域の中身

Quiz

次のC言語プログラムの実行結果はどうなるか？

題材のC言語プログラム
int a[2] = {UINT_MAX, 4}; // UINT_MAXは符号なしintの最大（FF..FF）
a[0] = a[0] + 1;          // FF..FFに1を加算
printf("%d %d\n", a[0], a[1]);  // ??? ???

Answer

答えは0 4．型指定によって演算結果が溢れないように保証される．0 5になる場合をバッファオーバーフローと呼ぶ．

レコード型#

レコード型は複数種類のデータを一つにまとめたデータ型であり，構造体とも呼ばれる．宣言はstruct student { int id; char[20] name; }のように指定する．本講義では詳細は省略する．

ポインタ型#

プログラム中で宣言された変数には，特定のメモリ領域が割り当てられる．このメモリ領域の位置をアドレスや左辺値，番地などと呼ぶ（以降は単にアドレスと呼ぶ）．アドレスが指定するメモリ上の値を右辺値と呼ぶ．例えばx = 5;のとき，変数xが格納している値5が右辺値である(1)．

  1. 一般的には右辺値は単に「値」とも呼ばれるが，本ページではアドレス（左辺値）との区別のために右辺値と呼ぶ．

ポインタ型変数はそれ自体の右辺値として変数のアドレスを持つ．例えばp = &x;のとき，ポインタ型変数pが格納している値は変数xのアドレスである．

ポインタの概念は計算モデルRAマシンにおける間接アドレス指定の概念と同様である．

再掲：RAマシンのアドレス指定（特徴と分類）
load命令に対するRAマシンの動作例
命令        挙動            メモリ
--------------------------------------------------------------
load #1    c(0)←1          c(0) [ 1 ]  // load先

load  1    c(0)←c(1)       c(0) [ 3 ]  // load先
                           c(1) [ 3 ]  // この値をc(0)にload

load *1    c(0)←c(c(1))    c(0) [ 5 ]  // load先
                           c(1) [ 3 ]
                           c(2) [ 4 ]
                           c(3) [ 5 ]  // この値をc(0)にload

ポインタ型が存在する理由の一つはプログラムの実行効率の改善にある．例えば巨大なメモリ領域を要する変数（配列や構造体など）がある場合を考える．このとき，その領域全体をコピーして渡す代わりに，その領域へのポインタを渡すことで代用できる．

ポインタ型による実行効率の改善例
HUGE_OBJECT  x =  huge_object;  // 巨大な領域全体をコピーするため低速
HUGE_OBJECT *x = &huge_object;  // アドレスだけをコピーするので高速

Note

巨大なPDFファイルをメールで直接送付する代わりに，Dropbox等のURLを送るのと同様である．「間接的に」データを渡す．どれだけ巨大なファイルでもURLの長さは一定である．

アドレスの値のサイズは高々8バイト程度である．long型のコピーとほぼ同じ速度で実行できる．ポインタ型のサイズ（アドレス値の大きさ）はprintf("%d", sizeof(int*));で確認できる．

Quiz

次のC言語プログラムの実行結果はどうなるか？

題材のC言語プログラム
printf("%d %d %d %d\n",  // 4 2 8 ???
    sizeof(int),         // int型のサイズは4バイト
    sizeof(short),       // short型のサイズは2バイト
    sizeof(int*),        // int型のポインタサイズは8バイト
    sizeof(short*));     // short型のポインタサイズは?

Answer

答えは4 2 8 8．型の（右辺値の）大きさに依らずアドレス自体は常に一定サイズである．PDFのファイルサイズに依らずURLの長さは変わらないのと同じである．

以降ではC言語のポインタ型について解説する．

あらゆる変数の右辺値はメモリに確保される．すなわち変数は必ずアドレスを持つ．このアドレスの値を直接取り出す単項演算子は&である．逆に，あるアドレスから右辺値を取り出す単項演算子は*である．

C言語のポインタ操作
int x = 5;
printf("%d\n", x);     // 5   右辺値
printf("%d\n", &x);    // 70  アドレス（値は仮のもの，実行時に変動する）
printf("%d\n", *(&x)); // 5   アドレス70の右辺値
//printf("%d\n", *x);  // 理論上アドレス5の右辺値だがCではコンパイルエラー

上記プログラムのメモリ領域に対する操作は以下のように解釈するとよい．

メモリ領域に対する操作
            &x   // アドレスの参照
             ↓
  ... 05 ... 70 71 72 73 ...    // メモリのアドレス
[ ... EC ... 05 00 A5 F8 ... ]  // メモリの値（右辺値）
      ↑      ↑
      *x     x   // 右辺値の参照

ポインタ型は間接アドレス指定のためのデータ型であり，右辺値としてアドレスを格納する．アドレスを右辺値として持つ特殊な変数だと考えると良い．

ポインタ操作を次に示す．メモリ領域に対する操作と併せて挙動をよく考えよ．

C言語のポインタ操作
int x = 5;
int *p;                     // ポインタ型の宣言
p = &x;                     // ポインタ型pの右辺値にxのアドレスを代入
printf("%d %d\n",  x,  p);  //  5 70
printf("%d %d\n", &x, &p);  // 70 72
printf("%d %d\n",  0, *p);  //  0  5  // これがまさに間接アドレス指定
メモリ領域に対する操作
     &x    &p
      ↓     ↓
  ... 70 71 72 73 74 ...    // メモリのアドレス（値は仮）
[ ... 05 00 70 00 AC ... ]  // メモリの値（右辺値）
      ↑     ↑
      x     p // xのアドレスを右辺値としてコピー（p = &x）
     *p // ポインタを経由したxの間接参照

ポインタ型を使って間接的に右辺値を操作（read/write）することもできる．

ポインタを使った間接的な右辺値操作
int x = 5;
int *p = &x;
*p = *p + 1;         // x = x + 1 と等価
printf("%d\n", x);   // 6
printf("%d\n", *p);  // 6

Note

ポインタが苦手な人は，int *p = &x;という文で混乱している場合が多い．このような情報量が多い文は分解して考えると良い．この文はint *p;とp = &x;の2つの文に分解できる．前者は単なるint型のポインタpの宣言であり，後者はポインタ変数pへxのアドレスを代入しているだけである．

Quiz

次のC言語プログラムの実行結果はどうなるか？

題材のC言語プログラム
int a[2] = {UINT_MAX, 4};
int *p = &a[0];
*p = *p + 1;     // 前回クイズのa[0] = a[0] + 1;をポインタで差し替え
printf("%d %d\n", a[0], a[1]);

Answer

答えは0 4．

さらに，次のC言語プログラムの実行結果はどうなるか？

題材のC言語プログラム
int a[2] = {UINT_MAX, 4};
long *p = &a[0];  // int型ポインタをlong型ポインタに変更
*p = *p + 1;
printf("%d %d\n", a[0], a[1]);

Answer

答えは0 5．加算時*p = *p + 1には元の変数a[0]がint型であったという情報が失われ，longの加算だとみなされる．結果的にバッファーオーバーフローが発生し，繰り上がった1が配列の隣の領域に書き込まれる．

なお，上記プログラムはコンパイル時に型のミスマッチであるという警告が出る．言語によってはこのような型ミスマッチの操作を厳しく制限（警告ではなくエラー）している．

《宿題1》#

Homework 約30分 答え

次のC言語プログラムを適当な実行環境で実行し，その出力結果を答えよ．さらに各出力行に対して，何番目のarrayの右辺値とアドレスを出力しているかを答えよ．"%p"はアドレスを16進で表示する書式指定である．

#include <stdio.h>

int main() {
    int array[3] = {1, 2, 3};
    for (int i = 0; i < 3; i++) {
        printf("%d %p\n", array[i], &array[i]);
    }
    printf("\n");

    int *p = array;
    int offset = 1;
    printf("%d %p\n", *(p+offset), p+offset);

    *(p+offset) += 5;
    printf("%d %p\n", *(p+offset), p+offset);

    p++;
    printf("%d %p\n", *p, p);
}

以下の書式をコピーして回答せよ．左側が出力結果，//以降が値の意味である．

1 0x7ffd76b36d3c  // array[0]の右辺値とアドレス
???

回答フォーム

手続き#

大規模で複雑なソフトウェアを設計する場合，システム全体をより簡単化された機能に分解し，その組み合わせによって全体の機能を実現する．この考えを部品化（モジュール化）と呼ぶ．より強調するなら，部品化は人間にとって複雑さを軽減できる唯一の方法である(1)．

  1. いわゆる分割統治である．
René Descartes

「困難は分割せよ」

"Divide each difficulty into as many parts as is feasible and necessary to resolve it."

©2

部品化は規模の大きなシステムだけでなく小さなシステムでも有効なアプローチであり，個々の部品が無意味となるまで繰り返される．

命令型言語では部品化されたプログラム単位を手続き（procedure）と呼ぶ．部品化の機能を持たない命令型言語はほぼ存在しないので，命令型言語と手続き型言語はほぼ同義となる．

再掲：プログラミングパラダイム（特徴と分類） 
%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 40, 'rankSpacing': 40, 'padding': 5}}}%%
graph TD
  classDef focus stroke-width:4px
  パラダイム --> 命令型;
  パラダイム --> 宣言型;
  命令型 -->|ほぼ同義| 手続き型;
  命令型 --> オブジェクト指向;
  宣言型 --> 関数型;
  宣言型 --> 論理型;

手続きの中で特に計算結果を返すものを特に関数（function）と呼ぶ(1)．数学における関数と同じ考えであり，いくつかの引数を受け取り特定の値を返す．例えば二乗を計算する関数square()は以下のように宣言される．

  1. int xxx()は関数，void xxx()は手続きである．近年では両者を区別せずに関数と呼ぶことも多い．
C言語における関数定義
int square(int x) { return x * x; }

この関数定義において，xを仮引数（parameter）と呼ぶ．それに対し，関数square()を呼び出す際に仮引数に割り当てられる実際の値を実引数（argument）と呼ぶ．

仮引数と実引数
int square(int x) {  // xは仮引数
    return x * x;
}
int main() {
    square(3);       // 3は実引数
    int i = 5;
    square(i);       // iも実引数
}

上記の例においてsquare(3)とsquare(i)を関数呼び出し（function call）と呼ぶ．

なお，仮引数に実引数を渡す方法を引数結合（argument binding）という．この例では値渡し（pass-by-value）による引数結合が行われている．値渡しでは実引数の右辺値そのものが，仮引数の右辺値としてコピーされる．他の引数結合方法も存在するが，これについては後述する引数の結合方法で述べる．

手続きの構文#

手続き定義のBNFは次のとおりである．

手続き定義のEBNF
<手続き定義> ::= <返り値の型名> <手続き名> (<仮引数>*) <手続き本体> ;
<仮引数>　　 ::= <型名> <仮引数名> ;
<手続き本体> ::= <複文> ;  // {}で囲われた文

手続き呼び出しは以下のとおりである．

手続き呼び出し定義のEBNF
<手続き呼び出し> ::= <手続き名> (<実引数>*) ;
<実引数>　　　　 ::= <式> ;

引数結合方法が値渡しの場合，<実引数>の<式>の値を計算した後に，その値を<仮引数名>にコピーする．例えば，square(1+2)はsquare(3)に計算してから仮引数xに3が割り当てられる．

<手続き本体>の<複文>の中で宣言された変数をローカル変数（局所変数）と呼ぶ．仮引数もローカル変数の一つである．ローカル変数の有効範囲はその変数が宣言された複文の中に限定される．他方，プログラム全体で有効な宣言をグローバル変数（大域変数）と呼ぶ．これらはスコープと存続範囲で説明する．

ローカル変数とグローバル変数
int g;        // グローバル変数
int main() {
    int x;    // ローカル変数
    ...

引数の結合方法#

手続きの仮引数に実引数を割り当てる方法として，C言語では値渡しが用いられる．他のプログラミング言語では，値渡し以外の引数結合方法を利用できる場合がある．Pascal言語では値渡しと参照渡し（pass-by-reference）の両方を利用できる．参照渡しでは実引数の右辺値ではなく，アドレスが仮引数にコピーされる．よって，実引数と仮引数はメモリの参照先が全く同一になる．従って，手続き内で仮引数の値が変化すると実引数も同様に変化する．

Pascal言語での値渡しと参照渡し
program Hello;
var x, y: integer;
                  { ↓デフォルトは値渡し }
procedure increment(a: integer; var b: integer);
begin                          { ↑ varをつけると参照渡し }
    a := a + 1;  { 変数aへの代入 }
    b := b + 1;  { 参照bへの代入 }
end;

begin
    x := 5;
    y := 5;
    increment(x, y);
    writeln(x, ' ', y);  { 5 6 }
end.

Quiz

なぜ参照渡しが存在するのか？ どういう場合に参照渡しを使うべきか？

Answer

ポインタを使うべき状況と全く同じである．

巨大なデータを手続きに渡す際に参照渡しを使うべき．データ領域全体のコピーではなくアドレスのコピーで代用する．

ポインタ型による実行効率の改善例
HUGE_OBJECT  x =  huge_object;
HUGE_OBJECT *x = &huge_object;

C言語は原則値渡しのみであるが，ポインタを利用した参照渡しも可能である．変数のアドレスを実引数に与えれば，アドレスそのものが（値渡しによって）仮引数の値となる．

値渡しを使った参照渡し
void increment(int a, int *b) {  // アドレスを仮引数bで受ける（参照渡し）
    a += 1;
    *b += 1;                     // ポインタbの参照先を+1
}
int main() {
    int x = 5;
    int y = 5;
    increment(x, &y);            // アドレス自体（&y）を値渡しする
    printf("%d %d\n", x, y) ;    // 5 6
}

上記は無意味な例だが，参照渡しは配列や構造体などの巨大なデータを手続きに渡す際に用いられる．より厳密に言えば配列や構造体は値渡しができない．自動的に参照渡し（＝ポインタの値渡し）となる．

配列は値渡しではなく参照渡し
void increment(int array[2]) {  // 配列全体の値渡しに見えるが，
    array[1] += 1;              // 実際には参照が渡されている
}
int main() {
    int array[2] = {5, 5};
    increment(array);
    printf("%d %d\n", array[0], array[1]); // 5 6
}
配列は値渡しではなく参照渡し
void increment(int *p) {
    *(p + 1) += 1;
}
int main() {
    int array[2] = {5, 5};
    increment(array);
    printf("%d %d\n", array[0], array[1]); // 5 6
}

Note

scanf("%d", &x);の第二仮引数xに&を付与する必要が理由は，参照渡しをするためである．xのアドレスをscanf()の仮引数に渡し，xの右辺値をポインタ経由で書き換える．

x = scanf("%d");と書きたいところだが，C言語の関数の返り値は1つしか定義できないためこのような記述となっている（のだろう）．

JavaやPythonもC言語と同様の引数結合方法を採用している．すなわち引数結合は原則値渡しのみであり，引数の型に応じて（アドレスの値渡しを使った）参照渡しが用いられる．

Quiz

次のC言語プログラムの実行結果はどうなるか？

題材のC言語プログラム
void increment(int *p) {
    *p += 1;
}
int main() {
    int *p;        // 初期化されていないポインタ
    increment(p);
    printf("%d\n", *p);
}

Answer

答えはSegmnentation fault．参照先がない，いわゆるNULLポインタへのアクセスが実行時エラーに発生する（環境にも依存する）．

コンパイルエラーではなく実行時エラーである点に注意せよ．コンパイル時点では検知できず，実行して直面するまで気づきにくいバグである．言い換えれば，コンパイラがうるさい（警告やエラーをよく吐く）言語ほど安全なプログラムを作りやすいといえる．

スコープと存続範囲#

宣言された変数の有効範囲をスコープと呼ぶ．スコープ外（有効範囲の外）で変数を参照するとコンパイルエラーが発生する．

命令型言語の多くは静的スコープ（static scope）を採用している．その有効範囲はプログラムの文面上の宣言位置と構造に依存して定められる．プログラムの字句（lexical）のみから決定できるため，レキシカルスコープとも呼ばれる(1)．

  1. 静的スコープの対義語として動的スコープも存在する．Lispが動的スコープの代表であるが近年では静的スコープが主流である．

ここでは単純化のために分割コンパイルやextern宣言，static宣言については考慮しない．より厳密なスコープの定義は教科書等を参考にせよ．

C言語における静的スコープの例を以下に示す．

変数名の有効範囲（スコープ）
int global1;         //  global1
int f(int param) {   //    |     param
    ...              //    |       ↓
}                    //    |
int global2;         //    |    global2
int main() {         //    |       |
    int local1;      //    |       |    local1
    if (...) {       //    |       |      |
        ...          //    |       |      |
        int local2;  //    |       |      |    local2
        ...          //    |       |      |      ↓
    }                //    |       |      |
    ...              //    ↓       ↓      ↓
}                    //

スコープの範囲をまとめると次のとおりである．

変数の種類 スコープの範囲
グローバル変数 宣言からプログラム終了まで
ローカル変数（仮引数を含む） 宣言から属する複文の終了まで

スコープが存在することで，その範囲内で利用できる変数が限定的になり，考慮すべき事項を減らすことができる．結果的に可読性の高いプログラムが実現できる．逆にグローバル変数を多用するプログラムは，当該スコープ内でどの変数が使えるのか，各種変数がいつどこで変更されるかなどが把握しにくく，予期せぬ誤動作につながりやすい．

Note

Global Variable Considered Harmfulである．

スコープを狭め考慮すべき変数の数を削減する考えは，プログラム全体を部品化して複雑さを軽減する試み（分割統治）と同じ考えである．この考えはプログラミング言語の目的に則っている．

再掲：プログラミング言語とは？（プログラミング言語）
目的：
プログラミングの労力を軽減すること
必須条件：
・プログラムを書く記法が定義されていること（厳格な構文を持つこと）
・コンパイラが実現できること（機械語に翻訳可能であること）
持つべき望ましい特性：
・簡潔・明晰な表現機構を持つ
・高い記述能力を持つ
・プログラムに明確で曖昧さの無い意味を与えられる
・プログラムの信頼性・再利用性・テスト容易性を高める機構を持つ
・高品質のコードを生成するコンパイラが実現できる

変数の存続範囲（extent）とは，変数に対してメモリ領域を割り当てている期間のことである．スコープと存続範囲は同一視されがちであるが，異なるものである(1)．例えばC言語では，ローカル変数のスコープは「宣言から複文終了まで」であるが，存続範囲は「所属する関数の実行開始から終了まで」である．

  1. もちろんスコープ ∈ 存続範囲である．メモリ上の割当領域がない変数へのアクセスはありえない．
スコープと存続範囲は異なる
void main() {
    int *p;
    if (1) {
        int x = 5;
        p = &x;
    }                    // xのスコープはここまでだが存続範囲は続く
  //printf("%d\n", x);   // スコープ外なのでエラー
    printf("%d\n", *p);  // 5
    *p += 1;             // 値の書き換えも可能
    printf("%d\n", *p);  // 6
}

これはプログラミング言語が採用するメモリ管理の方針と強く紐づく性質である．詳細は続く実行時スタックで述べる．

メモリ#

プログラム中で宣言された変数は必ず適当なメモリ領域が割り当てられる．本節では，この変数のメモリ領域がどのように割り当てられるかについて説明する．

ほとんどの場合，以下の図ように宣言された順に直列にメモリ領域が割り当てられる．ただし手続きを呼び出した場合，より複雑な挙動を取る．

再掲：メモリに格納された値
配列型のメモリの割り当て
     a[0]  a[1]  a[2]                // 配列要素
      ↓     ↓     ↓
[ ... 05 00 FF FF 0A 00 A5 F8 ... ]  // メモリ領域の中身

実行時スタック#

手続きが自分自身を再帰的に呼び出す方法を再帰呼び出し（recursive call）と呼び，再帰呼び出しを行う手続きや関数を再帰的手続き，再帰的関数と呼ぶ．例えば，次の\(n\)の階乗の関数\(f\)は再帰的関数である．

\[ f(n) = \begin{cases} 1, & (n = 1)\\ n \times f(n - 1) & (n \gt 1) \end{cases} \]

\(n \gt 1\)のときに関数\(f\)が自身を再帰的に呼び出す．C言語では以下のように記述される．

階乗計算関数
int f(int n) {
    if (n == 1) { // (1)!
        return 1;
    }
    return n * f(n - 1);  // 再帰呼び出し
}
  1. この条件文は再帰の基底と呼ばれる．再帰呼び出しの中でそれ以上再帰しない部分である．

再帰呼び出しはアルゴリズム設計において非常に重要であり，命令型言語のほとんど全てで再帰呼び出しの使用を許している．再帰的手続きを実行する場合，自分自身を呼び出すたびに手続き内のローカル変数に新たなメモリ領域を割り当てる必要がある．すなわち，同じローカル変数名に対して複数のメモリ領域の割り当てが必要となる．

例えば，上記の関数に対してf(3)を実行すると，f(3)は実行途中でf(2)を呼び，f(2)は実行途中でf(1)を呼ぶ．この時点で仮引数nに対して，n=3 n=2 n=1を順に割り当てるために3個のint型のメモリ領域が必要となる．仮引数だけでなく，関数内で利用される全てのローカル変数（iやsum等）についても同様のメモリ確保が必要である．

関数の呼び出しごとに必要な情報を格納するためのメモリ領域を駆動レコード（activation record）と呼ぶ．ここでは単にレコードと呼ぶ．先の階乗関数f(n)の場合，仮引数nのための一つのint型のメモリ領域がレコードに該当する．

実行時のレコードを格納するためのデータ構造として，スタック(1)が用いられる．このスタックを実行時スタックと呼ぶ．

  1. 先入れ先出しのデータ構造のこと．
スタックの振る舞い（参考）

©3

先のf(3)を題材に，実行時スタックの変化を確認する．

実行時スタックの変化
[f(1)] = f(1)のレコード（ローカル変数nのメモリ領域のこと）

                [f(1)]                   // メモリ領域
         [f(2)] [f(2)] [f(2)]            // メモリ領域
  [f(3)] [f(3)] [f(3)] [f(3)] [f(3)]     // メモリ領域
-|------|------|------|------|------|---> t
call   call   call   done   done   done  // イベント
f(3)   f(2)   f(1)   f(1)   f(2)   f(3)

まずf(3)が呼び出されるとメモリ上にはf(3)のレコードがプッシュされる．次にf(2)とf(1)を順にプッシュし，f(1)の実行が終了するとf(1)のレコードをポップする．さらに計算が終わるたびにf(2)とf(3)を順にポップする．

このように再帰呼び出しはスタックを用いて実現される．再帰の呼び出し構造とスタックのデータ構造は類似しているため，スタックの使用は必然といえる．

より複雑な再帰的手続きを用いて実行時スタックを確認する．題材は\(\sum_{n=1}^{3} n^2\)である．2つのローカル変数n xの存在がポイントである．

複数のローカル変数を持つ再帰的手続き
int f(int n) {
    int x;
    if (n == 1) {
        x = 1;
    } else {
        x = f(n - 1);  // 再帰呼び出し
    }
    return n * x;
}
void main() {
    printf("%d\n", f(3));  // 6 (= 3 * 2 * 1)
}

この例では再帰的手続きの中に複数のローカル変数を持つため，レコード内に複数のメモリ領域が存在する．

実行時スタックの変化
                      [n=1,x=1]→1------↴               // f(1)
            [n=2,x=?] [n=2,x=?] [n=2,x=1]→2------↴     // f(2)
  [n=3,x=?] [n=3,x=?] [n=3,x=?] [n=3,x=?] [n=3,x=2]→6  // f(3)
-|---------|---------|---------|---------|---------|------> t
call      call      call      done      done      done // イベント
f(3)      f(2)      f(1)      f(1)      f(2)      f(3)

命令型言語の計算モデルはRAマシンであることを特徴と分類で紹介した．RAマシンはレジスタを中心として計算処理を行うレジスタマシン（register machine）の一種である．

しかしメモリ上の振る舞いを考える計算モデルとしては，RAマシンよりもスタックマシン（stack machine）の方が適切である．スタックマシンではスタックをデータの記憶領域として用い，演算をスタックの一番上で行う．この点はC言語で詳細を解説する．

  • CPUの振る舞いの計算モデル：レジスタマシン（RAマシン）
  • メモリの振る舞いの計算モデル：スタックマシン

Quiz

Javaでよく見かける実行時エラーStackOverflowErrorはどういう時に発生するか？

Answer

無限に関数呼び出しを行った際に発生する．無限ループによって，文字通りスタックがメモリ領域を圧迫してプログラムがクラッシュする．

StackOverflowを発生させるプログラム
class Main {
    public static void f() {
        f();
    }
    public static void main(String[] args) {
        f();
    }
}

Exception in thread "main" java.lang.StackOverflowError
    at Main.f(Main.java:3)
    at Main.f(Main.java:3)
    at Main.f(Main.java:3)
    at Main.f(Main.java:3)
    ...

プログラミングのQ&Aサービス，Stack Overflow の 名前の由来でもある．

動的メモリ確保#

プログラム中で利用するメモリサイズがあらかじめ決められない場合がある．この場合，プログラム実行中にメモリ領域を確保する操作が必要となる．この操作を動的メモリ確保と呼ぶ．

動的メモリ確保が必要なケース
int size;
scanf("%d", &size);  // 入力する要素数を指定
int array[ /*?*/ ];  // 入力値に応じて配列サイズを実行時に決める必要がある

全てのプログラミング言語で動的メモリ確保が可能である．C言語ではmalloc()とfree()が利用できる．malloc()（memory allocation，エムアロック）でメモリを確保し，free()によって確保したメモリを解放する．

malloc()を用いた動的な配列用メモリの確保
int size;
scanf("%d", &size);
int *arrayp = malloc(size * sizeof(int));  // int型バイトをsize個確保
*(arrayp + 0) = 10;  // arrayp[0] = 10と等価
*(arrayp + 1) = 20;  // arrayp[1] = 20と等価
...
free(arrayp);                              // メモリを解放する

C言語はこのようにプログラマによる動的メモリ確保の操作が用意されているが，メモリリーク(1)などの問題にもつながりやすい．malloc() free()はgoto文と同様に低水準な命令であるといえる．

  1. メモリの解放忘れによって利用可能なメモリ領域が失われる状況のこと．バッファーオーバーフローと同様，脆弱性に繋がることもある．

近年の言語ではこのような低水準のメモリ操作命令は排除されている．言い換えれば，プログラマがメモリ操作をする必要がなくなっている．JavaやPythonでは自動的なメモリ解放の仕組み，ガベージコレクションが導入されている．Rustではより先進的なメモリ管理の仕組みが取り入れられている．

メモリ領域の構成#

C言語におけるメモリ領域はいくつかの領域から構成されている．

メモリ領域の構成
┏━━━━━━━━━━━━━━━┓
┃コード，大域変数，静的変数 /* (1)! */┃
┣━━━━━━━━━━━━━━━┫
┃ヒープ（動的データ）          ┃
┣━━━━━━━━━━━━━━━┫
┃             ↓               ┃
┃                              ┃
┃             ↑               ┃
┣━━━━━━━━━━━━━━━┫
┃スタック（ローカル変数）      ┃
┗━━━━━━━━━━━━━━━┛

  1. コード領域にはコンパイルされた機械語命令列が設置される．まさにプログラムをメモリに設置するノイマン型コンピュータである．グローバル変数はコード領域の下側に設置される．

ヒープは動的データを格納するための領域であり，メモリ領域前方から順に割り当てられる．実行時スタックはローカル変数を格納する領域であり，メモリ領域後方から前方に向かってスタック形式でデータが積み上げられる．先の駆動レコードの格納先もスタック領域である．

ヒープは動的メモリ確保で述べたように，プログラマがmalloc() free()を通じて自由に操作可能な領域であり柔軟性がある．しかしながら，プログラマが責任を持って管理する必要がある．メモリを確保したにも関わらず解放を忘れると，メモリリーク等のバグにつながる．

他方，スタックは実行時スタックでも確認したように，手続き呼び出しが行われるたびに自動的に積み上げられ，手続きの処理が終わると自動的に解放される．

基本的にスタックの方がアクセスが高速である．1変数に割り当てるメモリサイズが固定であり，その操作はプッシュとポップのみで実現できるためである．

実際にプログラムを実行してヒープとスタックの領域の違いを確認することもできる．

ヒープとスタックの振る舞い
void main() {
    int i1, i2;  // スタック領域の確保
    int *p1 = &i1;
    int *p2 = &i2;

    int *p3 = malloc(sizeof(int));  // ヒープ領域の確保
    int *p4 = malloc(sizeof(int));

    printf("%p %p\n", p1, p2);  // 0x7f..cb80  0x7f..cb84
    printf("%p %p\n", p3, p4);  // 0x56..a280  0x56..a260
}

以下の点を確認できる．

  • スタックとヒープの割当順序が逆（スタックは80→84，ヒープは80→60）
  • スタックとヒープの配置も逆（スタックは7f～，ヒープは56～）
  • ヒープの方が1変数の割当サイズが大きい（スタックは4ビット，ヒープは32ビット）

なお実行結果は処理系に強く依存するので注意せよ(1)．重要な点は，スタックとヒープはメモリ領域の構成や利用方法が大きく異なる点である．

  1. メモリアドレスは当然ながら，スタックとヒープをメモリの前方と後方のどちらに配置するか，スタックとヒープをどちらの方向に積み上げるか等も処理系に依存する．

まとめ#

命令型言語における制御構造とデータ構造について解説した．命令型言語の基本構成要素は機械的操作・制御構造・データ構造の3つである．またプログラムの一部を部品化する手続き（関数），およびデータを格納するメモリについて解説した．

《宿題2》#

Homework 約30分 答え

次のC言語プログラムと等価なPythonプログラム，およびJavaプログラムを答えよ．

int factorial(int n) {
    if (n == 1) { 
        return 1;
    }
    return n * factorial(n - 1);
}

void main() {
    printf("%d", factorial(5));
}

以下の書式をコピーして回答せよ．様々な回答がありうるが機能的に等価であれば良い．必ず再帰呼び出しを用いること．

# python
???

# java
???

回答フォーム

  1. Hamilton Richards, https://en.wikipedia.org/wiki/Edsger_W._Dijkstra ↩

  2. https://en.wikipedia.org/wiki/Ren%C3%A9_Descartes ↩

  3. Dominik Flüchter, https://dev.to/dfluechter/the-stack-data-structure-2ifl ↩