計算の基本要素
データは文字列の0,1のみ
演算は文字列型の基本演算
制御構造はif、whileのみ
↑のような基本要素のみを持ったプログラムを「標準形プログラム」と言うなら、
データの基本要素
集合$ \Sigma=\{0,1\}さえあれば、全てのデータを表現できる
実際、バイナリがそうだしなmrsekut.icon
文字列型
$ \Sigma上の文字列型を$ \Sigma^\astと表す
0、1を数値ではなく、文字列の記号として扱うという意味
$ \Sigmaでない一般の文字列$ \Gammaの文字列に関しても、コード化できれば$ \Sigmaの2進列で表現可能
数値型
1進表記でも表現できる
ex. $ \underline{2}_{10}= \underline{00}_1、$ \underline{4}_{10}= \underline{0000}_1とすればいい
整数型
こういうrecordを考える
code:ts
type N = {
sign: Σ, // 0==-, 1==+
abs: Σ^* // 2進数
}
recordはみやすさのために導入しているだけであって、本質ではない
ex. -12→{sign: 0, abs: 1100}
レコードを使わない場合は、以下のタプルを使って[0,1100]と表現
タプル、配列型
$ \Sigmaである0,1を表すために3bit使えば表現力が上がる
table:対応表
表現したいもの Σ上の記号
0 000
1 111
[ 100
, 010
] 001
ex. [10,11]→100111000010111111001
この表現方法を使えば、任意の要素数の配列も、入れ子の配列も表現可能
ただ、bitの使い方が富豪なので、めちゃくちゃ長くなる
上の例の場合だと桁数は$ 3(\sum^n_{i=1}|a_i|+n+1)になる
$ \sum+1の部分でカンマと両括弧分
Pascalにnullっぽいεというのがあるのかなmrsekut.icon
[1,ε,0]のときなどは、εはガン無視で100 111 010 010 000 001と表す
論理値
table:対応表
true 1
false 0
論理記号
ルールを定めれば$ \Sigma^*で表現できる
$ \lorは0011など
当たり前すぎるが
以上の議論を加味すれば、プログラミング言語で書かれたコードそのものも、逐次的に$ \Sigma^*に変換できる
printをpは1000111、rは1000110のように変換する(値は適当)
制御構造の基本要素
primitiveにはifとwhileがあれば全て表現可能
関数定義と関数呼び出し
ifとwhileで表現可能
if/whileのみで表現するまでの変換手順
これを変換する
code:a.ts
Loop: {
if x==null then halt(1);
a = head(x);
x = right(x);
if a==1 then halt(0) else goto Loop;
}
1. プログラムをif/gotoのみに変換する
関数呼び出しを全てインライン展開するなどする
再帰関数は最後までインライン展開できないがこれはスタックを利用すると良いらしい
意味がわからんmrsekut.icon
そもそも最後までインライン展開できないのか？
各行をラベル付けし、if/gotoのみで遷移できるように書き換える
code:b.ts
L1: if x==null then goto L5 else goto L2;
L2: a=head(x); goto L3;
L3: x=right(x); goto L4;
L4: if a==1 then goto L6 else goto L1;
L5: c=1; goto L0;
L6: c=0; goto L0;
L0: halt(c);
2. whileで全体を囲いgotoの代わりにswitchを使う
switchはifに変換可能
code:c.ts
pc=1;
while pc != o {
switch pc
case 1: if x==null then pc=5 else pc=2;
case 2: a=head(x); pc=3;
case 3: x=right(x); pc=4;
case 4: if a==1 then pc=6; pc=1;
case 5: c=1; pc=0;
case 6: c=0; pc=0;
}
参考