Comments
Description
Transcript
初期プログラミング教育のための スクリプト言語/対話型
論文
KIT
Progress№24
№24
KIT
Progress
初期プログラミング教育のための
スクリプト言語/対話型言語の検討
Study of Scripting/Interactive Languages forInitial Teaching of
Programming
堀田英一
Eiichi HORITA
大学における初期プログラミング教育のためには，従来，C 言語や Java を中心とす
るコンパイル型のプログラミング言語を使用することが一般的であった．この理由と
しては，この種類の言語の方がスクリプト言語等に比較して一般に処理性能が高く周
辺ライブラリも充実していたことが挙げられる．一方，近年の動向として，Python 言
語や数値計算ツール MATLAB 組込のスクリプト言語などの性能が向上し，周辺ライブ
ラリも充実するにつれて，これらのスクリプト言語/対話型言語を初期プログラミン
グ教育に適用する動きも一部で始まっている．本稿ではこれらの経緯と動向を踏まえ
て，大学における初期プログラミング教育において，スクリプト言語/対話型言語を適
用する可能性と，適用した場合の利害得失を検討する．プログラミング教育の内容と
しては，データ構造/アルゴリズムの理解，数値計算，記号処理を取りあげる．
キーワード：プログラム言語，スクリプト言語，対話型言語，ルービック・キューブ
For initial teaching of programming in universities, it has been
common to use C language or Java which are classified as complied
languages. The reason for this choice has been that performance of these
languages were substantially higher than that of scripting/interactive
languages, and libraries for compiled languages were richer than those
for scripting/interactive languages. In these days, however, the
performance of scripting/interactive languages, such as Python, has
improved significantly, and their libraries have improved remarkably.
As a result, attempts have started to employ scripting/interactive
languages for initial teaching of programming. Given the circumstances,
we investigate the possibility to apply scripting/interactive languages to
initial teaching of programming. As programming topics, we deal with
the understanding of datastructures/algorithms, numerical computation,
and symbolic processing.
Keywords: programming language, scripting language, interactive
language, Rubic cube
１. はじめに
本稿の主題は，大学１，2 年次においてデータ構造・アルゴリズム，及びプログラミングを学習する
に際して，どのようなプログラミング言語/環境がふさわしいかという問題である．データ構造やアルゴ
タイトル
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
123
リズムの学習においてはプログラミング言語を介する必要は必ずしもなく，フロー・チャート等を用い
て抽象的に理解することが重要であるという意見もある．著者はこの意見には反対である．その理由に
ついては本稿全体にわたって論じていくが，先ず次のことを指摘しておきたい．C.A.R. Hoare が チュ
ーリング賞受賞講演で述べているように，アルゴリズムの記述自体がプログラミング言語等の適切な表
現手段を必要とするということである．1) 計算機科学に著名な貢献をした Hoare の最初の大きな仕事
は Quicksort の提案とその計算量解析であった．1960 年に，Quicksort のアイディアを得たときには，
適切な表現手段がなく他人に説明することが困難であった．その後，再帰的手続き呼び出しをサポート
する Algol 60 の言語仕様に出会ってはじめて Quicksort アルゴリズムの明確な定式化と計算量解析が
可能になったとのことである．これと関連してプログラム言語の役割について次のように述べている．
「I have regarded it as the highest goal of programming language design to enable good ideas
to be elegantly expressed」 (「プログラム言語設計の最上の目標は，よいアイディアをエレガントに
表現できるようにすることにあると考えてきた」
）
．著者もこの主張に賛成であり，第 2 章以降で幾つか
の言語を比較するにあたって重要な比較基準とする．
大学における初期プログラミング教育のためには，従来，C 言語や Java を中心とするコンパイル型の
プログラミング言語を使用することが一般的であった．その理由としては，この種類の言語の方がスク
リプト言語等に比較して一般に処理性能が高く周辺ライブラリも充実していたことが挙げられる．
一方，
近年の動向として， Python 言語や数値計算ツール MATLAB 組込のスクリプト言語等の性能が向上し，周
辺ライブラリも充実するにつれて，これらのスクリプト言語/対話型言語を初期プログラミング教育に
適用する動きも一部で始まっている．9) 本稿ではこれらの動向を踏まえて，大学における初期プログラ
ミング教育において，スクリプト言語/対話型言語を適用する可能性と，適用した場合の利害得失を検討
する．
初期プログラミング教育の内容としては，データ構造・アルゴリズムの理解，数値計算，記号処理，
GUI インタフェース作成等を取り上げ，従来のコンパイル型の言語を採用した場合と，スクリプト言語
/対話型言語を採用した場合の比較を行い，近い将来における初期プログラミング教育のあり方を考察
する．
現在，金沢工大で実施されているデータ構造・アルゴリズムおよびプログラミングに関する教程に関
して，著者が改善の余地があると考えるのは次の諸点である．(1) データ構造・アルゴリズムについて
の座学と，プログラミング実践が乖離し，実践的な技能の習得に結びついていない．(2) プログラミン
グ言語やツールが低レベル（ハードウェアに近接しているという意味)で，今日的で高レベルの題材を
扱おうとすると問題が多い．(3) 特に，１～2 年生でアルゴリズム学習に主に用いている C 言語におい
ては，リスト処理，辞書データや高階関数の扱いが可能ではあるが，扱い上問題が多く，このことが学
習の妨げとなっている．
上記問題点(1)については，アクティブ・ラーニングにより学習を促進するという潮流からも検討す
べき点が多く，世界的にも問題となっているようである．文献 9)では言語学習とアルゴリズム学習を組
み合わせ，これら両者の学習を促進するという MIT の取り組みが紹介されている．自然かつ妥当な方向
ではないだろうか．
本稿で報告する内容は，平成 27 年度 JICA 研修生のためのプログラミングをテーマとした共通研修の
活動に負う部分が多い．この研修では８名の研修生に対して週一回のミーティングを行い，幾つかのプ
ログラミング言語を比較しながらプログラミング言語の学習/研修を進めている．ここで主に扱った言
語は，Python, Java, C 言語，及び Common Lisp である．また金沢工大の学生を対象として同様の目的
をもった学習会（プログラミング言語比較学習会）を開催しており，その活動に負う部分もある．また
第 3 章で扱う問題の１つは，平成 27 年度に情報工学科 2 年生を対象に開講された情報工学実験 I にお
124
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
いて履修生から提案されたものである．
２．使用言語の選択
約 30 年前に当時使われていた代表的なプログラミングを比較紹介した文献 3)と，現在使われている言
語を扱った文献 2) を読み比べてみると， ここ 30 年の間に起こった変化が読み取れる．主な変化とし
て，オブジェクト指向言語の定着，スクリプト言語の普及，Web プログラミング用言語の出現・普及が
挙げられる．
本稿で扱う言語は，Common Lisp, Python, Ruby, Perl, JavaScript, OCaml, MATLAB スクリプト言
語, Java, 及び C である．(これら言語の分類と特徴については文献 29) の表 1 にまとめられている．)
本稿では，汎用プログラミングのための言語を扱い，用途が限定された言語，例えば Web プログラミン
グ専用の言語は扱わない．
これらの言語のうち Common Lisp, OCaml, Java, C がコンパイル型であり，その他がスクリプト言
語である．
コンパイル型とは，ソース・プログラムを翻訳処理して機械語あるいは中間言語のオブジェクト・フ
ァイルあるいは実行ファイルを生成する機能を提供することを表す．スクリプト言語とは，ソース・プ
ログラムを直接実行する方式で実行可能であり，ソース・プログラムをスクリプトとして使用できるこ
とを示す．実際は「コンパイル型」と一応分類した Common Lisp もスクリプト言語として使用する場合
があり（http://www.clisp.org/を参照）
，一方「スクリプト言語」と一応分類した Python も，実行時
に中間コード(拡張子 .pyc)のファイルを生成しそれを実行することも可能である．こういう事情によ
り，この分類は明確なものではない．ここでは各言語の標準的な実行形態により「コンパイル型」か「ス
クリプト言語」に分類している．
また「対話型」言語とは，対話型の利用形式，所謂 REPL (Read-Eval-Print Loop) を装備しているこ
とを表す．REPL とは，インタラクティブに式を読み込み，その実行/評価結果をその都度表示する機能
である．初期の BASIC のコンソールや MATLAB のコマンドウィンドウが実現している．対話型言語の多
くはスクリプト言語であるが，
「コンパイル型」でかつ「対話型」であることも可能である(Common Lisp
や OCaml が該当)．なお本稿の焦点は，
「スクリプト言語」/「対話型言語」にあるが，比較のため「スク
リプト言語」/「対話型言語」ではない Java や C 言語も扱う．
これら言語のうち OCaml は，データ型の扱いについて他の言語と異質である．ここで焦点をあてる「ス
クリプト言語」や「対話型言語」は，OCaml 以外，全て「動的型付け」に分類されるものである．この種
類の言語は，記述の自由度が大きくラピッド・プロトタイピングや種々の実験には適している．しかし，
プログラミング言語の長年の研究により，
「静的型付け」が信頼度が高くかつ高効率のプログラムを構築
する上で有用であることは広く認められている.26) OCaml が提供する「型推論による静的型付け」は，
動的型付けによる記述の自由度と静的型付けによる信頼性の確保を両立させるための試みとみることが
でき，重要なアプローチである．詳しく扱うことはできなかったが，比較のため含めている．
３．あつかう問題
第 3.1 節では，言語の特性や性能を試すため実質的な問題を扱うための候補となる幾つかの言語につ
いて，関数呼出しの性能を評価するベンチマーク・プログラムを試験実行した．第 3.2 節から 3.4 節に
おいては，アルゴリズムの学習に有用と考えられる幾つかの問題の解を，その問題に適すると判断した
言語により実装し，記述性や性能について評価を行った．このうち第 3.2 節, 第 3.3 節 で扱う問題は
アルゴリズムの学習における標準的な問題である．第 3.4 節では，平成 27 年度の「情報工学実験 I」の
グループ学習において学生が取り組みを希望した問題
「ルービック・キューブのプログラムによる解法」
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
125
を扱う．
３．１ 基本性能の比較---竹内の Tak ベンチマーク関数によるテスト
最初に，
言語の特性や性能を試すため，
実質的な問題を扱うための候補となる幾つかの言語について，
ベンチマーク・プログラムを作成し実行した．このプログラムは，関数呼出しの性能評価のため竹内郁
夫が提案し竹内の Tak 関数と呼ばれる手順を用いている(文献 7) p.464)． Tak 関数は，C 言語では次の
関数 f として記述されるものである．
int f(int x, int y, int z){ if(x <= y){ return y; }else{ return f(f(x – 1, y, z), f(y –
1, z, x), f(z – 1, x, y)); } }
Tak(2・n, n, 0) を実行すると，再帰呼出しの回数は概略 nn のオーダとなる．以下に小さな n に対す
る再帰呼出しの回数を挙げる．Tak(10, 5, 0)に対し 343,073 回, Tak(12, 6, 0) に対し 12,604,861
回，Tak(14, 7, 0)に対し 588,802,013 回，Tak(16, 8, 0)に対し 33,635,863,081 回．Tak(18,9,0)に対
し 2,288,612,472,229 回．このように，小さな引数に対して多数の再帰呼出しを行うが，Tak により計
算される数学関数は次のように記述される関数 g が定義するものと同じであることが知られている．
int g(int x, int y, int z){ if(x <= y){ return y; }else if(y <= z){ return z; }else{ return
x; } }
Tak を実装するために必要なデータ型は小さな整数の型(例えば C 言語の int 型)のみであり，再帰呼出
しの回数は多いが，再帰のネストはそれほど深くなることはない．従って，ほぼ全ての言語で実装可能
でメモリーもそれほど必要とせず，実行速度評価のための便利なベンチマーク手段を提供している．
表 1 に 9 個の言語処理系で，Tak(14, 7, 0) を実行した際の処理時間を示す．(使用 OS は，Windoss8.1
64-bit, マシンは Intel®Core™i7-4500U [email protected], 16GB メモリ付である．) このベンチマークおい
ては，Java 言語が一番高速であり，MATLAB スクリプト言語と Perl が目立って低速であった．スクリ
プト言語の代表としてよく比較される Python, Ruby, Perl の中では Ruby が最も高速で，一方，Perl
が著しく低速でメモリ消費も大きいことが観察された．Common Lisp や OCaml については，コンパイル
済コードを実行しており，スクリプト言語より高速である． 最速の Java は，最も遅い MATLAB スクリプ
ト言語より約 3000 倍速いという結果である．これから，これら 2 つの処理系は異なる用途を想定した
別種のツールであることをが推測される．なお仮想マシンで動作する Java プログラムが機械語プログ
ラムに翻訳される C 言語プログラムより高速なのは，Java 処理系の JIT(Just In Time Compilation)機
能が有効に働いているものと推測される．数値計算プログラムにおいても同様の傾向が観察された．22)
表 1．竹内の Tak ベンチマーク関数の実行速度
言語
Common Lisp
Python
1.792
備考 (処理系のバージョン等)
Allegro Common Lisp 9.0 (64-bit)
91.018
Python 3.4.3 (64-bit)
Java
0.826
Java 1.8.0_60 (64-bit)
C
1.380
Visual Studio 2013 Professional
MATLAB スクリプト言語
2772.700
R2014b (Win64)
JavaScript (jjs コマンド)
13.213
nashorn 1.8.0_60 (Java 1.8.0_60 (64-bit) 付属)．文献 15)参照．
Ruby
27.205
ruby 2.2.3p173，x64-mingw32
Perl
1107.015
OCaml
126
実行時間 (秒)
21.635
v5.22.0 (Cygwin version)
The OCaml toplevel, version 4.01.0 (Cygwin version)
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
以上の結果は，Tak 関数という特定のベンチマーク関数による比較であり，言語処理系の一般的性能
を比較したものではない．しかし，第 3.2 節以降で実質的問題を扱う上では，関数呼出しを多用する必
要があるめ，このベンチマークで著しく遅い処理系は採用しないこととした．その結果，第 3.2 節以降
では，スクリプト言語/対話型言語として，Common Lisp, Python, JavaScript を採用し，それと比較す
るためのコンパイル型言語としては，Java と C 言語を採用することとした．ベンチマークの結果からは
Python よりも Ruby の方が有利と思われるが，第 1 章で述べたミーティングにおいて，スクリプト言
語として主に Python を扱っているので，ここでは Python を用いることとした．文献 24)等では，実働
ソフトウェアの実装に Python を適用する例が紹介されている．このような用途において，その性能がコ
ンパイル型の言語と比較してどの程度か観察する目的もある．
３．２ 標準的なアルゴリズム，その 1---行列計算と行列電卓
スクリプト言語 Python で扱う最初の実質的問題として，Gauss-Jordan の消去法や LU 分解を用いて，
連立一次方程式の解法や逆行列の計算法をプログラム化する問題を選び， JICA の学習会で扱った．さ
らに，そのプログラムに GUI インタフェースを装備し，行列電卓を構成することを試みた．GUI インタ
フェース作成のためには，Tkinter と呼ばれるライブラリを適用した．機能的には，3×3 の行列を扱う
行列電卓とし，ランダムに行列を生成し，その逆行列を計算して，もとの行列と掛け合わせ，単位行列
になることを確認できるものとした．Gauss-Jordan の消去法や LU 分解は標準的なアルゴリズムである
が，文献 23) に掲載されている C 言語によるプログラムを参考にした．その結果，行列計算は Python で
問題なく実行でき，配列サイズをコンパイル時に決定しなければならない C89 によるプログラムより，
一般的なプログラムが容易に作成できることが確認できた．但し文献 22)におけるような，速度的な評価
は行っていない．
実際上の問題で，高速な行列計算を目的とするのであれば高度に最適化された組み込み関数をふくむ
ライブラリ(numpy 等)が提供されているので，それらを用いるのが普通である．これらは，Python 処理
系の実装言語である C 言語等により高度に最適化して実装されている(https://www.python.org/ 等を
参照）
．
３．３ 標準的なアルゴリズム，その 2---動的計画法によるナップサック問題の解法
アルゴリズム設計の分野において動的計画法(dynamic programming)とは次のような手法を指す．即
ち，与えられた問題を解くに際して，重複した計算を避けるため，部分問題の解を求めて表に記憶して
いき，元の問題を解くに際してその表を参照してボトム・アップに解を構成していく手法である(文献 7)
p.562)．知識処理の分野ではこの手法は常套手段であり「動的計画法による」と修飾することなく採用
している場合も多い．19) 例えば，一般的なアルゴリズム設計で有効グラフの探索アルゴリズムという場
合，一度チェックしたノードの記憶を含まない場合が多いが（例えば文献 4)第 7 章)，知識処理の分野で
はこの記憶も含めて探索アルゴリズムと称するのが一般的である（文献 19)第 2.3 節)．第 3.4 節では後
者の方式の探索アルゴリズムを用いる必要がある．
なお，OR の分野では「動的計画法」という用語を，より限定された意味で使うようである(文献 7) p.563)．
動的計画法は重要な手法であり，文献 6)においても計算機分野の学部のカリキュラムに含めるべき項
目とされており，米国で出版されたアルゴリズムの教科書とその翻訳（文献 8), 9), 10)等)では詳しく解説
されている．一方，日本でよく使われているアルゴリズムの教科書では，項目名を挙げる程度か，ある
いは全くこの項目に触れていないものが多い（例えば文献 4), 5)）
．これは片手落ちと言えるだろうが，こ
うなった理由は何であろうか．重要度が見落とされている訳ではないだろうし，概念的に難しい訳でも
ないだろう．考えられる理由の１つは，文献 4), 5) 等でアルゴリズムを実装するための言語として想定し
ている C 言語においては，表（具体的にはハッシュ表)の扱いに難点があり実装例を提示する上で問題が
あることである．第 1 章で述べたように，プログラミング言語の最重要な目的の１つである「アイディ
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
127
アをエレガントに表現することを可能にする」という機能を，この項目について C 言語は果たしていな
い．
C 言語においてハッシュ表は基本データ型ではないので，使用する場合は新たに実装するかその機能
を提供するライブラリを利用する必要がある．ハッシュ表を構成するには，キーのデータ型と値のデー
タ型を定める必要があるが，個別のデータ型毎にハッシュ表を実装していたのでは手間がかかりすぎる
ので，一般的なキーと値のデータ型に対応する汎用のハッシュ表を構成することが望ましい．C 言語で
これを実現するには汎用ポインタ(void へのポインタ）を使いこなす必要があり平均的な学部１，2 年生
の技能では困難を伴う可能性がある．
一方，第 2 章で取り上げた幾つかの言語のうち，C 言語以外は，全てハッシュ表を基本データ型また
は標準ライブラリとしてサポートとしている．文献 9) では Python をアルゴリズム記述と実装のための
言語として用いて動的計画法による 0/1 ナップサック問題を平易に解説している．
0/1 ナップサック問題とは，ID，value, および cost からなる 3 つ組 (ID, value, cost) の有限系列
と，space (容量)と呼ばれる正整数が与えられたときに，その有限系列から部分系列を選択し，選択さ
れた部分系列の cost の総計が space 以下であるという制約の下で，部分系列の value の総計を最大
化する問題である．ここで，value と cost は正整数として与えられるものとする．
表 2. ナップサック問題解法の効率比較
実装
扱った問題
再帰呼出し
ハッシュ表
選択された
value
実行時間
言語
（ナップサック問題のパラメータ）
の回数
に登録され
項目の数
の
(秒)
n
Java
valBnd
costBnd
た項目の数
space
合計
100
10
128
3,200
449,076
229,172
70
481
2.058
200
10
128
6,400
1,927,889
974,013
114
815
5.016
400
10
128
12,800
7,478,399
3,758,893
255
1,720
40.950
800
10
128
25,600
31,127,919
15,603,052
503
3,361
299.627
Common
100
10
128
3,200
475,682
242,709
63
454
0.493
Lisp
200
10
128
6,400
1,886,897
952,850
130
886
4.635
400
10
128
12,800
7,502,161
3,770,261
257
1,746
20.488
800
10
128
25,600
31,313,825
15,696,311
497
3,523
171.064
100
10
128
3,200
475,328
242,793
55
393
24.870
200
10
128
6,400
1,857,654
938,192
129
917
182.674
400
10
128
12,800
7,567,492
3,802,627
261
1,672
1,536.856
800
10
128
25,600
30,819,581
15,448,077
512
3,470
12,923.422
100
10
128
3,200
478,782
244,297
64
459
317.232
200
10
128
6,400
1,872,340
945,393
136
946
4,571.498
100
10
128
3,200
462,022
235,586
63
442
5,089.238
Python
JavaScript
C 言語
本稿では，この問題を Python, Common Lisp, JavaScript, Java, 及び C 言語で扱い，記述上の利害
得失を分析し，実行効率を見てみる．
Python においては文献 9)にあるプログラム(図 18.8)を小さな修正を除いてそのまま用いた．修正点
は，系列の扱いにリンクト・リストを採用し効率化を図ったたことである．他の言語においても，アル
ゴリズムは同じである．
128
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
表 2 に幾つかの言語処理系で，ナップサック問題を解いた際の実行時間等のデータを示す．表 2 の「扱
った問題(ナップサック問題のパラメータ）
」の欄に，n, valBnd, costBnd, space という 4 つのパラメ
ータが並べられている．n は項目数を，valBnd は value を正整数としてランダムに選択する際の上限
を，costBnd は同様に cost をランダムに選択する際の上限を，space は上記で述べたナップサック問
題の space (容量)を表す．ここでは，costBnd を固定し，space = (costBnd/2)・(n/2) として，幾つ
かの n について問題を解いている．この形で，costBnd を固定すれば，かなりの範囲の n について実際
的に解を求めることができる．文献 9)に述べられているように，このアルゴリズムは疑似多項式(pseudo
polynomial)と呼ばれるクラスに属し，
（再帰呼び出しにおいて）パラメータ space のとり得る値を表現
するのに必要なビット数の指数オーダーの実行時間を必要とする手法である．
表 2 の最後にあるように，
C 言語によるプログラムが最も遅い．これは，リスト処理のために，オーバヘッドの大きい malloc を
多用したことが一番の原因と推測する．この問題については，第４章で考察する．
３．４ 学生提案の問題---ルービック・キューブのプログラムによる解法
四色問題を嚆矢として，離散数学にはプログラミングと数学の両者にまたがる著名な問題がある．こ
こで扱う問題もその一つである(ルービック・キューブのアルゴリズム的な扱いの基本については文献 7)
p.853 を参照)．
ここで扱うルービック・キューブは，サイズが 2×2×2 の最少構成のものであり，文献 21)で扱われて
いるものと同じである．図 1 にこのタイプのルービック・キューブの初期状態をしめす．図 1 の左半分
はキューブを正面上方から俯瞰したものであり，右半分は背面下方から見上げたものである（この状態
表示の仕方は文献 20)に倣った）
．図 1 で，w, r, b, y, o, g は色を示す．ルービック・キューブはパズ
ルとして考案されたものであるが，その理論的解析は，(離散)数学と計算機科学にまたがる問題として
種々の取り組みがなされている 20), 21), 28)．ルービック・キューブにも幾つかのサイズがあるが，2×2×
2 ルービック・キューブについては現在の計算機で，種々の解法のシミュレーションによる評価やさら
に解の網羅的探索が可能である（文献 7) p.853)．解の網羅的探索は，キューブの変換規則に即して，動
的計画法を適用した系統的探索を行えばよく比較的単純な手順であり，情報工学科の 1～2 年次で学習
するデータ構造とアルゴリズムの知識で対応できるはずの問題である．ただし，第 3.3 節で述べたよう
に C 言語で動的計画法を実装するには手間がかかるので，この種類の問題を学生課題として実施するに
は Java やあるいは適当なスクリプト言語を用いるのが適切であろう．系統的探索には深さ優先探索と
幅優先探索があるが，この問題に対しては最短解手順を求めることが望ましいため幅優先探索を用いる
のが適当である．幅優先探索を実装するに際しては，動的計画法を適用して同じノードを重複して検査
しないようにする必要がある．
2×2×2 ルービック・キューブの配置の数は，8!・37 = 88,179,840 である．これは 1/2 サイズの小さ
なキューブ（サブキューブという）が 8 個あり，これらサブキューブの空間配置の仕方が 8!通りであり，
１つの空間配置について，7 個のサブキューブについては向きづけが 3 通り可能であり，残り 1 個の向
付けは，他の 7 個の向付けにより決定されるからである（文献 21)定理 1 参照）
．
通常の PC で，
88,179,840 個の要素からなる探索空間を扱うのはメモリの容量の制限から困難を伴う．
そこで，キューブの 2 つの配置 A と B について，A を回転して B と重ねることができれば同一視するこ
とにする．この方式で同一視できる配置の数は 6・4 = 24 通りある（垂直方向上向きの面の選択法が 6
通りで，水平方向の回転が 4 通り)．この同一視を適用して抽象化した配置の数は 88,179,840 /24 =
3,674,160 通りであり，通常の 64bit PC で問題なく扱える空間サイズとなる．表 3 に，
（動的計画法を
適用した）幅優先探索を用いて，3,674,160 個の配置を，初期状態へ至る最短手順の数により分類した
結果を示す．表 3 に表れる「配置の配列表現」とは，キューブ表面の 6・4 = 24 個の小正方形に番号を
つけ，それらに対する色付けを配列で表現したものである．配列要素は w, r, b, y, o, g からなる列
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
129
挙型である．ここで w, r, b, y, o, g は各々 white, red, blue, yellow, orange, green に対応す
る．
「配置の整数表現」は，6 通りの各色付けを 3bit で表現し，24 個の色付けを並べて，72bit のビッ
ト・パターンを構成し，これを正整数に読み替えたものである．プログラムの中では，配置は整数表現
で扱われており，向き付けを無視して 24 個の配置を同一視する際にはこの整数表現で最少となるもの
により代表させる．
この問題に対しては，Common Lisp, Java, Python により，与えられた配置に対して初期配置に至る
最短経路を計算するプログラムを作成した（最短手順数 9 の配置に対して：Common Lisp 版で 2 時間 23
分，Java 版で 42 分で実行．Python 版では 25 時間 40 分で実行）
．また，このプログラムを少し拡張
し，全ての配置を，初期配置に至る最短経路の長さにより分類するプログラムを Common Lisp で作成
した（実行時間 3 時間 19 分）
．表 3 に示す結果は，このプログラムによる分類である．プログラミング
においては，図 1 における Z 軸を中心として，上部の半分を Z 軸正の方を向いて 90 度回転する変換を
１つの関数/メソッドとして実装する．同様の変換を合計 6 通り用意し，それらを組み合わせることによ
りルービック・キューブの１ステップで許される 18 通りの変換を構成し，これらの変換を用いて系統的
探索（ここでは幅優先探索）を行えばよい．
探索においてはノードの型を型パラメータとして指定できるように汎用の探索プログラムを準備する
ことが望ましい．Java 言語においてはノードの型を型パラメータとする総称型クラスとして実装した．
本節で扱う Rubic Cube 問題においては，ノードの型は 72 bit の整数を表現できる BigInteger クラス
となる．
４．考察
第 3 章の例題を実行することを通して，文献 9)で紹介されているような，アルゴリズム・データ構造
の学習とプログラミング学習を融合したアクティブ・ラーニング的なアプローチの有効性を再認識した．
第 3.3 節で述べたように，一般的な入力に対しては計算困難（技術的には NP 困難とよばれるクラス）に
分類されるナップサック問題が，実用上扱う可能性が高いパラメータに対しては十分に計算可能である
ことを認識するには，座学のみでは非常に困難であろう．文献 25)第 1 章で指摘されているように，アル
ゴリズムの扱いについては理論と現場の間にギャップがあり，これを埋める方策が必要である．
また，大学初年級でよく使われる C 言語の問題点も顕著に現れた．最重要のデータ型である辞書ある
いはハッシュ表が組込み型ではなく，その一般的な実装も（可能であるが）それほど容易でないことか
ら，結果としてアルゴリズム学習でカバーする範囲が限定されていることが推測される．
具体的にはどういう方策が考えられるであろうか．以下に選択肢を挙げてみる．
(1) 言語として C 言語を用いるが，汎用のハッシュ表ライブラリ等を含む充実したライブラリを共に提
供し，当初は（その実装法よりも）その仕様と使い方に重点を置く．
(2) 言語として，Java 等のデータ構造の充実したオブジェクト指向言語を用いる．
(3) Python, Ruby, Common Lisp, または JavaScript のようなスクリプト言語を中心とした対話型言語
を用いる．
方策(1), (2) を用いる場合でも，補助として，Python, Ruby, Common Lisp または JavaScript のよ
う対話型機能をサポートした言語を用いることが望ましい．対話型言語，特に動的型付けの言語でプロ
グラムすることは，フリー・ハンドで図を描くことに似ている．必要に応じて製図用具や CAD ツールを
使って精確な図を作成することは重要であるが，フリー・ハンド・ドローイングも一方では必要であろ
う．対話型言語として OCaml のような型推論機能を装備する言語を用いることも考えられるが，大学 1
～2 年次には敷居が高いという印象である．方策(3)を用いる場合は，補助として Java や C 言語のよう
なコンパイル型の言語について補足することも重要であろう．
130
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
C 言語については，ハッシュ表の扱い以外にも，幾つかの技術的な問題が浮上した．C 言語でリンク
ト・リストを操作する際には，標準ライブラリ関数 malloc 等で必要なメモリを確保してリストを構成
する方式を採用している文献が多く（例えば文献 4), 5))本稿でもその方式を採用した．しかし malloc の
処理は内部でシステム・コール（sbrc 等)を伴いオーバヘッドが大きいという問題がある．システム・
コールを伴わずにリンクト・リストを扱うため，配列を用いた実装方式が従来から知られている．8), 27)
この 2 つの方式の利害得失を論じることはアルゴリズムやプログラミングの教程では重要であろう．
また，C99 による改訂（文献 12), 13))により配列サイズの動的決定が可能になったのにもかかわらず，
オーバヘッドが大きくメモリ断片化や(不注意による）メモリ・リークを伴いがちな malloc による処理
を，利害得失を論じることなく採用している場合が多く，これも問題である．
なお本稿では C 言語の難点を種々述べてきたが，ハードウェアに近接したこの種類の言語の重要性に
ついては疑いがない．例えばスクリプト言語の代表として本稿で扱った Python の代表的な処理系は C
言語で記述されている．プログラミングのための言語は用途/目的に応じて種々あるので使い分けが重
要であろう．
本稿では，幾つかの問題について実行時間やメモリ消費量を計測し比較した．実行時間については，
短時間，例えば 1 秒で終了するプログラムが 1000 倍遅くなっても実際上の問題はそれほどないだろう．
しかし 1 時間で終了するプログラムが 1000 倍遅くなるとその影響は大きい．実行速度の比較が重要と
考える理由である．
５. おわりに---今日要求されるプログラミング能力とその実現のための方策
文献 18)で指摘されているように現在の IT 技術者に要求される能力は広くかつ深く，また変化しない
部分と急速に変化する部分を含んでいる．比較的変化しない部分としては，実践的なアルゴリズムに関
する知識とその実装能力が挙げられる．変化する部分としては，広い意味でのプログラミング言語が挙
げられる．言語の変化には，名前が同じで内容が変化することによるもの(例えば C89 と C99 の違いは
大きい）
，および新しい言語の出現によるものがある．IT 技術者の技能としては，標準的な言語に習熟
していることと共に，新たな言語を迅速・確実に習得する能力も重要であろう．そのためににも，系統
の異なる言語を，学生時代に使いことなす経験は重要であろう．なお本稿の作成の過程で著者が作成し
たプログラムは以下の URL（Comparative Study of Programming Languages のホームページ)で公開さ
れている．http://www.ws.kanazawa-it.ac.jp/~horita/prog_lang_meeting/index.html
本稿で扱ったプログラムの抜粋と説明は文献 29) に含まれる．以下の文献リストでは外国語原著に対す
る日本語訳がある場合には後者のみを挙げた．原著を含む文献リストについては文献 29)を参照されたい．
3:b
1:b
2:b
1:w
0:b
3:y
2:y
1:y
0:y
Y
3:o
Z 1:o
0:o
0:w
2:o
X
3:w
3:r
2:w
1:r
2:r
0:r
3:g
1:g
2:g
0:g
図 1．2×2×2 ルービック・キューブの初期配置
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
131
表 3．最短手順数による配置の分類
初期配置への
配置数
配置例
最短手順数
配置の整数表現
配置の配列表現
0
1
164743292617116525
#(w w w w r r r r b b b b y y y y o o o o g g g g)
1
9
31293637314028391250
#(w w y y r r r r b g b g y w y w o o o o g g b b)
2
54
31348618713671701677
#(w w y y r o r o g b g b w y w y o o r r b b g g)
3
321
106670208126905355090
#(w r y o o r y w g g b b w y o r r y o w g g b b)
4
1847
98152484990794730332
#(w r b g r w o y g y b r w b o b r y o w g g y o)
5
9992
101818143192060568221
#(w r y w b o w b g g y o y o r o g w r b r b y g)
6
50136
101680594269576143021
#(w r y w r o y b w b y o r y o o g g r b w b g g)
7
227536
114490815194275815586
#(w r o y b y o r w g y g r w o y g g r b w b o b)
8
870072
87866181835139921168
#(w r r o r g o y y w g g o w b g y r b y b o b w)
9
1887748
87863903657501471000
#(w r r o r g y y b b g g g b w o o r b y w o y w)
10
623800
11160928275135350093
#(w w r r g y o y o g b b r w b y w y o o b g r g)
11
2644
250833968327821694253
#(w y y r o o w g b r b y o w w g y r b r b o g g)
謝辞: ITEC 顧問 日下迢先生には，スクリプト言語の重要性について助言をいただいた．ITEC 宮田孝富
先生には，JICA 研修生に対するプログラミング言語の研修を共同で主催し有用な議論をしていただいた．
H27 年度 JICA 研修生の諸氏との議論は有用で，特に Hayde Martinez Landa 氏には Python 言語につい
て有用な情報をいただいた．住谷遥平氏には，プログラミング言語比較学習会で有用な議論をしていた
だいた．平成 27 年度情報工学実験 I の履修生諸氏，特に望月歩氏の提案により，ルービック・キューブ
をプログラムで扱うという興味深い問題に注意を向けることになった．以上の諸氏に感謝する．
参考文献
1） C.A.R. Hoare, 「The Emperor's Old Clothes」, Communications of the ACM, Vol. 24, No. 3,
pp.75—83, 1981.
2) 小林健一郎, プログラミング 20 言語習得法 初心者のための実践独習ガイド, 講談社，2014．
3) 有沢誠，プログラム言語への招待，岩波書店，1984．
4) 渡邊敏正，データ構造と基本アルゴリズム，2000．
5) 津田和彦他，コンピュータアルゴリズム，共立出版，2006．
6) The Joint Task Force on Computing Curricula ACM and IEEE Computer Society, Computer
Science Curricula 2013: Curriculum Guidelines for Undergraduate Degree Programs in
Computer Science, ACM and IEEE Computer Society, 2013.
7) 島内剛一 他（編)，アルゴリズム辞典，共立出版，1994．
8) Thomas H. Cormen, et al., 世界標準 MIT 教科書: アルゴリズムイントロダクション第 3 版 総合
版，近代科学社，2013．
9) J. V. Guttag，久保幹雄(監訳)，世界標準 MIT 教科書 Python 言語によるプログラミングイントロ
ダクション，近代科学社，2014．
10) Sara Baase，岩野和生他(訳)，アルゴリズム入門[新装版]---設計と解析---，ピアソン・エデュケ
ーションズ，2002．
11）Brian W. Kernighan, Dennis M. Ritchie，石田晴久(訳)，プログラミング言語 C 第 2 版，共立出
132
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
版，1989．
12）日本規格協会，JIS X 3010 (ISO/IEC 9899) プログラム言語 C，日本規格協会，2003．
13) 戸川隼人，ザ・理工系のための C---C99 準拠---， サイエンス社，2009．
14） Ken Arnold et al., 柴田芳樹(訳), プログラミング言語 Java 第 4 版，ピアソン・エヂュケーシ
ョンズ，2007．
15) Cay S. Horstmann, 柴田芳樹(訳)，Java プログラマーなら習得しておきたい Java SE 8 実践プロ
グラミング，インプレス，2014．
16) Guy L. Steele Jr., 井田昌之(訳)，Common Lisp 第 2 版，共立出版，1991．
17) 五十嵐淳，プログラミング in OCaml，技術評論社，2007．
18) 平山亮, 「高度 IT 人材育成に向けた IT 基礎教育カリキュラム」
，KIT Progress，No.17, pp.201—
216，金沢工業大学，2010．
19) 菅原研次，人口知能[第 2 版]，森北出版 ，2003.
20) 島内剛一，ルービックキューブと数学パズル，日本評論社，2008．
21) 島袋修 他，平成 20 年度 福島公専公開講座: 2×2×2 ルービックキューブ de 遊ぼう，福島工業専
門学校，2008．
22) 堀田英一，宮田孝富, 「工学系大学における数値計算教育のための言語/ツールの検討」，KIT
Progress, No.21，pp.191--203，金沢工業大学，2014．
23) William H. Press et al., 丹慶勝市他(訳)，Numerical Recipes in C [日本語版]，技術評論社，
1993．
24) Wesley J. Chun, Core Python Applications Programming Third Edition, Prentice Hall, 2012．
25) 杉原厚吉他(編)，アルゴリズム工学---計算困難問題への挑戦，共立出版，2001．
26) David A. Schmidt, The Structure of Typed Programming Languages, The MIT Press, 1994.
27) 浅野孝夫，情報の構造 (上/下) データ構造とグラフアルゴリズム/ネットワークアルゴリズムとデ
ータ構造，日本評論社，1994.
28) 和田英一，「Haskellプログラミング Rubicキューブと置換の乗算」，情報処理, Vol. 46, No. 7,
pp.829—835, 2005．
29) 堀田英一，「初期プログラミング教育のためのスクリプト言語/対話型言語の検討とサンプル・プロ
グラム」，ITEC Technical Report， No.1, 金沢工業大学情報基礎教育研究センタ，2015.
[受理 平成27年9月10日]
写真
堀田英一
教授 Ph.D. (計算機科学)
基礎教育部基礎実技教育課程
情報基礎教育研究センター
初期プログラミング教育のためのスクリプト言語 / 対話型言語の検討
133