Hatena::ブログ(Diary)

yukobaのブログ このページをアンテナに追加 RSSフィード Twitter

2008年01月23日 Pythonのyaccを作ったよ

[Python] Pythonのyaccを作ったよ

以下の情報は古いです。 ActionScriptのyaccを作ったよ - yukobaのブログ こっちをご覧ください。

kmyacc が Python に対応していなく、Haskell Hackathon (これ) の運営を考えると、kmyacc が Python, PHP, ActionScript に対応していないと、面倒なことになるので、kmyacc を Python 対応させました。yacc 互換の Python コンパイラコンパイラです。しかし、kmyacc の多言語対応のための工夫は凄いですね。

一部デバッグ系のオプションの switch 文をPython対応していません(Pythonにはswitchがない)。誰かやって!-> 2008/2/20 やりました

ひと段落したら、kmyacc作者さんにパッチを送ります。

SICP p.206

Scheme の SICP(計算機プログラムの構造と解釈) p.206 ですが、

(define (solve f y0 dt)
  (define y (integral (delay dy) y0 dt))
  (define dy (stream-map f y))
  y)

これが、本に載っているソースコードで、最新の Gauche 0.8.12 だと動かないのに、0.8.3 だと動く。ビックリ。y と dy が相互に参照していることが問題です。

(define (solve f y0 dt)
  (define y #f)
  (define dy (stream-map f y))
  (define y (integral (delay dy) y0 dt))
  y)

という感じで、ダミーデータを y に入れておくと、0.8.12 でも動いちゃいます。

(define (solve f y0 dt)
  (letrec
      ((y (integral (delay dy) y0 dt))
      (dy (stream-map f y)))
    y))

が Scheme の仕様の範囲内での書き方です。letrec を使うと、相互に参照できます。注71で動かない処理系がありますと書いてあるけれど、注意書きを書くくらいなら letrec 使おうよ>作者さん。

以下、今日、書いた(打ち込んだ)コード微分方程式 dy/dt = y を、初期値 y(0) = 1 で解き、e を計算します。遅延評価を使って無限の長さのリストを作り出しています。

(define-syntax cons-stream (
  syntax-rules () ((_ a b) (cons a (delay b)))))
(define the-empty-stream '())
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
(define (stream-null? stream) (null? stream))
(define (add-streams s1 s2) (stream-map + s1 s2))
(define (stream-ref s n)
  (if (= n 0)
    (stream-car s)
    (stream-ref (stream-cdr s) (- n 1))))
(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
    the-empty-stream
    (cons-stream
      (apply proc (map stream-car argstreams))
      (apply stream-map
        (cons proc (map stream-cdr argstreams))))))
(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))
(define (integral delay-integrand initial-value dt)
  (define int
    (cons-stream initial-value
      (let ((integrand (force delay-integrand)))
        (add-streams 
          (scale-stream integrand dt)
          int))))
  int)
(define (solve f y0 dt)
  (letrec
      ((y (integral (delay dy) y0 dt))
      (dy (stream-map f y)))
    y))
(stream-ref (solve (lambda (y) y) 1 0.001) 1000)

nishiohirokazunishiohirokazu 2008/01/23 18:58 なになに??

squldsquld 2008/01/24 21:58 yukobaがだんだんlisperになっていく・・・