comp.hsの仕様
概要
これは、『C言語による計算の理論』で紹介されているモデルに基づき、自然数を処理する万能関数compをHaskellを用いて実装したものである。
本書の1章で関数プログラム(疑似C言語)について、2章でジャンププログラムについて、3章でジャンププログラムのコード化について解説されており、それに則っている。
compは2つの引数
p と x を取り、自然数を返却する。 p は、プログラムを自然数にコード化したものであり、 x は、 p の引数となるものである。つまり、
p(x) の値を求める処理系にあたるものがcompである型表現は下記のようになる
hstype Code = Integer
comp :: Code -> Code -> Integer本書に則って用語を定義しておく
関数プログラム
疑似C言語
一見C言語と似た文法だが、for文の代わりにloop文があったりと多少異なる
ジャンププログラム
6種類の命令のみで記述されたプログラム
ラベルやGotoでループを行うなどする
<k,m,<S1,S2,..,Sn>> のような形式を取るコード化
プログラムを一つの自然数に変換する方法
pair関数などを使用する
コード
一つの自然数
リストやプログラムを表現する
全体図
構成の全体図を示す
詳細については後述する
赤の枠で囲われた箇所がcompの核心であり、青色の部分は関数プログラムの操作をする部分である
実装上の経緯
青色の部分を作ろうとした理由と、それを断念した理由について
本来、compは赤枠の部分のみで完結するプログラムではある。プログラムとその引数を自然数で表現したものを用意すると実行すことができる。
しかし、C言語のような人間に慣れ親しんだプログラムを自然数に変換するためにはいくつかの手順を踏む必要があり、バグを起こさずに手動で変換し切るのはプログラムが大きくなればなるほど困難になる。
そこで、関数プログラムのコードを自動でコードへ変換するものがあると便利だと思い、それを実装しようとしたのが青枠の部分である。
青枠の部分はほぼ完成したが、肝心の、青と赤をつなぐJumpBrigdeの部分が時間の都合で断念することになった。
故に青枠の部分が結果的に使用していないが、一応残しておく。
上の図の各モジュールの説明
赤枠
Code
ジャンププログラムをコード化したもの
<k,m,<S1,S2,..,Sn>> をコード化した一つの自然数ProgramCode
Codeを、変数とbodyに分離したもの
data ProgramCode = ProgramCode InputCode VarsCode CmdsCode という型AST Program
ジャンププログラムをAST化したもの
data Program = Program Vars [Cmd] という型hsdata Cmd = Goto Line
| Bind Integer Integer
| BindV Integer Integer
| Inc Integer
| Dec Integer
| If Integer Integer
| Start扱いやすさのため、
Start という命令を追加しているInteger
最終的な
comp(p,x) の結果に相当する一つの自然数AST Programに
execute を適用することで得られる青枠
Extend C
本の中では「関数プログラム」と呼ばれているもの
C言語に
loop などを追加したオリジナルな言語のコードただし関数定義は頭に
fn を付与するAST Define
C言語をparseして作成するAST
実装
モジュールの説明
AST/Program.hs
AST Programの型定義
ToProgram.hs
コード(一つの自然数)を、AST Programに変換する
toProgram の実装Code.hs
コード化に関する関数群
本書内で紹介されている
pair や element や replace なども定義している利用例はCodeSpec.hsを参照
Comp.hs
AST Programを実際に実行する
execute などの実装CompSpec.hsに実際にtashizanとguusuuのプログラムの例とテストがある
Util.hs
ExtendC
AST/Define.hs
Data/Functions.hs
JumpBridge.hs
Parser.hs
C言語をAST Defineに変換するparserの実装
インタプリタ上で試す
hsimport Text.Parsec
parseTest parseExpr "1+2"
parseProgram "fn hoge(a,b) {r = a + b; return(1);}"CodeGen.hs
AST DefineからExtendCコードを生成する
実行例
以下は、本のp.26に掲載されている「tashizan」で、「3+2」を実行させた経過の例
tashizanCode 213797904982138037454632940231947778583451643946214351539888667374659624571846317189430034392722181574191018775500344307826886363942159348121221846668501076259189172349201939902055099238535683718239773388149828334592987613507615588
↓
↓ toProgramCode
↓
ProgramCode 2 2 113410085239160792121509200101
↓
↓ toProgram, tasizanの引数に49(= pair [3,2])
↓
Program [(1,3), (2,2)] [(Start),(If 2 3),(Goto 6),(Dec 2),(Inc 1),(Goto 1)]
↓
↓ execute
↓
5実行方法
app/Main.hs がrootとなるプログラムであるこのファイル内のmain関数の内部で
add 3 2 のように呼び出しているghci上で実行する
$ stack ghcighciを起動
λ Main.main mainを実行
ビルドして実行
$ stack run実行時間に対する考慮
コードをASTに変換する際にものすごい時間がかかる
特に
depair 関数の部分 depair を何も考えずに実装すると時間が大変なことになる単純に
pair(1000, 1000) なる数値から、 (1000, 1000) を求めるためには、1000^2回ループを回す必要がある depair の高速化例としてm=1000が引数として与えられたとする
①mの2進数表示の桁数を取得する
→x_1=10桁
②\sqrt{2m}の2進数表示の桁数を取得する
→x_2=\frac{x_1+1}{2}=5.5
③x_2より大きい自然数を確定
5.5より大きい最小の自然数は、x_3=6
④2^{x_3-1}\le n\le 2^{x_3}を決める
→2^5\le n\le 2^6
⑤この範囲を2分探索してmより大きくなる部分を求める
f(x)=\frac{(x+1)(x+2)}{2}で求められる
2分
| x | 32 | 40 | 42 | 43j | 44 | 48 | 64 | ||||||||
| 表の0行 | ①561 | ④861 | ⑥946 | ⑦pair970 | ⑤1035 | ③1225 | ②2145 |
よって(x_5,t)=(44, 1035)が確定
⑥left, rightを求める
t-m=1035-1000=35←right
x_5-35=44-35=9←left
ここはもう少しまともな説明を追加する