プログラミング言語の特徴と分類#

導入

教科書2章

講義0.5回分

プログラミングパラダイム#

プログラミングパラダイムとは，プログラミング言語が持つ規範や哲学のことである．以下の図は代表的なパラダイムの親子関係である．

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 40, 'rankSpacing': 40, 'padding': 5}}}%%
graph TD
  classDef focus stroke-width:4px
  パラダイム --> 命令型;
  パラダイム --> 宣言型;
  命令型 -->|ほぼ同義| 手続き型;
  命令型 --> オブジェクト指向;
  宣言型 --> 関数型;
  宣言型 --> 論理型;

例えば，FortranやC言語，Pythonは命令型のパラダイム（命令型言語）に従って設計されている．命令型では命令（四則演算や比較，代入等）の逐次的な処理によってプログラムを実現する．

int sum = 0;
for (int i = 0; i <= 10; i++) {
    sum += i;
}
printf("%d", sum);  // 55

sum = 0
for i in range(11):
    sum += i
print(sum)  # 55

パラダイムが異なる言語は，その大原則となる規範や哲学が異なるため記法が大幅に変わる．LispやScalaは関数型パラダイム（関数型言語）を採用しており，命令型とは全く別の考えに従っている．

(define f (lambda (n)
  (if (= n 0) 0 (+ n (f (- n 1))))))
(f 10)

論理型パラダイム（論理型言語）では論理式の列挙でプログラムを表現する．

sum(0, 0) :- !.
sum(N, R) :- N1 is N - 1, sum(N1, Rt), R is Rt + N.

?- sum(10, X).  % 55

パラダイムは規範であり厳密な定義はできない．書籍や文献によって様々な解釈がある点に注意すること．命令型と手続き型は同一視されることが多い．命令型と宣言型は基本的に対義関係にある．

世の中には様々なパラダイムが存在している．新たなプログラミング言語を学ぶ際は，その言語がどのパラダイムを採用しているかを強く意識すること．

特定パラダイムの言語を習得すれば，それと同一パラダイムの言語習得（C言語からPython等）は決して難しい問題ではない．文法や構文などの差異はあるものの，大原則となる哲学が同一なためである．

教科書では，計算モデル（model of computation）を共有するプログラミングの枠組みをプログラミングパラダイムと呼んでいる．すなわち「パラダイムの違い＝規範や哲学の違い＝計算モデルの違い」と捉えることができる．

計算モデルとは，コンピュータ上における計算を抽象化した枠組みである．関数型言語が採用するラムダ計算や，命令型言語が採用するRAマシンなどが該当する．計算モデルの考案により，計算の停止問題などの計算理論研究が発展した．本講義では計算モデルを計算理論のためではなく，プログラミング言語の理解のために用いる．

以降では，現在のコンピュータの基本であるノイマン型コンピュータについて説明し，命令型パラダイムが採用する計算モデル，RAマシンについて解説する．

ノイマン型コンピュータ#

ノイマン型コンピュータはプログラムとデータを記憶装置に格納し，順番に読み込んで実行するコンピュータである．現在のほとんど全てのコンピュータがノイマン型に相当する．以降ではノイマン型コンピュータを単にコンピュータと呼ぶ．

コンピュータの基本構成は以下の通りである．単純化のために入出力装置を省略している．

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 50, 'padding': 5}}}%%
graph LR
    メモリ -- load --> CPU
    CPU -- store --> メモリ

コンピュータの基本動作は以下3ステップである．

1. CPUがメモリからデータを読み込む（load）
2. 演算の実行（add等）
3. CPUが演算結果をメモリへ格納（store）

プログラミング言語で示したアセンブリの動作と同一である．

load  B    // メモリB番地の内容をレジスタに転送
add   C    // レジスタの内容にメモリC番地の値を加算
store A    // レジスタの内容をメモリA番地に格納

このload→any process→storeの操作を抽象化すると，右辺に式を持つ代入文とみなせる．

<変数名> = <式>;  // A = B + C;

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

基本要素：

変数 ... データと計算結果を保持

文　 ... 代入文（=）や制御文（if for）など

特徴：

・プログラムは文の並びであり，逐次的に実行する

・代入文によって変数の値を動的に変化させて計算する

1. CやPython等の命令型パラダイムの言語のこと．

RAマシン#

命令型言語の振る舞いを考えるために，ノイマン型コンピュータの論理的な計算モデル，RAマシン（random-access machine）を説明する．

RAマシンの基本構成#

RAマシンは1個のレジスタc(0)を持つ．メモリは複数のメモリセルで構成されており，上から順にc(1) c(2)...と呼ぶ．RAマシンの構成は以下の通りである．ここでは入出力テープは省略して考える．

[プログラム]
0000 0000 0001 ◀  // load A
0001 0000 0010    // add B
0010 0000 0011    // store C
00.. ...  ...  ↑
      [プログラムカウンタ]

[記憶装置]
c(0) [ 9 ]  // レジスタ
c(1) [ 3 ]  // メモリ
c(2) [ 4 ]  //  〃
...   ...   //  〃

プログラム内の機械語命令は演算コードとオペランドの組で構成される．

<演算コード> <オペランド>   // load 1

演算コードは次の12個である(1)．

1. readとwriteは省略．

• 転送命令 load
• 格納命令 store
• 四則演算 add sub mult div
• 制御命令 jump jgtz jzero
• 停止命令 halt

オペランドには定数，直接アドレス，間接アドレスのいずれかを指定できる．

• #i ... 定数iを指定
• i   ... セルc(i)を指定（直接アドレス指定）
• *i ... セルc(c(i))を指定（間接アドレス指定）

loadとstoreに対する具体的なRAマシンの挙動を示す．loadとstoreの主体は常にc(0)と考えると良い．

命令        挙動            メモリ
--------------------------------------------------------------
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

命令        挙動            メモリ
--------------------------------------------------------------
store #1   これはNG

store  1   c(0)→c(1)       c(0) [ 9 ]  // この値をc(1)にstore
                           c(1) [ 9 ]  // store先

store *1   c(0)→c(c(1))    c(0) [ 9 ]  // この値をc(c(1))にstore
                           c(1) [ 3 ]
                           c(2) [ 4 ]
                           c(3) [ 9 ]  // store先

機械語命令にはジャンプのためのラベルを付与することもできる．

<ラベル>: <演算コード> <オペランド>   // loop: load 1

RAマシンの機械語プログラムは先頭から逐次的に実行されるが，制御命令（jump jgtz jzero）によって，命令のジャンプが可能である．例えばjump loopはloop:ラベルの命令へ制御を移動する．実際には，プログラムカウンタの値をそのラベルの値に変更することにより，ジャンプを実現している．

1. jump if greater than zero
2. jump if zero

RAマシンの挙動#

続いて，具体的な計算処理を題材にRAマシンプログラムの挙動を考える．題材は\(\sum_{n=1}^{50} n^2\)を出力するプログラムである．

void main() {
    int sum = 0;
    for (int i = 1; i <= 50; i++) { // (1)!
        int square = i * i;
        sum += square;
    }
    printf("%d", sum);  // 42925
}

1. for文はwhile文+if文に書き換え可能である．

   for (<初期化>; <条件式>; <変化式>) {
       <本文>
   }
   

   ↓ 書き換え可能

   <初期化>
   while(1) {
       if (!<条件式>) break;
       <本文>
       <変化式>
   }
   

上記Cプログラムに対応するRAマシンプログラムは次の通りである．各変数とRAマシン上のメモリセルの対応はc(1)↔i，c(2)↔square，c(3)↔sumとなっている．

  load   #0      // sum = 0;
  store  3
  load   #1      // i = 1;
  store  1
loop:
  load   1       // if (i > 50) goto exit; (1)
  sub    #50
  jgtz   exit
  load   1       // square = i * i;
  mult   1
  store  2
  load   3       // sum += square;
  add    2
  store  3
  load   1       // i++;
  add    #1
  store  1
  jump   loop    // goto loop;
exit:
  write  3       // printf("%d", sum);
  halt

1. if (i - 50 > 0)と解釈．

上記の例から分かる通り，C言語の単一文（i = 0;）はRAマシンの機械語の数命令（load+store）に翻訳・コンパイルすることができる．また，C言語の制御文（if文等）は制御命令（jumpやjgtz等）によって実現できる．

ここで扱ったコンパイル作業は比較的単純な処理である．これは，命令型言語の抽象度がそれほど高いものではないことを示唆している．言い換えれば，命令型言語はノイマン型コンピュータやRAマシンの基本動作に強く依存して設計されているといえる．

(define f (lambda (n)
  (if (= n 0) 0 (+ n (f (- n 1))))))
(f 10)

全てのCプログラムの計算はRAマシンで模倣可能である．C言語の計算モデルがRAマシンであるため，当然といえば当然である．

まとめ#

プログラミング言語が持つ規範や哲学であるプログラミングパラダイムについて説明した．パラダイムの違いとは，すなわち規範や哲学の違いであり，その言語が採用する計算モデルの違いである．

さらに命令型言語の計算モデルであるノイマン型コンピュータについて説明した．その特徴は，逐次的な文の実行，及び代入文の繰り返しによって計算を実施する点にある．

最後にノイマン型コンピュータの理論モデルであるRAマシンを紹介した．C言語はRAマシンの機械語命令列に容易に変換可能であり，これは命令型言語がコンピュータの基本動作に強く依存して設計されていることを意味している．

《宿題》#

void main() {
    int ans = 0;
    int x = 7;
    if (x > 5)
        ans = 10;
    else
        ans = 20;
    printf("%d", ans);
}

  load   #0
  store  2
  ???
labelx:
  load   ???
  ???