2009-06-25

Gauche-XMPPライブラリをリリース!

GaucheでXMPPクライアントを作ろう!
Gauche-xmpp-1.0.tgz

gitリポジトリ http://github.com/gemmat/Gauche-XMPP/tree

tweet.IMを使えばTwitterクライアントにもなる!
ただし、Google Talkには直接繋げません。(私がTLSをまだ実装していないので)
jabber.jpや、ローカルで立てたejabberdに繋いで楽しんでください。

簡単な説明

XMPPには以下の段階があります。

接続
認証
リソースバインド
セッションセット
プリセンス
メッセージのやりとり
...
切断

このライブラリはシンプルさを目指したので、この段階に逐一沿って、
メッセージのやりとりまでに5個も関数を呼ぶ必要がありますが、勘弁してください。

xmpp-connect で接続。
- おなじみの call-with-xmpp-connection もあるのでどうぞ。
xmpp-auth で認証。認証方法を自動で選んで使ってくれます
- digest-md5暗号認証を最優先し、次点にplain認証, anonymous認証
- 手動がよければ xmpp-sasl-digest-md5 などを直接呼んでください。
xmpp-bind でリソースバインド。
xmpp-session でセッションセット。
xmpp-presence でプリセンス。
xmpp-message でメッセージを送る。
xmpp-receive-stanza で受信。受信するまでブロックします。
- stanzaの解釈はあなたの仕事です(ぎゃー)。届いたSXMLを渡すので、sxpathを駆使して頑張ってください。
xmpp-disconnect で切断。

2009-06-20

インターネットOSとしてのGoogle Wave

みなさんこんにちは！私はアーキテクチャ宇宙飛行士です。
今日はみなさんを、インターネットOSの旅へとご案内しましょう！

インターネットOSとは

ティム曰く：
次第に我々はウェブサービスの荒野が変わるのを目の当たりにするだろう。開拓段階である第一段階は、スクリーンスクレイピングやバックエンドがデータベースのウェブサイトへの「無許可の」専用インターフェースを特徴とする。第二段階になると、ウェブサイト自身がより効率的で、XML ベースの API を提供するようになる（今これが起こり始めている）。第三段階になると、単一のベンダ（あるいは少数の競合ベンダ）が、インターネットをプログラム呼び出し可能なコンポーネントの膨大なコレクションに変え、それらのコンポーネントを、非技術系の人たちに毎日利用されるアプリケーションに統合する包括的な一連の API を提供することで、個々のサービスの寄せ集めが実際のオペレーティングシステムのレイヤーに統合されることになる。
from クラウドでLinuxディストリビューションにあたるものは何になるだろう？

2010年アーキテクチャ宇宙の旅

地上

人々が互いにワープロのドキュメントを送り合っていたり、互いにスプレッドシートを送り合っていたりする。

レベル１

そこに「ファイルを送る」という一般的なパターンがあることに気づく。

レベル２

人々がファイルを送るように、WebブラウザもまたWebページの要求を「送る」。

レベル３

オブジェクトのメソッドを呼び出すのもまた、オブジェクトにメッセージを送るようなものだ！また同じパターンが見つかった！

宇宙

すべてはメッセージング・・・宇宙からは、地上のすべてがすっきり見通せるのだ！

2009-06-17

Gaucheで天下一プログラマー予選例題

Klab 天下一プログラマーコンテスト

以下の文字列はUTF-8を文字エンコーディング形式とする16進数のバイト列である。
UTF-8でエンコーディングされた文字列として解析した場合、この文字列の【文字数】を答えなさい。
e4bba5e4b88be381aee69687e5ad97e58897e381af5554462d38e38292e69687e5ad97
e382a8e383b3e382b3e383bce38387e382a3e383b3e382b0e5bda2e5bc8fe381a8e381
99e3828b3136e980b2e695b0e381aee38390e382a4e38388e58897e381a7e38182e3828be38082

　　　／￣￣＼
　／　　 _ノ　　＼
　|　　　（ ●）（●） 　＜おっと、それ以上は言うなよ…
.　|　　　　 （__人__）＿＿＿_
　 |　　　　　｀ ⌒／ ─'　'ー＼
.　 |　　 　 　　／（ ○） 　（○）＼
.　 ヽ　　 　 ／　　⌒（n_人__）⌒ ＼
　　 ヽ　　　|、　　　　（　　ヨ　　　　|　Emacsでhexl-insert-hex-stringすれば
　　　/　　 　`ー─−　　厂　　　／
　　　|　　 ､ ＿ 　　__,,／　　　　 ＼

Gaucheでまっとうにやります。
処理内容

"e4bb....82" ->
'(e 4 b b a 5 ...) ->
'("e4" "bb" "a5" ...) ->
'(228 187 165 ...) ->
#u8(228 187 165 ...) ->
UTF-8文字列

(use srfi-1)
(use util.list)
(use gauche.uvector)

(define (天下一 str)
  (string-length
   (u8vector->string
    (list->u8vector
     (map (lambda (x)
            (string->number (apply string x) 16))
          (slices (string->list str) 2))))))

(天下一  (string-append "e4bba5e4b88be381aee69687e5ad97e58897e381af5554462d38e38292e69687e5ad97"
                        "e382a8e383b3e382b3e383bce38387e382a3e383b3e382b0e5bda2e5bc8fe381a8e381"
                        "99e3828b3136e980b2e695b0e381aee38390e382a4e38388e58897e381a7e38182e3828be38082"))
=> 41

もっと簡単な解き方がありそう。

(追記 2009/6/18 22:20)
packで一発でした。

(use binary.pack)
(string-length (pack "H*" '("e4bba5...中略...e38082") :to-string? #t))

2009-05-30

素因数分解もういっかい

素因数分解: ツムジのひとりごと
- ありがとうございます。111111111の計算に48秒もかかるのは私のミスです。factorizeの終了条件に[< n (expt p 2)]が抜けていたのが原因です。お見苦しいコードをお見せしました。

(use util.stream)
(define (composites s)
  (stream-delay
   (let1 p (stream-car s)
     (stream-cons (expt p 2)
                  (xor (stream-map (pa$ * p) (xor (stream-cdr s) (composites s)))
                       (composites (stream-cdr s)))))))

(define (xor s0 s1)
  (stream-delay
   (let ((x (stream-car s0))
         (y (stream-car s1)))
     (cond
      ((= x y) (xor (stream-cdr s0) (stream-cdr s1)))
      ((< x y) (stream-cons x (xor (stream-cdr s0) s1)))
      ((> x y) (stream-cons y (xor s0 (stream-cdr s1))))))))

(define primes (stream-cons 2 (xor (stream-iota -1 3) (composites primes))))

(define (divisor n m count)
  (if (zero? (modulo n m))
    (divisor (quotient n m) m (+ 1 count))
    (values n count)))

(define (factorizer n strm)
  (let loop ([n n] [strm strm] [l '()])
    (let ((p  (stream-car strm))
          (ps (stream-cdr strm)))
      (cond 
       ([= n 1]          (reverse l))
       ([< n (expt p 2)] (reverse (cons (cons n 1) l)))
       (else
        (receive (r count) (divisor n p 0)
          (if (zero? count)
            (loop r ps l)
            (loop r ps (cons (cons p count) l)))))))))

(define (main args)
  (print (factorizer (string->number (cadr args))
                     primes)))

% time gosh factStrm.scm 111111111
((3 . 2) (37 . 1) (333667 . 1))
gosh factStrm.scm 111111111  0.10s user 0.01s system 96% cpu 0.111 total

以上です。

素数ストリームを使う時点で速さは諦めていますが、きれいに書けるので好きです。
ツムジさんのコードは速くてすばらしいです。

自分用メモ:ツムジさんのコードを俺流に書いたもの。記録のため残す。

(define (divisor n m count)
  (if (zero? (modulo n m))
    (divisor (quotient n m) m (+ 1 count))
    (values n count)))

(define (factorize n)
  (let loop ([n n] [i 2] [l '()])
    (receive (r count) (divisor n i 0)
      (cond
       ([= n 1]          (reverse l))
       ([> (expt i 2) n] (reverse (cons (cons n 1) l)))
       (else             (loop r
                               (+ i (if (= i 2) 1 2))
                               (if (zero? count)
                                 l
                                 (cons (cons i count) l))))))))

(define (main args)
  (print (factorize (string->number (cadr args)))))

(追記 2009/5/31)
factorizerはstrmを受け取る汎用性があるので、ツムジさんのように素数列を求めずに"2と奇数列"でやるときは、こうします。

(define (main args)
  (print (factorizer (string->number (cadr args))
                     (stream-cons 2 (stream-iota -1 3 2)))))

2009-05-23

素因数分解英語でいうとファクタライゼーション

みずぴー日記素因数分解がナメたコードを書くことでおれの怒りが有頂天
Gaucheでエラトステネスの篩で素数ストリーム(世間一般のやつより速い)で破壊力ばつ牛ﾝ

(use util.stream)
    
(define (composites s)
  (stream-delay
   (let1 p (stream-car s)
     (stream-cons (expt p 2)
                  (xor (stream-map (pa$ * p) (xor (stream-cdr s) (composites s)))
                       (composites (stream-cdr s)))))))

(define (xor s0 s1)
  (stream-delay
   (let ((x (stream-car s0))
         (y (stream-car s1)))
     (cond
      ((= x y) (xor (stream-cdr s0) (stream-cdr s1)))
      ((< x y) (stream-cons x (xor (stream-cdr s0) s1)))
      ((> x y) (stream-cons y (xor s0 (stream-cdr s1))))))))

(define primes (stream-cons 2 (xor (stream-iota -1 3) (composites primes))))

(define (divisor n m count)
  (if (zero? (modulo n m))
    (divisor (quotient n m) m (+ 1 count))
    (values n count)))

;;素因数分解 英語でいうとファクタライゼーション
(define (factor n strm)
  (let ((p  (stream-car strm))
        (ps (stream-cdr strm)))
    (if (< n p)
      ;;この再帰は早くも終了ですね  
       '()
      (receive (r count) (divisor n p 0)
        (if (zero? count)
          (factor r ps) ;;一度も割れなかった→いくえ不明
          (append (make-list count p) (factor r ps))))))) ;;count回割れた→約数ができる

(define (main args)
  (for-each (compose print 
                     (cut factor <> primes)
                     string->number)
            (cdr args)))

% gosh prime.scm 42
(2 3 7)
% gosh prime.scm 84
(2 2 3 7)

(追記 2009/5/25)

http://twitter.com/mzp/status/1902085754
- おいィ？お前らは今の言葉聞こえたか?
みずぴー日記素因数分解(コードジェネレータ版)
- ほう、経験が生きたな

2009-05-05

nsIInputStreamPumpの非同期処理にジェネレータを使う

こいつの使いかたをググると、onDataAvailableのたびに配列(メッセージキュー)に並べておいて、上から順番に処理するコードがよく見つかる。

Fx Socket - 枕を欹てて聴く

実はAjaxのとき話題になったんだが、ジェネレータで、こういった非同期処理を同期処理のように書ける。

JavaScript1.7 の yield を使って、非同期処理を同期処理のように書く方法

この実験のために、いわゆるechoサーバをlocalhostの60000番ポートに立ててある。

"yield" == "onDataAvailableまでsleep".

2009-04-20

Gaucheでエラトステネスの篩で素数ストリーム(世間一般のやつより速い)

Haskellなどで人気の1行エラトステネスの篩は、アルゴリズム本来の計算量より遅いらしい。

sieve (p : xs) = p : sieve [x | x <- xs, x ‘mod‘ p > 0]

それを受けて、LtUで以下の速いHaskellコードがあった。

primes = 2 : xor [3..] (composites primes)

composites (p:ps) = cs
    where cs = (p*p) : xor (map (p*) (xor ps cs)) (composites ps)

xor (x:xs) (y:ys)  | x==y          = xor xs ys
                   | x<y           = x : xor xs (y:ys)
                   | x>y           = y : xor (x:xs) ys

Gaucheに移植してみた。

(use util.stream)
    
(define (composites s)
  (stream-delay
   (let1 p (stream-car s)
     (stream-cons (expt p 2)
                  (xor (stream-map (pa$ * p) (xor (stream-cdr s) (composites s)))
                       (composites (stream-cdr s)))))))

(define (xor s0 s1)
  (stream-delay
   (let ((x (stream-car s0))
         (y (stream-car s1)))
     (cond
      ((= x y) (xor (stream-cdr s0) (stream-cdr s1)))
      ((< x y) (stream-cons x (xor (stream-cdr s0) s1)))
      ((> x y) (stream-cons y (xor s0 (stream-cdr s1))))))))

(define primes (stream-cons 2 (xor (stream-iota -1 3) (composites primes))))

実行。25番めの素数は97。

(print (stream->list (stream-take primes 25)))
=> (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

Project Eulerに使えるかも。