読者です 読者をやめる 読者になる 読者になる

esolangを書く、の2

この記事は、TSG Advent Calendar 2016 - Adventar の14日目のために公開されました。

先日のやつ esolangを書く - 忖度 の続きです。

今回はどちらも素手で書くのが困難な言語なので、pythonソースコードを出力させます。
先にネタバレしておくと、WhiteSpaceはアセンブリ言語っぽくて、ferNANDoは論理回路っぽいなと思いました。計算機システムとハードウェア構成法ですね。

WhiteSpace

これです。駒場祭に展示させたかったので当日に書きました。
ソースコード

    		  	  
    	
 
			     
    	 
 
			 
  	 	 
    	 
			    	 
	  
    
	
	     
			    		    
	  		       	 
 
			     	
			    	
	  	 
     	
 
			     
 
		  	
			 	 
    	 
				
 	


です。
どちらも読みにくくて仕方がないので、書くために使ったpythonソースコードを載せます。

#coding: utf-8
from Tkinter import Tk

def i2w(x):
	res = ""
	if x>=0:
		res += " "
	else:
		res += "\t"
		x *= -1
	ad = ''
	while x>0:
		ad = ("\t" if x%2==1 else " ") + ad
		x /= 2
	res += " " + ad
	return res

#http://www.kembo.org/whitespace/tutorial.html
#http://koturn.hatenablog.com/entry/2015/08/10/000000

def push(x):
	return "  " + i2w(x) + "\n"

geti = "\t\n\t\t"

getc = "\t\n\t "
	
outi ="\t\n \t"

endp = "\n\n\n" 

heap_s = "\t\t "
heap_l = "\t\t\t"

dup = " \n "

add = "\t   "
sub = "\t  \t"
mul = "\t  \n"
mod = "\t \t\t"
div = "\t \t "

swap = " \n\t"

def mark(x):
	return "\n  " + x + "\n"

def jmpng(x): #負だったら飛ぶやつ
	return "\n\t\t" + x + "\n"

def load(x):
	return push(x) + heap_l
def store(x):
	return push(x) + swap + heap_s

r = Tk()
r.clipboard_clear()

#s = push(0) + geti + push(0) + heap_l + outi + endp
s = (
	push(100) + store(1) + #カウンタをheap(1)に
	push(0) + store(2) + #答えをheap(2)に
	mark("\t \t ") + #ラベル
	
	load(2) + push(2) + mul +  #ansを二倍
	push(0) + getc + load(0) + #入力をpush
	push(ord('0')) + sub + add + 
	store(2) + #getcの結果を足してstore
	
	load(1) + #カウンタロード
	push(1) + sub + dup + store(1) + #デクリメントしてstore.
	push(0) + swap + sub + jmpng("\t \t ") + #正だったら飛ぶ
	load(2) + outi + #出力
	endp
)
r.clipboard_append(s)
#print getc + getc + endp[:-1]

中ほどに載っているリファレンスとインタプリタを参考にしました。
whitespaceはいちおうスタック型言語ですが、スタックに対するランダムアクセスがあったり、heap領域が使えたりするので、ふつうの言語と遜色なく書けます。実質アセンブリみたいなもんです。

今回は、IdeoeのWhiteSpaceインタプリタの内部実装がHaskellだったので、整数の大きさに制限がないです。
そのため、アルゴリズム

i = 100
ans = 0
while i>0:
  ans = ans * 2 + getc() - 48
  i --
puti(ans)

みたいな感じでしました。実質アセンブリでしたね。(for文のとこ、先にロードしてデクリメントしてから比較ジャンプするとことか)

ferNANDo

ferNANDo - Esolang :: 仕様
FerNANDo – Try it online! :: インタプリタ

Brainf*ckやBefungeやWhiteSpaceは有名ですが、これは初耳でした。その他の言語が高性能に思えるくらい仕様がシンプルでした。

仕様の簡単な説明

変数名は何でも可(ただし?は特別)。最初は全て0で初期化されている。
命令は3種類のみ。

nand
a b c 

と書くと、a に b NAND cの結果が代入される。

a b 

と書くと、a に a NAND bの結果が代入される。

ループ
hogehuga

と、1行に1変数だけ書くと、上に全く同じ行がなければ特に何もせず、上に同様に hogehuga とだけ書かれた行があった場合、hogehuga が1なら上の行にジャンプし、0ならそのまま次の行に移る。

入出力
a b c d e f g h

と書くと、a b c d e f g h を8ビットの数字としてみたものに対応するアスキーコードが出力される。

r a b c d e f g h

と書くと、a b c d e f g h に入力を1文字読み込んだもののアスキーコードが、rに入力に成功したかどうかが入る。

あと、?は特別な変数で、いつでも読み出し時にランダムな値が出てくるらしいですが、今回は使いませんでした(むしろこれに気付かないバグを踏んだ)

解法

見ての通り全変数が1bitのみで演算がNANDしかない言語です。
こんなんでプログラミングできるんかいなと思う人がいるかもしれませんが、いちおうNANDがあればANDやORやNOTができるので論理演算には事欠かず、またループも可能だし入出力もできるので問題を解けるポテンシャルがあるように思えます。(実際にwikiのサンプルコードの中にルール30をシュミレートするプログラムが書いてありました。ルール110ができればチューリング完全なので、多分ferNANDoもチューリング完全なのではないでしょうか)*1

で、実際に解いてみました。

#coding: utf-8
from Tkinter import Tk


init = """
0 0 0
0 0 0 
1 1 1 
"""

var_num = 0
def getv():
	#一桁変数は避ける。
	global var_num
	var_num += 1
	return 'v' + str(var_num)

def getvs(x):
	if x==1:
		return getv()
	else:
		return [getv() for i in xrange(x)]

#一時変数名の衝突を防ぐためにdで深さを入れる。
#あと、同じ名前が入ってきても大丈夫なように設計しましょう...
#具体的には、sに代入したあとに、aやbを参照すると壊れてる可能性がある。

def nand(s,a,b): # s = a nand b
	return "%s %s %s\n" % (s,a,b)

def one(a): #aに1を代入
	return nand(a,a,'0')

def not_(s,a): #s = !a
	return nand(s,a,a)

def zero(a): #aに1を代入
	return one(a) + not_(a,a)

def and_(s,a,b): # s = a & b
	return nand(s,a,b) + not_(s,s)

def mov(s,a): # s := a
	return and_(s,a,a)

def or_(s,a,b): # s = a | b
	return not_(a,a) + not_(b,b) + nand(s,a,b)

def xor(s,a,b): # s = a ^ b
	ta,tb,mb = getvs(3)
	return mov(mb,b) + not_(ta,a) + not_(tb,b) + nand(s,a,tb) + nand(tb,ta,mb) + nand(s,s,tb)

def ha(c,s,a,b): #ハーフアダー。
	#s = a ^ b
	#c = a & b
	ma, mb = getvs(2)
	return mov(ma,a) + mov(mb,b) + xor(s,ma,mb) + and_(c,ma,mb)

def fa(c,s,p,q,r): #フルアダー。
	#s = a ^ b
	#c = a & b
	mp, mq, mr, tp= getvs(4)
	return (
		mov(mp,p) + mov(mq,q) + mov(mr,r) + 
		ha(c,s,mp,mq) + ha(tp,s,s,mr) + or_(c,tp,c)
	)
	
def inc(ds): #dsで表される配列をインクリメントする。
	tp,tq = getvs(2)
	res = one(tp)
	for s in ds:
		res += and_(tq,tp,s)
		res += xor(s,tp,s)
		res += mov(tp,tq)
	return res

def neq(r,cs,ds): #csとdsを比べた結果をrに格納する。等しいなら0。
	res = zero(r)
	tt = getv()
	for p,q in zip(cs,ds):
		res += xor(tt,p,q)
		res += or_(r,r,tt)
	return res

def add(c,cs,ds): #cs += ds, cには桁上がりが入る
	nc,ns = getvs(2)
	res = zero(nc)
	for p,q in zip(cs,ds):
		res += fa(nc,ns,nc,p,q)
		res += mov(p,ns)
	res += mov(c,nc)
	return res

def movv(cs,ds): #cs := ds
	res = ""
	for t,d in zip(cs,ds):
		res += mov(t,d)
	return res

def sub(c,cs,ds): #cs += ds, cには負数でないかどうかが入る
	td = getvs(len(ds))
	res = movv(td,ds)
	for t in td:
		res += not_(t,t)
	res += inc(td)
	res += add(c,cs,td)
	return res

def geq(r,ds,cs): #ds>=csか
	td = getvs(len(ds))
	return movv(td,ds) + sub(r,td,cs) #+ "0 0 1 1 %s %s %s %s" % (td[3],td[2],td[1],td[0]) + "\n"

def lls(ds): #論理左シフト
	res = ""
	for i in range(0,len(ds)-1)[::-1]:
		res += mov(ds[i+1],ds[i])
	res += mov(ds[0],'0')
	return res

def andv(ds,a): #ds = map(lambda x: x & a,ds)
	res = ""
	for d in ds:
		res += and_(d,d,a)
	return res

def nibai(dss): #4bitリトルインディアン(10進)のものを各桁ごとに上から2倍していく
	ls = len(dss)
	res = ""
	tp,tq = getvs(2)
	tds = getvs(4)
	for i in range(0,ls-1)[::-1]:
		ds = dss[i]
		res += geq(tp,ds,['1','0','1','0'])
		#res += movv(tds,['0','1','0','1'])
		#res += andv(tds,tp)
		#res += sub(tq,ds,tds)
		res += sub(tq,ds,[tp,'0',tp,'0'])
		res += add(tq,dss[i+1],[tp,'0','0','0'])
		res += lls(ds)
	return res

r = Tk()
r.clipboard_clear()

cnt = ['c' + str(i) for i in xrange(10)]
ans = [['a' + str(i) + ',' + str(j) for j in xrange(4)] for i in xrange(33)]

s = (
	init + 
	movv(cnt,['0'] * 10) + 
	""
)

for ds in ans:
	s += movv(ds,['0'] * 4)

tp = getv()
s += (
	'x' + "\n" + 
	nibai(ans) + 
	'x x x x x x x x b' + "\n" + 
	add(tp,ans[0],['b','0','0','0']) + 
	inc(cnt) + 
	#"0 0 1 1 %s %s %s %s" % (cnt[3],cnt[2],cnt[1],cnt[0]) + "\n" + 
	#geq(tp,cnt,['1','1','0','0']) + 
	#"0 0 1 1 0 0 0 %s" % tp + "\n" + 
	neq('x',cnt,map(chr,map(ord,'0001100100'[::-1]))) + 
	#neq('x',cnt,map(chr,map(ord,'0000000110'[::-1]))) + 
	'x' + "\n" +
	""
)

for ds in ans[::-1]:
	s += ("0 0 1 1 %s %s %s %s" % (ds[3],ds[2],ds[1],ds[0])) + "\n"

print len(s)
r.clipboard_append(s)

ハーフアダーとかフルアダーとかインクリメンタとかアダーとかがあるのでもう論理回路ですね。

おおまかなアルゴリズムとしては、

counter = '0000000000'
loop
ans <- ans * 2
x x x x x x x b
ans <- ans + 1
loop <- counter < '0001100100'
loop
print ans

みたいな感じですかね。
ansを二倍する部分は、そもそも4bitのものを35桁分持ってないといけないので、ループを回すことができず、各桁について、

c <- ans[i] >= '0101'
ans[i+1] += '000c'
ans[i] -= '0c0c'
ans[i] <<= 1

みたいなことを35回書いてどうにかしました。

で、これで解けるのですが、これで出力するとコードの長さが約35万文字になりました。
今回は提出システムを@hakatashiが作ってくれたのですが、システムの都合上1万文字に抑えてくれと言われたので、ここからさらに論理圧縮をしてコード長を1/35にすることになりました。

最終的には、

#coding: utf-8
from Tkinter import Tk


init = """
0 0 0
0 0 0 
1 1 1 
"""

def nand(s,a,b): # s = a nand b
	if s==a: #10242 -> 10162
		return "%s %s\n" % (s,b)
	elif s==b:
		return "%s %s\n" % (s,a)
	return "%s %s %s\n" % (s,a,b)

def one(a): #aに1を代入
	return nand(a,a,'0')

def not_(s,a): #s = !a
	if s==a: #174122 -> 144684
		return "%s %s\n" % (s,'1')
	else:
		return nand(s,a,a)

def zero(a): #aに0を代入
	#return one(a) + not_(a,a)
	return "%s 1 1\n" % a #144684 -> 144098

def and_(s,a,b): # s = a & b
	return nand(s,a,b) + not_(s,s)

def mov(s,a): # s := a
	return and_(s,a,a)

def or_(s,a,b): # s = a | b
	return not_(a,a) + not_(b,b) + nand(s,a,b) 

def xor(s,a,b): # s = a ^ b
	tc,td,te = ('A','B','C')
	if a==s:
		te = s #10162 -> 9798
	return (
		nand(tc,a,b) + 
		nand(td,a,tc) + 
		nand(te,b,tc) + 
		nand(s,td,te) #144098 -> 119922
	)

def inc(ds): #dsで表される配列をインクリメントする。
	tp,tq = ('D','E')
	res = one(tp)
	for s in ds:
		res += and_(tq,tp,s)
		res += xor(s,tp,s)
		res += mov(tp,tq)
	return res

def neq(r,cs,ds): #csとdsを比べた結果をrに格納する。等しいなら0。
	res = zero(r)
	tt = 'F'
	for p,q in zip(cs,ds):
		res += xor(tt,p,q)
		res += or_(r,r,tt)
	return res


def add0or5(a,b,c,r): # cba += r0r をする
	tp,ic,ib = ('G','H','I')
	#return add(tp,[a,b,c],[r,'0',r])
	res = ""
	res += and_(ib,a,r)
	res += and_(ic,ib,b)
	res += xor(ic,ic,r)
	res += xor(c,c,ic)
	res += xor(b,b,ib)
	res += xor(a,a,r)
	return res

def sub5(r,a,b,c,d): # dcba -= 0101 をする。で、rに、dcba += 1011の繰り上がりの結果が入る
	
	ib,ic,id,ir = ('J','K','L','M') #38372 -> 15662
	res = ""
	res += not_(a,a)
	res += not_(ic,b)
	res += nand(ic,ic,a)
	res += nand(id,ic,c)
	res += not_(d,d)
	res += nand(ir,id,d) # 10498 -> 10242
	res += xor(b,b,a)
	res += xor(c,c,ic)
	res += xor(d,d,id)
	res += not_(r,ir)
	return res

def mo5sub5(r,ds): 
	#if ds>=5 then {ds -= 5; r=1;} else {r=0;}
	tq = 'N'
	res = ""

	res += sub5(r,ds[0],ds[1],ds[2],ds[3])
	res += add0or5(ds[0],ds[1],ds[2],r)
	
	#res += zero(ds[3]) #シフトするので不要。 11935 -> 11711
	return res

def lls(ds): #論理左シフト

	res = ""
	for i in range(0,len(ds)-1)[::-1]:
		res += mov(ds[i+1],ds[i]) 
	return res


def nibai(dss): #4bitリトルインディアン(10進)のものを各桁ごとに上から2倍していく
	ls = len(dss)
	res = ""
	tp,tq = ('O','P')
	for i in range(0,ls-1)[::-1]:
		ds = dss[i]
		res += mo5sub5(tp,ds)
		
		res += not_(dss[i+1][0],tp) #119922 -> 90322
		#print ds,
		res += lls(ds)
		#print ds
	return res

#変数名をAからRまで割り振ることにより、
#14807 -> 11935

var_num = 0
def getv():
	global var_num
	var_num += 1
	res = ""
	nv = var_num
	d = 127-33
	ok = True
	while nv>0:
		nc = nv%d+33
		res += chr(nc)
		nv /= d
	if len(res)<=1:
		c = res[0]
		if c=='0' or c=='1' or c=='?' or (ord('A') <= ord(c) and ord(c) <= ord('R')):
			#11511 -> 10704
			return getv()
	
	return res

def getvs(x):
	if x==1:
		return getv()
	else:
		return [getv() for i in xrange(x)]


r = Tk()
r.clipboard_clear()

import sys

ketan = 33
if len(sys.argv)>=2:
	ketan = 3

ans = [[getv() for j in xrange(4)] for i in xrange(ketan)]
cnt = [getv() for i in xrange(7)] #38372 -> 38030

s = (
	init + 
	""
)

s += (
	'Q' + "\n" + 
	nibai(ans) + 
	'Q Q Q Q Q Q Q Q R' + "\n" + 
	mov(ans[0][0],'R') + #15662 -> 14807
	inc(cnt) + 
	neq('Q',cnt,map(chr,map(ord,'1100100'[::-1]))) + 
	'Q' + "\n" +
	""
)

for ds in ans[::-1]:
	s += ("0 0 1 1 %s %s %s %s" % (ds[3],ds[2],ds[1],ds[0])) + "\n"

print len(s)
r.clipboard_append(s)

となりました。
改善点としては、

  • 出来る限り1文字変数名が多く使われるようにする
  • 加算、減算の数値がほぼ一定(0か5)なのでアダーを使わず回路を直に書き込む
  • nandやxorなどで同じ記号を使っているならその分短く書くことができる

とかですかね。論理圧縮すると回路ががりがり縮んでいきました。
最終的に、9798文字になったので、晴れてACを貰うことができました。

感想

BFやBefungeやWhiteSpaceのいかに書きやすいことか!!