2014-12-20

SRFI-117の紹介

(LISP Library 365参加エントリ)

今回は最新のドラフトSRFI-117を紹介します。今年一年SRFIの紹介をしてきましたが、今回が最終回になります。そこで現在SRFIのMLで議論されている最新のSRFIを紹介してみたいと思います。

SRFI-117はR7RS-largeにも提案されているSRFIです。このSRFIではリストを用いたキューを定義します。もともとはQueueという名前をそのまま使っていたのですが、議論の中でAPIの説明が実装に踏み込みすぎているという指摘から最近名前をリストキューに変更しました。

まだ最終ではないのでAPIは変わるかもしれませんが、以下のように使うことが可能です。
(import (srfi 117))

(define q (make-list-queue '(1 2 3)))
;; -> queue

(list-queue-front q)
;; -> 1

(list-queue-remove-front! q)
;; -> 1
;; queue will contain only 2 and 3 after this
実装が見えるといったのは、このSRFIではAPIの説明ほぼ全てにオーダーが指定されています。例えば、list-queue-remove-front!はO(1)で終了しなければならず、またlist-queue-remove-backはO(n)で終了する必要があります。

議論の中で話題になったのはコンストラクタAPIで、make-list-queue(元はmake-queue-from-list)がO(1)を指定しかつ与えられたリストが共有されなければならないというもので、これだと処理系が提供するキューがこのSRFIをサポートできないというものです。これにより、キューという一般的な名前からリストキューというより実装を表して名前に変更になりました。もしかしたら将来のSRFIで下請けのデータ構造に依存しないキューのインターフェース的なものが出てくるかもしれません。

ここでSRFIのプロセスとR7RS-largeへの提案のプロセスを簡単に説明します。R7RS-largeはSRFI上で議論されたものがscheme-report.orgのML上で決を採られます。有効票のうち半数以上が賛成であればR7RS-largeに取り入れられます。流れとしては
  1. SRFIに提案する
  2. scheme-report.orgのMLに上記のSRFIをR7RS-largeに提案すると宣言する
  3. SRFIのML上で議論する
  4. 最終SRFIになる
  5. scheme-report.orgで決を採る
というものになります。現状R7RS-largeに提案されたSRFIは111、112、113、114、115、116で、111と112が正式に採用されています。(残りは決を取っていないはずですが、ひょっとしたら見落としているかもしれません。)これらのSRFIはSagittariusでサポートされているので(113、114及び116
は0.6.0以降)興味があれば試してみると面白いかもしれません。

今回はドラフトSRFI-117を紹介しました。

No comments:

Post a Comment