コンテンツにスキップ

C言語#

教科書7章 プログラミング言語 講義2回分

序論#

講義の概要でも述べたように，プログラミング言語の理解とは，ソースプログラムをそれと等価な機械語に翻訳する過程（コンパイル）の理解である．本ページでは命令型言語に対する理解を深めるために，C言語プログラムと機械語命令の対応を考える．

例えば，i = 4;という代入文に対応する機械語はLDC 4 STL 1である(1)．文i = 4;というプログラムの持つ意味はLDC 4 STL 1であると解釈できる．また文return 4;の意味はLDC 4 STL 0 RET 0である．

  1. 機械語の詳細は後述するので，深く考えなくて良い． 高級言語と機械語の1対1対応があると捉えれば良い．

このような，プログラムを計算ステップの連続として解釈する方法を，操作的意味論（operational semantics）という．プログラムの意味を数学的・形式的に捉える手段であり，他にも表示的意味論や公理的意味論などが存在する．

Note

言語学の一つとして意味論という学術分野もある．自然言語の意味論としては以下の文が有名である．

Colorless green ideas sleep furiously（色無き緑の考えが猛烈に眠る）

統語論（構文）としては正しいが意味論としては明らかにおかしい．

本ページはC言語プログラムを題材として操作的意味論を考える．これはコンパイラの入力と出力（プログラムと機械語）の対応を考える問題である．具体的なコンパイルの手順自体は扱わないので注意せよ．

理解を容易にするために以下のような簡単化を行う．

  • コンパイル元の言語　：C言語のサブセット言語，SC言語（Small C言語）を定義し用いる
  • コンパイル先の機械語：仮想計算機の上で動作する機械語命令，SCコードを定義し用いる
[ int i = 4;   ... ] // 入力：SC言語のプログラム
        ↓ コンパイラ
[ LDC 4 STL 1  ... ] // 出力：SCコード

操作的意味論を考えるためには，SC言語とSCコードの両方を理解する必要がある．よって本ページで理解すべきコンテンツは多めである点に注意せよ．個々の要素は比較的単純である．単純な要素が多数あると考えよ．

SC言語#

C言語はかなり複雑な構文規則を持っており，その全体の把握は容易ではない．ここではC言語を簡素化したサブセット言語，SC言語（Small C言語）を定義する．

C言語と比較したときのSC言語の特徴は主に次のとおりである．

  • 基本データ型はvoid型とint型のみ（charやlongはNG）
  • 構造型は1次元配列とポインタ型のみ（int a[3]やint *pはOK，2次元配列はNG）
  • 関数の引数はvoid int int *のみ
  • 関数の返り値はvoid int int *のみ
  • static extern constは存在しない
  • 局所変数は複文の開始直後でのみ宣言できる（... { int i; ...はOK）
  • 宣言時に初期化はできない（int i = 0;はNG，int i; i = 0;はOK）
  • 文は複文，式文，if文，while文，break文，return文のみである（for文やgoto文はNG）
  • 変数の有効範囲や存続範囲はC言語と同じ

具体的なSC言語のプログラムを示す．

ソースコード
int g;
int f(int i) {
    return i * g;
}
void main() {
    int i;
    g = 4;
    i = f(3 + g);
    printf("%d", i);
}

Quiz

上記プログラムの出力を考えよ．

Answer

28

SC言語はCの完全なサブセット言語であるため，一般的なC言語コンパイラで実行できる．プログラムの振る舞いが理解できないと感じたら，オンラインIDE等で実行してみること．

構文定義#

構文図式によるSC言語の構文定義を示す．サブセット言語とはいえ相応の規模の構文規則が含まれている．全規則を理解する必要はない．適宜参照すること．前提として式と文の違いをよく理解しておくこと．

再掲：式と文（構文#前提）

C言語においては;や}を末尾に持つ要素が文である．式は四則演算などの評価結果となる値を持つ要素である．

C言語の適当なプログラム
n = i * 2;
if (n > 5) return 1;
return 0;
  • 文：n = i * 2; if (n > 5) return 1; return 1; return 0;
  • 式：i * 2 i 2 n > 5 n 5 1 0

構文図式によるSC言語の構文定義

numは任意の数字（1や99），idは任意の識別子（iやsum）を表す非終端記号である．

構文図式の詳細は構文#構文図式を参照せよ．railroad diagramとも呼ばれる．鉄道が直角に進路を変更できないことを考えれば理解は容易である．

Note

（復習）

規則同士が深いネスト構造を作る理由は，曖昧性排除や演算子の優先度の制御のためである．例えば*に+よりも高い優先度を持たせるためには，まず加算式の生成規則を適用し，その後で乗算式の生成規則を適用する．これにより構文木の浅い位置に+が設置され，深い位置に*が設置される．構文の無曖昧さや演算子の優先度については，構文#無曖昧な文脈自由文法を参照せよ．

SCマシン#

世の中には様々なプロセッサ，およびプロセッサに対応した機械語が存在している．機械語の命令群は命令セット（instruction set）と呼ばれる．PC環境においてはx86やx64が有名である．スマホ等のモバイル環境ではARM64が広く用いられている．

一言にC言語をコンパイルするといっても，どの命令セットにコンパイルするかによって出力は異なる．例えば以下のようなC言語プログラムに対して；

square(int)のC言語プログラム
int square(int n) { return n * n; }

x64とARM64ではコンパイル結果は当然異なる．

x64へのコンパイル結果
square(int):
  push   rbp
  mov    rbp, rsp
  mov    DWORD PTR [rbp-4], edi
  mov    eax, DWORD PTR [rbp-4]
  imul   eax, eax
  pop    rbp
  ret
ARM64へのコンパイル結果
square(int):
  sub    sp, sp, #16
  str    w0, [sp, 12]
  ldr    w0, [sp, 12]
  mul    w0, w0, w0
  add    sp, sp, 16
  ret

実際のプロセッサで用いられる命令セットは極めて複雑なため，ここでは簡単な仮想計算機と命令セットを定義する．定義する仮想計算機はSCマシン（Small C machine）である．SCマシンはスタックマシンの一種であり，メモリをスタック形式で利用する単純な計算モデルである．

加算式4 + 3に対するSCマシンの振る舞いを示す．

青枠■がメモリの単一セルであり，赤丸●と緑丸●はがスタックの範囲を指し示すレジスタである（詳細は後述）．LDC命令（load constant，定数のロード）によってスタックに定数4と定数3が積み上がる．BOP命令（binary operator，二項演算）によってスタックの最上位の2セルの加算が適用され，4と3を取り除いた後に7がスタックに積み上げられる．

SCマシン上での命令の順序は逆ポーランド記法（reverse polish notation，prefix notation，後置記法）とほぼ対応する．逆ポーランド記法は演算子がオペランドの後に続く式の表記方法である．ポーランド記法の詳細は関数型言語#ポーランド記法を参照せよ．

3種類の記法
4 + 3  // 中間記法
+ 4 3  // 前置記法，ポーランド記法
4 3 +  // 後置記法，逆ポーランド記法

1 * (2 + 3)  // 中間記法
* 1 + 2 3    // 前置記法（括弧が不要）
2 3 + 1 *    // 後置記法（括弧が不要）
逆ポーランド記法とSCコード，及びスタック操作
4 3 +      // LDC 4 LDC 3 BOP +             | push4 push3 +
2 3 + 1 *  // LDC 2 LDC 3 BOP + LDC 1 BOP * | push2 push3 + push1 *

SCマシンの構成#

SCマシンは2種類のメモリ領域を持つ．

  • スタック領域（図左）
  • プログラム領域（図右）

LDC 4
LDC 3 // ● pc (program counter)
BOP +
HLT

図右側のプログラム領域には，実行すべき機械語命令SCコードが実行順に格納されている．図左側のスタック領域は，プログラム実行中の様々な値を保持するメモリ領域であり，SCコードを実行しながら適宜その値を書き換えていく．スタック領域での値のロードやストア処理は，当然スタック形式で実行される．

SCマシンは上記2つのメモリ領域を制御する3種類のレジスタを持つ．

  • ●pc（プログラムカウンタ）：プログラム領域のうち次に実行するSCコードを指す
  • ●sp（スタックポインタ）：スタック領域のうち実行中関数のスタック最上部を指す
  • ●base（ベースポインタ）：スタック領域のうち実行中関数のスタック最下部を指す

pcは一つのSCコードを実行すると値が1加算される．命令が逐次的に一つずつ実行されると考えると良い．プログラム領域自体はスタックではなく直列データとして扱われる点に注意せよ．関数呼び出しやif文などによる分岐（ジャンプ）が必要な場合は，pcの値を適切な分岐先に設定する．

実行中の関数のスタック領域はbaseからspの範囲である．スタック最下部を示すbaseは，関数を呼び出した瞬間を除いて値は不動である．スタック最上部を示すspはSCコードを実行する度に値が変更される．どのように変更されるかは実行するSCコードによって異なる．例えばLDC等のロード系命令はスタック上部に値を積み上げるプッシュに相当する操作であり，spの値は増加する．逆にストア系命令はポップに相当する操作であり，spの値は減少する．

SCコード#

機械語命令は一般的に<オペコード> <オペランド1> <オペランド2> ...の形式で表現される．オペコード（opcode，operation code）とは命令そのもののであり，オペランドはオペコードの操作対象である．機械語命令LDC 4のオペコードはLDC，オペランドは4である．

SCマシン上での機械語命令列SCコードを定義する．以下の表を参照せよ．SCコードは23個の命令で構成される．

一番右の列は各SCコードを実行したときの，スタック領域と3つのレジスタに対する操作をC言語形式で表現している．これは説明のための表現方法であり，コンパイラの入力となるC言語プログラムとは無関係である点に注意せよ．スタック領域は配列t[]，スタックポインタはspで表している．

全てを暗記する必要はない．操作的意味論の説明において，SCコードの振る舞いを考える際に適宜参照すれば良い．

SCコード 意味 スタック領域とレジスタに対する操作
1 LDC a load constant sp++;t[sp]=a;
2 LLD a load local sp++;t[sp]=t[bs+a];
3 LGD a load global sp++;t[sp]=t[a];
4 LLA a load local addr sp++;t[sp]=bs+a;
5 LGA a load global addr sp++;t[sp]=a;
6 STL a store local t[bs+a]=t[sp];sp--;
7 STG a store global t[a]=t[sp];sp--;
8 STO store at indexed addr t[t[sp-1]]=t[sp];sp-=2;
9 IND a indexed fetch t[sp]=t[t[sp]+a];
10 UJP L jump pc=L;
11 FJP L jump if false if(t[sp]==0){pc=L;sp--;}
12 ENT a enter block sp=bs+a;
13 MST mark stack sp++;t[sp]=base;sp++;
14 CUP a call user procecure t[sp-a]=pc+1;bs=sp-a-2;pc=t[bs];
15 RET a return from function sp=bs-a;pc=t[bs+2];bs=t[bs+1];
16 BOP o binary operation sp--;t[sp]=(t[sp])o(t[sp+1]);
17 UOP o unary operation t[sp]=o(t[sp]);
18 HLT halt
19 ISP a increment sp sp+=a;
20 DSP a decrement sp sp-=a;
21 IBS a increment base bs+=a;
22 DUP duplication sp++;t[sp]=t[sp-1];
23 STF store indirect & fetch t[t[sp-1]]=t[sp];t[sp-1]=t[sp];sp--

操作的意味論#

具体的なSC言語プログラムとSCコードの対応を確認しながら，SC言語の操作的意味論を考えていく．また，ここまでで未定義のSCマシンの詳細も具体例を交えながら説明する．

main関数#

まずベースとなる空のmain関数を考える．SC言語プログラムとSCコード，及び実行時スタックの挙動は以下の通りである．

ソースコード
void main() {
}
SCコード
ENT 2  // 制御領域2の確保
HLT

関数実行時には，まず制御領域として2つのメモリセルを確保する．main関数ではこの領域は使用しないが，それ以外の関数で活用する（詳細は後述）．視認性のため2つの制御領域セルを白抜き枠の■で表す．

局所変数#

先のプログラムに局所変数の定義と代入文を加える．

ソースコード
void main() {
    int i;
    i = 4;
}
SCコード
ENT 3  // 制御2+局所変数1の確保
LDC 4  // 定数4をロード
STL 3  // 局所変数iにストア
HLT

ENTによる領域確保は制御用2と局所変数用1の計3となる．局所変数のセルをピンク枠の■で表す．

代入文を実行する際は，まず右辺の値4をLDC命令でスタックに積み上げてから，局所変数iのメモリセルにSTL命令でストアする．変数iはベースポインタから3つ目の位置に配置されているため，ストア命令はSTL 3となる．このように，コンパイル時は各変数がスタックのどの位置に保持されるかを記憶しておく必要がある．

大域変数#

大域変数の宣言と代入は次の通りである．

ソースコード
int g;
void main() {
    int i;
    g = 4;
}
SCコード
IBS 1  // 大域変数1の確保
ENT 3  // 制御2+局所変数1の確保
LDC 4  // 定数4をロード
STG 1  // 大域変数gにストア
HLT

ENT命令の前にIBS命令によって大域変数1を確保する．この際ベースポインタは+1される．大域変数のスタック領域は現在実行中のmain関数の範囲外なためである．

それ以外は基本的に局所変数と同様であるが，ストア命令がSTLからSTGに変更されている．STG命令で指定するストア先は変数gの絶対位置である1となる．

大域変数は常にスタック最下部に設置されるため，アドレス指定は絶対指定が可能である．他方，局所変数はベースポインタの真上に設置されるため，アドレス指定はベースポインタからの相対指定となる．

右辺に式を持つ代入文#

さらに右辺に式を持つ代入文を考える．

ソースコード
int g;
void main() {
    int i;
    g = 4;
    i = g + 3;
}
SCコード
IBS 1  // 大域変数1の確保
ENT 3  // 制御2+局所変数1の確保
LDC 4  // 定数4をロード
STG 1  // 大域変数gに格納
LGD 1  // 大域変数gをロード
LDC 3  // 定数変数3をロード
BOP +  // スタック上部2つを加算
STL 3  // 局所iに格納
HLT

全体的な挙動はこれまでの説明の繰り返しである．i = g + 3の操作をよく観察すると良い．

ここで操作的意味論を考える．代入文とは以下のような機械語操作列であると意味付けできる．

代入文の操作的意味

ソースコード
i = ■■■;
操作的意味
■■■　　   // 右辺のSCコード
STL <i>  // 大域変数の場合はSTG

※<i>は変数iのbsからの相対位置であり，実際には非負整数を取る．

代入文の右辺は単なる値や二項演算，論理和など様々な式を取りうる．代入時には，まずその右辺に該当するSCコード列を実行する．その後，ストア命令を用いてスタック最上部にある式の処理結果の値を，代入先変数に対応するメモリセルに格納する．

《宿題1》#

Homework 約30分 答え

次のSC言語プログラムをSCコード列に変換（コンパイル）せよ．

int g;
void main() {
    int i;
    g = 4;
    i = 2 * (g + 3);
}

以下の書式をコピーして回答せよ．

IBS 1
???

回答フォーム

制御文#

if文やwhile文等の制御文を考える．制御文はUJP命令（無条件ジャンプ）とFJP命令（条件付ジャンプ）を用いて，プログラムカウンタを書き換えることにより実現される．適宜プログラムカウンタを書き換えてジャンプするというアイデアは，特徴と分類#RAMで説明した内容と同じである．

まず単純なif文は次のとおりである．

ソースコード
void main() {
    int i;
    if (7 > 5) {
        i = 10;
    }
}
SCコード
   ENT 3
   LDC 7
   LDC 5
   BOP >
   FJP x // 条件式の結果が0ならxへ
   LDC 10
   STL 3
x: HLT

if文の条件式は定数ロードとBOP >で処理されている．比較演算子>の結果は真偽値であり，具体的な値としては真が1，偽が0である．FJP命令はスタック最上部（条件式の結果）を確認し，値が0の場合プログラムカウンタ●をxに変更して分岐を実現する．

if文の操作的意味論は次の通りである．else文は●●●の処理と▲▲▲の処理がジャンプによって排他的である点に着目すれば良い．

if文の操作的意味

ソースコード
if(■■■) ●●●
操作的意味
    ■■■　　 // 条件式のSCコード
    FJP x  // 条件付ジャンプ
    ●●●　　 // if本文のSCコード
x:
ソースコード
if(■■■) ●●●
else ▲▲▲
操作的意味
    ■■■　　 // 条件式のSCコード
    FJP x  // 条件付ジャンプ
    ●●●　　 // if本文のSCコード
    UJP y  // 無条件ジャンプ
x:
    ▲▲▲　　 // else文のSCコード
y:

Note

上記if文のSCコードを考えると，以下の（一見不自然な）プログラムの挙動が理解できるはず．

int f = i > 5; // 比較演算の結果を変数に直接代入する
if (1) ...     // 比較演算を使わずに値をifの条件式として扱う
if (f) ...     // 比較演算を使わずに変数をifの条件式として扱う

Quiz

結局偽とは何か？真とは何か？機械語のレベルで具体的な値は何なのか？100は真か？偽か？-100は？

Answer

偽は0，真は 0以外 である．開発者の共通認識として真を1とする場合が多いが，機械語レベルではは100でも-100でも良い．

if (0)    // false
if (1)    // true

if (100)  // true
if (-100) // true

if ('a')  // true ('a'は97)
if ('0')  // true ('0'は48)

if ('\0') // false
if (NULL) // false

SCマシンだけでなく，実際の機械語命令も同じである．

続いてもう一つの制御文であるwhile文を考える．if文と同様，ジャンプ命令を適切なタイミングで実行すれば良い．なおこの題材は無限ループが発生するが，プログラムの操作的意味を考える上では本質ではない．

ソースコード
void main() {
    int i;
    while (7 > 5) {
        i = 10;
    }
}
SCコード
   ENT 3
x: LDC 7
   LDC 5
   BOP >
   FJP y  // 条件が偽なら終了
   LDC 10
   STL 3
   UJP x  // while頭へ強制ジャンプ
y: HLT

解説は省略する．ジャンプ命令に着目すれば理解は容易である．while文は以下2つのジャンプ命令で構成されると考えると良い．

  • ループを終了するジャンプ（FJP）
  • 繰り返しを実現するジャンプ（UJP 無条件ジャンプ）

whileの操作的意味は次の通りである．

while文の操作的意味

ソースコード
while(■■■) ●●●
操作的意味
x:  ■■■　　 // 条件式のSCコード
    FJP y  // 条件付ジャンプ
    ●●●　　 // while本文のSCコード
    UJP x  // 無条件ジャンプ
y:

式#

これまでに見てきたように，式は次のような意味を持つ．

式の操作的意味

二項演算子（+や>）の場合：

ソースコード
■■■ <op> ●●● // <op>は二項演算子
操作的意味
■■■   // 左オペランドのSCコード
●●●   // 右オペランドのSCコード
BOP <op>

単項演算子（-や!）の場合：

ソースコード
<op> ■■■ // <op>は単項演算子
操作的意味
■■■   // オペランドのSCコード
UOP <op>

スタック領域のレイアウト#

続いて関数呼び出し文を考えるが，その前にここまで未定義であったスタック領域のメモリレイアウトを説明する．

実行時スタックのレイアウト
  ┏━━━━━━━━━━━━┓● sp   // 関数fを実行中の場合
  ┃ 関数fの駆動レコード    ┃
  ┣━━━━━━━━━━━━┫● base // 関数fを実行中の場合
: ┃ 関数mainの駆動レコード ┃
3 ┣━━━━━━━━━━━━┫
2 ┃ 大域変数               ┃
1 ┗━━━━━━━━━━━━┛

メモリの番地は一番下から連番が振られる．各区画には複数のメモリセルが含まれる．

スタック最下部は大域変数の領域である．宣言された大域変数の数だけメモリセルが確保される．大域変数領域の真上が関数mainと関数fの駆動レコードである．駆動レコードとは，関数の呼び出しごとに必要な情報を格納するためのメモリ領域である（命令型言語#実行時スタック）．

プログラム実行時には，まず最初に関数mainが呼び出され関数mainのレコードが確保される．mainの中で別の関数fが呼び出されると，関数fの駆動レコードがmainレコードの上部に確保される．このとき，ベースポインタ●baseとスタックポインタ●spを移動させる．これにより，現在実行中の関数がmainからfに移動したことになり，以降の作業はfの駆動レコードの上部で行われることになる．

関数の駆動レコードは以下の内容で構成される．

駆動レコードのレイアウト
┏━━━━━┓● sp
┃ 作業領域 ┃
┣━━━━━┫
┃ 局所変数 ┃
┣━━━━━┫
┃ 引数     ┃
┣━━━━━┫
┃ 制御情報 ┃ // 戻り番地と動的リンク
┗━━━━━┛● base

最上部は作業領域であり，値のロードや式の計算等に用いられる．これまで説明してきたスタック上の処理はこの領域で行われていた．

局所変数領域には，その関数で定義された局所変数が割り当てられる．これまでの説明にあったmainの局所変数iはこの領域に格納されていた．ピンク枠の■のセルである．

関数fへ渡される引数は引数領域に格納される．局所変数と同様，渡される変数の数だけメモリセルが確保される．

最下部は制御情報であり，関数呼び出しにおいて最も重要な領域である．白抜き枠の■のセルである．関数呼び出しは一種のジャンプであるため，逐次実行とは挙動が大きく異なる．ジャンプの前に次の2つの制御情報を保持しておく必要がある．

  • 戻り番地　：関数終了後に戻るSCコードの位置（現在のプログラムカウンタ● pcの値）
  • 動的リンク：関数終了後に戻る呼び出し元関数のスタック最下部（現在のベースポインタ● baseの値）

Note

読書中に別ページへ飛ぶ際は，栞や指を挟んでおくのと同じである．ジャンプする前に現在の状態を記憶しておく．

Quiz

3種類のレジスタと制御領域の対応を考えると；

  • プログラムカウンタ●pc → 戻り番地として保持される
  • ベースポインタ●base → 動的リンクとして保持される
  • スタックポインタ●sp → ？？？

spを保持する必要はないのか？

Answer

保持する必要はない．理由は自身で考えよ．次節の内容をよく考えれば良い．

関数呼び出し#

関数呼び出しの操作的意味論を考える．まずは引数を持たず返り値のみを持つ関数を考える．

ソースコード
int f() {
    return 28;
}
void main() {
    int i;
    i = f();
}
SCコード
   ENT 3
   LDC x  // 関数fの番地をストア
   MST    // 動的リンクを確保
   CUP 0  // 関数を呼び出し
y: STL 3  // y: mainの戻り番地
   HLT
x: ENT 2  // x: 関数fの開始番地
   LDC 28
   STL 0
   RET 0

関数fを呼び出す前に，まずLDC xによって関数fのプログラム領域の番地xをスタックに積み上げる．続いてMST命令で動的リンクを確保する．保持すべき動的リンクは現在のベースポインタ●baseの値1である．同時に戻り番地用の空の領域も確保する．

CUP a命令で実際に関数呼び出しを開始する．オペランドaは関数の引数の数であるが，今回は引数がないのでa=0である．

CUP命令では大幅なスタックの変更が行われる．先述のSCコード定義では，CUP aの操作はt[sp-a]=pc+1;bs=sp-a-2;pc=t[bs];と定義されていた．これを一つずつ噛み砕くと次のとおりである．今回の場合a=0なので，簡単化のためにaを無視して話を進める．

  • t[sp-a]=pc+1;：●pc+1をスタックに積み上げる（戻り番地を確保）
  • bs=sp-a-2;：●baseを●sp-2に差し替える（-2は制御領域の分）
  • pc=t[bs];：●pcを次に実行すべき関数fに差し替える（関数fに移動）

ここまでの操作によって戻り番地と動的リンクを記憶し，ベースポインタ●とスタックポインタ●を関数fの駆動レコードに指定することに成功した．以降の関数fの本文の処理はmainと全く同様である．仮に関数fが再帰呼び出しであっても，LDC+MST+CUPを使って新たな駆動レコードをスタック上部に積み上げれば良い．

今回の関数fでは定数28を返すため，LDC命令で28を積み上げ，STL 0でベースポインタ+0の位置に返り値を格納する．ベースポインタ+0は返り値用の特殊な領域である．

最後にreturn文の処理としてRET 0を実行する(1)．RET命令はLDC+MST+CUPで記憶した関数終了後の状態を復元する命令であり，次の3手順から成る．

  1. RET aはvoidを返すときa=1，値を返すときa=0である．aは返り値用の領域が不要（void）か必要かを表している．

  • sp=bs-a;：スタックポインタ●を現在のベースポインタ●に差し替え
  • pc=t[bs+2];：プログラムカウンタ●を戻り番地に差し替え（呼び出し元の関数へ）
  • bs=t[bs+1];：ベースポインタ●を動的リンクに差し替え

関数呼び出しの操作的意味論を考える．関数呼び出しとは以下のような機械語操作列であると意味付けできる．

関数呼び出しの操作的意味

ソースコード
f();
操作的意味
LDC <f> // 関数の番地を記憶
MST     // 動的リンクを確保
CUP a   // 関数を呼び出し (aは引数の数)

関数のreturn文は次の機械語操作列と対応する．

return文の操作的意味

ソースコード
return ■■■;
操作的意味
■■■　　 // 式のSCコード
STL 0  // 返り値をbaseに格納
RET 0  // 元の関数に戻る（スタック最上部が返り値に）

関数fが引数を保つ場合に対しては，以下のように一般化できる．

関数呼び出しの操作的意味

ソースコード
f(■■■);  // 引数を持つ場合
操作的意味
LDC <f>
MST
■■■　　 // 引数のSCコード
CUP a  // aは関数fの引数の数

例えばf(3 + 4)の場合，MST命令の後にLDC 3 LDC 4 BOP +を実行してからCUP 1（1は引数の数）を呼び出せば良い．3 + 4という引数の値を処理して7をスタックの最上部に積んでおけば，その領域は関数fの駆動レコード内の引数領域に割り当てられる．この場合の具体的なスタック領域の挙動は，次の引数を持つ関数呼び出しを参照せよ．

引数を持つ関数呼び出し#

関数fが引数を持つ場合の例を示す．ここでは詳細の解説は省略するが，基本的にこれまでの内容の繰り返しである．特にi = f(3 + g)とreturn i * gの挙動をよく観察すると良い．なお，引数のセルも局所変数セルと同様ピンク枠の■で表している．

ソースコード
int g;
int f(int i) {
    return i * g;
}
void main() {
    int i;
    g = 4;
    i = f(3 + g);
}
SCコード
   IBS 1
   ENT 3
   LDC 4
   STG 1
   LDC x
   MST
   LDC 3
   LGD 1
   BOP +
   CUP 1
y: STL 3  // y: mainの戻り番地
   HLT
x: ENT 3  // x: 関数fの開始番地
   LLD 3
   LGD 1
   BOP *
   STL 0
   RET 0

ポインタ#

ポインタに対応する機械命令列を説明する．

ソースコード
void main() {
    int i, *p;
    p = &i;
    *p = 7;
}
SCコード
ENT 4
LLA 3  // &iをロード
STL 4  // pにストア
LLD 4  // pをロード (*p=7の左辺を積み上げ)
LDC 7
STO    // t[t[sp-1]]=t[sp]
HLT

スタック領域にストアされたアドレス値は灰色の文字で表している．

文p = &iに対しては，まず右辺の&iを処理する．変数iのアドレス4（メモリ上の絶対位置）をLLA命令によってスタックに積み上げる．あとは代入文の処理としてSTL命令で適切な変数（今回の場合ポインタ変数p）に格納する．

文*p = 7は特殊な代入文であり，ポインタpが指し示すアドレスへ右辺値を代入する．間接アドレス指定である．この場合，まずLLD命令でポインタpの参照先をスタックに積み上げてから，右辺値を処理する（この場合定数7のロード）．その後，STO命令によってスタック最上部の値をその一つ下のセルが指定するアドレスへ格納する．STOの詳細な操作はt[t[sp-1]]=t[sp];sp-=2;である．

ポインタの操作とは，以下のような機械語操作列であると意味付けできる．右辺値としての*pの具体例は省略する．

ポインタ操作の操作的意味

ソースコード
&i;  // 右辺値として評価する場合
操作的意味
LLA <i>
ソースコード
*p = ■■■;
操作的意味
LLD <p> // 代入先アドレスをロード
■■■　　  // 右辺値のSCコード
STO     // 代入先に右辺値をストア
ソースコード
*p;  // 右辺値として評価する場合
操作的意味
LLD <p> // pのアドレスをロード
IND 0   // そのアドレス先をロード

配列#

配列の操作を考える．C言語における配列操作はポインタ操作で置き換えが可能である．例えば，*(p + 3)とp[3]は機械語の視点では等価である(1)．よって，配列の機械的操作はポインタ操作と共通する部分が多い．

  1. 実際には型のエラーが発生するので書き換えはできない．機械語のレベルでは同じ操作だという意味である．
ソースコード
void main() {
    int a[2];
    a[1] = 8 + 7;
}
SCコード
ENT 5  // 制御2+aの中身2+a自体1
LLA 4  // &a[0]をロード (aの初期化)
STL 3  // a = &a[0] (aの初期化)
LLD 3  // 代入文の準備
LDC 1  // a[1]
BOP +  // a[1]はアドレス6
LDC 8
LDC 7
BOP +
STO    // 右辺値15をa[1]へ
HLT

配列が宣言された際には，配列の要素数+1を局所変数の領域として確保する．この+1は配列変数a自体のメモリセルとして利用される．配列変数aは配列を指し示すポインタだと解釈するとよい．

この配列変数aはLLA命令を用いて&a[0]に初期化される．配列内部要素へアクセスする際には，このaに格納されたアドレスからの（a[0]からの）相対的な位置を用いる．

配列へ代入する際は，まずはLLDで配列変数aに格納された&a[0]をロードする．次に添字の値1を積み上げてからBOP +によって，代入先の配列のアドレス（この場合&a[1]の位置6）を計算する．続いて代入文の右辺値を処理し，その結果を積み上げる．あとはSTOで代入を行えば良い．STOによる値の代入は先に説明したポインタを用いた代入操作と全く同じである．

配列の操作的意味は以下の通りである．

配列の操作的意味

ソースコード
int a[10];
操作的意味
ENT 13    // 2+10+1
LLA <a>+1 // a[0]のaddrをロード
STL <a>   // aにストア
ソースコード
a[■■■]= ●●●;
操作的意味
LLD &a-base // &aの相対addr
■■■　　// 添字のSCコード
BOP + // 相対addr+添字がストア先
●●●　　// 右辺値のSCコード
STO   //
ソースコード
a[■■■]; // 右辺値の場合
操作的意味
LLD &a-base
■■■
BOP +
IND 0

副作用を持つ単項演算子#

C言語における特殊な単項演算子として，インクリメント演算子++とデクリメント演算子--がある．この2つの演算子は，他の一般的な演算子にはない副作用（side effect）を持つ．例えばx = i++という文の主作用は変数xへの代入であり，副作用として変数iの加算が発生する．

インクリメント・デクリメント演算子は，前置++iと後置i++があり，その副作用のタイミングが異なる．ここでは，SCコードを用いながらその挙動を考える．

Note

インクリメント・デクリメント演算子の挙動はC言語を使いこなすためには必須の知識である．

Quiz

次のC言語プログラムの出力を考えよ．

void main() {
    int i, x;
    i = 0;
    x = i++ + ++i;
    printf("%d %d", x, i);
}

Answer

2 2

代入文x = i++ + ++i;は以下のように解釈すると良い．

      // 式の値　 i
x =   //         0
i++   // 0(i)    1
+     //
++i;  // 2(i+1)  2

まず，インクリメント演算子を持つ式が式文として直接利用された場合の例を示す．

ソースコード
void main() {
    int i;
    i = 0;
    i++;   // ++iでも同じ
}
SCコード
ENT 3
LDC 0 STL 3             // i=0
LLD 3 LDC 1 BOP + STL 3 // i++
HLT

この例ではi++はi = i + 1と全く同じSCコードとなる．また前置++iも後置i++も全く同じ結果である．文i++の作用が変数iへの代入のみであり，副作用タイミングの影響が一切現れない．

一方，インクリメント演算子が代入文の右辺値や式内部で利用された場合，前置と後置で副作用タイミングの影響が発生する．

ソースコード
void main() {
    int i, x;
    i = 0;
    x = i++; // xは0

    i = 0;
    x = ++i; // xは1
}
SCコード
ENT 4
LDC 0 STL 3  // i=0
LLD 3        // 代入の右辺はi(=0)
LLD 3 LDC 1 BOP + STL 3 // i+=1
STL 4        // x=右辺(=0)

LDC 0 STL 3  // i=0
LLD 3 LDC 1 BOP + STL 3 // i+=1
LLD 3        // 代入の右辺はi(=1)
STL 4        // x=右辺(=1)
HLT

まず1つ目の代入文x = i++に対しては，これまで通り右辺値の処理から開始される．このとき右辺値i++は後置インクリメント演算子であるため，現在の変数iの値0が先にスタックに積み上げられる．その後，i++が処理されてi=1となる．最後に変数xへの代入が実行されるが，代入対象の右辺値はすでにi=0のときの値がスタックに積み上げられているため，x=0となる．

一方後置インクリメントの場合は，代入対象の右辺値をスタックに積み上げる前にi++が実行される．よってx=1となる．

先のクイズの機械語命令を示す．インクリメント演算子を含む式が別の式の内部にあった場合の例である．

ソースコード
void main() {
    int i, x;
    i = 0;
    x = i++ + ++i;
}
SCコード
ENT 4
LDC 0 STL 3 // i=0
LLD 3       // 式i++の評価値i(=0)
LLD 3 LDC 1 BOP + STL 3 // i+=1
LLD 3 LDC 1 BOP + STL 3 // i+=1
LLD 3       // 式++iの評価値i(=2)
BOP +
STL 4
HLT

インクリメント・デクリメント演算は次のように一般化できる．

副作用を持つ単項演算子の操作的意味

ソースコード
■■■ i++ ▲▲▲; //(1)!
  1. この式は逆ポーランド記法で記述されていると考えよ．先の例i++ + ++iはi++ ++i +である．
操作的意味
■■■  // SCコード
LLD <i>
LLD <i> LDC 1 BOP + STL <i> // i+=1
▲▲▲  // SCコード
ソースコード
■■■ ++i ▲▲▲;
操作的意味
■■■  // SCコード
LLD <i> LDC 1 BOP + STL <i> // i+=1
LLD <i>
▲▲▲  // SCコード

以下のように考えると良い．

  • 式の途中に式i++があった場合：その式の評価値はi → 副作用としてi++を実行
  • 式の途中に式++iがあった場合：副作用としてi++を実行 → その式の評価値はi

なお，単一文の中で同一変数に対する複数のインクリメント演算は避けるべきである．処理系やコンパイラによって挙動が変わるためである．

void main() {
    int i;
    i = 0;                     // clang  gcc  msvc
    printf("%d\n", i++ + ++i); //   2     2     2    クイズの処理

    i = 0;
    printf("%d\n", i++ + i++); //   1     1     0

    i = 0;
    printf("%d\n", ++i + ++i); //   3     4     4
}

clangではコンパイル時に警告が発生する．

<source>:6:21: warning: multiple unsequenced modifications
               to 'i' [-Wunsequenced]
    6 |     printf("%d\n", i++ + i++);
      |                     ^     ~~

《宿題2》#

Homework 約30分 答え

SC言語の文に次のfor文を追加する．

for文の操作的意味を考えよ．

ソースコード
for (▲▲▲; ■■■; ▼▼▼) ●●●
// ▲：初期化
// ■：条件式
// ▼：カウンタ処理
// ●：本文

以下の書式をコピーして回答せよ．

   ▲▲▲
a  ■■■
   ???

ヒント：ジャンプ命令とジャンプ先ラベルの使い方がポイントである．while文の操作的意味を参考にすると良い．

回答フォーム