ATSプログラミング入門:
Prev		Next

Chapter 15. 線形データ型としてのデータ観型 (dataviewtype)

Table of Contents
線形オプショナル値
線形リスト
例: 線形リストのマージソート
例: 線形リストの挿入ソート
例: 線形リストのクイックソート
線形2分探索木
データ型からデータ観型への翻訳

データ観型 (dataviewtype) はデータ型の線形バージョンとして考えることができます。おおざっぱに言うと、データ観型はデータ型とデータ観との組み合わせです。このプログラミングの機能は手動でメモリ管理をする状況下でパターンマッチのような利便性を提供することを主な目的として ATS に導入されています。 GC を削減したり完全に除去しなければならない状況下では、データ観型はしばしばデータ型を置き換えることになります。この章ではいくつかの一般的に用いられるデータ観型とその使い方を紹介します。

線形オプショナル値

オプショナル値が生成さると、その値はたいがいすぐに使われて破棄されます。そのような値に線形型が割り当てられているなら、値を保管するために確保されたメモリを効率よく回収することができます。線形オプショナル値を表わすデータ観型 option_vt は次のように宣言されます:

//
datavtype
option_vt (a:t@ype+, bool) =
  | Some_vt (a, true) of a | None_vt (a, false) of ()
// end of [option_vt]
//
vtypedef Option_vt (a:t@ype) = [b:bool] option_vt(a, b)
//

datavtype は単に dataviewtype の短縮バージョンであることに注意してください。導入されたデータ観型 option_vt は1番目の引数について共変です。また関連した2つのデータコンストラクタ Some_vt と None_vt があります。次の例では、find_rightmost 与えられた述語を満たすようなリスト中の最右辺の要素を見つけようとします:

fun{a:t@ype}
find_rightmost
  {n:nat} .<n>.
(
  xs: list (a, n), P: (a) -<cloref1> bool
) : Option_vt (a) =
(
  case+ xs of
  | list_cons (x, xs) => let
      val opt = find_rightmost (xs, P)
    in
      case opt of
      | ~None_vt () => if P (x) then Some_vt (x) else None_vt ()
      | _ (*Some_vt*) => opt
    end // end of [list_cons]
  | list_nil () => None_vt ()
) (* end of [find_rightmost] *)

パターン None_vt() の前にあるチルダ記号 (~) は、そのパターンにマッチしたノードのためのメモリが、そのマッチ節の本体が評価される前に解放されることを表わすことに注意してください。この例では、None_vt は NULL ポインタにマップされるので、実際にはメモリの解放は起きません。データ観型に関連するコンストラクタのために確保されたメモリを解放する方法については、詳細をすぐに解説します。

別の例として、次の関数テンプレート list_optcons は与えられたオプショナル値を展開した要素を先頭にした新しいリストをコンストラクトします:

fn{a:t@ype}
list_optcons
  {b:bool}{n:nat}
(
  opt: option_vt (a, b), xs: list (a, n)
) : list (a, n+bool2int(b)) =
  case+ opt of
  | ~Some_vt (x) => list_cons (x, xs) | ~None_vt () => xs
// end of [list_optcons]

記号 bool2int は true と false をそれぞれ 1 と 0 に変換する ATS におけるビルトインの静的な関数です。ここで注目すべきなのは、list_optcons の最初の引数が線形であり、list_optcons 呼び出しが返ると消費され、それが占有していたメモリは回収されるということです。

Prev	Home	Next
観変化のための証明関数	Up	線形リスト