Scheme:LazyEvaluation

nobsunで出たアイディア

Gaucheの起動オプションで、評価方式を普通のEagerではなくLazyに 切り替えられたりするとうれしいなぁ（これじゃ、ぜんぜんSchemeじゃないか。^^;)

を発展させてってみよう、のコーナー。

• いきなり全部の評価をLazyに切替えた場合、セマンティクスが consistentなものになるのかどうかちょっと心配。

• Functionalに書くぶんには気にしなくて大丈夫でしょうが、 入出力のような副作用のある複数の式の評価順が変わらないかどうかを 検証しておくことが必要かもしれません。 --nobsun
• もともとSchemeでは引数の評価順は定められていないので、 そこは心配無いですが、beginやlet*なんかはまずいですね。 --Shiro
• beginは継続、let* はletの入れ子に置き換えるのかなあ。--nobsun
• letの入れ子じゃまずいっす。Schemeでは次のように書くと、 a, b, c にそれぞれ入力からの1文字目、2文字目、3文字目が入ることが 保証されます。

              (let* ((a (read-char))
                     (b (read-char))
                     (c (read-char)))
                 ...)

• Lazyにしちゃうと、a, b, cのうちどの値が最初に使われるかによって 結果が違ってきちゃうんです、よね？
  • let は値が利用されるかどうかとは関係なく、束縛をつくるようにすれば、束縛を作る順が保存されていればどの順で値が評価されても、結果はおなじになります。上の例が下と同じセマンティックスをもつとすれば、a, b, c にそれぞれ入力からの1文字目、2文字目、3文字目が入ることが保証されます。--nobsun
  • ちょっと不正確かもしれません。束縛が起るタイミングは適用が評価されるときで、そのとき、(read-char)の値は評価されないが、動作は起るという規定が必要ですね。たぶん^^;2002/01/18 07:35:03 PST

              (let ((a (read-char)))
                (let ((b (read-char)))
                  (let ((c (read-char)))
                    ...)))

• やさしいHaskell入門を 読んできました。ここで出されているletはHaskellでのdoにあたる、と解釈して よろしいでしょうか。Haskellのletの中ではモナドは使えない、と理解したのですが。--Shiro

• Haskell の do はシンタクスシュガーみたいなもので、 実体はlambda 束縛のジェネレータのようなものですので、Haskell の do は let の入れ子と看倣せます。--nobsun

              do p <- e1; e2    ===  e1 >>= ? p -> e2
                                === ((lambda (p) e2) (selector e1)) (厳密には違うけど)
                                === (let ((p (selector e1))) e2)    (厳密には違うけど)

• ううむ。しかしλ束縛はlazyに評価されるのですよね。lazyなSchemeにおいて、 以下の式は4を返すべきだと思うんですが、するとxに束縛する時点で(bot)は 評価されないわけですよね。でもここが(read-char)だと評価されなければならない。 すると、各式についてそれをlazyに評価すべきかeagerに評価すべきかをコンパイラが 知っていて切りかえればいいのかな。 --Shiro

              (letrec ((bot (lambda () (bot))))
                ((lambda (x) 4) (bot)))

• ええーと。Haskell では値の評価と動作の起動は別ものということになっています(たぶん^^;)。動作については、first-class ではないです。Haskell は入出力については IO という抽象型のなかに動作を隠蔽してしまいます。Scheme の構文では隠蔽が難しいかな。--nobsun

• 納得です。要は処理系が、あるフォームを見て動作が必要なかどうかを 判断できればいいわけですな。Schemeには型宣言が無いので、 何らかの方法で動作が起こることを明示してやれば良いと。--Shiro

• 純粋に関数的にやるのなら、ジェネレータの中に状態を持たせるのは そもそも間違いで、ジェネレータは状態オブジェクトを取り、最初の結果と 次の状態の２つの値を返すようにするのがスジなのかしらん。 Haskellで入出力をどう扱っているか知らないのでちょっと勉強してみます。 --Shiro

              (let*-values ((a state1) (read-char-functional state0))
                            (b state2) (read-char-functional state1))
                            (c state3) (read-char-functional state2)))
                 ...)

• Haskellでは束縛の順序を利用することで、副作用を取り扱います。--nobsun

• ライブラリかなんかを使って、delayとforceが自動的に挿入されるように なるといいかも。

• delayとforceの挿入はコンパイル時の問題だから、むしろ コンパイラへのhookを書けるようにしておくと良いのか? コンパイラ自身がobject systemを使って拡張できるようになってたら おもしろいかも。

• いくつかのScheme実装では、プリミティブ関数が引数にpromiseを 取ったら自動的にforceする (implicit force)ようになっている。 でもこれを組み込みにしてしまうのは遅くなりそうでやだなあ。

• 評価順を、作用順から正規順に変更することになるので、promiseやforceを 利用するのではなく、VMそのものを切り替えるようにするほうが筋かもしれませんねぇ。--nobsun
• GaucheではVMが実行する時点ではかなり基本的なインストラクションに 落ちているので、あまり変えようがない気もします。値を必要とするか どうかはプリミティブ側でないとわからないですし。 効率を考えるとやっぱりコンパイラ側での式変換が肝になりそう。-- Shiro
• VMのインストラクションセットそのものを別のもの(つまり別のVM)になるのではないかと想像したのですが、どうでしょう。そういえば、最近、"Implementation of Functional Programming Languages" が復刻あるいはweb公開されたような噂があったと思ったんだけど。 見つからないなあ。--nobsun

• "Implementation of Functional Programming Languages"は、microsoftにあります。Simon Peyton Jonesさんってmicrosoftに勤めてるのかな？Simon Peyton Jones"Implementation_of_Functional_Programming_Languages"

• Simon Peyton Jones は Haskell 業界:-)のおん大将ともくされる人で、1,2年前に Glasgow 大学から Microsoft Research Center に移ったようです。Haskellが .NET Framework をサポートする言語のひとつにリストされるのはそのためかも :-)--nobsun

• 横槍ですみません。最近、「プログラマのためのＣＯＭＭＯＮ　ＬＩＳＰガイド」Ｄｅｂｏｒａｈ　Ｇ．Ｔａｔａｒ著 丸善出版という本を本屋さんで立ち読みしました。この本の中にmacroの良い所は、非正格な所だという風に書いていたと思います。(たしかif文と作るためにmacroを使っていたような気がします。) たしかにmacro本体の評価(展開？)はEagerですが、macro本体の評価の順序に比べ引数の評価はLazyですよね。でもmacroが非正格と言われても、どうも私はしっくり着ません。不躾で申し訳ありませんが、nobsunのmacroの非正格性？についての、ご意見頂けるとうれしいです。

• (f _|_) ==> _|_ なら f は strict 、(f _|_) ==> 確定した値　なら、f は non-strict といいます。処理系が non-strict であるということは、non-strict な関数を 定義できるということです。macro が non-strict であるという謂いは、non-strict な適用形式を書くことができるという意味ではないかと思います。私自身は、macro の 本質は、call-by-name　だと思っているので、「macro は non-strict」という謂いには 違和感があまりありません。--nobsun (2002/05/07 15:03:07 PDT)

• さっそくのレス有難うございます。私の違和感の原因は、私がLispのmacroをちゃんと理解していないからの様ですね。。Cのプリプロセッサによるmacroの呪縛から私は逃れられてないようです。もっと勉強します。

• 私も Lisp の macro をちゃんと理解しているわけではないですが、通常のstrict言語をつかって いると、一連の操作手続きを抽象化するのに、call-by-name の機構が欲しいことがよくあります。 この要求に応えてくれるのが、macro かなと思っています。これは、C のプリプロセッサマクロでも 同様ではないかと感じますし、実際そういう使いかた私はよくやります。C でプログラミングをするとき、 変数名やラベル名を手続きに渡したいことってありませんか？ --nobsun

• Lispはある意味、call-by-nameの処理系(macro)とcall-by-valueの処理系という ふたつの言語処理系が同居しているものと言えるかもしれませんね。 --Shiro (2002/05/08 17:26:12 PDT)

• ご存知のことでしょうが、Cではmacroの展開はプリプロセッサによって行われ、極めて静的動作です。そしてコンパイル時1回しか評価されません。私の読んだ資料(以下のURL参照してください。M.Hiroiさんに感謝)読んだ限りでは、Lispのmacroは評価させるたびmacroの本体が展開されるように感じます。CとLispではmacroが評価されるタイミングが違うようなので同じものとはいえないのでは？と思っています。私はSICP第2版を買い、最近Lisp(というかScheme)を勉強し始めたばかりの超初心者です。私のLispのmacroに対する知識は、参照した資料と前に挙げた本を読んだ程度の知識しかありません。ですのでチャンとした質問ではありません。Lispの処理系での動作を確認してみたいと思っています。こんな、あやふやな質問をして申し訳ありませんでした。

• http://www.geocities.co.jp/SiliconValley-Oakland/1680/rakup/rakup20.html
• http://www.geocities.co.jp/SiliconValley-Oakland/1680/xyzzy_lisp/xyzzy27.html

• いや、コンパイルする処理系ではLispのmacroもコンパイル前に一回評価するだけです。 そのためオプティマイズの目的にもよく使われます。 インタプリタでは毎回評価する処理系もあるかもしれませんが(昔のemacsも バイトコンパイルしないと毎回評価していたような)。 Cのマクロと違っていかなるソースコードトランスレータも書けてしまうため、 マクロ内でデータフロー解析までやってソースコードレベルでオプティマイズ してしまうといったテクニックもあったようです。 あと、あやふやでも何でもどんどん書き込んで頂けると話題が発展して面白いので、 また何か気になったら書き込んで下さい。--Shiro (2002/05/09 12:13:42 PDT)

横槍の横槍ですみません。macroの話題がでてきたところで便乗して...ひとつ、質問させて下さい。 普段は、lua使いなので、schemeについてはいまひとつ？なのですが、正規表現を使える macro の処理系というのは存在しないのでしょうか？　あそこまで強力にするのであれば、lexer並の機能を期待してしまうのは自然なことだと思うのですが。ちなみにgemaのような仕様 をscheme風に整理したものを想像しています。 あっ”Scheme:マクロの効用”の方に書くべきだったか。--toki?

• Scheme:パーザジェネレータ の方に議論を移します --Shiro(2002/05/21 13:24:17 PDT)

teranishi: 動くものが無いと理解できない人間なので、とりあえず作ってみました。

#!/bin/sh
:; exec gosh -fno-inline -- $0 "$@"

(define-module lazy
  (use srfi-1)
  (use util.match)
  (export lazy-convert replace-primitive! force-all)
  (define *lazy-table* (make-hash-table))
  (define (lazy-convert expr)
    (let ((expr (macroexpand expr)))
      (cond ((or (symbol? expr) (identifier? expr)) (list force expr))
            ((literal? expr) expr)
            ((hash-table-get *lazy-table* (unwrap-identifier (car expr)) #f) => (cut <> expr))
            (else `(,(lazy-convert (car expr)) ,@(map delay-convert (cdr expr)))))))
  (define (delay-convert expr)
    (let ((expr (macroexpand expr)))
      (cond ((literal? expr) expr)
            ((eq? (unwrap-identifier (car expr)) 'lambda)
             ((hash-table-get *lazy-table* 'lambda) expr))
            (else `(delay ,(lazy-convert expr))))))
  (define (divide-rest-arg lst)
    (do ((rest lst (cdr rest)) (prev () (cons (car rest) prev)))
      ((not (pair? rest))
       (values (reverse! prev) rest))))
  (define-macro (replace-primitive! spec . ret)
    (receive (prev rest) (divide-rest-arg (cdr spec))
      (let ((original (gensym))
            (vars (map (lambda _ (gensym)) prev))
            (ret (if (null? ret) values (car ret))))
        `(set! ,(car spec)
           (let ((,original ,(car spec)))
             ,(if (null? rest)
                `(lambda ,vars
                   (,ret (,original ,@(map list prev vars))))
                (let ((rest-var (gensym)))
                  `(lambda ,(append! vars rest-var)
                     (,ret (,apply ,original ,@(map list prev vars)
                                   (,map ,rest ,rest-var)))))))))))
  (define (force-all expr)
    (let ((forced ()))
      (let loop ((expr expr))
        (cond ((promise? expr) (loop (force expr)))
              ((and (pair? expr)
                    (not (memq expr forced)))
               (push! forced expr)
               (set-car! expr (loop (car expr)))
               (set-cdr! expr (loop (cdr expr)))
               expr)
              (else expr)))))
  (define (literal? expr)
    (or (not-pair? expr)
        (eq? (unwrap-identifier (car expr)) 'quote)))
  (define (unwrap-identifier expr)
    (if (identifier? expr)
      (unwrap-syntax expr)
      expr))
  (hash-table-put! *lazy-table* 'lambda
    (lambda (expr)
      `(,(car expr) ,(cadr expr) ,@(map lazy-convert (cddr expr)))))
  (hash-table-put! *lazy-table* 'if
    (lambda (expr)
      `(,(car expr) ,@(map lazy-convert (cdr expr)))))
  (hash-table-put! *lazy-table* 'and (hash-table-get *lazy-table* 'if))
  (hash-table-put! *lazy-table* 'or (hash-table-get *lazy-table* 'if))
  (hash-table-put! *lazy-table* 'define
    (match-lambda
      ((name (fun . args) body ...)
       `(,name (,fun . ,args) ,@(map lazy-convert body)))
      ((name var val)
       `(,name ,var ,(delay-convert val)))))
  (hash-table-put! *lazy-table* 'begin (hash-table-get *lazy-table* 'if))
  (hash-table-put! *lazy-table* 'let
    (lambda (expr)
      `(,(car expr) ,(map (lambda (expr) `(,(car expr) ,(delay-convert (cadr expr)))) (cadr expr))
                    ,@(map lazy-convert (cddr expr)))))
  (hash-table-put! *lazy-table* 'define-macro values)
)
(import lazy)
(replace-primitive! (null? force))
(replace-primitive! (car force) force)
(replace-primitive! (cdr force) force)
(replace-primitive! (zero? force))
(replace-primitive! (+ . force))
(replace-primitive! (- . force))
(replace-primitive! (write/ss force-all . force))
(define load
  (lambda (file)
    (call-with-input-file file
      (lambda (port)
          (read-eval-print-loop
            (lambda () (read port))
            (lambda (expr env) (eval (lazy-convert expr) env))
            (lambda _ #f)
            (lambda _ #f))))))

(define (main args)
  (read-eval-print-loop
    read
    (lambda (expr env) (eval (lazy-convert expr) env))
    (lambda args (for-each (lambda (expr)
                             (write/ss expr)
                             (newline))
                           args))))

実行例

gosh> (define (zip-with fun lis1 lis2)
        (if (or (null? lis1) (null? lis2))
          '()
          (cons (fun (car lis1) (car lis2))
                (zip-with fun (cdr lis1) (cdr lis2)))))
zip-with
gosh> (define (take lis k)
        (if (zero? k)
          '()
          (cons (car lis)
                (take (cdr lis) (- k 1)))))
take
gosh> (define ones (cons 1 ones))
ones
gosh> (take ones 10)
(1 1 1 1 1 1 1 1 1 1)
gosh> (define nums (cons 1 (zip-with + ones nums)))
nums
gosh> (take nums 10)
(1 2 3 4 5 6 7 8 9 10)
gosh> (define fibs (list* 1 1 (zip-with + fibs (cdr fibs))))
fibs
gosh> (take fibs 10)
(1 1 2 3 5 8 13 21 34 55)

ただ、srfi-1の関数の定義を入力しても、まともに動かない場合が多々ありました。 たとえば、以下の関数は無限ループに陥ります。 (このような再帰は、append-mapやany,everyで使われています)

gosh> (define (error-fun elt rest)
        (if (null? rest)
          elt
          (cons elt (error-fun (car rest) (cdr rest)))))
error-fun
gosh> (define ones (cons 1 (error-fun (car ones) (cdr ones))))
ones
gosh> (take ones 10)

• Shiro: SRFI-45で述べられている 問題かな：

  Expressing the above algorithm in terms of {delay, force} in fact does not correctly capture common notions of call-by-need evaluation semantics.

• teranishi: SRFI-45 に書いてある内容が理解できなかったのですが、 多分違う問題だと思います。
  (cdr ones) を求めるためには、(error-fun (car ones) (cdr ones)) の値が必要です。 error-fun の関数定義を見ると、この関数の評価には (null? rest) の値が必要だと言う事が分かります。 この場合、rest は (cdr ones) なので、 (cdr ones) の値を求めるのに (cdr ones) の値が必要となってしまいます。
• teranishi: ほかには、リストを逆順に生成して最後に reverse して 返す関数(filterなど)も、無限リストに対しては動きません。 あとは、当然ながら、副作用のある関数(append-reverse!など)はほぼ全滅でした。
  評価を Lazy に切り替える場合は、使用するライブラリも切り替える必要がありそうです。
• nobsun: 上の ones の定義なら、(take ones 10) が無限ループに落ちるのは 正しい動作だと思います。無限リストに reverse を適用したときに、無限ループに 落ちるのも正しい動作だとおもいますが、どの挙動を期待されますか？
• Shiro: ここはつまり、srfi-1等のリストライブラリで無限リストも扱えるように するには、現在の末尾再帰＋累積変数＋reverseじゃだめで、stream-filterみたいに 返す方もlazy listになってないとだめだなぁ、と。セマンティクスをeagerからlazyに 変えることは、単に評価機レベルの切替えでは済まず、ライブラリから何から 全部見直さないとならない、ってことがポイントなんじゃないかと。
• teranishi: srfi-1 の関数を Lazy な環境に移植する時に苦労した点を 書き連ねた感じです。結論は、Shiroさんのおっしゃる通りです。 分かりにくくてすみません。
  本当は、上で話題になっている入出力を実際に実装するとどうなるかに興味があったのですが、 使用するライブラリの移植で力つきました。
• ねるWiki:ねる: 横から失礼します。結局ライブラリを書き換えなきゃいけないなら、SICPのSTREAMSライブラリの拡充版がGaucheにあれば便利かなぁという気がします。Scheme的にはLazy評価環境とEger評価環境をうまくまぜることができればうれしいですよね。基本的にはまぜるな危険だとおもうので難しそうですが...
• Shiro: srfi-40を そのうち実装するつもりです。

teranishi(2005/03/26 02:35:26 PST):上で言っていた入出力の話を少し。

              (let* ((a (read-char))
                     (b (read-char))
                     (c (read-char)))
                 ...)

で文字の順番を保証する方法ですが、begin が使えるなら

              (let* ((a (read-char))
                     (b (begin a (read-char)))
                     (c (begin b (read-char))))
                 ...)

と書き換えれば、特別な事をしなくても保証できると考えました。

しかし、この let* 文の中だけの実行順を保証できても、 let* 文自体がいつ実行されるかが確定しなければ、 実行開始から数えて何番目の文字が読まれるかは分からなくなってしまいます。 つまり、この let* を含む関数も実行順を保証しなければならないという事です。 さらに let* を含む関数を呼び出す関数も実行順を保証しなければならず・・・ と考えていくと、結局実行開始から let* に至る全ての関数で 実行順を保証する必要がある事になります。

すべての実行順を手動で保証していくのは大変なので、 以前いじっていたモナドを使う事を考えました。

(define (return val)
  (lambda (prev)
    (begin prev val)))

(define (>>= m f)
  (lambda (prev)
    (let ((new-prev (m prev)))
      ((f new-prev) new-prev))))

要するに、次の処理を実行する前にやっておかなければならない処理 (prev) を 持ち回って(>>=の処理)、順番を保証したい処理をする前に prev を実行することを 保証するのです(returnの処理)。 ついでに、read-char のように実行順を必ず保証したい関数は、 この枠組みでしか呼び出せないようにしてしまいます。

(define (read-charM)
  (lambda (prev)
    (begin prev (read-char))))

あとは、Monadic Programming in Schemeの LetM* や beginM を使えば、 実行順の保証が楽にできると考えたのです。

(letM* ((a (read-charM))
        (b (read-charM))
        (c (read-charM)))
  ...)

しかし、この枠組みで書いたコードは、「let* の束縛を eager に評価する」 というルールを追加しただけの場合と見た目がほとんど変わらないので わざわざこんなことをする必要は無かったかも・・・

teranishi(2005/03/29 19:55:08 PST):とりあえず実装。

(define (return val)
  (lambda (prev)
    (begin prev val)))

(define (>>= m f)
  (lambda (prev)
    (let ((new-prev (m prev)))
      ((f new-prev) new-prev))))

(define (read-charM)
  (return (read-char)))

(define (write/ssM val)
  (return (write/ss val)))

(define-macro (>> m1 m2)
  `(>>= ,m1 (lambda (,(gensym)) ,m2)))

(define fail error)

(define-macro (letM binding expr)
  `(>>= ,(cadar binding) (lambda (,(caar binding)) ,expr)))

(define-macro (letM* bindings expr)
  (if (null? (cdr bindings))
    `(letM (,(car bindings)) ,expr)
    `(letM (,(car bindings))
       (letM* ,(cdr bindings) ,expr))))

(define-macro (beginM . body)
  (if (null? (cdr body))
    (car body)
    `(>> ,(car body) (beginM ,@(cdr body)))))

実行例

gosh> ((letM* ((a (read-charM)) (b (read-charM))) (beginM (write/ssM b) (write/ssM a))) #f)xy
#\y#\x0

Tags: Haskell, Lazy