自作言語BinOpを使おう！

ホッ！ホッ！ホゥ！

プログラミング言語サンタh_shimakawaがやってきたよ！

今日はHapInS Advent Calendar 24日目、今年作った中で一番良い言語をプレゼントしに来たよ！

※ラムダ計算第4回のチューリングマシンの実装が間に合わなさそうだったので、やむを得ずプランBの記事を紹介します。 プランBとはいえ、むしろこっちが本命なくらい個人的には重要な記事ですのでみんな読んでみてください。

BinOpの構文木。メソッド呼び出しのツリーになっています。

はじめに

今回、私が実装した言語の中で最もイケてるプログラミング言語BinOp(びんおーぴー)を紹介します。 本当は自画自賛とか好きではないのですが、自分の作った言語の魅力を語っていきます。

由来

BinOpの命名は、2項演算子を意味するBINary OPeratorに由来しています。 BinOpはその由来のとおり、二項演算子にフォーカスした言語です。 どの辺がフォーカスしているのかは以下の説明で明らかにします。

BinOpのソースコード

BinOpは以下のような見た目のプログラミング言語です。

"== Dogクラスを宣言してインスタンスを3つ生成する =="
Dog := fun(name,age,
  dogClass := Object.clone();
  dogClass.name = name;
  dogClass.age = age;
  dogClass.greet = fun("I'm " + this.name);
  dogClass);

dog1 := Dog("Foo", 10);
dog2 := dog1.clone(); "直接オブジェクトをクローンしてもいい";
dog2.name = "Bar";  "objectのslotへの代入はクローン元に影響しない";
dog2.age = 6;
dog3 := Dog("Baz", 1);

dog1.greet().print(); "=> I'm Fooと表示";
dog2.greet().print(); "=> I'm Barと表示";
dog3.greet().print(); "=> I'm Bazと表示";

どうですか？

普通の言語しか知らないと結構衝撃を受けるかもしれません。

• "class"がないのにクラス作ってる。ってかcloneって何？
• 引数と関数の本体がカンマで区切られてる？
• 関数にreturnがない。何が返っている？
• ""は文字列なの？コメントなの？

さあ、この不思議な言語に興味を持っていただけたでしょうか？

BinOpの特徴

特徴１　関数型言語とプロトタイプオブジェクト指向型言語の両方の特徴を持つ、動的型付けの言語

• Io言語ライクなプロトタイプベースのオブジェクト指向言語です。
• 再帰やリスト構造をベースにした関数型言語っぽい言語でもあります。
• 変数に型はありませんが、値に型は一応あります。

特徴２　２項演算子を文法の中心に置いた、普通のようで普通じゃない見た目の言語

• 「+, -, *, /, =, ==」のようなよく見る演算子のほか、普通の言語では２項演算子にならない「;」「,」といった記号も２項演算子として解釈されます。
• 反対に２項演算子ではない文法要素は極力除いています。
  • 具体的にはコメント、単項演算子（+1, -1, !1, x++）や配列アクセス（ary[1]）などがありません。（そもそも配列が存在しませんが‥）
  • また文法要素ではありませんが、私の言語実装によくある「再帰あるならループ命令いらなくね？」によりfor/while文もありません。(全部まじめに作るのだるいし、再帰かっこいいじゃん！)※2024-05-05追記　ステキな実装を思いついたのでdoWhileのみ追加実装されました。
  • 結果として構文的に２項演算子でないものは、数値、文字列、カッコ、変数を含むレシーバのないメッセージぐらいしかありません。(改めて書くと結構ありますね‥)
• もしかしたらなんですが、2項演算子にフォーカスした言語って世界でも稀なんじゃないでしょうかね？ググってませんけど。

特徴３　文法はシンプルだからパーザの実装コストもコンパクト

• Io言語の文法はシンプルなルールでできています。なのでパーザ（構文解析機）が比較的シンプルです。
  • 言語実装経験者でないと伝わりにくいかもですが、プログラムでa=1+2*3-4>5-2を(a=(((1+(2*3))-4)>(5-2)))と適切に解釈させるのはそれなりに大変なんです。
  • そのうえで他の文法要素も取り入れるとなると複雑さが爆発します。
• 私は言語処理系の各要素の中で最もパーザが複雑だと考えています。なのでここの実装コストを削減できたことはそれなりに意義があることだと思っています。
• ソースコードはこちらです。
  • 非常に濃厚なコードですが、短い行にまとまっています。でも二項演算子に特化しているだけあって二項演算子の追加ならいくらでも簡単にできるようになっています。

特徴4　シンプルな文法の上に豊かな表現力

• BinOpでは、文法的な実装コストの圧縮（手抜き）があっても豊かな表現力をもっています。
• 文法的には「慣れればまあ分かる程度の見た目」をしています（よね？）。その上でマクロやユーザ定義2項演算子などなど強力な機能を持っています。
• また文法要素を加えることなく、オブジェクト指向プログラミングも実装しています
• このような実装方法は他の言語実装を目指す人にも大きな参考になるかもです。

特徴5　実用性皆無

• 初心者が覚えやすいわけでもなく、難しい問題をスマートに解けるわけでもありません。純粋に私の「実装したい欲」を満たすために作られています。
• なお、BinOpはTypescriptで作られていますのでインタープリタon インタープリタで実行速度もでません。

作った背景

1. 何かオブジェクト指向言語を作りたい。一番シンプルそうなIo言語を参考にしよう。
2. ２項演算子の実装すごく大変。疲れきる。
3. そうだ文法要素の大半を２項演算子にすれば簡単にできるじゃん！
4. ついでに単項演算子とかいらないもの全部捨ててしまえ！
5. BinOpの誕生！　

2022年の11月ごろに構想がスタートして2023年2月ごろには大まかな機能が完成しています。

インストール方法

• 以下のリンクを開き、git clone でインストールできます。
  • https://github.com/hoznas/binop-interpriter
• ts-nodeで実行してください。

チュートリアル

真偽値・数値・文字列

真偽値

真偽値はnilだけが偽で、それ以外は全て真です。

nil; "これだけが唯一の偽";
0; 1; ""; "hello"; "これらはすべて真です";
0>1;  "比較演算子は、偽の場合nilを返し、正の場合非nilを返します"

数値

数値は0と整数だけ即値で表現できます。 それ以外の負数や少数は自分で作る必要があります。 数値の精度は実装言語のtypescriptに準拠します。

0; 1; 2; 10; "全て有効な数値です";
0-1; "負数は計算で作る";
1/4; "少数も自分で作る"

文字列

ダブルクォーテーションで囲まれた範囲が文字列になります。 連結や部分文字列の取得もできます。

"これは文字列です";
"ab" + "cd"; "=> abcd"
"ab" + 12; "=> ab12"
"abcd" / 2; "=> ab"
"abcd" % 2; "=> cd"

コメント

BinOpにコメント機能はありません。 「評価されない位置」に適切に文字列をおいてください。 特にifや関数、マクロの内部に置く時は気をつけてください。

"これは文字列です。値を使わないならコメントにもなります。"

文法

変数

変数は:=による代入を行うことで宣言ができます。 値の変更は=を使用してください。

v := 1; "変数の宣言"
v = v + 5; "再代入"
v.print(); "=> 6と表示"

２項演算子

定義されている2項演算子は以下の通りです。 すべて左結合で、上の方(数字の小さい方)が結合が強いです。

優先順位	演算子
0	.
1	* / %
2	+ -
3	< > <= >=
4	== !=
5	&& ||
6	:= =
7	ユーザ定義2項演算子(後述)
8	;
9	,

上記のルールに従って以下のプログラムが適切な優先順位で計算が実行されます。

n := 1 + (2 - 3) * 4; "n.:=(1.+((2.-(3)).*(4)))と解釈される"
n.print(); "=> -3と表示"

セミコロンと改行

セミコロンと改行は、どちらも順次処理を行う2項演算子「;」です。 BinOpが持つ、最も特筆すべき特徴です。

• a;b は、a.;(b)と解釈され、a、bの順番に評価が行われます。bを評価した値が返却されます。
• 改行は、セミコロンとして読み替えられます。
• 連続したセミコロンや過剰なセミコロンは適切に読み飛ばされます。
• この仕組みによって後述の「関数の最後に評価した値が戻り値である」が実現しています。

"first".print();"second".print(); "=> first,secondの順に表示"

以下は１行目にセミコロンと改行が連続し、２行目には不要な位置にセミコロンがあるのですが、適切に読み飛ばされ、1,2の順に表示が行われます。 結果的にはJavascriptやRubyのようなあってもなくてもいいようなセミコロンにも見えますが、プログラムの順次実行という大事な仕事をセミコロンが担っています。

1.print();
2.print();

条件分岐

条件分岐はifを使います。 ifは"式"として扱われ、最後に評価した値を返します。 なお、最後に評価した値を返すのはBinOp全体の特徴です。

※ 2024-05-05追記 条件分岐は、組み込み関数ではなく組み込みメソッドになりました。 オブジェクトがnilであれば偽へ、それ以外であれば真への分岐が行われます。

条件分岐すらもオブジェクト指向になっているってステキですね！

(n==7).if(
  "seven",
  "not seven"
).print(); "=> not sevenと表示"

関数

関数

関数はfunで生成します。funは引数を複数受け付け、fun(arg1,arg2,.., functionBody)のように、最後の引数を関数本体とします。 なお、funの引数を区切る,も二項演算子なので、演算子の優先順位に従って、関数本体ではセミコロンによる複数行のプログラムを記述できます。 returnは存在せず、関数の最後に実行した値が、戻り値となります。

addPrint := fun(a,b,
  result := a+b;
  result.print();
  "最後に評価した値が戻り値になる";
  result);
addPrint(3,6); "=> 9と表示"

繰り返し処理

ループ表現は無く、再帰のみで繰り返し処理を行います。 BinOpインタプリタは「末尾再帰の最適化」が実装されていないため、深い再帰を行うとスタックオーバーフローで落ちます。

factorial := fun(n,
  (n>1).if(
    n * factorial(n-1),
    1))
factorial(4).print(); "=> 24と表示(4! = 24)

※2024-05-05追記 関数オブジェクトfunに、組み込みメソッドdoWhileを実装しました。 以下のように使用することでループを実行できます。

v:=0;
z:=fun(v<5).doWhile(
  v.print();
  v=v+1
);               "=> 0,1,2,3,4と表示される。zには最後に評価された5が代入される。"

クロージャ

BinOpはクロージャをサポートします。 関数外部の変数にアクセスできます。

makeCounter := fun(n:=0;fun(n=n+1))
counter := makeCounter()
counter().print(); "=> 1が表示される"
counter().print(); "=> 2が表示される"

データ構造（オブジェクト・リスト）

オブジェクトの作成とクローン

• BinOpはプロトタイプ型のオブジェクト指向言語でもあります。
• 余談ですが、BinOpではfoo.say("hello")は、fooオブジェクトにsay("hello")というメッセージを送るという意味を持ちます。メッセージング主体の言語にしたいのです。

Dog := fun(name,age,
  dogClass := Object.clone()
  "objectのプロパティへの代入は=と:=のどちらを使っても構わない"
  dogClass.name = name
  dogClass.age := age
  dogClass.greet = fun("I'm " + this.name)
  dogClass)

dog1 := Dog("Foo", 10)
dog2 := dog1.clone(); "直接オブジェクトをクローンしてもいい"
dog2.name = "Bar";  "インスタンスのslotへの代入はクローン元に影響しない"
dog2.age = 6
dog3 := Dog("Baz", 1)

dog1.greet().print(); "=> I'm Fooと表示"
dog2.greet().print(); "=> I'm Barと表示"
dog3.greet().print(); "=> I'm Bazと表示"

• Objectは組み込みの定数で、あらゆるクラス/オブジェクトの基底の存在です。
• オブジェクトはcloneでオブジェクトをコピーできます。
• cloneで生成されたオブジェクトはclone元への参照を持っている以外は空のオブジェクトです。自身に定義されていないメッセージを受け取った時はclone元を辿ってメッセージに応答します。
  • このことで「クラスからインスタンスを生成」「オブジェクトのcloneで同じ振る舞いのオブジェクトを複製」ができるようになります。

ポリモーフィズム

• BinOpは変数に型がないので、クラスの継承関係に関係なく、当たり前にメソッドを呼び出すことができます。

継承

以下のように継承関係を記載することで、基底クラスのメソッドを呼び出すことができます。

BaseClass := Object.clone()
BaseClass.func := fun(1+2)
SubClass := BaseClass.clone()
instance := SubClass.clone()
instance.func().print(); "=> 3と表示"

カプセル化

• カプセル化は、クロージャの機能を使うとクラスの内部の変数を隠蔽できます。

リスト構造

組み込みのデータ構造はObjectしかありませんので、リスト構造を定義する必要があります。 配列のようなデータ構造を定義できます。

Cell := fun(a,b,
    cellClass := Object.clone()
    cellClass.head := a
    cellClass.tail := b
    cellClass);
list := fun(i,n,
    (i<n).if(
        Cell(i,list(i+1,n)),
        nil));
sum := fun(lst,
    lst.if(
        lst.head + sum(lst.tail),
        0));

numbers := list(0,5);
numbers.print(); "=> 0,1,2,3,4を表すリストを表示";
sum(numbers).print(); "=> 10を表示"

メッセージング

メッセージとは

実はBinOpの全てのプログラムはメッセージになっています。 二項演算子であっても、例えば1+2は1.+(2)と評価され、1をレシーバに+(2)というメッセージが送られていると解釈されます。 また、1.+(2)のレシーバである1もメッセージです。

メッセージの生成

message関数でメッセージを生成し、evalで評価を行うことができます。 驚くべきことに生成されたメッセージはBinOpプログラムそのものです。 次項で紹介するevalと組み合わせると強力な機能になります。

message関数の第1引数はオプションで、以下の4種類があります。 オプション文字列の指定により、引数のバインドを調整できます。 ちょっと複雑で、あとで直すかもです。

binding option	説明
"__"	receiverなし、呼び出しなし
"_@"	receiverなし、呼び出しあり
"@_"	receiverあり、呼び出しなし
"@@"	receiverあり、呼び出しあり

以下のメッセージが生成されます。

message("__", "method"); "=> method"
message("_@", "method"); "=> method()"
message("_@", "method", 1, 2, 3); "=> method(1,2,3)"
message("@_", receiver, "method"); "=> receiver.method"
message("@@", receiver, "method"); "=> receiver.method()"
message("@@", receiver, "method", 1, 2, 3); "=> receiver.method(1,2,3)"

メッセージの評価

生成されたメッセージはevalによって評価(実行)することができます。 この機能によってメタプログラミングという「プログラムが作ったプログラムをプログラムが実行できる」というわけのわからないことができます。 賢い人が使うとすごいことができるようです。

evalNode(message("@@",5,"+",7)); "=> 12"
evalStr("5+7"); "=> 12"; "ついでに文字列からプログラムを直接評価する関数も作りました。"

自画自賛は苦手ですが、 実装コストを思いっきり削減したわりに野心的な機能を取り込んでいると思いませんか？

その他の機能

ユーザ定義2項演算子

ほとんどが２項演算子であるBinOpでは、以下のメソッド呼び出しの場合に限りますが、 ユーザ定義の２項演算子として表現できます。

o := Object.clone()
o.setValue = fun(x,this.value = x)
o setValue 123; "o.setValue(123)と解釈される"
o.value.print(); "=> 123と表示"

２項演算子を自由に定義できるのは、Swift,Scala,Haskellぐらい割と珍しい機能です。 繰り返しますが、私は自画自賛は苦手だけど、コンパクトな構文解析機なのによく出来てますね！

マクロ

• BinOpには簡易的なマクロ機能があります。
• 引数の評価を自分のタイミングで行いたい時に使える関数のようなものです。
• 参考にしたSchemeと違い、コンパイル時に展開せず実行時に展開するので非常に実行効率が悪いです。
• 文法的にスッキリできそうだなという時に使ってください。

while := macro(cond, block,
  f:=fun(cond, block,
    evalNode(cond).if(
      evalNode(block);
      f(cond, block),
      nil));
  f(cond, block))


"0,1,2,3,4,5,6,7,8,9と、改行しながら表示"
x := 0
while(x<10,
  x.print();
  x=x+1)

ホントマジで自画自賛が苦手なのですが、 whileを実装できるとか、他の言語ではプリミティブな機能を自分で作れるなんて結構すごいですよね！

これからやりたいこと

BinOpの開発は作者の技術力の限界を超えたので、現在開発はストップしています。 少しづつ以下の勉強を続けていました。

• 末尾再起の最適化
  • どれだけ再帰しても落ちないようにしたい。
  • そのためにCPS（継続渡しスタイル）を勉強中。
• ネイティブ環境orVMでの実行
  • コンパイルできたらいいと思い、Clafting interpritersを勉強中。
• Smalltalk系の言語を調査して、もっとプロトタイプベースのオブジェクト指向言語に寄せる。
  • 言語体系を整理して、もっと「メッセージを送り合ってプログラミングしてる感」を出したい。

趣味プログラミングはモチベーション維持が大事

• プログラミング言語作成に限らず、趣味プログラミングはその実用性を無視できることが多いので、あらゆる面で手を抜くことができます。
• 自分のやりたいことだけ、楽しいことだけ書くようにすれば、自然とプログラミングが楽しくなりモチベーションを維持できるようになります。
• BinOpにおいてはそれが「二項演算子以外の文法要素の削除」などであり、不要な実装とデバッグコストを回避できました。
• その結果高いモチベーションを維持できたため、evalやオブジェクト指向やユーザ定義二項演算子、マクロなど、より高度な言語機能を実装できました。
• 手抜きというとイメージが悪いですが、難しいプログラミングには挫折がつきもの。趣味プログラミングで一番大事なモチベーションを維持するため必要な「選択と集中」だと考えて趣味プログラミングをしてみてはいかがでしょうか？（え、当然やってるよね？趣味プログラミング？）

じゃあ良い子のみんな、また来年のプレゼントも楽しみに待っててね〜