トップ «前の日記(2012-01-08) 最新 次の日記(2012-02-03)» 編集

Route 477



2012-01-10

[scheme] R6RS Enumerationsに関する調査

というメモが見つかったので貼っておく。


Recordsほどではないがなんか無駄にややこしいような…

参考

ypsilonの実装

 (define-struct enum-type (universe members indexer constructor))
 (define-struct enum-set (type members))

各enum-setはmembers(シンボルのリスト)とtype(enum-type)をもつ。

各enum-typeはuniverse(母集合となるシンボルのリスト)、members(??)、indexer(シンボルから番号を返す手続き)、constructor(シンボルのリストからenum-setを作る手続き)をもつ。

よって、各enum-setは自分の母集合であるシンボルのリストを(enum-type経由で、間接的に)もつ。これを元文書ではenum-setの「universe」と呼んでいる。

enum-setはfirst classのデータ構造である。例えばypsilonでは「#<enum-set (a b c d)>」のように表示される(ypsilonの場合、属するtypeは表示されない)。Larcenyだと単に「#<record enum-set>」のように 表示される。

しかしやっかいなことに、enum-typeはfirst classのデータ構造*ではない*。R6RS Enumerationsでは、各enum-setに対しそのenum-typeを取得するようなAPIは用意されておらず、 Schemeの世界に取り出すことはできない。あるenum-setの母集合を知りたいときは、(enum-set-universe s) として、「sと同じenum-typeに属する、母集合の全ての要素を含んだenum-set」を得るという仕様になっている。また2つのenum-setが同じenum-typeに属しているかどうかを知る方法もない*1

さてそうすると、「どうやってあるenum-typeのenum-setを作るのか?」という疑問がわく。答えは以下。 define-enumerationでenum-typeを定義した場合は、第三引数で指定した名前がenum-setのコンストラクタ(enum-setを生成する手続き)になる。

(define-enumeration color
  (red green black white)
  color-set)

(color-set red black)

もう一つ低レイヤのAPIがあって、(enum-set-constructor s)とすることで、「sと同じenum-typeのコンストラクタ(enum-setを生成する手続き)」を取得することができる。 また(make-enumeration '(a b c))で、universeが(a b c)であるような新しいenum-typeを定義することができる。ただし返り値はenum-typeではなく(前述のようにenum-typeはfirst classではない)、#<enum-set (a b c)>が返る。

制限

以下の操作では、2つのenum-setは同じenum-typeに属していなければならない。

  • (enum-set-union es1 es2) -> enum-set
  • (enum-set-intersection es1 es2) -> enum-set
  • (enum-set-difference es1 es2) -> enum-set

以下の操作では、2つのenum-setは別のenum-typeであってもよい。

  • (enum-set=? es1 es2) -> bool
    • シンボルの集合として等しいかを返す。
    • 両者が別のenum-typeであっても、シンボルの集合として等しければ#tが返る。
  • (enum-set-subset? es1 es2) -> bool
    • es1がes2のサブセットであるとき#tを返す。
    • 両者が別のenum-typeであるときは、universeについても判定が行われる(即ち、es1のuniverseがes2のuniverseのサブセットでなければ#tが返らない)。
  • (enum-set-projection es1 es2) -> enum-set
    • これはむしろes1にes2が異なるタイプを指定するものかな。

マクロ

R6RS Enumerationsはマクロ(構文)を一つ定義する。define-enumerationがそれだ。

ypsilonでは、(define-enumeration type-name (symbol1 ...) constructor-syntax) をsyntax-rulesでdefineとdefine-syntaxに展開し、 展開されたdefine-syntaxではsyntax-caseを使うというちょっとテクニカルな実装になっている*2

まずdefineでconstructorという一時変数にコンストラクタを束縛する。

       (begin
         (define constructor (enum-set-constructor (make-enumeration '(symbol1 ...))))

次に(color red)のような構文を定義する。これが「マクロ展開時に引数がuniverseに含まれているかのチェックを行うこと」という定義があるので、syntax-rulesではなくsyntax-caseを使わないと書けないんだよね。symbol2はこの例でいう'red。(symbol1 ...)はenum_type定義時のuniverse。(_ symbol2) はパターンマッチで、(type-name symbol2)と書いてもいいんだけど、このsyntax-caseが使われる時点で 最初の要素はtype-nameにマッチするに決まっているから、ワイルドカード「_」を指定している。syntax-case/rulesではおなじみのイディオム。

(color red)は何をするかというと、単に'redを返す。それだけ。 ただし引数がuniverseに入ってるかはチェックするので、(color asdf)とかはエラーになる。 (正直使いどころがよく分からない…(color purpel)みたいにtypoしたときにエラーになるから 安全ですよ、ということかな)

         (define-syntax type-name
           (lambda (x)
             (syntax-case x ()
               ((_ symbol2)
                (or (memq (syntax->datum (syntax symbol2)) '(symbol1 ...))
                    (syntax-violation 'type-name "excpectd symbols which belong to the universe" x))
                (syntax 'symbol2)))))

最後に(color-set red black)のような構文を定義する。

         (define-syntax constructor-syntax
           (lambda (x)
             (syntax-case x ()
               ((_ symbol3 (... ...))
                (or (for-all (lambda (e) (memq e '(symbol1 ...)))
                             (syntax->datum (syntax (symbol3 (... ...)))))
                    (syntax-violation 'constructor-syntax "excpectd symbols which belong to the universe" x))
                (syntax (constructor '(symbol3 (... ...))))))))))))

*1 いや、(enum-set-union s1 s2)としてエラーがでるかで無理やり判別はできるが

*2 いや、Scheme的に普通かも知れないが

[scheme] Mac上にいろいろなR6RSインタプリタをインストールする (2012/01版)

R6RSのサイトに実装へのリンクがある。

Homebrewで入れられるもの

(MacPortsにもいろいろパッケージがあると思いますが、使ってないので省略)

Ypsilon
$ brew install ypsilon
$ ypsilon foo.scm
mosh
$ brew install mosh
$ mosh foo.scm

パッケージがあるもの

Chez Scheme

商用だが、フリー版の「Petite Chez Scheme」がある。

http://www.scheme.com/download/ から「Petite Chez Scheme」「32bit or 64bit」「threaded or nonthreaded」 「Petite Chez Scheme for Intel/AMD MacOS X」「*.pkg(インストーラ) or *.tar.gz(ソース)」を選ぶ。

今回はpcsv8.4-i3osx-1.pkg.tar.gzを選んだ。インストーラに従うと/usr/bin/petiteがインストールされる。

PLT Racket

brewでも入るけど、インストーラでバイナリを入れる方が簡単だったような。

起動

$ /Applications/Racket\ v5.1.1/bin/racket -f foo.scm
Larceny

http://www.larcenists.org/download.html から「prebuilt for Macintosh OS X/IA32」をダウンロード。

起動

LARCENY_ROOT=/Users/yhara/research/Scheme/larceny-0.97-bin-native-ia32-macosx larceny -- foo.scm

その他

Ikarus

開発が止まっていて、Vicareに引き継がれてるらしい。Vicareも6月からコミットがないが…

Guile
$ brew install guile

で入るんだけど、使い方がよく分からない…(そもそもどの程度R6RS準拠なのか)

$ echo '(import (rnrs (6)))' | guile
guile> 
Backtrace:
In standard input:
   1: 0* (import (rnrs (6)))

standard input:1:1: In expression (import (rnrs #)):
standard input:1:1: Unbound variable: import
ABORT: (unbound-variable)
guile>     
IronScheme

未トライ http://ironscheme.codeplex.com/

BiwaScheme (おまけ)
$ brew install node
$ brew install npm
Error: No available formula for npm
npm can be installed thusly by following the instructions at
  http://npmjs.org/

To do it in one line, use this command:
  curl http://npmjs.org/install.sh | sh
$ curl http://npmjs.org/install.sh | sh
$ npm install biwascheme