TSSI 基盤技術研修コース— プログラミング言語 — ＃ 3
久野靖∗

2011.6.10

1

はじめに• (答 1) コマンドを並べたもの←シェルスクリプト?

1.1

前回のアンケートを拝見して…

• (答 2) いい加減な/適当な言語←そんなの目標にするか?
• (答 3) インタプリタ方式の言語← Lisp なんかもそ□ 前回も練習問題の時間を取ったのは好評だったようです。

うなの?

今回もできればやりたかったのですが、資料には間に合• (答 4) ささっと書いて動かせる言語←コンパクト、
インタプリタ

わなかったので…
□ オブジェクト指向についてあまり納得していなかったの• (答 5) くっつける (glue) 言語←組み込み型が分かったというご意見もあったので、よかったと思います。よく知っている人は逆につっこみたい所もありそ□ スクリプト言語世代説

うですが、とりあえず分かりやすさ優先ということで• 第 1 世代→シェルスクリプト、Awk →コンパクト、適当に書ける

やっていますので…
□ グラフィクス関係の例題は Java のみでしたが、それは• 第 2 世代→ Perl →それ 1 つで結構何でも書ける (汎それでよいという感じのようでした。

1.2用)、自立した言語。ただしキタナイ• 第 3 世代→ Python、Ruby →言語デザインを整理、オブジェクト指向

今回の内容• JavaScript も第 3 世代でいいと思うが…

□ オブジェクト指向言語およびプログラミング言語全般で
周辺の話題

2.2

• JavaScript

JavaScript の由来• 総称的プログラミング (テンプレート、型パラメタ) □ Netscape Navigator 2 →当時の「最先端の」ブラウザ• 自己反映機能 (時間があれば)• Netscape 社はブラウザにスクリプト言語を組み込んで様々なことができるようにしようとした• 関数型プログラミング言語 (時間があれば)• 言 語 は 当 初「LiveScript」と い う 名 前 で 開 発 →お り か ら の Java ブ ー ム → Sun に お 金 を 払ってJavaScript − 弱い型の OOPL

2「JavaScript」にした□ スクリプト言語• 文法はできるだけ Java そっくりにしたが、言語としてはまったく別の言語。よく JavaScript と Java を□ 弱い型のオブジェクト指向言語

混同している人がいるので迷惑□ プロトタイプ方式• ブラウザ組み込みのスクリプト言語として「事実上□ 組み込み型処理系の標準」• MSIE もこれと互換の「JScript」を搭載

2.1

スクリプト言語□ って、聞いたことありますか?

□ 標準化の必要性→ ECMA(欧州情報通信システム標準化機構) による標準化→ ECMA-262 規格として成立何を意味すると思う?

□ たとえば…

• そ の 後 、ブ ラ ウ ザ 組 み 込 み だ け で な く Flash のスクリプト言語 (AcitonScript)、MS ASP(Active
Server Page) のスクリプト言語としても採用∗ 筑波大学大学院経営システム科学専攻1• ECMA によるコア部分は共通だが組み込まれている追加機能はそれぞれの環境で異なる

2.4□ 制御構造の構文は Java にソックリ□ 以下では (当然) ブラウザ組み込みの JavaScript を扱• while、for、do-while、if、try-catchう (どこにでもあって簡単に試せる)

2.3• 文字列との連結の「+」も同じ
var x1 = 1, x2 = 1;
while(x1 < 50) {document.writeln(x1);var z = x1+x2; x1 = x2; x2 = z;}

JavaScript 入門□ HTML の説明はしませんので…
□ JavaScript コードを書ける場所…HTML ファイル中の次□ オブジェクト指向言語の 3 箇所□ その 1:JavaScript の特徴

o = new Object();
document.writeln("...");

script 要素 (埋め込み、別ファイル)□ 弱い型→型宣言はない、変数に型がない<script type="text/javascript">
コード...
</script>

var x = "ABC", y = 1;

• 文字列/文字の区別はなく「’x’」でも「"x"」でも同じこと<script type="text/javascript" src="ファイル"></script>• この場合、コード中で「document.write(...)」を □ 「値」と「オブジェクト」の 2 種類がある (Java と同じ)実行して出力したものは HTML 中のその場所 (script□ 「値」は数値型 (1 つだけ)、論理値型 (Java と同じ)、要素のある場所) に埋め込まれる
文字列型 (文字型も兼ねる。Java では文字型は値、文字<pre><script type="text/javascript">
document.writeln(’ 乱数: ’ + Math.random());</script></pre>

列はオブジェクト)□ 3 種類の「値」それぞれに対応するオブジェクト種別もある (Java と同じ)が上に乗ったら〜) 「onclick="..."」(クリックした □ 値に対してメソッドを呼ぼうとすると自動的にオブジェ
クトにら) などの指定 (イベントハンドラ) の中□ その 2:

HTML タグの「onmouseover="..."」(マウスvar n = 3.141592;
document.writeln(n.toExponential(4));• 長いものは書きづらいのでよそに関数を定義して呼ぶことが多い<p onmouseover="window.alert(’こ</p>□ 関数 (function) がある、関数もオブジェクト□ 関数リテラルがある。下の 2 つは同じこと乗った ね’)">こ□ まとめると…

function add(x, y) { return x+y; }var sub = function(x, y) { return x-y; }document.writeln(add(3, 5) + ’, ’ + sub(3, 5));• 常に実行するもの (関数定義、ページ中への埋め込み) → script 要素□ 関数オブジェクトはクロージャ(まわりの環境を一緒に持つ)• ユーザの操作に対応するもの→イベントハンドラ
function test(n) {return function() { return ++n; };}var f = test(5), g = test(10);document.writeln(f() + ’ : ’ + g());
document.writeln(f() + ’ : ’ + g());
document.writeln(f() + ’ : ’ + g());<html><head><title>文書のタイトル…</title><script type="text/javascript">
常に実行するコード (関数定義等)...
</script></head><body>
ページ内容…
<script type="text/javascript">
document.write() を使うようなコード…
</script>... onclick="..." ...
</html>□ オブジェクトはすなわち連想配列 (任意の型の値を添字として取れる配列)□ オブジェクトのプロパティ(フィールド) は連想配列の要素と同じ□ 一般に「x.y」と「x[’y’]」は同じものを指す
var x = new Object();
x[’a’] = 10; x[’bc’] = 11; x[100] = 12;
x.b = 13; x.de = 14;
for(var i in x) document.writeln(’x[’+i+’] == ’+x[i]);

2

2.5

JavaScript のオブジェクト指向機能□ JavaScript ではどうなっているか…

• 「new 関数 (...)」によってオブジェクトが作成さ□ オブジェクトのプロパティとして関数を入れる→メソッドれるときに、□ メソッドの中ではオブジェクトを「this」で参照できる• その「関数」に prototype というプロパティが定義

var o = new Object();o.count = 100;o.show = function(msg) {document.writeln(msg + this.count);}o.show(’My number is: ’);

されていると、• その値が作成されたオブジェクトの「親」としてセットされる• (実際には関数を作ると prototype プロパティには「new Object()」の結果が自動的にセットされる→
そこに色々設定すればよい)□ コンストラクタも実はただの関数だが、「new 関数名(...)」の形で呼び出すと中で this が使える

function Counter(n) { this.count = n; }Counter.prototype.add =function(n) { this.count += n; }Counter.prototype.getCount =function() { return this.count; }var c1 = new Counter(3), c2 = new Counter(5);c1.add(2); c2.add(2);document.writeln(c1.getCount() + ’, ’ +c2.getCount());

function Counter(n) {this.count = n;this.add = function(n) { this.count += n; }this.getCount = function() { return this.count; }}var c1 = new Counter(3), c2 = new Counter(5);c1.add(2); c2.add(2);document.writeln(c1.getCount() + ’, ’ +c2.getCount());□ プロトタイプ方式の特徴…

• いつでも親にメソッドを追加したりしていじること□ これで Java と遜色なくオブジェクト指向…だと思う?

ができる (単なるオブジェクトだから)• 場合によっては親を指しているポインタをとり替えることで、オブジェクトをまったく別物に「変身」させられる (ECMA-262 では不許可、ただし一部の実装
ではこれを許している)□ ちゃんとあるもの• オブジェクト、インスタンス変数 (プロパティ)、メソッド• 同種のオブジェクト、コンストラクタ←かなり ad hoc

function Counter(n) { this.count = n; }Counter.prototype.add =function(n) { this.count += n; }Counter.prototype.getCount =function() { return this.count; }var c1 = new Counter(3); c1.add(4);Counter.prototype.sub =function(n) { this.count -= n; }c1.sub(2);document.writeln(c1.getCount());• メッセージ送信記法• 動的分配←型がないので簡単□ 足りないと思うもの…

• クラス→クラスは必要なのか?

(単なる構文単位?)• カプセル化→確かに保護は「全然」ない→スクリプ
トだから?

(ブラウザと組み合わせた場合、ブラウ□ 継承みたいなのはどうするの?
ザ側での保護はアリ)• 継承 (のようなもの) →以下で説明

2.6• 親 (プロトタイプ) を探して見つからない場合はさらにその親を探しに行く。
• 例: Counter オブジェクトを継承してメソッド subを追加するには…

プロトタイプ方式オブジェクト指向言語

function Counter(n) { this.count = n; }Counter.prototype.add =function(n) { this.count += n; }Counter.prototype.getCount =function() { return this.count; }function ExCounter(n) { this.count = n; }ExCounter.prototype = new Counter(0);ExCounter.prototype.sub =function(n) { this.count -= n; }var c1 = new ExCounter(7);c1.add(4); c1.sub(2);document.writeln(c1.getCount());□ オブジェクトの種類 (形) を表す (定義する) やり方→おもに 2 通り• 「こういう種類のオブジェクトはこういう形」という定義 (==クラス) を書く→クラス方式• 必要なプロパティ、メソッドを持つオブジェクトをまず作り、あとはそれをコピーする (概念的には) →プロトタイプ方式• 実際には全部コピーすると領域が無駄なので、プロトタイプ (親) へのポインタを持っておき、「自分が□ プロトタイプ方式の特徴をまとめると…

持っていないものは親が持っているものを使う」ようにする• 実行系のデザインはわりとシンプルにできる
3□ できあいのオブジェクトを操作する場合の考慮点• コンパイラよりインタプリタ向き。動的• その分、何をやっているのか分かりにくい• 自分が設計したデータ構造でないのでよく分からない• (きちっと構文を作って行くとクラス方式みたいに…)

2.7• 向こう側はチェックして例外を投げる側、こちらはだ
ましだまし使う側• きちんと型を書くのが煩雑 (しかし型検査はあった方がよいと思うが…)

組み込み型スクリプト□ スクリプト言語の 1 つの目的→組み込み型処理系□ 具体例は次の DOM で• 大きなアプリケーションがあったとして、それをカ
スタマイズすることを考える→どうしますか?

2.8□ 沢山パラメタがあって、それを設定して調整すればいDocument Object Model (DOM)□ DOM →ブラウザ内のページをオブジェクトの組み合わせ

いか?

で表現

□ パラメタは静的• W3C による標準化→ http://www.w3.org/DOM/• 「こういう場合はこう」というのが書きにくい• 現在のブラウザでは DOM level 2(DOM2) が中心• 「動き」はつけにくい• DOM2 の 標 準 は Core、Views、Events、Style、□ →パラメタを設定する代わりに「プログラム」を設定

Traversal、HTML と分かれているする• 以下では例題とともに簡単に説明• →そのプログラムが動いてさまざまな動作をすればよい□ DOM2 では文書全体は Node オブジェクトの木構造として表される• →組み込み型スクリプト• Node オブジェクトのプロパティ/メソッドを用いて• (例は既に出て来た…「マウスが乗ったら〜をする」)

木構造を自由に変更できる□ 組み込み型スクリプトに使われる言語…

<script type="text/javascript">function rot() {• tcl →もともとこのような用途のために作られた。しvar n = document.body.lastChild;
かし言語仕様があまり美しくないので普及はいまい
document.body.removeChild(n);document.body.insertBefore(n,ち (tcl/tk としてだけ有名)
document.body.firstChild);• scheme →もともとは Lisp 系の汎用言語だが、コン }パクトな処理系が作れるので組み込みスクリプト用と function dup() {var n = document.body.firstChild;
しても使われるように。gwm(ウィンドウマネージャ)、var m = n.cloneNode(true);gimp(画像加工ソフト)
document.body.appendChild(m);}• ECMA-262(JavaScript) →元はブラウザ用の組み込
function del() {みスクリプト言語だが、他の用途にも進出 (Flashvar n = document.body.firstChild;
document.body.removeChild(n);ActionScript など)}□ JavaScript の場合、オブジェクト指向ならではの利点□ HTML 要素に対応するノードのスタイル→その Node オブ→具体的には?

ジェクトの style プロパティに値をつけることで色々操□ アプリケーション自体および、アプリケーションが扱う

作できる

データ→オブジェクトであると考えることができる• 位置の変更→ CSS の位置指定機能で実現できる• オブジェクトを自由に操作するには、オブジェクト<script type="text/javascript">
var elt, time = 0.0;
function change() {elt = document.getElementsByTagName(’h2’)[0];elt.style.position = ’relative’;elt.style.backgroundColor = ’yellow’;
setInterval(step, 50);}
function step() {time += 0.05;

指向言語がよい (アタリマエ)• これまでと違うところ→オブジェクトは既に大量に(アプリやそのデータとして) 存在している→既存のオブジェクトを操るのが主目的• 従来のプログラムでは自前でオブジェクトを設計したり生成したりしてからそれを使っていた→大きな
変化 (どんな?)4• 以下で説明する Java Generics を使うには JDK 1.5
以降必要。C++ テンプレートは最近の C++コンパイ

var p = Math.sin(time) * 200;
elt.style.left = p + ’px’;}</script><button onclick="change()">Start</button>

ラはだいたい実装ずみ。

3.1□ その他できること…

コンテナクラス• テキストノードの中の文字列を操作できる (挿入、 □ C++でも Java でも配列は「個数を最初に指定」→途中
で大きさが伸び縮みできるものが欲しい→ライブラリで
削除、…)
用意。

• マウスイベント、キーイベントを受け止めて処理で□ Java (JKD1.4 まで) では → 例: ArrayList クラス。
任意のオブジェクトを格納できる配列。

きる• フォーム部品の内容 (値など) を操作できる (わりと昔からある機能)import java.util.*;public class Sample31 {public static void main(String[] args) {ArrayList a = new ArrayList(); //サイズ 0
for(int i = 0; i < 10; ++i) a.add("X" + i);
for(int i = 0; i < a.size(); ++i) {String s = (String)a.get(i); // 取出し
System.out.println(s);}}}□ 結局、DOM で何ができるかというと…

• ブラウザが表示している内容→内部のデータ構造が対応• データ構造 (オブジェクト) を任意に操作→自由に内容が変更できる• →究極のカスタマイズ (?)

2.9• 何か疑問な点はありますか?

本節のまとめ• この方法の弱点は何だと思う?

□ スクリプト言語→ささっと書ける言語、glue 言語□ ダウンキャスト … 「元の型にキャストし戻す」こと。

□ JavaScript →ブラウザ内蔵むけスクリプト言語が発端• a.add("abc") --- Object 型のパラメタに String
を渡す→ OK• 弱い型の言語• プロトタイプ方式のオブジェクト指向言語• String s = a.get(i) --- Object 型は String 型に入れられない。×。

□ 組み込み型スクリプト• String s = (Object)a.get(i) --- ダウンキャス• ブラウザ組み込み→ブラウザの制御、DOM によるペート:親クラスの型から子クラスの型へのキャスト。こジ内容の制御3のとき「元々なに型だったか」がチェックされる。

String でなかったものは String にはキャストできない (ClassCastException が投げられる)。

総称的プログラミング□ 弱点 (まずいこと) のまとめ

□ 配列型→「int の配列」「char の配列」など型をパラメ
タに持てる

• a.

ダウンキャストは繁雑。

• 見かたを変えれば…1 つの「もの」が複数の型に対• b.

実行時にチェックが必要→オーバヘッドになる(Java はそれを気にしない言語だということはあるが) 。

し利用できる←「総称的」(generic) という• 組み込み演算子なども総称的。5 / 2 == 2, 5.0 /2.0 = 2.5。
• 総 称 関 数 … max(int,int)max(double,double)

→

→

• c.

オブジェクトでないと入れられない。たとえば

int は Integer クラスのインスタンスにして入れなければならない (これもオーバヘッド)。

int,

double 等 。← オ ー• d. 配列だから「均一なものの並び」にしたいのに、何でも入ってしまう。

バローディングである程度はできるが、有限個数• array[int]、array[double] …型がパラメタになっている (型パラメタ) →無限の場合に対応。

• e. 間違ってヘンなものを入れてもコンパイラは怒ってくれない。

□ そういうものを「自前で」(ユーザ定義で) 作れるよう• f.

にするには?

そのヘンなものが取り出されて来たところで実行時にエラー。

5□ 実行してみないとエラーが出ないというのはコンパイル

cout << a[i] << ’\n’; // operator[]}する言語にとっての敗北。
□ 根本的な問題…本来「型パラメタ」によって複数の型 (ク• C++では型パラメタをソースのその位置に埋め込んで全体をコンパイルするという実装 (非均一な実装、

ラス) を使用するべきところを 1 個の ArrayList クラ
スで済ませていること。

heterogenous implementation)。だから型パラメ
タごとに別のコードができる。その代わり、その場□ JDK 1.5 から「型パラメタ」が使えるようになった (Java展開ができる→極めて高速。

Generics)。ArrayList<T>のようにパラメタは「<>」の中に指定する。T のところには任意の型 (ただしクラス)を入れてよい。

3.2□ 動かすときは…当然、JDK 1.5 の javac を使う。逆に型パラメタと継承関係

1.5 の javac で 1.4 のソースを動かすときはオプション □ X ⊃ Y で継承関係を表すものとする。たとえば Object⊃ String。
指定必要• javac -source 1.4 Sample31.java ←ソース• javac Sample31b.java ←(Generics)

JDK1.5□ パラメタつきクラス C<T>を考える。

JDK1.4□ クイズ:ソ ー ス

X ⊃ Y ならば、C<X>⊃ C<Y> だといえるか?

• た
と
え
ば
、ArrayList<Object> ⊃ArrayList<String> か? YES/NO?

import java.util.*;□ 次のように考えるべき

public class Sample31b {public static void main(String[] args) {• X ⊃ Y とは、X 型オブジェクトの代わりに Y 型オブ
ArrayList<String> a = new ArrayList<String>();ジェクトを使っても OK であること (互換性がある
for(int i = 0; i < 10; ++i) a.add("X" + i);
for(int i = 0; i < a.size(); ++i) {こと)
String s = a.get(i);• 例: 「自動車」クラスの変数に「乗用車」を格納しSystem.out.println(s);}ても OK(互換性がある)}}□ ArrayList<Object> a = new ArrayList<String>;

は OK?

• これで先の弱点のうち a、b、e、f が解消。残る c はダメ。

• a.get(0) ...

• 実はこのコードを実行するとき内部的には先と同様のコードが使われている。つまり ArrayList の実装は 1

String が取り出されるから OK。

• a.set(0, Z) ...

Object が入れられないと困るが String しか駄目!!!

つ (均一な実装、homogeneous implementation)。

□ よって先の質問の答えは「NO」であるべきなんだけど…

だから c の制約が残っている。
• c の 緩 和 策 と し て 、JDK 1.5 で int とInteger、double と Double 等 の 自 動 変 換(AutoBoxing/Unboxing) を追加。

□ 実は配列でも同じことが起こる。
□ しかし!

Java では X ⊃ Y ならば X[] ⊃ Y[] になっている

ArrayList<Integer> a = ...
a.add(3); // JDK1.5 で○...
int i = a.get(0); // 〃• 「X[] a = new Y[10];」が可能。そのあとで「a[0]= new X();」→ ArrayStoreException 発生□ C++では→言語設計上のポリシーとして、c は受け入れられない。また、C++では配列は「直接そのオブジェク □ 一 般 に こ う い う の を contravariance/covariance
トが埋め込まれた」ものになるので、コンテナクラスもproblem というらしい
同様でなければ受け入れられない。←フルスピードで動く C に負けないことが原則。

3.3//sample31#include <vector>#include <iostream>

Java Generics の制約□ Java Generics では実行時には型パラメタ情報がなくなっている→そのため、型検査の抜け道が起きる可能性

int main() {vector<int> a;for(int i = 0; i < 10; ++i)a.push_back(i+9);for(int i = 0; i < a.size(); ++i)

→それを防ぐための制約• たとえば、「パラメタ型の配列は作れない」「パラメ
タつき型の配列は作れない」
6

□ C++では共通のインタフェースはない (各コンテナごとに違う) が形としては次のもの。

ArrayList<String>[] lsa = new ArrayList<String>[5];// ↑これは本来は許されない
Object[] oa = (Object[])lsa; // Java では OKoa[0] = new ArrayList<Integer>(); // !!!
...
String s = lsa[0].get(0); // 実行時例外!!!

3.4*p --- 現在の要素を参照++p、p++ --- 次の要素に進める
p == q --- 同じ要素を指すかどうか判定//sample31b#include <vector>#include <iostream>

イテレータ□ コ ン テ ナ の 種 類 → 可 変 長 配 列 (ArrayList<T>、
int main() {vector<int> a;for(int i = 0; i < 10; ++i)a.push_back(i+9);for(vector<int>::iterator
i = a.begin(); i != a.end(); )cout << *i++ << ’\n’;}

vector<T>)、連 結 リ ス ト、B 木 、ハッシュ表 、などなど。
• どれでも「順番に要素を処理する」などの操作は必要→それをどれでも同等に扱えるようにしたい (後でコンテナを取り替えたりしても利用コードは変えないで済むように)。

• 「vectior<int>::iterator」→ vector<int>クラ• 「イテレータ (iterator、反復子)」→次々に要素にアクセスしていくためのオブジェクト。

スにおいて typedef で定義されている iterator という型名。

□ Java では共通の Iterator インタフェースとして規定。
JDK 1.5 では Iterator<T>のように各要素の型が型パラメタになる。

• 普通の「配列要素を指すポインタ」もイテレータとbool hasNext() --- 終わりかどうか調べる
T next() --- 次の値 (T:パラメタ型) を取り出す
void remove() --- 現在値を削除 (今回は使わない)• コンテナにもよるが単なるポインタではないイテレー
タが大半

して使える

import java.util.*;

3.5

public class Sample31c {public static void main(String[] args) {ArrayList<String> a = new ArrayList<String>();for(int i = 0; i < 10; ++i) a.add("X" + i);for(Iterator<String>i = a.iterator(); i.hasNext(); ) {String s = i.next();
System.out.println(s);}}}□ さらに!
いては□ 例:

型パラメタつきクラスを作る「最後の 2 つの値を記憶するバッファ」(前回やったもの) ただし、記憶される値の型は「任意」□ C++版 (クラス定義の中に直接コード本体も書いている。
こうするとインライン展開が可能に。または従来通り分
けて書いてもいいが、その場合は inline と指定。)//sample32#include <iostream>using namespace std;

Iterable<E>を実装するオブジェクト X につ

template<typename T> class last2 {T v1, v2;
public:last2(T x, T y) { v1 = x; v2 = y; }void put(T v) {v2 = v1; v1 = v;}
T get() {T x = v1; v1 = v2; return x;}};for(E v: X) { ...

という for ループ (for-in ループ) を書くと以下と同等に動作
for(Iterator<E> i = X.iterator(); i.hasNext(); ) {E v = i.next(); ...

□ たとえば上の例も ArrayList<E> が Iterable<E> を実装しているので次のように書ける。

int main() {last2<int> a(0, 0);a.put(1); a.put(2); a.put(3);cout << a.get() << ’\n’;
cout << a.get() << ’\n’;
cout << a.get() << ’\n’;
last2<char*> b("", "");
b.put("ab"); b.put("cd"), b.put("ef");cout << b.get() << ’\n’;
cout << b.get() << ’\n’;

import java.util.*;public class Sample31d {public static void main(String[] args) {ArrayList<String> a = new ArrayList<String>();for(int i = 0; i < 10; ++i) a.add("X" + i);for(String s: a) System.out.println(s);}}7template<typename T> inline void swap(T& x, T& y) {T z = x; x = y; y = z;}float a[100]; ... swap(a[i], a[j]) ...

cout << b.get() << ’\n’;}□ Java 版。

• 関数テンプレートの型パラメタは推定される (a[i]import java.util.*;等が float だから T は float) →繁雑な指定が不要

public class Sample32 {public static void main(String[] args) {Last2<Integer> a = new Last2<Integer>(0, 0);a.put(1); a.put(2); a.put(3);System.out.println(a.get());
System.out.println(a.get());
System.out.println(a.get());
Last2<String> b = new Last2<String>("", "");
b.put("ab"); b.put("cd"); b.put("ef");
System.out.println(b.get());
System.out.println(b.get());
System.out.println(b.get());}}• 「float z = a[i]; a[i] = a[j]; a[j] = z;」
がこの場所に埋められているのと同様→高速□ アルゴリズム関数を利用すれば制御構造をこちら側で書かなくてもよくなる。たとえば for each を使うとループが不要になる。
//sample33#include <algorithm>#include <vector>#include <iostream>using namespace std;
template<typename T> void f(T x) {cout << x << ’\n’;}class Last2<T> {T v1, v2;
public Last2(T x, T y) {v1 = x; v2 = y;}public void put(T v) {v2 = v1; v1 = v;}
public T get() {T x = v1; v1 = v2; return x;}}

int main() {vector<int> a;for(int i = 0; i < 10; ++i)a.push_back(i);for_each(a.begin(), a.end(), &f<int>);}• これで for each の中で「f(値)」が繰り返し呼ばれる→「ベクタの各要素を出力」ができる。ループは
不要。

3.6

Standard Template Library (STL)• しかし「合計を取る」だとどうするか?

□ C++の標準ライブラリの土台となった、テンプレートを □ 関数オブジェクト… operator() を持つようなオブジェ
クト。先の「f(値)」というのは関数でなく operator()
駆使したライブラリ群→現在では C++標準ライブラリのの呼び出しでもよいので。
コンテナクラス部分のことをそう呼ぶ。重要なアイデア://sample33b#include <iostream>#include <vector>#include <algorithm>• テンプレートを使った効率のよいコンテナクラス群• 要素アクセスはコンテナクラスのメソッドではなくイテレータ経由 (その方が高速化しやすい)• イテレータに対して働くアルゴリズム群。find (線形探索)、sort (整列)、count(計数)、などなど。

using namespace std;
template<typename T> class sum {T res;
public:sum(T init) { res = init; }void operator()(T x) { res += x; cout<<res<<"\n"; }T result() const { return res; }};• アルゴリズム群はテンプレート関数 (型パラメタつき関数) →高速。
□ 例:

普通の swap(C 版)

void swap(int *x, int *y) {int z = *x; *x = *y; *y = z;}
int a[100]; ... swap(&a[i], &a[j]) ...

int main() {vector<int> a;for(int i = 0; i < 10; ++i)a.push_back(i);sum<int> s(0);s = for_each(a.begin(), a.end(), s);cout << s.result() << ’\n’;}• 関数呼び出しのオーバヘッド、ポインタ経由のアクセス→遅い。しかも型ごとに用意する必要。
□ 関数テンプレート版の swap(C++版)

8• ループ周回を通じて保存されて欲しいものは関数オブジェクトのインスタンス変数にすればよい。→ ルー//sample34b#include <iostream>

プ構造と処理の分離

テンプレートの特殊化

3.7□ テンプレートで一般向けの実装のほかに「特殊ケース」を用意したいことがある。

class point {double x, y;
public:point(double a, double b): x(a), y(b) { }};• たとえば bool(0/1) のバッファだったら 1 ビットず
つ入れれば 32 個の値が 1 語で入るとか…
• コンテナクラスの場合、「ポインタ用」はそれなりのポインタ用のものを使う方がよさそう… (「ポイン
タ用」のクラスを 1 つ用意して残りはすべてそれを

int main() {point a3[] = { point(0,0), point(1,1),
point(2,2), point(3,3), point(4,4) };maxbuf<point> m3(a3[0]);for(int i = 1; i < 5; ++i) m3.put(a3[i]);}呼ぶ→コードを何回も展開しなくて済む→コード量の爆発を防ぐ上で重要なテクニック)□ そのような「特殊ケース」を別途用意できる→特殊化
template <typename T> class last32 {//一般}
template <typename T> class last32<T*> {// ポインタ用}
template <> class last32<bool> {// bool 用}□ 上記のをコンパイルすると…
In method ‘void maxbuf<point>::put(point)’:
22:
instantiated from here
7: no match for ‘point & < point &’□ 確かに「<」がない、と言われる… 次のを入れればよくなるが。
bool operator<(point &p) {return x*x+y*y < p.x*p.x+p.y*p.y;}型パラメタに対する制約

3.8
□ 例:

template<typename T> class maxbuf {T max;
public:maxbuf(T x) : max(x) { }void put(T x) { if(max < x) max = x; }T get() { return max; }};maxbuf<T>というコンテナを作る。

• しかし「コンパイルしてみたら無かった」では実装• 次々に put(T x) で値を入れていく。

の中に立ち入っていてエラーメッセージとしてあま• T get() でその時点での最大値を取得できる。

り良くないのでは…

• 実際、極めて分かりづらいエラーメッセージに遭遇//sample34#include <iostream>

することがよくある• 本来だったら「この型パラメタにはこういう型しかあてはめてはいけませんよ」という指定ができた方

template<typename T> class maxbuf {T max;
public:maxbuf(T x) : max(x) { }void put(T x) { if(max < x) max = x; }T get() { return max; }};がいいのでは?

→ 賛否両論。否定派:

指定が繁雑になり自由度が減る。ともあれ、Java Generics
ではこちらの立場。
□ 上記の Java Generics 版。整数は Integer クラスを使

int main() {int a1[] = { 5, 9, 2, 7, 6 };maxbuf<int> m1(a1[0]);for(int i = 1; i < 5; ++i) m1.put(a1[i]);cout << "a1: " << m1.get() << ’\n’;
double a2[] = { 3.0, -2.7, 6e2, 4e1, 0.5 };maxbuf<double> m2(a2[0]);for(int i = 1; i < 5; ++i) m2.put(a2[i]);cout << "a2: " << m2.get() << ’\n’;}う必要。
import java.util.*;public class Sample33 {public static void main(String[] args) {int[] a1 = { 5, 3, 8, 2, 4 };Maxbuf<Integer> m1 = new Maxbuf<Integer>(a1[0]);for(int i = 0; i < 5; ++i) m1.put(a1[i]);System.out.println(m1.get());
String[] a2 = { "this", "by", "foo", "z", "x" };Maxbuf<String> m2 = new Maxbuf<String>(a2[0]);for(int i = 0; i < 5; ++i) m2.put(a2[i]);□ 型 T には演算子「<」が必要。これを満たさないと…

9• char* → strcmp が使われる

System.out.println(m2.get());}• その他特殊ケースはいくらでも対応可能 … C++の実用性に 1 日の長があるかも?

}class Maxbuf<T extends Comparable<T>> {T max;
public Maxbuf(T x) { max = x; }public void put(T x) {if(max.compareTo(x) < 0) max = x;}public T get() { return max; }}3.9

テンプレートによる mixin クラス□ 前回やったように、mixin とは「他のクラスに混ぜるためのクラス」• それ自体単独でインスタンスを生成しないことから「抽象サブクラス」と呼ぶことも□ Comparable<T>というのは x.compareTo(T y) というメソッドを持ち、このメソッドが x と y の大小関係に応• 前回の話では flavors などの多重継承を使って混ぜじて正/負/零を返す。

ていた□ この方が確かにあらかじめチェックはできるが、窮屈かも• しかし C++のような静的検査な言語では多重継承ではうまく行かない…

□ あらかじめ Comparable<T>を implements しているク □ たとえば、次のようなクラスを考える。
ラスにしか使えない→自分がソースを持っていればいい
class balance {int value;
public:balance() : value(0) { }void update(int v) { value += v; }int getValue() { return value; }};が、そうでないと…

• 実は C++版にも同様の問題がある。たとえば char*の maxbuf を取ろうとすると「アドレスが最大の」ものが取れてしまう…求めていることと違う。
□ C++の場合は、単独関数テンプレートと特殊化を使えばclass maxbuf {int max;
public:maxbuf() : max(0) { }void update(int v) { if(v>max) max=v; }int getValue() { return max; }};OK。
//sample34c#include <iostream>#include <cstring>using namespace std;
template<typename T> bool lt(T x, T y) {return x < y;}template<> bool lt(char* x, char* y) {return strcmp(x, y) < 0;}
template<typename T> class maxbuf {T max;
public:maxbuf(T x) : max(x) { }void put(T x) { if(lt(max, x)) max = x; }T get() { return max; }};□ 「update の回数を数える」
class count {int num;
public:count() : num(0) { }void update(int v) { ++num; update(v); }int getCount() { return num; }};□ 「更新履歴を記録する」
class history {int record[1000], nrecs;
public:history() : nrecs(0) { }void update(int v) {record[nrecs++] = getValue(); update(v);}void showHistory() {for(int i = 0; i < nrecs; ++i)
cout << ’ ’ << record[i];cout << ’\n’;}};

int main() {int a1[] = { 5, 9, 2, 7, 6 };maxbuf<int> m1(a1[0]);for(int i = 1; i < 5; ++i) m1.put(a1[i]);cout << "a1: " << m1.get() << ’\n’;
char* a2[] = { "this", "by", "foo", "z", "x" };maxbuf<char*> m2(a2[0]);for(int i = 1; i < 5; ++i) m2.put(a2[i]);cout << "a2: " << m2.get() << ’\n’;}□ 特殊化の応用• 一般の T →「<」が使われる□ これを次のようにして使いたい。

10int a[] = { 5, 9, 2, 7, 6 };history< count< balance > > c1;
count < history< maxbuf > > c2;
for(int i = 0; i < 5; ++i) {c1.update(a[i]); c2.update(a[i]);}cout << "c1: " << c1.getCount(); c1.showHistory();cout << "c2: " << c2.getCount(); c2.showHistory();

class MyClass :public balance, count, history {};□ flavors ではこれでできる (どっちの update が呼ばれるかの規則があって OK)。しかし C++ではそもそも

getValue() や update() の宣言がないと型検査できな
くてアウト。
□ ではどうするか…

}□ mixin クラスを使うことで、1 つのクラスに盛り込まれている複数の側面を分離して記述し、使う時に組み立て• count や history で親クラスを指定すればもちろん動くようになる。

ることができる。

• しかしさまざまなものにこれらの機能を組み込もう □ しかし、実際には 1 つの「側面」が複数のクラスにまたがって存在していることが普通→このような「一群のクと思って作ったのに、決め打ちで親クラスを書いてラス」を 1 つの「層」として、それを積み重ねてシステしまうのでは 1 つにしか使えない (または繰り返し
ムが構成されるというイメージ。

コピーになる) のでよろしくな。

□ そのようなものを実現するには→ C++でもクラスの中にクラスが書けることを利用し、外側クラスをパラメタつきとする。
その親クラスをテンプレートパラメタで指定す• ではどうすればいい?
□ 答:
る!!

template<class T> class ThisLayer : public T {public:class First : public T::First { ... };class Second : public T::Second { ... };...
};//sample35#include <iostream>class balance {int value;
public:balance() : value(0) { }void update(int v) { value += v; }int getValue() { return value; }};□ こうすれば、一群のクラスで Fist は First どうし、Second は Second どうし、…で縦に合成が起きる。
• ThisLayer の中にはこの層が実現する機能のためのデータやコードをまとめて入れることができる。

class maxbuf {int max;
public:maxbuf() : max(0) { }void update(int v) { if(v>max) max=v; }int getValue() { return max; }};template<class T> class count : public T {int num;
public:count() : num(0) { }void update(int v) { ++num; T::update(v); }int getCount() { return num; }};• このような構成を「mixin layers」と呼ぶ。
• このような「構成法」の代替案→言語自体の拡張 (AOP
言語) →すぐ後で

3.10

テンプレートメタプログラミング (簡単に)□ テンプレートの展開→関数の評価のようなもの→計算に利用できる//sample36#include <iostream>
template<int n> class Fact {public:enum { RET = Fact<n-1>::RET * n };};template<> class Fact<0> {public:enum { RET = 1 };};template<class T> class history : public T {int record[1000], nrecs;
public:history() : nrecs(0) { }void update(int v) {record[nrecs++] = T::getValue(); T::update(v);}void showHistory() {for(int i = 0; i < nrecs; ++i)
cout << ’ ’ << record[i];cout << ’\n’;}};

int main() {std::cout << Fact<5>::RET << ’\n’;}• これを動かすと当然「120」が表示されるが、それは実行時に計算しているのではなく、コンパイル時にint main() {11「5*4*3*2*1*1」という式が生成され、それが計算されている→高速• もっと複雑なデータを処理したり、複雑な手順を持つ

4.1

3-Lisp: リフレクションの元祖□ ベースレベルとメタレベルを区別

関数を生成したりすることもできる → テンプレー• ベースレベル:トメタプログラミング• メタレベル:• 使いこなすのはとっても難しいと言われている (あまりやりたくない)

通常の実行
ベースレベルの実行系の情報 (バインディング、継続等) が見える

• メタレベルを変更→ベースレベルでの対応する状態
変化が起こっている→これにより、言語セマンティ

3.11

クス (実行順序の制御等) が拡張可能

本節のまとめ□ 総称的プログラミング (型パラメタ、パラメタつき型)□ 3-Lisp のさらに特徴→「メタレベル」はさらに「メタメタレベル」によって制御可能→無限の reflective→ C++ テンプレート、Java Genrics で実現 (内容はかなり違っている)。主な用途:

tower になっている

コンテナクラス• 実装上は「遡られたところまで自動的にメタレベル□ STL(C++) → イテレータによるアクセス、汎用アルゴ

を用意」

リズム
□ 型パラメタの制約 → 賛否分かれるところ。Java では
インタフェース/サブクラスによる制約指定可能 (だが不自由でもある) → C++に対する制約機構 (concepts)
は設計途上 → 後で少し紹介

4.2

Smalltalk のクラスとメタクラス□ Smalltalk では「クラス」もまたオブジェクト• クラスに対してメッセージを送る→メソッドを追□ mixin クラス (C++) → 親クラスを拡張するための抽象加したり修正したり等ができる (実行環境全体がSmalltalk で書かれているので当然といえば当然)

サブクラス□ 全体として C++テンプレートは強力、しかし難しい。より詳しく知りたい人は:□ クラスオブジェクトは Metaclass というクラスのインスタンス。たとえばクラス Collection のクラスオブ• アンドレイ・アレキサンドレスク著, 村上訳, Modern
C++ Design, ピアソン, 2001.

ジェクトは Collection class(という式でアクセス)。

(むずかしい)Collection class は Metaclass というクラスのイン• επιστημη, 高橋晶, C++テンプレートテク
ニック, ソフトバンク, 2009. (少しやさしい。筆スタンス

頭著者の読みは「えぴすてーめー」)• Metaclass は各クラスオブジェクトを初期設定する機能をおもに提供→ Metaclass を修正すると、4

Smalltalk システム全体の動作が変化させられる

自己反映機能□ 自己反映 (reflection):

実行中のコードが、実行系の情報にアクセスしたり、実行系の状態/動作を変更したりできるような機能• 狭い意味では前者のみ (後者を reification と呼んで区別することも)4.3□ 「オブジェクト」を統括する (ふるまいを定義する) オ
ブジェクト→「メタオブジェクト」(例:

デバッガ→実行系の内部状態を調べたり変更す

クラスに対してはメタクラス)□ メタオブジェクトが提供するサービス、API →メタオブ□ 何のためにそんなことをするのか?

• 例:

メタオブジェクトプロトコル (MOP)

ジェクトプロトコル□ 最近の多くの言語ではメタオブジェクトプロトコルを提供することで自己反映機能をさまざまに利用可能

る必要• 例: システムの拡張→「任意の手続き呼び出しを遠隔メッセージに変換」など• CLOS: メソッド呼び出しの意味づけなどを自由に変
更可能

• 例:

• OpenC++: コンパイル時 MOP →メタオブジェクトを定義すると、コンパイル時にメタオブジェクトがソー

拡張可能言語 (構文や意味づけ等)

スを変更した上でコンパイル→言語の意味づけが変化させられる12

4.4

Java の自己反映機能

cons[cno].newInstance(new Object[]{});
Method[] meths = cls.getMethods();for(int i = 0; i < meths.length; ++i)
System.out.println(""+i+": "+meths[i]);System.out.print("Method Number? ");System.out.flush();int mno = Integer.parseInt(br.readLine());
Object res =meths[mno].invoke(obj, new Object[]{});
System.out.println("Result Class:"+(res.getClass()));
System.out.println("Result: "+res);} catch(Exception e) { e.printStackTrace(); }□ Java の自己反映機能→処理系そのもを変更する、という部分はない。

• 内部の状態をのぞく• のぞいた情報を利用して、その場でメソッド呼び出し等を組み立てて実行させられる□ 強い型の言語は「型が合わなければ扱えない」→リフレ
クションのような自由自在なことは表しにくい}• Java ではこれらをきちんと型を割り当てた上で可能
にしている

}
}

• ある意味では、Lisp 等の「eval」(任意のプログラ □ これをたとえば次のクラスに対して使ってみる…
ムを合成してその場で走らせる」を強い型の言語上
class Sample33Test {int val;public Sample33Test() { val = 1; }public Sample33Test(int i) { val = i; }public Sample33Test add() {return new Sample33Test(val+1);}
public Sample33Test sub() {return new Sample33Test(val-1);}
public String toString() {return "Sample33Test("+val+")";}}

で可能にしたといえる□ 任意のオブジェクトは getClass() でその Class オブ
ジェクトを取得できる• または、static メソッド Class.forName("...") でも□ Class オブジェクトはそのクラスに関する情報を取得するメソッドを持つ• 例: getConstractors(), getMethods(),
getMembers()□ Constructor オブジェクトの newInstance() を呼ぶと

□ なお、この方法で通常取れるのは public なものだけ (セキュリティ上の制約)

オブジェクトが生成される□ Method オブジェクトの invoke() を呼ぶとメソッドが
実行できる

4.5

自己反映機能とコード生成ツール□ たとえば、任意のクラスを 1 つもってきてオブジェクト □ 例: コンポーネントツールや GUI ビルダを生成しメソッドを呼ぶ (ただし引数はすべて空) というプログラム• 画面で直接部品を配置したり動かしてみたりしたい• 動かせるためには「部品そのもの」を操作したい

import java.io.*;import java.lang.reflect.*;• しかし、部品オブジェクトは部品ごとに「使い方」が異なる
public class Sample33 {public static void main(String args[]) {• →自己反映機能を用いて調べつつ「呼び出せば」よいBufferedReader br =□ Java による GUI 部品配置の例
new BufferedReader(
new InputStreamReader(System.in));import java.awt.*;
while(true) {import javax.swing.*;try {import java.awt.event.*;
System.out.print("Class Name? ");import java.lang.reflect.*;
System.out.flush();String cname = br.readLine();public class Sample34 extends JPanel {if(cname.equals("")) break;int x1, y1, x2, y2, x0, y0, width, height;
Class cls = Class.forName(cname);
Component c0 = null;Constructor[] cons = cls.getConstructors();
JLabel l0 = new JLabel("Component:");for(int i = 0; i < cons.length; ++i)
JTextField t0 = new JTextField();
System.out.println(""+i+": "+cons[i]);JButton b0 = new JButton("Create");System.out.print("Constructor Number? ");JButton b1 = new JButton("Move");
System.out.flush();JLabel l1 = new JLabel();int cno = Integer.parseInt(br.readLine());
JComboBox c2 = new JComboBox();Object obj =13

public void mouseReleased(MouseEvent e) {JLabel l2 = new JLabel("String:");x2 = e.getX(); y2 = e.getY(); calc();
JTextField t2 = new JTextField();}
JButton b2 = new JButton("Call");});
JPanel p1 = new JPanel();addMouseMotionListener(new MouseMotionAdapter() {Method[] meths; int[] maps;
public void mouseDragged(MouseEvent e) {public Sample34() {x2 = e.getX(); y2 = e.getY(); calc();
setLayout(null);}add(l0); l0.setBounds(10, 40, 80, 30);});add(t0); t0.setBounds(100, 40, 200, 30);}add(b0); b0.setBounds(320, 40, 80, 30);
private void calc() {add(b1); b1.setBounds(420, 40, 80, 30);x0 = Math.min(x1, x2); y0 = Math.min(y1, y2);add(l1); l1.setBounds(10, 70, 500, 30);
width = Math.abs(x1-x2); height = Math.abs(y1-y2);add(c2); c2.setBounds(10, 100, 500, 30);
p1.setBounds(x0, y0, width, height);
add(l2); l2.setBounds(10, 140, 80, 30);}add(t2); t2.setBounds(100, 140, 200, 30);
public static void main(String[] args) {add(b2); b2.setBounds(320, 140, 80, 30);
JFrame f = new JFrame("demo");add(p1); p1.setBounds(0,0,1,1);
f.add(new Sample34());
p1.setBackground(Color.green);f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
b0.addActionListener(new ActionListener() {f.setSize(600, 600);
public void actionPerformed(ActionEvent e) {f.setVisible(true);try {}c0 = (Component)Class}.forName(t0.getText()).newInstance();p1.setBounds(0, 0, 1, 1);
add(c0); c0.setBounds(x0, y0, width, height);
t0.setText("");
4.6 本節のまとめ
meths = c0.getClass().getMethods();
maps = new int[meths.length];□ 自己反映機能→「プログラムの中で、プログラムそのも
c2.removeAllItems();のを操作できる」→より柔軟なソフトウェア構成が可能
for(int i=0,k=0; i < meths.length; ++i) {Class[] arg =になるmeths[i].getParameterTypes();if(arg.length == 1 &&• その反面、プログラムが分かりにくくなる(arg[0] == String.class ||• どこまで「静的」(コンパイル時)、どこから「動的」
arg[0] == Object.class)) {(実行時) の線引き→トレードオフを考えることが
c2.addItem(meths[i].toString());
maps[k++] = i;重要}}
□ ついでに: オブジェクト指向言語の諸側面のまとめ} catch(Exception ex) {l1.setText(ex.toString());• 非常に多数の機能がある、ということは分かったと
}
思う
}
});
• それらすべてに「発明された理由」はもちろんある
b1.addActionListener(new ActionListener() {• しかし「それらがすべてが今いるのか?」は別の問題
public void actionPerformed(ActionEvent e) {if(c0 != null) {• 言語の多様な機能を使えば使うほど「難しく」もなる
p1.setBounds(0, 0, 1, 1);→「機能の増加」と「簡潔に/分かりやすく記述でき
c0.setBounds(x0, y0, width, height);
る」のトレードオフについて常に考える(例: Java}}vs C++)});
b2.addActionListener(new ActionListener() {public void actionPerformed(ActionEvent e) {5 Haskell: 関数型言語
try {Method m = meths[maps[c2.getSelectedIndex()]];
m.invoke(c0, new Object[]{t2.getText()}); □ 関数型言語 --- 「関数とその適用に基盤を置く言語」
t2.setText("");• 「副作用のない言語」 --- こちらの方がぴったりす} catch(Exception ex) {l1.setText(ex.toString());
る感じ?
}• 「参照透明性」(referencital transparency) と
}
});
も呼ぶ
addMouseListener(new MouseAdapter() {• 副作用はバグの原因となり、また並列実行を難しく
public void mousePressed(MouseEvent e) {する
x1 = x2 = e.getX(); y1 = y2 = e.getY(); calc();}• 副作用がなければ遅延評価を標準としやすい

14

5.1

関数型言語の歴史

Main> (\x -> x + x) 2
4

□ Lisp (McCarthy) --- ラムダ式に基盤□ 中置記法、前置記法• 確かに「関数とその適用」に基盤を置くが…

• 関数名を ‘...‘ で囲むと中置記法にできる。逆に中置演算子は (...) で囲むと普通の関数名と同じに扱える• 副作用はそこら中で使う「(setq x 1)」「(replaca(cdr x) y)」• このため関数型と呼ばずに「適用型」(applicative)

Main> 1 ‘add‘ 2
3Main> (+) 1 2
3と呼ぶ向きも• Lisp 族の言語は多数あり今日でも増えている• Lisp 1.5, Scheme, CommonLisp, EmacsLisp,...

□ カリー化• 「a -> a」は、「a 型を引数として受け取り、a 型を結果として返す関数」□ FP (Backus) --- 最初の「副作用を避ける」試み• 「副作用がないと出力も結果の保存もできない」問• すべての関数は引数は 1 つ• で は 、先 程 の add や (+) は? 「a -> a -> a」
は「a を引数として受け取り、a -> a を返す」

題に直面→「トップレベルは特別」扱い• 実験的な言語で実用性はない

add1 = add 1
add2 = (+) 2□ ML (Milner) --- 実用となった最初の「関数型」言語• つまり add に 1、(+) に 2 を与えた結果も 1 つの関数

• 「書き換えられる値」を明示的にその旨定義「ref 1」

Main> :type add1
add1 :: Integer -> Integer
Main> add1 2
3• 書き換えが起こる箇所を限定し、残りは参照透明• 型推論による強い型検査• 多くの処理系、拡張言語の基盤となる• 「N 引数の関数に 1 つの引数を与えて、残り N-1 引
数を受け取って結果を返す関数を得る」ことを「部• SML (Standard ML), Miranda, CAML, OCAML(Objective CAML)

分適用」と呼ぶ□ Haskell --- 参照透明性をすべてに適用• 遅延評価をすべてに適用• このように関数を全部 1 引数として扱うこと→カリー化• 副作用は IO モナドと呼ばれる形で統一して扱う• なお、今度は add1 の引数や返値の型は Integer。これは「1 と足す」ことまで分かったから• 並行プログラムにも複数の機能を通じて対応

5.2• このように、演算や引数の値によって式の型を推論すること→型推論 (type inference)• 中置記法を使えば第 2 引数を部分適用することもできる

Haskell 入門□ 基本は「関数定義」

sub x y = x - y
sub1 = (‘sub‘ 1)• 以下の実行例は Hugs98 という処理系によるadd x y = x + y← (? ‘sub‘ 1) の意味□ 以下では「関数の型」は宣言し、中で使う変数は宣言し• プログラムはファイルに記述し、それを読ませて、ないことにする ←型チェックと記述の手間を勘案して実行• すべての式は強く型付け。 「:type 式」で型を調べられる□ 再帰関数 --- 繰り返しの代わりにすべて再帰を使う• 変数は書き換えられないので別のインスタンスを作るしかない

Main> :load "test1.hs"
Main> add 1 2
3Main> :type add
add :: Num a => a -> a -> afact1 :: Integer -> Integer
fact1 n| n > 0= n * fact1 (n-1)| otherwise = 1• これは「ある型 a は Num の一種であり、add は a ->a -> a 型」と読む• ガードを使った本体の振り分け• 字下げに意味がある (字下げが増える→上の行の内側)□ 定義しないで直接関数を書くこともできる (λ式)15• この素朴な定義だと再帰 1 回ごとに中間結果を保存する必要があるMain> addlist2 [1,2,3][3,4,5]• 別バージョン→こちらの方は中間結果の保存不要• 補助関数 f2sub を where を使って定義• 実はこれと同じことをする標準関数 map が用意されている →プログラマが書くのは「addlist2 = map(+ 2)」だけ

fact2 :: Integer -> Integer
fact2 n = f2sub 1 n
where
f2sub r n
| n > 0= f2sub (n*r) (n-1)| otherwise = r□ 同様のものとして「リストから特定の条件のものを選別」

分の結果とする」場合→実装では関数の先頭に新myfilter fn (x:xs) =if (fn x)
then x:myfilter fn xs
else myfilter fn xs
myfilter fn []= []し い 引 数 を 持って ジャン プ (TCO --- tail calllarger1 = myfilter (> 1)• このように「最後に自分自身を呼びその結果を自optimization)
Main> larger1 [0,1,2,3][2,3]• TCO を意識して書く必要→ちょっとワザを強制されている感じ?

□ こ れ も 標 準 関 数 filter が 用 意 さ れ て い る の で

5.3「larger1 = filter (> 1)」でよい

リストデータ構造□ リスト --- Lisp 以来の、関数型言語で広く使われる□ 「合計」のようなものは?

データ構造• foldl (+) 0 [w,x,y,z] = ((((0+w)+x)+y)+z)• foldr (+) 0 [w,x,y,z] = (w+(x+(y+(z+0))))• Haskell では「:」がリストの「先頭」と「残り」をつなぐ構成子mysum :: [Integer] -> Integer
mysum = foldr (+) 0• [1,2,3] == 1:2:3:[]

Main> mysum [1,2,3,4]
10□ 素朴には、リストを扱う関数は再帰で書ける• ここでは説明しない理由により、foldr の方が効率がいい

addlist1 :: [Integer] -> [Integer]
addlist1 (x:xs) = x+1:addlist1 xs
addlist1 []= []• 引数部分にパターンを記述→パターンマッチによる
枝分かれ□ 例題:「1 から 10 までの奇数の自乗和を求めよ」• 「1 から 10 までのリスト」は次の記法で作れる

Main> addlist1 [1,2,3][2,3,4]Main> [1..10][1,2,3,4,5,6,7,8,9,10]• 関数の合成: (f (g x)) = (f.g) x• 考え方: 「奇数のものを抜き出し、自乗して、合計」□ 実は上の例のようなのはいまいち• 「1 足す」という仕事と「リストにそれぞれ適用」という仕事は別の概念 → 分けた方がいい

oddsqsum :: [Integer] -> Integer
oddsqsum = (foldr (+) 0).(map sq).(filter evenp)
where
evenp x = mod x 2 /= 0
sq x = x * x

mymap :: (a -> a) -> [a] -> [a]mymap fn (x:xs) = fn x : mymap fn xs
mymap fn []= []• このように「引数に言及せず関数だけ合成して行く」
やり方 (「pointless な記法」) が関数型らしいところ

addlist2 :: [Integer] -> [Integer]
addlist2 = mymap (+ 2)• mymap の型は「ある型 a を受け取り a を返す関数と、
a の並んだリストを与えると、a の並んだリストを返す」

Main> oddsqsum [1..10]165□ リスト内包表記• この a のところに任意の特定の型が入る ← 型パラ
メタ• これに「2 足す」関数を与えるので、できあがる関
数は「整数のリストを受け取り、整数のリストを返す」型

16[式|変数<-リスト, 変数<-リスト, ..., 条件]
Main> [(a,b)|a<-[1..5],b<-[1..5],mod a b == 0][(1,1),(2,1),(2,2),(3,1),(3,3),(4,1),(4,2),(4,4),(5,1),(5,5)]

• 連結演算 (++) の右側の fibx の呼び出しは、必要になった時に行われる• quicksort を ML で書くと…
qsort :: [Integer] -> [Integer]
qsort (x:xs) =(qsort [a|a<-xs,a<x])++[x]++(qsort [a|a<-xs,a>x])
qsort [] = []Main> take 10 fib[1,1,2,3,5,8,13,21,34,55]□ 遅延評価の利点• 「++」はリストの連結演算• 再帰を書くのに枝分かれが要らない (先の fib の例)

5.4

→シンプル

型クラス

• 「いくつまで用意するか」を考えないでよい (無限に用意して使う時に必要なだけ取る)□ ところで、整列は「順序があるもの」のリストなら何でもいいはず• きっちり必要なだけしか計算しないで済む• 「演算子 > ::a -> a -> Bool を持つような型 □ 遅延評価の弱点a」のように、「ある型についてこういう関数を持つ」• 普通の人は慣れていないということを表現する → Haskell では「型クラス」• いつ実行されるか予測しづらい ← しかし、純粋なを使う (オブジェクト指向のクラスとはまったく別
関数型言語であれば副作用がないので、いつ実行さのもの)。
れても結果は同じ (はず)• 上の場合は型宣言を次のように直す:
qsort :: Ord a => [a] -> [a]5.6

Main> qsort "How are you?"" ?Haeoruwy"□ 既存の型をもとに新しい型を定義 → data 定義 (代数的データ型の定義。他にもいくつか型を定義する方法がある)• 実は「文字列」は「文字のリスト」なので。
□ 他の型クラス: 「等しい演算 (==) を持つ」:
字列に変換できる関数 show を持つ」:

5.5

データ型の定義

Eq, 「文Show など。

data Tree a = Leaf | Node (Tree a) a (Tree a)deriving (Show, Eq)• 2 分木を定義。保持するデータは型パラメタ a で表す

遅延評価• show と (==) を自動的に生成• データを 1 つだけ持った木を生成□ 実は「無限のリスト」も作れる。「[1..]」• ただし、無限のリストを打ち出すと無限に打ち出し始めるが…
• 「先頭から N 個取る」関数 take と組み合わせれば問
題なく大丈夫Main> take 10 [1..][1,2,3,4,5,6,7,8,9,10]• 無限リストに対して演算することも問題ない
Main> take 10 (map (* 2) [1..])[2,4,6,8,10,12,14,16,18,20]• 普通の言語: 関数 (メソッド) 呼び出し時にパラメ
タは値に評価される (正格評価, eger evaluation)• Haskell: 関数適用は「そのままの形」で覚えられている。実際にその値が必要になった時にはじめて評価 (実行) される (遅延評価, lazy evaluation)• 例: 「フィボナッチ数から成る無限リスト」を計算する関数 fib。(引数がないので -> がなく結果の型
だけ)

newtree :: a -> Tree a
newtree x = Node (Leaf) x (Leaf)• 木への挿入 (副作用はないので挿入した新しい木を返す)
instree :: Ord a => Tree a -> a -> Tree a
instree (Leaf) x = newtree x
instree (Node l y r) x
| x < y = Node (instree l x) y r| x > y = Node l y (instree r x)
| otherwise = Node l y r
Main> instree (instree (newtree 3) 5) 2
Node (Node Leaf 2 Leaf) 3 (Node Leaf 5 Leaf)• 木の中にめざすデータがあるかどうか検索
searchtree :: Ord a => Tree a -> a -> Boolsearchtree (Leaf) x = False
searchtree (Node l y r) x
| x < y= searchtree l x| x > y= searchtree r x| otherwise = True
Main>searchtree (instree (instree (newtree 3)5)2)2
True
Main>searchtree (instree (instree (newtree 3)5)2)4
False

fib :: [Integer]
fib = fibx [] 1 1
wherefibx l a b = l ++ (fibx [a] b (a + b))

17

5.7

IO モナド□ 最大の問題:s2 <- getLine
putStr (s2 ++ s1)
return ()副作用がないのに、どうやって入出力とかするの?

(C で getchar() を 2 回呼んだら別の文字□ Haskell は副作用のない言語、というのは本当なのか?
が取れて来るし…)• IO a を使うことで「副作用のある箇所を明示/分離• 答え: 「世界を関数の引数の一部として渡し、世界している」という方が正確を返してもらう」• ほとんどの場所は IO a を使わずに書ける→副作用の• このために「IO a」という型を使う。これが「世界ない世界の状態ともに型 a の値を持っている」ことを表す。
• 「少量の副作用のある世界から、大量の副作用のな• 「IO a」は Monad という型クラスに属していて、こい世界を呼び出してやりたい仕事をこなす」と考えの型クラスは次の 2 種類の演算 (関数) を定義しているるのがいいかも(>>=) :: IO a -> (a -> IO b) -> IO b
return :: a -> IO a

• 重要なのは (>>=) で、これは「ある世界の状態での

5.8

Haskell のまとめ

a の値と、a の値を処理してある世界の状態での b の □ 関数型プログラミング言語 Haskell --値を返す関数とを組み合わせることで、処理を実行• 高階関数を駆使するなどにより記述がコンパクトした後の世界の状態での b の値を返す」演算子。
• 強い型検査、ただし型宣言はしなくても型推論が補っ• 入出力を行う関数などはすべて、結果が IO a 型に
てくれる
なっている
• 参照透明性 --- ある式を評価した結果は常に同じ

Main> :t getLine
getLine :: IO String
Main> :t putStr
putStr :: String -> IO ()• 遅延評価 --- 無限データ構造なども作れる。実際に値を計算するのは「使われた時」でよい• 副作用のある部分は明確に分離して記述 (型が違う• なお型「()」は unit と読み、「何か値を渡す必要がの分かる)

あるが値の内容は何もなくていい」時に使う。その値もやはり「()」□ かなり「違う世界」ですが、どうですか?

□ メイン関数は「IO ()」を返す関数を実行できる (=副作用を持つ動作を実行できる)

• 例題:

6

2 つ文字列を読み込み、逆順に連結して出力

test1 :: IO ()test1 = putStr "str1? ">>=\x1 -> getLine>>=\x2 -> putStr "str2? ">>=\x3 -> getLine>>=\x4 -> putStr (x4 ++ x2)>>=\x5 -> return ()第 3 回課題□ 以下の課題から 1 つ以上を選択してプログラム作成ない
し実験を行ない、作成したプログラムが課題を達成していることを論ぜよ。課題中に指定した考察をきちんと書くこと。
□ (11) JavaScript を用いて、自分の Web ページに動きや機能をつけるような「ライブラリ」(つまり自分だけにしか使えないのではなく、他人にあげたら使ってもらえるような形のもの) を作ってみよ。その経験に基づ
いて、JavaScript によるプログラミングと他の言語(Java 等) によるプログラミングの違いについて考察せよ。「動きや機能」の例としてはたとえば次のものが考

Main> test1
str1? aaa
str2? bbb
bbbaaa

えられる (ただしこれらに限定せず自由にアイデアを出してよい)。

• この「>>=」でつなげて書くのは書きづらくよみづら
いので、これと同じことをもっと短く書ける do という構文が用意されている• HTML 要素を動かしたり現われさせたり消したりさせる• ポップアップ/プルダウンメニュー機能 (サブメニュー

test2:: IO ()test2 = do
putStr "str1? "s1 <- getLine
putStr "str2? "も出せるとなおよい)• ページ内でクリックすることでクリックした個所を強調するなどページ内容が加工できるようにする
18

□ (12) C++テ ン プ レ ー ト ま た は Java Generics (JDK

1.5 以降必要) を用いて、自分なりの「汎用的な役に立• 企業科学専攻システムズマネジメントコース --- 博
士課程つクラス」を開発してみよ (イメージとしては max バッ• http://www.gssm.otsuka.tsukuba.ac.jp/

ファや last2 バッファのような感じでよい)。実際に複数の型をあてはめて動作させること。また、それを使っ□ 修士では、2006 年度から「4 プログラム制」として、情報系の人も積極的に受け入れるています→興味ある方はた場合と使わずに「普通に」書いた場合の性能比較も行

ぜひご検討を。

うこと。(さらに、C++テンプレートと Java Generics□ 博士課程 (入試は 8 月提出/9 月試験。例年だと 2 月にの両方作って両者の比較もするとなおよい。)□ (13) C++テンプレートメタプログラミングで階乗以外の何らかの値の計算をさせてみよ (組合せの数とかフィボナッチ数とか?)。その上で、普通のコードで計算した場合と性能比較を行ってみよ。もしコンパイルが異常に遅いならその原因も究明せよ。
□ (14) Java 言語の自己反映機能を使った何らかのプログ
ラムを動かしてみよ。
□ (15) Haskell 言語を使って簡単なプログラムを書いてみよ。それと同じ処理をする C++ないし Java のプログ
ラムも書き、比較してみよ。

7

さいごに

□ この講座では、さまざまなプログラミング言語に現れる
概念を、その設計思想、用途、実装、特徴、問題点などの観点から整理して見てきたつもりです。
□ 構成としては、1 回目→プログラミング言語一般〜抽象
データ型、2 回目→オブジェクト指向、3 回目→より「変わった」「新しい」の話題、のように構成しました。
□ 例年「オブジェクト指向の将来は (次は) 何か」みたいな質問がありますが、私が知りたいです… とりあえず、

C++ではさらにテンプレートが多く使われるでしょうとか、それくらいのことは分かっていますが。
□ 関数型プログラミングは最近人気が出て来ているので、昨年度から入れるようにしたのですが、どうだったでしょうか。
□ ともあれ、おつかれ様でした。

8

おまけ: 久野の所属先について□ 筑波大学 (東京地区) ビジネス科学研究科 --- 社会人
対象の夜間大学院• 「東京地区」というのは文京区大塚にある (旧・東京教育大の跡地)。最寄り駅:

茗荷谷 (東京メトロ丸の内線)1 分。茗荷谷は池袋から 5 分、JR 東京駅から15 分。
• (2010 年度は建物を建て替え中→神保町に仮校舎)• 経営システム科学専攻 --- 修士課程
19

も試験あり) は、修士を持っている人を対象として、在職のまま「博士 (経営学)」または「博士 (システムズ・
マネジメント)」を取得。情報系の人も多数受け入れています→修士持っていて「研究」に興味のある方はぜひご検討を。