Efficient Parallel Functional Programming with Effects を読んだ

SML MaPLe

いわゆる Parallel ML の一つである MPL の論文最新作です > Efficient Parallel Functional Programming with Effects: Jatin Arora Sam Westrick Umut A. Acar. PLDI 2023.
重要な拡張に思えたので全体を読みましたのでメモしておきます。

MPL

MPL はいわゆる Parallel ML の実装の一つで、(dis)entanglement という性質に基づいたメモリマネージャを搭載することで、コア数に沿って関数型並列プログラムの実行速度がスケールする(ことを目指している)SML処理系です。
並列化の方針としてはExplicitかつNested Parallelismです。
実装としては MLton をフォークしていますので、シーケンシャルプログラムの実行速度はひとまず十分であろうところから開発が始まっています。

達成したこと

これまでMPLが並列実行できるのは、この研究グループ(？)が以前提案した disentanglement という性質を満たしたプログラムだけでした*1。
今回の論文では (dis)entanglement という概念を(プログラム全体から)オブジェクトレベルの適用に詳細化することで、 mutable な参照がタスクを跨ぐような(≒ entanglementな)任意のプログラムが並列実行できるようにする手法を提案しています。
提案手法はこのブランチで実装されています*2 > MPL/pldi23-artifact。

当然この手法を適用しても並列プログラムがコア数に対してスケールし、さらにentanglementの管理に必要なメモリ領域が十分小さいという主張がされています。

パフォーマンス

実際のパフォーマンスはどうかということで、論文中ではベンチマークとして72コアマシン上での各種並列アルゴリズムの実行速度(のスケール)とメモリ使用量を示しています。
また比較先として、C++, Go, Java, OCamlによる同じアルゴリズムの実装を使用しています。

おおよそ言語間の比較の結論を述べると、C++, MPL, Go, Java, OCaml の実行時間の平均の比はこの順で 0.63, 1.00, 2.07, 2.00, 6.30 です。
C++ の1/2倍、Go, Java の2倍、OCaml の3倍の速度ですね。
シングルスレッドでのMLtonの速度は論文中で比較されてませんが、甘めに言ってもC++の1/3倍速くらいだと思いますので、うまくスケール出来ていると思います。


また同様の条件での最大メモリ使用量の比は同じ順で 1.22, 1.00, 1.36, 4.20, 2.47 です。
なんとC++よりも2割少なくなっておりかなりすごいですね。論文中にはなぜC++より少なくなるのかの考察は無いようですが、タスクをjoinするときに即メモリを回収出来るのが効いているんじゃないでしょうか。
少なくともentangled objectを追跡するためのデータによるオーバーヘッドは(主張通り)考えなくとも良さそうです。

前提

提案手法について述べる前に必要な概念を導入します。

parallel task tree

MPLは素のSMLに比べて val par: (unit->'a * unit->'b) -> 'a * 'b というプリミティブが追加されただけの言語です。
親タスクがこのparを呼ぶと、それに渡した二つの関数をそれぞれspawnした子タスクに渡して実行し、両方の子タスクが停止したとき、結果をタプルとして取得し、自身の実行を再開します。
親タスクは必ず子タスクが停止するまでブロックします。

ですのでMPLプログラムでは、実行時のタスク関係全体が常に木(computation tree)を成し、必ず親より子タスクが先に停止します。
このときブロック(suspend)している親タスクを internal task、実行している(active)子タスクを leaf task と呼びます。

entanglement / disentanglement

entanglement/disentanglement というのは ICFP2016 で提案された概念で、並列プログラムのタスク(ツリー)上で定義された性質です。
簡単に述べると、それぞれのタスクで管理しているヒープ領域を指すポインタを(並列に実行される)別のタスクが持っている場合、entanglement であるといいます。
また entanglement でないことを disentanglement といいます。
disentanglement が成り立っている並列タスクは、それぞれに独立したヒープマネージャとGCを持たせることで、アロケーションやGCがブロックすることなく(= ボトルネックになることなく)CPUコア数に応じてスケールすることができます。

提案手法

論文の内容自体がかなり実装寄りなのでアイデアだけ簡単にまとめたいと思います。

entangled object の追跡

まず、entanglement 関係を(プログラム全体ではなく)オブジェクトレベルで実行時追跡するようにしたいというのが主要なアイデアです。
MPLはタスクごとにアロケータとGCをもって並列に動作しているため、このオブジェクトの追跡も互いのタスクをブロックしないように実行する必要があり、ロックを使用せずcasを使用するアルゴリズムが提案されています。

おおよそ各ポインタのデリファレンス時(≒ ! : 'a ref -> 'a or sub : 'a array * int -> 'aを呼び出したとき)に以下のような処理を行います。

  • オブジェクトのアロケートしたタスクと、デリファレンスしたタスクが異なる場合 entangled object と判定する
    • disentangled なオブジェクトはコピー&コンパクション (relocating) の対象とする
      • relocation 対象オブジェクトは移動(コピー)先を示すポインタ(forward pointer)に差し替え、これ以降にアクセスされた場合に追跡できるようにする
    • entangled なオブジェクトは pin フラグをセットしておくことでGCに relocation の対象外であることを知らせる
      • デリファレンスしたタスクのタスクツリー上での深さが最浅だった場合 expiration depth として保持する


上の操作の一部はobjectではなく entanglement region と呼ばれる単位で行います。
これは entangled object を効率よく追跡するため、他のタスクから参照される immutable object と、そこから(immutable)参照を辿って到達できる一連のローカルオブジェクトを含む集合のことです。
entangled object から辿れるならそうでない(disentangledな) object へも他のタスクからアクセスされうるためですね。

最後の expiration depth というのは、entangled region の寿命を管理するための値です。
entangled region を参照しているタスクのすべてが join された際にそのオブジェクトは disentangled object になります。
これを把握するため、各 entangled region を参照しているタスクの内最も浅い(rootに近い)ものの深さを計算しておきます。

GC

上のようにしてデリファレンス時に、各オブジェクトが entangled かどうかを判別し、タスク間で(lock freeに)協調します。
ここで作成したデータはGCにも利用されます。

MPLではinternal taskのGCにはconcurrent mark sweep、leaf taskのpinned/unpinned objectのためのハイブリッドGCを行います。

leaf taskでは、unpinned object を relocate (&コンパクション)する場合、
1. まず移動先にオブジェクトをコピーしたのち、
2. コピー先を示すポインタ(forward pionter)を設定し、他のポインタから対象オブジェクトが参照されていた場合、移動後のオブジェクトの場所がわかるようにします。
3. 移動元のオブジェクトは forward pointer を設定した後に、そのオブジェクトにアクセスしうる参照がすべて移動後のオブジェクトの位置を知った後にメモリを回収します。

pinned object については、entangled region のタスクツリー上の深さと expiration depth が一致した際に、entangled を解消(unpin)します。
オブジェクトをアロケートしたタスクが参照より先に join された場合は、子タスクの管理するヒープとその参照情報は親タスク側のヒープ(と参照情報)とマージされます。

internal taskでは、fork 時に生きているオブジェクト全体のスナップショットとentangled regionのrootを取り、
mark-sweep方式で到達不能なオブジェクトの使用しているメモリを回収します。

感想

disentangled はかなり簡潔に定義されている概念とはいえ、型で保障されるわけでもない並列プログラムの性質ですので、
自分の書いたコードが disentangled かどうかを気にしなくて良くなった今回の提案はかなり嬉しいと思います。

とはいえ今のところロックプリミティブが存在すらしないので(!)ロックフリーアルゴリズムしか書けないというのは大分ヘビーな世界である一方、
Related Workの末尾にはちらっと future にも対応したいと書いてあるのでそっちにも期待したいところです。

*1:entanglementの提案された論文: Hierarchical Memory Management for Parallel Programs: Ram Raghunathan, Stefan K. Muller, Umut A. Acar, and Guy Blelloch. ICFP 2016

*2:v0.4でマージされるはず

Prattパーサの記事を読んだ

日記 Rust Parser Algorithm

Rustで追実装しながら zenn.dev を読みました。
頭から読んでいけば分かる丁寧な説明だったため思ったより理解に時間は掛かりませんでした。
ただmixfix operator(そんな分類はこのアルゴリズムには無さそうだが)のbinding powerについてはもう少し説明が欲しい気はしました。

また Pratt 文法(？)がどういう文法クラスに対応しているのかといった説明は無く、純粋にアルゴリズムの説明でした。
このため実際に利用(を検討)する際には1次情報にあたる必要がありそうです。

プログラミング言語の形式的意味論入門を買った

日記 Semantics 書評

プログラミング言語の形式的意味論入門 を買いました。
表紙に書いてありますが The Formal Semantics of Programming Languages: an Introduction という洋書の和訳です。
多分途中で挫折しますが、とりあえず頭から眺めてみようと思います。

エラッタ

見つけた(気がする)ヤツはここにメモしていこうと思います。

  • p.22 末尾
    • 誤: b_{0}\land{}b_{1}\to{false}
    • 正: b_{0}\land{}b_{1}\to{true}
  • p.25 中央
    • 誤: 状態を変えずにすぐ停止しするだろう
    • 正: 状態を変えずにすぐ停止するだろう
  • p.29
    • 誤: を得た後に、左側の部分式を評価し、
    • 正: を得た後に、右側の部分式を評価し、
  • p.29
    • 誤: 1ステップの実行の結果状態がσに変化し
    • 正: 1ステップの実行の結果状態がσ'に変化し
  • p.37
    • 誤: ただし、 m = m0' + m1'
    • 正: ただし、 m' = m0' + m1'
  • p.41
    • 誤: \sigma{}[n-m/N] m\lt{}n のとき
    • 正: \sigma{}[m-n/M] n\gt{}m のとき
  • p.41
    • 誤: \langle{}Euclid,\sigma{}''\rangle{}\to{\sigma{}''} となる \sigma{}'' が存在する
    • 正: \langle{}Euclid,\sigma{}''\rangle{}\to{\sigma{}'} となる \sigma{}' が存在する
  • p.43 末尾のステートメントが理解出来ないけど少なくとも何かは間違っている気がする…
    • 誤: d\vDash \langle{}c,\sigma{}\rangle{}\to\sigma{} かつ \vDash \langle c,\sigma_{0}\rangle\to \sigma_{1}
    • 正: d\vDash \langle{}c,\sigma{}\rangle{}\to\sigma{} かつ d\vDash \langle c,\sigma_{0}\rangle\to \sigma_{1}

あるいは d\vDash \langle{}c,\sigma{}\rangle{}\to\sigma{}\ かつ\ \langle c,\sigma_{0}\rangle\to \sigma_{1} …かな？

  • p.46
    • 誤: 最小の導出 d が存在して \exists\sigma,\sigma'\in\Sigma.\ \vDash\langle w,\sigma\rangle\to\sigma'
    • 正: 最小の導出 d が存在して \exists\sigma,\sigma'\in\Sigma.d\vDash\langle w,\sigma\rangle\to\sigma'
  • p.46
    • 誤: 真部分導出として d’\vDash\langle w,\sigma\rangle\to\sigma’
    • 正: 真部分導出として d’\vDash\langle w,\sigma''\rangle\to\sigma’

Zig言語用コンテナライブラリ llrbtree-zig を実装しました

Zig Algorithm

序

Zig 言語の標準ライブラリにはジェネリックなキーバリューコンテナが含まれません。
このためZig言語用に Red-Black treeを用いた(当然ジェネリックな)コンテナライブラリ GitHub - eldesh/llrbtree-zig: A container library with llrbtree written in Zig. を実装しました。

順序の付いた値の集合である LLRBTreeSet(T) と、順序の付いたキーに値を紐付ける LLRTTreeMap(K,V) を提供します。

アルゴリズム

このライブラリはRed-Black tree(RB tree)の中でもinvariantをより強くした Left-Leaning Red-Black tree(LLRB tree)を実装しています。

RB treeでは 3-node に対応するノードの構成が二つ存在するのに対して、LLRB tree では一つ(左傾版)に正規化されます。

アルゴリズムの作者である Robert Sedgewick は分岐が少なるため速くなると主張していますが、多分それほど変わらないと思います。気分です。(あと、著者の実装はバグっています。)

LLRB tree は RB tree なので計算量はそれに倣います。つまり検索、挿入、破棄はそれぞれノード数 n に対して O(log n) です。

使い方

このライブラリの使い方は Rust の BTreeSet/Map におおよそ準拠します。

ただし、削除されたエントリなどは caller 側(の変数)に所有権が戻るので明示的に削除する必要があります。

Set of u32

u32 の集合を使用する例を示します。

var set = llrbtree.llrbset.LLRBTreeSet(u32).new(alloc, .{});
defer set.destroy();
// 値を追加するには insert 関数を使います。
// 同じ値が存在する場合は、古い値が返値として返されます。
_ = try set.insert(5);
// 古い値である 5 が返されます。
assert((try set.insert(5)).? == 5);
assert((try set.insert(7)) == null);

// 集合から値を検索するには `get` 関数を使います。
// 存在しない場合は `null` が返ります。
assert(set.get(&@as(u32, 5)).?.* == 5);
assert(set.get(&@as(u32, 10)) == null);

// 値を削除するには `delete` 関数を使います。
// 削除された値が戻り値として返されます。
assert(set.delete(&@as(u32, 5)).? == 5);
// '5' は既に削除されています。
assert(set.delete(&@as(u32, 5)) == null);

_ = try set.insert(5);
_ = try set.insert(9);
// イテレータは値を昇順で列挙します
var items = set.to_iter();
assert(items.next().?.* == 5);
assert(items.next().?.* == 7);
assert(items.next().?.* == 9);

Map of u32 → []u8

キーとして u32、値として []u8 を使用する場合を以下に示します。

var map = llrbtree.llrbmap.LLRBTreeMap(u32, []u8).new(alloc, .{});
defer map.destroy();
// key/value ペアを追加するには `insert` 関数を使います。
// 既に同じキーについて値が存在する場合は古い値が返されます。
_ = try map.insert(5, try alloc.dupe(u8, "25"));

// 古い値である "25" が返されます。
var old = (try map.insert(5, try alloc.dupe(u8, "20"))).?;
defer alloc.free(old);
assert(mem.eql(u8, old, "25"));
assert((try map.insert(7, try alloc.dupe(u8, "28"))) == null);

// あるキーに紐付いた値を検索するには `get` 関数を使います。
// 値が紐付けられていない場合は `null` が返されます。
assert(mem.eql(u8, map.get(&@as(u32, 5)).?.*, "20"));
assert(map.get(&@as(u32, 10)) == null);

// エントリを削除するには `delete` 関数を使います。
// そのキーに紐付けされた値が返されます。
var deleted = map.delete(&@as(u32, 5)).?;
defer alloc.free(deleted);
assert(mem.eql(u8, deleted, "20"));
// '5' に紐付けされた値は既に削除されています。
assert(map.delete(&@as(u32, 5)) == null);

_ = try map.insert(5, try alloc.dupe(u8, "20"));
_ = try map.insert(9, try alloc.dupe(u8, "36"));
// イテレータはキーの昇順でエントリを列挙します。
var kvs = map.to_iter();
var k0 = kvs.next().?;
assert(k0.key().* == 5 and mem.eql(u8, k0.value().*, "20"));
var k1 = kvs.next().?;
assert(k1.key().* == 7 and mem.eql(u8, k1.value().*, "28"));
var k2 = kvs.next().?;
assert(k2.key().* == 9 and mem.eql(u8, k2.value().*, "36"));

イテレータ

上の例で使用しているイテレータは GitHub - eldesh/iter-zig: A basic iterator library written in Zig で定義されているイテレータであり、map、filter、fold などの操作をすることができます。

イテレータについては Zig 言語用のイテレータライブラリを書きました - ::Eldesh a b = LEFT a | RIGHT b で説明しています。

注意点として、llrbtree-zig が提供しているイテレータは所有権を持たないもののみということがあります。つまり現状ではイテレータだけを持ち運んでツリー本体を破棄することは出来ません。(それ以前に他の書き換え操作全てが出来ません)

// これは出来ない
var iter = map.to_iter();
map.destroy(); // この時点で iter の参照している値も破棄される
while (iter.next()) |item| {}

所有権管理

Zig では(文脈無しで使用できる)標準のアロケータというものが存在しません。このためコンテナでも何らかの方法でアロケータを指定出来る必要があります。ついでに型からvalidなインスタンスを得る一般的な方法も存在しません*1

このため LLRBTreeSet/Map ではコンストラクタ(new関数)で動的にアロケータを受け取ります。

new 関数のシグネチャは Set/Map のいずれも以下のようになっています。

pub fn new(alloc: Allocator, cfg: Self.Config) Self;

第一引数でツリーノードのアロケータを指定します。

第二引数の Config では(必要であれば)キーやバリューのアロケータを独立に指定できます。

また キー、バリュー それぞれについてコンテナが所有権を持たないように指定することも出来ます。

Config の実体は Set の場合は:

pub const Config: type = struct {
    item: Ownership = Ownership.owned(),
};

Map の場合は:

pub const Config: type = struct {
    key: Ownership = Ownership.owned(),
    value: Ownership = Ownership.owned(),
};

となっています。

Ownershipは所有権の有無と用いるアロケータを指定する型で、以下のように定義されています。

pub const Ownership: type = union(enum) {
    OwnedAlloc: std.mem.Allocator,
    Owned: void,
    NotOwned: void,
    ...
};

各バリアントはそれぞれ以下のような意味を表しています。

OwnedAlloc
指定したアロケータによって管理されるメモリ上に所有する
Owned
デフォルトアロケータ(newの第1引数)によって管理するメモリ上に所有する
NotOwned
コンテナによって所有されない

例えば LLRBtreeMap を以下のように構成すると、所有権を持たない文字列リテラルをバリューとしてコンテナに管理させることが出来ます。

var map = LLRBTreeMap(u32, []const u8).new(alloc, .{ .value = .NotOwned });
defer map.destroy();

コード中にあるようにコンテナ自体の破棄については所有権がある場合と変わりなく destroy() を呼ぶことで行えます。

他のプロジェクトからの参照方法

llrbtree-zig は依存プロジェクトを zigmod で管理しており、自身も zigmod で参照することを想定しています。

依存関係の指定には例えば以下のように記述すれば使用できます。

root_dependencies:
  - src: git git@github.com:eldesh/llrbtree-zig commit-v1.0
dependencies:
  - src: git git@github.com:eldesh/llrbtree-zig commit-v1.0

Cite

*1:馬鹿なの？

Zig 言語用のイテレータライブラリを書きました

Zig

basis-concept-zig に続いて、Zig 言語のためのイテレータライブラリ iter-zig を作りました。
そこそこ頑張ってReadmeを書いたので詳細はそれを読むことで分かると思います。この記事には書きたいことを書きます(自明)。

Concept

イテレータは、値の集合から各要素を高々一度ずつかつ網羅的に列挙するデータ構造のことです*1。
iter-zig ではRustと同じくイテレータコンセプトを以下の条件を満たす型と定めました。

  • Self: type = @This() 型を持つ
  • Item: type 型を持つ
  • fn next(*Self) ?Item というメソッドを持つ

この条件を確認するメタ関数として concept.isIterator: fn (type) bool という関数が用意されています。

comptime assert(!isIterator(u32));
comptime assert(isIterator(range.Range(u32)));

対応コンテナ

標準で提供されるコンテナをラップする以下のようなイテレータが提供されています。

  • ArrayIter
  • SliceIter
  • ArrayListIter
  • SinglyLinkedListIter
  • BoundedArrayIter
  • TailQueueIter

使い方はREADMEやテストなどを参照して下さい。
どれもラップされたコンテナを書き換えずにイテレーションが出来ます。

派生メソッド

このライブラリの提供するイテレータの実装型は、それぞれの next 関数のみに依存したさまざまな派生関数(？)を持っています。

例えば map, filter, fold などがあります。(Rust の Iterator trait の備えている関数は大体あります)

これらは以下のように使用できます。

var arr = [_]u32{ 1, 2, 3, 4, 5, 6 };
var it: Filter(Copied(SliceIter(u32)), fn (u32) bool) = iter.to_iter.SliceIter(u32).new(arr[0..]).copied().filter(struct {
    fn call(x: u32) bool {
        return x % 2 == 0;
    }
}.call);
assert(@as(u32,2) == it.next());
assert(@as(u32,4) == it.next());
assert(@as(u32,6) == it.next());
assert(null == it.next());

上のコード中の it の型(Filter(Copied(SliceIter(u32)), fn (u32) bool))を見ても確認出来ますが、
これらの派生関数の実装はRustと同じくいわゆるアダプタースタイルで実装されており、新たに値の列を返す関数は、イテレータ型のインスタンスを返すように実装されています。
従って新しく作られる値の列の各要素の評価は新しいイテレータの next が呼ばれた時点で行われます。
例えば it.map(f).map(g).map(h) は3回マップしてますが、 it は1度だけイテレーションされます(3重にマップされるイテレータが返る)。

ユーザ定義イテレータ

イテレータをユーザ定義することも出来ます。
例えばライブラリユーザがイテレータを定義する場合は以下のようにします。

const Counter = struct {
  pub const Self = @This();
  pub const Item = u32;
  count: u32,
  pub fn new() Self { return .{ .count = 0 }; }
  pub fn next(self: *Self) ?Item {
    self.count += 1;
    if (self.count < 6)
      return self.count;
    return null;
  }
};

この Counter はイテレータコンセプトを満たし、(当然)以下のように使うことが出来ます。

comptime assert(isIterator(Counter));
var counter = Counter.new();
assert(@as(u32, 1) == counter.next());
assert(@as(u32, 2) == counter.next());
assert(@as(u32, 3) == counter.next());
assert(@as(u32, 4) == counter.next());
assert(@as(u32, 5) == counter.next());
assert(null == counter.next());

しかしこのイテレータは map や filter を実装していません。
それらの派生関数(?)を自分で実装するのは大変です。そこで iter-zig は prelude.DeriveIterator というメタ関数を提供しており、派生関数を自動で導出することが出来ます。

const CounterExt = struct {
  pub const Self = @This();
  pub const Item = u32;
  pub usingnamespace prelude.DeriveIterator(@This()); // 派生関数を導出

  count: u32,
  pub fn new() Self { return .{ .count = 0 }; }
  pub fn next(self: *Self) ?Item {
    self.count += 1;
    if (self.count < 6)
      return self.count;
    return null;
  }
};

この CounterExt イテレータは各種の派生関数を備えており、以下の例では map、filter、scan を使用しています。

var counter = CounterExt().new();
var it = counter
    .map(incr) // 2,3,4,5,6
    .filter(even) // 2,4,6
    .scan(@as(u32, 0), sum);
assert(@as(u32, 2) == it.next());
assert(@as(u32, 6) == it.next());
assert(@as(u32, 12) == it.next());
assert(null == it.next());

prelude.DeriveIterator はユーザ定義の実装が存在しない関数のみ導出するため、対象の型について効率的な実装が出来る場合は、素直にそれを実装しておくだけで共存することが出来ます*2。

プロジェクトへの追加

iter-zig はパッケージマネージャとして zigmod の利用を想定しています。他のパッケージから(現在のバージョンである v0.2 の) iter-zig に依存する場合は以下のように commit-v0.2 を指定します。

root_dependencies:
  - src: git git@github.com:eldesh/iter-zig commit-v0.2
dependencies:
  - src: git git@github.com:eldesh/iter-zig commit-v0.2

*1:この辺は微妙で、単に null を返すかも知れない関数みたいに定めた方が便利かも知れません？

*2:ただしZigの制限でシグネチャの厳密なチェックは(おそらく)出来ないため、型についてはユーザが気をつける運用になります。

Zig 言語用ライブラリ basis-concept を書きました

Zig

Zig 言語用のライブラリ basis-concept を書きましたのでその紹介をします。
> github.com/eldesh/basis_concept

序

Zig は手続き的な型付き言語です。表現力としては、型上のコンパイル時計算によりアドホック多相を表現出来ます。

ただし型コンストラクタや部分特殊化が無いため、型の分類をシステマチックに行うのが面倒になっています。

このライブラリは型上の述語によって基本的な型の分類方法とそれらの上のジェネリックな関数を提供するユーティリティーライブラリです。

Concept

このライブラリでは型を分類するための述語をコンセプトと呼びます。主なコンセプトを紹介します。

Eq
等値比較を可能な型です。== で比較でき、かつポインタを含まない型は自動的にこのコンセプトを満たします。eq と ne という関数を持っている型の場合もこのコンセプトを満たします。
Ord
全順序が定義されている型を表します。プリミティブの数値型の他、 fn compare(*const @This(), *const @This()) std.math.Order という関数を持っている型もこのコンセプトを満たします。
Clone
値のディープコピーが可能な型を表します。プリミティブ型、ポインタを含まない複合型、あるいは fn clone(*const @This()) @This().CloneError!@This() を持つ型がこのコンセプトを満たします。値を複製する際アロケーションが必要になることが考えられるため、エラーを返すことが出来る戻り型になっています。

この他に rust と同様に PartialEq や PartialOrd も定義してみましたが、それらの分類を行っても処理系が活かせない情報なため削除を検討しています。

使い方

例としてユーザ定義の struct 型を等値比較する方法を示します。

以下のような型 S を考えます。

const S = struct {
  val_int: u32,
  val_opt: ?u8,
  val_eit: error{MyError}![5]u8,
};

このようなポインタを含まない struct のインスタンスを Eq.eq で比較できます。

comptime assert(isEq(S));
const s1: S = ...;
const s2: S = ...;
if (Eq.eq(&s1, &s2)) {
    ...
}

標準ライブラリにある std.mem.eql でも同様に構造に基づいた比較が可能ですが、これはポインタフィールドをアドレスで比較します。
ポインタを含む構造体で Eq コンセプトを満たすためには eq と ne メソッドを持つ必要があります。

const T = struct {
  val: *u32,
  pub fn eq(self: *const @This(), other: *const @This()) bool {
      return self.val.* == other.val.*;
  }
  pub fn ne(self: *const @This(), other: *const @This()) bool {
      return self.val.* != other.val.*;
  }
};

const x: T = ...
assert(Eq.eq(&x, &x));

より詳しくは README.md をご覧下さい。

プロジェクトへの追加

basis-concept は外部ライブラリに依存していないためその場でビルドすることが出来ます。

私は開発に zigmod を使用しているので zigmod プロジェクトへの依存の追加例を示しておきます。

root_dependencies:
  - src: git git@github.com:eldesh/basis_concept-zig commit-v1.3
dependencies:
  - src: git git@github.com:eldesh/basis_concept-zig commit-v1.3

AnteでAObenchを書いた

AObench Ante

Ante という新しいプログラミング言語(とその処理系)があります。


面白そうなので勉強がてらAObenchを移植してみました:
GitHub - eldesh/aobench_ante: A microbench for floating point calculation in Ante programming language

言語仕様

簡単に特徴を述べると以下のような感じです：

  • Rust製
  • 正格評価
  • 関数型言語
  • 型クラス
  • GC無し
  • Lifetime 推論 (未実装)
  • 篩型 (未実装)
  • Algebraic Effect (未実装)


肝心の機能が全部未実装なんですが…。
(そもそもこれらの機能は全部共存出来るんでしょうか？(疑))

文法

作者はかなり syntax element の冗長性を減らす志向があるようです。
例えば以下はレコードの定義です。

// 定義
type Vec = x: float, y: float, z: float
// 構築
v = Vec 1.1 1.2 1.3
// アクセス
s = v.x + v.y + v.z

また特殊なオフサイドルールを採用しており、直後にインデントされるはずではないトークンの直後ではエスケープ無しで改行出来ます。

a = 3 + 2 *
    5 + 4
    * data

速度比較

aobench-ante の実行結果です。

compiler time
ante 0m7.487s
ante(-O3) 0m2.431s
gcc 0m0.658s
polyml 0m4.589s
mlton 0m1.536s


Poly/MLの2倍時間が掛かっていますのでまだかなり遅いですね。
// 追記ここから
-O3フラグを付けてビルドしたところPoly/MLの1/2倍、GCCの3.5倍の実行時間になりました。
anteの筆者によるともう少しGCCに近い速度が出るはずとのこと。
これが本当ならネイティブコンパイルされる言語としては他の関数型言語に近くなりそうですね。
// 追記終わり
言語自体は低レイヤ指向を標榜しているのでもう少し頑張って欲しいところです。

所感

今回のコードを書くにあたって何度もコンパイラのバグに行き当たりました。(3つほど報告、うち2つは修正済み)
まだかなり基本的な箇所にバグがあり、まともな使用には耐えません。

例えば aobench-ante では画サイズ(256x256)を変数にしていますが、それを使わず決め打ちにしている箇所が複数あります(e.g. aobench_ante/aobench.an at 419d63cfa428595ff35bf53cdeb89fbe388ec923 · eldesh/aobench_ante · GitHub)が、これは型エラーを避けるためです。恐らくトップレベルの変数の型を解決する箇所にバグがあります。


今はまだこんな感じですが篩型やalgebraic effectはロマンがあるので頑張って欲しいところですね。