プログラミング言語の特徴と分類#
教科書2章 導入 講義0.5回分
プログラミングパラダイム#
プログラミングパラダイムとは，プログラミング言語が持つプログラムの規範や哲学のことである．以下の図は代表的なパラダイムの親子関係である．
%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 40, 'rankSpacing': 40, 'padding': 5}}}%%
graph TD
パラダイム --> 命令型;
パラダイム --> 宣言型;
命令型 -->|ほぼ同義| 手続き型;
命令型 --> オブジェクト指向;
宣言型 --> 関数型;
宣言型 --> 論理型;例えば，FortranやC言語，Pythonは命令型（≒手続き型）のパラダイムに従って設計されている．命令型では命令（四則演算や比較，代入等）の逐次的な処理によってプログラムを実現する．
パラダイムが異なる言語は，その大原則となる規範や哲学が異なるため記法が大幅に変わる．LispやScalaは関数型パラダイムを採用しており，命令型とは全く別の考えに従っている．関数型の詳細については関数型言語で説明する．
(define sum (lambda (n)
(if (= n 0) 0 (+ n (sum (- n 1))))))
(display (sum 10)) ; 55
論理型言語は論理式の列挙でプログラムを表現する．
sum(0, 0) :- !.
sum(N, R) :- N1 is N - 1, sum(N1, Rt), R is Rt + N.
?- sum(10, X). % 55
パラダイムは規範であり厳密な定義はできない．書籍や文献によって様々な解釈がある点に注意すること．命令型と手続き型は同一視されることが多い．命令型と宣言型は基本的に対義関係にある．
Note
パラダイムは音楽のジャンルに似ている．厳密な定義はできないが一定の共通認識はある．
世の中には様々なパラダイムが存在している．新たなプログラミング言語を学ぶ際は，その言語がどのパラダイムを採用しているかを強く意識すること．
特定パラダイムの言語を習得すれば，それと同一パラダイムの言語習得（C言語からPython等）は決して難しい問題ではない．文法や構文などの差異はあるものの，大原則となる哲学が同一なためである．
Note
昨今は複数のパラダイムを採用したマルチパラダイム言語が一般的である．各種パラダイムの利点を組み合わせて良い言語を設計している．例えばJavaはオブジェクト指向言語であるが，部分的に関数型の機構（ラムダ式やStream API等）を採り入れている．
パラダイムは排他的ではなく共存可能である．
教科書では，計算モデル（model of computation）を共有するプログラミングの枠組みをプログラミングパラダイムと読んでいる．すなわち「パラダイムの違い＝規範や哲学の違い＝計算モデルの違い」と捉えることができる．
計算モデルとは，コンピュータ上における計算を抽象化した枠組みである．関数型言語が採用するラムダ計算や，命令形言語が採用するRAMやチューリングマシンなどが該当する．計算モデルの考案により，計算の停止問題などの計算理論研究が発展した．本講義では計算モデルを計算理論のためではなく，プログラミング言語の理解のために用いる．
以降では，現在のコンピュータの基本であるノイマン型コンピュータ，および命令型言語が採用する計算モデルRAMについて説明する．
ノイマン型コンピュータ#
John von Neumann
©1
ノイマン型コンピュータはプログラムとデータを記憶装置に格納し，順番に読み込んで実行するコンピュータである．現在のほとんど全てのコンピュータがノイマン型に相当する．以降ではノイマン型コンピュータを単にコンピュータと呼ぶ．
Note
量子コンピュータは非ノイマン型である．
コンピュータの基本構成は以下の通りである．単純化のために入出力装置を省略している．
%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 50, 'padding': 5}}}%%
graph LR
メモリ -- load --> CPU
CPU -- store --> メモリコンピュータの基本動作は以下3ステップである．
- CPUがメモリからデータを読み込む（
load） - 演算の実行（
add等） - CPUが演算結果をメモリへ格納（
store）
序論で示したアセンブリの動作と同一である．
再掲：単純なアセンブリ言語プログラム（序論#アセンブリ言語）
このload→any process→storeの操作を抽象化すると，右辺に式を持つ代入文とみなせる．
命令型言語はこのような代入文の繰り返しによって，メモリ上の変数の値を動的に変化させ計算を行う点に特徴がある．命令型言語の特徴は以下のようにまとめられる．
- 基本要素：
- 変数 ... データと計算結果を保持
- 文 ... 代入文（
=）や制御文（iffor）など - 特徴：
- ①プログラムは文の並びであり，逐次的に実行する
- ②代入文によって変数の値を動的に変化させて計算する
Note
この時点で驚きのある内容ではないはず．皆さんのよく知る一般的なプログラミング言語(1)の挙動である．
- CやPython等の命令型パラダイムの言語のこと．
RAM#
命令型言語の振る舞いを考えるために，ノイマン型コンピュータの論理的な計算モデル，RAM（random-access machine）を説明する．
Note
ここでのランダムは「任意の」という意味であり「無作為」の意味ではない．メモリの任意の場所にアクセスできる機械という意味である．順序に従ってのみアクセスできるという，チューリングマシン（TM）のテープと対比するための語である．
現在のコンピュータのメモリはランダムアクセス可能なため，TMよりもRAMの方が現実に近い．チューリングマシンについては3年前期の「計算理論」で扱う．
RAMは1個のレジスタc(0)を持つ．メモリは複数のメモリセルで構成されており，上から順にc(1) c(2)...と呼ぶ．RAMの構成は以下の通りである．ここでは入出力テープは省略して考える．
[プログラム]
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 ] 〃
... ... 〃
プログラム内の機械語命令は演算コードとオペランドの組で構成される．
演算コードは次の12個である(1)．
readとwriteは省略．
- 転送命令
load - 格納命令
store - 四則演算
addsubmultdiv - 制御命令
jumpjgtzjzero - 停止命令
halt
オペランドには定数，直接アドレス，間接アドレスのいずれかを指定できる．
#i... 定数iを指定i... セルc(i)を指定（直接アドレス指定）*i... セルc(c(i))を指定（間接アドレス指定）
loadとstoreに対する具体的なRAMの挙動を示す．loadとstoreの主体は常にc(0)と考えると良い．
命令 挙動 メモリ
-----------------------------------------------------------------
load #1 c(0)←1 c(0) [ _ ] // ← 1
load 1 c(0)←c(1) c(0) [ _ ] // ← 3
c(1) [ 3 ] // この値をc(0)へ転送
load *1 c(0)←c(c(1)) c(0) [ _ ] // ← 5
c(1) [ 3 ]
c(2) [ 4 ]
c(3) [ 5 ] // この値をc(0)へ転送
命令 挙動 メモリ
-----------------------------------------------------------------
store #1 これはNG
store 1 c(0)→c(1) c(0) [ 9 ] // この値をc(1)に格納
c(1) [ _ ] // ← 9
store *1 c(0)→c(c(1)) c(0) [ 9 ] // この値をc(c(1))に格納
c(1) [ 3 ]
c(2) [ 4 ]
c(3) [ _ ] // ← 9
機械語命令にはジャンプのためのラベルを付与することもできる．
RAMの機械語プログラムは先頭から逐次的に実行されるが，制御命令（jump jgtz jzero）によって，命令のジャンプが可能である．例えばjump loopはloop:ラベルの命令へ制御を移動する．実際には，プログラムカウンタの値をそのラベルの値に変更することにより，ジャンプを実現している．
| 命令 | 動作 |
|---|---|
load a |
c(0) ← c(a) |
store a |
c(0) → c(a) |
add a |
c(0) ← c(0) + c(a) |
jump b |
プログラムカウンタ ← b |
jgtz b |
プログラムカウンタ ← b，ただしc(0) > 0ならば |
jzero b |
プログラムカウンタ ← b，ただしc(0) = 0ならば |
halt |
実行終了 |
以上がRAMの主要構成の説明となる．続いて，具体的な計算処理を題材にRAMプログラムの挙動を考える．題材は\(\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
}
for文はwhile文+if文に書き換え可能である． ↓ 書き換え可能
上記Cプログラムに対応するRAMプログラムは次の通りである．各変数とRAM上のメモリセルの対応は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
if (i - 50 > 0)と解釈．
上記の例から分かる通り，C言語の単一文（i = 0;）はRAMの機械語の数命令（load+store）に翻訳・コンパイルすることができる．また，C言語の制御文（if文等）は制御命令（jumpやjgtz等）によって実現できる．
Note
このコンパイル作業は3年後期の「情報科学演習D」で実装することになる．今のうちに機械語の基本動作をよく理解しておくこと．
ここで扱ったコンパイル作業は比較的単純な処理である．これは，C言語や命令型言語そのものの抽象度がそれほど高いものではないことを示唆している．言い換えれば，命令型言語はコンピュータの基本動作に強く依存して設計されているといえる．
Note
命令型と対義関係にある関数型の場合，命令の列挙ではなく数学的な関数の組み合わせでプログラムを実現する．
全てのCプログラムの計算はRAMで模倣可能である．C言語の計算モデルがRAMであるため，当然といえば当然である．
まとめ#
プログラミング言語が持つ規範や哲学であるプログラミングパラダイムについて説明した．パラダイムの違いとは，すなわち規範や哲学の違いであり，その言語が採用する計算モデルの違いである．
さらに命令型言語の計算モデルであるノイマン型コンピュータについて説明した．その特徴は，逐次的な文の実行，及び代入文の繰り返しによって計算を実施する点にある．
最後にノイマン型コンピュータをさらに単純化したRAMを紹介した．C言語はRAMの機械語命令列に容易に変換可能であり，これは命令型言語がコンピュータの基本動作に強く依存して設計されていることを意味している．