2014-04-06

ループでEval（その1）

C# Scallop

evalを再帰で書くとすぐStackOverflowExceptionで死んじゃうので、ループで書いてみようという試み。
単純に走査するだけのコードを前回のエントリで書いたので、それを使いつつ。
こんな感じ。

using System;
using System.Collections.Generic;

abstract class SExp { }

class Pair : SExp
{
  public SExp Car { get; set; }
  public SExp Cdr { get; set; }

  public Pair(SExp car, SExp cdr)
  {
    this.Car = car;
    this.Cdr = cdr;
  }

  public override string ToString()
  {
    return "(" + this.Car + " . " + this.Cdr + ")";
  }
}

class Atom : SExp
{
  public string Value { get; set; }

  public Atom(string str)
  {
    this.Value = str;
  }

  public override string ToString()
  {
    return this.Value;
  }
}

class Nil : SExp 
{
  public override string ToString()
  {
    return "()";
  }
}

class App
{
  static void Main(string[] args)
  {
    // (a b c)
    SExp exp1 = new Pair(new Atom("a"), new Pair(new Atom("b"), new Pair(new Atom("c"), new Nil())));
    // (a b c . d)
    SExp exp2 = new Pair(new Atom("a"), new Pair(new Atom("b"), new Pair(new Atom("c"), new Atom("d"))));
    // (x y (a b c) z)
    SExp exp3 = new Pair(new Atom("x"), new Pair(new Atom("y"), new Pair(exp1, new Pair(new Atom("z"), new Nil()))));

    SExp result = Scan(exp1);
    Console.WriteLine("result: " + result);
    Console.WriteLine("==========");

    result = Scan(exp2);
    Console.WriteLine("result: " + result);
    Console.WriteLine("==========");

    result = Scan(exp3);
    Console.WriteLine("result: " + result);
    Console.WriteLine("==========");

    result = Scan(new Atom("hoge"));
    Console.WriteLine("result: " + result);
    Console.WriteLine("==========");

    result = Scan(new Nil());
    Console.WriteLine("result: " + result);
    Console.WriteLine("==========");
  }

  static SExp Scan(SExp exp)
  {
    Stack<SExp> stk1 = new Stack<SExp>();
    Stack<Frame> stk2 = new Stack<Frame>();
    Frame frame = new Frame();
    int sqn = 0;

    SExp result = null;

    while (true)
    {
      if (exp is Pair)
      {
        SExp car = (exp as Pair).Car;
        SExp cdr = (exp as Pair).Cdr;

        if (cdr is Nil || cdr is Atom)
        {
          frame.State = Frame.StateForEval.LastCellScaned;
        }

        stk1.Push(cdr);
        exp = car;

        if (car is Pair)
        {
          Console.WriteLine("push");
          stk2.Push(frame);
          frame = new Frame();
        }
      }
      else
      {
        Console.WriteLine("eval: " + exp);
        result = exp;
        if (frame.State == Frame.StateForEval.LastCarEvaled)
        {
          frame.State = Frame.StateForEval.CanEval;
        }
        if (frame.State == Frame.StateForEval.LastCellScaned)
        {
          frame.State = Frame.StateForEval.LastCarEvaled;
        }

        if (frame.State == Frame.StateForEval.CanEval)
        {
          if (frame.List is Nil)
          {
            frame.List = new Pair(exp, new Nil());
          }
          else
          {
            Pair last = GetLastPair(frame.List as Pair);
            if (exp is Atom)
            {
              last.Cdr = exp;
            }
          }

          // 評価した部分リストは、表示短縮のために　E1, E2, E3,... で表記しておく
          sqn++;
          Console.WriteLine("EVAL: " + frame.List + " => E" + sqn);
          Atom a = new Atom("E" + sqn);

          if (stk2.Count == 0)
          {
            result = a;
          }
          else
          {
            Console.WriteLine("pop");
            frame = stk2.Pop();

            if (frame.State == Frame.StateForEval.LastCarEvaled)
            {
              frame.State = Frame.StateForEval.CanEval;
            }
            if (frame.State == Frame.StateForEval.LastCellScaned)
            {
              frame.State = Frame.StateForEval.LastCarEvaled;
            }

            if (frame.List is Nil)
            {
              frame.List = new Pair(exp, new Nil());
            }
            else
            {
              Pair last = GetLastPair(frame.List as Pair);
              last.Cdr = new Pair(a, new Nil());
            }
          }
        }
        else
        {
          if (frame.List is Nil)
          {
            frame.List = new Pair(exp, new Nil());
          }
          else
          {
            Pair last = GetLastPair(frame.List as Pair);
            last.Cdr = new Pair(exp, new Nil());
          }
        }

        if (0 == stk1.Count) break;
        exp = stk1.Pop();
      }
    }

    return result;
  }

  class Frame
  {
    public SExp List { get; set; }
    public StateForEval State { get; set; }

    public Frame()
    {
      List = new Nil();
      State = StateForEval.None;
    }

    public enum StateForEval
    {
      // まだ最後のコンスセルまで来てない
      None,
      // 最後のコンスセル読み込んだ
      LastCellScaned,
      // 最後のコンスセルのcarを処理した
      LastCarEvaled,
      // 最後のコンスセルのcdrを処理した（リストの要素全部を評価した）
      CanEval,
    }
  }

  // 最後のノード取得は番兵でやるべきだろ
  static Pair GetLastPair(Pair list)
  {
    while (list.Cdr is Pair)
    {
      list = list.Cdr as Pair;
    }
    return list;
  }
}

実行結果→Ideone.com - sh0FXd - Online C# Compiler & Debugging Tool
スタック2個使ったけど、大丈夫なのかな。変な事してないかな...。

構文木を走査するためのスタック（stk1）
リストの評価がどこまで終わってるか覚えておくためのスタック（stk2）

今回は手続きだけを想定して書いたけど、構文（defineやlambdaなど）は、それ独自の評価ルールがあるから、どげんかせんといかん。

2013-11-20

S式の要素を走査する

C# Scallop

再帰とループの2通りの方法でS式（リスト）を走査してみる。ループの方はスタックの使い方これでいいのかよくわからんけど。

using System;
using System.Collections.Generic;

abstract class SExp { }

class Pair : SExp
{
  public SExp Car { get; private set; }
  public SExp Cdr { get; private set; }

  public Pair(SExp car, SExp cdr)
  {
    this.Car = car;
    this.Cdr = cdr;
  }

  public override string ToString()
  {
    return "(" + this.Car + " . " + this.Cdr + ")";
  }
}

class Atom : SExp
{
  public string Value { get; set; }

  public Atom(string str)
  {
    this.Value = str;
  }

  public override string ToString()
  {
    return this.Value;
  }
}

class Nil : SExp 
{
  public override string ToString()
  {
    return "()";
  }
}

class App
{
  static void Main(string[] args)
  {
    // exp2 == (x y (a b c) z)
    SExp exp1 = new Pair(new Atom("a"), new Pair(new Atom("b"), new Pair(new Atom("c"), new Nil())));
    SExp exp2 = new Pair(new Atom("x"), new Pair(new Atom("y"), new Pair(exp1, new Pair(new Atom("z"), new Nil()))));

    Scan1(exp2);
    Console.WriteLine("==========");
    Scan2(exp2);
  }

  // 再帰処理で走査
  static void Scan1(SExp exp)
  {
    if (exp is Pair)
    {
      Scan1((exp as Pair).Car);
      Scan1((exp as Pair).Cdr);
    }
    else
    {
      Console.WriteLine(exp);
    }
  }

  // ループ+スタックで走査
  static void Scan2(SExp exp)
  {
    Stack<SExp> cs = new Stack<SExp>();
    while (true)
    {
      if (exp is Pair)
      {
        SExp car = (exp as Pair).Car;
        SExp cdr = (exp as Pair).Cdr;
        cs.Push(cdr);
        exp = car;
      }
      else
      {
        Console.WriteLine(exp);
        if (0 == cs.Count) break;
        exp = cs.Pop();
      }
    }
  }
}

car部にPairがくると木構造（？）になってしまう。car部の部分木を走査し終わった後にcdr部の部分木を走査するためには、位置を記憶しておかないといけないので、スタックが必要になる。メソッド呼び出しは、この「戻ってくる場所をスタックで記憶しておく」という仕事を処理系が裏でやってくれるので簡潔に書ける。

以前二分木のイテレータで散々悩んだときのやり方でも考えてみるかな。S式も木構造だけど、あの時の木構造と違うのは、ノードが「自分の値」を持っていない（leftとrightだけ）ってことなのかな？

2013-09-30

階乗計算

C# Scallop

言語が提供するコールスタックを利用せずに再帰の要領で計算したくなった。特にオチは無い。

using System;
using System.Collections.Generic;

class App
{
  static public void Main(string[] args)
  {
    const int N = 6;

    /////////////////////////////////////
    // 6!=720 を、3つの方法でやってみた。
    /////////////////////////////////////

    // 1. 素朴にループで
    Console.WriteLine(Fact1(N));

    // 2. 素朴に再帰で
    Console.WriteLine(Fact2(N));

    // 3. コールスタックを自前で用意して再帰っぽく
    Console.WriteLine(Fact3(N));
  }

  // 素朴にループ
  static int Fact1(int n)
  {
    int prod = 1;
    for (int i = 0; i < n; i++)
    {
      prod *= (i + 1);
    }
    return prod;
  }

  // 素朴に再帰
  static int Fact2(int n)
  {
    if (n == 0) return 1;
    return n * Fact2(n - 1);
  }

  // コールスタックに積まれる情報
  class Frame
  {
    public int Arg { get; set; }
    public int Ret { get; set; }
    public Frame(int arg) { Arg = arg; }
  }

  // C#が提供するコールスタックを使わず
  // スタックを自前で用意
  static int Fact3(int n)
  {
    // なんちゃってコールスタック
    Stack<Frame> frames = new Stack<Frame>();

    Frame f = new Frame(n);
    while(true)
    {
      if (f.Arg == 0)
      {
        // 再帰の出口
        f.Ret = 1;
        break;
      }
      else
      {
        // 再帰呼び出し
        frames.Push(f);
        f = new Frame(f.Arg - 1);
      }
    }

    // 残りの掛け算
    while (0 < frames.Count)
    {
      Frame peek = frames.Peek();
      peek.Ret = f.Ret * peek.Arg;
      f = frames.Pop();
    }
    return f.Ret;
  }
}

動かしてみた。ちゃんと動いてるっぽい。

2013-06-19

一度に複数レコードをINSERT

oracle DB

仕事でOracle触ってる。テストデータとして大量のレコードをINSERTしたかったので、

INSERT ALL
INTO TABLE1 (FIELD1, FIELD2, FIELD3, ...) VALUES (VALUE11, VALUE12, VALUE13, ...)
INTO TABLE1 (FIELD1, FIELD2, FIELD3, ...) VALUES (VALUE21, VALUE22, VALUE23, ...)
INTO TABLE1 (FIELD1, FIELD2, FIELD3, ...) VALUES (VALUE31, VALUE32, VALUE33, ...)
...
SELECT * FROM DUAL;

ってやってみたけど、レコードが多くなった場合（カラム数が数十、レコード数が数千件）にORA-24335のエラーが出た。次のようにしたら大丈夫だった。

INSERT INTO TABLE1 (FIELD1, FIELD2, FIELD3, ...) (
    SELECT VALUE11, VALUE12, VALUE13, ... FROM DUAL UNION ALL
    SELECT VALUE21, VALUE22, VALUE23, ... FROM DUAL UNION ALL
    SELECT VALUE31, VALUE32, VALUE33, ... FROM DUAL UNION ALL
    ...
)

解決方法として妥当なのか良くわからんけど、まぁいいや。

2013-06-09

VirtualBoxのGuestAdditions

開発環境備忘録

VirtualBoxにdebian wheezyを入れたが、GuestAdditionsの入れ方忘れてたのでメモ。

sudoできるようにする
1. suでrootになる
2. visudoで自分を設定
次のパッケージをインストール（aptitude updateとaptitude apgradeは適宜やっておく）
- build-essential
- module-assistant
GuestAdditionsのインストール用のスクリプトを実行
- sudo sh /media/cdrom/VBoxLinuxAdditions.run

2012-11-08

メールによる画像のアップロード

PHP Mobile

スマホからは

<input type="file">

でファイルをアップロードできないっぽいので、メールによるアップロードで実現する方向になりそうなので、やってみた。
メールによる方法のほかにも、FacebookとかがやってるJavaScriptによる方法もあるっぽいけど。

QdmailReceiverを使う

結論からいうと、iPhone5で画像を添付して送ると、ヘッダの形が期待している形式じゃないからかできなかった。QdmailReceiverに関しては、ヘッダを解析する部分の正規表現をいじると良いという情報がたくさん公開されているようで、それを試してみたけどダメだった。
開発止まってるみたいだなぁ。QdmailReceiverとは - QdmailReceiver Multibyte mail decoder & POP Client

PEARを使う

PEAR::Net_POP3とPEAR::Mail_mimeDecodeを使うとよさげ。ってことで、次の記事を参考にやってみた。cronでバッチ処理を想定しているので、vendorに配置してみた。

後者はラッパークラスを作ってくださってて、ありがたやありがたや〜。

<?php

// 配置したパスに応じて変更すること
// http://d.hatena.ne.jp/ya--mada/20080415/1208318475より拝借
App::import('vendor', 'ReceiptMailDecoder', array('file' => 'mail' . DS . 'ReceiptMailDecoder.class.php'));

class CheckmailShell extends Shell {

  function main() {

    $server = 'mail.hogehoge.com'; // サーバ
    $port = 110; // ポート番号（POP3 on SSLなら995）
    $user = 'foobar@hogehoge.com'; // メールアドレス
    $pass = 'foobarbazqux'; // パスワード

    // 保存先のディレクトリ
    $img_dir = 'foo/bar/baz';

    require_once 'Net/POP3.php';
    $pop = new Net_POP3();
    $ret = $pop->connect($server, $port);
    if ( !$ret ) {
      echo 'wrong settings for mail server.';
      exit;
    }

    // ユーザ名 と パスワード でログイン
    $ret = $pop->login($user, $pass);
    if ( !$ret ) {
      echo 'failed to login.';
      exit;
    }

    // メールの件数を取得
    $num = $pop->numMsg();
    for ($mail_id = $num; 1 <= $mail_id; $mail_id--) {

      // メールを取得（IDは1〜件数なので注意。0開始じゃないっぽい）
      $data = $pop->getMsg($mail_id);

      // 解析用のオブジェクト作成
      $decoder = new ReceiptMailDecoder($data);

      /////////////////////////////////////////
      // 必要に応じて利用する
      /////////////////////////////////////////
      //// To:アドレスのみを取得する
      //$toAddr = $decoder->getToAddr();
      //// To:ヘッダの値を取得する
      //$toString = $decoder->getDecodedHeader( 'to' );
      // Subject:ヘッダの値を取得する
      //$subject = $decoder->getDecodedHeader( 'subject' );
      //
      //// text/planなメール本文を取得する
      //$body = mb_convert_encoding($decoder->body['text'],"eucjp-win","jis");
      //// text/htmlなメール本文を取得する
      //$body = mb_convert_encoding($decoder->body['html'],"eucjp-win","jis");

      if ($decoder->isMultipart()) {

        $tempFiles = array();
        $num_of_attaches = $decoder->getNumOfAttach();

        for ($i = 0; $i < $num_of_attaches; $i++) {

          $file = $decoder->attachments[$i];

          // 保存先のディレクトリ
          $fpath = $img_dir . DS . $file['file_name']);

          // とりあえず保存してみる
          $decoder->saveAttachFile($i, $fpath);

          // 確認
          echo $fpath, PHP_EOL;
        }
      }
      // メールを削除
      $pop->deleteMsg($mail_id);
    }
    $pop->disconnect();
  }
}

2012-11-07

絵文字の削除

PHP Mobile

あるサイトのPCサイトとスマホサイト作ってて、スマホで入力された絵文字を削除するという必要に迫られたのでメモ。理想は、

<input type="password">

の時みたいに、絵文字のキーボードを利用不可にして、絵文字を入力できないようにすることだけど。できないっぽい？
ガラケーで使われてる絵文字と、スマホで使われてる絵文字は仕組みが違うのかな？その辺のことはよく分かってないけど、とりあえずiOS6とAndroidに関していうと、「http://www.unicode.org/~scherer/emoji4unicode/snapshot/full.html」の

iOSではunicode（それをエンコードしたUTF-8）
AndroidではGoogle定義のコード

が使われてるそうだ。「携帯絵文字変換ライブラリ HTML_Emoji - libemoji.com」というライブラリを

<?php
  // 数値文字参照の絵文字を UTF-8 の絵文字に変換
  $text = $emoji->filter($text, array('DecToUtf8', 'HexToUtf8'));
  // $text に含まれている、３キャリアの UTF-8 の絵文字を削除
  $text = $emoji->removeEmoji($text);
?>

って使うと、iOSの絵文字は消えてくれた。これはガラケーの絵文字を削除するためのものなのかな？よくわからん。消えてくれたからいいや。
一方、Androidで使われているのはGoogle定義の絵文字だからか（？）消えてくれなかった。ってことでCakePHP（1.2.8）のcomponent書いた。

<?php
class DelemojiComponent extends Object
{
  // 1桁の16進数を、4桁の2進数へ変換する
  function toStrBin($strHex) {
    $int = intval($strHex, 16);
    $result = sprintf('%04b', $int);
    return $result;
  }

  // 4桁の2進数を1桁の16進数へ変換する
  function toStrHex($strBin) {
    $int = intval($strBin, 2);
    $result = sprintf('%1X', $int);
    return $result;
  }

  // utf8をunicodeへ変換する
  function toStrUnicode($strUtf8) {
    $len = mb_strlen($strUtf8);
    $b = '';
    // 16進数1文字を2進数4bitへ変換
    for ($i = 0; $i < $len; $i++) {
      $b .= $this->toStrBin($strUtf8[$i]);
    }

    $strUnicodeBin = '';
    $byte = $len / 2;
    $unicodeByte;
    if ($byte == 1) {
      // 1バイト文字
      // unicodeのコードポイントは2バイト: 00000000, 0xxxxxxx
      $unicodeByte = 2;
      $strUnicodeBin = '00000000' . $b;
    } else if ($byte == 2) {
      // 2バイト文字
      // unicodeのコードポイントは2バイト: 00000xxx, xxyyyyyy
      $unicodeByte = 2;
      $strUnicodeBin = '00000' . mb_substr($b, 3, 5) . mb_substr($b, 10, 6);
    } else if ($byte == 3) {
      // 3バイト文字
      // unicodeのコードポイントは2バイト: xxxxyyyy, yyzzzzzz
      $unicodeByte = 2;
      $strUnicodeBin = mb_substr($b, 4, 4) . mb_substr($b, 10, 6) . mb_substr($b, 18, 6);
    } else {
      // 4バイト文字
      // unicodeのコードポイントは3バイト: 000wwwxx, xxxxyyyy, yyzzzzzzz
      $unicodeByte = 3;
      $strUnicodeBin = '000' . mb_substr($b, 5, 3) . mb_substr($b, 10, 6) . mb_substr($b, 18, 6) . mb_substr($b, 26, 6);
    }

    // 16進表現に直す
    $strUnicodeHex = '';
    for ($i = 0; $i < $unicodeByte * 2; $i++) {
      $s = mb_substr($strUnicodeBin, $i * 4, 4);
      $strUnicodeHex .= $this->toStrHex($s);
    }
    return $strUnicodeHex;
  }

  // google定義の絵文字を削除する
  function removeGoogleCharCode($str) {

    // まず、数値文字参照形式のgoogle独自のコードを削除しておく。
    // 正規表現で表わすと &#xFE[0-9a-fA-F]{3}; となる。
    $removedCharRef = mb_ereg_replace('&#xFE[0-9a-fA-F]{3};', '', $str);

    // 以降では、数値文字参照ではなく、UTF-8のバイト列として表わされた絵文字を削除する。
    $hex = bin2hex($removedCharRef);
    $length = mb_strlen($hex);
    $maxByte = 4;  // 最大4バイト
    $offset = 0;
    $result = '';

    while ($offset < $length) {

      $head = $hex[$offset] . $hex[$offset + 1];
      $dec = base_convert($head , 16, 10);
      $byte = 0;
      $skip = false;
      if (240 <= $dec) {
        // 4バイト文字: 1バイト目が1111 0xxx
        $byte = 4;
      } else if (224 <= $dec) {
        // 3バイト文字: 1バイト目が1110 xxxx
        $byte = 3;
      } else if (192 <= $dec) {
        // 2バイト文字: 1バイト目が110x xxxx
        $byte = 2;
      } else {
        // 1バイト文字: 1バイト目が0xxx xxxx
        $byte = 1;
      }

      $b = '';
      for ($i = 0; $i < $byte; $i++) {
        $b .= ($hex[$offset + (2 * $i)] . $hex[$offset + (2 * $i + 1)]);
      }

      // 削除対象かどうか調べる
      if ($byte == 4) {
        $unicode = $this->toStrUnicode($b);
        // UTF-8が4バイトだと、unicodeは3バイトなので6文字
        if ($unicode[0] === '0' &&
          $unicode[1] === 'F' &&
          $unicode[2] === 'E') {
          // コードポイントが 0FE000 以降は、googleの絵文字コードなので削除
          $skip = true;  
        }
      }

      if (!$skip) {
        // この文字は必要なので追加
        $result .= $b;
      }
      $offset += ($byte * 2);
    }

    $result = pack('H*', $result);
    return $result;
  }
} 
?>

これを、

<?php
class HogeController extends AppController {
  var $components = array('Delemoji');

  // ... 中略 ...

  function doSomething () {
    // ... 略 ...
    $text = $this->Delemoji->removeGoogleCharCode($text);
    // ... 略 ...
  }

?>

みたいに使うと、消えるんじゃないかなー。クソ効率悪いからあんまり長い文字列食わせると時間かかるかも。