日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

関数型言語からキーバリューストアへの型安全なアク
セス機構
上野 雄大

大堀 淳

本稿では，強い型付けを持つ関数型言語から高水準かつ型安全にキーバリューストア（KVS）にアクセスするための言語機構を提案する．KVS はキーと値の対応を管理するデータストレージであり，その可用性や拡張性の高さが注目を集めている．一方，その単純なデータモデルのため，複雑なデータ構造やその操作を KVS 上に実現するためには，クライアントプログラム側での煩雑な対応が必須である．本稿で提案する機構は，任意の代数的データ構造
を KVS にストアするためのデータモデルと，そのモデルの下での型安全な KVS アクセスをユーザーに提供する．
KVS アクセスに必要な一連の操作はプログラムの型情報から自動的に選択される．本稿では，この機構の実現方式を与え，既存の KVS と関数型言語 SML# を用いた本方式の実装について，その概要を報告する．

ば，独立なデータとみなせるため，キーと値の対応関

1 はじめに係を，キーと値の組の集合としてネットワーク上に分Google BigTable [2] や Amazon S3 [3] などのクラ散して格納することができ，また障害に備えたデータ

ウド系ストレージが，高可用情報ストレージ基盤のたの複製も比較的容易である．これにより，スケールア

めのデータアクセスフレームワークとして注目を集め

ウト性を持つ高可用ストレージが実現できる．

ている．それらクラウドストレージでよく使用される

従来のキーバリューストアの研究開発の中心は，ス

データ格納方式は，データをキーと値（バリュー）のケールアウト性や高可用性を確保するデータの分散方

対応関係として表現するキーバリューストア（KVS)

式や複製方式の開発であり，そのプログラミング技術と総称されるものである．キーバリューストアの標準の研究開発は，必ずしも進んでいるとは言えない．各的な仕様は未だ存在するとは言えず，それぞれのシス

キーバリューストアは文字列を基本とするネットワー

テムで種々の独自の機能や構造が提供されているが，クプロトコルや API を提供しており，ユーザーはこ

その基本は，キーと値を文字列などのネットワークでの API と直接的な文字列操作を組み合わせてキーバ安全に交換可能なデータで表現し，ストレージサーバ

リューストアへのアクセスを実装する．この単純な方

がキーと値の対応関係を維持し，ユーザにキーと値式は，基本的なデータのみを処理する上では適していの対応関係の登録，キーに対応する値の検索と更新

るものの，高度な構造を持つデータの書き出しと読みの機能を提供する，という単純なものである．キーも込みには煩雑な手順を要することや，キーバリュース

データであるため，キーをポインタとして値に含め

トアとのインターフェースにおいて型安全性などのプることにより，帰納的に定義可能な種々のデータ構造

ログラミング言語が持つ機能が活用しにくいなどのを表現することができる．さらに，キーと値の組は，不便があり，高水準プログラミング言語におけるキー

データに含まれるキーの整合性等の条件を無視すれバリューストアへのアクセスのサポートは十分とは言えない．もしキーバリューストアを高水準プログラ
ミング言語から簡便かつ安全に取り扱う技術が確立

Katsuhiro Ueno, Atsushi Ohori, 東北大学電気通信研究所, Research Institute of Electrical Communication,
Tohoku University.

されるならば，キーバリューストアの利点である種々のクラウド系アプリケーションの開発が格段に容易になると期待される．

戦略

本研究の目的は，ML 系関数型言語からキーバリュー

キーバリューストアは，キー分散方式や耐障害性なストアを簡便かつ型安全に扱う枠組みとそれを実現す

どの実装技術を抽象しプログラミングの観点から考るコンパイル技術を確立することである．SML# でえれば，以下の関数で提供される抽象データ構造と考は，すでに，通常の業務で広く使用されている関係えることができる．

データベースの型安全かつ簡便なアクセスが実現されcreate:string ∗ string→unitており [8]，これにキーバリューストアのアクセス機

get:string→string

能も加わるならば，関係データベースに蓄積されていput:

string ∗ string→unit

る拠点ストレージデータと分散キーバリューストアに

ここでは，string（文字列型）をキーとバリューを表クラウドデータを統合したソフトウエア開発などが現する領域とした．create(K,V ) は，K をキーとし可能になると期待される．本稿では，キーバリュース

V を値とする対応をキーバリューストアに追加する．

トアのための型システムを提示する．さらに，SML#

get(K) は，キー K をもつ値をキーバリューストアかが持つ型主導コンパイル技術を用いることにより，構ら探索する．put(K,V ) は，存在するキー K に対し築したキーバリューストアの型システムを SML# コて，その値を V に変更する．get(K)，put(K,V ) とンパイラへの組込むことが可能なはずである．本稿でも，キー K がキーバリューストアに存在しなければ，は，その方針の概要を述べる．方針の詳細と実装は現例外を発生されるものとする．通常のキーバリュース

在開発中であり，本稿の改訂版ならびに本稿に続く論

トアは，より複雑な機能を提供している．たとえば，文にて報告する予定である．

BigTable では，キーは単純な値ではなく，列，行，タ

本節の最後に，関連研究を概観する．本方式は，関イムスタンプの三つ組であり，また，Amazon S3 で数型言語が取り扱う代数的データ構造を，その構造

はキーと値の組みの集合はバケットとよばれる集合単と型安全性を保存したままヒープの外部に取り出す

位で管理される．しかし，これらの機能は，上記の３という点で，データ直列化に関する研究と関連が深機能で十分に表現可能であり，プログラミング機能をい．関数型言語における直列化方式には，特別なラ分析し設計する上で本質的ではない．

ンタイムサポートを必要としない直列化コンビネー

上記３機能は，言うまでもなく，既存のプログラミ

タ [6] [4]，メモリダンプに dynamic 型を付加するアプ

ング言語から使用することができ，従って，これら機

ローチ [1] [7]，およびメモリグラフに対する型推論 [5]

能の言語への統合自体に技術的課題は存在しない．前によるアプローチなどが提案されている．これらの節で触れた通り，実際に，それぞれのキーバリュース

研究は，直列化対象のデータ全体をひとつのバイナ

トアの実装では，これら機能に相当する API を種々リデータとして一度に直列化および復元する方式と，の言語に提供し，広く使用されている．これらプリミ

その型安全性を議論の対象としている．本研究は，こティブは，数値データなどの単純なデータの処理にはれら既存の成果を踏まえ，キーバリューストアを使い適しているが，構造をもつデータを含む高度な処理にこなす上で必要な機能，例えばキーバリューストアには必ずしも十分とは言えない．

書き出したデータの部分的な参照や，プログラムと

前述の通り，キーはデータであり値に含めることがデータストアを独立にメンテナンス可能な可搬性の可能であるため，キーバリューストアは，上記の機能高いデータ表現などを考慮し，高い安全性と実用性をのみで，原理的には任意に複雑な構造を表現可能であ

両立するキーバリューストアへのアクセス方式の実現

る．例えば，キー K に対して，要素 10 の整数配列を目指すものである．

を格納したければ，以下のようなキー構造を作れば2 キーバリューストア型システムの課題とよい．

1. 高水準なアクセスの実現．通常の高水準言語で

キー

値

K/0

1 番目の要素

...

...

K/9

10 番目の要素

可能なデータ構造の操作を，プログラマに複雑で危険なキーのエンコーディングを要求することなく実現すること．

2. 型安全なアクセスの実現．型付き高信頼言語が
ここで，nは整数 n の文字列表現であり，K/iは文字実現している型安全性を基礎とする高い信頼性

列 K に “/” とiを連結して得られる文字列である．文を，キーバリューストアクセスにおいても実現す字列集合は加算無限であるから，これら構造をキー

ること，の中に自由にエンコードすることができる．言語で上記の分析のとおり，キーバリューストアでは，
通常 K[i] と表現される配列の要素へのアクセスは， 「キー K に構造をもつ値 V を格納する」という機
get(K/i) とすれば実現できる．このような表現を系
能を統的に定義していくことにより，任意のネスト構造も• 表現すべき値 V の構造をポインタ構造で表現し，表現できる．K1 から Kn を，上記の方式で表現され• 必要なポインタ集合を文字列 K を根幹とするた配列が格納されている（添字部分を除く）キーとすキー集合で表現する

ると，10 × 10 の配列 M は以下のように表現可能でことによって実現する．必要とされるキー集合は，表ある．

現すべきデータ構造に対して静的に決定可能であり，
キー

値

従って，コンパイラで生成可能なはずである．そこ

M/0

K1

で，目標の第一点目のデータ構造の高水準の操作の実

...

...

現は，コンパイラによるキー構造の生成とデータア

M/9

Kn

クセス式のキーのアクセスへの翻訳によって実現可能なはずである．キーバリューストアを含むプログラ

言語で通常 M[i][j] と表現される行例の要素へのア
クセスは，get(get(M/i)/j) とすれば実現できる．この式において，まず get(M/i) によって i 番目の配列が格納されているキーの共通部分 Ki が返され，それに “/” とjを連結し，i 番目の配列の j 番目の要素へのキーが生成され，それに対応する値が検索される．
以上から理解されるとおり，通常のプログラミング
言語で実現されているデータ構造は，その構造をキーの集合としてエンコードすることによって表現可能である．しかしながら，このような表現をプログラマが行うのは煩雑なばかりでなく，そのようにして得られたプログラムは，言語の型システムなどで発見することができない誤りを含んでいる可能性が高く，脆弱で信頼性に乏しいものになると予想される．さらに，
キーバリューストア上のデータを，プログラムが扱う他のデータ構造と共に操作することも困難である．
プログラミング言語の型システムにキーバリュース
トアをシームレスに統合する上での課題は，以下の２点である．

ミングフレームワークを構築する上での主な課題は，型安全性の実現である．
キーバリューストアに保存される値はすべて，文字列（またはそれに準じる低レベルのデータ）で表現される．この事情は，プログラミング言語が，すべてのデータを低レベルのビット列で表現するのと同様である．高信頼型言語では，型安全性を保証するために，すべてのデータの型を，プログラムが管理追跡している．これが静的型システムの役割である．キーバ
リューストアの操作系を，このような型を追跡する規則の集合として定義し尽くすことができれば，高水準
でかつ型安全なシステムが実現できる．データ構造の作成や，作成されたデータ構造の操作は，キー集合の設計などの要素が入り，プログラミング言語のデータ
構造の操作より複雑になるものの，基本的には同一の原理に従うため，それらを型推論規則として表現するのは困難ではない．しかしながら，キーバリュース
トア上の名前であるキーは外部名であり，その持つ値は，一般に，プログラムが実行される以前に（あるいはプログラムとは独立に他のプログラムによって）作成されたものである．従って，これらキーの型をプロ
グラミング言語の静的型システムが追跡することは原理的に不可能である．このような外部の永続データ

4. プログラムからの高水準の操作関数の定義
本稿では，以下の文法で定義されるキーバリュース
トアに格納可能な型の集合を考える．

σ::=b | P tr(σ) | P air(σ, σ) | Array(σ)

を型システムから扱う一つの戦略は，永続データに型

b は ，整 数 型（int）や 真 理 値 型（bool），実 数 型の記述をメタデータとして含め，キーを指定して永続（real）などの原子型を代表するメタ変数である．

データを最初にアクセスする時，メタデータを一緒に

P tr(σ) は σ 型の値へのポインタ，P air(σ1 , σ2 ) は σ1取り出し，型の整合性をチェックすることである．こと σ2 の型の値の組，Array(σ) は σ の型を持つ値のの考え方に従って永続データを扱う静的型推論規則に配列を表す．この集合は，型付きキーバリューストア

は，Abadi らによって提案された dynamic 型の型推の型理論の構築の問題を検討する上で十分に大きな

論規則 [1] がある．このシステムは，型を追跡できな集合である．

い外部オブジェクトに相当する特殊な型 dynamic を次に，各型に対するキーバリューストア上での表現

導入し，この外部オブジェクトの作成と使用に関するを定義する．型 σ の値をキー K に格納するための実規則を定義している．その本質は以下の規則で表現可

装構造を R(K, σ) と書く．R(K, σ) は型 σ に対応す能である．

る構造のキーバリューストア上での表現であり，σ が(create)(use)Γe : τ複合型であれば，他の構造を部分構造として含む入Γ  create(e) : dynamic

れ子に構造を持つ．そこで，キーバリューストア上でΓ  e : dynamic

必要がある．これを標準文字列表現と呼び，E(σ) とΓ  use e1 as τ : τ

書くことにする．通常のヒープメモリーの場合，σ がこの考え方を，前述のキーバリューストア上でデータ構造を表現する方式と組み合わせれは，型安全で高水
準なキーバリューストアのプログラミングフレーム
ワークが実現できるはずである．
本研究では，以上の方針の下でキーバリューストア
の型理論を構築した．以下，その概要を報告する．

3 キーバリューストアの型システム
通常のデータ構造の設計では，操作関数を定義し，その型と評価規則を定義する，というステップを踏む
が，キーバリューストアのアクセスでは，プログラムに提供する操作関数は，型に依存する複雑な定義が必要であり，直接は定義できない．そこで本研究では，
キーバリューストアに対する高水準なアクセスのための型理論の構築にために，まず，以下の各要素を定義する．

1. キーバリューストアに格納可能な型の集合
2. 各型のキーバリューストア上での表現
3. 各型に対するプログラミング言語上の表現の構造 R(K, σ) を他の構造の中での表現を定義する

原子型であればそのデータの他構造中の表現はそのデータそのもの，複合型であれば，その構造へのポインタである．キーバリューストアの場合，原子型はエンコードされた文字列，ポインタはキーで表現される．そこで，E(b) を文字列へのエンコード原子型 bのデータ，原子型以外の各型 σ に対する標準文字列表
現 E(σ) は，その型を格納しているキーバリュースト
アの（主要な）キー文字列とする．この R(K, σ) は，E(σ) を用いて σ の種々の属性を表す K に付随する依存する種々のキーとそれぞれの属性値の集合と定義される．R(K, σ) の定義の例を図 1 以下に示す．
ここで主要な型 K に格納される値 accessInfo は，ユーザ毎のアクセス権限などの管理情報をモデル化したものであり，その詳細は本研究の対象外である．
プログラムからこれらキーバリューストア上のデー
タを操作するためには，プログラムに対して，これら構造を反映する型を与える必要がある．その型はユー
ザにとって使いやすい高水準の表現であることが望ましい．設計上の自由度があるが，ここでは，オブジェ
クト指向の考え方にならい，各値を，それを操作す
R(K, b)=R(K, P tr(σ))

=

=

=

b の名称

K/val

7→

E(b)

K

7→

accessInfo

7→

文字列”ptr” K/val

K/secondK K/type

 K/0


 ···
K/n-1

図1

7→

K


 K/type K/f ist


R(K, Array(σ))

7→ K/type
R(K, P air(σ1 , σ2 ))accessInfo K/type




7→

K




E(P tr(σ))





7→

accessInfo

7→

文字列”pair” 

7→

E(σ1 )

7→

E(σ2 )








7→

accessInfo

7→

文字列”array” 

7→

E(σ)

7→

···

7→

E(σ)








各型のキーバリューストア上の構造

る関数を含むレコードで表現することにする．キー

キー K とその持つべき型の指定を受け取り，キーバ

バリューストア上に格納された σ 型のプログラム上リューストアを探索し，その型チェックを行なった後，の表現を，σ 型の表現型と呼び Obj (σ) と書くことにキーバリューストアの構造に対応するプログラミング

する．Obj (σ) は，キーバリューストアをポートする内のデータ Obj (σ) を作り出す関数を定義することでホスト言語の型である．本プロジェクトでは，ホストある．それら関数は，高水準で系統的なアクセスが可

言語は我々が開発した次世代高信頼言語 SML# であ

能な高階の汎用関数であることが望ましい．理想的にり，Obj (σ) は SML# の型である．図 2 に定義の例をは，以下の汎用の関数が実現できることが望ましい．

示す．

create : ∀t :: KV S.string * t -> unit

ここで，Obj (b) は，キーバリューストアに格納さfind : ∀t :: KV S.string -> Obj (t)れる標準フォーマットの基底型 b を意味する．通常のこれら関数の直感的な意図は以下のとおりである．

意味でのキーバリューストアに格納された基底型 b のcreate は，キーと型 t の値の組みを受け取り，型 t

プログラム上の型は Obj (P tr(b)) である．Obj (b) のの任意のインスタンス型 σ に対応する構造 R(K, σ)

定義は，配列などの複合型にキーではなく直接基底をキーバリューストアに構築する．find 関数は，型

型 b の内容を格納することをゆるすために必要となt の任意のインスタンス型 σ に対して，前述の [1] 等る．これら両者の詳しい関係は，本稿に続く論文で詳の Dynamic 型の理論とキーバリューストア内に保存述する予定である．

された構造 R(K, σ) をチェックし，成功すれば，プ

これらは SML# の通常の型であるため，それらのログラムから操作するためのデータ構造 Obj (σ) をメ

型をもつオブジェクトの作成ができたなら，その型にモリー上に構築する．従って，find が一旦成功すれ応じた操作を適用することができる．

ば，その後の操作はすべて型安全であることが保証

残る課題は，ユーザから指定された任意のキー Kされる．しかしながら，型 t のインスタンス σ 型にと型 σ を持つ任意の値 V に対して，キーバリュース

対するキーバリューストア内の構造 R(K, σ) やメモ

トア上に R(K, σ) で定義した構造を作り出す関数と，リー上の構造 Obj (σ) は，σ に応じて異なっているたObj (b) = E(b)Obj (P tr(σ)) = {key : string, getVal : unit -> Obj (σ), putVal: Obj (σ) -> unit}

Obj (P air(σ1 , σ2 )) ={key : string, getFirst : unit -> Obj (σ1 ), putFirst : Obj (σ1 ) -> unit,
getSecond : unit -> Obj (σ1 ), putSecond : Obj (σ1 ) -> unit }Obj (Array(σ)) ={key : string, length : int, getElem : int -> Obj (σ1 ),putElem : int * Obj (σ1 ) -> unit}

図2

キーバリューストアオブジェクトのプログラム上の表現

め，これら関数の動作は，唯一のコードのインスタン

create と find の関数適用に，そのインスタンス σ

スとして表現することはできず，これらを実現するパに対する適用に対してそのオブジェクトを適用を自動

ラメトリック多相な多相関数は存在し得ない．

挿入することである．この２つが実現できれば，そこで本研究では，型 t のインスタンス型 σ に対create : ∀t :: KV S.string * t -> unit

して，create 及び find を実現するために必要な処

find : ∀t :: KV S.string -> Obj (t)理，すなわちキーバリューストア上の値の作成，キーの型の多相関数が実現できることになる．この中の後の探索と型チェック，対応するオブジェクトの作成に者の課題は，SML# のもつレコード多相性のための必要な機能を持ったメタオブジェクト M(t) を型に関型主導コンパイル方式で実現可能である．この点にして帰納的に定義し，create 及び find を，それら関する詳細は，本稿に続く論文で報告することとし，を引数として受け取る以下の高階の関数として実現

以下本稿ではメタオブジェクト M(σ) の定義の方針する戦略をとる．

を提示する．

create : ∀t :: KV S.M(t) -> string * t -> unit

1. int 型などの原子型の場合．Obj (b) の定義の箇

find : ∀t :: KV S.M(t) -> string -> Obj (t)

所で説明した通り，M(b) は，標準文字列表現を

create と find は，M(t) をそれらを実現する機能をつくるためのものであり，キーバリューストアの含む以下のような構造のレコードとして表現すれば，構造を作るものではない．create と find を標

SML# のレコード多相性を用いて必要なフィールド

準のシリアライザを用いて直接定義する．これにをアクセスし処理を実行する高階の多相関数関数と加えて，これら型を引数としてとる型構成子の定して実現可能である．

義のために，型チェック文字列 type フィールド{create :と E(int) の生成方法を表現する encode フィー

find :.
.
.

string * ’a -> unit,
string -> Obj(’a),}

ルドを持つ．int 型のメタオブジェクト M(int)は以下の型を持つ．

{type :

string,find は，M(t) を受け取り，そのレコードの create

create :および find フィールドを取り出し利用するだけで実find :

現可能である．そこで，解決すべき課題は，KV S 集

encoder :合の任意の要素型 σ に対して，上記フィールドを含をメタオブジェクト M(σ) を定義すること，およびstring * int -> unit,
string -> int,
int -> string}
ここで，type および encode フィールドは，以下の再帰的定義を実現するためのものである．

2. キーバリューストア上のポインタ M(P tr(σ))

えられ，キーバリューストアの簡便なアクセス機能型．通常の意味での基底型のキーバリュースト

が SML# 上に実現できると期待される．これらの結ア表現を作成するためのメタオブジェクトであ果は，本稿に続く論文にて報告予定である．

る．M(P tr(b)) は，M(b) を引数として取り，その type フィールド，encoder フィールドを使っ謝辞て，メタオブジェクトを生成する汎用高階関数を本研究の一部は，以下の研究補助金の助成を受けてM(b) に適用することによって生成する．

実施されたものです．

1. 文部科学省委託研究「イノベーション創出を支

val ptrMeta: [’a#{encoder: ’b -> string,
find: string -> ’b,ty: string}, ’b.
’a -> {encoder: Obj (’b) -> string,
find: string -> Obj (’b),

える情報基盤強化のための新技術開発— 高機能
高可用性情報ストレージ基盤技術の開発」

2. 科 学 技 術 補 助 金 基 盤 研 究（B) 課 題 番 号
25280019「ML 系多相型言語 SML# の実用化技術に関する基礎研究」

init: string * ’b -> unit,ty:string}]
3. ’a array のような型パラメタを持つ型構成子．
上記の場合と同様の考え方により，要素の型のメ
タオブジェクト M(σ) を受け取り M(σ array)を返す高階の関数を定義することによって実現す
る．array 型構成子を実現する汎用の高階関数の定義を，Obj (’b) の部分も含め，図 3 に示す．
以上の方針に基づき M(σ) を KV S 集合全体に対して定義し，実装実験を行なった．図 4 はその実行トレースである．

4 まとめと今後の課題
本研究では，キーバリューストアを簡便かつ型安全に多相型関数型言語から利用するための枠組みを提案し，その枠組みをコンパイラに組み込むための型システムを構築した．この型システムは，型に関して帰納的に定義されるメタオブジェクトを使い，系統的なアクセスを実現している．提案した枠組みの実用性を確認するため，簡単なインタープリタを試作し，その実効性を確認した．
現在，以上の結果をコンパイラに組み込む機構を構築中である．さらに，SML# の型主導コンパイルの技術を応用すれば，メタオブジェクトの生成と適用
はコンパイラによって自動的に行うことが可能と考参 考 文 献[1] Martı́n Abadi, Luca Cardelli, Benjamin C. Pierce,and Gordon D. Plotkin. Dynamic typing in a statically typed language. ACM Trans. Program. Lang.
Syst., 13(2):237–268, 1991.
[2] Fay Chang, Jeﬀrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows,
Tushar Chandra, Andrew Fikes, and Robert E.
Gruber. BigTable: A distributed storage system
for structured data. ACM Trans. Comput. Syst.,
26(2):4:1–4:26, June 2008.
[3] Giuseppe DeCandia, Deniz Hastorun, Madan
Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo:
Amazon’s highly available key-value store. In Proceedings of twenty-first ACM SIGOPS symposium
on Operating systems principles, SOSP ’07, pages
205–220, 2007.
[4] Martin Elsman. Type-specialized serialization
with sharing. In TFP’05: Revised Selected Papers
from the Sixth Symposium on Trends in Functional
Programming, pages 47–62, 2005.
[5] Grégoire Henry, Michel Mauny, Emmanuel Chailloux, and Pascal Manoury. Typing unmarshallingwithout marshalling types. In Proceedings of the
17th ACM SIGPLAN international conference on
Functional programming, pages 287–298, 2012.
[6] Andrew J. Kennedy. Pickler combinators. J.
Funct. Program., 14(6):727–739, November 2004.
[7] Xavier Leroy and Michel Mauny. Dynamics in ml.
J. Funct. Program., 3(4):431–463, 1993.
[8] Atsushi Ohori and Katsuhiro Ueno. Making Standard ML a practical database programming language. In Proceedings of the 16th ACM SIGPLAN
international conference on Functional programming, pages 307–319, 2011.

val arrayMeta = fn
: [’a#{encoder: ’b -> string, find: string -> ’b}, ’b.
’a-> {encoder:{getElem: int -> ’b,
getLength: unit -> int,
key: string,
putElem: int * ’b -> unit}-> string,find:string-> {getElem: int -> ’b,
getLength: unit -> int,
key: string,
putElem: int * ’b -> unit},
init: string * (int * ’b) -> unit,
ty: string}]
図3

配列型を実現する汎用高階関数# init (arrayMeta intMeta) ("arrayKey", (78, 0));val it = () : unit
# val intArrayObj = find (arrayMeta intMeta) "arrayKey";val intArrayObj = {getElem = fn, getLength = fn, key = "arrayKey", putElem = fn}: {getElem: int -> int,
getLength: unit -> int,
key: string,
putElem: int * int -> unit}# #getLength intArrayObj ();val it = 78 : int# #getElem intArrayObj 0;val it = 0 : int# #putElem intArrayObj (0,888);
val it = () : unit
# #getElem intArrayObj 0;val it = 888 : int# find (arrayMeta intMeta) "bogusKey";
uncaught exception: TypedKVS.KeyNotFound# find intPtrMeta "arrayKey";
uncaught exception: TypedKVS.TypeMismatch
図4

型付きキーバリュースト実証アプロトタイプ実行例