ラベル Scheme の投稿を表示しています。 すべての投稿を表示
ラベル Scheme の投稿を表示しています。 すべての投稿を表示

2012-03-28

Chicken Schemeのビルド

WindowsでChicken Schemeをビルドするには、CygwinかMinGWのどちらかのgccを使う。Visual Studioはサポートされていない。MinGWを使ってビルドする場合はMSYSは必須ではないけど、いずれにせよGNU makeは必要。以下の例はCygwinを使っている場合。

makeのマクロによって、どういった感じでビルドするか設定をする仕組み。どんなオプションがあるかはREADMEに書いてある。

% tar xf chicken-4.7.0
% cd chicken-4.7.0
% make PLATFORM=cygwin
% !! install

インストールする場所を指定しないと/usr/localにインストールされる。指定する場合はmake PLATFORM=cygwin PREFIX=/opt/chicken-4.7.0といった感じでPREFIXという名前のマクロを指定する。

2012-02-29

末尾再帰で木を走査

何年か前、Scheme:末尾再帰で木をトラバースを読んだときは何をしてるかさっぱりだったんだけど、今なら分かるんじゃないかなー、と思って暇な時間に考えてたら自分でも書けたので、結果に至る過程を記録。

ちょっとアレンジして、木のコピーを例に考える。まずは、普通の再帰で素直に書いてみる。

;; 素朴な木のコピー
(define (copy-tree tree)
  (let loop ((node tree))
    (if (pair? node)
        (cons (loop (car node)) (loop (cdr node)))
        node)))

単純で分かりやすい。これをベースに、継続渡しスタイルを利用して末尾再帰のコードに変換してみる。人力CPS変換。

ちなみに、継続渡しスタイルについての詳しい話や、継続渡しスタイルと末尾再帰(末尾呼び出し)の関係についての説明は、ここではしない。他人に色々説明できるほど深く理解をしているわけじゃないので。詳しく知りたい人は、先人の書いた良い文章があると思うから、そちらを読んで欲しい。例えばThe 90 minute Scheme to C compilerとか。

とりあえず、最初に最終的なコードから。

;; 継続渡しスタイルによる末尾再帰な木のコピー
(define (copy-tree tree)
  (let loop ((node tree)
             (cont values))
    (if (pair? node)
        (loop (car node)
              (lambda (x)
                (loop (cdr node)
                      (lambda (y)
                        (cont (cons x y))))))
        (cont node))))

再帰に馴染みがないと、見た瞬間に心理的に3メートルくらい引くと思う。今あらためて見たら、書いた自分でも1メートルくらい引いた。だけど、段階を踏めばそんなに意味不明でもないので、あまり心配しなくても良い。

最初の素直な再帰の例に戻って、

;; 素朴な木のコピー
(define (copy-tree tree)
  (let loop ((node tree))
    (if (pair? node)
        (cons (loop (car node)) (loop (cdr node)))
        node)))

まず、継続を渡していくための引数が必要になる。ここでは、contという引数を増やす。なお、継続に定番のkとかいう名前を代わりに付けると、そっち方面への馴染みが薄い人への攻撃力をさらに強化できる。継続の中身はまだ考えない。

;; 継続渡しのために引数を増やす
(define (copy-tree tree)
  (let loop ((node tree)
             (cont ))
    (if (pair? node)
        (cons (loop (car node)) (loop (cdr node)))
        node)))

次に、最初にcontに指定する継続を考える。つまり、コピーし終わった木を受け取る、一番最後に実行される継続。copy-treeはコピーした木を返す手続きにしたいので、受け取った値をそのまま返す継続が良い。(lambda (x) x)とかでも良いけど、出来合いで、より省タイプなvaluesを使う。最近はCommon Lispに染まっていたのでidentityを探したが、なかった。

;; 最初に指定する継続はvalues
(define (copy-tree tree)
  (let loop ((node tree)
             (cont values))
    (if (pair? node)
        (cons (loop (car node)) (loop (cdr node)))
        node)))

継続渡しスタイルでは、値を返す代わりに、値を渡して継続を呼ぶので、値を返す部分はすべて継続の呼び出しになる。この例では二ヶ所。

;; 値を返す部分で継続を呼ぶ
(define (copy-tree tree)
  (let loop ((node tree)
             (cont values))
    (if (pair? node)
        (cont (cons (loop (car node)) (loop (cdr node))))
        (cont node))))

そして本題。loopの再帰呼び出しのときに指定する継続について考える。まずは(loop (car node))から。

(loop (car node))の継続、つまり、(loop (car node))が返す値をどうしたいのかという話だけど、ご覧の通り、(loop (cdr node))が返す値とペアを作りたい。そして、それを継続contに渡したい。コードで表現するとこうなる。

;; (loop (car node))の継続
(lambda (x)
  (cont (cons x (loop (cdr node)))))

継続が分かったので、実際のコードに当てはめてみる。

;; (loop (car node))を継続渡しスタイルに変更
(define (copy-tree tree)
  (let loop ((node tree)
             (cont values))
    (if (pair? node)
        (loop (car node)
              (lambda (x)
                (cont (cons x (loop (cdr node))))))
        (cont node))))

同じように、次は(loop (cdr node))の継続についても考えてみる。xとペアを作り、contに渡したいので、

;; (loop (cdr node))の継続
(lambda (y)
  (cont (cons x y)))

となる。これを実際のコードに当てはめると、

;; (loop (cdr node))を継続渡しスタイルに変更
(define (copy-tree tree)
  (let loop ((node tree)
             (cont values))
    (if (pair? node)
        (loop (car node)
              (lambda (x)
                (loop (cdr node)
                      (lambda (y)
                        (cont (cons x y))))))
        (cont node))))

最初に紹介したコードと同じになった。ご覧の通り、二ヶ所ある再帰は両方とも末尾呼び出しになっている。

実際に試してみると、

gosh> (let* ((t1 '(0 1 2))
             (t2 (copy-tree t1)))
        (values (eq? t1 t2) (equal? t1 t2) t2))
#f
#t
(0 1 2)
gosh> (let* ((t1 '(0 (1 2)))
             (t2 (copy-tree t1)))
        (values (eq? t1 t2) (equal? t1 t2) t2))
#f
#t
(0 (1 2))
gosh> (let* ((t1 '(0 ((1) 2) 3))
             (t2 (copy-tree t1)))
        (values (eq? t1 t2) (equal? t1 t2) t2))
#f
#t
(0 ((1) 2) 3)
gosh> 

意図した通りの動作をしてる模様。めでたし。

以下おまけ。Common Lispに(中略)ので、constantlyを探したがなかったため、(lambda _ 1)。

;; 共通のwalkerを定義
(define (tree-walk tree leaf-proc inner-proc)
  (let loop ((node tree)
             (cont values))
    (if (pair? node)
        (loop (car node)
              (lambda (x)
                (loop (cdr node)
                      (lambda (y)
                        (cont (inner-proc x y))))))
        (cont (leaf-proc node)))))

;; 木のコピー
(define (copy-tree tree)
  (tree-walk tree values cons))

;; 葉を数える
(define (count-leaf tree)
  (tree-walk tree (lambda _ 1) +))

;; 葉を文字列に変換した木を作る
(define (copy-tree/string-node tree)
  (tree-walk tree
             (lambda (x)
               (if (null? x) x (x->string x)))
             cons))

関数型便利。

2010-12-06

フィードを表示するWiLiKiのリーダーマクロ

オプション引数の処理がad hocなのは仕様です。

(use gauche.charconv)
(use srfi-1)
(use srfi-13)
(use srfi-19)
(use rfc.822)
(use rfc.http)
(use rfc.uri)
(use sxml.ssax)
(use sxml.sxpath)
(use sxml.tools)
(use util.list)

(define-reader-macro (feed url . args)
  (define *item-max* 10)
  (define *date-format* "~Y/~m/~d")
  (define *item-format* "(~a) ~a")
  (define *ns*
    '((atom . "http://www.w3.org/2005/Atom")
      (openSearch . "http://a9.com/-/spec/opensearchrss/1.0/")
      (georss . "http://www.georss.org/georss")
      (thr . "http://purl.org/syndication/thread/1.0")
      (rss1 . "http://purl.org/rss/1.0/")
      (rdf . "http://www.w3.org/1999/02/22-rdf-syntax-ns#")
      (content . "http://purl.org/rss/1.0/modules/content/")
      (dc . "http://purl.org/dc/elements/1.1/")
      (foo . "bar")))
  (define (w3cdtf->date str)
    (define (df->nano df)
      (string->number (string-pad-right (number->string df) 9 #\0)))
    (and-let*
        ((match (#/^(\d\d\d\d)(?:-(\d\d)(?:-(\d\d)(?:T(\d\d):(\d\d)(?::(\d\d)(?:\.(\d+))?)?(?:Z|([+-]\d\d):(\d\d)))?)?)?$/ str)))
      (receive (year month day hour minute second df zh zm)
          (apply values (map (lambda (i) (x->integer (match i))) (iota 9 1)))
        (make-date (df->nano df)
                   second minute hour day month year
                   (* (if (negative? zh) -1 1)
                      (+ (* (abs zh) 3600) (* zm 60)))))))
  (define *feed-attributes*
    `((atom 
       (converter
        ,(sxpath '(// atom:entry atom:title *text*))
        ,(sxpath '(// atom:entry
                   (atom:link (@ (equal? (rel "alternate"))))
                   @ href *text*))
        ,(sxpath '(// atom:entry atom:published *text*)))
       (date-parser . ,w3cdtf->date))
      (rss1
       (converter
        ,(sxpath '(// rss1:item rss1:title *text*))
        ,(sxpath '(// rss1:item rss1:link *text*))
        ,(sxpath '(// rss1:item dc:date *text*)))
       (date-parser . ,w3cdtf->date))
      (rss2
       (converter
        ,(sxpath '(// item title *text*))
        ,(sxpath '(// item link *text*))
        ,(sxpath '(// item pubDate *text*)))
       (date-parser . ,rfc822-date->date))))
  (define (feed-attr type field)
    (cdr (assoc field (cdr (assoc type *feed-attributes*)))))
  (define (decompose-uri url)
    (receive (_ specific) (uri-scheme&specific url)
      (uri-decompose-hierarchical specific)))
  (define (authority&path?query url)
    (define (path?query path query)
      (with-output-to-string
        (lambda ()
          (display path)
          (when query (format #t "?~a" query)))))
    (receive (authority path query _) (decompose-uri url)
      (values authority (path?query path query))))
  (define (feed-get url)
    (receive (authority path?query) (authority&path?query url)
      (receive (status header body) (http-get authority path?query)
        (unless (equal? status "200")
          (error "フィードの読み込みに失敗しました。ステータスコードは~aです。"
                 status))
        (if (or (null? args) (null? (cdr args)))
            body
            (ces-convert body (cadr args))))))
  (define (feed->sxml feed)
    (with-input-from-string feed
      (cut ssax:xml->sxml (current-input-port) *ns*)))
  (define (feed-type-of sxml)
    (define root-node ((car-sxpath '(*)) sxml))
    (define (rss1?)
      (eq? (sxml:name root-node) 'rdf:RDF))
    (define (rss2?)
      (and (eq? (sxml:name root-node) 'rss)
           (equal? (sxml:attr root-node 'version) "2.0")))
    (define (atom?)
      (eq? (sxml:name root-node) 'atom:feed))
    (cond ((rss1?) 'rss1)
          ((rss2?) 'rss2)
          ((atom?) 'atom)
          (else (error "対応していない種類のフィードです。"))))
  (define converter-title car)
  (define converter-link cadr)
  (define converter-date caddr)
  (define (take-item-max nodes)
    (let1 n (if (null? args) *item-max* (car args))
      (take* nodes n)))
  (let* ((feed (feed->sxml (feed-get url)))
         (type (feed-type-of feed))
         (conv (feed-attr type 'converter))
         (proc (feed-attr type 'date-parser))
         (title (converter-title conv))
         (link (converter-link conv))
         (date (converter-date conv)))
    `((ul ,@(map (lambda (title link date)
                   `(li (a (@ (href ,link))
                           ,(format #f *item-format*
                                    (date->string (proc date) *date-format*)
                                    title))))
                 (take-item-max (title feed))
                 (take-item-max (link feed))
                 (take-item-max (date feed)))))))

W3C-DTF文字列をSRFI 19の日付オブジェクトに変換する関数

WiLiKiのrssmix.scmを参考に、W3C-DTFの文字列をSRFI 19の日付オブジェクトに変換する関数を書いた。

(use srfi-1)
(use srfi-13)
(use srfi-19)

(define (w3cdtf->date str)
  (define (df->nano df)
    (string->number (string-pad-right (number->string df) 9 #\0)))
  (and-let*
      ((match (#/^(\d\d\d\d)(?:-(\d\d)(?:-(\d\d)(?:T(\d\d):(\d\d)(?::(\d\d)(?:\.(\d+))?)?(?:Z|([+-]\d\d):(\d\d)))?)?)?$/ str)))
    (receive (year month day hour minute second df zh zm)
        (apply values (map (lambda (i) (x->integer (match i))) (iota 9 1)))
      (make-date (df->nano df)
                 second minute hour day month year
                 (* (if (negative? zh) -1 1)
                    (+ (* (abs zh) 3600) (* zm 60)))))))

2009-12-12

Common Lispでの標準出力へのバイナリデータの出力

SchemeがR6RSで揉めているので、Scheme Steering Committeeが何らかの成果を出すまで様子見をしつつ、Common Lispを試してみることにした。結構居心地が良い。SLIMEが便利過ぎる。

ただ、Schemeとの違いに戸惑うことも結構あって、今回は標準出力へのバイナリデータの出力について。

Schemeでは、R5RSのポートはテキストとバイナリの区別が無いので、処理系依存にはなるものの、バイナリデータを素直に書き出すことができる。R6RSでは、テキストポートとバイナリポートが定義され、standard-output-portは標準出力に対応するバイナリポートを返し、current-output-portはテキストポートを返すと決められている。R5RSと互換性を取りつつも、バイナリデータもしっかり扱えるようになっていて、R6RSはこういう所が結構上手くできていると感じる。レコードの仕様とか、とても賛成できないようなものも多いけど。

Common Lispでは、ポートではなくストリームになるわけだけど、テキストとバイナリの区別はちゃんとできる。ただ、標準出力に対応するストリームの*standard-output*が処理系依存なので、標準出力にバイナリデータを出力するポータブルな方法がない。ただ、/dev/stdoutを使ったり、処理系の独自拡張を使えば、処理自体はできたりする。

詰めが甘いというか、この辺、もっとどうにかならなかったんだろうか。パイプでデータを受け渡すやり方って、昔から割と良くあるパターンだと思うんだけども。

ちなみに、今回のきっかけは、処理系が対応してない外部文字エンコーディングのCGIでの取り扱い。変換されたバイト列を、標準出力にバイナリデータとして出力すればいいんじゃないかと思ったら、ひと工夫必要だった、という話。

2009-03-27

LarcenyのSRFI事情

Larcenyが準拠しないSRFIの一覧とその理由。2007年の12月から更新がないので多少古いけど、今読んでも十分参考になる。

例えば、

Larceny does not support SRFI 88. Use symbols instead.

Larceny Project. Deprecated SRFIs, Version 3, Dec 2007. At https://trac.ccs.neu.edu/trac/larceny/wiki/DeprecatedSRFIs.

とのことで、キーワードには反対の立場らしい。シンボルを使え、とのこと。確かに、alistとかで簡単に同じことができるし、そういう考え方も理解できる。

他にも、SRFI 18やSRFI 21のマルチスレッドサポートは、POSIXスレッドを前提にしている節があるのでサポートしてない、とか。Larcenyでスレッドを使いたいときは、tasking.schがファイバの実装なので、それを使えってことなんだろうか。

こういう、開発者の考えが詳しく書かれたドキュメントがあると、処理系選びの助けになるし、それに、自分以外の考えを知るのは単純に面白い。

2009-03-22

Scheme処理系に対する心の声

使ってて思ったこと。

Gauche
FFIを、PLT SchemeやLarcenyやIkarus Schemeみたいに動的にやりたい。あのライブラリのあの関数をちょっと使いたい、なんてときにコンパイルやリンクが間に入るとめげる。対応するのは1.0以降とのことで、先は長い。
PLT Scheme
賛成したからには、規格が風化する前に、実用的なR6RS環境を整備して欲しい。独自ライブラリの対応があんまり進んでない気がする。
Larceny
0.97を早く使いたい。それと、Solaris/x86でのネイティブコンパイルに対応して欲しい。Solarisは使うんだけど、うちにSPARCはないんだ。
Ikarus Scheme
早く独自拡張部分の仕様を固めて欲しい。リポジトリにシンボリックリンクとか入っててWindowsで困る。BazaarのWindows用の公式バイナリが使えない。

2009-03-20

Ikarus Schemeのインストール

Cygwin 1.7.0-43にIkarus Schemeをインストールする。

Ikarusは多倍長整数の計算にGMPを使うので、ない場合はインストール。GMPはGCC 4も使っているので、GCC 4がインストールされている環境にはある。今回はGCC 4.3.3でコンパイルしたのでインストールは省略。

FFIを使うために、libffiのインストール。

$ tar xfz libffi-3.0.8.tar.gz
$ cd libffi-3.0.8
$ ./configure
$ make
$ make install

libffi 3.0.8時点での標準では、libffiのヘッダが、PREFIX/includeではなくて、PREFIX/lib/libffi-version/includeにインストールされることに注意。これを忘れていると、Ikarusのconfigureでffi.hが見付からずにエラーになる。

Ikarusのインストール。今回はリポジトリの最新版をチェックアウトしてビルドするので、AutoconfとAutomakeが必要なのに注意。それと、IkarusはBazaarでバージョン管理されているので、チェックアウトにはBazaarが必要。ないときはCygwinのインストーラからインストールする。公式のWindowsバイナリではシンボリックリンクが張れないので、チェックアウトに失敗する。

$ bzr co --lightweight http://www.cs.indiana.edu/~aghuloum/ikarus.dev
$ cd ikarus.dev
$ CPPFLAGS=-I/usr/local/lib/libffi-3.0.8/include ./configure
$ make
$ make install

2009-01-04

and-let*

モナド的な何かに向かってを見て、when-bindみたいなマクロなら、Gaucheにもありそうだと思って探したところ、やっぱりあった。

SRFI 2で提案されているand-let*がそうで、

(let ((the-value (func-which-returns-useful-value-or-#f)))
  (if the-value
    (do-something-based-on the-value)))

こういう処理を、

(and-let* ((the-value (func-which-returns-useful-value-or-#f)))
  (do-something-based-on the-value))

こう書ける。条件式が減らせて見通しも良くなる。

なお、束縛する変数がひとつの場合、例によって、if-let1というGauche独自のマクロがあり、

(if-let1 the-value (func-which-returns-useful-value-or-#f)
  (do-something-based-on the-value))

のように書ける。

ただ、and-let*にしても、if-let1にしても、変数への束縛がある分、参照元の>>=より冗長になってしまうので、そういうパターンがかなりの頻度で現われるなら、束縛まで省略できる手続きを自分で定義した方が良いかもしれない。Haskellを知らない自分としては、>>=だと分かりづらいから、and-composeとかだろうか。

2008-12-06

compose

関数的なプログラミングをしていると、手続きの結果を別の手続きに渡して、さらにその結果を別の手続きに、みたいな処理が日常的に出てくるけど、処理が複雑になると、ネストが深くなったり、見通しが悪くなったりする。

composeを使うと、そういった問題を避けられることがある。

;; 手続きの結果を順に渡す場合
(a
 (b
  (c
   (d
    (e x)))))

;; composeで手続きを合成する場合
((compose a b c d e)
 x)

composeはR5RSやR6RS、SRFIにはない手続きのようだけど、Gauche以外にもPLT Schemeでも使うことができる。

2008-11-26

2008-04-10

cutで記述量を減らす

SRFI-26で定義されているcutを使うと、記述量を減らせて楽。簡単な例を挙げると、

(cond ((#/post-(.+)$/ "tag:blogger.com,1999:blog-blogID.post-postID") =>
       (lambda (m) (m 1))))

というのが、

(cond ((#/post-(.+)$/ "tag:blogger.com,1999:blog-blogID.post-postID") =>
       (cut <> 1)))

と書けたりする。些細な違いかもしれないけど、lambdaなんていくらでも使うものだし、塵が積もって山になる……かもしれない。