Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2015-01-01

あけましておめでとうございます 2015

あけましておめでとうございます。日本のプログラマには古来より「正月はフラクタル」という習わしがあります。正月はフラクタルに触れて心穏やかに過ごそうというものです。

今年は L-system で遊んでみました。以下でススキっぽいのが描けます。

$ ruby 2015-fractal.rb 7 20 X X:A-[[X]+X]+A[+AX]-X A:AA

出力には Sixel を使ってみました。mltermで動作確認。

コッホ曲線

$ ruby 2015-fractal.rb 4 90 A A:A+A-A-A+A

ドラゴン曲線。

$ ruby 2015-fractal.rb 16 90 AX X:X+YA+ Y:-AX-Y

C 曲線。

$ ruby 2015-fractal.rb 13 45 A A:+A--A+

ヒルベルト曲線。

$ ruby 2015-fractal.rb 6 90 X X:-YA+XAX+AY- Y:+XA-YAY-AX+ A:A
$ ruby 2015-fractal.rb 4 90 X X:XAYAX+A+YAXAY-A-XAYAX Y:YAXAY-A-XAYAX+A+YAXAY A:A

シェルピンスキーのギャスケット。

$ ruby 2015-fractal.rb 9 60 X X:YA-XA-YA Y:XA+YA+XA A:

ペンローズ・タイル

$ ruby 2015-fractal.rb 4 36 [N]++[N]++[N]++[N]++[N] M:OA++PA----NA[-OA----MA]++ N:+OA--PA[---MA--NA]+ O:-MA++NA[+++OA++PA]- P:--OA++++MA[+PA++++NA]--NA A:

Sixel 初めて使ってみましたが、簡単でいいですね。何か作りたくなった。

# 2015-fractal.rb

# read L-system definition
if ARGV.size < 4
  puts "usage: ruby #$0 <iteration> <angle> <init> <rules...>"
  exit 1
end
Iteration = ARGV.shift.to_i
Angle     = ARGV.shift.to_i
Init      = ARGV.shift
Rules = {}
ARGV.each do |s|
  pre, post = *s.split(":",2)
  Rules[pre] = post
end

# generate a program by L-system
s = Init
Iteration.times { s = s.gsub(/\w/) {|c| Rules[c] } }
s = s.gsub(/[B-Z]/, "")

# run the generated program
mod = 180 / Angle
lines  = {}     # drawn lines
pos = [0] * mod # current position (represented by polynomial)
dir = 0         # current angle
stack = []
s.each_char do |c|
  case c
  when ?A
    npos = pos.dup
    npos[dir % mod] += dir < mod ? 1 : -1
    line = [pos, npos].sort
    lines[line] = true if !lines[line]
    pos = npos
  when ?+ then dir = (dir + 1) % (mod * 2)
  when ?- then dir = (dir - 1) % (mod * 2)
  when ?[ then stack << [pos, dir]
  when ?] then pos, dir = *stack.pop
  end
end

# translate polynomials to the actual point
lines = lines.keys.map do |line|
  line.map do |point|
    point.map.with_index do |mag, i|
      Complex.polar(mag, Math::PI * Angle * i / 180)
    end.inject(&:+)
  end
end

# render it to the buffer
S = 450
l, r = lines.flatten.map {|p| p.real }.minmax
u, d = lines.flatten.map {|p| p.imag }.minmax
scale = S / 1.1 / [r - l, d - u].max
translate = Complex(r + l, d + u) / 2
fine = [(scale / 3).round, 4].max
image = (0 ... S / 6).map { [0] * S }
lines.each do |p1, p2|
  fine.times do |i|
    p = ((p1 * i + p2 * (fine - i)) / fine - translate) * scale
    x = (S / 2 + p.real).round
    y = (S / 2 + p.imag).round
    image[y / 6][x] |= 1 << (y % 6)
  end
end

# output the buffer as Sixel
r = (100 * rand).round
g = (100 * rand).round
b = (100 * rand).round
print "\eP0;0;0;q#0;2;0;0;0#1;2;#{ r };#{ g };#{ b }#1"
image.each do |line|
  print line.map {|c| (c + 0x3f).chr }.join + "-"
end
print "\e\\"

2014-12-29

CRC32 Quine を Z3 で解く

ref: http://shinh.hatenablog.com/entry/2014/12/25/013926

おー。

Z3 で再現してみた。

$ time python crc32.py 
86319a79    
58a8a1b9

real    151m1.375s
user    151m7.607s
sys     0m0.179s

1 つめは 3 分くらいで見つかるけど、2 つめは 2 時間くらい、チェック完了までは 3 時間弱かかった。

単純に 2^32 個を全チェックする方法なら、秒間 100 万個調べられるとして 1 時間ちょっとという計算。まあ、こんなもんなのかな。追記:shinh さんによると 1 分でできるらしい。残念。

ソースはこんな感じ。もっと綺麗に書けそう。

# coding: utf-8
from z3 import *

# CRC-32 の生成多項式(の反転)
POLY = 0xedb88320 * 2 + 1

# BitVec(1) の 0
ZERO = BitVecVal(0, 1)

# 求めたい CRC-32
answer_crc32 = BitVec("answer", 32)

# answer_crc32 をテキスト化する
text_crc32 = []
for i in range(8):
    d = ZeroExt(4, Extract(31 - i * 4, 28 - i * 4, answer_crc32))
    d = If(d < 10, d + 48, d - 10 + 97) # [0-9a-f] の ASCII コードに変換する
    text_crc32.append(d)
text_crc32.append(10) # 最後の改行
# テキスト化をしない場合はこっち
# for i in range(4):
#    d = Extract(31 - i * 8, 24 - i * 8, answer_crc32)
#    text_crc32.append(d)

# テキスト化したものの CRC-32 を求める
crc32 = BitVecVal(0xffffffff, 32)
for d in text_crc32:
    n = ZeroExt(32, Extract(7, 0, crc32) ^ d)
    for i in range(8):
        n = If(Extract(i, i, n) == ZERO, n, (POLY << i) ^ n)
    crc32 = Extract(39, 8, n) ^ ZeroExt(8, Extract(31, 8, crc32))
calculated_crc32 = ~crc32

# 元の CRC-32 と求めた CRC-32 が一致するケースを全列挙する
s = Solver()
s.add(calculated_crc32 == answer_crc32)
while s.check() == sat:
    found_crc32 = s.model()[answer_crc32].as_long()
    print("%08x" % found_crc32)
    s.add(answer_crc32 != found_crc32)

他のソルバでもやってみたかったけど、Z3 でも 3 時間かかるんじゃ無理かな。

追記:

テキスト化しない場合は 30 秒。これなら他のソルバとベンチマークできそうですね。

$ time python crc32.py 
cc4fbb6a
ffffffff

real    0m29.339s
user    0m29.327s
sys     0m0.032s

2014-12-25

100 言語版 Quine リレー

(この記事は Quine Advent calendar 2014 の 25 日目です)

以下は、自分自身を出力する REXX プログラムを出力する Ratfor プログラムを出力する R プログラムを出力する (...略...) を出力する Scala プログラムを出力する Ruby プログラムです。合計 100 言語を使います。

コピペしたい人はリンク先を辿ってください。

解説

昨年公開した 50 言語版 Quine リレーのパワーアップ版です。Quine-relay Advent calendar として、2014/11/05 から 50 日間、1 言語ずつ加えて行った成果物です。

将来の参照用に、1 記事としてまとめておきました。あと Quine Advent calendar 2014 の記事のためにも。(こんな手抜き記事がトリになってごめんなさい!)

次の記事でだらだらと Quine-relay Advent calendar 反省会を書きます。本当にだらだらなので、読まなくていいです。

Quine-relay Advent calendar 反省会

企画について

当初は「1 日 1 言語を紹介しながら追加していく」という企画を目論んでいました。しかし Quine リレーに追加する過程では、Hello, world 程度の知識(+重箱の隅をつつくような知識)しか身につかないので、紹介できるほどのネタはなく、淡々と追加報告していくだけという結果になりました。企画倒れ。

まあ、100 言語版を一気に作るのはモチベーションの点で難しかった気がするので、1 日 1 言語ずつ地道に進められたのは良かったのかもしれない。

難しさについて

50 言語版 Quine リレースポイラーでも書きましたが、Quine リレーに言語を追加するのは実務的には簡単で、パッケージ名やビルド方法やコード断片を書いたクラスを 1 つ定義するだけです(わかりやすい例:haXe)。というか、そうなるように基底クラスやコード生成コアを書いてます。

ただ、言語間に暗黙的な依存関係が数多くあって、実際に追加してみるといろいろはまります。例えば今の Shell や Verilogプログラムではバックティックを出力できない*1ので、それより先のプログラムでバックティックを使ったらいけないとか。コードが大きくなると Java の圧縮展開アルゴリズムバッファサイズを広げないといけないとか。他にも思い出せない制約やノウハウがいろいろあったはずです。

そのうち整理しないとなあ、とずっと思ってましたが、目標地点まで到達してしまったのでやらない。そして後のメンテの時に泣くのでしょう。

Travis CI について

Quine リレーの動作デモとして、Travis CI を利用してみました。100 言語動いた様子

Travis CIUbuntu のバージョンが 12.04 LTS と古いですが、適当に PPA を入れることで対処しています。メモリ不足でプロセスが死ぬ問題にも悩まされましたが、数回に一度はパスするので、リトライを繰り返すことで強引に解決しました。

Travis CI中の人@hiro_asari さんなど)には、いろいろ情報頂いたり、デバッグ用の一時 VM を提供頂いたり、支援いただきました。ありがとうございました。

まあ、Travis CI は 100 のプログラミング言語の対応実績がある、と唄えばいいでしょう。(なぜか上から目線

(そういえば Dockerfile も作りたいなあと思ってましたがやらなかったなあ。)

追加を断念した言語たち

最後に、追加しなかった・できなかった言語たちを並べて追悼しておきます。なお、言語の選定基準はマイナス 25 日目に書いてあります。

QCL

量子計算のためのプログラミング言語。今の Quine リレーには A から Z のうち Q で始まる言語だけが欠けているので、それが埋まるという意味でも、さらに量子計算というネタ的にも、ぜひ入れたい言語でした。しかし、出力の先頭に ": " というプロンプトが強制的につくという致命的な仕様があり、直後の R でどうやっても構文エラーになるので、導入を断念しました。

Qalb

アラビア語で記述するプログラミング言語。これも、ネタ的にも Q 的にも大変魅力的だったのですが、ブラウザで動く処理系しかないっぽいのが致命的で断念しました。

QuakeC

Quake というゲームを拡張するための言語らしい。これはなんと Ubuntu にパッケージがあるようです (fteqcc) 。しかし、「progs.src という名前のファイルを含んだディレクトリ」をソースコードとみなす仕様らしいのがどうしても気に入らず、導入しませんでした。

Agda

依存型関数プログラミング言語。主に定理証明で使われます。Hello, world も書けるらしいのですが、ubuntu の Agda パッケージは ffi が含まれていない?のか、とにかくコンパイルできないので断念しました。

malbolge

最凶と名高い難解プログラミング言語shinh さんが頑張って頑張って Hello, world を 70 バイト強を達成するという感じの言語です。

Quine リレーに追加することは、まあ考えるまでもなく無理なんですが、プログラムサイズ上限が 3^10 = 59049 バイト(しかも 1 バイトには 8 種類の文字しか書けない) ので 177147 ビットの情報しか持てません。一方で Malbolge 直後の Maxima のソースサイズが約 25kB つまり約 200000 ビットの情報を持たせなければならないので、原理的に書けません。え、圧縮?

Oz (Mozart)

よく知りませんが、昔はしばしば名前を聞いたプログラミング言語です。論理型が入ってるようなやつ。Ubuntu にパッケージがあるのですが、依存している Emacs パッケージのせいで (?) インストールできないので断念。

Shakespeare

有名な難解プログラミング言語シェイクスピアの脚本風にプログラムを書きます。

Quine リレーに追加することは別に難しくはないと思いますが、プログラムサイズがかなりでかくなるので、やめておきました。

Chuck

音楽関係のプログラミング言語Ubuntu にパッケージあるし入れたかったのですが、標準出力の stdout/chout が一時的に止められているということで断念。

Z80

ネタ的に入れたかったですが、標準的な入出力プロトコルがない(当たり前だけど)ので断念。

日本語プログラミング言語

G-Portugol の時にも書きましたが、ほとんどの日本語プログラミング言語Windows オンリーなようで、たいへん遺憾です。Mind だけは Unix 版がありましたが、Debian/Ubuntu パッケージにはなってないようなので断念。

Ezhil

タミル語で記述するプログラミング言語。見た目がたまりません。ただ、やっぱり Ubuntu パッケージがないので追加しませんでした*2。わりとアクティブに開発されてる気がするので、そのうちパッケージ化されないかな。

Aribas, Goo, Inform, Euler

この辺は Ubuntu にパッケージがあるのですが、何らかの理由で断念したやつらです。バナーが消せないとか、出力が勝手に整形されるとか、GUI が立ち上がってユーザの操作を待ち受けてしまうとか、そんなんだったと思います。*3

Rust, Fantom, Factor, Nemerle, Swift, Elixir, Dart, Concurrent Clean, Eupohria, Fortress, IO, Dylan, Self

この辺は Ubuntu にパッケージがないので断念。まともなプログラミング言語を名乗るなら、Ubuntu で標準的に入れられるようにしてほしい!

*1:Shell の方は普通にエスケープすればいいんだけど、Verilog ではバックティックはマクロ展開の記号で、どうもエスケープのやり方がわからなかった。

*2バンドルするのは原則として esolang 限定。

*3:ちゃんと覚えてない。

2014-12-24

Quine-relay Advent calendar Day 24: Lazy K

ref: https://github.com/mame/quine-relay

24 日目の今日は、Lazy K を追加しました (コミット) 。100 言語達成! ロゴも新しくなりました。(@hirekoke さんありがとう)

Lazy K は、純粋関数型の難解プログラミング言語です。SKI コンビネータを直接書く系。

Lazy K は入出力をラムダ式エンコードする必要があるので、短いプログラムで長大な文字列を出力するというのはなかなか面倒です。既存研究がありそうな気もしましたが、調べるより自分で考える方が楽しそうだったので考えました。表示すべきバイト列をビット列とみなして、各ビットを k と i で表現することにしました。このビット b を、(b i inc (dbl num)) というように適用すると、b が k だったら (dbl num) に、b が i だったら (inc (dbl num)) になります。これを繰り返せば二進数的に数字を作れます。7 ビットを 1 文字として出力してます。

ただ、単純に ``````<main><k と i の列> みたいなプログラムにするとインタプリタが segfault してしまったので、やや冗長になりますがバイト単位で区切って適用するような感じのコードにしています。

以上のエンコードを、Kaya で行ってます。思ったより短くきれいにかけて、Kaya いいなーと思った。


ということで、Merry Quine-mas!


Quine-relay Advent calendar はこれで終わりですが、明日、一人反省会の記事を載せる予定です。それは Quine Advent Calendar 2014 の 25 日目の記事を兼ねる予定。さらに「重大発表(笑)」もある予定。

2014-12-23

Quine-relay Advent calendar Day 23: Lisaac

ref: https://github.com/mame/quine-relay

23 日目の今日は、Lisaac を追加しました (99 言語目、コミット) 。正直まったく知らない言語です。Wikipedia によると、静的型付きプロトタイプベース言語で、Self や Eiffel の影響を受けているそうです。Isaac とかいう OS を書くのに使われてるそうですが、こっちもも知りません。

Quine リレーに組み込むのは、1 行に 256 文字以上書くとエラーになる他は特に問題なし。前段の Kaya が切り分けます。

ただ、言語の問題以外で、コンパイラが結構なメモリを要求するみたいです。Travis CI で動くかどうか不安。(よくわからないんだけど、内部的に gcc を起動する際、clone で ENOMEM になる現象がよく見られる)

明日はついに 100 言語目です。Lisaac がうまく動けばですが。