ソフトウェアにおけるものつくりの変革 －HaskellとFPGAから見えてくる組込み系のものつくりの革新－（PDF）

ソフトウェアにおけるものつくりの変革

−Haskell と FPGA から見えてくる組込み系のものつくりの革新− Innovation for Software Design and Imprementation by Haskell and FPGA

福良 博史 FUKURA Hirofumi １．はじめに 高信頼ソフトウェアによるものつくりにつ いて根本的に何が問題となっているかを検討 し、そのあるべき方向性を見極めていきたい。 はじめに、ソフトウェアによるものつくり の大前提は何かと考えるとそれは現在のコン ピュータが挙げられる。このコンピュータを 動かすためにはそれなりの「言語」が必須で あり、その言語をどのようなものにしたら良 いかという努力がこの半世紀あまり続いてき ている。このなかで大きな流れとして、手続 き型の言語（imperative language）と関数型 言語（functional language）の二種類に焦点 を当てて双方の特徴を概観し、関数型言語の 今後の有効性を述べる。 ハードウェアの世界では、メモリーが安価か つ大容量となり、速度も高速化し、色々なノイ マン型コンピュータ用 CPU のチップが続々と でてきている。そして FPGA のように自分で CPU のプロトタイプを製作できる環境も安価 に調達できる素地が整ってきている。 本論は、今後の高信頼性システムを製作して いくための一方法として関数型コンピュータを 検討していくために、調査・分析を行っている 内容の途中経過を紹介する。 ２．半世紀におよぶ言語の変遷 ソフトウェアによるものつくりについて従来 行われている方法論を整理するための一つの観 点として、プログラミング言語に焦点を当てて 考えてみる。 コンピュータが世に現れて半世紀以上が経過 した。コンピュータは、それまでの機械と異な り、人間から色々な指示を受けて仕事をしてく れる。この指示の集まりをソフトウェアと呼ぶ。 ソフトウェアは、コンピュータというハードウ ェアに強く依存し、ハードウェアが無ければた だの紙くず同然となってしまう。パソコン、マ イコンも含め、現在使われている通常のコンピ ュータは、一般にはノイマン型といわれている 部類に属する。 このノイマン型コンピュータは、どのように して動いているかを考えてみる。このコンピュ ータへの指示は、コンピュータのメモリー上に 人間が指示すべき命令をその実行してほしいと 考えた手順通りに記録しておき、コンピュータ がその命令をひとつずつ取り出して実行するよ うになっている。そしてその結果として人間が 指示した通りの仕事をこなしてくれる。 ２．１ アセンブラの出現 コンピュータのメモリー上に配置するための 一番基本になる言葉を機械語と呼ぶ。人間はは じめ機械語を二進数の値そのままをを用いてメ モリー上に配置していた。これでは人間の労力 が大変だと考え、アセンブラが出現してきた。 アセンブラを使うことにより機械語と一対一対 応の人間が理解しやすい記号（これをニーモニ ック mnemonic コードと呼ぶ）を用いて指 示を書き、それを機械が理解できる機械語に自 動的にコード化することが可能になった。 ２．２ 手続き型言語の変遷 このアセンブラでも記述が未だ機械の言葉 であり人間の表現する言葉からは、かけ離れ ており、記述が大変である。たとえばa+b を ｃに格納するような加算を行うのに、Load a、 Add b、Store c のような手順がアセンブラで

は必要になる。これが c=a+b のように表現で きれば、今まで以上に人間の思考に近づき便 利である。ということで高級言語と呼ばれる 各種言語が登場してくる。 ・1950 年代 最初にFORTRAN が出現する。これは 1954 年にIBM の John Backus により考案された 最初の高級言語といわれる部類の言語である。 1950 年代後半には ALGOL、COBOL が登場 する。 ・1960 年代 1965 年に IBM が PL/I を発表する。 ・1970 年代 1970 年にはスイスのチューリッヒ工科大の Niklaus Wirth が PASCAL を教育用に考案し た。1973 年にはベル研の Dennis Ritchie らに よるC 言語が登場してくる。 ・1980 年代 1983 年には信頼性を向上させる意味で抽象 データ型を考慮したオブジェクト指向言語の C++がベル研の Bjarne Stroustrup によって 考案された。 ・1990 年代 1990 年代に入り、サン･マイクロシステムズ 社のJames Gosling が、ポータブル性、ドキ ュメント性などを向上させたオブジェクト指 向の言語Java を考案した。 以上は手続き型の言語の発展である。 以上で概観した手続き型言語は、現在のビ ジネスアプリケーションおよび、組込み系ア プリケーションのソフトウェア開発の現場で 使われている。手続き型の言語以外はほとん ど使われていないといっても過言ではない。 ・手続き型言語の問題点 近年、社会問題となった金融関連のシステ ムトラブル、エレベータ制御のトラブルなど を引き起こしているものはこのような環境の もとでつくられたシステムである。 この手続き型言語の問題点が大きくクロー ズ ア ッ プ さ れ た の は 、1968 年 に Edsger Dijkstra が発表したレター(1)_{からである。この} 中で、goto 文が、プログラムの理解の妨げに なることを述べている。ここからgoto 文論争 が巻き起こり一時はgoto 文が魔女狩りにあっ ているような状況が出現した。この後から出 てきた言語は、例外処理または繰り返しのル ープからの脱出用の制御命令としてのexit 文 等は許しても、無条件にどこにでも移動可能 なgoto 文は使えないように制限するようにな ってきている。 この手続き型の言語の本質は、goto 文論争 において明らかになってきたように、人間が 機械への命令・指示の手順を計画し、機械は その手順通りに機械的に実行していくように できている。まさにこの手順をプログラムす ることの困難さから色々な問題が生じている。 買い物をしてくれる二足歩行のロボットが 居て、このロボットに頼んで、ジュースとり んごを買ってくるように依頼する場合を想定 してみる。このとき、機械的な手順とは、図 ２．１のようになると想定できる。これは、 いわゆる、How を表現するための言語となっ ている。この図の中の手順１と手順２でりん ごとジュースを買う順序は、必ずこの順序を いやでも守ることになる。先にジュースを手 にし、後からりんごを手にすることは決して 起こらない。もしそのようなことが起こった ならそれは何か「システム障害」が生じたこ とになる。 図２．１ 手続き型のHow イメージ 手順１．りんごがあれば、 りんごを買う 手順２．ジュースがあれば、 ジュースを買う

２．３ 関数型言語の変遷

関数型言語の歴史も古く、手続き型の高級言 語のFORTRAN が出てから数年後に登場する。 ・1950 年∼1960 年代

はじめに、関数型言語のLISP は、1958 年に MIT の John McCarthy 等によって考案され た。当初、紙の上でのラムダ算法の記法であ ったが、色々な経緯を経て1960 年代にはプロ グラミング言語となる。 ・1970 年代 1974 年にエジンバラ大から ML という言語 が出てきた。 関数型言語は、コンピュータのメモリやCPU の資源を多く必要とするため、実用的ではない という傾向になり、一時期低迷していた。 ・1980 年∼1990 年代 1987 年に米国オレゴン州ポートランドにて、 関 数 型 プ ロ グ ラ ミ ン グ 言 語 の 国 際 会 議 Functional Programming Language and Computer Architecture（FPCA’87）が開催さ れ、現実のアプリケーションを構築するための 共通の関数型言語を作ることが決定された。 この委員会の主要な目標は以下の５項目の制 約を満す言語を設計することにあった。(2) (3) 1. 教えること、研究すること、大規模な システムを構築することを含む 応用 に適するものであること。 2. 形式的な構文と意味論の公開をもって 完全に記述されたものであること。 3. 自由に利用できるものであり、なんび ともこれを実装することを許可され、 誰にでも配布することが許可されてい るものであること。 4. 広く認められたアイディアに基づいて いるものであること。 5. 関数型プログラミング言語における不 必要な多様性を 軽減するものである こと。 この決定に基づいてつくられた言語が純粋な 関数型言語と言われているHaskell 98 である。 このHaskell は、現在ネットワークを介在し たアプリケーションをはじめとしグラフィック を利用したゲーム等と多彩な応用例が出てきて いる。 関数型の言語のイメージを先ほどの買い物ロ ボットに当てはめると、図２．２のようになる。 図２．２ 関数型のWhat イメージ これは、一見したところ図２．１と同じでは ないかと思うかもしれない。しかし他への副 作用を持たずかつ、手順ｘを規定ｘとしたよ うに、順序を意識しない、というところが根 本的に手続き型言語と異なる。 ２．４ 副作用についての若干の考察 副作用（side effect）とは何か、そのイメー ジを把握しやすいように図２．３を用いて考 えてみる。 この図では仮想的な手続き言語を用いる。 関数は、Main プログラムから呼び出された時 に動くものとする。この図の中の外部変数の 値に注目する。 この図において外部変数は、関数を呼出す 前に初期化されており、関数ｆ（ｘ）の中で この外部変数の値を変更している。これを副 作用という。 この副作用と呼ぶ意味は、以下のようなプ ログラムの動作から理解できる。 規定１ りんごがあれば、 りんごを買う 規定２ ジュースがあれば、 ジュースを買う

このMain プログラムを実行すると、２行目 と３行目のPrint で何が表示されるか？ どちらも Print ｆ（３）となっているが、 結果は異なる。 ２行目の結果表示されるものは、 ６ （←３×２×１） となる。このとき、関数ｆ（３）の実行中に図 ２．３のｂの行で、ｙの値が’1’から’―1’に変化 する。そのため次の３行目の結果は、 ―６ （←３×２×（―1）） となる。この二回目の関数の呼び出しによって、 再度ｂの行が実行されｙの値が’―1’から’1’に戻 る。外見上同じ関数の実行をしたにもかかわら ず、同じ関数から返却される値が異なる。これ は、手順（実行順序）と副作用の相互作用によ って必然的に生じる。 図２．３ 副作用のイメージ オブジェクト指向の基本的概念としてデー タのカプセル化または抽象データ型という考 え方がある。この考え方は、副作用を無くす ことが前提となっていると考えられる。しか し現実の手続き型言語は一般に自分の外部を 見ることが可能な仕様となっている。この副 作用があるのは一見ソフトウェアを組む現場 では便利である反面、多用すると信頼性・保 守性などをあやうくしかねない。 なお、純粋な関数型言語は、手続き型のよ うに値をセットするものではない。定義をし ているのであるから、値は最初から最後まで 不変である。このように両者の考え方が根本 的に異なる。このため、関数型言語において は、副作用という状況がそもそも発生しない ことになる。 ３．具体的な言語の例 アセンブラ、手続き型言語、関数型言語につ いて具体的なプログラミングのコード例を比較 してみる。 ３．１ Z80 のアセンブラ言語の例 図３．１にアセンブラで１から１０の和を 求める例を示す。各行の手続き概要は以下の 通り。アセンブラ自体は手続き型の構造とな っている。 図３．１ アセンブラの例 01⇒プログラム開始番地を 100 番地とする 02⇒レジスタ B に 10 をセットする 03⇒アキュムレータ A をゼロ化する 04⇒A←A+B （最初は 0+10、最後は 54+1） 05⇒B←B−1 06⇒05 の結果 B≠０の場合は LOOP に行く 07⇒SUM←A １から 10 の和を格納 01. ORG 100H 02. LD B,10 03. SUB A 04. LOOP: ADD A,B 05. DEC B 06. JR NZ,LOOP 07. LD (SUM),A 08. HALT 09. ORG 200H 10. SUM: DEFS 1 11. END 外部変数 y ―――――――――――― 関数ｆ（ｘ） a. ｘ←ｘ＊２＊ｙ b. ｙ←ｙ＊（−１） c. Return x ―――――――――――― Main プログラム １． 外部変数ｙ＝１ ２． Print ｆ（３） ３． Print ｆ（３）

08⇒プログラムの停止 09⇒和の格納域を 200 番地からとする 10⇒和の格納域の確保 11⇒言語記述の終了 ３．２ C 言語（手続き型言語）の例 図３．２に C 言語で１から１０の和を求め る例を示す。各行の概要は以下の通り。 図３．２ C 言語で和を求める例 01⇒主プログラムで引数を持たないと宣言 02⇒整数の i と sum をゼロとして初期化 03⇒i を 1 から 10 まで１ずつ増加させ ながら04 を繰り返す 04⇒sum←sum+i （最初は、0+1、最後は 45+10） 05⇒求めた和 sum を出力 ３．３ Haskell（関数型言語）の例 図３．３にHaskell で１から１０の和を求め る例を示す。各行の概要は以下の通り。 図３．３ Haskell で和を求める例 01⇒関数 sumFunc 0 ≡ 0 02⇒関数 sumFunc n ≡ n + sumFunc (n-1) と定義する。 （注）≡：左辺を右辺のように定義する意 このプログラムを実行した結果を図３．４に 示す。ここでは、０から０の和、０から3 の和、 そして0 から 10 の和を求めた結果を示す。 図３．４ Haskell の実行例 以下に、関数型言語の特徴の再帰的な定義 を駆使したテキスト行数を勘定する場合の例 を二件示す。 図３．５は、テキストファイルの行数を求 めるプログラムである。ここでは、改行コー ドを「¥n」と記述している。 01⇒行カウント関数の引数が空≡ 0 行 02⇒同関数の引数の頭が改行コード ≡ 1 行と勘定し、 関数（引数は頭1 文字除外）を呼ぶ 03⇒同関数の引数が空ではない ≡ 行勘定せずに、 関数（引数は頭1 文字除外）を呼ぶ と各々定義する。 この行数カウントは改行コードの数を勘定 することになる。つまり改行コードが無い文 字列は１行分あるとは看做さない。 図３．５ Haskell で行数を求める例１ 図３．６は、テキストの最後が改行コードで終 了しなくても１行と勘定する場合のコードを例 01. int main(void) { 02. int i,sum=0;

03. for (i=1; i<=10; i++) 04. sum=sum + i; 05. printf ("sum=%d¥n",sum);} 01. sumFunc 0 = 0 02. sumFunc n = n + sumFunc (n-1) 01. linesCount [] = 0 02. linesCount ('¥n':cs) = 1 + linesCount cs 03. linesCount (c:cs) = linesCount cs

示する。この場合は再帰の定義を駆使している。 図３．６ Haskell で行数を求める例２ 図３．６の定義の概要は以下のようになる。 03、06⇒行頭であれ、行頭以外であれ、 空の文字列は、０行とする 04⇒行頭が改行コードの場合は、１行とし かつ、残りを再度行頭とする 05⇒改行コード以外の行頭も、１行とする しかし、残りは行頭以外とする 07⇒行頭以外の中に改行コードがあれば、 それを除いた残りを行頭とする。 （この行は、すでに05 で勘定済の行な ので、ここでは勘定しない） 08⇒行頭以外は常に、1 文字除き、 その残りを行頭以外とする （ここでは、改行コードが来なければ、 結果的にその他の文字をすべて読み飛 ばしていることになる） Haskell の場合、「＝」は代入や置換えではな い。「A＝B」とは「A を B と定義する」を意味 している。 ４．言語による生産性の比較例 プログラムのコードの多さによる生産性の比 較は、本当に客観的な尺度といえるのかという 議論はある。たしかに数十行の差などは、本当 に差が意味を持っているのか、有意差があるの かは議論の余地がある。しかし、ある程度の目 安にはなり得ると考える。 まずここで取り上げた、１∼10 までの和を求 める問題を見てみる。この場合は、 ・ アセンブラ言語の場合は、11 行 ・ C 言語の場合は、5 行 ・ Haskell の場合は、2 行 となり、Haskell が他より少ない行数でプログ ラムコードが書ける。 米国海軍関係におけるプログラミング言語に ついての調査結果の中に興味深い報告書(4)_があ る。この注目に値する結果を、表４．１に抜粋 して紹介する。報告書には言語が多々示されて いるが日本で主に知られている言語を記す。 表４．１ 米国海軍関係の調査による ソフトウェア開発の評価例 この表からは、Haskell が他を圧している。 とくに注目すべき点は、最後の行のHaskell で ある。これは、大卒で特別な訓練を受けず、8 日間Haskell の訓練を受けた後同じ課題を行っ た結果と言われている。 ５．高品質ソフトウェアのものつくり 以上、いくつかの例で示したように、手続き 型言語は、「やりたいことの手順を間違えない ように時間の順序を記述する」（How）ことが 求められる。これに対し関数型言語は、「やりた いことの定義を矛盾無く、条件に抜けがないよ うに記述する」（What）ことが求められている。 今後信頼性の高いソフトウェアを構築してい 01. linesCount str = lineHead str 02. where 03. lineHead [] = 0 04. lineHead ('¥n':cs) = 1 + lineHead cs 05. lineHead (c:cs) = 1 + lineOthers cs 06. lineOthers [] = 0 07. lineOthers ('¥n':cs) = lineHead cs 08. lineOthers (c:cs) = lineOthers cs 言語 コード 行数 ドキュメント 行数 開発期間 （時間） Haskell 85 465 10 Ada 767 714 23 Ada9X 800 200 28 C++ 1105 130 -(*2) Awk/Nawk 250 150 -(*2) Haskell(*1) 156 112 8 (*1)大卒で Haskell を 8 日間訓練しただけ (*2)報告なし

くためには、How を記述する言語から脱却し、 What を記述する言語に向かうことが必要では ないかと考えている。関数型言語において一番 ネックだったと思われる資源の消耗の激しさに 対しては、近年のハードウェアの高密度化によ り問題点が減少してきている。そして高品質な ソフトウェアを構築していくための形式手法 （数学の集合論や記号論理を基礎においてい る）による設計・妥当性の証明などとの親和性 にすぐれている、と考えている。 ６．組込み系のソフトウェア開発 現在Haskellによってパソコン上のシステム は開発例の蓄積が始まっている。 近年組み込み系のソフトウェア開発ニーズ は増加傾向にある。組込み系のシステムは人体 に影響を与えたり、社会システムに致命的な打 撃を与えるような問題が増えてくる可能性が 高い。このような事態を避けるためには、高信 頼性ソフトウェア開発の方法論の確立が望ま れるようになってくると思われる。 この課題に対応するためには、従来の開発技 法のみならず関数型言語のようにWhatを定義 するような形態の開発環境の整備が必要とな ってくると考える。 現在の技術水準から考えると、CPUを独自 に試行錯誤しながらつくることは技術的にと いうより、コスト的に困難であると考える。し かし、FPGA（Field Programmable Gate Array）等を利用することにより実験的なプロ セッサを作成し、実験を試行錯誤に行い、調 査・分析を行う環境は整ってきている。たとえ ば、Altera社が提供しているNIOSⅡ(5)_および Xilinx社が提供しているMicroBlaze( 6 )_につい ては、itronフリー版のTOPPERS(7) (8)_なども 用意されている。 このような状況にあるため、根本的に新し いプロセッサ（つまり新しいCPUと機械語） を考えていく素地が出来つつあると考える。 ７．今後の課題 これまでの検討経過を踏まえ、今後の計画テ ーマの大枠は以下のようになると考えている。 (1) 関数型的な言語との親和性に富んだ機械 語の検討を行う (2) (1)のプロセッサを具体的にFPGAに実装 して評価検討を行う この前提として、過去のLISPマシン等 の調査も必要 (3) 関数型的な言語で、ソフトウェア開発が容 易に行える言語の検討 (4) 開発した言語によって構築したソフトウ ェアシステムの信頼性を形式的手法によ って評価・検証するための方法論の検討 (5) 各種情報(９ ) (10) (11) (12) (13)_{等調査・分析を} 継続していく (6) 以上の検討を重ねながら、その都度、プロ トタイプを作成し試行を継続的に行う なお、これらの課題を総て具体的に推し進め ていくのは並大抵なことではない。このため、 (4)の評価・検証の方法論を見据えながら、土 台となる(1)の関数型のプロセッサの検討に重 点を置いていこうと考えている。

参考文献

1) Edsger W. Dijkstra, Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148 2) http://haskell.org/onlinereport/ 3) http://www.sampou.org/haskell/report-re vised-j/preface-jfp.html 4) http://www.mcs.vuw.ac.nz/courses/COMP 432/2006T2/docs/HaskellvCjfp.pdf “Haskell vs. Ada vs. C++ vs. Awk vs. ...An Experiment in Software Prototyping Productivity”,1994 5) http://www.altera.co.jp/products/ip/proces sors/nios2/ni2-index.html 6) http://www.xilinx.co.jp/ipcenter/processor _central/microblaze/doc/mb_tutorial_c2bi ts.pdf 7) http://www.toppers.jp/press/release-0504-1.pdf 8) http://www.ertl.jp/~honda/microblaze/ind ex.html 9) http://glew.org/nglew/papers/talx86-wcsss .pdf

“TALx86: A Realistic Typed Assembly Language”

10) http://homepages.inf.ed.ac.uk/da/papers/ hbal/hbal.pdf

“Heap Bounded Assembly Language” 11) http://directory.fsf.org/devel/prog/Other_p

rogramming_languages/hla.html

“High Level Assembly Language - Helps advanced Assembly programmers write better code” 12) http://en.wikipedia.org/wiki/SECD_machi ne 13) http://citeseer.ist.psu.edu/cache/papers/cs /15301/http:zSzzSzresearch.microsoft.co mzSzUserszSzlucazSzPaperszSzCompili ngML.A4.pdf/cardelli84compiling.pdf

“Compiling a Functional Language”

14) http://lml.ls.fi.upm.es/~jjmoreno/paper_a b.html