抽象データ型とはなんぞや？

fsharp-lessonで抽象データ型を定義する段になり、抽象データ型の解説をリンクしようとした所、どうも良い解説が無い。仕方ないので自分で解説を書く事にする。

この記事では抽象データ型、Abstract Data TypeをADTとも略します。

この記事は初心者向けの話なのでベテランは読む必要はありません。

データ型を考える

抽象データ型（Abstract Data Type）とは、データ型の拡張と考えるのが良い。

抽象データ型を考えるには、まず抽象じゃないデータ型を見てみるのが良い。という事で単なるデータ型を考えよう。

データ型というのは、ようするにintとかfloatとかの事です。データ型というのは、それを使って変数を定義したりして、プログラムを書くのに使います。

int x = 0;

int SomFunc(int b) { ... }

float y = 0;
float SomeFunc2(float c){ ... }

さらに、普通の言語なら、それらを組み合わせたデータ型も新しいデータ型として定義出来る。具体的にはC言語なら構造体、F# ならレコード型などがそれに当たります。

例えば以下のような極座標を表す型を考えてみます。

struct Polar{
  doulbe radius;
  doulbe theta;
};

このPolarという型は、以後はfloatなどと同じようにデータ型として使える。（Cじゃ使えないけどC++なら使えるからいいでしょう）

Polar p;

Polar SomeFunc3(Polar z) { ... }

先程のintやfloatの例との類似性に着目してください。

こうやって既存の型を組み合わせて新しい型を定義し、その型に対してプログラムをしてく、というのは、普通のプログラミングですね。

つまりデータ型というのは普通は、

intやfloatなどのprimitive型
primitive型を組合わせた型（およびそれをさらに組み合わせたもの）

という感じで定義されるものです。

つまり提供されているprimitive型と、それを組み合わせる言語機能（Cならstruct）の２つで構成される事が分かります。

抽象データ型

抽象データ型というのは、この既存の型を組み合わせて新しい型を作るstructという機能の兄弟のようなものと考える事が出来ます。

抽象データ型は名前に操作を並べたものとして定義されると考える。 C言語に抽象データ型そのものは無いので、ここでは新しい仮想的なadtとい機能で抽象データ型が定義出来るとしましょう。

すると、それは例えばこんな感じになる。

adt Polar{
  double toX()
  double toY()
}

こうして定義した型をそれまでと同じように使えると考える。

Polar p;

Polar SomeFunc4(Polar w){ ... }

このように、structがその構成要素のprimitiveで定義出来る新しい型であるのと似た考え方で、型の名前とその行える操作を並べたものを型として定義出来るようにする、というアイデアを、抽象データ型といいます。

上記のコードでこのPolarが、いかにintやfloatの例と似ているのか、という事をよくよく考えるのが大切です。

現代において抽象データ型を理解するのに重要なポイントとしては、まず最初は実現方法は「考えない」というのが大切です。以下その辺の事を説明したいと思います。

抽象データ型を学ぶ最初の一歩は、実現方法を「考えない」こと

既存の抽象データ型の解説を読んで、こりゃ意味分からんな、と思うのは、最初に実現方法の話をしてしまうからです。

上記のようなadtのような事を現在の言語機能でどう実現するか、と考えると途端に意味がわからなくなります。これは現代のプログラム言語の機能が抽象データ型を実現する為に使える機能を拡充していった為、個々の機能との区別がつきにくいからです。実現方法を考えてはいけません。実現方法を考えてはいけません。実現方法を考えてはいけません。とりあえず三回繰り返しておきます。

抽象データ型を考える上でポイントになるのは、考え方を理解する事です。実現方法に目をやってはいけない。考え方に集中する。実現方法はどうでもいい。実現したいアイデアはなにか？という事に集中する。

その実現したいアイデアはなにか？と言えば、structと類似のなにかで、新しいデータ型を定義するような言語機能があるかのような世界をつくりたい、と考える事です。

そして抽象データ型は名前の通り型に注目するのが大切です。現代の用語で言うとインスタンスに着目してはいけない。型に着目する。型を定義する方法。型を定義する方法。型を定義する方法。大切なことなので三回繰り返しました。

新しい型というのを、structはその構成要素を並べる事で定義します。同様に、adtはその行える操作を並べる事で定義します。この、yet anotherな型定義の方法だ、という事を強烈に意識していないと、なんなのかわからなくなってしまいます。

メソッドを用意して内部の構造の情報を隠す、とかそういう風に考えてはいけません。それは実現方法だから。実現方法を考えてはいけません。実現方法を（以下略）

とにかく、structと同じような感じで新しく型を定義出来ると考える、というのが大切なんです。

struct Polar{
  doulbe radius;
  double theta;
};

と、

adt Polar{
  double toX();
  double toY();
}

の類似性を強烈に考えるのが大切です。「radius」の所を「toX()」に置き換えただけですよね。そういう、ほとんどstructと同じように定義出来るなにかだ、と強く思い込むのが大切です。抽象概念というのはそういうものです。

primitiveを並べるstruct、operationを並べるadt。違いはそれだけ。

抽象データ型は名前の通り「抽象的」なので、実体を強烈に頭でイメージしてやらないと、実在出来ない。このイメージを確固たる状態に出来てない状態で実装方法を考えると意味がわかりません。

群を考える時に具体的な整数の足し算に引きずられてしまうと群が分からないのと一緒です。概念の方に集中して、具体的な足し算の事は一旦忘れる。

使う側を考えてみる

実装側は考えてはいけない、という事で、使う側を強烈に考え続けるのがADT理解の第一歩です。という事でここでも実装は考えずに使う事を考えましょう。

構造体を定義すると、その要素には以下のようにアクセス出来ます。

struct Polar{
  double radius;
  double theta;
};

Polar p;
p.radus = 0.2;

このように、定義するのに並べた要素を使う事が出来る。同じようにadtも定義するのに並べた要素は、何らかの方法で使えると考える。

adt Polar {
  double toX()
  double toY()
};

Polar p;
(toX p);

クラスと違いを強調する為に、適当なシンタックスを導入しました。

これをもとに、例えば以下みたいなコードを考える。

adt Polar {
  double toX()
  double toY()
};

double calcArea(Polar p) {
  return (toX p)*(toY p);
}

こうやってプログラムを書いていけるというのは想像出来ると思います。

この時に、structのコードとの類似性に着目するのがポイントです。adt Polarの実現方法に注意をそらしてはいけない。型の上ではstructとほとんど同じ、と考えるのが重要です。

抽象データ型とは、このように型を定義する新しい方法であり、またそれを用いてプログラムをするのが素晴らしい、というアイデアです。どう素晴らしいのかについてはこの記事の末尾に足した原典を読むと良いと思いますし、説明されなくても現代的なプログラマならだいたい想像出来るでしょう。そこは難しい話じゃない。難しいのは新しい型の定義方法だと、強烈に型を意識して思い込む所です。

抽象データ型とは、新しいデータ型を定義する方法についての、仮想的なアイデアです。

F#でなんでADTが重要になるのか

F#でクラスをなるべく作らない方がいいのは、この辺とかこの辺にも書かれている所です。端的に言ってしまえばカリー化を使って部分適用をする事で新しい関数をバンバン生成するスタイルと相性が悪いからですね。

でもmoduleを使ってADTを実現するのは良くやります。なのでクラスと区別がついていないと困ってしまう。 moduleでclassの出来損ないをエミュレートしようとしてしまっては本末転倒です。それではclassと同じ弊害を持ち込んでしまう。 ADTをより直接実装する方が望ましい事が多く、そのためにはADTが何なのかをわかっている必要がある。

何がADTなのか、という事がわかっていれば、実現方法は見れば誰でも分かるので実現方法はそんなに解説する必要は無いと思う。それよりも実現したいのがなにか、という事をわかっていないと困る。

でも抽象データ型の説明を探すとどうも特定の実現方法（特にJavaとか）の話ばかりしてしまって、それをmoduleなどの方法で実現するのにあまり役に立たない解説が多かった。

一方、ここまでの解説をちゃんと理解出来ていれば、クラスとは別の言語機能でADTを実現する方法も、それをやっているコードを見れば理解出来ると思います。

例えばmoduleでPolarのADTを実現しようと思えば、以下みたいな感じで実装する事になります。

module Polar =
  type T = {Radius: double; Theta: double}

  let init rad theta =
    { Radius=rad; Theta=theta }
  
  let toX p =
    p.Radius * cos(p.Theta)

  let toY p =
    p.Radius * sin(p.Theta)

さっきの点の下の長方形の面積を求める例は以下のようになる。

let calcArea p =
  (Polar.toX p)*(Polar.toY p)

pの作り方は以下みたいになる。

let p = Polar.init 3.0 0.5*PI

こんなものは、F#をわかっていれば誰だって読めば分かる。大切なのは実現方法では無くて、さきほどの仮想的なコードとの類似性です。さきほどの仮想的なコードが頭に無いとADTとしては見る事が出来ない。

このコードを、以下のように心の目で見る、というのが大切です。

module Polar =
  let toX p
  let toY p

let calcArea p =
  (Polar.toX p)*(Polar.toY p)

Polarを定義するのにオペレーションを並べている。しかも実装では無くてシグニチャを並べているだけで定義されるなにかだと考える。

抽象データ型を理解するというのは、コードをこう眺める事が出来て、こうして見たコードが先程のadtという仮想的な構成方法を使ったコードととても似ているという事を理解出来る事であり、またこういう風に読めるようなコードを書けるという事です。

型を作る新しい構築子のようなものがある、と考える訳です。型を作る新しい方法。型を作る方法だというのが大切です。

ちなみにちょっとだけF#特有な事情は、pの型はPolarじゃなくてPolar.Tになっています。この辺は紳士協定でTとする事にして、心の目では.Tは見ない事にする、という事になっています。

F#は型に着目するのが大切で、以下のように、型を最初に設計するのも良くある事です。

type CalcArea = Polar.T -> Double

こういう風にPolar.Tを型として考えて、その上での演算をType-Firstに試行錯誤するのは、Type-First Developmentが良いという話でも以前に書きました。

「型でいろいろな事を試行錯誤する」という言語の性質から、型というものの重要性がより高いので、新しい型の定義の仕方、というのも重要な訳です。

Record、Discriminated Union、Abstract Data Typeの３つの定義方法を使いこなしてバンバン新しい型を作っていきたい。

原典の話とか

Liskov女史の原典を今見ると、割とわかりやすく具体的に書かれている。

Programming with abstract data types - Proceedings of the ACM SIGPLAN symposium on Very high level languages

この例に使われている、この時点での仮想言語はのちのCLUという奴だと思うけれど、それでのadtの定義は以下のようになる。

stack: cluster(element_type: type)
  is push, pop, top, erasetop, empty ;

clusterがadt定義の専用機能のようですが、こうやって操作を並べるだけでデータ型を作ってそれを使っていく、というのがそのまま実現されていて分かりやすい。そしてelem_typeはgenericsの引数のようなものですね。

stack型の変数sを定義するのは以下のようになっている。

s: stack(token)

カッコのtokenは現代で言う所のgenericsの引数ですね。そしてコンストラクタ的な事もここでしていた模様。

generics引数的なものを省略して少しisとかなくすと以下みたいになる。

stack: cluster
  push, pop, top, erasetop, empty ;

s: stack // stack型の変数の定義

こんな風にオペレーションだけ並べて型を定義するのが抽象データ型。

そしてこうして作った変数sに対して以下のように操作していたらしい。

stack$push(s, tk)

stack$erasetop(s)

使う方はおいといて、データ型の定義は割とアイデアそのままで、普段F#でADT作って使っている自分たちからすると分かりやすいですね。

これをJavaとかで考えようとするから変な話になるので、クラスの無い（F#にはクラスあるけど）言語で考えるのが入門には良いでしょう。

そもそもにクラスなどの現代的なオブジェクト指向言語の機能はこれらのアイデアを実現するのに都合が良いように作られているので、見た目がとても似ていて、違いは何なのか？とか考えるのは混乱しやすい上に大してご利益もありません。そうした言語でもADTとしても見る事が出来る視点を持つのは良い面もありますが、はじめてそういう概念を学ぶ人のための学習目的には不向きでしょう。

F# などのようにADTを手作りしないといけない上にデータ型の重要度が高い言語の方が、こうした話の重要度は高いし、また理解もしやすいと思う。実現したいアイデアと作り方に多少の距離があるので両者の違いに悩む必要も無いし。

型がそこに入る事の出来る要素の集合を表すと考えると、集合の性質をそこに適用出来る演算で考えるというのは、代数的構造を考えるのと似た話で、ある種馴染みのある考え方と感じる人も多いでしょう。リー群とかと似てますよね。

現代においてADTで重要なのは、ADTとしてコードを見るというものの見方です。 structと同じようにadtという言語機能がある、と思ってコードを見てみるのが大切です。情報隠蔽がどうとかメンバにアクセスしないとかそういう実現方法はADTの話ではありません。 ADTとは何を実現したいのか、という話です。実現方法では無く実現したい事、つまりどういう風にコードを見るのか、という事をマスターしましょう。