Zenn
Open27

Kmkm 進捗

Haskell
C言語
プログラミング言語処理系
岡本和樹岡本和樹

前史

岡本和樹岡本和樹

今のパスの説明をする。

ソースコード（S 式）

    ↓ 構文解析
    ↓ Language.Kmkm.Parser.Sexp

構文木（カリー化・未ラムダ持ち上げ・未型付け）
Language.Kmkm.Syntax.Phase1

    ↓ 型検査
    ↓ Language.Kmkm.Builder.Pass1

構文木（カリー化・未ラムダ持ち上げ・既型付け）
Language.Kmkm.Syntax.Phase2

    ↓ 逆カリー化
    ↓ Language.Kmkm.Builder.Pass2

構文木（非カリー化・未ラムダ持ち上げ・既型付け）
Language.Kmkm.Syntax.Phase3

    ↓ 部分適用除去
    ↓ Language.Kmkm.Builder.Pass3

構文木（非カリー化・未ラムダ持ち上げ・既型付け）
Language.Kmkm.Syntax.Phase4

    ↓ ラムダ持ち上げ
    ↓ Language.Kmkm.Builder.Pass4

構文木（非カリー化・既ラムダ持ち上げ・既型付け）
Language.Kmkm.Syntax.Phase5

    ↓ トップレベルの非コンパイル時式の関数化
    ↓ Language.Kmkm.Builder.C.Pass1

構文木（非カリー化・既ラムダ持ち上げ・既型付け）
Language.Kmkm.Syntax.Phase5

    ↓ C 構文木へ変換
    ↓ Language.Kmkm.Builder.C.Pass2

構文木（C 抽象）
Language.Kmkm.Builder.C.Syntax

    ↓ より具象な C 構文木へ変換
    ↓ Language.Kmkm.Builder.C.Pass3

構文木（C 具象）
Language.C.Syntax.AST (language-c)

    ↓ C ソースコード生成
    ↓ Language.C.Pretty (language-c)

C ソースコード
岡本和樹岡本和樹

副作用のある関数（procedure と呼ぶ）を書くための下ごしらえができた

岡本和樹岡本和樹

束縛時の型を不要にして型注釈を書けるようにした

型が必須なのは、関数引数と、再起変数を束縛する式への型注釈になった

実装としては

  • 変数を束縛する式を見て別の変数への依存を見つける
  • 依存関係グラフを強連結成分分解
  • トポロジカルソート
  • 被依存側から順に型検査
岡本和樹岡本和樹

モジュールシステム（ソースファイル分割）ができた

パスが更新された

ソースコード（S 式）

    ↓ 構文解析
    ↓ Language.Kmkm.Parser.Sexp

構文木（カリー化・未ラムダ持ち上げ・未型付け）
Language.Kmkm.Syntax.Phase1

    ↓ 型検査
    ↓ Language.Kmkm.Builder.Pass1

構文木（カリー化・未ラムダ持ち上げ・既型付け）
Language.Kmkm.Syntax.Phase2

    ↓ 逆カリー化
    ↓ Language.Kmkm.Builder.Pass2

構文木（非カリー化・未ラムダ持ち上げ・既型付け）
Language.Kmkm.Syntax.Phase3

    ↓ 部分適用除去
    ↓ Language.Kmkm.Builder.Pass3

構文木（非カリー化・未ラムダ持ち上げ・既型付け）
Language.Kmkm.Syntax.Phase4

    ↓ ラムダ持ち上げ
    ↓ Language.Kmkm.Builder.Pass4

構文木（非カリー化・既ラムダ持ち上げ・既型付け）
Language.Kmkm.Syntax.Phase5

    ↓ トップレベルの非コンパイル時式の関数化
    ↓ Language.Kmkm.Builder.C.Pass1

構文木（非カリー化・既ラムダ持ち上げ・既型付け）
Language.Kmkm.Syntax.Phase5

    ↓ C 構文木へ変換
    ↓ Language.Kmkm.Builder.C.Pass2

構文木（C 抽象）
Language.Kmkm.Builder.C.Syntax

    ↓ ソースファイル C 構文木からヘッダーファイル C 構文木へ変換
    ↓ Language.Kmkm.Builder.C.Pass3

構文木（C 抽象）
Language.Kmkm.Builder.C.Syntax

    ↓ より具象な C 構文木へ変換
    ↓ Language.Kmkm.Builder.C.Pass4

構文木（C 具象）
Language.C.Syntax.AST (language-c)

    ↓ C ソースコード生成
    ↓ Language.C.Pretty (language-c)

C ソースコード
岡本和樹岡本和樹

モジュールの変換ができた（6月19日）

int main(void) {
    return ({0});
}

が出力できた

岡本和樹岡本和樹

見やすいエラー出力（出現位置表示）を実装したら盛大にデグレードしたのをやっと修正した

エラー出力

岡本和樹岡本和樹

文字列をとりあえずサポートしたので hello world ができるようになった

(module
  main
  (list
    kmkm.io
    kmkm.prim
    kmkm.proc)
  (list
    (bind-value
      main
      (procedure
        (list
          (call (apply kmkm.io.print "Hello world!"))
          (call (apply kmkm.proc.pureInt 0)))))))
岡本和樹岡本和樹

パラメーター多相の実装をポインター（ジェネリクス）か実体化（テンプレート）かでなやんでいる

とりあえずポインターでやってみようかな

岡本和樹岡本和樹

2021.10.31

パラメーター多相の実装を実装した。
関数についてのみ。データ型はまだ。

 (module
   parametricPolymorphism
   (list
     kmkm.prim)
   (list
     (bind-value id (for-all a (function a a a)))
     (bind-value hello (apply id "Hello world!"))))
岡本和樹岡本和樹

やーーっとパラメーター多相なデータ型（Java 系でいうジェネリックなクラス）の定義ができた

これが

(module
  foo
  (list)
  (list
    (define solo (for-all a (list (solo (list (item a))))))))

こうなる

#ifndef FOO_H
#define FOO_H

struct foo_solo {
  void (* foo_item);
};

struct foo_solo foo_solo(void const (* const foo_item));

#endif

#include "foo.h"

struct foo_solo foo_solo(void const (* const foo_item))
{
  return (struct foo_solo) { foo_item };
}

使う部分の実装がまだ