忍者ブログ

LAL 昭和な気まぐれ飛行機

LALのブログです。 http://eisl.kan-be.com/index.html

FAST局所関数定義

FASTはGCCの拡張機能を利用しています。labelsによる局所関数はGCCの内部関数になっています。通常、C言語では関数内での関数定義はできません。GCCはこれを可能としています。

例えば次の例です。
(defun prime-factors (n)
  (labels ((iter (p x ls z)
                 (cond ((> p z) (cons x ls))
                       ((= (mod x p) 0)
                        (let ((n1 (div x p)))
                          (iter 2 n1 (cons p ls) (isqrt n1))))
                       ((= p 2) (iter 3 x ls z))
                       (t (iter (+ p 2) x ls z)))))
    (cond ((< n 0) nil)
          ((< n 2) (list n))
          (t (iter 2 n '() (isqrt n))))))

この中のiter関数はGCCの局所定義関数に変換されています。そのままでレキシカルな動作をすることができ、実行速度も高速です。

> (prime-factors 2546549873213111)
(26916571079 2557 37)
>

20桁程度の素因数分解であれば瞬時です。
> (time (prime-factors 2546549873213111))
Elapsed Time(second)=0.000000
<undef>
>

GCC拡張機能を使ってことにより、生成されるコードは単純化されましたが、ISLispの仕様を一部、満たせない結果となりました。flet構文はlabelsとは異なるスコープを持ちますが、FASTではどちらも同じです。また、laberlsの内部にさらにlabelsにより局所関数定義をすることができるのですが、その関数名は重複した場合にはエラーとなります。ISLispではこれが許されています。しかし、そのような命名をすると理解しづらいコードになりますから、この程度は合理的な制約だろうと思っています。

また、内部定義関数をfuncallで呼ぶこともできません。その必要性も低いことから、これも合理的な制約の範囲内だろうと割り切っています。


FASTでは整数をCのint型、long型、そしてLisp独自のBIGNUM型で表現し、それらをシームレスにつないでいます。20桁程度ですと、long型をちょっと超える程度ですので、BIGNUMによる速度低下を抑え込めています。int型は即値としており、セルを消費しません。
PR

コメント

プロフィール

HN:
笹川
性別:
非公開

P R