不思議なPerlリテラル
ちょっとパーサの実装の参考にするためにPerlの数値リテラルについて調べていたのですが、手元のPerl5.8.3では「1.1.1」のような式を正しく解析できないようです。
予想では「1.1.1」は数値「1.1」と文字列結合演算子「.」と数値「1」と解釈され、「1.1」と「1」を文字列結合した文字列「1.11」になると思っていたんですが、実際に試してみると、なかなか不思議なことになりました。
my $i = 1.1.1; print sprintf("string:'%s' number:'%d' length:%d\n", $i, $i, (length $i)); print join(',', unpack("C*", $i));
最新版のPerlでは修正されてるかもしれませんが、上記のコードはsyntax errorにはならず、手元の環境では謎の値を生成してしまいました。
string:'' number:'0' length:3 1:1:1
処理系のバグでしょうか?
そうでないなら、単に私の知らないリテラル記法があるんでしょうか。
ちなみにPerlのBNFは公開されてないようですが、Perl処理系のtoke.c内にあるscan_num関数のコメントには以下のような記述がありました。
Read a number in any of the formats that Perl accepts: \d(_?\d)*(\.(\d(_?\d)*)?)?[Ee][\+\-]?(\d(_?\d)*) 12 12.34 12. \.\d(_?\d)*[Ee][\+\-]?(\d(_?\d)*) .34 0b[01](_?[01])* 0[0-7](_?[0-7])* 0x[0-9A-Fa-f](_?[0-9A-Fa-f])*
メタプログラミング
先日書いたC++のコードをコンパイルした場合、結果を静的に保持してるかどうかの検証です。
手っ取り早くobjdmpで見てみましょう。
ちなみに今回利用したコンパイラはgcc3.3.3のg++です。
値が3の場合(結果は8)
以下はmain関数の抜粋です。
08048684: 8048684: 55 push %ebp 8048685: 89 e5 mov %esp,%ebp 8048687: 83 ec 08 sub $0x8,%esp 804868a: 83 e4 f0 and $0xfffffff0,%esp 804868d: b8 00 00 00 00 mov $0x0,%eax 8048692: 29 c4 sub %eax,%esp 8048694: 83 ec 08 sub $0x8,%esp 8048697: 68 a4 85 04 08 push $0x80485a4 804869c: 83 ec 0c sub $0xc,%esp 804869f: 6a 08 push $0x8 80486a1: 68 f0 99 04 08 push $0x80499f0 80486a6: e8 09 ff ff ff call 80485b4 <_ZNSolsEi@plt> 80486ab: 83 c4 14 add $0x14,%esp 80486ae: 50 push %eax 80486af: e8 a0 fe ff ff call 8048554 <_ZNSolsEPFRSoS_E@plt> 80486b4: 83 c4 10 add $0x10,%esp 80486b7: b8 00 00 00 00 mov $0x0,%eax 80486bc: c9 leave 80486bd: c3 ret
以下の行に注目してください。
804869f: 6a 08 push $0x8
値が4の場合(結果は3)
値を4にした場合、以下のように変化しました。
804869f: 6a 03 push $0x3
どうやら、ちゃんと定数として結果を保持しているようです。
続・Collatz予想
C++の特殊化されたtemplateは、KL1等のGHC(Guard Horn Clause)に基づく言語の条件付clauseに似ています。
(特殊化してない場合はguardが常にtrueのclauseでしょうか)
試しに先日のCollatz予想のステップ数を求めるtemplateを、だいたい同じような形でKL1に対応させたコードを書いてみました。
どうでしょう、templateが特殊化によって、異なるguardを持つclauseのように振舞ってるように見えませんか?
(templateの特殊化はguardほど柔軟ではありませんが)
C++
#includetemplate struct f2{ enum{value = 0}; }; /* even */ template struct f2<0, n>{ enum{value = 1 + f2<(n / 2) % 2, n / 2>::value}; }; /* odd */ template struct f2<1, n>{ enum{value = 1 + f2<(n * 3 + 1) % 2, n * 3 + 1>::value}; }; template <> struct f2<1, 1>{ enum{value = 1}; }; template struct f{ enum{value = f2 ::value}; }; int main(){ std::cout << f<3>::value << std::endl; return 0; }
KL1
:- module main. main :- f(3, Step), io:outstream([print(Step),nl]) . f(In, Out):- true | f2(In, 0, Out). f2(In, Count, Out):- In = 1 | Out := Count + 1. f2(In, Count, Out):- In mod 2 =:= 0 | Temp := In / 2, NewCount := Count + 1, f2(Temp, NewCount, Out). f2(In, Count, Out):- In > 1, In mod 2 =:= 1 | Temp := In * 3 + 1, NewCount := Count + 1, f2(Temp, NewCount, Out).
KL1の処理系はklicを想定しています。
というか、それ以外の処理系は私の手元にありません。
第5世代コンピュータプロジェクトの初期の頃は、他の処理系も開発されていたようですが、現在でも手に入るんでしょうか?
Collatz予想
キミならどう書く 2.0 - ROUND 2 -
http://ll.jus.or.jp/2006/blog/doukaku2
Collatz予想のステップ数を求めるコードを書こうかと思いましたが、私の気になる言語Scheme, Io, Ocamlは既に先を越されているようで無念至極、諦めかけたところC++で記述してる例を見かけました。
C++はLLではないとの見方が優勢なのだと思っていましたが、特に誰も気にしてないようなので、私もこっそりC++で書いてみることにします。
(ロクにC++使ったことも無いくせに・・・)
ただし、こちらは以下のルールを勝手に設けてみました。
要するにtemplateで解を得ましょうという話です。
まず、ステップ数の計算は以下のようなtemplate展開から求められます
#includetemplate struct _f{ enum{value = 0}; }; /* even */ template struct _f<0, n>{ enum{value = 1 + _f<(n / 2) % 2, n / 2>::value}; }; /* odd */ template struct _f<1, n>{ enum{value = 1 + _f<(n * 3 + 1) % 2, n * 3 + 1>::value}; }; template <> struct _f<1, 1>{ enum{value = 1}; }; template struct f{ enum{value = _f ::value}; }; int main(){ std::cout << f<3>::value << std::endl; return 0; }
パラメータ「3」を与えている上記のコードをコンパイル、実行してみると、ステップ数である「8」が出力されます。
では、お題は1から100までのなかから、最大のステップ数となる数を求めるとのことなので、そのように展開されるtemplateを定義してみましょう。
#includeconst int max = 100; template struct _f{ enum{value = 0}; }; /* even */ template struct _f<0, n>{ enum{value = 1 + _f<(n / 2) % 2, n / 2>::value}; }; /* odd */ template struct _f<1, n>{ enum{value = 1 + _f<(n * 3 + 1) % 2, n * 3 + 1>::value}; }; template <> struct _f<1, 1>{ enum{value = 1}; }; template struct f{ enum{value = _f ::value}; }; template struct _Compare{ enum{value = 0}; enum{index = 0}; }; template struct _Compare<1, x, y, xi, yi>{ enum{value = x}; enum{index = xi}; }; template struct _Compare<0, x, y, xi, yi>{ enum{value = y}; enum{index = yi}; }; template struct Compare{ enum{value = _Compare = y, x, y, xi, yi>::value}; enum{index = _Compare = y, x, y, xi, yi>::index}; }; template struct Loop{ enum{value = 0}; enum{index = 0}; }; /* last */ template struct Loop<1, current, max>{ enum{value = f ::value}; enum{index = current}; }; template struct Loop<0, current, max>{ enum{value = Compare< f ::value, Loop ::value, current, Loop ::index >::value }; enum{index = Compare< f ::value, Loop ::value, current, Loop ::index >::index }; }; /* main loop */ template struct h{ enum{value = Loop<0, 1, max>::index}; }; int main(){ std::cout << h ::value << std::endl; std::cout << f< h ::value >::value << std::endl; return 0; }
このコードをコンパイル、実行した結果、「97」と「119」が出力されるはずです。
前者が解で、後者はそのステップ数となります。
上記のコードは無駄が散見されるものですが、サンプルということでお目汚しのほどご勘弁を。