Hatena::ブログ(Diary)

::Eldesh a b = LEFT a | RIGHT b このページをアンテナに追加 RSSフィード Twitter

2015-01-21

XtoWに期待

Cygwin/Xの起動方法の変化を調べていて知ったのだけど、cygwinではXtoWという、よりネイティブ環境と密に連携できるWindow Managerが使える。

これを使うには startxtow というコマンドで X を起動すればよい。


プロトタイプらしく実際そういう品質のようで、手元では挙動が不安定、画面の更新が部分的に(秒単位で)遅れる、頻繁にスタックする(キーボード,マウス入力だけ死んでる雰囲気)等の問題が発生する…。


ただしデフォルトのXでは表示できないような、リモートのlinux上で動く GLFW のデモが表示できたりするので今後に期待出来そう。

ヒトバシラーの人は一度起動してみてはどうでしょうか。


参考

2015-01-20

cygwinのX serverの使い方が変わった

2015/1/20現在、

これまで startxwin で使えていた、cygwinをXサーバにする方法が変更されて使えなくなった。ログから察するに2014/11/13の更新から。

新しい方法では以下のようにする。

$ run xwin -multiwindow
$ xterm
xterm> xhost +192.168.xxx.xxx

(参考 X does not start after cygwin upgrade)


起動ログ

参考として起動ログ(/var/log/xwin/XWin.0.log)を張っておく。

Welcome to the XWin X Server
Vendor: The Cygwin/X Project
Release: 1.16.3.0
OS: CYGWIN_NT-6.1 user-PC 1.7.33-2(0.280/5/3) 2014-11-13 15:45 i686
OS: Windows 7  [Windows NT 6.1 build 7600] (Win32)
Package: version 1.16.3-1 built 2014-12-30

続きを読む

2015-01-13

smlnjlibをSML#に移植した

あけましておめでとうございます。2015年最初の記事です。今年もよろしくお願いします。


smlnjlibというライブラリ集の一部をSML#(2.0.0)用に移植しました。> smlnjlib#

例によって移植と言ってもsmiファイルをひたすら書いただけなので実装を詳細に把握しているわけではありません。


smlnjlibは SML/NJ の配布物に含まれるライブラリ集で、mltonが一部(ほとんど?)を移植、sml#が一部を取り込んで使用するなどSML界では広く知られています。

このライブラリは以下のライブラリ群から成ります。'X' の付いたライブラリを移植済みです。

ライブラリ移植適当な説明
ControlsXグローバル設定
Doc なんだかよく分からない。テンプレートエンジン??
HashConsXコンストラクタを圧縮表現するテクニックを実装(多分)
HTML HTML3.2(!!)のパーサとプリンタ。要らんでしょ…。
HTML4 HTML4.01のパーサとプリンタ。
INet socketのてきとーなラッパー
JSON JSONパーサ。ストリームパーサとイベントパーサ(?)が使える。
PP X典型的な実装のpretty printer。
Reactive よく分からない。
RegExp X正規表現。文法とバックエンドをfunctorパラメータとして選択出来る。
SExp 最近入ったナゾのS式パーサ。なぜ入れた。
Unix unixパスのユーティリティ。
Util Xこの中で一番便利な小物集。特にmap/setが他のライブラリからよく参照される。
XML 最新版(110.77)で入ったXMLパーサ。なぜ入れた。

移植したライブラリが参照していたため、SML#の提供していないbasisの一部と、njが提供しているunsafeモジュール(の一部)も実装してあります。

これも頭に入れておくと無駄な再実装を避けられる場合があるかも知れません。

ライブラリ実装適当な説明
basis XArray2とpackword
unsafe Xnjに合わせたunsafe array/vector

使い方

ビルドするのに必要なことはトップレベルで make するだけです。

make -f Makefile.smlsharp

使うためには、使いたいライブラリのトップレベルのsmiファイルを_requireして下さい。

個別に指定してもいいですが、トップレベルのファイルを参照しておくと.cmの参照と対応が取りやすいです。

例えば Util の機能を使いたい場合は以下のようになります。

(* hoge.smi *)
_require "Util/smlnj-lib.smi"

(* hoge.sml *)
... IntRedBlackMap.find ...
$ smlsharp -I/path/to/smlnjlib-sharp hoge.sml

Note

  • オリジナルのコードでは where K = K などとしているものはsmlnjによる拡張機能ですので where type K.ord_key =... 等のように書き換えてあります。
  • Util/rand.sml はWord31をWord32に単純に置き換えているだけなので乱数の性質とか怪しいかも知れません

2014-12-10

kitlibをSML/NJとSML#に移植

kitlibというSMLライブラリSML/NJSML#に移植しました*1。 #全く誰も嬉しくないと思いますが(^^;;


kitlibはMLKitという処理系を実装されているElsman先生が作っているSMLライブラリ集です。

元々はMLKitのソースコードと一緒に配布されていましたがライブラリとして切り出したようですね。*2


移植と言っても処理系依存の箇所はほとんど無いので、実際はMakefile(と.cmと.smi)を書いたくらいです。

ライブラリに含まれる機能としては 正規表現、Pickle(シリアライズ/デシリアライズ)、Map(コンテナ)等、ありがちな内容なのでsmlnj-libや他のライブラリが使えるならそちらを使えばいいと思いますが、この手の小回りの効くライブラリはいくつか選択肢にあると安心かも知れません。


注意

SML/NJとSML#はそれぞれ別の個所でpickle(バイナリシリアライザ)のテストに失敗する個所があるのでどれかの処理系が怪しいかも知れません。

あんまり突き詰めたくないのですが、やる気が出たら原因究明しようと思います。

*1:pull requestがスルーされているようなのでもう紹介しちゃいます

*2:他のSMLプロジェクトをガリガリ書いているようなのでそのためでしょう

2014-12-07

SMLでDynamic(再び)


この記事は ML Advent Calendar 2014 7日目の記事です。


ここではSMLによるDynamic(あるいはAny)と呼ばれる*1、任意の型の値を保持出来るテクニックを紹介します。

任意の型の値を保持可能な型という内容は 以前も紹介したことがあります(2) が、前回紹介した実装では例外を使っており、プログラム作法またはパフォーマンスに懸念があるかも知れません。プログラマの心理的にもよろしくなさそうです。

この記事では例外を使わずポータブルなコードのみで同等の振る舞いを実現するテクニックを紹介し、実装を理解出来るように解説します。


序/Dynamicの必要性

StandardMLでジェネリックなコードを書こうとすると、型に応じて処理を切り替えるということが一切出来ないことがネックになります。(その代わり型が完全に推論される)

しかしどうしても型によって振る舞いを変えたい場合があり、そういった場合はどこかで妥協する必要が出てきます。

その妥協のひとつの方法として、型と同名の値(or関数)と、そのコンビネータを提供することでユーザに型*2を強制的に指定させる手法が知られています(3)。

この手法は型ごとの振る舞いのデータベースを(暗黙に)構成出来ることが重要ですが、それにはここで紹介する Dynamic を駆使して UniversalType と呼ばれるテクニックを用いることで実現出来ます。


振る舞い

まず簡単なユースケースから見ていきます。

Dynamicは以下のようなシグネチャを持ち、例外を用いた実装と変りません。

structure Dynamic : sig
  type t
  type 'a key : ('a -> t) * (t -> 'a option)

  val mk : unit -> 'a key
  val emb : 'a key -> 'a -> t
  val prj : 'a key -> t -> 'a option
end = ...

t 型に(任意の型の)値を保持させ、'a key を使って対応する型の値を設定または取り出します。

埋め込みと取り出しには emb/prj という名前が付けてありますが、自分でkeyタプルを分解しても同じです。

- structure D = Dynamic;
(* 型タグを作成 *)
- val int : int D.key = D.mk()
- val string : string D.key = D.mk()
- val int_string : (int * string) D.key = D.mk()

- val val0 = D.emb int 314      (* intの値を埋め込み *)
val val0 = - : Dynamic.t

- val get = D.prj int val0      (* int 型の値を問い合わせる *)
val get = SOME 314 : int option (* 入れた値が出てくる *)

- val get = D.prj string val0   (* string 型で問い合わせてみる *)
val get = NONE : string option  (* 入ってない *)

図にしてみました。

それぞれの型に対応するキーを使って Dynamic.t 型の値に問い合わせを行い、値を取り出します。

値を設定した時のキー(型)以外を使って問い合わせるとNONEが返ります。

f:id:eldesh:20141206234757p:image

混成リスト

お約束ですが Dynamic の分かりやすい適用先として、互いに異なる型の値から出来たリスト(混成リスト)の作成があります。

以下の例では int,string,int*string の値からなるリストを構成し、それぞれに対する一般化toStringを定義;適用しています。

- val hlist =
      [D.emb int 256
      ,D.emb string "hello"
      ,D.emb int_string (1414, "good bye.")
      ];
val hlist = [-,-,-] : Dynamic.t list (* いろいろな型の値が入ったリスト *)

- fun maybe _  NONE    n = n ()
    | maybe t (SOME x) _ = t x

- fun IStoString (x,s) = concat["(",Int.toString x,",",s,")"]

- fun toString d = (* Dynamic用toString *)
  maybe Int.toString (D.prj int        d) (fn()=>
  maybe (fn x=>x)    (D.prj string     d) (fn()=>
  maybe IStoString   (D.prj int_string d) (fn()=>
  "unkown type")))
val toString = fn : Dynamic.t -> string

- map toString hlist;
val it = ["256","hello","(1414,good bye.)"] : string list (* それぞれを文字列に変換出来た *)

実装

では実装を示します。

短いですが読んでいきなり理解するのはかなり難しいと思います。

structure Dynamic :> DYNAMIC =
struct
  datatype any = V of {
                    disclose:   unit -> unit,
                    undisclose: unit -> unit
                 }
  type t = any
  type 'a key = ('a -> t) * (t -> 'a option)

  fun mk () =
    let
      val box = ref NONE (* 通信チャネル *)
      fun discloser v () = box := SOME v
      fun undiscloser () = box := NONE
      fun mkV v = (* それぞれが box にアクセスするサンク *)
         V { disclose   = discloser v,
             undisclose = undiscloser }
      fun useV (V {disclose, undisclose}) =
        ( box := NONE;  (* mkV したときと同じ box にアクセスするなら *)
          disclose ();  (* 同じ box に v を書く *)
          let val v = !box (* すぐに取り出す *)
          in undisclose(); v end )
    in
      (mkV, useV)
    end

  fun emb (f,_) = f
  fun prj (_,f) = f
end

見ての通り、例外(やその他怪しい機能)は一切使っていません。

ですがかなり入り組んだリファレンスの使い方をしています。


以下に概念図を書いてみました。

f:id:eldesh:20141207001434p:image

mkとuseVの使う関数が一致している場合、クロージャ内の box を介して通信していることがポイントです。

useVを使う際(=値を取り出す時)、同じ box の実体を共有する場合は、「キーが一致した」ことになり、discloseが書いた値を直後に取り出すことになります。

そうで無い場合は、useVに渡したdiscloseが値を設定したものとは異なる box の実体に値を設定しているため、box に何も設定されていないままの値、つまり NONE が取り出されます。

box に実際に値が書かれるのは useV 内で値を取り出す直前だということに注意して下さい。ユーザが埋め込んだ(embした)値は mkV の返すクロージャに含まれています。


結び

例外を用いずにDynamicを実装する方法を見てきました。 #理解できたでしょうか?

これはリファレンスの便利さに加えて、通常考えられている以上に強力な機能だということも示しています。

自明な挙動をするように見えるSMLのコードでも、リファレンスが絡むと挙動を簡単には理解出来ないようなプログラムになることがある、ということは気を付けておくとよいでしょう。

参考/出典

*1:大抵こういう名前のstructureとして提供される

*2:のような値