Twitter見てたら「プログラム言語なんて１つやれば後はなんとかなる」という発言に対して「お前Malbolgeでも同じこと言えんのか」みたいなレスがありました。私浅学なもので「Malbolgeって何？」となって調べてみたのですが、なかなか強力な言語仕様だったんですねこれ。
私も上記の「１つやれば〜」系の呟きをした事がありますが、自分が井蛙だったと恐縮する次第なのでした。
言語仕様を見て、さすがに自分でコードを書く気にはならなかったのですが、インタプリタであればインプリ量がそう多くもなさそうと分かり、なんちゃってで作ってみました。
環境は以下で確認。他で動くかはわかりませんごめんなさい…
- Mac OS 10.14.4
- Python3.7
Malbolgeについて
ペディアだと以下英語の方だと仕様も記載されています。
後はロベール (id:Robe) さんの以下の記事が大変参考になりました。ありがとうございます。
上記を見ると分かりますが、書くのが非常に難しい…というかこれ鉛筆で書ける人いるんですかーぐらいな感じの言語です。ペディアに掲載されているHello World（以下）を見ても難しさがわかるかと思います。
(=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<
個人的には言語というよりは仮想CPUという印象を抱きました。私なりに理解した特徴をざっと。
- メモリモデルと命令と演算が定義されている
- メモリはワード単位
- 命令は８種類、ロード、ジャンプ、ローテート、演算等
- レジスタは演算系のAとデータのD、後はPC的な意味合いのCがあります。ちなみに命令を実行するとCはもちろん、Dもインクリメントされます。
- その演算はCrazyと呼ばれるものしかないので、足し算とかもどうすればいいのやら状態（頭の悪い私には）
- プログラマが書いたコードがそのまま命令とはならず、変換テーブルの結果が命令コードになる（なのでそれを予測してコードを書く必要がある）
- メモリの内容も一定のルールで書き換わるので、それを意識してコードを組む必要がある
要は難読化されたコードでアセンブラというか機械語で書くって感じです。
インタプリタを動かしてみる
Macでやる場合、Takaaki Yamamoto | 山本一彰さんの以下のページが大変参考になります。ありがとうございます。
インタプリタのソース（C言語）は以下。
Macで動かす場合の箇条書きです。
- ソースをコピペ。 .c で保存
- #include ＜malloc.h＞ をコメントアウト
- gcc malbolge_interp.c -o malbolg でビルド
- Hello World(上とか、WikiPediaにあるやつ）のソースをファイルに。例えばhello_maとか
- ./malbolg hello_ma で実行出来ます。
なんちゃってインタプリタを作ってみた
命令数が少なく、メモリ最大値も大した事はないので、インタプリタを作るのはプログラムを作るよりは遥かに楽ですｗ
なのでPythonでざっと作ってみました。
仕様通りに完璧に出来ているという事は当然ありませんので、そこは注意してくださいなのです。多分どこかにバグはあると思ってます。
#!/usr/bin/env python
# coding: utf-8
#
# malbolge_test.pyとして書きました
#
import sys
import hexdump
class MalbolgeInterpreterModoki:
"""
Malbolgeインタプリタ（もどき）
→細かい動作確認まではしてないのでご容赦！
"""
def __init__(self, debug_mode):
"""
初期化
"""
self.debug_mode = debug_mode
self.OP_INDEX_CODE = 0
self.OP_INDEX_FUNC = 1
# xlat1で変換したコード（命令）の内訳
self.op_table = [
[106, self.op_mod_d],
[105, self.op_jmp],
[42, self.op_rotate],
[112, self.op_crz],
[60, self.op_print],
[47, self.op_input],
[118, self.op_end],
[111, self.op_nop]
]
# 元のコードを見ると１ワードは３進数10桁という考えっぽい？
self.BASE3_DIGITS = 10
# メモリサイズ（バイトじゃないよワード-unsigned short-だよ）
self.MEMORY_SIZE = 59049
# xlat1は[C]から命令コードを取る時に使う変換テーブルです。
self.xlat1 = "+b(29e*j1VMEKLyC})8&m#~W>qxdRp0wkrUo[D7,XTcA\"lI"
self.xlat1 += ".v%{gJh4G\\-=O@5`_3i<?Z';FNQuY]szf$!BS/|t:Pn6^Ha"
# xlat2は実行後に、[C]の内容を書き換えるのに使う変換テーブルです。
self.xlat2 = "5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72FhOA1C"
self.xlat2 += "B6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G\"i@"
self.cpu_reset()
def cpu_reset(self):
"""
レジスタとメモリの初期化（後関連変数も）
BSSっぽくしてますが、すぐに埋めるのであんまり意味はないかな…
"""
self.memory = [0] * self.MEMORY_SIZE
self.A=int(0)
self.C=int(0)
self.D=int(0)
self.seq = 0
self.end = False
self.console = ""
def show_regs(self):
"""
レジスタ表示。デバッグなどで必要があれば使ってください。
"""
print (self.seq, ": A=", self.A, "C=", self.C, "D=", self.D)
def dump_memory(self, max):
"""
メモリダンプ。デバッグなどで必要があれば使ってください。
＃アドレスがないと厳しいかも（；^ω^）
"""
print ("memory: size=", len(self.memory), " max=", max)
text = "["
i = 0
for data in self.memory:
text += hex(data) + " "
i += 1
if i == max:
break
text += "]"
print(text)
def to_base3(self, data):
"""
Malbolgeでは３進数演算を行いますので、３進数を作る必要があります。
これは10進数を3進数にします。一番頭の悪い変換方法でやってます（汗
"""
# まずは元のデータから一桁ずつ取り出していきます。
digits = []
while True:
digits.append(data % 3)
if data <= 2:
break
data = int(data / 3)
# Malbolgeでは桁固定なので、残りは0として埋めます
remain = self.BASE3_DIGITS - len(digits)
for i in range(0, remain):
digits.append(0)
return digits
def from_base3(self, digits):
"""
Malbolgeでは３進数演算を行いますので、３進数を作る必要があります。
これは3進数を10進数にします。一番頭の悪い変換方法でやってます（汗
"""
# 例： 123 -> 3 + 2 * 3 + 1 * 9 = 18
data = 0
base = 1
i = 0
for digit in digits:
data += digit * base
i += 1
if i == 1:
base = 3
else:
base *= 3
return data
def crazy(self, x, y):
"""
Malbolgeの演算処理です。２つの３進数を演算して１つの３進数を出力
各桁毎に以下の計算をします。桁数が固定なので、それで記述出来ます
x/y 0 1 2
----------------
0 1 0 0
1 1 0 2
2 2 2 1
例： crazy(x=10, y=12) = 12（３進数なので10進なら5）
"""
crazy_table = [
[1, 0, 0],
[1, 0, 2],
[2, 2, 1]
]
digits_x = self.to_base3(x)
digits_y = self.to_base3(y)
result = []
data = 0
for i in range(0, self.BASE3_DIGITS):
data = crazy_table[digits_x[i]][digits_y[i]]
result.append(data)
return result
def op_mod_d(self):
"""
MOV命令 D = [D];
"""
ref_D = self.memory[self.D]
if self.debug_mode:
print (self.seq, "C=", self.C, ":106: D = [D]; # D=", self.D, "[D]=" , ref_D)
self.D = ref_D
def op_jmp(self):
"""
JUMP命令 C = [D]; jmp [D];
"""
ref_D = self.memory[self.D]
if self.debug_mode:
print (self.seq, "C=", self.C, ":105: C = *D; jmp [D]; # D=", self.D, "[D]=", ref_D)
self.C = ref_D
def op_rotate(self):
"""
右シフト命令 rotate_right [D]; A=D;
"""
ref_D = self.memory[self.D]
# 右シフトは桁を1個減らす（10進数で123/10 -> 12みたいに）
result = int(ref_D / 3)
# 最下位桁の内容を最上位桁に移動（上の続きだと 123 -> 312にする感じ）
# 19683 は ３進数で1000000000
result = result + (ref_D % 3) * 19683
if self.debug_mode:
print (self.seq, "C=", self.C, ": 42: rotate_right [D]; A=D; # D=", self.D, "[D]=", ref_D, "result=", result)
self.memory[self.D] = result
self.A = result
def op_crz(self):
"""
演算命令 [D] = crazy(A, [D]); A=[D];
"""
ref_D = self.memory[self.D]
result_digits = self.crazy(ref_D, self.A)
result = self.from_base3(result_digits)
if self.debug_mode:
print (self.seq, "C=", self.C, ":112: [D] = crazy(A, [D]); A=[D]; # D=", self.D, "[D]=", ref_D, "A=", self.A, "result=", result)
self.memory[self.D] = result
self.A = result
def op_print(self):
"""
一文字出力 print A;
すみません、処理面倒なので一文字毎に改行しちゃいます m(__)m
"""
#元のコードを見るとキャストさせて
#出力させるのでも良いみたいです
#（文字列作る際の参考になりますかねこれ）
ascii = chr(self.A % 256)
if self.debug_mode:
print (self.seq, "C=", self.C, ": 60: print A; # put(\"", ascii ,"\") A=", self.A, ",", hex(self.A))
else:
print("put(\"", ascii ,"\")=", self.A)
self.console += ascii
def op_input(self):
"""
一文字入力 input A
すみません、処理面倒なので<enter>が必要です m(__)m
@ : 改行
# : システム終了（内部特殊コマンド的な扱い）
"""
print ("(m_o_m) Sorry, please input 1 char(@=cr,#=exit) and <enet>:")
text = input()
if text[0] == "@":
data = 0x0a
elif text[0] == "#":
print("exit this program.")
sys.exit(0)
else:
data = ord(text[0])
if self.debug_mode:
print (self.seq, "C=", self.C, ": 47: input A; # putc=", ord(text[0]), hex(data))
self.A = data
def op_end(self):
"""
終了 end;
プログラムをここで終了させています。
"""
if self.debug_mode:
print (self.seq, "C=", self.C, ":118: end;")
print ("end of program.")
print("console:")
print(self.console)
print("--------completed.")
sys.exit(0)
def op_nop(self):
"""
NOP nop
"""
if self.debug_mode:
print (self.seq, "C=", self.C, ":111: nop;")
return
def execute_opcode(self, op_code):
"""
命令コードに基づいた処理を実行します
各命令コードとその処理はself.op_tableに列挙したので
比較して飛ばすのがお仕事
"""
for op in self.op_table:
if op[self.OP_INDEX_CODE] == None or op[self.OP_INDEX_CODE] == op_code:
op[self.OP_INDEX_FUNC]()
return
if self.debug_mode:
print ("illegal op code ", op_code, " : -> nop.")
def inc_regs(self):
"""
Malbolgeでは各処理完了後でCとDを+1します。
メモリ終端まで行くと、最初に戻します。
"""
if self.C == self.MEMORY_SIZE-1:
self.C = 0
else:
self.C += 1
if self.D == self.MEMORY_SIZE-1:
self.D = 0
else:
self.D += 1
self.seq += 1
def execute_1step(self):
"""
1命令だけ実行します。
ステップ実行でよしなにしたい方は
こちらが便利かもしれません。
"""
# Malbolgeではメモリのコードを
# 単純に実行する事はしません。
# 以下のように、テーブル変換した
# コードを使います。
# つまりは、これを意識して
# 命令を記述する必要があるらしいのです。
ref_C = self.memory[self.C]
t_index = (ref_C - 33 + self.C) % 94
op_code = ord(self.xlat1[t_index])
# 命令を実行します
self.execute_opcode(op_code)
# 命令を実行した後、メモリが書き換えます。
# メモリ操作書くときはこれも意識しないと
# いけないと思われます。
ref_C = self.memory[self.C]
self.memory[self.C] = ord(self.xlat2[ref_C - 33])
self.inc_regs()
def execute(self):
"""
プログラムを実行します。
endが出るか、バグで死ぬかのどっちかで抜けます
（あ、後input で ＃でも抜けます）
"""
while True:
self.execute_1step()
def is_this_valid_code(self, i, b):
"""
簡易文法チェック
valid_listにある命令以外かどうかをチェック。
ダメな場合はexitしてしまいます。
"""
# 以下の命令（命令？）以外はNGにします。
valid_list = "ji*p</vo"
#( x - 33 + i ) % 94
t_index = (b - 33 + i) % 94
c = self.xlat1[t_index]
for valid in valid_list:
if valid == c:
return
print("Illegal opcode= \"" + c + "\"(org:"+ str(b) + ")")
sys.exit(1)
def load_code(self, path):
"""
プログラムをメモリに展開します。
"""
# 初期化
self.cpu_reset()
cnt = 0
# コードの読み込み
with open(path, "rb") as f:
data = f.read()
for b in data:
# スペース改行は無視
if b == 0x20 or b == 0x0d or b == 0x0a:
continue
# 簡易文法チェック。ダメなら抜ける
self.is_this_valid_code(cnt, b)
# メモリにプログラムを書きます
#
# Malbolgeのメモリモデルは
# unsigned shortなのですが
# プログラムは unsigned charです。
# 何を言っているかというと
# memory(0) <- code(0)
# memory(1) <- 飛ばす
# memory(2) <- code(1)
# memory(3) <- 飛ばす
# とします。詰めちゃうとダメみたいです
# これはPythonなので配列に入れてるだけですが…
self.memory[cnt] = b
cnt += 1
# C言語なんかだとメモリの残りは０で埋めればよいのですが
# Malbolgeはそれを許してくれなくて、こんな感じで
# Crazy演算して入れないといけません。
while cnt < self.MEMORY_SIZE:
x = self.memory[cnt - 2]
y = self.memory[cnt - 1]
self.memory[cnt] = self.from_base3(self.crazy(x,y))
cnt += 1
if __name__ == "__main__":
# 引数チェック
if len(sys.argv) < 2 or (len(sys.argv) == 3 and sys.argv[1] != "debug"):
print ("python malbolge_test.py (debug) <program file>")
sys.exit(1)
# 引数からデバッグモードの有無と、プログラムファイルの設定を行います
debug = False
path = sys.argv[1]
if len(sys.argv) == 3:
debug = True
path = sys.argv[2]
# Malbolgeの実行
m = MalbolgeInterpreterModoki(debug)
m.load_code(path) # プログラムをメモリに展開
m.execute() # プログラムの実行
本記事では説明時に上記をmalbolge_test.pyとして取り扱います。
使い方
一応２つの使い方を用意しています。
通常モード
普通に実行するモードです。とはいえ、私の実力がないのと手抜き（汗）とで以下の点が異なります。
- 一文字出力でいちいち改行表示されます
- 一文字入力では A ＜enter＞のようにする必要があります。ちなみに＃ ＜enter＞するとMalbolgeの仕様とは関係なくプログラムを抜けます。
このあたり、ひでーなと思ったらソースを修正していただければと思いますです（汗）
実行例は以下の通り（hello_ma は hello worldのMalbolgeプログラム）
python ./malbolge_test.py hello_ma <enter>
デバッグモード
こちらは上記に加えて各命令の実行状況がトレース出来るモードです。ただしハンパなくprintされるのでウザさ倍増なのでご注意ください。
同様に実行例。debugを追加します。
python ./malbolge_test.py debug hello_ma <enter>
動作確認状況
以下の動作は確認しています。逆に言えばこれだけしかやってません。。
- hello world
- cat：英語のペディアにあるサンプル
- 99 Bottles of Beer：Hisashi Iizawaさんが作成したプログラムで「Bottles of Beer」みたいなのがいっぱい出てきます。debugモードでやるといつ終わるのかこれ状態です…
コードについて
こんなやっつけで作ったクソなインタプリタ（のようなもの）でも見て頂けるという慈愛あふれる方ありがとうございます。下のmainから見ていくと流れ的には追えるかなーとか思います。
ちなみに仕様などではわからなくて、インタプリタのコードで分かったこともあります。
- ３進数は10桁固定でいいみたいです
- putする際はcastで良いみたいです。なので下位バイトだけ目的のデータにするやり方が通用すると見て良いみたいです。
- Pythonではあまり意識しなくて良いみたいですが、メモリモデルにプログラム（テキストファイル）入れる際に例えばC言語のmemcpyみたいな事をしてはいけないみたいです。
Hello Worldがどう処理されているか。
実は、これが一番やりたかった感じなのですが。あの複雑怪奇なソースが実際にどう処理されているのかを可視化してみました。
全部やると長いのでdebugモードで実行し、途中（”Hell”まで）までのログを転載します。
0 C= 0 :106: D = [D]; # D= 0 [D]= 40
1 C= 1 :112: [D] = crazy(A, [D]); A=[D]; # D= 41 [D]= 93 A= 0 result= 29524
2 C= 2 :112: [D] = crazy(A, [D]); A=[D]; # D= 42 [D]= 75 A= 29524 result= 72
3 C= 3 : 60: print A; # put(" H ") A= 72 , 0x48
4 C= 4 :112: [D] = crazy(A, [D]); A=[D]; # D= 44 [D]= 90 A= 72 result= 29506
5 C= 5 :112: [D] = crazy(A, [D]); A=[D]; # D= 45 [D]= 89 A= 29506 result= 35
6 C= 6 :112: [D] = crazy(A, [D]); A=[D]; # D= 46 [D]= 52 A= 35 result= 29507
7 C= 7 :112: [D] = crazy(A, [D]); A=[D]; # D= 47 [D]= 52 A= 29507 result= 44
8 C= 8 :112: [D] = crazy(A, [D]); A=[D]; # D= 48 [D]= 69 A= 44 result= 29541
9 C= 9 : 60: print A; # put(" e ") A= 29541 , 0x7365
10 C= 10 :112: [D] = crazy(A, [D]); A=[D]; # D= 50 [D]= 48 A= 29541 result= 73
11 C= 11 :112: [D] = crazy(A, [D]); A=[D]; # D= 51 [D]= 47 A= 73 result= 29552
12 C= 12 :112: [D] = crazy(A, [D]); A=[D]; # D= 52 [D]= 123 A= 29552 result= 60
13 C= 13 :112: [D] = crazy(A, [D]); A=[D]; # D= 53 [D]= 109 A= 60 result= 29548
14 C= 14 : 60: print A; # put(" l ") A= 29548 , 0x736c
15 C= 15 : 60: print A; # put(" l ") A= 29548 , 0x736c
ここまでだとcrazyの計算で頑張って、目的の文字列を作っている感じなようです。後ろの方に行くと、ジャンプ命令を使っていたりもするようです。
ローテート命令とかは使っていなかったですね。ちなみに99 Bottles of Beerはローテートも使っていました。つか良くこのプログラム書けますよねもうひたすら尊敬の念しか出ないです駆け出しレベルの私としては。
おまけ：ちょっとハマったケース
実はデバッグをしていてハマったケースがあります。ロべールさんのサイトにある「入力のコピー（作者：Lou Scheffer）」です。コードを転載します。
D'BA@?>=<;:9876543210/.-,+*)('&%$#"!~}|{zyxwvutsrqponmlkji
hgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/
.-,+*)('&%$#"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTS
RQPONMLKJIHGFEDC&_ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ菴ｽｽ
ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ
ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ
ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ菴ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ
ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ
（ロべールさんのサイト（以下にURLも）から転載）
これ、オリジナルのインタプリタでは動きますが、私のインタプリタでやると以下のエラーが出ます。
Illegal opcode= "~"(org:239)
駆け出しレベルが中途半端に自作インタプリタに手を出すとやっぱ痛い目見るよなーと思ったのですが、どうもオリジナルのインタプリタでも想定外な挙動のように思えます。
オリジナルを以下のように修正してみました。exec関数の所に範囲チェックを入れています。
#if 1 /* 追加部分：範囲チェックを付けてみる */
if (mem[c] -33 >= sizeof(xlat2))
{
printf("!!!!!!!!!!!!!!! %d >= %lu \n", mem[c] -33, sizeof(xlat2));
return;
}
#endif
mem[c] = xlat2[mem[c] - 33];
if ( c == 59048 ) c = 0; else c++;
if ( d == 59048 ) d = 0; else d++;
これで実行すると以下。
!!!!!!!!!!!!!!! 156 >= 95
つまり、xlat2という変換テーブルの範囲外のデータアクセスをして成立しているように見えるのです。この場合はどういう事になるのかなーと思いました。
＃私はMalbolgeは（も？）初心者なのでここらの知見が全くありません。また上記のどこかが理解間違えの可能性も十分にあります事をご容赦下さい。
最後に
という事で「プログラム言語なんて１つやれば後はなんとかなる」とマウントを取られたらMalbolgeを差し出してあげましょう（苦笑）。
＃あ、ジョークですからねジョーク。