tabe

tabe と申します。
http://fixedpoint.jp/

Scheme を知ってプログラマになりました。
Gauche のおかげで C も好きになってきました。

fortune --r6rs

(library (export export) (export export) (import (rnrs)) (define-syntax export (syntax-rules () ((_ import) (import (import import))))))
(import (export export))
(export export)

fortune --scheme

(do()(#f)) ;; a shortest sexp yielding infinite loop

(call/cc (lambda (x) ((lambda (y) (display y) (newline) (x (- 1 y))) (call/cc (lambda (c) (set! x c) 0)))))
 AND
((lambda (x) ((lambda (y) (display y) (newline) (x (- 1 y))) (call/cc (lambda (c) (set! x c) 0)))) call/cc)

((rec (cer rec) (rec cer)) (rec (cer rec) (rec cer)))

((call/cc call/cc) (call/cc call/cc))

(let ((let ((let let ((let (let let () let))) let)))) (eq? let (let)))

((lambda (lambda) (lambda lambda)) (lambda (lambda) (lambda lambda)))

Yet Another bfi

Scheme:Brainfuck を参考にしています。 インタプリタ実行時の tape を3つに分けて、末尾再帰の形にしています。

 (define (bfi iport)
  
  (define (parse iport handler)
    (let loop ((stack '())
               (temp '()))
      (let ((char (read-char iport)))
        (if (eof-object? char)
            (if (null? stack)
                temp
                (handler "unmatched " #\[))
            (case char
              ((#\+ #\, #\- #\. #\< #\>)
               (loop stack `(,@temp ,char)))
              ((#\[)
               (loop (cons temp stack) '()))
              ((#\])
               (if (null? stack)
                   (handler "extra " #\])
                   (loop (cdr stack) `(,@(car stack) ,temp))))
              (else
               (handler "unknown command: " char)))))))
  
  (define (emulate tree head pt tail)
    (if (null? tree)
        (values head pt tail)
        (case (car tree)
          ((#\+) (emulate (cdr tree) head (logand (+ pt 1) #xff) tail))
          ((#\-) (emulate (cdr tree) head (logand (- pt 1) #xff) tail))
          ((#\,) (emulate (cdr tree) head (read-byte) tail))
          ((#\.) (write-byte pt)
           (emulate (cdr tree) head pt tail))
          ((#\<) (if (null? head)
                     (error "pointer underflow: " (cons pt tail))
                     (emulate (cdr tree) (cdr head) (car head) (cons pt tail))))
          ((#\>) (if (null? tail)
                     (emulate (cdr tree) (cons pt head) 0 '())
                     (emulate (cdr tree) (cons pt head) (car tail) (cdr tail))))
          (else (if (= pt 0)
                    (emulate (cdr tree) head pt tail)
                    (receive (h p t)
                             (emulate (car tree) head pt tail)
                             (emulate tree h p t)))))))
  
  (receive (head pt tail)
           (emulate (parse iport error) '() 0 '())
           (values (reverse head) pt tail)))

• teranishi(2005/03/02 05:05:24 PST): ポインタのさす値が最初から 0 の場合には、'[' と ']' の間の処理は 一度も実行されないはずですが、このコードでは必ず一度は実行されてしまいます。

• tabe(2005/03/02 06:36:54 PST): ご指摘ありがとうございます。修正いたしました。

• teranishi(2005/03/05 06:57:40 PST): 個人的な意見ですが、parse が必要以上に複雑に見えます。 以下の書き方ではまずいのでしょうか。 (handler に error 以外が渡される可能性を考え、call/cc を使っています)

  (define (parse iport handler)
    (call/cc
      (lambda (ret)
        (let loop ((top? #t))
          (let ((char (read-char iport)))
            (if (eof-object? char)
              (if top?
                '()
                (ret (handler "unmatched " #\[)))
              (case char
                ((#\+ #\, #\- #\. #\< #\>)
                 (cons char (loop top?)))
                ((#\[)
                 (let ((inner (loop #f)))
                   (cons inner (loop top?))))
                ((#\])
                 (if top?
                   (ret (handler "extra " #\]))
                   '()))
                (else
                 (ret (handler "unknown command: " char))))))))))
  

• tabe(2005/03/05 08:17:00 PST): まったくまずくないです。 S式の構成の点からすると、すぐ上の定義よりもとの定義は複雑だと自分も考えます。 同時に、上の定義による recursive process ともとの定義による iterative process とは、スタック消費の点で有意な違いがあります。 loop の末尾呼び出しによる末尾再帰にした分、もとのは複雑になりました。 -> 末尾再帰のままでより簡潔にしてみました。

• teranishi(2005/03/05 13:08:52 PST): 単に CPS(Continuation Passing Style) もどきの書き方にした理由を聞きたかっただけなのに、 言葉足らずで申し訳ないです。
  たしかに CPS にすればスタックの消費は抑えられますが、 単にスタックに積まれるはずの内容を Closure に移しているだけなので、 結局私のコードでやっている事と変わらないのではないか、というのが質問の主旨です。
  CPS は確かに必要な場面もありますが、 単に見た目を iterative にするためだけに使うべきではないと私は思います。