LISPUSER

LISPMEMOQ: How can you tell when you've reached Lisp Enlightenment?
A: The parentheses disappear. -- Anonymous

(top)  (memo)  (rss)

末尾再帰とループ問題

CL の人が「なんでも再帰」しない理由は、再帰うんぬん以前にループの構文があるからでしょう。 「"Hello" を10 回出力してね繰り返してね」といわれたら〜はいはい繰り返しね、って感じで。

;; すっきり CL
(loop rpeeat 10 do (print "hello"))
(dotimes (i 10) (print "hello"))
;; 偏見に満ちた Scheme
(llet loop ((n 0)) (when (< n 10) (print "hello") (loop (+ n 1))))
(foreach (lambda () (print "hello")) (iota 10))

だいたいのコンパイラだと最適化オプションで ON/OFF できますしね。 毎回完璧に最適化されちゃうとデバッグがなぁ〜

とうわけで、 http://www.cliki.net/Tail%20Recursion の翻訳(CL の人が末尾再帰について一般的に思う事)。

末尾再帰

注意深く書かれた再帰関数呼び出しを、一定のスペース消費のみで実行するという、 Scheme に見られる「厳密な」末尾再帰は、CL には欠けている機能だ。

ほとんどの高性能な CL コンパイラは、すでに目立った末尾呼び出しを除去することができる(個別にマニュアルを参照すること)。 c.l.l のスレッドにおいて、漠然としたアイデアの仮想的標準化作業がおこった。いくつかの要素には定義が必要だ。

CL において "末尾コンテキスト" を構成するものは何か?

良く言われるのが、末尾の "最適化可能な場所" というものだ。 どこが末尾コンテキストであるかという話になると、R5RS の 3.5 節のようなリストが必要になる(ここでは Shcheme の文法のサブセットで場所が定義sされている)。 Scheme の定義は一般的常識になっていると思うが、しかし CL においては"直感的に明らか" ではないかもしれない。 CMUCL のマニュアル 5.5 節では「末尾再帰位置」として語られている しかし、それは CL におけるすべての "末尾再帰位置" / "末尾コンテキスト" の可能性を網羅したものではないようだ。

CMUCL ユーザーマニュアルの説明は、(少なくとも)CMUCL において末尾再帰の最適化が他の機能によって邪魔される状況を説明している。 主に動的束縛の問題でね。 こういった最適化を阻害する状況というのは、Scheme から CL に来た人にとって、ほぼ確実に "直感的にあきらかではない"。

主要な感心は、処理系が :tail-whatever を feature として備え、(optimise (tail-whatever 3)) を最適化を切り替える宣言として 提供し、最低でも有効な末尾コンテキストのリストの要求に従い、プログラマに既知の最適化を無効にする状況のリストを与えることだろう。

そうすると、ただ #- を使うだけで、その機能に依存したコードを締め出せることになる。 もし仲間があなたのコードを危険を冒して準拠していない処理系で動作させたいと思ったら、

ぼくらに必要なのものは?

  • 全てのフォームの末尾コンテキストの仕様

    TODO ってことで :-)

  • 最適化を止めなきゃいけない状況のリスト

    たとえば CMUCL User Manual の 5.5 節をみてみるといいんじゃないかな。

  • *features* エントリ

    :x-tail-rec とかなんかそんな感じ

  • 新しい宣言

    例: Joe Marshall の提案

     (declaim (optimize (dynamic-space 3))) = 可能な末尾再帰の除去をすべて行なう
    
     (declaim (optimize (dynamic-space 2))) = 自己呼び出しやローカル定義 (FLET や LABELS)に限定で、可能ならば末尾再帰の除去を行う
     
     (declaim (optimize (dynamic-space 1))) = 自己呼び出しに限定で、可能ならば末尾再帰の除去を行う
     
     (declaim (optimize (dynamic-space 0))) = 末尾再帰の除去を行わない
    

    というもの。

もういっこ CLiki から紹介

それでも心配症なあなたへ: http://www.cliki.net/org-no-carrier-tail-funcall

posted: 2007/09/16 23:43 | permanent link to this entry | Tags: MISC

(top)  (memo)  (rss)