2012-04-29

【電脳卸】全てのカテゴリをパースする。

電脳卸のWebAPIで「全てのカテゴリを返す」XMLファイルがあるので、それをパースしてみたよ。
PHPの組み込み関数にもXMLをパースする関数があるけど、自分で実装したくなったので自分で書いてみたよ。

APIから返されるXMLの構造が微妙に難しかったので、再帰関数とスタックでやってみた。

APIのURLは→「http://webservice.d-064.com/3.x/category.xml」です。

/**
  電脳卸用全てのカテゴリをパースして配列して、シリアライズ後保存する。
  パース結果の配列は以下のような仕様で出力される
  
  結果配列仕様:
    array( 'カテゴリID 1' => array( 'name' => 'カテゴリ名', 'parent' => '親カテゴリID' ) );
    array( 'カテゴリID 2' => array( 'name' => 'カテゴリ名', 'parent' => '親カテゴリID' ) );
    array( 'カテゴリID 3' => array( 'name' => 'カテゴリ名', 'parent' => '親カテゴリID' ) );
    ...
    array( 'カテゴリID n' => array( 'name' => 'カテゴリ名', 'parent' => '親カテゴリID' ) );
    ※一番上のカテゴリは親カテゴリIDが「-1」となっている。
  
  商品のカテゴリIDから親カテゴリ全てを取得するには、    
    function get_category_tree( $category_id, &$category_tree )
    {
      global $global_category_array;
      
      $id = $category_id;
      $name   = $global_category_array[ $id ][ 'name' ];
      $parent = $global_category_array[ $id ][ 'parent' ];
      
      $category_tree[ $id ] = 
        array( 'name'   => $name, 'parent' => $parent );
      
      if( $parent == '-1' ) {
        return ;
      } else {
        get_category_tree( $parent, $category_tree );
      }
    }
    
    $global_category_array = unserialize( file_get_contents( './category_array.dat' ) );
    $tree = array();
    get_category_tree( '1269', $tree );
    var_dump( $tree );
  といったプログラムで返せる。
*/
define( 'CATEGORY_XML_URL',         'http://webservice.d-064.com/3.x/category.xml' );
define( 'CATEGORY_XML_FILENAME',    dirname( __FILE__ ) . DIRECTORY_SEPARATOR . 'category.xml' );
define( 'CATEGORY_ARRAY_FILENAME',  dirname( __FILE__ ) . DIRECTORY_SEPARATOR . 'category_array.dat' );
define( 'CATEGORY_SRC_ENCODING',    'UTF-8' );
define( 'CATEGORY_DIST_ENCODING',   'SJIS' );
date_default_timezone_set( 'Asia/Tokyo' );

/*
  個々のカテゴリデータを取得する
  @return array [ 'category_id', 'category_depth', 'category_name' ]
*/
function get_id_depth_name()
{
  global $xmlp;
  return array(
    preg_replace( '/<[^>]+>(.*?)<\/[^>]+>/', '$1', trim( fgets( $xmlp ) ) ),        // カテゴリID
    preg_replace( '/<[^>]+>(.*?)<\/[^>]+>/', '$1', trim( fgets( $xmlp ) ) ),        // カテゴリ深さ
    preg_replace( '/<[^>]+>(.*?)<\/[^>]+>/', '$1', trim( fgets( $xmlp ) ) ) );      // カテゴリ名
}
 /**
  カテゴリXMLをパースする。再帰関数。
  @param $parent 親カテゴリID
*/
function parse( $parent = -1 ) 
{
  global $xmlp;
  global $global_category_array;
  global $global_parent_ids;        // 親IDのスタック
  
  $line = trim( fgets( $xmlp ) );
  switch( true ) {
    // 空行
    case ($line == ''):
      parse( $parent );
      break;
    
    // XML定義
    case preg_match( '/<\?xml(?:[^>]+)>/', $line ):
      parse( $parent );
      break;
    
    // 一番外側のタグ
    case ($line == ''):
      parse( $parent );
      break;
    case ($line == ''):
      fclose( $xmlp );
      return;
    
    // 1つのカテゴリ
    case ($line == ''):
      list( $id, $depth, $name ) = get_id_depth_name();
      $name = mb_convert_encoding( $name, CATEGORY_DIST_ENCODING, CATEGORY_SRC_ENCODING );
      // 親IDを退避
      $parent = $global_parent_ids[ 0 ];
      // スタックに自分を積む
      array_unshift( $global_parent_ids, $id );
      
      $global_category_array[ $id ][ 'name' ]    = $name;
      $global_category_array[ $id ][ 'parent' ]  = $parent;
      
      parse( $parent );
      break;
    case ($line == ''):
      // 自分のIDを捨てる
      array_shift( $global_parent_ids );
      parse( $global_parent_ids[ 0 ] );
      break;
      
    // サブカテゴリ
    case ($line == ''):
      parse( $global_parent_ids[ 0 ] );
      break;
    case ($line == ''):
      parse( $global_parent_ids[ 0 ] );
      break;
    
    // ファイルが終わる前に「/Categorys」が来るはずなので使わないかも。
    case feof( $xmlp ):
      fclose( $xmlp );
      return;
      
    // 何かあったときのための保険。そのまま終了。
    default:
      die( '[' . $line . '] Exception.' );
  }
}


// XMLファイルダウンロードと保存
file_put_contents( CATEGORY_XML_FILENAME, file_get_contents( CATEGORY_XML_URL ) );

// XMLファイルのポインタ取得
$xmlp = fopen( CATEGORY_XML_FILENAME, 'r' );
if( !$xmlp ) {
  die( 'XML File Dont Open.' );
}

// 親IDスタックと結果配列準備
$global_parent_ids      = array( -1 );
$global_category_array  = array();

// パース本体
parse();

// 結果配列をシリアライズして保存
file_put_contents( CATEGORY_ARRAY_FILENAME, serialize( $global_category_array ) );

exit( 0 );

こんな感じ。

2012-04-25

【Scheme】ForthをSchemeで実装してみた。


はい。今度はScheme(処理系はGaucheを使用)でForthを実装してみました。

プログラムは5つの部分に分かれていて、
1)スタック管理
2)標準入力からプログラムを読むリーダ
3)ForthプログラムをSchemeプログラムに変換するトランスレータ
4)ワードが登録される辞書
5)実行制御
という構成になっています。

とりあえず、各部分の説明をしていきます。

1)スタック管理
;;; スタック管理

(define *data-stack* '())

(define (push val)
  (set! *data-stack* (cons val *data-stack*)))

(define (pop)
  (cond
   ((null? *data-stack*)
    (raise "Stack UnderFlow."))
   (else 
    (let ((val (car *data-stack*)))
      (set! *data-stack* (cdr *data-stack*))
      val))))

スタック管理は面倒くさくないグローバル変数を使ったものにしました。
関数もPUSHとPOPのみです。POPにはスタックアンダーフローがでたら例外が投げられるようになっています。

2)標準入力からプログラムを読むリーダ
;;; 標準入力から読み込み、トークンに分割する。

(define (trim str)
  (begin
    (set! str (regexp-replace #/^\s+/ str ""))
    (set! str (regexp-replace #/\s+$/ str ""))
    str))

;; シンボルに使えない文字を変換する
(define (def-word-translate str)
  (begin
    (set! str (regexp-replace-all #/\;/ str "edef"))
    (set! str (regexp-replace-all #/\:/ str "sdef"))
    (set! str (regexp-replace-all #/\./ str "dot"))
    (set! str (regexp-replace-all #/\.([a-zA-Z])/ str "dot\\1"))
    (set! str (regexp-replace-all #/\s+/ str " "))
    str))

;; 半角スペースで分割
(define (tokenizer str)
  (token->symbol (string-split (def-word-translate str) " ")))

;; トークンをシンボルと数値のリストにする
(define (token->symbol tokens)
  (cond
   ((null? tokens) '())
   ((rxmatch #/[0-9\.]+/ (car tokens))
    (cons (string->number (car tokens))
   (token->symbol (cdr tokens))))
   (else
    (cons (string->symbol (car tokens))
   (token->symbol (cdr tokens))))))

;; 標準入力からプログラムを読み取り、トークンにして返す
(define (reader)
  (let ((line (read-line)))
    (cond
     ((eof-object? line) '())
     ((string=? "" (trim line))
      (reader))
     (else
      (tokenizer (trim line))))))

基本的には標準入力から入ってきた文字列をトークンに分割するだけなのですが、「;」や「.」がSchemeでは特別な意味を持っているので、変換してからトークンに分割しています。

3)ForthプログラムをSchemeプログラムに変換するトランスレータ
;;; ForthプログラムをSchemeに変換する
(define *program* '())

(define (translate-token token)
  (cond
   ((number? token)
    (list 'push token))
   ((search-dict token)
    (list (get-dict token)))
   (else
    (raise (format #f "Undefined [~A]." token)))))

(define (define-word tokens)
  (cond
   ((null? tokens)
    (raise "Syntax Error: [;] is missing."))
   ((eq? 'edef (car tokens)) '())
   (else
    (cons (translate-token (car tokens))
   (define-word (cdr tokens))))))

(define (translate tokens define-flag)
  (cond
   ((null? tokens) '())
   ((and define-flag)
    (if (eq? (car tokens) 'edef)
 (translate (cdr tokens) #f)
 (translate (cdr tokens) #t)))
   ((eq? (car tokens) 'sdef)
    (add-dict (cadr tokens) 
       (append '(lambda ()) (define-word (cddr tokens))))
    (translate (cdr tokens) #t))
   (else
    (cons (translate-token (car tokens))
   (translate (cdr tokens) #f)))))

トランスレータは今はこれだけです。これに「ループ処理」や「ローカル変数」などを実装するともっと長くなりそうです。
ワード定義もここでやっていて、
(append '(lambda ()) '(define-word ...))
とやれば、手軽にワードを生成することができますね。

4)ワードが登録される辞書
;;; 辞書用プログラム
(define *dictionaly* (make-hash-table 'equal?))

;; 辞書初期化
(define (init-dict)
  (begin
    (hash-table-put! *dictionaly* '+ 
       (lambda () (push (+ (pop) (pop)))))
    (hash-table-put! *dictionaly* '- 
       (lambda () (let ((a (pop))) (push (- (pop) a)))))
    (hash-table-put! *dictionaly* '* 
       (lambda () (let ((a (pop))) (push (* (pop) a)))))
    (hash-table-put! *dictionaly* '/ 
       (lambda () (let ((a (pop))) (push (/ (pop) a)))))
    (hash-table-put! *dictionaly* 'mod 
       (lambda () (let ((a (pop))) (push (mod (pop) a)))))
    (hash-table-put! *dictionaly* 'dot 
       (lambda () (print (pop))))
    (hash-table-put! *dictionaly* 'dots
       (lambda () (print (reverse *data-stack*))))
    (hash-table-put! *dictionaly* 'exit
       (lambda () (exit)))
    ))

;; 辞書に追加
(define (add-dict key val)
  (hash-table-put! *dictionaly* key val))

;; 辞書検索
(define (search-dict key)
  (hash-table-exists? *dictionaly* key))

;; 辞書から取得
(define (get-dict key)
  (if (search-dict key)
      (hash-table-get *dictionaly* key)
      (raise (format #f "Undefined [~A]" key))))

ワード辞書もグローバル変数としました。辞書からワードを取得するとき、ワードが存在しなければ例外が投げられます。
ワードは「init-dict」関数に追加していけば使える組み込みワードが増えます。今は四則演算と表示くらいしかないですがw

5)実行制御
;;; Forthエントリポイント

;; 処理系初期化
(define (init-forth)
  (begin
    (load "./dictionaly")
    (load "./reader")
    (load "./stack")
    (load "./translate")
    (init-dict)))

;; ForthプログラムをSchemeに変換した結果を実行する
(define (exec-forth prog ret)
  (cond
   ((null? prog) ret)
   (else
    (exec-forth (cdr prog)
  (eval (car prog) (interaction-environment))))))


(init-forth)
(let loop ()
  (display "> ")
  (flush)
  (display (exec-forth (translate (reader) #f) #f))
  (newline)
  (loop))

これは特に説明することもないです。
処理系の初期化関数とトランスレートしたForthプログラムの実行くらいです。
トランスレートしたプログラムはただevalしてるだけですね。

こんな感じです。

2012-04-20

【Forth】JavaScriptでForthっぽいの作ってみた。

ちょっと前から、簡単な言語構造をしているプログラミング言語を他の言語で実装することにはまっています。
今回挑戦したのはForth言語です。
今回はJavascriptで作ったので、整数も浮動小数点数も同じ1つのスタックで処理できます。つまり、「1.2 2 + sqrt」とか書くことが可能です。
この言語の特徴は「スタック志向」と「逆ポーランド記法(後置記法)」につきます。他の言語で言う「関数」は「ワード」といいます。ワードは辞書に登録されています。
と、突然言われても良くわからないのと思うので、早速サンプルプログラムをいくつか列挙して解説していきたいと思います。
Forthは(というより後置記法がですが)偶然にも日本語の並びにとても似ているので日本語で説明するのが実は簡単です。

04-21追記:個別サイトを作ってみました。JS Forth

●インタプリタデモ
1.下の入力欄にプログラムを入力して、エンターキーを押します。
2.自動的に計算結果が入力欄の下にたまります。
※このページをリロードすると定義したワードが消えてしまいますので注意してください。




●20000円を3人で割り勘にする
 → 20000 3 /mod floor . .
解説:
上のプログラムは以下の通り処理が進みます。
1)20000をスタックに積む。3をスタックに積む。(20000 3)
2)スタックから2つ値を取り出して、除算をし、剰余をスタックに積む。商をスタックに積む。(/mod)
3)スタックからひとつ取り出して小数点以下を切り捨てる。(floor)
4)スタックから1つ取り出して表示する。(.)
5)スタックから1つ取り出して表示する。(.)
ね、簡単でしょ?
日本語で説明するときは、「20000円と3万円で割り算して商と余りを出す。商の小数点以下を切り捨てて結果を出す」といったところでしょうか。

●割り勘ワード定義
上のプログラムをワード(関数)にしてみます。
 → : warikan ( n1 n2 -- n n ) /mod floor ;
解説:
1)「:(以下コロン)」はワード定義が始まるときに書きます。コロンがないとForthインタプリタは解釈モードとして動作し、結果を出そうとします。それをやめさせるにはこのコロンが必要です。コロンが見つかったときインタプリタは「コンパイルモード」になってプログラムがワード定義だとわかり、結果を出すのではなく定義されたワードを辞書に登録します。
2)「warikan」はワード名です。
3)「(」~「)」はコメントです。この場合のコメント「( n1 n2 -- n n )」はスタックから2つ取り出し、処理結果を2つ積む。という内容のコメントです。
4)「/mod floor」はwarikanワードのプログラム本体でこれらに引数の記述は必要なく、ワードの中でスタックからポップする処理やプッシュ処理が記述されているので「引数を本当に」とりません。
5)「;」はコロン定義の終了マークです。

Forth言語のプログラムは以上のような感じです。

●組み込みワード
今のところ組み込みワードは以下の通りです。
注意としては、制御構造ワードは「コンパイルモード」でしか使用できないところでしょうか。
詳しいワードの説明は「GForthマニュアル」がいいと思います。

・算術演算(整数・小数の区別なし)
+ 1+ - 1- * / mod /mod negate abs min max

・ビット演算
and or xor invert lshift rshift 2* 2/

・比較演算
< <= <> = > >= 0< 0<= 0<> 0> 0>=

・算術関数
floor round ** sqrt exp log cos sin tan acos asin atan atan2 pi

・制御構造
if else then endif begin agein repeat while until ?do loop +loop -loop unloop leave exit recurse

・スタック操作
drop nip dup over tuck swap rot -rot pick clearstacks

・表示
. .s

2012-04-07

【Lisp/Scheme】Pythonで実装されたSchemeインタプリタをPHPにコンバートしてみた。

関数型言語勉強の一環として、比較的簡単なSchemeのインタプリタをいつも使ってるPHPで実装してみることを考えたのですが、参考になる書籍がなかったのでネットで探したところ以下のページを見つけました。
((Pythonで) 書く (Lisp) インタプリタ) http://www.aoky.net/articles/peter_norvig/lispy.htm

このページのプログラムはPythonで書かれています。PythonとPHPはかなり違う言語なので、なぜかPythonの勉強もしてしまいましたw

評価器以外には特に苦労しなかったので、評価器以外を直接見たい場合はこの記事一番下からダウンロードしてください。

■評価器(Evaluator)
評価器は標準入力から入力されたS式(Lisp系言語のプログラムのこと)を読取り器から得るシンボルや定数の列を受け取って解釈しプログラムを実行するものです。
以下具体的に見ていきます。実際のPythonプログラムは上のページを見てください。
評価器は再帰関数になってて、Schemeのスペシャルフォーム(評価器が式の内容全てを評価しない式のこと)の処理と、普通の式を処理するかなり簡単なプログラムです。
が、これをPHPにコンバートするのに苦労しました。以下が自分の書いた評価器プログラムです。

・コンバートしたPHPプログラム
/**
  定数、シンボルまたはシンボルの配列を評価する。再帰関数。
  @param $symbols 定数、シンボル、またはシンボルの配列
  @param $env     環境オブジェクト。指定されない場合はトップレベル環境。
*/
public static function lisp_eval( $symbols, $env = null )
{
  // 環境が指定されていないときはトップレベルの環境を指定
  if( $env == null ) {
    global $global_environment;
    $env = $global_environment;
  }
  
  // シンボルの場合
  if( is_a( $symbols, 'Symbol' ) ) {
    return $env->get( $symbols->value );
  
  // 定数の場合
  } elseif( is_scalar( $symbols ) ) {
    return $symbols;
  
  // 以降リストの場合
  } elseif( $symbols[ 0 ]->value == 'quote' ) {     // (quote exp)
    list( $quote, $exp ) = $symbols;
    return $exp;
    
  } elseif( $symbols[ 0 ]->value == 'if' ) {        // (if test conseq alt)
    list( $if, $test, $conseq, $alt ) = $symbols;
    if( self::lisp_eval( $test, $env ) ) {
      return self::lisp_eval( $conseq, $env );
    } else {
      return self::lisp_eval( $alt, $env );
    }
    
  } elseif( $symbols[ 0 ]->value == 'define' ) {      // (define var (lambda exp))
    list( $define, $var, $exp ) = $symbols;
    $env->add( $var->value, self::lisp_eval( $exp, $env ) );
    
  } elseif( $symbols[ 0 ]->value == 'lambda' ) {      // (lambda vars exp)
    list( $lambda, $vars, $exp ) = $symbols;
    $str_lambda  = '$args = func_get_args();' . "\n";
    $str_lambda .= '$env  = array_pop( $args );' . "\n";
    $str_lambda .= '$vars = unserialize( stripslashes( ' . "'" . addslashes( serialize( $vars ) ) . "'" . ' ) ); ' . "\n";
    $str_lambda .= '$exp  = unserialize( stripslashes( ' . "'" . addslashes( serialize( $exp ) ) . "'" . ' ) ); ' . "\n";
    $str_lambda .= '$new_env = new Environment( &$env );' . "\n";
    $str_lambda .= '$new_env->zip( $vars, $args );' . "\n";
    $str_lambda .= 'return Evaluator::lisp_eval( $exp, $new_env );' . "\n";
    $lambda_function = create_function( '', $str_lambda );
    return $lambda_function;
  
  } elseif( $symbols[ 0 ]->value == 'begin' ) {       // (begin exps)
    each( $symbols );
    foreach( $symbols AS $symbol ) {
      $val = self::lisp_eval( $symbol->value, $env );
    }
    return $val;
    
  } else {                                            // 関数評価
    $exps = array();
    
    foreach( $symbols AS $symbol ) {
      $exps[] = self::lisp_eval( $symbol, $env );
    }
    $proc = array_shift( $exps );
    
    /*
      小細工
      関数が使う環境オブジェクトを関数の引数として渡す。
    */
    array_push( $exps, $env );
    $ret  = call_user_func_array( $proc, $exps );
    return $ret;
  }
}


Pythonの評価器には「S式をリスト構造に直した」リストと、環境オブジェクト(後述)が渡されるようですが、PHPにはリストのように扱える組み込みデータ構造が用意されていません。
この関数のためにいちいちリスト構造を実装するのも面倒なので、配列をリストの代わりにしました。
引数の「$symbols」がその配列です。この配列に対して「each」「array_shift」「list」などを使えば、案外簡単に配列をリストのように扱えます。

・環境オブジェクトのこと
環境オブジェクト(以下環境)はトップレベルやレキシカルな環境を実現するためにあります。評価器に渡される環境オブジェクトには現在自分がいる階層の変数、関数が見えています。
また、環境には1つ外側の環境のポインタを持っていて、「あるシンボルを参照したいときに自分のいる環境に無い場合はひとつ外側の環境を参照する」という再帰メソッドが定義されています。
自分のいる階層の環境には自由に関数やシンボルを登録することができますが、自分より下(よりレキシカルな)環境にはアクセスできません。

・関数定義と環境オブジェクトに関する小細工
評価器にはS式のリストと環境が渡されます。リスト内に関数定義があると、評価する際微妙な問題を起こしました。
Pythonのプログラムは普通にクロージャ内に直接実行時の環境を渡せるのですが、自分が使っているPHP(Ver5.1.4)のクロージャには現在の環境をそのままでは渡せません。
なので、関数実行時に「関数の引数とともに現在の環境を押し込む」というなんともチカラ技なプログラムになってしまいました。
そんな感じなので、クロージャでは「引数のチェック」なんてものはしてませんw

こんな感じです。


Pythonのプログラムページに載っている以下のプログラムも「遅い」ですけど、一応動作します。
lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))
lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1)))))) lis.py> (define first car)
lis.py> (define rest cdr)
lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))


PHPのソース全部は以下からダウンロード可能です。
http://www.tagajo.tv/lisphp_1.0.zip

■使い方
シェルに以下のように入力してください。
$ php -f lisphp.php

ZenBack

WebMoney ぷちカンパ