やっさんの雑記

プログラミングでやってみたこととか

C#からC++/CLIのdllを呼び出すときのIntelliSenseの挙動がひどい

みなさんお久しぶりです。2ヶ月半ぶりくらいですね。

今回は小ネタで、大学の実験課題をやってて気になったことです。

C#Visual Studioでの開発との親和性がとても高く、そのキモになってるのがIntelliSenseでもあるわけです。

しかし、OpenCVとかみたいにどうしてもC++で書かれたライブラリを使わないといけない場合もあります(OpenCVの場合はOpenCVSharpという素晴らしいラッパライブラリがありますが)。

C++で開発するよりもC#で開発するほうが圧倒的に楽なので、大きなアプリケーションはできればC#で開発したいわけです。

ということで、C++/CLIC++で書かれたライブラリをラップしてdll化し、それをC#で参照して使うと、既存のライブラリを楽に使えますし、また時間のかかる処理をC++で書いてdll化して高速化、みたいなことも考えられます。

しかし、このときのIntelliSenseの挙動がちょっとひどい。

同じソリューション内に

  • dllを作るほうのプロジェクト(C++/CLIで書いた、ライブラリのラッパ)
  • dllを使う方のプロジェクト(C#で書いた、GUI処理部分とか)

があって、後者は前者のプロジェクトを参照設定しているとします。このとき、dllを作る方のプロジェクトをまずコンパイルしないと、使う方のプロジェクトでは、そのdll内にある名前空間とかはIntelliSenseの中ではなかったことにされます。いちいちコンパイルするのめんどくせぇ。

まあこれは同じソリューションの中のプロジェクトから作られるdllでないdllを参照するときと同じ仕様にしてるんだろうなぁということでまだ納得できます(やっぱりいちいちコンパイルするのめんどくさいけど)。

しかし、休憩するだとかで開発中を一旦中断してVisual Studioを閉じてもう一回開くと、dllを使う側の方のdllを参照しているところについては、やはりそのdll内にある名前空間とかはIntelliSenseの中ではなかったことにされます。回復方法は今のところ不明。

なんなんだこれは。IntelliSenseの意味ほとんどないじゃん。C++単体より便利さ下がってるじゃん。死んでくれ。

イラついて一気に書いたのでぐちゃぐちゃな文章ですが、最後までお付き合いいただきありがとうございました。

C#でJSONのパース

こんばんはおはようございますこんにちは

今回はC#でJSONのパースをしてみたいと思います。

neueccさんの作られたDynamicJsonという素晴らしいライブラリもありますが、ここでは標準ライブラリを使うことにします。

標準ライブラリでJSONのパースをするには、DataContractJsonSerializerクラスを使います。

なお、.NET Framework 4.0以上が必須です。

まずは使ってみる

使い方はとても簡単で、取得したいオブジェクトの型でDataContractJsonSerializerのインスタンスを初期化して、文字列をMemoryStream経由で読み込ませるだけです。

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Json;
using System.Text;

[DataContract]
class Data
{
    [DataMember]
    public int a;

    [DataMember]
    public double d;

    [DataMember]
    public string s;
}

class Program
{
    static void Main()
    {
        var json = @"{""a"":123, ""s"":""test!"", ""pi"":3.14}";
        var serializer = new DataContractJsonSerializer(typeof(Data));
        using (var ms = new MemoryStream(Encoding.UTF8.GetBytes(json))) {
            var data = (Data)serializer.ReadObject(ms);
            Console.WriteLine(data.a);
            Console.WriteLine(data.d);
            Console.WriteLine(data.s);
        }
    }
}

このように、JSONデータの中に存在しないフィールド・プロパティがあるなどJSONデータとオブジェクトが完全には一致していなくても、デフォルト値を入れるなど適当に処理してくれます。

また、読み込ませたいオブジェクトにはDataContractAttributeを、読み込むフィールド・プロパティにはDataMemberAttributeをつけないといけないことに注意しましょう。DataMemberAttributeをつけていないフィールドやプロパティはJSONから読み込まれません。

DataMemberAttributeさえつけていれば、publicだけではなく例えばprivateなフィールド・プロパティでも読み込んでくれます。

Dictionaryの読み込み

このDataContractJsonSerializerは、組み込み型でもユーザ定義型でもだいたい読み込んでくれます。

ただし、データをDictionaryとして読み込みたいときは少しコードを変えないといけません。

具体的に何をするかというと、DataContractJsonSerializerSettingsのインスタンスを作って、UseSimpleDictionaryFormatプロパティをtrueにして、DataContractJsonSerializerのインスタンスを作ります。

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Json;
using System.Text;

[DataContract]
class Data
{
    [DataMember]
    public Dictionary<string, double> xs;
}

class Program
{
    static void Main()
    {
        var json = @"{""xs"":{""1"":1, ""e"":2.718, ""pi"":3.14}}";
        var settings = new DataContractJsonSerializerSettings();
        settings.UseSimpleDictionaryFormat = true;
        var serializer = new DataContractJsonSerializer(typeof(Data), settings);
        using (var ms = new MemoryStream(Encoding.UTF8.GetBytes(json))) {
            var data = (Data)serializer.ReadObject(ms);
            foreach (var x in data.xs) {
                Console.WriteLine("{0}\t{1}", x.Key, x.Value);
            }
        }
    }
}

読み込み時に自動的にデータを変換する

TwitterAPIを叩いたときに返ってくるJSONデータの中には、created_atプロパティのように「中身は実質的にDateTimeだけど、JSONに載せる都合上stringで送られてくる」ものも存在します(JSONに載せられるデータ型は実質的に、数値と文字列とそれらの配列だけです)。

中身は実質的にDateTimeなので、JSONを読み込むと自動的にstringからDateTimeに変換してほしいものですが、実際にはそんなに簡単にはいきません。

というのも、Twitterから送られてくるcreated_atプロパティの中のフォーマットがDateTimeのデフォルトの文字列解釈のフォーマットと異なるため、そのままではちゃんと読み込んでくれないのですね。

そこで、DataMemberAttributeをつけたものしか読み込まないという仕様をうまく使って、データ読み込み時に自動的にデータ変換するようにします。

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Json;
using System.Text;

[DataContract]
class Data
{
    [DataMember(Name = "created_at")]
    private string created_at_str_prop
    {
        get
        {
            return created_at_str_field;
        }

        set
        {
            created_at_field = DateTime.ParseExact(value, "ddd MMM dd HH:mm:ss zzz yyyy", DateTimeFormatInfo.InvariantInfo, DateTimeStyles.None);
            created_at_str_field = value;
        }
    }
    private string created_at_str_field;
    public DateTime created_at
    {
        get
        {
            return created_at_field;
        }

        set
        {
            created_at_str_field = value.ToString("ddd MMM dd HH:mm:ss zzz yyyy", DateTimeFormatInfo.InvariantInfo);
            created_at_field = value;
        }
    }
    private DateTime created_at_field;
}

class Program
{
    static void Main()
    {
        var json = @"{""created_at"":""Wed Sep 11 20:01:35 +0000 2013""}";
        var serializer = new DataContractJsonSerializer(typeof(Data));
        using (var ms = new MemoryStream(Encoding.UTF8.GetBytes(json))) {
            var data = (Data)serializer.ReadObject(ms);
            Console.WriteLine(data.created_at);
        }
    }
}

JSONデータを読み込むときに、DataMemberAttiributeがついているcreated_at_str_propプロパティのsetterが呼び出されるので、その中でデータを変換しているわけです。

Data.created_atプロパティ以外はクラスの外からは見えないので、あたかもJSONを読み込むと自動的にstringをDateTimeに変換しているように見えるわけですね。

また、今まで特に触れていませんでしたが、DataMemberAttributeをつけるときに、Name = "hogehoge"と指定することで、JSONデータ中のフィールド名を指定できます。

最後に

これでDataContractJsonSerializerを使ってJSON形式のデータを読み込む方法の紹介がざっと終わったわけですが、書き込むときもReadObjectメソッドではなくWriteObjectメソッドを使って同じようにすればできるみたいです。

LinkedListとArrayの速度が全く違う件

今回の内容は軽めです。

前回の多項式の因数分解プログラムリファクタリング中に気づいたのですが、約数の一覧を配列で持たせるかLinkedListで持たせるかで実行速度が数倍違うような気がしました(どうも勘違いで、実際にはほとんど変わってなかったみたいです)。

実験

本当にLinkedListで持たせてるのが遅くなっている原因なのか調べるために、次のような簡単なC#のコードを書いて実験してみました。単に1からnまでの整数の和を求めるだけのコードです。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main()
    {
        int n = 10000000;	// テストするデータ数
        var sw = new Stopwatch();
        long res;

        Console.WriteLine("----- LinkedList");
        sw.Reset();
        sw.Start();
        var ll1 = new LinkedList<int>();
        for (int i = 0; i < n; ++i) {
            ll1.AddLast(i);
        }
        sw.Stop();
        Console.WriteLine("Generate: {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);
        sw.Reset();
        sw.Start();
        res = 0;
        foreach (var x in ll1) {
            res += x;
        }
        sw.Stop();
        Console.WriteLine("Compute : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);

        Console.WriteLine();

        Console.WriteLine("----- Array");
        sw.Reset();
        sw.Start();
        var a1 = new int[n];
        for (int i = 0; i < n; ++i) {
            a1[i] = i;
        }
        sw.Stop();
        Console.WriteLine("Generate: {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);
        sw.Reset();
        sw.Start();
        res = 0;
        foreach (var x in a1) {
            res += x;
        }
        sw.Stop();
        Console.WriteLine("Compute : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);

        Console.WriteLine();

        Console.WriteLine("----- LinkedList -> Array");
        sw.Reset();
        sw.Start();
        var ll2 = new LinkedList<int>();
        for (int i = 0; i < n; ++i) {
            ll2.AddLast(i);
        }
        sw.Stop();
        Console.WriteLine("Generate: {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);
        sw.Reset();
        sw.Start();
        var a2 = ll2.ToArray();
        sw.Stop();
        Console.WriteLine("ToArray : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);
        sw.Reset();
        sw.Start();
        res = 0;
        foreach (var x in a2) {
            res += x;
        }
        sw.Stop();
        Console.WriteLine("Compute : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);
    }
}

手元のPCで実行した結果は下のとおりです。

----- LinkedList
Generate: 1.343535e+003[ms]
Compute : 8.357720e+001[ms]

----- Array
Generate: 2.087620e+001[ms]
Compute : 1.494910e+001[ms]

----- LinkedList -> Array
Generate: 1.392360e+003[ms]
ToArray : 5.870290e+001[ms]
Compute : 1.685090e+001[ms]

生成時間が2桁も違うのはアレですが、和の計算時間もおよそ5.6倍も開きがあります。

さらに驚きなのは、LinkedListのまま先頭から末尾まで走査して和を計算するより、一旦配列に変換してから先頭から末尾まで走査して和を計算するほうが、配列変換にかかる時間を考えても短いことですね。

理由

LinkedListは遅いと断定できたところで私は思い出したんですが、みなさんご存知の通り、線形リストの動作は一般に非常に遅いです。

これはコンピュータのしくみとも関係があるのですが、配列の場合はデータを記憶するために必要なデータ量が必要最小限で済んでしかもデータがメモリ上に連続的に配置されるのでデータが高速なキャッシュメモリに乗りやすく、そのお陰で動作も高速です。

一方線形リストの場合は、データを記憶するために必要なデータ量が多く(LinkedListの場合は双方向リストなので、64bit環境でint型のデータを格納する場合は、配列に比べておよそ5倍のデータ量が必要です)、データもメモリ上に連続的に配置されるとは限らないのでキャッシュミスが必然的に多くなり、動作が遅くなってしまうわけです。

となると、「なんでLinkedListそのままで全部の数の和を計算するよりもToArrayしてから全部の数の和を計算するほうが速いのか。LinkedListのままで和を計算するのもToArrayするのもどうせデータの先頭から末尾まで操作するんだから時間は後者のほうが長くなるはずなのに」という疑問が湧いてくるわけですが、さっきのテストプログラムを逆アセンブル(ILのコードを人間が読みやすいように変換)して実行可能ファイルを見てみると、どうやらToArrayはCLRの内部関数に投げちゃってるらしいです。

CLRの内部関数なんだから恐らく僕達が適当に書くより速く動作するんでしょう。知らないけど。

ということで(アセンブラあまり読めないし)こういうことで適当に納得することにしました。

結論

ここまで書くと、なんで線形リストなんか存在するんだっていう感じですが、ちゃんと存在理由はあります。

線形リストの最大の利点は、「要素の追加・削除・挿入がとても簡単にできる」ということです。配列の場合はサイズ変更が必要になったときにデータの移動が必要ですが、線形リストはそんなの全く必要ないですからね。

また、LinkedListは単なる双方向線形リストですが、線形リストクラスを自分で作るなどすれば、ノードのつなぎかたによっては循環リストだとかそういうのも作ることができて応用範囲が非常に広いです。

ということでLinkedListと配列の使いどころのまとめ。

LinkedList

  • いくつ入るかわからないデータの格納に使う
  • データの追加・挿入・削除が簡単
  • LinkedListに持たせたデータの処理は、ToArrayでLinkedListを配列に変換してからやるほうが速そう。何回もそのデータを使うような場面なら効果絶大
  • 参照型とかintみたいな単純な値型ならToArrayする方が速いけど、フィールドがたくさんある複雑な値型ならToArrayが遅そうな気がする(だからLinkedListのままデータ処理する方がよさそう)

そもそも大量のデータ持ってるときにさらにToArrayしたら使うメモリががが

配列

  • 最初からいくつ入るかわかってるデータの格納に使うといい
  • データの参照とかが高速
  • 使うメモリが必要最小限

というかパフォーマンス気にしなきゃいけないような段階にきたらまずは使うアルゴリズム変えるのを検討しろよって僕は思うので、普段のコーディングではLinkedListでも配列でも使いやすい方を使いましょう。

以上、おしまい。

多項式の因数分解

今回は多項式因数分解をしようと思います。

因数分解にも(本当は)いろいろあるのですが、今回は1変数整数係数多項式を、定数でない1変数整数係数多項式の積で書くことを考えます。若干表現が遠回りかもしれませんが、いわゆる普通の因数分解です。

さて、コンピュータで因数分解をするにはどうすればいいでしょうか。

直接因数分解するのは難しそうなので、因子の候補をすべて挙げて、その中から適しているものを選べばよさそうです。

問題はその因子の候補の選び方ですね。因子の候補はモレがあってはいけませんし、できることなら候補の数は減らしたいわけです(候補の数が多いと、適しているかどうかのチェックに時間がかかってしまいます)。

効率のいいアルゴリズムとかだと環論とかの知識を使うらしいんですが、残念ながらそういう抽象代数学の知識がないので、今回は頭の悪い方法で計算量的にはかなり効率が悪いのですが、単純な方法で因数分解してみたいと思います。

アルゴリズムの主要部分

今回紹介するのはKroneckerの方法(Wikipedia(英語))です。原理はわりと単純なので理解しやすいと思います。

英語版wikipediaを読むのが一番手っ取り早いと思いますが、英語なんて読めねぇぜって人もいると思うので要点だけかいつまんで説明すると、因数分解したい多項式の整数での値の約数を調べて、約数の全組み合わせに対して多項式を調べて因子を決定する、というものです。

ところがこの方法、たった5次の多項式因数分解するのにも、128通り(英語版wikipediaには実質64通りって書いてありますが組み合わせだけからどうやって高速に見分けるんでしょうねぇ)調べなければならず、結構大変です。

{x^{18}-1}みたいなわりと単純な多項式因数分解する場合でも、約100兆通りも調べなければならなくて、こんなのは現代のPCではめちゃくちゃ計算時間がかかってやってられないわけです。

そこでいろいろ工夫をして処理量を減らすわけですね。

工夫その1

Kroneckerのアルゴリズムの欠点は、因数分解したあとの因数の数(重複度も含めて考えます)が増えると、約数の数も当然増えて、組み合わせが膨大になってしまう点です。

そこで、Kroneckerのアルゴリズムに頼らなくても(完全なとはいわないけど)因数分解できるところについては分解してしまえば、因数分解する多項式の数は増えますがそれよりも組み合わせ爆発を抑える効果のほうが圧倒的に大きくなり、因数分解が高速化されます。

ここで登場するのが無平方分解です。

無平方分解というのは、多項式因数分解したときに{\{f(x)\}^n (n\ge 2)}の部分が現れないようにすることです。

一見実行が難しそうですが、かなり単純なアルゴリズムで計算できます。

多項式微分したものと元の多項式の最大公約数(最大公約多項式といったほうがわかりやすいかも)をとると、多項式因数分解したときの{\{f(x)\}^n}の部分が{\{f(x)\}^{n-1}}になって出てきます。

従って
{\frac{GCD(f^{(n-1)}(x),f^{(n)}(x))}{GCD(f^{(n)}(x),f^{(n+1)}(x))}}
を計算すれば、重複度がちょうど{n+1}の因子が出てくるわけです。

多項式微分は普通に各項ごとに微分すればいいですし、多項式の最大公約数はユークリッドの互除法と同じアルゴリズムで計算できます。

これにより、因子の数を減らして計算を高速化できるようになるばかりか、最終的に出てきた候補のうち次数が小さいものから順に割っていって割り切れたら商をもとの多項式として試行除算を繰り返す、という操作だけで因子の規約性も保証されながらすべて求められるというオマケ付きです。

工夫その2

先のような工夫は平方因子を持つ多項式に対しては非常に有効なのですが、先ほどの{x^{18}-1}のように平方因子をもたない多項式に対しては完全に無力です。

では、平方因子を持たない多項式に対して打つ手はないのでしょうか?

いいえ、あります。うまく枝刈りをすればいいわけです。

合同式の性質として、任意の整数係数多項式に対して、{i\equiv j}ならば{f(i)\equiv f(j)}が成り立つというものがありましたね(合同式の法はなんでもいいです)。つまり、整数係数多項式なら{f(i)-f(j)}{i-j}で割りきれます。ということは、{f(i)-f(j)}{i-j}の倍数でないような{i,j}が存在するなら、その約数の組み合わせは整数係数多項式を生成しないので不適ということがわかります。

これは整数列が整数係数多項式を生成するための必要十分条件ではない(例えば{f(0)}{f(4)}がそれぞれ1,1,1,1,13のとき、{f(x)}は整数係数じゃないのに{f(i)-f(j)}{i-j}で割りきれる)ですが、反例となる多項式の数はかなり少なく、また整数列の途中までしか見なくても整数係数多項式にはならないということがわかるので非常に有効な枝刈り法です。

実験

それでは実際にソースコードを書いてみようとなるわけですが、多項式の演算とかそういうのまでちゃんと書こうとすると結構行数が増えてしまって、全部でだいたい1200行くらいになってしまっています。言語はC#です。
計算途中に出てくる数が大きくなるのも想定すると任意精度整数が必要で、それならデフォで任意精度整数が使えるC#がいいかなーという感じでC#にしました。
ソースコードについてですが、長すぎてここに直接貼っても見にくくなるだけなので、githubの方に上げておきました。適当に動かして遊んでみてください。

Befungeで遊ぶ

今回は難解プログラミング言語の1つ、Befungeで遊んでみようと思います。
Befungeの言語仕様はwikipediaを見てもらえばいいと思いますが、大きな特徴はプログラムポインタがソースコード中を2次元的に動きまわることと、プログラム内の命令によって自分自身を書き換えられることでしょう。
ソースコードの大きさが無制限の場合はチューリング完全C言語とかと同等のプログラミング能力を(理論上)持ちますが、今回は80桁25行に限定したのでチューリング完全というわけではありません。しかし、これだけでも結構書けるものです。

処理系

とりあえずまずは処理系を作ってみることにします。
命令の数が多くないので、そこまで大変ではありません(といっても4時間くらいかかりましたが)。
適当にJavaScriptで書いてみました。JSはあまり得意じゃないので汚いかもです。

var code = new Array(25);
var stack = new Array();
var x = 0;
var y = 0;

var direction = [[1, 0], [0, -1], [-1, 0], [0, 1]];
var dir = 0;
var skip = false;
var string = false;
var interval = 100;
var quit = false;

function escape(letter) {
    if (letter < 32 || letter >= 127) {
        return '&nbsp;';
    }
    switch (letter) {
        case '<'.charCodeAt(0):
            return '&lt;';
        case '>'.charCodeAt(0):
            return '&gt;';
        case '&'.charCodeAt(0):
            return '&amp;';
        case ' '.charCodeAt(0):
            return '&nbsp;';
        default:
            return String.fromCharCode(letter);
    }
}

// (x, y)がハイライトされた状態でソースコード表示
function show_code(source_code, x, y) {
    var rows = "ABCDEFGHIJKLMNOPQRSTUVWXY";
    var digit = "0123456789ABCDEF"
    var i, j;

    // 1行目の記述
    var text = "&nbsp;|&nbsp;";
    for (i = 0; i < Math.floor(x / 16); ++i) {
        text += i + "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
    }
    if (x % 16 == 0) {
        text += "<div>" + Math.floor(x / 16) + "</div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
    } else {
        text += i;
        for (j = 1; i * 16 + j < x; ++j) {
            text += "&nbsp;";
        }
        text += "<div>&nbsp;</div>";
        for (++j; j < 16; ++j) {
            text += "&nbsp;"
        }
    }
    for (++i; i < 5; ++i) {
        text += i + "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
    }
    text += "<br />";

    // 2行目の記述
    text += "&nbsp;|&nbsp;";
    for (i = 0; i < x; ++i) {
        text += digit[i % 16];
    }
    text += "<div>" + digit[i % 16] + "</div>";
    for (++i; i < 80; ++i) {
        text += digit[i % 16];
    }
    text += "<br />";

    // 3行目の記述
    text += "-+-";
    for (i = 0; i < x; ++i) {
        text += "-";
    }
    text += "<div>-</div>";
    for (++i; i < 80; ++i) {
        text += "-";
    }
    text += "<br />";

    // 4行目以降
    for (i = 0; i < y; ++i) {
        text += rows[i] + "|&nbsp;";
        for (j = 0; j < x; ++j) {
            text += escape(source_code[i][j]);
        }
        text += "<div>" + escape(source_code[i][j]) + "</div>";
        for (++j; j < 80; ++j) {
            text += escape(source_code[i][j]);
        }
        text += "<br />";
    }
    text += "<div>" + rows[i] + "|&nbsp;";
    for (j = 0; j < x; ++j) {
        text += escape(source_code[i][j]);
    }
    text += "</div><div id='pointer'>" + escape(source_code[i][j]) + "</div><div>";
    for (++j; j < 80; ++j) {
        text += escape(source_code[i][j]);
    }
    text += "</div><br />";
    for (++i; i < 25; ++i) {
        text += rows[i] + "|&nbsp;";
        for (j = 0; j < x; ++j) {
            text += escape(source_code[i][j]);
        }
        text += "<div>" + escape(source_code[i][j]) + "</div>";
        for (++j; j < 80; ++j) {
            text += escape(source_code[i][j]);
        }
        text += "<br />";
    }
    document.getElementById('source').innerHTML = text;
}

// 初期位置ハイライトでソースコード表示
function show_code_init(source_code) {
    var rows = "ABCDEFGHIJKLMNOPQRSTUVWXY";
    var digit = "0123456789ABCDEF"
    var i, j;

    // 1行目の記述
    var text = "&nbsp;|<div>&nbsp;</div>";
    for (i = 0; i < 5 ; ++i) {
        text += i + "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
    }
    text += "<br />";

    // 2行目の記述
    text += "&nbsp;|<div>&nbsp;</div>0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF<br />";

    // 3行目の記述
    text += "-+<div>-</div>--------------------------------------------------------------------------------<br />";

    // 4行目の記述
    text += "<div>A|</div><div id='pointer'>&nbsp;</div><div>";
    for (j = 0; j < 80; ++j) {
        text += escape(source_code[0][j]);
    }
    text += "</div><br />";

    // 5行目以降
    for (i = 1; i < 25; ++i) {
        text += rows[i] + "|<div>&nbsp;</div>";
        for (j = 0; j < 80; ++j) {
            text += escape(source_code[i][j]);
        }
        text += "<br />";
    }

    document.getElementById('source').innerHTML = text;
}

// 逐次解釈・実行
function interpret() {
    var xx, yy, vv;
    show_code(code, x, y);
    document.getElementById('stack').innerHTML = stack.join("&nbsp;");
    if (string) {
        if (code[y][x] == '"'.charCodeAt(0)) {
            string = false;
        } else {
            stack.push(code[y][x]);
        }
    } else if (!skip) {
        switch (code[y][x]) {
            case '<'.charCodeAt(0):
                dir = 2;
                break;
            case '>'.charCodeAt(0):
                dir = 0;
                break;
            case '^'.charCodeAt(0):
                dir = 1;
                break;
            case 'v'.charCodeAt(0):
                dir = 3;
                break;
            case '_'.charCodeAt(0):
                xx = stack.pop();
                if (xx == 0) {
                    dir = 0;
                } else {
                    dir = 2;
                }
                break;
            case '|'.charCodeAt(0):
                xx = stack.pop();
                if (xx == 0) {
                    dir = 3;
                } else {
                    dir = 1;
                }
                break;
            case '?'.charCodeAt(0):
                dir = Math.floor(Math.random() * 4);
                break;
            case '#'.charCodeAt(0):
                skip = true;
                break;
            case '@'.charCodeAt(0):
                return 0;   // プログラム停止のサイン
            case '0'.charCodeAt(0):
                stack.push(0);
                break;
            case '1'.charCodeAt(0):
                stack.push(1);
                break;
            case '2'.charCodeAt(0):
                stack.push(2);
                break;
            case '3'.charCodeAt(0):
                stack.push(3);
                break;
            case '4'.charCodeAt(0):
                stack.push(4);
                break;
            case '5'.charCodeAt(0):
                stack.push(5);
                break;
            case '6'.charCodeAt(0):
                stack.push(6);
                break;
            case '7'.charCodeAt(0):
                stack.push(7);
                break;
            case '8'.charCodeAt(0):
                stack.push(8);
                break;
            case '9'.charCodeAt(0):
                stack.push(9);
                break;
            case '"'.charCodeAt(0):
                string = true;
                break;
            case '&'.charCodeAt(0):
                stack.push(parseInt(prompt("value?")));
                break;
            case '~'.charCodeAt(0):
                do {
                    xx = prompt("value?");
                } while (xx.length > 0);
                stack.push(xx.charCodeAt(0));
                break;
            case '.'.charCodeAt(0):
                document.getElementById('output').innerHTML += stack.pop() + "&nbsp;";
                break;
            case ','.charCodeAt(0):
                document.getElementById('output').innerHTML += escape(stack.pop());
                break;
            case '+'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(xx + yy);
                break;
            case '-'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(xx - yy);
                break;
            case '*'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(xx * yy);
                break;
            case '/'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(Math.floor(xx / yy));
                break;
            case '%'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(xx % yy);
                break;
            case '`'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                if (xx > yy) {
                    stack.push(1);
                } else {
                    stack.push(0);
                }
                break;
            case '!'.charCodeAt(0):
                xx = stack.pop();
                if (xx == 0) {
                    stack.push(1);
                } else {
                    stack.push(0);
                }
                break;
            case ':'.charCodeAt(0):
                xx = stack.pop();
                stack.push(xx);
                stack.push(xx);
                break;
            case '\\'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(yy);
                stack.push(xx);
                break;
            case '$'.charCodeAt(0):
                stack.pop();
                break;
            case 'g'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(code[yy][xx]);
                break;
            case 'p'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                vv = stack.pop();
                code[yy][xx] = vv;
                break;
            default:
                break;
        }
    } else {
        skip = false;
    }
    x += direction[dir][0];
    y += direction[dir][1];
    if (x < 0) {
        x = 79;
    } else if (x >= 80) {
        x = 0;
    }
    if (y < 0) {
        y = 24;
    } else if (y >= 25) {
        y = 0;
    }
    return 1;
}

// 一定間隔で実行するための関数
function run_int() {
    var ret = interpret();
    if (ret != 0 && !quit) {
        setTimeout("run_int()", interval);
    } else {
        document.getElementById('exe').innerText = '実行';
        document.getElementById('exe').onclick = run;
        document.getElementById('clear').disabled = false;
    }
}

// 実行関数
function run() {
    document.getElementById('exe').innerText = '停止';
    document.getElementById('exe').onclick = stop;
    document.getElementById('clear').disabled = true;
    document.getElementById('output').innerHTML = '';

    x = y = 0;
    quit = false;
    stack = new Array();
    dir = 0;
    skip = string = false;
    interval = parseInt(document.getElementById('interval').value);

    // ソースコードの設定
    var txt = document.getElementById('befunge').value.split("\n");
    var i;
    for (i = 0; i < Math.min(25, txt.length) ; ++i) {
        code[i] = new Array(80);
        for (j = 0; j < Math.min(80, txt[i].length) ; ++j) {
            code[i][j] = txt[i].charCodeAt(j);
        }
        for (; j < 80; ++j) {
            code[i][j] = 0;
        }
    }
    for (; i < 25; ++i) {
        code[i] = new Array(80);
        for (var j = 0; j < 80; ++j) {
            code[i][j] = 0;
        }
    }
    show_code_init(code);

    if (interval > 0) {
        setTimeout("run_int()", interval);
    } else {
        while (interpret() != 0);
        document.getElementById('exe').innerText = '実行';
        document.getElementById('exe').onclick = run;
        document.getElementById('clear').disabled = false;
    }
}

// 停止用
function stop() {
    document.getElementById('exe').innerText = '実行';
    document.getElementById('exe').onclick = run;
    document.getElementById('clear').disabled = false;
    quit = true;
}

// 内容の全消去
function my_clear() {
    stack = new Array();
    document.getElementById('output').innerHTML = '';
    document.getElementById('stack').innerHTML = stack.join("&nbsp;");
    show_code_init(code);
}

// 初期化
for (var i = 0; i < 25; ++i) {
    code[i] = new Array(80);
    for (var j = 0; j < 80; ++j) {
        code[i][j] = 0;
    }
}

show_code_init(code);

だいぶダラダラと長くなってますが、3/8くらいがソースコードをキレイに表示するための関数で、処理本体は半分弱くらいです。残りは実行用のエントリポイントだとか初期化処理だとかその類のやつです。

HTMLの方もかなり適当で、

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
	<meta content="text/html; charset=utf-8" http-equiv="Content-Type" />
	<title>Befunge</title>
	<style type="text/css">
	div div {
		background-color:aqua;
		display:inline-block;
	}
	div div#pointer {
		background-color:lime;
		display:inline-block;
	}
	div.tt, div#source {
		display:inline-block;
		font-family:"MS ゴシック";
	}
	</style>
</head>
<body>
	<form>
	<textarea cols="80" rows="25" id="befunge"></textarea><br />
	<input type="text" size="5" id="interval" value="100" />ms
	<button type="button" onclick="run()" id="exe">実行</button>
	<button type="button" onclick="my_clear()" id="clear">クリア</button>
	</form>
	<div class="tt">出力: </div><div class="tt" id="output" style="background-color:yellow"></div><br />
	<div class="tt">スタック: </div><div class="tt" id="stack" style="background-color:yellow"></div><br />
	<br />
	<div class="tt">ソースコード</div><br />
	<div style="display:inline-block;font-family:'MS ゴシック'" id="source">
	</div>
	<script language="javascript" type="text/javascript" src="befung.js"></script>
</body>
</html>

みたいな感じで適当にちゃちゃーっと作っちゃいましょう。
これでBefungeで遊ぶ準備ができました(ようやく)。
なお、プログラムサイズは80桁25行以下限定です。
また、本当はデバッグ用にステップ実行機能をつけたかったのですが、めんどくさかったのと時間があまりなかったので省略。つけたい場合はお好みでどうぞ。プログラムの実行速度は制御できるようにしてあります。

まずはHello world

定番のプログラムですね。まずはこれで遊びましょう。
wikipediaに載ってるコードをそのままコピペしちゃいましょう。

v @_       v
>0"!dlroW"v 
v  :#     < 
>" ,olleH" v
   ^       <

これだけ見るとなんのこっちゃって感じなんですが、実際に動かしてみると動作の様子がよくわかると思います。
,とか!を表示させる文字列と命令記号と兼用させているところがちょっと工夫されているところでしょうか。
ぶっちゃけ、こんなややこしいことしなくても、単純にこれで十分だと思いますが。

                   v
>,v                 
|:<"Hello, World!"0<
@                   

もしくはこんな感じ。

0"!dlroW ,olleH">:v 
                ^,_@

どのプログラムも、数字の0に続いて、Hello, World!の文字をスタックに積んで、それを順に出力しているわけですね。
この時点で書字方向が左右逆だったり変な記号ばっかりで気持ち悪いんですが、とりあえずそこには目をつぶって先に進みましょう。

もう少し進んだプログラム

Hello worldしただけでは面白くないので、もう少し複雑なプログラムを書いてみましょう。
プログラミングの入門書によくある、「1からnまでの整数の和を求める」プログラムを書いてみましょう。公式を使うと面白くないので、for文を回して(?)求めたいと思います。
こんな感じで書けばいいですね。

0&>:!v v+ <
@.-#\_:00p^
  ^1 g0<   

やっぱりこれだけ見てもなんのこっちゃなので、プログラムの構成法を書いておきます。
まず、今までに足した数の和と、足す数の上限を記録しておかないといけないので、0と、&でユーザが入力した数をスタックに積みます。問題はそのあとですね。
スタックの状態が

[sum][counter]

の状態から

[sum+counter][counter-1]

にしたいわけです。
どうすればいいかというと、もっていきたい状態の方から逆順に考えればよくて、(x, y)をソースコード中の適当な場所として

[sum+counter][counter-1]       --[counter]
[sum+counter][counter][1]      --[counter]
[sum+counter][counter]         --[counter]
[sum+counter][x][y]            --[counter]
[sum+counter][x]               --[counter]
[sum+counter]                  --[counter]
[sum][counter]                 --[counter]
[sum][coutner][counter][x][y]  --[???]
[sum][counter][counter][x]     --[???]
[sum][counter][counter]        --[???]
[sum][counter]                 --[???]

という感じで考えれば、やり方がわかりますね。--[counter]みたいなのは(x, y)に記録されているデータとします。
counterが非0であれば、

:xyp+xyg1-

という処理をすればいいわけです(xやyは適当な数字に置き換えましょう)。
counterが0のときはsumの値を表示してプログラムを終了するだけなので、

\.@

という処理をすればいいというのはすぐわかると思います。
あとはまあなんというか試行錯誤というか、ソースコードをいかに圧縮するかの戦いみたいな感じでしょうか。
もちろんいろんな実装方法があるので、例えばこんなのも考えられるでしょう。

v v>#<:00pv
0 -^_ \.@ +
>&>:^^1g00<

これの面白いところは、#の部分を左右にいったりきたりするところでしょうか。

もっと複雑なプログラム

FizzBuzzでもやってみることにしましょう。

&00p1>:00g`!v     v             <        >%\52*v v*86< 
>,v  +  v`1:_@v                          *#<   / +>\`| 
|:<", "0_v    #   #                      ^2 5:<: ,*    
     1   >:3%!10p:5%!20p10g20g*v^"Buzz"0_:52*\^_$v^2<  
>    $   ^     v!:<"Fizz Buzz"0_10gv       #     >:5^  
     ^        <_, ^         "Fizz"0_20g ^  ^         < 

こんな感じでいいと思います。これをもっと短くするとかいうのはちょっとやりたくないですね(これでもちょっとはやりました)。
一番苦労したのは数字を表示する部分です。
普通なら.で簡単に出力できるんですが、数字の直後はスペースじゃなくてカンマにしたかったのでわざわざ自分で処理を書きました。
FizzBuzzの難しいところは、条件分岐がたくさんあるので、さっきのnまでの和を求めるプログラムみたいになってほしい状態が複雑なことですね。
そのまま考えるはちょっと難しいので、C言語で書いたソースコードをもとに考えてみます。

#include <stdio.h>
int main(void)
{
  int n;
  int i = 1;
  int mod3, mod5;
  scanf("%d", &n);
  while (i <= n) {
    if (i > 1) {
      printf(", ");
    }
    mod3 = !(i % 3);
    mod5 = !(i % 5);
    if (mod3 && mod5) {
      printf("Fizz Buzz");
    } else if (mod3) {
      printf("Fizz");
    } else if (mod5) {
      printf("Buzz");
    } else {
      printf("%d", i);
    }
  }
  return 0;
}

C言語ならみなさん慣れ親しんでいる(はず)なので、これが正しくFizzBuzzを表示することはまあわかると思います。
それでは部分ごとに分けて考えてみます。

初期化

&でとってきた入力とi=1をスタックもしくはソースコードのどこかに保存します。どこに保存するのが適切かはこの段階ではまだよくわかりません。

", "の出力

iと1を比較してiの方が大きかったら", "を出力するので、この段階でiがスタックの先頭に来てないといけないですね。あとでiは頻繁に参照・更新することを考えると、iはスタックに置くほうがよさそうですね。

v_, v →1`v  
 ^!:<", "_$>→
>          ^

という雛形ができます(→はここから入る、←はここから出る印とします)。

条件振り分け

3とか5で割った余りをとりあえず変数に保存します(解説書いてて思った
のですが、ちょっと無駄かもしれません)。
最終的に

[i]          --[!(i%3)][!(i%5)]

とかいう感じになっていてほしいので、さっきのプログラムと同じ要領で考えると、(A, B), (C, D)をそれぞれ適当な場所として

:3%!ABq:5%!CDq

とすると、結果が保存できますね。
肝心の条件分岐ですが、Befungには、&&みたいな演算子がないので、掛け算で対応です。

→:3%!ABq:5%!CDqABgCDg*v
                   イ←_ABgv
                       ロ←_CDgv
                           ハ←_→ニ

イはFizz Buzzを表示するブロック、ロはFizzを表示するブロック、ハはBuzzを表示するブロックで、それぞれ抜けると最初のループ条件のところに戻ります。ニは次で説明する十進数表示ルーチンです。

十進数表示

残念ながらBefungeの.での数値表示は、C言語

printf("%d ", number);

というのに相当し、数値の後ろにスペースが入ってしまいます。今はそれでは困るので、自分の手で1桁ずつ表示します。
1番下の桁の数は表示したい数を10で割った余りで、それより上の桁の数は表示したい数を10で割った商です。ということは、10で割った余りをスタックに積んでいって、商が0になった段階でASCIIコードで48足しながらスタックの先頭から表示していくと、ちょうどいい感じに表示されそうです。
10で割った余りをスタックに積んでいくには

→:52*\>:52*%\52*/v
      ^          _$→

でいいですね。あとは48を足しつつ表示していくので、

→>:52*\`v
 ^ ,+*86_$→

みたいな感じになります。なお、終了判定のためにスタックの底(から1つ上)に10を積んでいます(スタックから取り出した値が10以上ならループ脱出)。

初期化処理をもう一度

&で最初に拾ってきた値をスタックの底に積むと終了判定がうまく書けなかったので、ソースコードの適当な場所に値を記憶させることにします。
(E, F)に値を記憶させるとして、

→&EFp1 :00g`v
           @_→

という部品が出来上がりますね。
ループから戻ってくるときはカウンタに1を足して、上の:の直前の空白のところに戻ってくればいいわけです。

まとめ

こんな感じで出来上がった部品を組み合わせて、あとはいろいろ配置とかをいじくると完成すると思います。

感想

めんどくさい。二度と触りたくないけど、しばらくしたらまた触りたくなってそう。
あと、記事の面積の2/3くらいが自作処理系のソースコードになっちゃってる事実に触れてはいけない。

おまけ

JavaScript触りながら、「なんで文字定数ないねん!」とかいっぱいツッコミ入れながら書いてました。JSも触りたくない。

追記

記事書いた3時間後くらいにFizzBuzz見返してたら、なんじゃこのコードはわけわからんわーとなったので、いろいろ解説を追加しました。

配列の要素の和

何か配列を用意したとき、その配列の要素すべての和を求めたいことはよくありますね。

そのとき、すべての要素が数値型(intとかfloatとか)なら特に問題はないんですが、stringの配列だったりだとか、2次元配列だったりとかすると事態は複雑です。スクリプト言語とかで配列の要素の型が1種類じゃない場合はもっと複雑ですね。

そこで、私の独断と偏見で選んだ代表的なスクリプト言語4つの「配列の要素の和を求める標準関数」を使って、下の4つの配列の要素の和をそれぞれ求めてみました。

a = [1, 2, 3, 4, 5, 6]
b = [1, "2", 3, 4, 5, 6]
c = [1, 2, 3, 4, [5, 6]]
d = [1, "2", 3, 4, [5, 6]]

Ideone上でためしに実行するとこんな感じになります。スクリプト言語はあまり好きではないのでよく知らないのですが、変な書き方などしているところがあったらご指摘ください。

Perl

use strict;
use List::Util qw(sum);

my @a = (1, 2, 3, 4, 5, 6);
my @b = (1, "2", 3, 4, 5, 6);
my @c = (1, 2, 3, 4, (5, 6));
my @d = (1, "2", 3, 4, (5, 6));
print List::Util::sum(@a), "\n"; # => 21
print List::Util::sum(@b), "\n"; # => 21
print List::Util::sum(@c), "\n"; # => 21
print List::Util::sum(@d), "\n"; # => 21

Perlは入れ子になった配列でも再帰的に和を計算してくれるらしいです。
文字列も数値に変換した上で合計を計算してくれています。

PHP

<?php
$a = array(1, 2, 3, 4, 5, 6);
$b = array(1, "2", 3, 4, 5, 6);
$c = array(1, 2, 3, 4, array(5, 6));
$d = array(1, "2", 3, 4, array(5, 6));
echo array_sum($a) . "\n"; # => 21
echo array_sum($b) . "\n"; # => 21
echo array_sum($c) . "\n"; # => 10
echo array_sum($d) . "\n"; # => 10
?>

こちらはPerlと違って入れ子の配列は再帰的に和を計算するとかはせず、単に0扱い(or 単に足さないだけ)らしいです。

Python

a = [1, 2, 3, 4, 5, 6]
b = [1, "2", 3, 4, 5, 6]
c = [1, 2, 3, 4, [5, 6]]
d = [1, "2", 3, 4, [5, 6]]
print sum(a), "\n" # => 21
# print sum(b), "\n" # => error
# print sum(c), "\n" # => error
# print sum(d), "\n" # => error

お行儀がいいと言いましょうか、最初の数字だけの配列以外はすべてREになりました。

Ruby

a = [1, 2, 3, 4, 5, 6]
b = [1, "2", 3, 4, 5, 6]
c = [1, 2, 3, 4, [5, 6]]
d = [1, "2", 3, 4, [5, 6]]
puts a.inject(:+) # => 21
# puts b.inject(:+) # => error
# puts c.inject(:+) # => error
# puts d.inject(:+) # => error

Pythonと同じ結果です。

まとめ

ということで適当にアルファベット順に実行してみたわけですが、PythonRubyは配列に「変なもの」が入っていても型付けの強さのおかげですぐREを出してくれます。

Perlの仕様は1次元配列だけではなくて多次元配列の全要素の和を求めたいときなどにはとても楽に書けるようになっているんじゃないかと思います。しかし、下手に無理やり答えを計算しようとしちゃっているので、「一応エラーは出ないけど答えが正しくない」とかいう一番厄介なパターンのバグを含みやすそうな気がします。

PHPの仕様は誰得なんでしょうね。数値型じゃない要素は足さないという仕様ならまだしも、文字列型のものは数値型に変換して足しちゃってるので、便利になりそうなケースも思い浮かばないですし、Perlでの一番厄介なバグも含みやすそうです。数値型にできないものは足さないというのは内部の実装としてはわりと簡単そうですが。


まあそもそも配列にぐちゃぐちゃいろんな型の値を突っ込むのが間違いだと思うので、スパゲティコードを書きたくない人は素直に、配列に入れるのは1種類の型(もしくはintとfloatみたいに1種類の型とみなしても差し支えない範囲の複数の型)だけにしましょうw


(2013/06/06追記)

Ideone上で実行と書きましたが、一応それぞれの言語のバージョンを書いておきます。

言語 Perl PHP Python Ruby
バージョン perl 5.16.2 php 5.4.4 python 2.7.3 ruby-1.9.3

始めました

プログラミングの忘備録とかの意味も兼ねて作ってみました

よろしくお願いします