自作プログラミング言語Malgoがかなりそれっぽくなってきた

プログラミング言語Malgo

2017ごろから、自作のプログラミング言語Malgoとそのコンパイラを作っている。 2018年の2月に、このことをブログに書いた。あれから三年経ち、色々とできることが増えた…かというと、そうでもない。しかし、言語設計はかなり変わった。ガワだけ見るとほとんど別物だ。

当時のブログ：https://takoeight0821.hatenablog.jp/entry/2018/02/28/122847

現在のMalgoは、Haskellに影響を受けた構文を持つ、非純粋な正格評価の言語だ。型推論、高階関数、代数的データ型などの、いわゆる「関数型」な言語機能を備えている。例えば、フィボナッチ数を計算するプログラムはこんな風に書く：

-- Fibモジュールの宣言
module Fib = {
  -- Builtinモジュールのインポート
  import Builtin;
  import Prelude;

  -- 外部関数newlineのインポート
  -- newlineの実装はCで書かれている
  foreign import newline :: () -> ();

  -- 中置演算子<=の定義
  infix 4 (<=);
  (<=) = { (Int32# x) (Int32# y) -> isTrue# (ge_Int32# y x) };

  infixl 6 (+);
  (+) = { x y -> add_Int32 x y };

  infixl 6 (-);
  (-) = { x y -> sub_Int32 x y };

  -- フィボナッチ数列のn番目の要素を求める関数
  fib = { n ->
    -- ifは関数として定義されている
    -- {}で囲まれた値は遅延評価される
    if (n <= 1)
      { 1 }
      { fib (n - 1) + fib (n - 2) }
  };

  main = {
    print_Int32 (fib 5)
  };
}

Malgoの言語設計

Malgoは、できるだけ言語仕様が小さくなるように設計されている。これは、実装の負担を軽減するためと、僕個人の好みが主な理由だ。

言語の小ささを表す象徴的な例にif関数がある。 Malgoのifは、次のように関数として定義されている。

if :: Bool -> {a} -> {a} -> a;
if = { True t _ -> !t
     | False _ f -> !f
     };

重要なのはif関数の型Bool -> {a} -> {a} -> aだ。波括弧{}で囲まれた型の値は、明示的に評価（!演算子）されるまで評価が遅延される。これによって、ブロックを第一級の値として扱うことが可能になっている。

Malgoコンパイラの実装

MalgoコンパイラはLLVMを用いて実装されている。 MalgoのソースコードをLLVM IRに変換するわけだが、これは自明な処理ではない。だいたい次のようなことを考慮する必要がある。

関数値の表現方法

LLVM IRには関数値を表現する方法がない。 Malgoは関数値を多用するので、これは困る。そこで、クロージャ変換という方法を用いる。

クロージャとは、関数ポインタと自由変数の値の組だ。例えば、連想配列envにinsert関数を使って要素を追加する、次のような関数を考える。

-- 連想配列envと関数insertは定義済みとする

let insertToEnv = { name val -> insert name val env };

この関数をコンパイルするためには、

関数にユニークな名前をつける（LLVMでの関数名、関数ポインタの名前になる）
自由変数を求め、引数に付け加える
自由変数の値と関数ポインタを組にして、クロージャとする（これがinsertToEnvの実態となる）

また、insertToEnvを関数として呼び出す際は、組を分解して関数ポインタと自由変数の値を取り出し、取り出した関数ポインタに自由変数の値と本来の引数を引数として与えて呼び出す必要がある。

クロージャ変換の結果、上記のコードは次のように変換される（擬似コード）。

-- insertToEnvの関数部分
define insertToEnv_impl(name, val, captures) {
  insert = captures[0];
  env = captures[1];
  return insert(name, val, env);
}

define ... {
  // insertToEnvの定義
  insertToEnv = (insertToEnv_impl, (insert, env));

  // insertToEnvの呼び出し
  closure_func = insertToEnv[0];
  closure_captures = insertToEnv[1];
  closure_func(name, val, closure_captures);
}

型消去

Malgoはパラメータ多相を持つ。例えば、次のようにしてパイプライン演算子|>を実装できる。

infixl 0 (|>);
(|>) :: a -> (a -> b) -> b;
(|>) = {x f -> f x};

|>には、どんな型のxとfでも渡すことができる。 "Hello, world" |> upcase |> putStrLnとか、2 |> { x -> x * 20}のように書ける。

|>をLLVM IRで定義するには、型変数aやbをどのように表現するかを決める必要がある。型消去は、「すべての型の値が1ワードだと仮定すると、単に型を無視するだけでパラメータ多相を実現できる」というアイディアだ。 Malgoでも型消去を採用している。

型消去を実現するための方法はいくつかあるが、最も単純なやり方は、符号拡張なりヒープへの割り付けなりで、すべての値を１ワードに収めてしまう完全なボックス化である。 Malgoはユーザー定義型が代数的データ型しか存在しない（構造体とかがない）ので、プリミティブ型のボックス化だけを定義すればよく、完全なボックス化は自然に実装できる。

型消去により、|>のLLVM IRにおける型は次のようになる（ここではクロージャを無視している）。

{ i8*, i8* (i8*, { i8*, i8* (i8*, i8*)* }*)* }* @"|>"(i8* x)

ちょっとごちゃごちゃしているが、引数xの型がi8*になっているのがわかる。（i8*は、Cにおけるvoid*に相当する）

アンボックス型

前節では、完全なボックス化の実現のためにはプリミティブ型のボックス化を定義すればよいと述べた。しかし、実際にはMalgo処理系にはボックス化の方法が定義されていない。プリミティブ型のボックス化は、次のようにユーザー定義の型と関数で実現される。

-- 32bit符号付き整数のボックス表現
data Int32 = Int32# Int32#;

-- ボックス化関数
int32# :: Int32# -> Int32;
int32# = { x -> Int32# x };

Malgoの数値リテラルは、42と書くとint32# 42#に変換される。 42#はボックス化されていない生の整数値であり、多相的な関数に渡すことはできない。これは、型変数aとプリミティブ型Int32#に、異なるカインドを与えることで実現している。具体的には、型変数aやInt32はカインドTYPE BoxedRepをもち、Int32#はカインドTYPE Int32Repをもつ。また、BoxedRepやInt32RepはカインドRepをもち、TYPEはRepのみを引数にとる。

内部実装では、型とカインドは同一のものとして扱い、型の型はカインドに、カインドの型は自分自身になるように定義している。型を総称化する際に、カインドRepをもつ型変数があれば、それを型パラメータにする代わりにBoxedRepを代入する。

TODO

だいぶ本物のプログラミング言語っぽくなってきたが、実用的なレベルには達していない。実装するべき機能はいろいろとあるが、今ぼんやりと考えているのは

レコード型
存在型
型クラス
高度な最適化
パッケージ管理システム
MLライクなモジュールシステム
Algebraic effects
構文木マクロ
Language Server

標準ライブラリもかなり貧弱なので、近いうちに気合いを入れてガッと実装してしまいたい。

星にゃーんのブログ

ほとんど無害。