κeenです。最近はAIで自作プログラミング言語を作るのが流行ってますね。私も前から温めていたアイディアを形にしてみたので紹介します。

設計思想

作ったのは SLCという言語です。一応純粋関数型言語になるのかな？ならないかも。

プログラムというのは計算です。開始状態から始め、値を評価して条件分岐をしたり合流したりしながら終了状態へと向かっていき、最後には値となります。

はじめは値がなくて計算だけ、実行中の状態をみると計算途中の値と残りの計算があり、おわりは計算がなくて値だけです。よく考えてみると値と計算は表裏の関係にあるのに気付きます。

我々が関数を書くときも値を受け取ったところからはじめて値を使った計算を書いたり値に基いた条件分岐を書いたりしながら書き進めますよね？

このスタイル、アンバランスじゃないですか？値と残りの計算は表裏の関係だったので値を中心にプログラムを書くだけでなく残りの計算を中心にプログラムを書けてもいいと思いませんか？ 残りの計算側から書くというのは要は終了状態から書きはじめるということです。

プログラムの始点と終点、両端から書くことで散らばりがちな条件分岐もスマートに書ける気がします。分かりやすい例だと「このプログラムが終了するときは正常終了して値を返すか異常終了してメッセージを返すかだ」のように関数の終了条件を記述できると便利だと思いませんか？ そういうプログラミング言語SLCを作りました。

ところでさっきから「残りの計算」と呼んでいたものは継続という名前で知られていますね。以後、継続と呼ぶことにします。

継続の話を続けましょう。継続というのは残りの計算、もっとちゃんと言うと終了状態に到達するまでの残りの計算です。値と継続を合成するとプログラムが完成し、そのままプログラムが終了するまで実行が進みます。いくつかのプログラミング言語には exit という関数があって呼んだらその場でプログラムが終了してしまいますが、そんなイメージです。値が v 、 継続が k だとすると、SLCでは <v | k> という記法で値と継続を合成します。

値でも継続でもない存在として関数があります。みなさん関数を値に適用しますよね？関数を f とするとその記法はちょっと見馴れないですが、 <v | f と書きます。

値に関数を適用できるということは表裏の関係にある継続も関数に適用できます。その記法は f | k> になります。継続を関数に適用するというのがイメージつきづらいですかね？例えば k の型が i32 だったとします。これは数値を受け取ってプログラムが終了するまで計算する継続です。例えば先に例に挙げた exit なんかが該当します。 そして f の型が String -> i32 だとします。これは例えば "OK" を受け取ったら 0 を、それ以外の文字列を受け取ったら -1 を返す関数だったとしましょう。この2つを f | k> のように合成すると「"OK" を受け取ったら終了ステータス 0 で、それ以外の文字列を受け取ったら終了ステータス -1 でプログラムを終了させる継続」という意味になります。元々 i32 の継続だったのが String の継続になっているので私は String -> i32 のアダプターのようなものを噛ませてるイメージを持っています。

記法からちょっと予想がついたかもしれませんが、値→関数→継続と連続して合成することもできます。

<v | f | k>

これは v に f を適用して得られた値と k を合成すると捉えてもいいですし、 f に k を適用して得られた継続と v を合成すると捉えても構いません。どちらでもプログラムの意味は変わりません。 f1, f2, f3のように複数の関数があれば一気に合成することもできます。

<v | f1 | f2 | f3 | k>

コード例

ハローワールド

基本アイディアが分かったところでHello Worldをみてみましょう。まだ紹介していない機能もありますが、一旦スルーして下さい。

proc main | (exit: i32) / {IO} {
    <"Hello, SLC!" | println;
    <0 | exit>
}

いきなり継続がでてきました。 (exit: i32) と書いてあるのがこの main 手続の継続を受け取っている箇所です。 | の左側が値の引数、右側が継続の引数なのですが、 main は値の引数がないので | の左側は空です。 / {IO} の部分は今回説明しないのでスルーしましょう。

関数本体の1行目は <"Hello, SLC!" | println; で関数を値に適用して返り値は特に使っていません。この辺はRust風に ; で複数行のプログラムを書けるようになっています。 そして2行目がさきほど説明した <0 | exit> と値と継続の合成です。値と継続の合成のことはカットと呼んでいます。ちゃんと main がカットで終わっていますね。

関数

さっき定義したのは値も継続も受け取る proc でしたが、値だけしか受け取らない、あるいは継続だけしか受け取らないものはちょっとだけ省略した記法で func で書けます。

func double(n: i64) -> i64 {
    <(n, 2) | mul
}

これは値を受け取って値を返す関数です。親しみやすいでしょう。因みにSLCには中置演算子がないので四則演算も2引数関数になっています。

逆に、継続を受け取って継続を返す関数も書けます。そのときは返り型の前にある矢印を <- にして記述します。

func stringify(out: String) <- Bool {
  mu Bool {
    True => <"True" | out>,
    False => <"False" | out>,
  }
}

String 継続を受け取って Bool 継続を返す関数です。みなさんの馴れた言い方だと Bool 値を受け取って String 値を返す関数とも言えます。 mu はもうちょっとあとで説明するので一旦スルーして下さい。

-> の関数と <- の関数は値と継続のどちらに名前をつけるかだけでとくに振舞の違いはありません。

データ型

個人的に気に入ってるのはデータ型です。Rustを出発点としてるのでRustでいう struct、SLCでは data と呼ぶものと enum があります。

data Point {
    x: i64,
    y: i64,
}

enum Size {
    Small,
    Big(i64), // how far over the limit
}

ですがこれらは値のためのデータ型ですよね？継続のためのデータ型、 menu と form もあります。

form は分かりやすいですね。 継続を束ねた継続、データを受け取れます。 data が値を作るときにデータを入れてあげて使うときにパターンマッチで分解してどうやって使うか書きますよね？その逆をやるのが form です。

こういうフォームを用意したとします。

form User {
    id: i32,
    name: String,
}

このフォームのインスタンスは i32 と Stirng を受け取る継続です。インスタンスを作るときは id: i32 と name: String を受け取ったら何をするかを記述します。

// exit: i32は継続とする

let f = mu User {
    // idとnameを受け取ったらやることを書く
    User {id, name} => {
        of <(id, 0) | gt {
            // exitで早期リターン
            False => <-1 | exit>,
            True => (,),
        };
        of <(name, "anonymous") | eq {
            True => (,),
            // exitで早期リターン
            False => <-2 | exit>
        };
        // formは継続なので最後の計算まで書く、
        // つまり最後はカット
        <0 | exit>
    }
};

このインスタンスを計算に使うときはデータを入れてあげます。

<User{ id: 1, name: "anonymous"} | f>

menu も form と同様に継続を束ねるデータ型ですが、 enum のようにどれか1つの継続が使えます。

menu Drink {
    cola: String,
    beer: String,
}

この Drink メニューのインスタンスを作るには、 cola, beer をそれぞれどう提供するか記述してあげます。 cola, beer それぞれが継続なのでその継続に提供する値を食わせてあげて下さい。

let m = mu Drink {
    cola <= <"Cola" | cola>,
    beer <= <"🍺" | beer>,
};

このメニューから選ぶには m.field の構文を使います。

<m.cola | println; // "Cola"
// あるいは
<m.beer | println; // "🍺"

値を保持する data や enum と違って計算を保持しているのでフィールドを参照する度に計算が走ります。

パターンマッチと2つの mu

この言語でのパターンマッチには of を使います。とはいっても既に出てきていますがね。

func not(b: Bool) -> Bool {
    of b {
        True => False,
        False => True,
    }
}

of EXPR { PAT => EXPR, PAT => EXPR} の構文です。

もう1つ、 mu という変な構文がありましたね。あれもパターンマッチができますが、どちらかというとパターンマッチはオマケみたいなものです。本質的にはSchemeにあるような call/cc に近い存在です。

先の not を <- で実装してみましょう。

func not(out: Bool) <- Bool {
    // ...
}

これ、ちょっと困りません？あるのは出力する継続だけで条件分岐する対象の値がありません。値が渡されるのは分かっているのにそれを呼ぶ名前がありません。そこで mu という構文で「渡されるはずの値」 を取り出すことができます。

func not(out: Bool) <- Bool {
    mu Bool {
        b => of b {
            True => <False | out>,
            False => <True | out>,
        }
    }
}

さらにそのままパターンマッチに入れるのでこういう書き方もできるのです。

func not(out: Bool) <- Bool {
    mu Bool {
        True => <False | out>,
        False => <True | out>,
    }
}

mu は mu TYPE { PAT => CUT, PAT => CUT, ...} の構文です。 => の左側が値のパターン、=>の右側がカットです。 mu と { の間が型ですし、マッチした腕が式でなくカットだったりとちょっとクセがありますね。イメージとしては「継続を組み立ててる中で急に値を取り出す構文、全体としては継続になる」と思っておいて下さい。

mu にはもう1つの構文があります。menu を組み立てたときの構文を覚えていますか？ mu ですが、腕が <= になっています。

let m = mu Drink {
    cola <= <"Cola" | cola>,
    beer <= <"🍺" | beer>,
};

これは先の mu とは逆の機能で、主に menu を組み立てるのに使います。 <= の左側が継続のパターン、<=の右側がカットです。イメージとしては「値を組み立ててる中で急に継続を取り出す構文、全体としては値になる」と思っておいて下さい。

タプルの親戚

SLCにはテンソル(タプル) (T1, T2) がありますが、それ以外の無名データ型もあります。data, enum, menu, form それぞれに対応するものがあります。

値を複数受け取る関数は (T1, T2) を引数にとり、継続を複数受け取る関数は (K1 & K2) を引数にとります。全体として「T1 と T2 を使って K1 または K2 を実現できる」のような意味を型から読み取れます。

// 引数として継続を複数とる。
// ok: 成功したときの継続
// failed: 失敗したときの継続
proc parse_literal(input: String, pos: i64, text: String) | (ok: i64 & failed: String) {
    let end = <(pos, <text | str_len) | add;
    // The slice is taken only once it is known to be in range.
    let matches = of (<(end, <input | str_len) | le) {
        True => <(<(input, pos, end) | substring, text) | eq,
        False => False,
    };
    of matches {
        // 成功したらok継続を呼ぶ
        True => <end | ok>,
        // 失敗したらfailed継続を呼ぶ
        False => <"invalid JSON literal" | failed>,
    }
}

他の言語で例外や Either, Result などで処理していたエラーの扱いを継続でできます。ここでは ok, failed と名前をつけましたが、 return, throw なんかにしても面白いかもしれません。

menuの真価

data と enum はRustをはじめとして色々な言語でよく知られているとして、 menu (enum の双対なので co data)はあまり知られていないんじゃないでしょうか。これはかなり面白い機能を提供してくれます。フィールドを選んではじめて計算が行なわれるので遅延計算ができます。

menu Lazy<*T> {
    force: T,
}

遅延計算を上手く使えば、無限の数列なんかも作れます。

menu Stream<+T> {
    head: T,
    tail: Stream<T>,
}

// 例えばこう構築できる
func repeat<+T>(x: T) -> Stream<T> {
    mu Stream {
        head <= <x | head>,
        tail <= <x | repeat | tail>,
    }
}

// 1,1,1,1,1,…と無限に続く数列
let s = <1 | repeat;
<s.head | println;                // 1
<s.tail.head | println;           // 1
<s.tail.tail.tail.head | println; // 1

各フィールドは enum よろしく引数もとれます。それを上手く使うとオブジェクト指向のようなこともできるのです。

menu StringBuilder {
    append(part: String): StringBuilder,
    finish: String,
}

// 中間状態を作る関数
func from(text: String, part: String) -> StringBuilder {
    let text = <(text, part) | add;
    mu StringBuilder {
        append(part) <= <(text, part) | from | append>,
        finish <= <text | finish>,
    }
}
// 初期状態を作る関数
func new() -> StringBuilder {
    mu StringBuilder {
        append(part): out <= <("", part) | from | out>,
        finish <= <"" | finish>,
    }
}

// こう使う
let start = new();
let left = <"left: " | start.append;
let left = <"42" | left.append;
let right = <"right" | start.append;
<left.finish | println;   // left: 42
<right.finish | println;  // right

純粋関数型言語ですがこのような手続型っぽいコードも書けるのが面白いですね。

継続を使った大域脱出

継続には色々な使い方があります。

早期リターンの進化形として大域脱出なんかもあります。木の探索を考えましょう。関数呼出がネストするのでコールスタックが深くなります。その状態で目的の値がみつかったら何が起きるでしょうか？普通なら今まで積み重ねてきたコールスタックを1つずつreturnして回る必要があります。しかし、あらかじめ継続を受け取っておけばその継続を起動することで一気にコールスタックを飛び越えて値を返せます。

enum Tree {
    Leaf,
    Node(Tree, i64, Tree),
}

proc walk(t: Tree, target: i64) | (
    jump: i64
    & done: (unit / {IO})
) / {IO} {
    of t {
        Leaf => <(,) | done>,
        Node(left, value, right) => {
            <("visiting ", <value | int_to_str) | add | println;
            of (<(value, target) | eq) {
                // 大域脱出する。これでネストしたwalk全てを飛び越えて呼出元に返れる
                True => <value | jump>,
                False => (,),
            };
            // walkの再帰呼び出し1
            <(left, target) | walk | (jump & mu unit {
                // walkの再帰呼び出し2
                finished_left => <(right, target) | walk | (jump & done)>,
            })>
        },
    }
}

let tree = ...;
let hit = mu {
    k <= {
        let not_found = mu unit { exhausted => <-1 | k> };
        // 呼出元
        <(tree, 2) | walk | (k & not_found)>
    }
};

継続でファイルを必ず閉じる

ファイルをopenしたあと、必ず閉じる処理って難しいですよね。言語ごとに専用の構文が用意されていると思いますが、SLCならイディオムでカバーできます。 関数から返る手段は exit などの継続しかないので exit 変数をシャドウイングしてしまえば関数から返るときに必ずファイルを閉じるようにできます。

// exit: i32は継続とする

// 一旦ファイルを開く
let file = <"examples/basics/hello.sl" | fs::open;
// exit継続をシャドウイング
let exit = mu i32 {
    status => {
        <file | fs::close;
        <status | exit>
    },
};
// ファイルにアレコレする

Cの goto FAIL; とかGoの deferred とかに近いパラダイムですね。ですが goto FAIL; よりもユーザがミスする余地が減りますし、 deferred のように専用の構文も必要ありません。なんとなく継続の有用さが伝われば嬉しいです。

雑多な話題

この記事は継続に焦点をあてたので色々紹介できてない機能があります。例えば副作用の扱いは代数的エフェクトを導入しています。構文は hook / hand でインタフェースと実ハンドラを定義して do でハンドリングをします。ハンドラをインラインで定義する構文は hn です。

Rustのようにデータ型にメソッドを定義する構文 impl もあります。トレイト相当のものは spec です。

名前空間は sect で作って cite で利用します。

なんとなく想像ついたかもしれませんが、トップレベルの宣言のキーワードは全部4文字、式は全部2文字で統一しています。 menu とか form とかを含め、いくつかのものはAIが考えてくれました。特に menu は enum のアナグラムですし気に入ってます。

中置演算子がないのは他の機能をたくさん入れるためです。例えば(T1 | T2)や(T1 & T2)が実現してるのは中置演算子がないおかげもあります。その他にも全体的に糖衣構文は少なめです。

純粋関数型なのはミュータブルな機能を入れ忘れたからです。でも無限ループがあるので純粋関数型警察がきたら怒られるかも。ここでいう純粋関数型というのは値は全てイミュータブルで、副作用はEffectという専用の仕組みで管理できるという意味です。

if 式はありません。全部 of でやります。これは if を言語に入れると Bool を特別扱いしないといけなくなるのが嫌だったからです。of だけだと if else 相当の式がないのでちょっと不便です。

SLCの名前のとおりSymmetric Lambda Calculusから着想を受けてますが、コア言語はλ̄μμ̃(ラムダ・バー・ミュー・ミュー・チルダ)計算を採用しています。カリーハワードでいうと古典シーケント計算LKに対応します。

え？じゃあ排中律とか書けるの？書けます。

enum Choice {
    Holds(i64),
    // -TはTの継続の意味
    Refutes(-i64),
}

func lem() -> Choice {
    mu { k <= <Choice::Refutes(mu i64 { a => <Choice::Holds(a) | k> }) | k> }
}

SLCのインタプリタ、コンパイラ、ランタイム、標準ライブラリ、ドキュメントは全部AIに書かせてコードは一切読んでないです。このブログやドキュメントに書いてあることはそうなるはずの内容ですが本当に正しいかは私も知りません。特に静的検査回りはけっこう怪しいです。

結びに

値と同じくらい継続を主役にするプログラミング言語を作ってみました。もっと詳しく知りたい方はドキュメントやexamplesをみてみて下さい。

継続の強力さが伝われば幸いです。

継続は力なり