LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Syuparn

【ストレンジコード】Filskaコンパイラ開発計画(1) 言語仕様を整理する【MLIR】

Last updated at Posted at 2024-05-28

シリーズ一覧:

TL; DR

  • MLIRで言語処理系を実装したい
  • 題材として、難解プログラミング言語「Filska」を採用
    • 言語仕様がシンプル

はじめに

本シリーズでは、『ストレンジコード』に登場する難解プログラミング言語「Filska」をMLIRへ移植します。本家がPython製インタプリタなので、コンパイラにすることで高速化できるのでは？という淡い期待も寄せています。

今回は、Filskaの移植を思い立った背景についてです。具体的な実装については次回以降取り上げます。

MLIRとは？

MLIR（Multi-Level Intermediate Representation）は、言語の中間表現や中間表現同士の変換等を定義することができるコンパイラ基盤です。

コンパイラ基盤LLVMのプロジェクトの1つとして管理されており、LLVM、MLIRを使用することでコンパイル処理を複数言語間で共通利用可能です。すでに用意されている処理であれば自前で実装する必要が無く、巨人の肩に乗って開発を進めることができます。

MLIRについては、こちらの記事で詳しく紹介されています。

実装に至った背景

効率よくコンパイラを開発できるというお触れ込みもあり前々からMLIRで処理系を実装したいと思っていました。しかし、なかなか手ごろな題材が見つからず手つかずのままでした。

公式チュートリアルに「Toy言語」の実装が紹介されていますが、テンソルの扱いに特化した内容のため少しハードルが高いと感じていました1。

どんな言語を題材にしたいか

MLIRの仕様を学ぶことができ、かつ途中でやる気をなくしてしまわない、以下の条件を満たす言語が理想です。

  • 既存の言語
    • ゴールが明確（自分で作った言語だと実装が楽な仕様に捻じ曲げてしまうおそれあり）
  • 言語仕様がシンプル
    • 挫折せずに完走できる
  • 型がシンプル
    • 型が複雑だとMLIR以前に型チェック、型推論に時間を取られてしまう
    • テンソルではなくスカラー値のみを扱う
  • 誰もまだMLIRへ移植していない
    • この処理系が欲しければ自分で作るしかない！

後述するFilskaは、これらの条件にすべて当てはまる言語でした。

Filska言語とは？

続いて、Filska言語について軽く紹介します。

Filskaは書籍『ストレンジコード』に登場するプログラミング言語です。

本書は、人間にとって可読性が低い（意図的に低くされている）「難解プログラミング言語(Esolang)」を紹介するものです2。なんといっても、帯にでかでかと

この奇妙で素晴らしき変態言語の世界へようこそ！

と書かれているのがそそられます。この記事を閉じて今すぐ本屋に行きましょう（ダイマ）

そして、本書のために「書き下ろされた」難解プログラミング言語の1つがFilskaです。

特徴

Filskaはアセンブリ等の低級言語に似た構文を持ちます。brainf*ckやwhitespace等と異なり、見た目の可読性は高いです。
また、使用できるデータ型はnumberのみで、配列もありません3。

sample.filska
{ main
    set,10
    prt
    hlt
}
実行結果
10

一般的な言語と比較すると、変数と関数に対して制約が加えられています。処理は関数の代わりに「サブプログラム」という単位でまとめられ、以下の特徴を持ちます。

  • 使用できる変数（レジスタ）は以下の4つのみ
    • m サブプログラムごとに1つ、共有不可
    • x, y, z, 全サブプログラムで共有
  • サブプログラム間の移動は呼び出しではなくジャンプ
    • 処理が終わっても元のサブプログラムへ戻ってこない

そのため、サブプログラムごとのメモリをいかに使いまわすかが設計のカギとなります。
（この制約を活かした設計手法については『ストレンジコード』をご覧ください）

fact.filska
" ※ダブルクォーテーションの後はコメント

{ main
    ipt
    tmx
    jmp,fact " 入力した整数(以下Nとする)をxに格納し階乗計算
}

{ fact " x: N, y: N!の計算に使用
    set,1
    tmy " y = 1

    txm " ★
    cmp,1
    tst,g,4 " N > 1ならば4行先へジャンプ

    tym
    prt " そうでなければ N! を表示して終了
    hlt

    mul,y=yx " y = y * x
    set,1
    sub,x=xm " x = x - 1

    gto,-9 " 9行前（「★」）にジャンプすることでループ
}

$ echo 10 | filska fact.filska
3628800

Filskaでのプログラミングには難儀しますが、言語仕様がシンプルなため処理系は比較的簡単に実装できます。
本家のPython製インタプリタは600行しかありません。

ここまで挙げた特徴をまとめると、冒頭の「題材にしたい言語の条件」にぴったり当てはまりました！これは運命

  • 既存の言語
    • 互換性100%を目指すためごまかしが効かない
  • 言語仕様がシンプル
    • 本家実装は600行
  • 型がシンプル
    • float64のスカラーのみ
  • 誰もまだMLIRへ移植していない
    • Filskaの移植自体まだ無さそう
    • 難解プログラミング言語が高速で動くところを見てみたい

仕様の整理

続いて、本題のFilska移植についてです。

実装に入る前に、まず言語仕様を確認します。

  • Filskaプログラムは1つ以上のサブプログラムからなる
  • サブプログラムは0個以上の命令からなる4
  • 命令は0個以上の引数（オペランド）を持ち、引数の個数と形式は命令の種類によって決まっている

命令の引数の形式は以下の通りです。

引数 例
0個 prt
1個(数値) set,10
1個(サブプログラム名) jmp,sub1
2個(代入式) add,x=xy
2個(スワップ) swp,xy
2個(テストフラグとジャンプ先) tst,g,4

構文の仕様をWirth Syntax Notation でまとめると下記のようになります5。

Syntax = { Subprogram } .
Subprogram = "{" identifier { Instruction } "}" .
Instruction = NullaryInstruction | UnaryInstruction | BinaryInstruction | JumpInstruction | TestInstruction
NullaryInstruction = nullary_operator
UnaryInstruction = unary_operator "," number_literal
BinaryInstruction = AssignmentInstruction | SwapInstruction
JumpInstruction = jump_operator "," identifier
TestInstruction = test_operator "," test_flag "," number_literal
AssignmentInstruction = assignment_operator "," Assignment
Assignment = register "=" register register
SwapInstruction = swap_operator "," register register

nullary_operator = "inc" | "dec" | "sin" | "cos" | "tan" | "log" | "exp" | "flr" | "cel" | "rnd" | "neg" | "chr" | "prt" | "ipt" | "sqr" | "asn" | "acs" | "atn" | "tmx" | "tmy" | "txm" | "tym" | "tzm" | "tmz" | "hlt" .
unary_operator = "set" | "gto" | "cmp"
assignment_operator = "add" | "sub" | "mul" | "div" | "mod" | "pow"
swap_operator = "swp"
jump_operator = "jmp" | "jpr"
test_operator = "tst"
register = "x" | "y" | "z" | "m"
test_flag = "z" | "e" | "l" | "g" | "n"

本来、命令による引数の違いは意味論(semantics)で管理する方が適切ですが、

  • ユーザー定義命令が存在せず、命令数も少ない
  • MLIRの命令に置き換える際、引数の不整合は早い段階(Parser)で検知し構文エラーへ倒したい

という理由から構文(syntax)で定義しました。

Lexer, Parser実装時はこの仕様に沿って実装する予定です。

おわりに

以上、Filskaコンパイラ開発計画の概要の紹介でした。次回からは、具体的な実装の話に入っていく予定です。
作りながら書いているため時間が空いてしまうこともあるかもしれませんが、少しずつ進めていきたいと思います。

  1. そもそも多次元のデータ型を扱わないの場合MLIRはオーバースペックなのかもしれません... ↩

  2. 前半は一般的な言語（本書では「定型」と表現されている）についても触れられています。様々なプログラミングパラダイムに触れる意味でもおすすめです。 ↩

  3. chr 命令で数値に対応するアスキーコードの文字を出力することができるため、文字列の表示は可能です。 ↩

  4. サブプログラムの命令が0個の場合異常終了してしまうため、実際には1つ以上必要です。 ↩

  5. よく見ると z が衝突していますが、現れる場所で役割を区別可能なためパーサー実装を工夫すれば対処可能です。 ↩

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?