20080408

Serializing universal types as S-expressions using Sexplib

The standard ML way to "unify" multiple types is to use sum types a.k.a. discriminated unions, e.g. type foo = Int of int | String of string | Pair of foo * foo.

Universal types are types without type variables that allow you to store and retrieve values of any arbitrary type. They can be handy in some situations. For instance, you might decorate an abstract syntax tree with cells of a universal type and insert various data inferred at different phases of your compiler without having to polymorphise your AST types.

Sweek blogged about this recently here and the MLTon wiki has nice entries about property lists and universal types.

Sexplib on the other hand is a very nice piece of Markus Mottl engineering (again at Jane St) and is an absolute must for developing in Ocaml. The Sexplib camlp4 syntax extension automatically defines converters for any type you define, and handles polymorphism, modules and functors perfectly well.

Obviously, Sexplib can't serialize functions. (You can have a look at AliceML if you absolutely want that; function serialization requires some kind of byte code).

And that's where universal types and Sexplib don't mix well. Why? Because, at least for implementation techniques of universal types that I know, universal types work by cheating on the type system using closures and side-effects. Greetings to the relaxed value restriction!

Basically, to store a value of type bar, the computer creates a closure of fixed type unit -> unit that stores within its environment the value of type bar; when invoked, the closure spits it out at a pre-agreed location.

For every type, the closure will have the same closed type unit -> unit and can be stored anywhere you please. To retrieve the value, you invoke the closure, and it writes its content somewhere known. This will usually be a foo option ref. If multi-threading is used, you must protect that reference, for instance with a mutex.

However, functions are generally not serializable. Marshall does an ugly thing by spitting out a PC, the environment and the MD5 of your code, which works until you recompile your program. Not particularly persistent. As for Sexplib, as it works at the preprocessor level, it is not even possible.

Fortunately you can always define your own foo_of_sexp and sexp_of_foo. With some trickery, I managed to write a Sexp-aware Proplist.

Interface:

(* Proplist *)

type property_id = string
type 'a propname
type proplist

val propname : ('a -> Sexplib.Sexp.t) -> (Sexplib.Sexp.t -> 'a) -> property_id -> 'a propname
val proplist : unit -> proplist
val set : proplist -> 'a propname -> 'a -> unit
val get : proplist -> 'a propname -> 'a
val get' : proplist -> 'a propname -> 'a option
val sexp_of_proplist : proplist -> Sexplib.Sexp.t
val proplist_of_sexp : Sexplib.Sexp.t -> proplist


Implementation:

(* Proplist *)

TYPE_CONV_PATH "Util.Proplist"

open Sexplib
open Sexp

type property_id = string

module I = struct type t = property_id let compare (x : property_id) y = compare x y end
module SS = Set.Make(I)
module SM = Map.Make(I)

type 'a propname =
{
id : property_id;
to_sexp : 'a -> Sexp.t;
mutable value : 'a option
}

type property =
{
extract : unit -> unit;
sexpify : unit -> Sexp.t
}

type proplist =
{
mutable stuff : property SM.t
}

let ids = ref SM.empty

let proplist () = { stuff = SM.empty }

let sexp_of_property p = p.sexpify ()

let sexp_of_proplist p =
List(
SM.fold
(fun k p result ->
List[Atom k; sexp_of_property p] :: result
)
p.stuff
[]
)

let set p name x =
let f () = name.value <- Some x in let g () = name.to_sexp x in let r = { extract = f; sexpify = g } in p.stuff <- SM.add name.id r p.stuff let propname to_sexp from_sexp id = if SM.mem id !ids then failwith "Property already defined" else begin let name = { id = id; value = None; to_sexp = to_sexp; } in let f pl x = set pl name (from_sexp x) in ids := SM.add id f !ids; name end let get' p name = let r = SM.find name.id p.stuff in r.extract (); let x = name.value in name.value <- None; x let get p name = match get' p name with | Some x -> x
| None -> raise Not_found

let proplist_of_sexp x =
let pl = proplist () in
begin
match x with
| List l ->
List.iter
(function
| List[Atom k; p] ->
let f = SM.find k !ids in
f pl p
| x -> raise (Conv.Of_sexp_error("Pair expected", x)))
l
| _ -> raise (Conv.Of_sexp_error("List expected", x))
end;
pl


Note that if you are using a property list where property names are integers generated from a global counter, there is no guarantee that property names will always get the same ID. So, when constructing property names, you'll have to give, well, a unique property name. And strings are more convenient than integers, here. The unicity of such strings cannot be checked at runtime but that's about the best you can do. Also, when constructing a property name, you have to give the foo_of_sexp and sexp_of_foo converters. Retrieving them at unsexprification time is a little bit tricky since the return type must be hidden - these will go into a private global table indexed by property names.

39 comments:

cheap wow gold said...

CHEAP wow gold BUY wow power leveling MY wow power leveling

cheap wow gold said...

MY wow gold CHEAPEST wow power leveling my gold wow

CurtisSBordeaux said...

成人圖庫,口交技巧,成人18,自慰方法,Fleshlight,情色自拍貼圖,成人情色貼圖,少婦自拍,一夜情聊天,本土av,色情av,av圖片,色情聊天,成人情色網,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,080視訊聊天室icandy,情色少女貼圖,免費視 訊聊天網,av女優18,免費線上視訊fm358,avdvd免費AV女優,女優王國,做愛,無碼影片,情色交友

石薇 said...

加油!期待更新哦! ........................................

佳慧 said...

很棒的分享~~~來留個言囉~~~~........................................

睿玄 said...

TAHNKS FOR YOUR SHARING~~~VERY NICE ........................................

嘉容嘉容 said...

上床圖片av圖片免費色情圖台灣性網陰蒂淫妹貼圖色情激突成人論壇成人色情網激情成人聊天室情色影音鹹濕女生自慰影片淫慾自慰色情a片成人色情圖片網情人視訊網成人話題成人色情台灣成人淫蕩a圖片情色留言板女生奶頭情色成人全裸美女圖片情色寫真裸體照大奶子台灣色情成人網站一夜正妹美女裸體寫真g罩杯美女sex520情趣娃娃視訊打槍視訊辣妹uthome淫亂走光照av情色網女生高潮成人自拍火辣眉眉太太陰毛美女視訊聊天全裸入鏡火辣av三點全露

琦竹 said...

85cc片觀看,77美女dvd影片,熊貓貼區,ut網際聊天,一葉情,av,嘟嘟,影音live秀,a片,做愛影片,視訊做愛,美女短片,78論壇,ut聊天,打飛機,a片,免費視訊,免費視訊,成人影院,性愛小說,辣妹視訊,網路交友,捷克論壇,h影片,色咪咪,免費影片85cc,kiss911,後宮,a片,影音視訊聊天,交友,免費聊天,聊天室交友,做愛影片,線上a片,美女影片,免費影片下載,免費聊天室,視訊做愛,美女視訊聊天

雅伯 said...

彰化聊天室二聊天勢苗栗聊天室ut中部人聊天聊天尋夢亞洲無碼成人影片亞洲無碼影片區亞洲短片 亞洲長片亞洲短片亞洲長片亞洲貼圖站亞洲電影瘋情網亞洲瘋情網下載亞洲瘋情影城亞洲歐美影片亞洲免費線上a片亞洲免費電影亞洲免費情色影片男同自男同志gay圖片男同志gay網男色情片男免費聊天亞色情網亞亞光碟網亞亞成人網免費影片亞亞成人影片亞洲go2免費影片亞洲成人線上看亞洲色圖亞洲免費色情片無碼美女視訊免費桌布下載成人文章成人圖片

SigridNolen1祐音 said...

人生最可憐的是半途而廢,最可悲的是喪失信心,最遺憾的是浪費時間,最可怕的是沒有恆心。..................................................

則其則其 said...

思想與理論,貴呼先於行動,但行動較思想或理論更高貴 ..................................................

AlexanderLotts0 said...

78論壇 A片,成人影片分享 080視訊聊天室 666成人 視訊交友網 xvideo免費影片 視訊美女ws888 6k聊天室辣妹視訊 A片-免費視訊 視訊美女mybank sex888影音視訊聊天室 影音情人趣味 85cc免費影片 視訊激麻館 禁地論壇成人 情色視訊 成人影片情色網 bt成人論壇 18成人avooo 玩美女人試看片 hilive tv視訊妹 免費聊天firework av999免費影片 avdvd無碼影片成人情色 一葉晴貼影片av127 520聊天室 一夜情視訊聊天室 視訊聊天室交友 免費視訊辣妹avdvd一夜情 1元視訊 網愛聊天 250av女優免費影片 免費影音視訊fm358 sex女優王國情色 嘟嘟情人色網 dvd 台灣18網 視訊交友雙贏論壇 色a金激麻館 性愛故事性愛文學 凹凸情欲網 成人視訊happylife 視訊聊天交友mm358 免費視訊辣妹sex女優王國 情色香港論壇 亞洲情色貼圖區 日本 a 片自拍偷拍網站情色小說 免費avi影片下載 台灣情色視訊網 17358 視訊聊天室 日本a片免費下載 情色影片免費觀賞you tube影片下載

730A_ngelinaRabideau0 said...

成功等於目前,其他都是這句話的註解。........................................

冠宛君中 said...

you two make a lovely couple............................................................

王周宏儒 said...

Better be the head of a dog than the tail of a lion...................................................

雲亨 said...

Make yourself necessary to someone...................................................................

楊俊美 said...

能猜得出女人真實年齡的男人也許耳聰目明,但肯定毫無大腦。哈哈!..................................................................

林怡洋 said...

要照顧身體歐~保重......................................................................

政儒 said...

Pay somebody back in his own coin.....................................................................

皇銘 said...

成熟,就是有能力適應生活中的模糊。.................................................................

星美星美 said...

君子立恆志,小人恆立志。.................................................................

夏康如 said...

不只BLOG內容很棒留言也很精采 XDDDD..................................................................

茹希茹希 said...

Pay somebody back in his own coin.............................................................

懿綺懿綺 said...

教育的目的,不在應該思考什麼,而是教吾人怎樣思考............................................................

云依恩HFH謝鄭JTR安 said...

有用的才華若不用,便如同日晷儀放在陰暗之中............................................................

吳婷婷 said...

我們這一代最偉大的發現是,人類可以藉由改變心中的態度來改變人生。.......................................................

蔡舜娟蔡舜娟 said...

人生有如洶湧的波濤,如果沒有岩石的阻擋,怎能激起美麗的浪花?............................................................

佳皓佳皓 said...

蛛絲馬跡皆學問、落花水面皆文章............................................................

alv賴arez冠bar伶rett said...

在莫非定律中有項笨蛋定律:「一個組織中的笨蛋,恆大於等於三分之二。」. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

吳淑芬吳淑芬 said...

真是太猛了,請受小弟一拜Orz(>O<)............................................................

蕙王帆蕙王帆蕙王帆 said...

文章不求沽名釣譽,率性就是真的..................................................................

馬志榮惠玲成 said...

良言一句三冬暖,惡語傷人六月寒。......................................................................

群育航學 said...

A good medicine tastes bitter. ............................................................

蔡曼鄭美玉屏 said...

人若賺得全世界,賠上自己的靈魂,有什麼益處?......................................................

偉曹琬 said...

一個人的價值,應該看他貢獻了什麼,而不是他取得了什麼....................................................

于庭吳 said...

大肚能容,了卻人間多少事,滿腔歡喜,笑開天下古今愁。..................................................

木詹詹詹詹詹行詹詹 said...

人生匆匆-把握當下,支持鼓勵~事事如意~..................................................

張王雅竹欣虹 said...

Pen and ink is wits plough...................................................................

怡靜怡靜怡靜怡雯 said...

好熱鬧喔 大家踴躍的留言 讓部落格更有活力..................................................