多相からプログラミング言語を見る

こんにちは。ホビー型システミストの岡本です。

最近 C++ の習得をしていて、なんとなく多相（polymorphism）の視点からいくつかのプログラミング言語をまとめてみようという気になったので書いてみます。

部分型多相（subtype polymorphism）

クラスベースオブジェクト指向言語でよく使うのは部分型多相ですかね。

Java や C#・C++ にある、名称的部分型多相（nominal subtype polymorphism）はこんな感じ。次の例は Java です。

class A {}

class B extends A {}

public class Main {
    public static void main(string[] args) {
        A foo = new B();
    }
}

変数 foo は A 型だけど、型（クラス）B は A の部分型（サブクラス・派生クラス）なので、foo は B 型の値に束縛することができます。

C や Haskell にはこれはありませんね。ML 系言語もないのかな。

部分型多相には名称的の他に構造的部分型多相があります。次の例は TypeScript です。

class A {
  public readonly foo: number;

  public constructor(foo: number) {
    this.foo = foo;
  }
}

class B {
  public readonly foo: number;
  public readonly bar: string;

  public constructor(foo: number, bar: string) {
    this.foo = foo;
    this.bar = bar;
  }
}

const bar: A = new B(0, "");

型 B が A の部分型であると明記していませんが、B は A として扱うに足るフィールドを持つので A として扱うことができます。

構造的部分型多相は TypeScript や Go にあります。

静的なダックタイピングと見ることもできるかも。

PureScript にある列多相（row polymorphism）も構造的部分型多相の一種なのかな。こっちは余分なものがあるということを r で明記していますが。

foo :: { name :: String, age :: Int }
foo = { name: "foo", age: 0 }

name :: forall r. { name :: String | r } -> String
name p = p.name

name foo

パラメーター多相（parametric polymorphism）

パラメーター多相は Java・C#・C++ でそれぞれジェネリクス・ジェネリック・テンプレートと呼ばれるものです（C++ のテンプレートはちょっと違うかも）。

恒等関数を Java・C#・C++・Haskell で書くと次のような感じ。

<T> T id(T value) { return value; }

T Id<T>(T value) { return value; }

template<typename T>
T id(T value) { return value; }

id :: a -> a
id a = a

一般的には型変数になった型（上記でいう T や a）に関する性質は使えません。T や a にはどんな型も来られるようにしないといけないためです。性質を使いたい場合は後述します。

アドホック多相（ad-hoc polymorphism）

例えば + 演算子について Int -> Int -> Int という型としても使いたいし Double -> Double -> Double としても使いたく、そして実装が違う、という場合に出てくるのがアドホック多相です。

Java・C#・C++ だとオーバーロードと呼ばれます。Haskell だと型クラスで、他言語だと同様のものはトレイトやプロトコルなどと呼ばれるようです。

std::string hello(int a) { return std::to_string(a); }
std::string hello(std::string a) { return a; }

class Hello a where
  hello :: a -> String

instance Hello Int where
  hello = show

instance Hello String where
  hello = id

アドホック多相が他の多相と組み合わさると、どの実装が選ばれるのかのアルゴリズムを知るために言語仕様を読むはめになってちょっとやっかいです（個人の感想）。

オーバーロード

Java・C# のオーバーロードは機能がちょっと弱くて返り値に関する多相にできません。

C++ でもストレートにはできませんが、テンプレートを使って実現できます。基本的にパラメーター多相のためのテンプレートですが、アドホック多相にも使うというのがややこしいところ。

#include <climits>

int max() { return INT_MAX; }
long int max() { return LONG_MAX; }

// prog.cc:19:10: error: ambiguating new declaration of 'long int max()'
//    19 | long int max() { return LONG_MAX; }
//       |          ^~~
// prog.cc:18:5: note: old declaration 'int max()'
//    18 | int max() { return INT_MAX; }
//       |     ^~~

#include <climits>

template<typename T>
T max();

template<> int max<int>() { return INT_MAX; }
template<> long int max<long int>() { return LONG_MAX; }

型クラス

型クラスのコードはパラメーター多相を使ったコードに変換することができます。下記は Haskell での例です。

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeSynonymInstances #-}

main :: IO ()
main = do
  putStrLn $ hello (0 :: Int)
  putStrLn $ hello "Job"
  putStrLn $ hello' fooDictInt 0
  putStrLn $ hello' fooDictString "Job"

-- 型クラスを使ったコード
class Foo a where
  foo :: a -> String

instance Foo Int where
  foo = show

instance Foo String where
  foo = id

hello :: Foo a => a -> String
hello a = "Hello, " ++ foo a ++ "!"

-- パラメーター多相に変換したコード
data FooDict a = FooDict { foo' :: a -> String }

fooDictInt :: FooDict Int
fooDictInt = FooDict { foo' = show }

fooDictString :: FooDict String
fooDictString = FooDict { foo' = id }

hello' :: FooDict a -> a -> String
hello' FooDict { foo' = f } a = "Hello, " ++ f a ++ "!"

実際 Haskell のデファクトスタンダードのコンパイラーである GHC は型クラスを上記のように脱糖します。Int に関する Foo のインスタンスは一意に決まるので fooDictInt を自動的に挿入できるという寸法です。この辞書を暗黙に挿入するので Scala ではインプリシットパラメーターというらしいです。

多相の組み合わせ

先述したパラメーター多相のパラメーターを性質で制限したい場合について記述します。それにはアドホック多相を採用する言語と部分型多相を採用する言語があります。

パラメーターを部分型多相で制限する

部分型多相で制限する場合は「特定の型の部分型でないといけない」というように制限します。Java や C# などがそうです。下記は Java の例です。

public class Main {
    public static <T extends Hello> String greet(T target) {
        return target.hello() + "!";
    }
}

interface Hello {
    String hello();
}

T は Hello の部分型であることが保証されるので target.hello が呼べるわけですね。

パラメーターをアドホック多相で制限する

型クラスで制限する場合は「特定の型クラスを実装している型でないといけない」というように制限します。Haskell などがそうです。下記は Haskell の例です。

greet :: Hello a => a -> String
greet a = hello a ++ "!"

class Hello a where
  hello :: a -> String

a は Hello 型クラスを実装していることが保証されるので hello が呼べるわけです。

C++ の場合はちょっと変わっていて関数を使用すると暗黙にその関数の存在が要求されるようです。次のコードは、Java や C# と違ってエラーなくコンパイルできます。

#include <string>

template<typename T>
std::string greet(T target) {
    return hello(target) + "!";
}

std::string hello(int) のない int について greet(0) のように呼ぶとエラーになります。

int main() {
    std::cout << greet(0) << std::endl;
}
// prog.cc: In instantiation of 'std::string greet(T) [with T = int; std::string = std::__cxx11::basic_string<char>]':
// prog.cc:10:25:   required from here
// prog.cc:5:17: error: 'hello' was not declared in this scope; did you mean 'ftello'?
//     5 |     return hello(target) + "!";
//       |            ~~~~~^~~~~~~~
//       |            ftello

ここで下記のような std::string hello(int) を用意してやるとエラーが解消されます。

std::string hello(int n) {
    return std::to_string(n);
}

暗黙の型クラスのようなものが要求されていると見ることもできます。これが C++ 20 のコンセプトなのかな？

他の多相

線形型があると線形性に関する多相とか他にもいろいろあるだろうけどよく知らないのでこの辺で。