不思議な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

処理系のバグでしょうか?
そうでないなら、単に私の知らないリテラル記法があるんでしょうか。


ちなみにPerlBNFは公開されてないようですが、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])*

どうやら上2つがPerlの数値リテラルの10進表現の仕様のようです。
(続いて2進、8進、16進表現でしょう)

メタプログラミング

先日書いた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++
#include 

template 
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++使ったことも無いくせに・・・)
ただし、こちらは以下のルールを勝手に設けてみました。

  • ループを使わない(for, whileなど)
  • 関数の再帰呼び出しを行わない
  • ifや3項演算子による分岐を行わない

要するにtemplateで解を得ましょうという話です。
まず、ステップ数の計算は以下のようなtemplate展開から求められます

#include 

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};
};




int main(){
	std::cout << f<3>::value << std::endl;
	return 0;
}

パラメータ「3」を与えている上記のコードをコンパイル、実行してみると、ステップ数である「8」が出力されます。
では、お題は1から100までのなかから、最大のステップ数となる数を求めるとのことなので、そのように展開されるtemplateを定義してみましょう。

#include 

const 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」が出力されるはずです。
前者が解で、後者はそのステップ数となります。
上記のコードは無駄が散見されるものですが、サンプルということでお目汚しのほどご勘弁を。

以上、ループも関数の再帰呼び出しも行わないC++の例でした。