Subscribed unsubscribe Subscribe Subscribe

Perl6での6記号プログラムの作りかた

先日、

の2つの記事でPerl6の記号プログラムを紹介したけど、その作り方については何も言及していなかったので ちゃんと書いておこうと思います。

おさらい: Perl5における記号プログラムの基礎

Perl5における記号プログラミングの手法は古くから確立されていて、 記号だけのPerlプログラミングの基本原理 - JPerl Advent Calendar 2010 Sym Track の記事にも全貌が載っていますが、要するに「任意のプログラム文字列を排他的論理和(XOR)を使って生成し、それを拡張正規表現を利用してevalする」という方法です。

   01100000  => 0x60 ('`')
^) 00100001  => 0x21 ('!')
-----------
   01000001  => 0x41 ('A')

このように2つの文字のASCIIコードのXOR演算によって別の文字を生成できるので、記号文字同士のXOR演算でアルファベットや数字を生成することができ、最終的に実行したいプログラムなど 任意の文字列をすべて記号だけで表現することができます。

で、その生成した文字列を実際に実行するための手段として拡張正規表現(?{ code })という記法があります。

'' =~ /(?{ print "Hello" })/;

のようにして書くと (?{ ... })内のコードが実行され"Hello"が出力されます。これを

'' =~ '(?{ print "Hello" })';

と書くこともでき、つまり記号だけでこの右辺の文字列を生成すれば、任意のプログラムを実行することができる、という仕組みです。


記号プログラムでアスキーアートを作れる Acme::EyeDrops というCPANモジュールでも、この手法が使われています。
ただし、Perl 5.18以降では拡張正規表現の使用に制限ができており、use re 'eval'プラグマを宣言しないと実行できなくなっています。とても残念です。


Perl6での記号プログラム実現方法

で、Perl6ではこれはどうなるか、というと 1.「排他的論理和で任意の文字列を生成する」に関してはPerl5と同様に出来ました。ただし演算子が変わっておりPerl5でのXOR演算子^は one Junction を生成する演算子となっています。

http://docs.perl6.org/language/operators#infix_%5E

で、上記ドキュメントには明記されていないけど どうやら文字列の排他的論理和~^という演算子で実現できるようでした。
こっちには書いてありますね。

http://design.perl6.org/S03.html#Symbolic_unary_precedence

ちなみに~^""で文字列のビット反転が取れるらしいですが、実際に使ってみるとprefix:<~^> NYIとエラーを吐いて死にます。Not Implemented Yet!!


そして 2.「拡張正規表現によるeval」について、こちらは正規表現の書き方・仕組みが大きく変わっている影響で使えなくなっているようでした。

'' ~~ /{ say "Hello" }/

のような書き方でblock内のコード実行は出来るけれど、文字列に置き換えることは出来ないようで。


で、別の手段を使う必要がある… ということで某soozyというSlackグループで尋ねたところ、以下の方法を教えていただきました。

::('&EVAL')('say q{Hello}');

::というのがグローバルのstash的なもの?で、ここに対して文字列でシンボルを参照できる仕組みがあるようで。"dynamic symbol lookup" というsyntaxだそうです。

http://doc.perl6.org/language/5to6#%26_Sub

これを使うことで文字列からPerl6の"EVAL"関数を呼び出すことができ、ここに任意のプログラム文字列を渡すことでeval実行することができます。
なので、"&EVAL"とプログラム文字列を記号から生成することができれば任意のプログラムを記号だけで表現できる、ということになります。

こうして作られたのが1つめの記事で書いた記号Hello worldになります。

::('!{.(?'~^'.~!)~'~^')^.^^'~^'?!^?('~^'??)!{')('!?}}~~(!^~{~))(.{~('~^'))?^?.).(?.}?)().!~'~^'~!.?}?~.^.{?!)~}!).'~^'}!!.~(}(!?}~{!}).(('~^')^(^.(.)~?!.()!})?)')

前半の::('!{.(?'~^'.~!)~'~^')^.^^'~^'?!^?('~^'??)!{')の部分が::('&EVAL')を表していて、後半の('!?}}~~(!^~{~))(.{~('~^'))?^?.).(?.}?)().!~'~^'~!.?}?~.^.{?!)~}!).'~^'}!!.~(}(!?}~{!}).(('~^')^(^.(.)~?!.()!})?)')部分が"Hello, world!".sayというコード本文になっています。分かりやすいですね。

6つの記号に制限する

さて、任意の記号プログラムが作れることが分かったので、あとは使う記号の種類を減らすことを考えます。Perl5の場合は、' = ~ ( ) ^ .と最低限必要な7種類の記号だけを使って実現できていました。

Perl6においては、前述の通り記号プログラミングに最低限必要なのは: ' ( ) ~ ^の6種類だけとなります。この6種類の記号の組み合わせで任意の文字列を生成することができれば、6種類の記号だけで任意のプログラムを記号だけで書けるわけですが…

use v6;

my @chars = <: ( ) ~ ^>;
my %dict;
for @chars -> $c1 {
    %dict.push: $c1 => ($c1);
    for @chars -> $c2 {
        %dict.push: $c1~^$c2 => ($c1, $c2);
        for @chars -> $c3 {
            %dict.push: $c1~^$c2~^$c3 => ($c1, $c2, $c3);
            for @chars -> $c4 {
                %dict.push: $c1~^$c2~^$c3~^$c4 => ($c1, $c2, $c3, $c4);
                for @chars -> $c5 {
                    %dict.push: $c1~^$c2~^$c3~^$c4~^$c5 => ($c1, $c2, $c3, $c4, $c5);
                }
            }
        }
    }
}

for %dict.keys.sort({ .ord }) -> $c {
    next unless %dict{$c}:exists;

    '\x%02X %s => %s'.sprintf(
        $c.ord,
        $c ~~ /<[\x20 .. \x7E]>/ ?? qq{"$c"} !! '(?)',
        %dict{$c}.pick.sort({ .ord }).join(' ')
    ).say
}
say %dict.keys.elems;

のように試してみると、

\x00 (?) => ) ) ~ ~
\x01 (?) => ( ) ) )
\x08 (?) => ( ( ( ^ ~
\x09 (?) => ) : : ^ ~
\x12 (?) => ( :
\x13 (?) => ( ( ) :
\x1A (?) => ) ) : ^ ~
\x1B (?) => ( ) : ^ ~
\x20 " " => ) ) ^ ~
\x21 "!" => ( ) ^ ~
\x28 "(" => ( : : : :
\x29 ")" => ) ) ) : :
\x32 "2" => ( : ^ ~
\x33 "3" => ) : ^ ~
\x3A ":" => ( ( ) ) :
\x3B ";" => ( ) : ~ ~
\x44 "D" => ( ( : ~
\x45 "E" => ( ) : ~
\x4C "L" => ( ) ) : ^
\x4D "M" => ) : ^ ~ ~
\x56 "V" => ( ~
\x57 "W" => ( ( ) ~
\x5E "^" => ) ) : : ^
\x5F "_" => ( ) ) ) ^
\x64 "d" => : ^ ~ ~
\x65 "e" => ( ) : ^
\x6C "l" => ( : : : ~
\x6D "m" => ( ( ) : ~
\x76 "v" => ( ) ) ^
\x77 "w" => ) ^ ~ ~
\x7E "~" => ) ) : : ~
\x7F (?) => ( ) : : ~
32

と32種類の文字しか生成できません。これでは'&EVAL'を作ることもできない… ので、使う記号種類は6のままで別の文字列を作る方法を模索するしかありません。

で、前述のperl5での7記号プログラミングに似た手法で"0"を作ります。それが~(^(''~~''))です。これは、'' ~~ ''正規表現マッチでTrueを生成し、そこにRangeを作るprefix operator^を適用させて0..^1というRangeを作り、それを文字列として評価することで"0"を作る、ということになります。

dd (''~~'');     #=> Bool $var = Bool::True
dd ^(''~~'');    #=> Range $var = 0..^1
dd ~(^(''~~'')); #=> Str $var = "0"
dd ~(^2);        #=> Str $var = "0 1"
dd ~(^3);        #=> Str $var = "0 1 2"

Rangeの文字列表現はスペースでの連結になるようなので、「0からTrue(つまり1)までのRange」の文字列表現として"0"が生まれるようです。ちなみにPerl6ではPerl5と違ってTrue(真値)の文字列表現は"True"になるので、ここから"1"を作るようなことはできません。数値コンテキストとして評価する+演算子を使って~(+(''~~''))のようにしないと"1"が作れません。ここでは"+"を使うことができないので、つらい。

さて、"0"を作れることは分かったので それを使える前提として改めて何種類の文字を記号から生成できるか、を見てみると…

\x00 (?) => ( ( 0 0 : :
\x01 (?) => ( ) ^ ^ ~ ~
\x02 (?) => ( 0 : ^ ~
\x03 (?) => ) 0 : ^ ~
\x08 (?) => ( 0 0 ^ ~
\x09 (?) => ) 0 0 ^ ~
\x0A (?) => 0 : ^ ^ ~ ~
\x0B (?) => ( ) 0 : ^ ^
\x10 (?) => 0 : : ^ ~
\x11 (?) => ( ) 0 ^ ~
\x12 (?) => ( ) ) : ~ ~
\x13 (?) => ) ) ) : ^ ^
\x18 (?) => ( ) ) 0 ^ ^
\x19 (?) => ) 0 0 0 ^ ^
\x1A (?) => : ^ ~ ~ ~
\x1B (?) => ( ) : ^ ~
\x20 " " => ) ) : : ^ ~
\x21 "!" => ( ) : : ^ ~
\x22 """ => ( 0 : ^ ^
\x23 "#" => ( ( ) 0 :
\x28 "(" => ( 0 0 ~ ~
\x29 ")" => ) 0 0 ~ ~
\x2A "*" => 0 : ^ ~ ~ ~
\x2B "+" => ( ) 0 : ^ ~
\x30 "0" => ( ( 0 ~ ~
\x31 "1" => ( ) 0
\x32 "2" => ( : : : ^ ~
\x33 "3" => ) 0 0 : ^ ~
\x38 "8" => ( 0 : : ^ ~
\x39 "9" => ( ( ) 0 ^ ~
\x3A ":" => 0 0 : ~ ~
\x3B ";" => ( ) 0 0 :
\x44 "D" => ( ( : : : ~
\x45 "E" => ( ) 0 0 : ~
\x46 "F" => ( 0 ^ ~ ~
\x47 "G" => ( ( ) 0 ^
\x4C "L" => ( ( ( : ^
\x4D "M" => ( ( ) : ^
\x4E "N" => 0 0 0 ^ ^ ~
\x4F "O" => ( ) 0 ~ ~ ~
\x54 "T" => ) ) 0 : ^
\x55 "U" => ( ) 0 : ^
\x56 "V" => ( 0 0 : : ~
\x57 "W" => ) ) ) ^ ^ ~
\x5C "\" => ( ) ) 0 : ~
\x5D "]" => ) 0 0 0 : ~
\x5E "^" => ) ) 0 0 ^
\x5F "_" => ( ) ) ) ^
\x64 "d" => 0 0 : ^ ~ ~
\x65 "e" => ( ) : ^ ~ ~
\x66 "f" => ( 0 : : ~
\x67 "g" => ) 0 ~ ~ ~
\x6C "l" => ( 0 0 : ~
\x6D "m" => ) 0 0 : ~
\x6E "n" => 0 : : ^ ^ ^
\x6F "o" => ( ) 0 0 0 ^
\x74 "t" => 0 : : : ~
\x75 "u" => ( ) 0 : ~
\x76 "v" => ( 0 0 : : ^
\x77 "w" => ( ( ) 0 0 ^
\x7C "|" => ( 0 : : : ^
\x7D "}" => ( ( ) 0 : ^
\x7E "~" => ^ ^ ~ ~ ~
\x7F (?) => ( ) ^ ^ ~
64

と、64種類まで増やせました、がこれでもまだ"A"を作ることもできない…。ここに出てこない文字をさらにどうにかして作り出す必要があります。数値コンテキストとして評価する演算子が使えないので"1", "2", "3"が使えてもそこから"4", "5", "6", "7"を作ることもできなくて、つらい。

「"4"」

ここで思い出すのが::('&EVAL')でdynamicにsymbolを参照する方法。'&EVAL'は呼べなくても他のものなら呼べるのでは…!と。なんと偶然にも、"Mu", "Num", "VM"などの文字は先ほどまでの方法で作れます。ということで編み出したのが

~(::('Num')('1*2**2'))

という方法。::('Num')でNumクラスを参照、これはそのままコンストラクタを呼ぶような形で利用できるので、括弧で文字列を渡して数値を生成することができます。ただしどんな文字列でも受け付けられるわけではなく.Numで数値としてparseできるような文字列でなければならなりません。単純な足し算や掛け算の式はダメ。
しかしどうやらexponentials(指数)を使う表現として特殊な記法が用意されているようです。

http://design.perl6.org/S02.html#Exponentials

所謂 6.02\times10^{23} のような形式を表すために"6.02*10**23"という形式の文字列はサポートされているらしい。"1", "2", "*"の文字はここまでで生成できているので、これを利用して、"1*2**2"という文字列から"4"を作り出すことができる!!


ということで"4"を使うことができるようになると、無事に"\x00"から"\x7F"までのASCIIコードをすべて表現することができるようになります。
あとは"\x80"より上の範囲、マルチバイト文字列が含まれる場合を考慮する必要がありますが、これはすべて"\x3042"のような形で表現するよう変換してしまえばすべてASCII範囲内で収まるので問題ありませんね。

これで任意のプログラムを6種類の記号だけを使った等価なプログラムに変換することができそうです。やったー!!

作ったもの

というわで、この方法で任意のコードを6種類の記号プログラムに変換するモジュールを作っておきました。ご自由にお使いください。