プログラミング言語を書きました。方法もここにあります。

過去6か月間、私はPineconeと呼ばれるプログラミング言語に取り組んでいます。まだ成熟しているとは言いませんが、次のような使いやすい機能が既に備わっています。

  • 変数
  • 関数
  • ユーザー定義の構造

興味がある場合は、パインコーンのランディングページまたはそのGitHubリポジトリをご覧ください。

私は専門家ではありません。このプロジェクトを始めたとき、私は自分が何をしていたのか見当がつかなかったのですが、まだわかりません。言語の作成に関する授業はゼロで、オンラインでそれについて少しだけ読んだのですが、与えられたアドバイスの多くは従いませんでした。

それでも、私はまだ完全に新しい言語を作りました。そしてそれは動作します。だから私は何か正しいことをしているに違いない。

この投稿では、内部を掘り下げて、ソースコードを魔法に変換するために使用するパイプラインPinecone(および他のプログラミング言語)を紹介します。

また、これまでに行ったトレードオフのいくつかと、私が決定した理由についても触れます。

これは決してプログラミング言語の作成に関する完全なチュートリアルではありませんが、言語開発に興味がある場合は出発点として適しています。

入門

「どこから始めればいいのかまったくわからない」というのは、他の開発者に自分が言語を書いていると言ったときによく耳にするものです。それがあなたの反応である場合、新しい言語を開始するときに行われるいくつかの初期決定と実行されるステップを今から見ていきます。

コンパイル済みvs解釈済み

コンパイルされた言語と解釈された言語の2つの主要なタイプがあります。

  • コンパイラは、プログラムが実行するすべてのことを把握し、それを「マシンコード」(コンピュータが非常に高速に実行できる形式)に変換し、後で実行するために保存します。
  • インタープリターは、ソースコードを1行ずつステップ実行し、その進行状況を把握します。

技術的には、どの言語でもコンパイルまたは解釈できますが、通常は特定の言語に対してどちらか一方の方が理にかなっています。一般的に、解釈はより柔軟になる傾向がありますが、コンパイルはより高いパフォーマンスを持つ傾向があります。しかし、これは非常に複雑なトピックのほんの一部に過ぎません。

私はパフォーマンスを非常に重視しており、高いパフォーマンスとシンプルさを重視したプログラミング言語が不足しているのを見て、Pinecone用にコンパイルしました。

これは、多くの言語設計の決定が影響を受けるため、早期に行う重要な決定でした(たとえば、静的型付けはコンパイルされた言語にとって大きな利点ですが、解釈された言語にとってはそれほどではありません)。

Pineconeはコンパイルを念頭に置いて設計されているという事実にもかかわらず、しばらくの間それを実行する唯一の方法であった完全に機能するインタープリターがあります。これにはいくつかの理由がありますが、これについては後で説明します。

言語の選択

私はそれが少しメタであることを知っていますが、プログラミング言語はそれ自体がプログラムなので、あなたはそれを言語で書く必要があります。 C ++を選択したのは、そのパフォーマンスと大きな機能セットのためです。また、私は実際にC ++での作業を楽しんでいます。

インタープリター言語を作成している場合は、インタープリターの言語とインタープリターを解釈しているインタープリターのパフォーマンスが低下するため、コンパイル済みの言語(C、C ++、Swiftなど)で作成するのは非常に理にかなっています。

コンパイルする場合は、遅い言語(PythonやJavaScriptなど)を使用する方が適しています。コンパイル時間は悪いかもしれませんが、私の意見では、それは実行時間が悪いほど大したことではありません。

高レベル設計

プログラミング言語は通常、パイプラインとして構造化されます。つまり、いくつかの段階があります。各ステージには、特定の明確に定義された方法でフォーマットされたデータがあります。また、各ステージから次のステージにデータを変換する機能も備えています。

最初の段階は、入力ソースファイル全体を含む文字列です。最終段階は実行可能なものです。これは、Pineconeのパイプラインを段階的に進めるにつれて明らかになります。

レキシン

ほとんどのプログラミング言語の最初のステップは、字句解析またはトークン化です。 「Lex」は字句解析の略で、テキストの束をトークンに分割するための非常に派手な言葉です。 「トケナイザー」という言葉はもっと理にかなっていますが、「レクサー」はとにかくそれを使うと言ってとても楽しいです。

トークン

トークンは、言語の小さな単位です。トークンは、変数または関数名(識別子とも呼ばれます)、演算子、または数字です。

レクサーのタスク

字句解析プログラムは、ソースコードに相当するファイル全体を含む文字列を取得し、すべてのトークンを含むリストを吐き出すことになっています。

パイプラインの将来の段階では元のソースコードを参照しないため、レクサーは必要なすべての情報を生成する必要があります。この比較的厳密なパイプライン形式の理由は、レクサーがコメントの削除や、何かが数字または識別子であるかどうかの検出などのタスクを実行する可能性があるためです。両方の言語をレクサー内にロックしたままにしておくと、残りの言語を記述するときにこれらのルールを考慮する必要がなくなり、このタイプの構文をすべて1か所で変更できます。

フレックス

私が言語を始めた日、私が最初に書いたのはシンプルなレクサーでした。その後すぐに、おそらくレキシングを簡単にし、バグを減らすツールについて学び始めました。

そのようなツールの主なものは、レクサーを生成するプログラムであるFlexです。言語の文法を記述する特別な構文を持つファイルをそれに与えます。それから、文字列を字句化し、必要な出力を生成するCプログラムを生成します。

私の判断

とりあえず書いた字句解析器を保持することにしました。最終的に、Flexを使用することの大きな利点はありませんでした。少なくとも依存関係の追加とビルドプロセスの複雑化を正当化するには十分ではありませんでした。

私の字句解析器は数百行しかないので、めったにトラブルを起こすことはありません。独自のレクサーをローリングすると、複数のファイルを編集せずに言語に演算子を追加できるなど、柔軟性が向上します。

解析

パイプラインの2番目のステージはパーサーです。パーサーは、トークンのリストをノードのツリーに変換します。このタイプのデータの保存に使用されるツリーは、抽象構文ツリー(AST)と呼ばれます。少なくともPineconeでは、ASTには型に関する情報や識別子はありません。単純に構造化されたトークンです。

パーサーの職務

パーサーは、レクサーが生成するトークンの順序付きリストに構造を追加します。あいまいさを防ぐには、パーサーは括弧と操作の順序を考慮する必要があります。単純に演算子を解析することはそれほど難しくありませんが、より多くの言語構成要素が追加されるにつれて、解析は非常に複雑になる可能性があります。

バイソン

繰り返しになりますが、サードパーティの図書館を含む決定を下しました。主な解析ライブラリはBisonです。 BisonはFlexとよく似ています。文法情報を保存するカスタム形式でファイルを作成すると、Bisonはそれを使用して解析を行うCプログラムを生成します。私はBisonの使用を選択しませんでした。

カスタムが優れている理由

字句解析器を使用した場合、自分のコードを使用する決定はかなり明白でした。字句解析プログラムは、私自身の「左パッド」を作成しないのと同じくらいばかげていると感じた、ごく簡単なプログラムです。

パーサーでは、それは別の問題です。現在、私のPineconeパーサーの長さは750行です。最初の2つはゴミだったので、そのうちの3つを書きました。

私はもともといくつかの理由で決定を下しましたが、完全にスムーズにはいかなかったものの、そのほとんどは真実です。主なものは次のとおりです。

  • ワークフローのコンテキストスイッチングを最小限に抑える:C ++とPineconeの間のコンテキストスイッチングは、Bisonの文法をスローせずに十分に悪い
  • ビルドをシンプルに保つ:文法が変更されるたびに、ビルドの前にBisonを実行する必要があります。これは自動化できますが、ビルドシステムを切り替えるときに苦痛になります。
  • 私はクールなたわごとを構築するのが好きです。私はそれが簡単だと思ったので、松ぼっくりを作りませんでした。カスタムパーサーは簡単ではないかもしれませんが、完全に実行可能です。

当初、実行可能な道を進んでいるかどうかは完全にはわかりませんでしたが、ウォルターブライト(C ++の初期バージョンの開発者であり、D言語の作成者)が言わなければならないことに自信がありましたトピック:

「もう少し物議をかもしますが、レクサーやパーサージェネレーターや他のいわゆる「コンパイラコンパイラ」に時間を浪費することはありません。時間の無駄です。レクサーとパーサーを書くことは、コンパイラーを書く仕事のごく一部です。ジェネレーターを使用すると、1つずつ手作業で作成するのと同じくらいの時間がかかり、ジェネレーターと結婚します(コンパイラーを新しいプラットフォームに移植するときに重要です)。また、ジェネレーターは、お粗末なエラーメッセージを送信するという不幸な評判も持っています。」

アクションツリー

現在、一般的で普遍的な用語の領域を離れました。または、少なくとも用語の意味がわかりません。私の理解では、「アクションツリー」と呼ぶものは、LLVMのIR(中間表現)に最も似ています。

アクションツリーと抽象構文ツリーの間には、微妙ではありますが非常に大きな違いがあります。それらの間には違いがあるはずだと理解するのにかなり時間がかかりました(パーサーの書き換えの必要性に貢献しました)。

アクションツリーとAST

簡単に言えば、アクションツリーはコンテキストを持つASTです。そのコンテキストは、関数が返す型などの情報であるか、変数が使用される2つの場所が実際に同じ変数を使用しているという情報です。このすべてのコンテキストを把握して記憶する必要があるため、アクションツリーを生成するコードには、多くのネームスペースルックアップテーブルやその他のものが必要です。

アクションツリーの実行

アクションツリーを作成したら、コードの実行は簡単です。各アクションノードには、「入力」という関数があり、入力を受け取り、アクションの実行(サブアクションの呼び出しを含む)を実行し、アクションの出力を返します。これが実際のインタープリターです。

コンパイルオプション

「でも待って!」と言うのを聞きました。「パインコーンはコンパイルされたものではないのですか?」はい、そうです。しかし、コンパイルは解釈よりも困難です。いくつかの可能なアプローチがあります。

自分のコンパイラをビルド

これは、最初は良いアイデアのように思えました。私は自分で物を作るのが大好きで、組み立てが上手になるための言い訳が必要です。

残念ながら、ポータブルコンパイラの記述は、各言語要素のマシンコードの記述ほど簡単ではありません。アーキテクチャとオペレーティングシステムの数が多いため、個人がクロスプラットフォームコンパイラバックエンドを作成することは実用的ではありません。

Swift、Rust、およびClangの背後にあるチームでさえ、すべて自分でそれを気にしたくないので、代わりに彼らはすべて使用します...

LLVM

LLVMは、コンパイラツールのコレクションです。これは基本的に、言語をコンパイル済みの実行可能バイナリに変換するライブラリです。完璧な選択のように思えたので、私はすぐに飛び込みました。悲しいことに、私は水の深さを確認せず、すぐにdr死しました。

LLVMは、アセンブリ言語ではありませんが、巨大で複雑なライブラリです。使用することは不可能ではなく、優れたチュートリアルが用意されていますが、Pineconeコンパイラを完全に実装する準備が整う前に、ある程度練習する必要があることに気付きました。

トランスパイリング

ある種のコンパイルされた松ぼっくりが欲しくて、それが速く欲しかったので、私は仕事をすることができるとわかっていた1つの方法に移りました:トランスピリング。

PineconeをC ++トランスパイラーに書き込み、GCCで出力ソースを自動的にコンパイルする機能を追加しました。現在、これはほとんどすべてのPineconeプログラムで機能します(ただし、それを破るエッジケースがいくつかあります)。これは特に移植性のある、またはスケーラブルなソリューションではありませんが、当面は機能します。

未来

私がPineconeの開発を続けていると仮定すると、遅かれ早かれLLVMのコンパイルサポートが得られます。どれだけ作業しても問題ないと思います。トランスパイラーが完全に安定することは決してなく、LLVMの利点は数多くあります。 LLVMでいくつかのサンプルプロジェクトを作成し、それを理解する時間があるときだけです。

それまでは、インタプリタは些細なプログラムに最適であり、C ++トランスパイルは、より多くのパフォーマンスを必要とするほとんどのものに対応しています。

結論

プログラミング言語があなたにとってもう少し神秘的ではないことを願っています。自分で作成したい場合は、強くお勧めします。理解するための実装の詳細は山ほどありますが、ここでの概要で十分に理解できます。

開始するための高レベルのアドバイスを次に示します(自分が何をしているかはよくわからないので、一粒の塩を使ってください)。

  • 疑わしい場合は、解釈してください。通訳された言語は、一般的に設計、構築、学習が容易です。あなたがそれをやりたいことを知っていれば、コンパイルされたものを書くことを落胆させませんが、あなたがフェンスにいるなら、私は解釈しに行きます。
  • レクサーとパーサーに関しては、何でも好きなことをしてください。独自の記述には賛否両論があります。最終的に、デザインを考えて、すべてを適切な方法で実装する場合、それは重要ではありません。
  • 私が終わったパイプラインから学びましょう。私が現在持っているパイプラインの設計には多くの試行錯誤がありました。 AST、アクションツリーに変わるAST、およびその他のひどいアイデアを排除しようとしました。このパイプラインは機能するため、本当に良いアイデアがない限り変更しないでください。
  • 複雑な汎用言語を実装する時間や動機がない場合は、Brainfuckなどの難解な言語を実装してみてください。これらのインタプリタは、数百行ほどの短いものになる場合があります。

Pineconeの開発に関しては、後悔はほとんどありません。途中でいくつかの悪い選択をしましたが、そのようなミスの影響を受けるコードのほとんどを書き直しました。

現在、松ぼっくりは十分に機能する状態にあり、簡単に改善できます。松ぼっくりを書くことは、私にとって非常に教育的で楽しい経験であり、まだ始まったばかりです。