Scheme:多値

Scheme:多値

多値の機能はR5RSになってから追加された、Schemeでは比較的新しい機能だ。 CommonLispやDylanにはある。 純粋な意味での多値、すなわちコンティニュエーションに一つ以上の値が渡るという意味での 多値を実装している言語は、メインストリームではあまり無いと思う。

ただ、多重代入(データストラクチャをdecomposeして複数の変数に代入する機能) があれば、ほとんど多値と同じことができる。RubyやPythonにはこの機能がある。 そのため、多値の必要性に関しては大きな議論があり、Schemeコアな人々の中でも 意見が割れている。最近もcomp.lang.schemeで 大きなスレッドが立った。

個人的には多値はかなり頻繁に利用している。 このページでは主として使いどころに関していろいろ書いてみる。 突っ込み歓迎。 --Shiro

多値の使い方について、興味深いセマンティクスの拡張案が 議論の中から出てきたので、別ページにしておく。(2004/06/05 23:54:57 PDT)

方法 - どうやって使う?

R5RSには、多値を扱う2つのプリミティブが定義されている。 

  (values obj ...)   ; 多値を返す
  (call-with-values generator consumer) ; 返された多値を渡す

はっきり言ってこれだけではえらく使いにくい (プログラムをCPSで書くならともかく)。 実用的には、以下のような構文が使いやすい。全てマクロで実現できるが、 あらかじめ備えている処理系もたくさんある。 

  (receive variables mv-expr
      body ...)
  
  (let-values ((variables mv-expr)
               ...)
      body)
  
  (let*-values ((variables mv-expr)
                ...)
     body)
  
  (define-values variables mv-expr)
  
  (set!-values variables mv-expr)

ここで、mv-expr は多値を返す式。

R5RSの標準関数で多値を返すものは無いが、SRFIにはいくつかある。 SRFI-1のpartition(SchemeCrossReference:partition) は述語とリストを取り、 その述語を満たす要素のリストと満たさない要素のリストの二つを返す。 

  (receive (odds evens) (partition odd? '(2 3 5 6 8 10 13 19))
    (format #t "odd  : ~s~%" odds)
    (format #t "even : ~s~%" evens)
    #f)

   ==> prints 
    odd  : (3 5 13 19)
    even : (2 6 8 10)

他の言語で「多重代入」と呼ばれる形式がある。例えばPerlで 

  sub mv_fun {  .... return (1, 2); }

  my ($x, $y) = mv_fun( ... );

などとする形式だ。実用上はほとんどの場面で、多値の受渡しと同様に 使えるだろう。(意味的には違いがある；「意味」参照)。

現象 - どんな時に使われる?

処理の結果として複数の情報が出て来ることは結構ある。 C言語で、 引数にcallerの変数のポインタを渡してcalleeが値をそこに入れるような 関数を使ったり書いたりしたことが無い、というCプログラマはいないだろう。 いつもいつも必要だというわけではないが、rareというよりは頻繁に出会う。 そんな時に多値が使える。

Shiroが個人的によく使うのは、parsingだ。 例えばlex相当のものを書く時は、「トークンのタイプ」及び「トークンの値」を 返すようにする。 (Cのyylexでは後者はglobal variableを介して受け渡されるね。うげ。) 入力がポートでなく文字列の場合はさらに「マッチしたトークン以降の文字列」も 返すことがある。 文字列のパーズだけでなく、tokenizeされた後でLL構文解析をやったり、 あるいは入力されたS式にマッチングをかける場合なんかでも頻繁に使う。 処理の結果と、その結果として変化したstate (オートマトンのスタックとか) を両方返してやるのだ。state変化を代入に頼らずに実装できるし、 代入をしてないということはバックトラックで別解を探しに行ったりするのも らくちんだ。

あと、本質的に複数の値を返すのが自然な処理というのがあると思う。 上に挙げたpartitionとか、Gaucheの組み込み関数で sys-pipeとか quotient&remainderとかmin&maxとか。いずれも一度の処理で複数の結果が 出て来るものだ。

下は、このWiLiKiで一行を取って、WikiNameの部分を探してformat する関数。トーカナイザ token は3つの値を返し、パーザ find-closerが 2つの値を返す。WikiName中で2重中括弧がネストする場合も考慮しているので、 find-closerの部分は実質push-down automatonになっている。 

 (define (format-line line)
   ;; parse to next "[''''''[" or "]'''''']"
   (define (token s)
     (cond ((rxmatch #/\[\[|\]\]/ s)
            => (lambda (m)
                 (values (rxmatch-before m)
                         (rxmatch-substring m)
                         (rxmatch-after m))))
           (else (values s #f #f))))
   ;; return <str in paren> and <the rest of string>
   (define (find-closer s level in)
     (receive (pre tok post) (token s)
       (cond ((not tok)
              (values #f (tree->string (cons "[[" (reverse (cons pre in))))))
             ((string=? tok "[[")
              (find-closer post (+ level 1) (list* "[[" pre in)))
             ((= level 0)
              (values (tree->string (reverse (cons pre in))) post))
             (else
              (find-closer post (- level 1) (list* "]]" pre in))))))
 
   (list
    (let loop ((s line))
      (receive (pre post) (string-scan s "[[" 'both)
        (if pre
            (cons (format-parts pre)
                  (receive (wikiname rest) (find-closer post 0 '())
                    (if wikiname
                        (cons (format-wiki-name wikiname)
                              (loop rest))
                        (list rest))))
            (format-parts s))))
    "\n")

価値 - どんなメリットがあるの?

多値がSchemeに追加される前に、Schemerはどうやって複数の値を受け渡して いたんだろう。

calleeは値をリストにして返し、caller側でそれを分解する

多分これが一番順当だが、受け側で分解するのはめんどくさいし、 関数リターンの度にこれをやるとなるとinnermost loopで使う時に性能が心配。

cons cellを引数で渡して、calleeがset-car!する

Cのポインタ渡しアプローチ。ぞっとするけど、2番目の値が必要とされる 確率が少ない場合なんかは有効かも。

callerからも見える変数にcalleeがset!する

これもぞっとする。この方法の問題は、バックトラックが必要になる処理なんかで stateの保存を自分でやんなきゃならないこと。

もっとも、最初の方法は次のようなマクロを書けば性能問題以外はずいぶん 楽になる。 

  (define-syntax receive+
    (syntax-rules ()
     ((_ vars expr body ...)
      (apply (lambda vars body ...) expr))))

  (receive+ (a b) (list 1 2) (cons b a)) => (2 . 1)

これは実はPerlなんかの多重代入とほぼ等価。返り値のdecomposeとbindingを 処理系がやってくれるだけで、ずいぶん書きやすくなる。

これができるのに、わざわざ多値を持ち込む「実用上の」理由は、性能だ。 valuesで返される多値はそれ自体はfirst classじゃない。 (各値はfirst classだけど、多値全体としてはそうじゃない)。 多値は、それがvaluesで作られてからcontinutationに渡されるまでしか 総体として存在しないのだ (立場によっては、全く存在しないと言っても良いだろう)。 だから、処理系はvaluesで返される値をヒープアロケートする必要がない。 レジスタに乗り切る分はレジスタで返してもいいし、 continuationへ値をスタック渡しする場合はスタックに積んで返しても 効率が良いだろう。 Kent Dybvigが多値を非常に効率良く扱うコンパイラに関する論文を書いてたと思う。

もちろん、このせいで多値を "performance hack" と考える人も居る。 それに反対する人が持ち出すのが、意味論だ。

意味 - そもそも多値の意味するところは?

Continuation-passingで考えると、関数呼び出しと関数からのリターンには 区別が無くなる。どちらもcallerの用意した値をcallee側の仮引数にbindする だけだ。ところで、Schemeでは2個以上の引数を持つ関数が許されている。 ならば2個以上の値を返す関数も許されるのが、対称性の上からも好ましい。

手続き型言語におけるn-in, 1-outの関数は、処理系の実装の手抜きから生じた ものだと思う。call by referenceやcall by nameの言語ではそれで困ることは なかった (関数は単純な数学関数にさえ使っておけば良かった)。 それがCみたいにcall by valueにして何でも関数だ、と言い出したところではたと 困った。複数の状態を返すにはどうしたらいいか。Cではポインタ渡しで call by referenceをエミュレートした。 C++では参照を言語に持ち込んで call by referenceを正式にサポートした。でも、アセンブラで書いていた時に 多値を複数のレジスタで返すサブルーチンなんて皆書いてたんだよね。

関数型言語では、1-in, 1-outが普通だ。一見複数の引数を渡してるように見えても、 タプルを使ったりcurryingしたりして、少なくとも意味上は1-in, 1-outになっている。 処理系によってはフロー解析して、余分なタプルやクロージャの生成を 行わない最適化を行っているものもあるだろう。

で、Schemeはn-in, 1-outだったのだが、これが「美しくない」わけだ。 せっかくfirst-class continuationまで持ち込んで、関数呼び出しとリターン も意味的に統合したのに。というわけで、R5RSではn-in, m-outになったと。

参考リンク

議論

多値の説明ありがとうございました。

自分でもよく処理結果をリストにしてまとめ返しするんで、こういう手段があるなら使いたいです。関数の戻り値パラメータをそのまま次の関数引数に代入できたら結構使えそう。 というか、入出力が値渡しですべて完結できる(参照元の書き換えなどが必要ない)から、むしろ副作用無しなコードでは自然な解決方法な感じですね。

それはそうと、やはり規格書の２つのインタフェースのみでは少なすぎですよね。あの規格書の説明だけ見て使ってみようという人はいなさそうだし。 実装の面だと、R5RSの要件のひとつのdynamic-wind?はschemeコードによるcall/ccの上書きで比較的容易に追加できるけど、多値は処理系の根本改造が必要なところがネックですね。--moxth

0個の値を取る継続?

多値の意味論はなるほど納得しました。関数の引数に複数の値が許されているなら、複数の値を返す(CPSなら複数の引数で継続を呼ぶ）ことができるほうが、対称性が高いというわけですね。

でもちょっと考えてみると、引数をとらない関数というのもあります。これに対応するのは値を返さない関数だと思うのですが、値を返さない関数という概念はSchemeにないですよね？ Gaucheでは(values)はundefを返すみたいですけど。

Shiro: ありますよ。(values)がそうです。概念的に、継続に0個の値を渡します。 Gaucheで「(values)がundefを返す」というのは不正確で、R5RSでは 「継続が期待している値の個数と違う数の値が渡された場合の動作は未定義」 であり、Gaucheではたまたまた1つの値を期待している継続に0個の値を 渡した場合に、その継続にはundefが渡されている、ってだけです。 (なお、beginのtail以外のcallのように値を捨ててしまう式において、 その継続がいくつの値を取るものかってことはたまに議論になりますが、 それもR5RS的には未定義、実装依存ってことみたいです)

可変長引数を取る継続

hira: R5RS的に、可変長引数のときはどう動くべきなんでしょう。 

    (+ (values 1 2 3)) => 1 or 6
    (+ (values 1 2 3) (values 4 5 6)) => 5 or 21

私はここで6や21が返ってくるものだと思っていたのですが、現状では1や5が返されます。 対称性を問うなら6や21が返ることを期待したいのですが、どうでしょう。 

    (define (values . things)
      (call-with-current-continuation
        (lambda (cont) (apply cont things))))

継続に渡す値の数のミスマッチ

hira: 値を返す・返さないという問題を実際に見てみるとこうなる。 

    gosh> (length (list (values))) => 1 ;つい、コレを0だと期待しちゃう
    gosh> (length (list)) => 0
    gosh> (car (list (values))) => #<undef>
    ;; こうするとなにも返さないし、なにも受け取らない
    gosh> (length (call-with-values (lambda () (values)) list)) => 0
    gosh> (car (call-with-values (lambda () (values)) list))
    => *** ERROR: pair required, but got ()

call-with-valuesに依らない通常の継続は「正確に1つの値を受け取る」のでcalleeは「何も返していない」けどGaucheが裏でこっそりundefを格納せざるを得ないと。 callerが「何も受け取りたくない」なら、やっぱりcall-with-valuesを使わなきゃならんのですね。 しかしめんどくさいなぁ、この仕様。

hira: 多値と継続の仕様について、あれこれ考えてみました。 callerが多値の使用を明示的に許可する、という現在の仕様のほうが堅牢なプログラムを書きやすいのでしょうね。 常時可変継続の世界では、受け取りたい戻り値の数をcallerが明示的に指定しないと動作の保障が難しくなってしまいます。 引数の数を静的にチェックできる範囲も狭くなります。動的の極み、て感じですね。 可変長引数好きの私としては、そんなじゃじゃ馬に乗ってみたい、という気持ちもあるのですが。

Shiro: Common Lispではこうなっています。対称性より 実用性重視って感じですね：

g000001?: Common Lispの場合、0の時はnilを補います。しかし、足りなければnilが補われるという一般化まではできないかと思います。 multiple-value-bindは内部にオプショナル引数が潜んでいるため補っているように見えますが、これはmultiple-value-bindという構文の仕様であって、 

(multiple-value-call (lambda (&optional a b) (list a b)) (values 1)) => (1 nil)

下請けのmultiple-value-callを直接使い必須引数にすれば、個数が合致しないとエラーになります。 

(multiple-value-call (lambda (a b) (list a b)) (values 1)) >> error

多値の引数へのスプライシング

→Scheme:戻り値のスプライシング

継続のarityとCommon Lisp的動作

→Scheme:継続のarity

Strict な言語での多値の意味

nobsun: Scheme のような Strict な言語で n-in 、m-out というのがピンと こないんです。関数適用時にn個の(リダクション済の)値がそろっていなくては いけないなら、1-in だし、values がその引数に Strict なら、やっぱり、 1-out じゃないかなぁと。

プログラムを書くときには、データのパターンマッチの代わり使えるので便利だとは思っていました。util.match があるので、values じゃなくて list でもいいかなと思います。

Shiro: まあ、タプルだと考えればセマンティクスは同じですね。 ただ、静的型付けの無い言語だと、アロケーションの最適化が難しいんですよ。 「valuesじゃなくてlist」だと値を返す度に値の数だけconsが入っちゃいます。 バッチコンパイラで頑張って静的フロー解析すれば削れるところもあるでしょうが、 インタラクティブなやつはきつい。

多値って結局複数の値をリストにして渡すのとどう違うのかなぁと思ってたんですが、 上で nobsun がおっしゃっているのは同じ様な意味でしょうか?
つまり多値で書く方がスマートだったりはするけど、 多値じゃないと書けないってのはあまり無いように思ったんですけど。cut-sea:2004/06/03 14:15:06 PDT

Perl は多値を実装していない？

Inaba? Perlの多重代入は「データストラクチャをdecomposeして複数の変数に 代入する」ことではないと思うのですが？RubyやPythonはそのようですが。

Shiro (2006/02/08 23:37:10 PST): ふーむ。これを書いた当初は、Perlだとarrayで受けられるから、 ということが頭にあったのですが、考えてみたら引数もarrayでまとめて受けられるし、 スタックに積んで返した値を受け側で引数の場合と同様にbindしてると考えれば これはまっとうな多値と言えそうですね。 ということで本ページの冒頭の部分を直しておきました。

Tag: 多値

Topics
Sponsored Links
Search
Recent Changes
More ...
Last modified : 2023/02/07 10:23:43 UTC
WiLiKi 0.8.3 running on Gauche 0.9.15-p2