Zenn
⌨️

直和型の代わりにユニオン型を持つ静的型付け関数型言語 Cotton

2023/02/02に公開
15件
コンパイラ
自作言語
tech
// 割る2をする関数の引数が偶数であることを型によって強制する例（実用性はない）

data O // 数字の0を表すデータ型
data S(A) forall { A } // +1を表すデータ型

// 型エイリアス
type Nat = O | S[Nat] // 非効率すぎる他倍長整数
type Even = O | S[Odd]
type Odd = S[Even]

// 偶数を引数にとって2で割った結果を言語組込みの整数として返す関数
div2 : Even -> I64 =
    // 網羅性チェックつきのパターンマッチ
    | O => 0
    | S(S(n)) => 1 + n.div2

TL;DR

ユニオン型は直和型の上位互換である（追記あり）。関数型言語を作るときは直和型の代わりにユニオン型を採用するのもあり。

はじめに

Cottonというプログラミング言語を2021年の夏頃から作っています。2022年度の未踏にも採択していただきました。まだまだ未熟な言語ですが、未踏の成果報告会も近いので紹介記事を書くことにしました。前半ではCottonの言語仕様の紹介を、後半では直和型と比較したユニオン型のメリットについて解説していきます。

どんな言語？

Cottonは静的型付けの関数型言語です。網羅性チェックのあるパターンマッチが使えますが、Rustのenumや、OCamlやHaskellの（複数のコンストラクタを持つ）データ型のような、パターンマッチが使える言語によくある機能（適切な用語がいまいちよくわかっていないのですが、ここでは直和型と呼ぶことにします）は持っておらず、代わりにTypeScriptやCrystalにあるようなユニオン型が使えます。これが「直和型の代わりにユニオン型を持つ」というタイトルの意味です。

HaskellやOCamlなどの言語が好きな人は直和型が大好きなイメージがありますが、私は直和型よりもユニオン型の方が表現力が高く、優れていると思っています。静的型付け関数型言語とユニオン型の相性の良さを実例として示し、新しく関数型言語を作る人が自分の言語に直和型ではなくユニオン型を採用しようと思うようにすることがこの言語の目的の１つでもあります。

またユニオン型以外にもCottonの魅力はいろいろあります。シンプルながら必要な機能が備わっていて書きやすい言語を目指しています。

用語の定義

さっきから「直和型」と「ユニオン型」という用語を使っていますが、これらの用語はプログラミング言語によって全然別の意味で使われる厄介な用語です。例えば Vのsum typeは私が思うユニオン型ですし （追記あり: [1] ）、CやC++、Rustのunion（共用体）は私が言いたいユニオン型とは全くの別物です。そのため、本題に入る前にこの記事で使っている「直和型」と「ユニオン型」の意味を明確にしたいと思います。わざわざ説明されなくても雰囲気で大体わかったという人は読み飛ばしてください。

ユニオン型とは、TypeScriptやPython、Crystal、Juliaなどの言語が持つようなユニオン型のことであるとします。これらの言語のユニオン型は、次のような性質を持っています。

  • 0個以上（言語によっては1個以上？）の型から構成される。
  • ユニオン型を構成するすべての型は、そのユニオン型の部分型である。（ここで部分型というのは、部分集合の型バージョンのようなもので、次のような性質を持つものであるとします: AがBの部分型であることは、Bを引数に取る関数に、Aの値をそのまま（明示的な型変換をせずに）渡すことができることと同値。）
  • 名前をつけることなく作ることができる。（例えばTypeScriptではstring | numberに対してtype StringOrNumber = string | numberというように名前をつけることができるが、別につけなくてもstring | numberは使える。）
  • 実行時に、値がどの型に属すものなのかを判別できる。（例えばTypeScript（JavaScript）ではtypeofやinstanceofなどを使って実行時の型を知ることができる。）
  • 組み込み型を含めた任意の型をユニオン型の構成要素とすることができる。

ここで列挙した性質は、私と皆さんの認識をすり合わせるために適当に選んで列挙したものなので、他にも追加できる性質や追加すべき性質はあるかもしれません。

一方直和型というのは、Rustのenumや、HaskellやOCamlのデータ型、F#のdiscriminated unionのような型のことであるとします。次のような性質を持っています。

  • 0個以上（言語によっては1個以上？）の、バリアントやコンストラクタなどと呼ばれるものから構成される。
  • 直和型を構成するバリアントを単体で型として取り出すことができない。（例えば、RustのOptionはSomeとNoneから構成されているが、SomeやNoneという型があるわけではない。）
  • 作るときに名前をつける必要がある。
  • 実行時に、値がどのバリアントのものなのかを判別できる。（これはユニオン型と同じ）

繰り返しになりますが、直和型やユニオン型という用語は、他の文脈では別の意味で使われることがあります。ここで説明したような使い方が正当な使い方だとも思っていません。直和型やユニオン型よりももっと適切そうな用語を知っているという方がいましたらコメントで教えてください。

Cottonの機能紹介

用語の定義だけで長くなってしまいましたね。次にCottonの機能紹介をします。

Playgroundもあるので、読みながら実行してみてください。（Playgroundと言っていますが、Playgroundではなく、Gitpodです。利用するにはGitpodのアカウントを作る必要があります。また初回利用時にはエディターを選択する画面が出てくるので、VS Code Browserを選択してください。）

変数定義

変数は次のように定義できます。（ちなみにコードブロックのシンタックスハイライトはTypeScriptを指定しています）

a : I64 = 1

: I64の部分は型アノテーションです。I64は64ビット整数を意図していますが、現状プログラムはJavaScriptにトランスパイルされるので実際には浮動小数点数です。将来的にはバックエンドをLLVMにする予定です。

型が推論できる場合、型アノテーションは省略できます。

変数はイミュータブルです。ミュータブルにしたい場合は、中身を書き換えることができる専用のデータ構造に値を入れるということにするつもりですが、こちらはまだ実装していません。

関数

引数を２つ取って和を返す関数は次のようになります。

add : I64 -> I64 -> I64 =
    | a, b => a + b

関数定義は変数に関数を代入する形で行います。| a, b => a + bはラムダ式です。

関数呼び出しは、add(1, 2)のようにカッコを使います。

型からわかるように、関数はカリー化されています。つまり、add(1, 2)はadd(1)(2)のシンタックスシュガーです。また| a, b => a + bは| a => | b => a + bと同じ意味です（パターンマッチが絡んでくると若干挙動が変わる場合があるので、シンタックスシュガーではありません）。

演算子定義

Cottonでは二項演算子を定義することができます。例えば次のコードで、+と同じ意味を持つ++++++演算子が定義できます。

(++++++) : I64 -> I64 -> I64 = | a, b => a + b

infixl 6 ++++++

infixl 6 ++++++は、++++++演算子が左結合で、演算子の優先順位が6であることを宣言しています。数字が大きいほうが優先度が高いです。Haskellと同じです。

次のような演算子を定義することもできます。

(.) : A -> (A -> B) -> B forall { A, B } =
    | a, f => f(a)

infixl 10 .

右辺の関数に左辺の値を適用する演算子です。forall { A, B }は、AとBが型変数であることを宣言しています。

この演算子によって、関数呼び出しをオブジェクト指向言語のメソッド呼び出しのように書くことができるようになります。

例えば、f(g(a))は、a.g.fと書けます。また先程のadd(1, 2)は1.add(2)と書けます。

パターンマッチ

フィボナッチ数列の第n項を求める関数は次のようになります。

fib : I64 -> I64 =
    | 0 => 0
    | 1 => 1
    | n => (n - 1).fib + (n - 2).fib

後の3行はこれで１つのラムダ式です。引数に0が来たら0を、1が来たら1を、それ以外が来たら、来た数字をnとして(n - 1).fib + (n - 2).fibを返します。.は先程の.演算子です。prelude（暗黙的にインポートされるモジュール）で定義されているので、先程のように自分で定義しなくても最初から使えます。

Cottonには、HaskellのcaseやRustのmatchのような、指定した値に対してパターンマッチを行う構文はありません。その代わり、| ... => ...を縦に並べることで、ラムダ式の引数の部分でパターンマッチを行うことができます。

引数ではなく、指定した値に対してパターンマッチを行いたい場合は、次のように.演算子を使って行います。

fib : I64 -> I64 =
    | n => n. // ←ここに`.`があります
        | 0 => 0
        | 1 => 1
        | n => (n - 1).fib + (n - 2).fib

パターンは次のようなものを実装しています。

  • リテラル
  • 束縛（変数定義）
  • ワイルドカード（_）
  • コンストラクタ（後述）
  • 型によるフィルター（後述）
  • パターンマッチ中に関数を適用してその結果を更にパターンにかけるパターン（例: examples/apply_pattern.cot#L7）

Hello World

お待ちかねのHello Worldです。次のようになります。

main : () -> () =
    | () => "Hello, world.".println

実行にはmain関数が必要です。main関数の型は() -> ()です。()は特に意味を持たない値()の型です。RustやHaskell、OCamlにもあるやつです。特に情報を渡す（受け取る）必要はないが、言語仕様上値を渡しておく（受け取っておく）必要がある、というような場面で使います。

Cottonは副作用のある言語ですが、関数は必ず１つ以上の引数を取る必要があるためこのような型になっています。

do

printlnを２回呼びたい場合は次のように書きます。

main : () -> () =
    | () => do
        "Hello, world.".println
        "Hello, world.".println

doは、複数の式を１つの式にまとめるための構文です。ラムダ式の=>の右側には、１つの式しか書けないので、複数の式を書きたい場合はdoを使います。

データ型の定義

以下のようにデータ型を定義することができます。データ型はCやRustでいうところの構造体です。

data Dog {
    name: String,
    size: I64,
}
data StringPair(String, String) // フィールドの名前を省略した書き方
data Pair(A, B) forall { A, B } // A, Bは型パラメーターです
data None // フィールドがないデータ型
data Some(A) forall { A }

次のようにして使います。

a : Pair[I64, Some[Dog]] = Pair(
    1,
    Some(Dog {
        name: "pochi",
        size: 1,
    })
)

size_of_pochi = a.
    // パターンマッチ
    | Pair(_, Some(Dog {name: _, size: s})) => s

型の名前とコンストラクタの名前は同じものが使われます。

上のDogのようにフィールドに名前をつけてデータ型を定義すると、そのフィールドと同じ名前の、データ型からフィールドの値を取り出す関数が定義されます。

例えば、

data Dog {
    name: String,
    size: I64,
}

と定義すると、コンパイラによって以下の２つの関数が生成されます。

name : Dog -> String
size : Dog -> I64

そのため次のようにしてフィールドにアクセスすることができます。

pochi : Dog = Dog {
    name: "pochi",
    size: 1,
}

size_of_pochi = pochi.size

ユニオン型

冒頭でも説明した機能です。A | Bのように書くことで、「AまたB」を意味する型を書くことができます。集合でいうところの和集合です。AやBはA | Bの部分型で、(A | B) -> Cのような関数があった場合、AやBの値をそのままその関数に渡すことができます。A | BとB | Aは同じで、A | AとAは同じです。

ユニオン型はパターンマッチによってダウンキャストすることができます。例えば、

data None
data Some(A) forall { A }

a : None | Some[I64] = Some(0)

というようなデータ型と変数があった場合、

main : () -> () =
    | () => a.
        | None => ()
        | Some(i) => i.println

のようにパターンマッチを使うことで、場合分けをしてSomeの中身を取り出すことができます。（printlnはStringに対してもI64に対しても使える関数です。詳しくは後述します。）

次のように型によってフィルターをかけることもできます。

a : String | I64 = 0

main : () -> () =
    | () => a.
        | s : String => "this is a String".println
        | i : I64 => "this is a I64".println

型エイリアス

次のように、型エイリアスを定義することができます。

type Bool = True | False

上はpreludeで定義されているBoolの定義です。

例えばOCamlのoptionやRustのOption、HaskellのMaybeのようなものは、次のように定義できます。（これらもpreludeで定義されています。）

data None
data Some(A) forall { A }
type Option = | A => None | Some[A]

再帰的な型エイリアスも許されます。例えば、単連結リストは次のように定義できます。

data Nil
data Cons(A, List[A]) forall { A }
type List = | A => Nil | Cons[A]

Listの各要素に関数を適用して新しいリストを返す関数mapは次のように定義できます。

map : List[A] -> (A -> B) -> List[B] forall { A, B } =
    | Nil, _ => Nil
    | Cons(h, t), f => h.f.Cons(t.map(f))

オーバーロード

Cottonでは、同じ名前のグローバル変数を複数定義することができます。ただし変数の型は異なっている必要があります。

同じ名前のグローバル変数が複数ある状態でその変数を使った場合、その場所で使っても型エラーにならない変数が採用されます。例えば、次のコードは2を出力します。

a : I64 = 1
a : String = "あ"

main : () -> () =
    | () => (a + 1).println

I64のaを使っても型エラーにはなりませんが、Stringのaを使うと型エラーになるからです。型エラーにならないような候補が複数ある場合もエラーになります。どの変数を採用するかはコンパイル時に決定されます。

他の例も見てみましょう。次のようにすると、別々の型に対してStringに変換するための関数をto_stringという共通の名前で定義することができます。

// preludeをインポートしないようにするための命令です。
// to_stringが既にpreludeで定義されていて、これをつけないとコンパイルエラーになるためつけているだけなので、あまり気にしないでください。
#![no_implicit_prelude]

use prelude::(++)
use prelude::(.)
use intrinsic::*

data Dog {
    name: String,
    size: I64,
}

to_string : I64 -> String = i64_to_string

to_string : String -> String =
    | a => a

to_string : Dog -> String =
    | d => "Dog { name: " ++ d.name ++ ", size: " ++ d.size.to_string ++ " }"

main = | _ => ()

１つの関数の中で候補が複数ある（オーバーロードされている）変数が複数使われていた場合、変数の名前解決はコード上で先にあるものから１つずつ行われます。例えば、次のコードはコンパイルエラーになります。

data D1
data D2
data D3

next : D1 -> D2 = | _ => D2
next : D2 -> D3 = | _ => D3
next : D3 -> D1 = | _ => D1

main : () -> () =
    | () => do
        next(D1.next)
        ()

next(D1.next)の名前解決・型チェックをする際、コンパイラはまず外側のnextを名前解決しようとしますが、内側で使われているのnextがまだ名前解決されておらず、D1.nextの型がわからないため、外側のnextを決定できないからです。

次のようにすればコンパイルできるようになります。

data D1
data D2
data D3

next : D1 -> D2 = | _ => D2
next : D2 -> D3 = | _ => D3
next : D3 -> D1 = | _ => D1

main : () -> () =
    | () => do
        D1.next.next
        ()

まず一番左にあるnextを名前解決しようとするため、D1.nextの型が確定し、それに伴って右側のnextも名前解決することができるからです。

オーバーロードが起きるのはグローバル変数だけで、ローカル変数の場合はシャドーイングが起こります。

インターフェース

TypeScriptやGoのようなインターフェースが使えます。

例:

data Nil
data Cons(A, List[A]) forall { A }
type List = | A => Nil | Cons[A]

interface ToString {
    to_string : Self -> String
}

list_to_string_rec : List[A] -> String forall { A : ToString } =
    | Nil => ""
    | Cons(h, t) => ", " ++ h.to_string ++ t.list_to_string_rec

to_string : List[A] -> String forall { A : ToString } =
    | Nil => "[]"
    | Cons(h, t) => "[" ++ h.to_string ++ t.list_to_string_rec ++ "]"

main : () -> () =
    | () => do
        1
            .Cons(2.Cons(4.Cons(0.Cons(Nil))))
            .to_string
            .println // -> [1, 2, 4, 0]

preludeで定義されているprintln関数は型がA -> () forall { A : ToString }であるため、Stringに変換できるものなら何でも渡すことができます。（こういうライブラリのデザインはあまり深く考えて決めているわけではないので、後で名前や型を変更する可能性は高いです。）

flat_mapのシンタックスシュガー

Rustには、?演算子というのを使ってエラーハンドリングを簡潔に書くことができる機能があります。これは非常に便利なので、Cottonにも採用しました。他の演算子とは性質がかなり違うので、Cottonでは?演算子ではなく?記法と呼ぶことにしています。

次のようにして使います。

add_one_option : Option[I64] -> Option[I64] =
    | a => (a? + 1).Some

main : () -> () =
    | () => do
        1.Some.add_one_option.println // --> Some(2)

?の左側には、OptionやResultのような、エラーかもしれないことを表す型の値が来ます。そして、エラーを表す値（None）だった場合にはアーリーリターンし、正常な値（Some(hoge)）だった場合にはその中身（hoge）を返します。つまり、上のadd_one_optionのコードは次のコードと同じです。

add_one_option : Option[I64] -> Option[I64] =
    | a => a.
        | None => None
        | Some(a) => (a + 1).Some

アーリーリターンというのは、その後の計算を行わずにすぐに関数から抜けるという意味です。このとき関数はNoneなどの?の左側にあった値を返します。

アーリーリターンで抜ける範囲は次のようにdoで制限することができます。

add_one_option : Option[I64] -> Option[I64] =
    | a => do
        a = do (a? + 1).Some
        a.println // --> Some(2)
        a

main : () -> () =
    | () => do
        1.Some.add_one_option.println // --> Some(2)

JavaやJavaScriptのtry-catchのような感じでしょうか。

?記法は、実はflat_mapという関数のシンタックスシュガーです。

次のコードは

add_one_option : Option[I64] -> Option[I64] =
    | a => do
        a = do (a? + 1).Some
        a.println // --> Some(2)
        a

コンパイラによって次のようなflat_map関数を使ったコードに変換されます。

add_one_option : Option[I64] -> Option[I64] =
    | a => do
        a = a.flat_map(| b => Some(b + 1))
        a.println // --> Some(2)
        a

ここで使われるflat_mapは、そのスコープにあるflat_mapです。自分でflat_mapを定義していなければ、preludeで定義されているflat_mapが使われますが、自分で定義したりしてスコープに持ってきた場合にはそれが使われます。

例えばこんな感じのコードを書くと

flat_map : I64 -> (I64 -> ()) -> () =
    | a, f => do
        f(a)
        f(a * 2)
        f(a * 3)

main : () -> () =
    | () => (1? + 100?).println

次のコードに変換されるため、

flat_map : I64 -> (I64 -> ()) -> () =
    | a, f => do
        f(a)
        f(a * 2)
        f(a * 3)

main : () -> () =
    | () => 1.flat_map(| a => 100.flat_map(| b => (a + b).println))

出力は次のようになります。

101
201
301
102
202
302
103
203
303

複雑すぎるので出力の意味は深く考えないほうが良いです。明らかにこのような奇抜なコードは書くべきではありませんね。

モジュールシステム

一応、ファイルの中でモジュールを定義できる機能は実装しています。（例: https://github.com/nanikamado/cotton/blob/8d4aacfbf47dada3681ee9ae70f42d6c3030491d/examples/modules.cot）

別のファイルをモジュールとして扱ってインポートするような機能は未実装です。

ランゲージサーバー

ランゲージサーバーも開発中です。シンタックスハイライトと、変数の上にマウスカーソルを載せたときに変数の型を表示する機能は一応動きます（Playgroundで試せます）。ただ保存しないとシンタックスハイライトされなかったり、シンタックスハイライトが遅かったり、コンパイルエラーになるようなコードをシンタックスハイライトできないなど、いろいろ問題があります。エラーの表示、定義ジャンプ、補完などの機能も未実装です。

未実装の機能・足りていないもの

今やっている・これからやっていきたい事として、次のようなものがあります。かなりいろいろ足りていないので、まだ実用的なプログラミング言語としては使えません。

  • ドキュメントの整備
  • 標準ライブラリの整備
    まだテスト用の短いプログラムしか書いておらず、実用的なプログラムを書くにはファイル操作や乱数の取得のような組み込み関数/標準ライブラリが足りません。
  • ランゲージサーバーの改善
  • LLVMバックエンドの実装
    機能紹介の最初の方にも書きましたが、現状はJavaScriptにトランスパイルして実行しています。これをLLVMに置き換える予定です。
  • エラーメッセージの改善
    一部のエラーはわかりやすいエラーメッセージが出るようになっていますが、開発者以外意味不明なエラーメッセージが出たり、コンパイラ内のアサーションが失敗して終了することも多いです。
  • 型システムの改善
    型システムにはバグが多く、アルゴリズムの欠陥もあります。例えば、型引数を取る再帰的な型のうち、再帰する度に型引数の値が少しずつ変わっていくようなものは、部分型の判定がうまくいきません。
    再帰する度に型引数の値が少しずつ変わっていくようなものというのは、次のような型です。
    data R(A) forall { A }
type S1 = | A => A | S1[R[A]]
    次のコードをコンパイルすると、
    data R(A) forall { A }
type S1 = | A => A | S1[R[A]]
type S2 = | A => A | R[S2[A]]

main : () -> () =
    | () => do
        (() : S1[()]) : S2[()]
    次のようなエラーが出ます。
    Error: `rec[fn[d0 | d1[R[d0]]]][()]` is not subtype of `rec[fn[d0 | R[d1[d0]]]][()]`
because `rec[fn[d0 | d1[R[d0]]]][R[()]]` is not subtype of `rec[fn[d0 | R[d1[d0]]]][()]`
because `rec[fn[d0 | d1[R[d0]]]][R[R[()]]]` is not subtype of `rec[fn[d0 | R[d1[d0]]]][()]`
because could not verify `rec[fn[d0 | d1[R[d0]]]][R[R[R[()]]]]` is subtype of `rec[fn[d0 | R[d1[d0]]]][()]` because of the loop count limit.
   ╭─[test.cot:7:9]
   │
 7 │         (() : S1[()]) : S2[()]
   ·         ──────┬──────  
   ·               ╰──────── expected `rec[fn[d0 | R[d1[d0]]]][()]` but found `rec[fn[d0 | d1[R[d0]]]][()]`.
───╯
    コンパイラはS1[()]がS2[()]の部分型であることをチェックしようとします。これは成功するべきなのですが、現状のアルゴリズムだとこのチェックは無限ループに陥ってしまいます。今は応急処置として、ループの数に制限をかけるということをしています。
  • パッケージマネージャー、フォーマッターなど
  • コンパイル時計算
  • セルフホスティング
  • その他いろいろバグなど: https://github.com/nanikamado/cotton/issues

直和型 vs ユニオン型

以上でCottonの機能紹介は終わりです。ここからは、直和型と比較したユニオン型のメリットについて解説していきます。

直和型にできることはユニオン型にもできる

まず説明したいのは、直和型にできることはユニオン型にもできる、つまりユニオン型は直和型の上位互換であるということです（追記あり）。

直和型を持つ言語の例として、Rustを使って説明します。次のコードはRustのコードです。

example_1.rs
// Aか、Bか、Cのいずれかの形を取るようなデータ構造
enum S {
    A(i32),
    B(String),
    C,
}

fn to_string(s: S) -> String {
    // パターンマッチの例
    match s {
        S::A(x) => x.to_string(),
        S::B(s) => s,
        S::C => "C".to_string(),
    }
}

HaskellやOCamlなどの直和型を持つ他の言語を書いたことがある方なら、Rust書いたことなくてもなんとなく何が書いてあるかはわかると思います。この上のenumのSというのは、Aか、Bか、Cのいずれかの形を取るようなデータ構造です。下のto_string関数は、Sに対してパターンマッチを使う例として書きました。

Cottonで同じようなコードを書くと、次のようになります。

example_1.cot
data A(I64)
data B(String)
data C

type S = A | B | C

to_string : S -> String =
    | A(x) => x.to_string
    | B(x) => x
    | C => "C"

Rustのコードと同じように動きます。網羅性チェックも実装しており、例えば次のようにパターンマッチの枝を減らすと、エラーになります。

to_string : S -> String =
    | A(x) => x.to_string
    | B(x) => x

データにタグをつける、異なる型を混ぜて使えるようにする、パターンマッチングによって安全にダウンキャストする、などの直和型でできることがユニオン型でもできていることがわかってもらえるかと思います。

「ユニオン型は直和型の上位互換である」についての追記

型推論については上位互換にはならないのではないかという指摘をいただきました。

https://twitter.com/bd_gfngfn/status/1621089628693630976

確かにその通りだと思います。例えば型推論ができるコードの範囲が狭まるということはあると思います。

また、ユニオン型だと本来エラーが出てほしいところでエラーが出ず、エラーメッセージがわかりにくくなる場合があるという指摘もいただきました。

https://twitter.com/gakuzzzz/status/1621789083277357056?s=20&t=CJyFYaCJrqc-uc03pJgKcw

これもその通りだと思います。

他にも上位互換ではなさそうな点があったら指摘してもらえるとありがたいです（私の勉強になります）。

ユニオン型は型の構成要素も独立した型になっている

次に説明したいのは、ユニオン型は型の構成要素が独立した型になっていて、直和型はなっていないという違いです。

Rustで関数型言語のパーサーを書いている場面を考えます。トップレベルに現れる宣言を表す型として、次のようなものを定義しました。

１つのenumとして定義する場合.rs
enum Decl {
    // データ型の宣言
    Data {
        name: String,
        field_len: usize,
    },
    // 変数宣言
    Variable {
        name: String,
        type_annotation: Option<Type>,
        value: Value,
    },
}

後になって、Variableを引数にとって何かをする次のような関数を書きたくなりました。

fn do_something_with_variable(variable: Decl::Variable) {
    // do something
}

しかし当然、このような関数を書くことはできません。Decl::VariableはDeclのバリアントであり、型ではないからです。そのため、Variableを独立した型として定義し直す必要があります。コードを修正すると、次のようになります。

２つのstructと１つのenumとして定義する場合.rs
struct DataDecl {
    name: String,
    field_len: usize,
}

struct VariableDecl {
    name: String,
    type_annotation: Option<Type>,
    value: Value,
}

enum Decl {
    Variable(VariableDecl),
    Data(DataDecl),
}

fn do_something_with_variable(variable: VariableDecl) {
    // do something
}

これでコンパイルできるようになりました。

ここには二つの問題点があります。一つは、ほとんど同じデータ構造を、前者（１つのenumとして定義する場合）のようにも後者（２つのstructと１つのenumとして定義する場合）のようにも書くことができてしまうという点です。どちらを使って書くべきかは状況によって変化するもので、プログラマーが選択する必要があります。上で説明した場面のように、後から変更する必要が出てくるかもしれませんし、そうでなくてもどちらで書くべきか迷ってしまう可能性があります。

二つ目の問題点は、後者のように書いた場合、コードが必要以上に複雑になってしまうという点です。例えば、Dataを作成する場合、Decl::Data(DataDecl {name: "None".to_string(), field_len: 0})などと書く必要がありますが、2回もDataと書いていて冗長です。

ユニオン型を持つCottonであれば、次のように書けます。

example_2.cot
data DataDecl {
    name: String,
    field_len: I64,
}

data VariableDecl {
    name: String,
    type_annotation: Option[Type],
    value: Value,
}

type Decl = DataDecl | VariableDecl

do_something_with_variable : VariableDecl -> () =
    | _ => ()    // do something

Cottonには、Rustのenumのようなものはなく、enumのようなことをしたい場合はユニオン型に別名を付けます。シンプルで、かつ問題点をすべて解決しています。

ユニオン型はエラーを表す時に便利

もう一つ、エラーハンドリングをするときにも、ユニオン型が役立つ場面があります。

次のRustコードを見てください。

example_3_1.rs
struct Error1;
struct Error2;
struct Error3;

fn may_fail_1() -> Result<(), Error1> {
    Err(Error1)
}

fn may_fail_2() -> Result<(), Error2> {
    Err(Error2)
}

fn may_fail_3() -> Result<(), Error3> {
    Err(Error3)
}

fn do_1_2_3() -> Result<(), Error1> {
    may_fail_1()?; // `?`はエラーだったときにアーリーリターンする記法です（Rustを書いたことがない方のためのコメント）
    may_fail_2()?;
    may_fail_3()?;
    Ok(())
}

このコードは当然コンパイルできません。may_fail_2やmay_fail_3が返すエラーがError1ではないからです。解決策は2つあります。1つは、エラーをenumでまとめることです。コードは次のようになります。

example_3_2.rs
struct Error1;
struct Error2;
struct Error3;

fn may_fail_1() -> Result<(), Error1> {
    Err(Error1)
}

fn may_fail_2() -> Result<(), Error2> {
    Err(Error2)
}

fn may_fail_3() -> Result<(), Error3> {
    Err(Error3)
}

enum Errors {
    Error1(Error1),
    Error2(Error2),
    Error3(Error3),
}

impl From<Error1> for Errors {
    fn from(e: Error1) -> Errors {
        Errors::Error1(e)
    }
}

impl From<Error2> for Errors {
    fn from(e: Error2) -> Errors {
        Errors::Error2(e)
    }
}

impl From<Error3> for Errors {
    fn from(e: Error3) -> Errors {
        Errors::Error3(e)
    }
}

fn do_1_2_3() -> Result<(), Errors> {
    may_fail_1()?; // Rustの`?`には、必要がある場合にFromトレイトのメソッドを使って型を変換してくれるという機能があります（Rustを書いたことがない方のためのコメント）
    may_fail_2()?;
    may_fail_3()?;
    Ok(())
}

もう一つの解決策は、トレイトを使うことです。コードは次のようになります。

example_3_3.rs
struct Error1;
struct Error2;
struct Error3;

fn may_fail_1() -> Result<(), Error1> {
    Err(Error1)
}

fn may_fail_2() -> Result<(), Error2> {
    Err(Error2)
}

fn may_fail_3() -> Result<(), Error3> {
    Err(Error3)
}

trait Errors {}

impl Errors for Error1 {}
impl Errors for Error2 {}
impl Errors for Error3 {}

impl<'a, E: Errors + 'a> From<E> for Box<dyn Errors + 'a> {
    fn from(err: E) -> Box<dyn Errors + 'a> {
        Box::new(err)
    }
}

fn do_1_2_3() -> Result<(), Box<dyn Errors>> {
    may_fail_1()?;
    may_fail_2()?;
    may_fail_3()?;
    Ok(())
}

どちらの解決方法にもデメリットがあります。1つ目の解決方法は、エラー用のstructと同じ名前のバリアントを持つenumを定義してる部分や、エラーを変換するためにErrorsにFrom<Error1>を実装している部分などにボイラープレートが多く、冗長です。またDeclの例でもあったように、Errorsを作成する場合はコンストラクタを2つ重ねないといけないという問題点もあります。

2つ目の解決方法は、do_1_2_3のエラーの型がBox<dyn Errors>となっていますが、これはErrorsトレイトを実装したエラーが発生することを表しているだけなので、このエラーに対して網羅性チェックのあるパターンマッチをすることができないという問題があります。（Rustではそもそもトレイトオブジェクトに対して通常のパターンマッチをすることはできませんが、仮にできたとしても本質的に網羅性チェックはできません）。

ユニオン型を持つCottonであれば、次のように書くことができます。

example_3.cot
data Error1
data Error2
data Error3

may_fail_1 : () -> Result[(), Error1] = | () => Err(Error1)

may_fail_2 : () -> Result[(), Error2] = | () => Err(Error2)

may_fail_3 : () -> Result[(), Error3] = | () => Err(Error3)

do_1_2_3 : () -> Result[(), Error1 | Error2 | Error3] =
    | () => do
        ().may_fail_1?
        ().may_fail_2?
        ().may_fail_3?
        ().Ok

各エラーをまとめるためのenumを定義したり、各エラーに対してトレイトを実装するようなコードがありません。またdo_1_2_3の型には発生する可能性のあるエラーが具体的に示されていて、このエラーに対して網羅性チェック付きのパターンマッチをすることも可能です。

シンプルであり、かつ問題点をすべて解決しています。

ユニオン型は再帰的な構造にも制約を加えることができるので便利（かもしれない）

ユニオン型を使うとこんなコードが書けます。

nat.cot（実用性はない）
data O // 数字の0を表すデータ型
data S(A) forall { A } // +1を表すデータ型

type Nat = O | S[Nat] // 非効率すぎる他倍長整数
type Even = O | S[Odd]
type Odd = S[Even]

// 偶数を引数にとって2で割った結果を言語組込みの整数として返す関数
div2 : Even -> I64 =
    // 網羅性チェックつきのパターンマッチ
    | O => 0
    | S(S(n)) => 1 + n.div2

Oは数字の0を意味し、Sは+1を意味します。この２つのデータ型によって自然数を表そうとしているお遊びコードです。Natは自然数、Evenは自然数の部分集合の偶数、Oddは自然数の部分集合の奇数、div2はEvenの値を2で割って普通の整数を返す関数です。

例えば、div2のパターンマッチを次のように間違えると、

div2 : Even -> I64 =
    | O => 0
    | S(n) => 1 + n.div2

次のようにちゃんとエラーが出ます。（型の表示は内部表現をそのまま表示しているため開発者以外何を言っているのかわからなそうな感じですが、直す予定です。）

Error: `S[rec[O | S[S[d0]]]]` is not subtype of `rec[O | S[S[d0]]]`
* because `rec[O | S[S[d0]]]` is not subtype of `S[rec[O | S[S[d0]]]]`
* because `O | S[S[rec[O | S[S[d0]]]]]` is not subtype of `S[rec[O | S[S[d0]]]]`
* because `O` is not subtype of `S[rec[O | S[S[d0]]]]`
* because `:O` is not subtype of `:S`
    ╭─[examples/mutual_recursive_type_alias.cot:10:21]
    │
 10 │     | S(n) => 1 + n.div2
    ·                     ──┬─  
    ·                       ╰─── expected `S[rec[O | S[S[d0]]]] -> I64` but found `rec[O | S[S[d0]]] -> I64`.
────╯

直和型でも、OとSでNatを定義することろまでは出来ますが、EvenやOddをNatの部分型として定義することはできないと思います。

他にも、型によって回文を表現したり、赤黒木の「赤ノードの子ノードは必ず黒ノード」という性質を表現したりすることもできます。

これらの例には実用性はほとんどありませんが、きっと実用性のある使い方もあるはずです...

シールドクラスとの比較

上で説明した直和型やトレイトの問題点は、Scalaなどの言語にあるシールドクラス/シールドトレイトを使うことでも解決できます。Scalaのシールドクラス/シールドトレイトは、Rustのトレイトと似ていますが、クラス/トレイトが宣言されたファイルと同じファイル内でないとそのクラス/トレイトを実装(Scalaの言葉で言えば継承)することができないという制約を持っています。この制約によって、そのクラス/トレイトを実装(継承)している全ての型が分かるようになっており、これは通常のトレイトの「パターンマッチ時に網羅性チェックができない」という問題点を解決しています。

しかし、シールドクラスにも次のような欠点があります。

  • Scalaのクラスやトレイトは型の宣言時に継承するものであるから、組み込みの型や他のライブラリで定義された型などを部分型にすることができない。
  • 仮に既に定義された型を部分型にすることができたとしても、例えば「AまたはB」のようなものを表現する場合、ユニオン型の場合はA | Bと書けば済むが、シールドクラスの場合は「AまたはB」を表すためのAOrBのような専用のシールドクラスを宣言しなければならない。

OCamlの多相バリアントとの比較

OCamlの多相バリアントはユニオン型にかなり近く、ほとんど同じことができます。

しかし、多相バリアントにも次のような欠点があります。

  • 多相バリアントのタグは宣言することなく使うため、タイポしたときや、中に入れる値の型を間違えたときのエラーが分かりづらいかもしれない。
  • 組み込み型や、普通の直和型として定義してある型を多相バリアントに混ぜて使うときにも多相バリアントのタグをつける必要がある。
  • （これは多相バリアントの問題というよりOCamlの問題だが、）OCamlには多相バリアントも直和型もあるので、どちらを使うべきか迷ってしまうかもしれない。

最後に

あれもこれもと書いていたら長い記事になってしまいました。最後まで読んでいただきありがとうございます。

2月18日、19日の「MITOU2022 Demo Day／第29回 未踏IT人材発掘・育成事業 成果報告会」にて、この記事の内容を20分にまとめたものを喋ります。（20分... 果たしてそんなことが可能なのだろうか）YouTubeで生配信され、アーカイブも残るそうです。（喋りました。皆さんコメントありがとうございました。コメントはまだまだ大歓迎です。） この記事の中でわかりにくかったところ、疑問に思ったところ、勘違いをしていそうなところ、質問などありましたら、コメントしてください。

脚注

  1. Vのsum typeはこの記事のユニオン型には該当しないことを指摘していただきました:
    https://twitter.com/zakuro9715/status/1621067490481831936
    ↩︎

Discussion

れもんれもん

Discriminated Union(文章中では直和型とされている)は日本語ではタグ付きユニオンと言ったりもしますね。

まどまど

日本語のタグ付きユニオン/タグなしユニオンという言葉は、二通りの意味で使われることがある気がしています。一つがこの記事のユニオン型/直和型のような使い方で、もう一つがCの共用体のような、ランタイム表現にも型のタグが付いていないようなものとそうでないものを区別するために使っている使い方です。
この記事のユニオン型は、ランタイム表現には型のタグがついています。
そのため紛らわしいのでタグ付きユニオンという言葉は使いませんでした。

しかしDiscriminated Unionという英語ならランタイム表現についての意味で使われることはないかもしれませんね。ありがとうございます。

ナルミンチョナルミンチョ

パターンマッチとラムダ式が1種類構文で表現されているのは良いですね. (僕もそういう言語考えてました)

エラーの例は とても便利そうだと感じました

質問なんですが, 型パラメーターが後置なのは 何でですか?

data Tuple(Left, Right) forall { Left, Right }

を入力するときに (| はキャレット)

data Tuple(Left, R|)

の時点では, Right が入力補完機能に出力させることができず, 不便かなと思いました

data forall { Left, Right } Tuple(Left, R|)

Rustと同様に型パラメーターが前置なら入力補完機能の候補を出力できる

まどまど

ありがとうございます。型パラメーターが後置なのは、重要なことは前に書いて、重要度が低いものは後ろに書いたほうがいいのではと思ったからです。なるほど、入力補完のことは考えていませんでした。

響響

型パラメータの制約を後置するのはRustのwhere句に似てて分かりやすいですね。
ただRustでも型パラメータの名前の宣言は前置なので、その2つを分けられると補完的にも読みやすさ的にも良いんじゃないかと思います。

まどまど

例えば型パラメータの宣言を[A] =>で、制約をforallではなくwhereで書くとすると、

to_string : List[A] -> String forall { A : ToString }

は

to_string : [A] => List[A] -> String where { A : ToString }

のように書くことになりますが、Aを2回書くのは冗長で面倒な気がします。かといって

to_string : [A : ToString] => List[A] -> String

のように型パラメータの制約を型パラメータの宣言の部分にも書けるようにすると、同じことをやるのに2つのやり方がある状態になってしまいます。これはあまり好きではありません。

しかし、型パラメータの宣言と型パラメータの制約を一緒にするのは混乱の元になるという気持ちもわかります。次のようなコードを想定されているのではないかと思いす。

// このコードは現状は動きませんが、動くようにする予定です。
print_list : List[A] -> () forall { A, List[A] : ToString } =
    | a => a.println

forall の中のAは型パラメータの宣言ですが、List[A] : ToStringは型パラメーターを宣言しているわけではないのでちょっと変です。

悩ましいです。

まどまど

補完については、型パラメータは大体1文字なので補完ができなくても大した問題ではないのではと思ってきました。

IcemanIceman

ユニオン型でnominalでない型を複数利用したい場合はどう区別するのでしょうか？

まどまど

nominalでない型というのがいまいちよくわかっていないのですが、I64やStringのような組み込み型や関数の型のことでしょうか。組み込み型を含むユニオン型からこれらの型を取り出すときには、次のような「型によるパターンマッチ」が使えます。

a : String | I64 = 0

main : () -> () =
    | () => a.
        | s : String => "this is a String".println
        | i : I64 => "this is a I64".println

ただし、型によるパターンマッチの型の部分に関数の型(->)を含む型を指定することはできません（まだこれをチェックするコードは書いていないのですが、関数の型を含む型があったらエラーにする予定です）。なので関数と関数を区別することはできません。

IcemanIceman

nominalでない型とはまさしく関数型を指しているつもりでした。他には型変数やユニオン型自体も該当しそうです。他の言語ではタプル型などもあります。
ユニオン型における型よるパターンマッチに関数型が利用できない場合、関数型になり得る型変数もパターンマッチに利用できなくなり、色々と不便が起こりそうに思いました。これを解決するために型変数にnominal型を強制する型境界を定義できると良さそうに思いました。

まどまど

確かにそうですね。型変数によるパターンも未実装なので考えていませんでした。ありがとうございます。考えてみます。採用させていただくかもしれません。