はじめに
ここ1年ぐらいかけて、Fixという名前のプログラミング言語を作っています。
コアとなる機能の実装がある程度落ち着き、実際にFixを使ってプログラムを書けるようになってきたので、そろそろ言語の紹介をしてみようと思います。
本記事はFixのチュートリアルではなく、どういう思想で設計されていて、どういう特徴を持つ言語なのか、という点を紹介するものです。
意見・提案・助言などをいただけるとうれしいです。
リポジトリはこちらです。
※ コメントやコミットメッセージは一応拙い英語で書いていますが、日本語でissueを立てたりdiscordで意見・質問してもらっても大丈夫です。
※ 急いで作った部分もあるため、コンパイラのコードは結構汚いです。ご容赦ください。
現状、Fixをローカルで実行するためにはLLVMのインストールが必要で時間がかかりますが、Fix playgroundを使えばブラウザ上でFixを試すことができます。本記事中の各種ソースコードには、Fix playground上でそのコードを実行するためのリンクを付けています。
Fixの特徴
Fixは以下のような特徴を持っています。
文法面
- 関数型言語です1。副作用がない点2、部分適用ができる点、全ての関数は一つの引数をとり、カリー化された関数を多用する点はHaskellに似ています。高階カインド型とトレイト（型クラス）があり、ファンクタやモナドを定義・実装することができます。
- ただし、文法はHaskellには似ていません。文法を検討する際は、普通の言語3に慣れたプログラマーにとって覚えやすく読みやすいように配慮しました。例えば：
- 関数の呼び出しには括弧を使います（
f(x)）。 - 「
.」演算子は、右にある関数を左にある関数に適用する演算子です。これを使うことで、普通の言語の「メソッド呼び出し」スタイルでコードを書くことができます。例えば、method : Arg -> Self -> Resという関数があるとき、self.method(arg)のように呼び出すことができます。この式の評価では、まず部分適用で関数method(arg) : Self -> Resが作られ、「.」演算子によりこの関数にselfが渡されます。
- 関数の呼び出しには括弧を使います（
動作面
- 正格評価です。サンクによるメモリ消費に悩まされることはありません。
- 参照カウンタによるガベージコレクションを採用しています。また、循環参照を作ることができないため、メモリリークが発生しません。
- 関数型言語なのですが、配列の要素や構造体のフィールド値をO(1)で更新することが得意です。
- ここでの「得意」の意味は、HaskellのようにSTモナドを使う必要がなく、普通に
set : a -> Array a -> Array aという関数で配列のO(1)時間での更新ができる、という意味です。「配列」という現代のコンピュータで最も高速なデータ構造を使ったプログラムと相性が良いことは大きなメリットです。配列を使って実装されるデータ構造（ハッシュマップなど）を使うときも、自然な書き方で最適な計算量オーダーを得ることができます。 - 同様の仕組みで、構造体のフィールドの値を構造体全体をコピーせずに更新することもできます。
- この動作は、参照カウンタを使ったCopy on writeにより実現しています。ある配列（あるいは構造体）を更新しようとするとき、参照カウンタが2以上であれば複製が行われますが、1のときは複製なしに変更が行われます。参照カウンタが1だということは、更新関数（
set）の引数に渡された参照が唯一の参照だということなので、その値の変化が外部から観測されることはなく、参照等価性を維持したまま変更を行うことができるためです。
- ここでの「得意」の意味は、HaskellのようにSTモナドを使う必要がなく、普通に
Fix（のメモリ管理とCopy on write部分）は「動的なRust」だと言えるかもしれません。これについては後のセクションで説明します。
他言語との比較
他の言語と比較しつつ、前セクションに記載したFixの特徴をより詳しく説明します。
私が気に入っている言語・よく使う言語はC++, Rust, Haskellであるため、これらの言語との比較で説明します。
Haskellとの比較
見慣れたシンタックス
Haskellの問題点の一つと私が考えている点は、あまりにも「普通の」言語とシンタックスがかけ離れているところ、特に、right-to-leftなコーディングスタイルが標準的となっているところです。
例えば、与えられた数の約数の個数を数える関数countDivsをHaskellで標準的な方法で実装すると、以下のようになるでしょう。
与えられた数nに対し、nの平方根以下の約数dをリストアップしたあと、
-
dがnの平方根でないならば、約数dと約数n/dが得られるので、約数の個数に2を加え -
dがnの平方根のときは、約数の個数に1を加える
というアルゴリズムを使います。
countDivs :: Int -> Int;
countDivs n = foldl (+) 0
. map (\d -> if d*d == n then 1 else 2)
. filter (\d -> n `mod` d == 0)
. takeWhile (\d -> d*d <= n) $ [1..]
無限リストに対する変換と畳み込みを使った美しいコードではありますが、関数適用が括弧を使わないところと、右から左へ読む必要があるところが、Haskellに慣れていないプログラマーにとっては敷居が高く感じるのではないでしょうか。
もちろん、Haskellでも適切な演算子4を定義することで、left-to-rightスタイルでプログラミングすることができますが、それはおそらく標準的ではないですよね。
Fixでは、関数適用の文法として括弧を採用し、left-to-rightの関数適用演算子.を言語組み込みの演算子にしました。
約数を数える関数count_divsをFixでは以下のように実装することができます。
count_divs : I64 -> I64;
count_divs = |n| (
Iterator::count_up(1)
.take_while(|d| d*d <= n)
.filter(|d| n%d == 0)
.map(|d| if d*d == n { 1 } else { 2 })
.fold(0, Add::add)
);
メモリ確保量の予測可能性（正格評価、参照カウンタ）
Haskellは、遅延評価であること、ガベージコレクタを採用していることから、プログラムの各時点におけるメモリ確保量を予測するのはなかなか難しいです5。
個人的には、メモリ確保量の予測可能性は重要な性質だと考えているため、Fixでは正格評価型とし、不要になったヒープ上のデータはすぐに解放されることが保証される参照カウンタによるガベージコレクションを採用しました。
配列の使いやすさ
Fixで参照カウンタを採用したもう一つの理由が、構造体や配列要素のO(1)時間更新が可能になることです（参照カウンタによるCopy on write）。
Haskellの標準的な配列のインターフェースを定めるパッケージData.Array.IArrayには、配列の要素を更新する演算子(//)の計算量について以下のように書かれています。
(//) :: (IArray a e, Ix i) => a i e -> [(i, e)] -> a i e
...
For most array types, this operation is O(n) where n is the size of the array.
引用元：https://hackage.haskell.org/package/array-0.5.6.0/docs/Data-Array-IArray.html
Haskellは純粋関数型言語であるため、同じ配列を指し示す2つの参照ref1とref2があったとして、ref1経由で配列の値を更新したら、ref2経由でアクセスする配列の値が変わってしまった、という動作を許すわけにはいきません6。
そのため、Haskellで配列を更新するときは、O(n)時間かけて配列を複製してから、複製された配列の値を更新します。
Fixでは、ヒープメモリ上の値には必ず参照カウンタがついているため、配列の要素を更新する関数（set）が呼ばれたとき、その配列を指し示す参照の個数を知ることができます。
このとき、もし2つ以上の参照が存在する場合は、Haskellと同様にO(n)時間かけて配列の複製を行います。一方、もし1つの参照しか存在しなかった場合は、配列を更新しても問題が生じない（副作用がない）ため、O(1)で配列要素を更新します。
例えば、次のFixプログラムはフィボナッチ数列を格納した配列を計算しますが、この過程で一度も配列の複製は発生しません。
calc_fib : I64 -> Array I64;
calc_fib = |n| (
let arr = Array::fill(n, 0);
let arr = arr.set(0, 0);
let arr = arr.set(1, 1);
loop((2, arr), |(idx, arr)|
if idx == arr.get_size {
break $ arr
} else {
let arr = arr.set(idx, arr.@(idx-1) + arr.@(idx-2));
continue $ (idx+1, arr)
}
)
);
上記のコードに3回登場するset関数の型はI64 -> a -> Array a -> Array aで、更新したい配列要素のインデックスi、新しい要素の値e、更新対象の配列arrを受け取ります（I64は64bit整数の型です）。
式arr.set(i, e)では、まずsetにiとeを渡してset(i, e) : Array a -> Array aという関数（クロージャ）が作られ7、演算子.によりこの関数にarrが渡されます。
Array::fill(l, e)は長さlで全ての要素がeであるような配列を生成する関数です（Arrayはfillの属する名前空間で、省略可能ですが、配列が生成されるということが分かりやすくなるため、明示的に書いています）。
なお、Fixでは、スコープに既にある名前xが存在する場合でも、letによりxという名前の値を新しく作ることができます。letの右辺の式にxが含まれている場合、それは古いスコープにおけるxの値となります（よって、letで再帰的定義を行うことはできません8）。よって、上記のコードは次のコードと等価になります。
calc_fib : I64 -> Array I64;
calc_fib = |n| (
let arr1 = Array::fill(n, 0);
let arr2 = arr1.set(0, 0);
let arr3 = arr2.set(1, 1);
loop((2, arr3), |(idx, arr4)|
if idx == arr4.get_size {
break $ arr4
} else {
let arr5 = arr4.set(idx, arr4.@(idx-1) + arr4.@(idx-2));
continue $ (idx+1, arr5)
}
)
);
このように書くと、最初のsetの呼び出し時点（arr1.set(0, 0)）で、その配列を指し示している参照はarr1の一つだけであることが分かりやすいと思います。
また、ここがarr1の最後の使用箇所であるため、arr1.set(0, 0)を評価した時点でarr1という参照はなくなったものとして扱われます。よって、arr2.set(1, 1)の時点でも、その配列に対する参照はarr2の一つだけであり、やはり複製が行われることはありません。
なお、補足として、Haskellでも配列のO(1)更新ができないわけではありません。よく知られた、STモナドとMArrayを使う方法の他に、DiffArrayを使う方法やLinear typesを使う方法があるようです。
特に、DiffArrayを使う方法は（パッケージData.Array.Diffの冒頭を読んだだけの知識ですが）FixのArrayに使い勝手が似ているかもしれません。
構造体の使いやすさ
Haskellにはレコード構文があり、C++での構造体と同様に、直積型の各成分に「フィールド名」を付けて扱うことができます。
data Foo = Foo { bar :: String, baz :: Int }
言語拡張やライブラリを使わない「生の」Haskellにおいては、レコード構文にはいくつかの不便な点があります。
フィールドアクセサの自動定義
一つ目は、フィールド値の更新をスマートに記述することができない点です。
レコードを定義することで、bar :: Foo -> Stringやbaz :: Foo -> Intといったgetter関数は自動で定義されます。一方で「setter関数」のようなものは定義されず、フィールド値の更新は関数ではなく「構文」で行うことになります。
例えば、Foo型の値fooがあったとき、フィールドbarの値を"Bar!"に設定してできるFoo型の値は、
foo { bar = "Bar!" }`
のように表します。また、さらにFoo型のフィールドを持つレコードQux
data Qux = Qux { foo :: Foo }
とQux型の値quxがあったとき、quxの中のfooの中のbarの値を"Bar!"に設定するには、
qux { foo = (foo qux) { bar = "Bar!" } }
と書くことになります。
これはとても書きやすいとは言えないため、Lensと呼ばれるライブラリを使うのが一般的となっています。このライブラリは、レコードのフィールドに対し、"lens"と呼ばれる関数（setter関数を一般化したもの）を自動定義するテンプレートを提供しています。例えば、
data Foo = Foo { _bar :: String, _baz :: Int }
makeLenses ''Foo
data Qux = Qux { _foo :: Foo }
makeLenses ''Qux
と定義しておけば、
qux & foo . bar .~ "Bar!"
と書くことができます。良い感じですね。
Fixでは、構造体を定義すると、getterとsetter、そしてmodifierと呼ばれている関数が自動で定義されます。例えば、
type Foo = struct { bar : String, baz : I64 };
このように定義すると、
- フィールド値を取り出す関数
@bar : Foo -> String,@baz : Foo -> I64 - フィールド値を特定の値に設定する関数（を作り出す関数）
set_bar : String -> Foo -> Foo、set_baz : I64 -> Foo -> Foo - フィールドに特定の関数を作用させて構造体の値を変換する関数（を作り出す関数）
mod_bar : (String -> String) -> Foo -> Foo、mod_baz : (I64 -> I64) -> Foo -> Foo
など9が定義されます。
setter関数を使うと、Foo型の値fooがあったとき、フィールドbarの値を"Bar!"に設定した値は、
foo.set_bar("Bar!")
と書くことができます。また、さらに
type Qux = struct { foo : Foo };
と定義したとしましょう。Qux型の値quxがあったとき、quxの中のfooの中のbarの値を"Bar!"に設定するには、
qux.mod_foo(set_bar("Bar!"))
と書くことができます。各部分式の型は、set_bar("Bar!") : Foo -> Foo、mod_foo(set_bar("Bar!")) : Qux -> Quxです。よりlensっぽく書きたいなら、
qux.(mod_foo $ set_bar $ "Bar!")
あるいは
qux.(mod_foo << set_bar $ "Bar!")
と書いてもよいかもしれません（<<は、right-to-left関数合成演算子(g << f)(x) == g(f(x))）。
さらに、setterやmodifierにおいても、参照カウンタによるCopy on writeが機能します。すなわち、setter/modifier関数に参照カウンタが1である値を渡すようにすれば、構造体の全体を複製することなく値の更新をすることが可能です。
構造体に対するgetter, setter, modifierの動作を確認するためのFixのサンプルコードを載せておきます。
module Main;
type Foo = struct { bar : String, baz : I64 };
type Qux = struct { foo : Foo };
main : IO ();
main = (
let qux = Qux { foo : Foo { bar : "truth", baz : 42 } };
let qux2 = qux.mod_foo(set_bar("Bar!"));
let qux3 = qux.(mod_foo $ set_bar $ "Bar!");
let qux4 = qux.(mod_foo << set_bar $ "Bar!");
let _ = *(println $ qux2.@foo.@bar);
let _ = *(println $ qux3.@foo.@bar);
let _ = *(println $ qux4.@foo.@bar);
pure()
);
なお、本記事執筆時点では、構造体のフィールドに対するlens関数は自動定義されませんが、将来的には追加予定です。lens関数はact_bar : [f : Functor] (String -> f String) -> Foo -> f Fooという名称（および型）となる見込みです。
また、配列の要素に対するlens関数（を作る関数）act : [f : Functor] I64 -> (a -> f a) -> Array a -> f (Array a)は既に実装されています。
オーバーロード
もう一つのHaskellのレコードの不便な点は、フィールド名の衝突です。例えば、以下のようにレコードを2つ作成したとしましょう。
data Doggo = Doggo { name :: String }
data Catto = Catto { name :: String }
nameという同じ名前のフィールドを持つ、異なるレコードDoggoとCattoを作りました。一見すると何も問題ないように見えるかもしれませんが、これはコンパイルエラーになります。
Main.hs:2:22: error:
Multiple declarations of ‘name’
Declared at: Main.hs:1:22
Main.hs:2:22
これは、2つのgetter function、name :: Doggo -> Stringとname :: Catto -> Stringの名前が衝突しているために起きます。
Fixでは、構造体Doggoの各フィールドのgetter, setter, modifierはDoggoという名前空間の中に定義されます10。
また、Fixコンパイラには、各識別子の名前空間を型情報から推論する機能を持っています（推論できなかったときはコンパイルエラーとなります）。
これにより、複数の構造体で同じフィールド名を使用しても、Haskellのレコードのような問題は発生しません。
module Main;
type Doggo = struct { name : String };
type Catto = struct { name : String };
main : IO ();
main = (
let doggo = Doggo { name : "ポチ" };
let catto = Catto { name : "タマ" };
println $ "ウチの犬の名前は" + doggo.@name + "で、猫の名前は" + catto.@name + "です。"
);
上記のコードにおいて、@name関数には、
Doggo::@name : Doggo -> StringCatto::@name : Catto -> String
の2つが存在します。
doggo.@nameやcatto.@nameという式をコンパイルする際、@name関数に与えられる値doggoやcattoの型は既に分かっているため、どちらの@nameを指し示しているのか推論することができ、コンパイルに成功します。
Fixにおける名前空間の推論は「対象となる識別子よりもソースコード上で「前」に書かれている部分から推論する」というふうに実装しています。なので、例えば、
println $ "ウチの犬の名前は" + @name(doggo) + "で、猫の名前は" + @name(catto) + "です。"
と書くと、@nameの名前空間の推論に失敗し、以下のようなエラーとなります。
error: Name `@name` is ambiguous: there are `Main::Catto::@name`, `Main::Doggo::@name`.
Maybe you need to add type annotation to help overloading resolution.
これを修正するには（型アノテーションを加えるといいかも、というコンパイラの提案は間違っていて）@nameに名前空間を明記する必要があります。
println $ "ウチの犬の名前は" + Doggo::@name(doggo)
+ "で、猫の名前は" + Catto::@name(catto) + "です。"
モナドのサポート
Haskellと同様に、Fixもモナドを扱うための専用の構文を持っています。Optionモナドを使う例を挙げます。
module Main;
divide : F64 -> F64 -> Option F64;
divide = |a, b| if b == 0.0 { Option::none() } else { Option::some(a / b) };
a_over_b_plus_c_over_d : F64 -> F64 -> F64 -> F64 -> Option F64;
a_over_b_plus_c_over_d = |a, b, c, d| (
pure $ *divide(a, b) + *divide(c, d)
);
main : IO ();
main = (
println $ a_over_b_plus_c_over_d(1.0, 2.0, 3.0, 4.0).as_some.to_string
);
関数a_over_b_plus_c_over_dの中で使われている前置演算子*がモナド専用の構文です。
pure $ *divide(a, b) + *divide(c, d)
という部分は、Haskellでの
do
x <- divide a b
y <- divide c d
return $ x + y
と同じになります。
より具体的には、Monadトレイトのメンバbind : (a -> m b) -> m a -> m bを使った
divide(a, b).bind(|x| divide(c, d).bind(|y| pure $ x + y))
というFixのコードに展開され、コンパイルされます。
本来はdivide(a, b) + divide(c, d)と書きたいようなものなので、それに近いコードpure $ *divide(a, b) + *divide(c, d)で書けるところが気に入っています。
一方、Haskellのdo構文に対して、欠点と言える点もあります。
前置演算子*を展開するとき、x <- divide a bやy <- divide c dなどに相当する「モナド的束縛」の処理がどの位置に自動挿入されるか？は重要で、これが変わるとプログラムの動作が変わってしまいます。
しかし、この自動挿入位置の選択について「自然な選択肢」と言えるようなものはなく、モナドの典型的なユースケースにとって便利なものを選ぶ、という決め方になっています。
詳細については、ドキュメントの"do block and monadic bind operator *"を参照してください。
C++・Rustとの比較
抽象度の高さ
FixとRustはどちらも以下の保証をもち、これらの保証が安全なプログラミングを助けてくれます。
- 不正なメモリアクセスが発生しないこと11
- あるデータへの参照が唯一であるときのみ、そのデータを変更することができること
また、現状のFixにはマルチスレッド機能が実装されていませんが、いずれ実装された際は、Rustと同様に以下の保証を持つようになる予定です。
- データ競合が発生しないこと
これらの保証を実現するためのRustのアプローチは、コンパイル時に静的検査を行うというものです。
- Rustにおける「型
Tの値への参照の型」は（単一の型ではなく、）ライフタイム（'a）と呼ばれるものにパラメータ付けされた型&'a Tであり、参照型にその参照の有効期間がエンコードされています。このパラメータ付けされた参照型に対するコンパイル時の型チェックにより、解放済みとなったデータに対する参照を使用するようなコードをコンパイル時にエラーとすることができます。 - Rustの参照には不変参照（
&'a T）と可変参照（&'a mut T）があります。ある値に対し、一つの可変参照あるいは複数の不変参照を取得することだけが可能です。言い換えれば、同時に複数の可変参照を取得したり、可変参照と不変参照を同時に取得することはできません（コンパイル時にエラーとなります）。これにより、プログラム中である値を変更するとき、その値は他の場所からは参照されていないことが保証され、値の変更による意図しない副作用を防止したり、データ競合を防ぐことができます。
一方、Fixでは、参照の寿命管理や可変性の制約管理をプログラムの実行時に行います。
- Fixは、ヒープメモリ上の各データに参照カウンタと呼ばれる変数を割り当て、そのデータへの参照の個数を数えています。参照カウンタが0になったときにそのデータに割り当てられたメモリを解放するため、不正なメモリアクセスが発生することはありません。
- Fixでは、ヒープメモリ上のあるデータの参照カウンタが1のときに限り、そのデータを書き換えることができます12。参照カウンタが2以上のときにデータを書き換えようとしたときの動作は、その場でデータを複製するか、プログラムを停止させるかのどちらかです。どちらの動作になるかはデータを書き換えようとする関数により異なります。後者の振る舞いをする関数には名前の末尾に「!」がついています。
実行時にメモリ管理・可変性管理を行うようにし、プログラムの実行時の時間的・空間的オーバーヘッドというデメリットを支払う代わりに、FixプログラムはRustプログラムよりも高い抽象度を持つことができます。
Rustでは、ある型Tの値をプログラムの色々なところに受け渡したり保持する方法にはT, &T, &mut Tの3通りがあり（Box<T>, Rc<T>やRefCell<T>もこれに加えるべきかもしれません）、それぞれの特性をよく理解しておくことが重要です。
一方、Fixにおいては「T」の一つだけです。また、Fixの値は常に不変であるかのように振る舞い、必要に応じて自動で値の複製が行われます。
やや恣意的な例かもしれませんが、Rustにおいては参照や可変性を意識する必要があるということを示す例を挙げてみます。
Optionが挟まってしまった2次元配列を平坦化する関数flattenは、Fixでは以下のように実装できます。効率のため、まず要素の個数をすべて数えてから、その要素数を格納できるだけのキャパシティをもつArrayを作って、そこに配列たちをappendしていくように実装します。
flatten : Array (Option (Array a)) -> Array a;
flatten = |vov| (
let len = vov.to_iter.fold(0, |sum, ov| sum + ov.map_or(0, Array::get_size));
let res = Array::empty(len);
vov.to_iter.fold(res, |res, ov| ov.map_or(res, |v| res.append!(v)))
);
ここで、opt.map_or(def, f)は、Option値optが無効値のときはdefを返し、有効値のときは格納していた値に関数fを適用したものを返します（map_or : b -> (a -> b) -> Option a -> b）。
Array::empty : I64 -> Array aは、指定されたキャパシティを持つ空の配列を作成する関数です。
また、a1.append!(a2)は、a1にa2を結合したものを表す式で、「!」はa1の参照カウンタが2以上であることが原因で配列の複製が必要になってしまった場合はプログラムを停止させることを意味しています。
このappend!を使ったflatten関数が実行できるということは、期待通り、要素数lenを格納できるメモリを確保したあとは、複製なしに、結果となる配列への要素の追加が行われていることを示しています。
Rustではどうなるでしょうか。もちろん色々な実装方法がありますが、上記のFixのコードに近い方法で実装すると、以下のようになると思います。
fn flatten<T>(mut vov: Vec<Option<Vec<T>>>) -> Vec<T> {
let len = vov
.iter()
.fold(0, |sum, ov| sum + ov.as_ref().map_or(0, |v| v.len()));
let res = Vec::with_capacity(len);
vov.iter_mut().fold(res, |mut res, ov| {
match ov {
Some(v) => {
res.append(v);
}
None => {}
}
res
})
}
lenを求める式はFixとよく似ていますが、ov.map_or(...)と書いてしまうと、まだ後で使用するvovの要素をムーブアウトしてしまうため、as_ref()によって&Option<T>をOption<&T>に変換する必要があります。
また、Vec::appendは2つの可変参照をとるインターフェースであるため、引数vovやresにmutがついていたり、後半パートでイテレータを取得する際はiter_mut()とするなど、appendの呼び出し位置まで可変参照を届けるための記述が必要となります。
なお、後半パートのfoldの中では、map_orを使ってコンパイルを通す方法を見つけられませんでした。例えば、仮に、
fn flatten<T>(vov: Vec<Option<Vec<T>>>) -> Vec<T> {
let len = vov
.iter()
.fold(0, |sum, ov| sum + ov.as_ref().map_or(0, |v| v.len()));
let res = Vec::with_capacity(len);
vov.into_iter().fold(res, |mut res, ov| {
ov.map_or(res, |mut v| {
res.append(&mut v);
res
})
})
}
と書くと、以下のようなエラーとなります。
error[E0382]: use of moved value: `res`
--> src/main.rs:4:60
|
4 | vov.into_iter().fold(res, |mut res, ov| ov.map_or(res, |mut v| { res.append(&mut v); res }))
| ------- --- ^^^^^^^ --- use occurs due to use in closure
| | | |
| | | value used here after move
| | value moved here
| move occurs because `res` has type `Vec<T>`, which does not implement the `Copy` trait
For more information about this error, try `rustc --explain E0382`.
map_orは実行パスを2つに分ける関数ですが、実行される片方のパスのみにresの所有権を渡す、ということはどう頑張ってもできなさそうな気がしています。
一方、Fixのov.map_or(res, |v| res.append!(v)の場合は、map_orが呼び出された時点でresの参照カウンタは2になる（単一所有性を失っている）ものの、ovが有効値だと判明してres.append!(v)が実行される時点では、resの参照カウンタは1に戻っている、という動作が実現できています。
このように、Rustのプログラムを書くときは「値というものはメモリ上に置かれているデータで、そのアドレスが参照で、そのデータを書き換えたり複製したりすることで処理を行っている」ということを意識しておく必要があります。さらに、その計算の過程でプログラムが不正な動作を行わないようにするためのRustのルール（Rustのライフタイム管理や借用規則）について理解しておく必要があります。
Rustは個人的に非常に気に入っている言語の一つではあるのですが13、理想的には「値というのは型が表す集合の要素のことであって、値に関数を適用して新しい値を作り出すことで計算を行っている」というより抽象的なイメージでプログラムを書くことができる言語が望ましいと考えています。
Fixの開発のきっかけとなった気付きは、参照カウンタを使った「動的なRust」のようなものを作ってやれば、「メモリ安全性」「スレッド安全性14」「唯一参照を介した値の可変性」などの性質を維持したまま、Rustを大幅に単純化することができる、ということでした。もちろん、これは、プログラミング言語の実装・設計について深く考えている人にとっては周知の事実であったことでしょう。
これを関数型言語（式ベース言語）にして高階カインド型を加えたのがFixです。これで、本記事のタイトルにある「HaskellとRustを足して2で割った」という言葉に納得していただけるでしょうか。
メモリリークの回避
参照カウンタによるメモリ管理は、循環参照が発生すると破綻します。例えば、C++のshared_ptrでは、以下のように循環参照を作ることができてしまいます。
#include <iostream>
#include <memory>
using namespace std;
struct Leaker {
~Leaker() { cout << "~Leaker" << endl; }
shared_ptr<Leaker> ptr;
};
int main() {
shared_ptr<Leaker> leaker = make_shared<Leaker>();
leaker->ptr = leaker;
}
上記のコードを実行しても「"~Leaker"」と表示されないため、Leakerのデストラクタが呼ばれておらず、メモリリークが発生していることが確認できます。
Rustで循環参照を作るのはもう少し難しいですが、似たような方法で可能です15。
use std::cell::RefCell;
use std::rc::Rc;
struct Leaker {
ptr: Option<Rc<RefCell<Leaker>>>,
}
impl Drop for Leaker {
fn drop(&mut self) {
if self.ptr.is_some() {
println!("Leaker (ptr = some) dropped!")
} else {
println!("Leaker (ptr = none) dropped!")
}
}
}
fn main() {
let leaker = Rc::new(RefCell::new(Leaker { ptr: None }));
*leaker.as_ref().borrow_mut() = Leaker { ptr: Some(leaker.clone()) };
}
これを実行すると「"Leaker (ptr = none) dropped!"」とだけ表示されるので、main()の2行目で作られたLeakerがDropされていないことが分かります。ということは、その内側にあるRcの参照カウンタは0になっていないことでしょう。
Rustの保証に「メモリリークの回避」が入っていないことは、The Rust Programming Language の Reference Cycles Can Leak Memory にはっきりと書かれています。
Preventing memory leaks entirely is not one of Rust’s guarantees, meaning memory leaks are memory safe in Rust.
引用元：https://doc.rust-lang.org/book/ch15-06-reference-cycles.html
一方で、Fixはメモリリークが発生しないことを保証しようとしています16。そして、今のところ、保証できているようです。
C++での例でもRustの例でも、循環参照を作るキーとなる操作は、一度作成した値を書き換えるところです。Fixでは基本的に値は不変なのでこのような操作はできません。また、Fixのlet式では再帰的定義ができません。
そのため、あるFixの値に埋め込まれている「他の値への参照（ポインタ）」は、その値が作成されるより前の時刻にアロケートされたメモリ領域へのポインタとなっています。よって、ヒープメモリ上のオブジェクトとその参照関係がなすグラフはDirected Acyclic Graphとなり、ループを持つことはありません。
実際には、上の議論にはまだ穴があり、Fixでも参照カウンタが1の値を変更することはできることを考慮に入れる必要があります。
例えば、以下のようなコードを考えましょう（structの前のboxという指定子は、Leakerをいわゆる「値型」ではなく「参照型」とすることを指定しています）。
module Main;
type Leaker = box struct { ptr : Option Leaker };
main : IO ();
main = (
let leaker = Leaker { ptr : Option::none() };
let leaker = leaker.set_ptr!(Option::some(leaker)); // panics
pure()
);
構造体Sのフィールドx : Tに対し、setter関数set_x : T -> S -> Sは、渡されたS型の値の参照カウンタが2以上の場合はS型の値を複製してから値の書き換えを行います。
別種のsetter関数set_x! : T -> S -> Sは、渡されたS型の値の参照カウンタが2のときはpanicする（プログラムを停止させる）ものです。
ここでは、leakerの値を書き換えて循環参照を作ることを目的としているため、set_ptrではなくset_ptr!を使用しています。
実際に上記のコードを実行すると、set_ptr!に渡されたleakerの参照カウンタが1ではないため、プログラムはpanicします。
もしset_ptr!ではなくset_ptrを使った場合は、プログラムはpanicしませんが、mainの1行目と2行目のleakerは異なるLeakerインスタンスとなり、2行目のleakerが1行目のleakerを参照するだけであるため、循環参照は発生しません。
この例を一般化して考えると、setter関数でも循環参照が発生しない理由は、次のように説明できます。
Fixにおいてある値を変更する式self.set_x(arg)を実行したとしましょう。もし、argから参照をたどってselfに到達することができるなら、この時点でのselfの参照カウンタは1ではありません。そのため、set_xはまずselfの指し示す値を複製してから、そこにxをセットします。selfの値自体を変更するわけではないので、循環参照は発生しません。
なお、Fixは正格評価言語であるため、letで値の再帰的定義をしたいことはないと思いますが、関数の再帰的定義をしたいことはあるかもしれません。その場合は、fix : ((a -> b) -> (a -> b)) -> a -> bという組み込み関数を使って、ローカルな再帰的関数を作ることができます。
module Main;
main : IO ();
main = (
let f = fix $ |f, a, n| (
if n == 0 {
a
} else {
f(a + n, n - 1)
}
);
println $ f(0, 100000).to_string // 1 + 2 + ... + 100000
);
fixで作った再帰的関数にも末尾再帰最適化が効くようです。ただし、通常のグローバルな再帰的関数に比べてパフォーマンスは落ちるものと思われます。
その他の機能
ここまでの説明で登場していない言語機能のいくつかについて、簡単に紹介しておきます。
union
タグ付き共用体を定義することができます。
Optionはここまでのプログラムの例で既に登場しましたが、これは以下のように定義されています。
type Option a = union { none: (), some: a };
box型とunbox型
unbox型はいわゆる「値型」で、box型はいわゆる「参照型」です。
unboxのローカル変数を作ると、スタックメモリ（あるいはレジスタ）上にその値が置かれます。構造体のあるフィールドの型がunbox型のときは、フィールドの値はその構造体のメモリ領域に埋め込まれます。
一方、box型の値は必ずヒープメモリ上に置かれ、参照カウンタにより管理されます。box型の値のローカル変数があるとき、そのスタックメモリ（あるいはレジスタ）上での表現はポインタであり、構造体のあるフィールドの型がbox型のときは、構造体のメモリ領域にはポインタが埋め込まれます。
組み込み型では、BoolやI64などの基本的な型はunbox型で、Arrayはbox型です。また、ペア・タプルはunbox型となっています。
クロージャはunbox型ですが、何らかの値をキャプチャしているときは、キャプチャされている値たちをメンバに持つ無名のbox型の値が作られ、クロージャはその値を参照します。すなわち、クロージャのデータは「関数ポインタ」と「ヒープメモリ上のキャプチャリストへのポインタ」です。何もキャプチャしていないクロージャは、後者のフィールドの値はNULLとなり、ヒープメモリ確保なしに作ることができます。
ユーザ定義の構造体はデフォルトではbox型ですが、structの前にunboxと書くことで、unbox型の構造体を作ることができます。
ユーザ定義の共用体はデフォルトではunbox型で、unionの前にboxと書くことで、box型の共用体を作ることができます。
あまり低レベルな概念をプログラマに意識させたくないのですが、これぐらいの制御はできないと性能が出せないだろうな、と考えて、このような文法を追加しました。
FFI
CALL_Cという構文で、リンクされているC言語の関数を呼ぶことができます。たとえば、Debug::debug_printの実装は以下のようになっています。
debug_print : String -> ();
debug_print = |s| (
s.borrow_c_str(|ptr| (
let _ = CALL_C[I32 printf(Ptr, ...), ptr];
let _ = CALL_C[I32 fflush(Ptr), nullptr];
()
))
);
また、Fixのコンパイラには共有ライブラリ・静的リンクライブラリを指定するオプションがあります（--dynamic-link, --static-link）。
今後について
プログラミング言語を作るのはFixが初めての経験で、ここまでの作業で非常に多くの学びがありました（Parsing Expression Grammer, LLVM, Hindley-Milner型システム, etc）。
これからも、色々な学びが得られることを期待して、開発を進めていこうと思います。例えば、手頃そうなところであれば、
- match式やif let式の追加
- デバッグシンボルの出力、エラーメッセージの改善
などで、もう少し規模が大きそう or 研究が必要そうなところでは
- 高速化・最適化
- スレッド機能の追加
- Language Server Protocolの実装
などができたらよいなと思っています。
-
「関数型言語」の定義はよくわかりません。文ベースではなく式ベースの言語であるとか、クロージャを簡単に作れる、とかでしょうか。 ↩
-
もちろん、「unsafe」から始まる関数を呼び出したり、C言語の関数を呼んだ場合を除きます。 ↩
-
「普通の言語」の定義もよくわかりませんが、まぁ、C++やJavaやPythonのことです。 ↩
-
(&) = flip ($)↩ -
と考えているのは私のHaskellレベルが低いだけでしょうか？ ↩
-
もちろんこれはC++, Java, Pythonなどの言語では当たり前に起きる動作なのですが、この動作が初心者のハマりどころ・バグの元になることはよく知られていることで、このような動作を禁止することでより良い言語を作るのが関数型言語の発想だと言えます。 ↩
-
実際にはuncurry optimizationによりクロージャは生成されない場合があります。 ↩
-
これによりヒープメモリ上に置かれたデータが循環参照を作ることがなくなり、参照カウンタによるガベージコレクションの弱点を塞ぐことができます。 ↩
-
あとは後述する
set_bar!,set_baz!も定義されます。 ↩ -
より厳密には、構造体
Doggoが定義されている名前空間の中に、Doggoという名前空間を定義し、そこにgetter, setter, modifierが定義されます。 ↩ -
もちろん、unsafeな関数を使った場合や、他言語の関数を呼び出した場合にこのような保証はありません。 ↩
-
なお、スタックメモリ上のデータを書き換えるときは常に複製を行うようなLLVM-IRを出力しています。実際に複製が行われるかどうかはLLVMの最適化によります。 ↩
-
FixのコンパイラはRustで書いています。Fixをここまで開発してこれたのは、間違いなく、Rustやそのエコシステムによる高い生産性のためであり、例えばC++で書き始めていたらもっと時間がかかっていたのではないかと思います。 ↩
-
繰り返しになりますが、Fixのスレッド機能は未実装です。 ↩
-
メモリリークを起こしたいだけなら
Box::leakを使えば簡単です。 ↩ -
「unsafe」がついた関数や、FFIでC言語関数を呼び出さない限りの保証です。 ↩