内園の日記

2007-03-30 不思議な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進表現でしょう)

2006-07-25 メタプログラミング

先日書いたC++のコードコンパイルした場合、結果を静的に保持してるかどうかの検証です。

手っ取り早くobjdmpで見てみましょう。

ちなみに今回利用したコンパイラはgcc3.3.3のg++です。

値が3の場合(結果は8)

以下はmain関数の抜粋です。

08048684 <main>:
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

どうやら、ちゃんと定数として結果を保持しているようです。

2006-07-23 続・Collatz予想

C++の特殊化されたtemplateは、KL1等のGHC(Guard Horn Clause)に基づく言語の条件付clauseに似ています。

(特殊化してない場合はguardが常にtrueのclauseでしょうか)

試しに先日のCollatz予想のステップ数を求めるtemplateを、だいたい同じような形でKL1に対応させたコードを書いてみました。

どうでしょう、templateが特殊化によって、異なるguardを持つclauseのように振舞ってるように見えませんか?

(templateの特殊化はguardほど柔軟ではありませんが)

C++
#include <iostream>

template <unsigned is_odd, unsigned n>
struct f2{
	enum{value = 0};
};

/* even */
template <unsigned n>
struct f2<0, n>{
	enum{value = 1 + f2<(n / 2) % 2, n / 2>::value};
};

/* odd */
template <unsigned n>
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 <unsigned n>
struct f{
	enum{value = f2<n % 2, n>::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世代コンピュータプロジェクトの初期の頃は、他の処理系も開発されていたようですが、現在でも手に入るんでしょうか?

2006-07-19 Collatz予想

キミならどう書く 2.0 - ROUND 2 -

http://ll.jus.or.jp/2006/blog/doukaku2

Collatz予想のステップ数を求めるコードを書こうかと思いましたが、私の気になる言語Scheme, Io, Ocamlは既に先を越されているようで無念至極、諦めかけたところC++で記述してる例を見かけました。

C++はLLではないとの見方が優勢なのだと思っていましたが、特に誰も気にしてないようなので、私もこっそりC++で書いてみることにします。

(ロクにC++使ったことも無いくせに・・・)

ただし、こちらは以下のルールを勝手に設けてみました。

要するにtemplateで解を得ましょうという話です。

まず、ステップ数の計算は以下のようなtemplate展開から求められます


#include <iostream>

template <unsigned is_odd, unsigned n>
struct _f{
	enum{value = 0};
};

/* even */
template <unsigned n>
struct _f<0, n>{
	enum{value = 1 + _f<(n / 2) % 2, n / 2>::value};
};

/* odd */
template <unsigned n>
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 <unsigned n>
struct f{
	enum{value = _f<n % 2, n>::value};
};




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

パラメータ「3」を与えている上記のコードをコンパイル、実行してみると、ステップ数である「8」が出力されます。

では、お題は1から100までのなかから、最大のステップ数となる数を求めるとのことなので、そのように展開されるtemplateを定義してみましょう。


#include <iostream>

const int max = 100;



template <unsigned is_odd, unsigned n>
struct _f{
	enum{value = 0};
};

/* even */
template <unsigned n>
struct _f<0, n>{
	enum{value = 1 + _f<(n / 2) % 2, n / 2>::value};
};

/* odd */
template <unsigned n>
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 <unsigned n>
struct f{
	enum{value = _f<n % 2, n>::value};
};



template <unsigned f, unsigned x, unsigned y, unsigned xi, unsigned yi>
struct _Compare{
	enum{value = 0};
	enum{index = 0};
};

template <unsigned x, unsigned y, unsigned xi, unsigned yi>
struct _Compare<1, x, y, xi, yi>{
	enum{value = x};
	enum{index = xi};
};

template <unsigned x, unsigned y, unsigned xi, unsigned yi>
struct _Compare<0, x, y, xi, yi>{
	enum{value = y};
	enum{index = yi};
};

template <unsigned x, unsigned y, unsigned xi, unsigned yi>
struct Compare{
	enum{value = _Compare<x >= y, x, y, xi, yi>::value};
	enum{index = _Compare<x >= y, x, y, xi, yi>::index};
};






template <unsigned last, unsigned current, unsigned max>
struct Loop{
	enum{value = 0};
	enum{index = 0};
};

/* last */
template <unsigned current, unsigned max>
struct Loop<1, current, max>{
	enum{value = f<current>::value};
	enum{index = current};
};

template <unsigned current, unsigned max>
struct Loop<0, current, max>{
	enum{value = Compare<
		f<current>::value,
		Loop<current + 1 == max, current + 1, max>::value,
		current,
		Loop<current + 1 == max, current + 1, max>::index
		>::value
		};
	enum{index = Compare<
		f<current>::value,
		Loop<current + 1 == max, current + 1, max>::value,
		current,
		Loop<current + 1 == max, current + 1, max>::index
		>::index
		};
};

/* main loop */
template <unsigned max>
struct h{
	enum{value = Loop<0, 1, max>::index};
};



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

このコードをコンパイル、実行した結果、「97」と「119」が出力されるはずです。

前者が解で、後者はそのステップ数となります。

上記のコードは無駄が散見されるものですが、サンプルということでお目汚しのほどご勘弁を。

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

みんなのプロフィールみんなのプロフィール 2006/07/21 05:53 ブログ開設おめでとうございます!!

アクセス数を上げるために当コミュニティサイトに登録しませんか?
http://blog.livedoor.jp/responsibility_asd/


より多くのひとに貴方のブログを見てもらえます。

参加するにはこちらからが便利です
http://blog.livedoor.jp/responsibility_asd/?mode=edit&title=%93%E0%89%80%82%CC%93%FA%8BL&address=http%3A%2F%2Fd%2Ehatena%2Ene%2Ejp%2Fuchizono%2F


お問い合わせはコチラから
http://blog.livedoor.jp/responsibility_asd/?mail