comp.hsの仕様

概要

これは、『C言語による計算の理論』で紹介されているモデルに基づき、自然数を処理する万能関数compをHaskellを用いて実装したものである。

本書の1章で関数プログラム(疑似C言語)について、2章でジャンププログラムについて、3章でジャンププログラムのコード化について解説されており、それに則っている。

compは2つの引数pとxを取り、自然数を返却する。

pは、プログラムを自然数にコード化したものであり、

xは、pの引数となるものである。

つまり、p(x)の値を求める処理系にあたるものがcompである

型表現は下記のようになる

code:hs

type Code = Integer

comp :: Code -> Code -> Integer

本書に則って用語を定義しておく

関数プログラム

疑似C言語

一見C言語と似た文法だが、for文の代わりにloop文があったりと多少異なる

ジャンププログラム

6種類の命令のみで記述されたプログラム

ラベルやGotoでループを行うなどする

<k,m,<S1,S2,..,Sn>>のような形式を取る

コード化

プログラムを一つの自然数に変換する方法

pair関数などを使用する

コード

一つの自然数

リストやプログラムを表現する

全体図

構成の全体図を示す

https://gyazo.com/64b9d6721e611d4bc533f77012b43cee

詳細については後述する

赤の枠で囲われた箇所が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]という型

code:hs

data 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

実装

repository

モジュールの説明

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の実装

インタプリタ上で試す

code:hs

import 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」を実行させた経過の例

code:tashizan

Code 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

↓

実行方法

app/Main.hsがrootとなるプログラムである

このファイル内のmain関数の内部でadd 3 2のように呼び出している

ghci上で実行する

$ stack ghci

ghciを起動

λ 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}で求められる

table: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

ここはもう少しまともな説明を追加する

#作った