Scheme:Brainfuck

Brainfuck を Scheme で実装してみる企画

bf のサンプルコード(上記ウェブページから拾ってきたもの)

hello.b

ハローワルド

quine.b

自己コピー(ちょっと重い)

quine2.b

その２(結構重い)

• インタプリタ
• 遊び方
• 副作用無しバージョン
• コンパイラ
• ベンチマーク
• Scheme:Brainfuck:別解

インタプリタ

skimu: とりあえず、モトネタです. (ソース bfi.scm)

• アドバイス、突っ込み大募集！
• obscure/esoteric バージョン募集中。

遊び方

 % gosh bfi.scm hello.b
 Hello Wold!
 % gosh bfi.scm quine.b > q.b
 % gosh bfi.scm q.b > p.b
 % cmp p.b q.b

• Shiro: 元の仕様だとバイトの値が256でwrap aroundしないとまずいような気がします。
  • skimu: その通りなんですが、いくつか実装をみたところまちまちなんですね。　C で書かれたリファレンスインプリメンテーションは 0 から 100 までで、これだと quine が動かない...

副作用無しバージョン

Shiro: bfi を次の3つの関数に置き換えます。 このバージョンでは、抽象的な「メモリ」の各バイトがクロージャで表現されています。 また、副作用を一切用いていません。変更が起こる度に新たなクロージャが作成 されます。 ちょいとトリッキーなのは、各「バイト」は直前と直後の「バイト」へのリンクを 保持しているため、隣の「バイト」がアップデートされた時は自分もアップデート (リンクを新しくした新たなクロージャを作成)しなければならないことです。 これは、オンデマンドで行われます (set-prev, set-nextコマンド)。

• skimu: をを、かっこいい。しかも速い。こういうコードをサクッとかける様になりたいです。
• Shiro: おや、速くなるとは思っていなかったです。なぜだろう。 なお、このバージョンは多くの場合、更新前の「バイト」へのリンクがどこかに残ってしまうので、ヒープを馬鹿喰いする可能性があります (一度使用済みメモリの最初から最後までをvisitすれば古いリンクは消えてGCされますが)。

 (define (make-pointer prev next value)
  (define (pointer cmd arg)
    (case cmd
      ((#\>) (if next
                 (next 'set-prev pointer)
                 (make-pointer pointer #f 0)))
      ((#\<) (if prev
                 (prev 'set-next pointer)
                 (error "pointer undeflow")))
      ((set-prev) (if (eq? prev arg)
                      pointer
                      (make-pointer arg next value)))
      ((set-next) (if (eq? next arg)
                      pointer
                      (make-pointer prev arg value)))
      ((#\+) (make-pointer prev next (+ value 1)))
      ((#\-) (make-pointer prev next (- value 1)))
      ((#\.) (write-byte value) pointer)
      ((#\,) (make-pointer prev next (read-byte iport)))
      ((loop) (if (= value 0)
                  pointer
                  ((bfi2 arg pointer) 'loop arg)))
      ))
  pointer)

 (define (bfi2 codes pointer)
  (cond
   ((null? codes) pointer)
   ((pair? (car codes))
    (bfi2 (cdr codes) (pointer 'loop (car codes))))
   (else
    (bfi2 (cdr codes) (pointer (car codes) #f)))))

 (define (bfi codes)
  (bfi2 codes (make-pointer #f #f 0)))

コンパイラ

skimu: scheme->bf はかなーりつらいのでとりあえず bf->Scheme です。:-) (ソース bfc.scm)

• write-byte と read-byte を char->integer かなんかを使って書き換えれば、R5RS に準拠します。

ベンチマーク

  wugga% time gosh bfi.scm quine.b > /dev/null
  real    0m2.803s
  user    0m2.350s
  sys     0m0.140s
  wugga% time gosh bfi-no-side-effect.scm quine.b > /dev/null
  real    0m1.838s
  user    0m1.460s
  sys     0m0.150s
  wugga% gosh bfc.scm quine.b > bq.scm   
  wugga% time gosh bq.scm > /dev/null
  real    0m0.575s
  user    0m0.380s
  sys     0m0.120s

Scheme:Brainfuck:別解