私はプログラミング言語を書きました。これがあなたもできる方法です。

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

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

興味がある場合は、PineconeのランディングページまたはGitHubリポジトリを確認してください。

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

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

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

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

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

入門

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

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

言語には、コンパイルとインタープリターの2つの主要なタイプがあります。

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

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

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

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

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

言語の選択

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

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

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

高レベルの設計

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

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

字句解析

ほとんどのプログラミング言語の最初のステップは、字句解析またはトークン化です。「Lex」は字句解析の略で、大量のテキストをトークンに分割するための非常に凝った単語です。「tokenizer」という言葉の方がはるかに理にかなっていますが、「lexer」という言葉はとても楽しいので、とにかく使っています。

トークン

トークンは言語の小さな単位です。トークンは、変数または関数名(別名、識別子)、演算子、または数値の場合があります。

レクサーのタスク

レクサーは、ファイル全体に相当するソースコードを含む文字列を取り込み、すべてのトークンを含むリストを吐き出すことになっています。

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

フレックス

私が言語を始めた日、私が最初に書いたのは単純な字句解析器でした。その後すぐに、字句解析をより簡単にし、バグを少なくするツールについて学び始めました。

そのような主なツールは、レクサーを生成するプログラムであるFlexです。言語の文法を説明するための特別な構文を持つファイルを指定します。それから、文字列を字句解析して目的の出力を生成するCプログラムを生成します。

私の決定

とりあえず書いた字句解析器をそのままにしておくことにしました。結局、Flexを使用することの大きなメリットはわかりませんでした。少なくとも、依存関係を追加してビルドプロセスを複雑にすることを正当化するには十分ではありませんでした。

私のレクサーは数百行の長さで、問題が発生することはめったにありません。自分のレクサーをローリングすると、複数のファイルを編集せずに言語に演算子を追加できるなど、柔軟性も向上します。

構文解析

パイプラインの第2段階はパーサーです。パーサーは、トークンのリストをノードのツリーに変換します。このタイプのデータを格納するために使用されるツリーは、抽象構文ツリー(AST)と呼ばれます。少なくともPineconeでは、ASTにはタイプやどの識別子がどれであるかについての情報はありません。単純に構造化されたトークンです。

パーサーの義務

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

バイソン

繰り返しになりますが、サードパーティのライブラリを使用するという決定がありました。主な解析ライブラリはBisonです。BisonはFlexとよく似ています。文法情報を格納するカスタム形式でファイルを作成すると、Bisonはそれを使用して、解析を実行するCプログラムを生成します。私はバイソンを使うことを選びませんでした。

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

レクサーを使用すると、自分のコードを使用するという決定はかなり明白でした。レクサーは非常に些細なプログラムなので、自分で書いていないと、自分の「左パッド」を書かないのと同じくらいばかげていると感じました。

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

私はもともといくつかの理由で決断を下しましたが、完全にスムーズに進んだわけではありませんが、ほとんどの理由が当てはまります。主なものは次のとおりです。

  • ワークフローでのコンテキスト切り替えを最小限に抑える:C ++とPineconeの間のコンテキスト切り替えは、Bisonの文法文法を投入しなければ十分に悪いです
  • ビルドをシンプルに保つ:文法が変わるたびに、ビルドの前にBisonを実行する必要があります。これは自動化できますが、ビルドシステムを切り替えるときに面倒になります。
  • かっこいいものを作るのが好きです。簡単だと思ったのでPineconeを作成しなかったのに、自分でできるのになぜ中心的な役割を委任するのでしょうか。カスタムパーサーは簡単ではないかもしれませんが、完全に実行可能です。

最初は、実行可能な道を進んでいるかどうかは完全にはわかりませんでしたが、Walter Bright(C ++の初期バージョンの開発者であり、D言語の作成者)がトピック:

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

アクションツリー

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

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

アクションツリーvsAST

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

アクションツリーの実行

アクションツリーができたら、コードの実行は簡単です。各アクションノードには、何らかの入力を受け取り、アクションが必要なこと(サブアクションの呼び出しを含む)を実行し、アクションの出力を返す関数 'execute'があります。これが実際の通訳です。

コンパイルオプション

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

独自のコンパイラを構築する

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

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

Swift、Rust、Clangの背後にあるチームでさえ、すべてを自分たちで気にかけたくないので、代わりにすべてを使用しています…

LLVM

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

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

トランスパイル

ある種のコンパイル済みPineconeが欲しかったのですが、それを高速にしたかったので、仕事ができるとわかっていた1つの方法、つまりトランスパイルに目を向けました。

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

未来

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

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

結論

プログラミング言語をもう少し不思議なものにしたことを願っています。自分で作りたいのなら、ぜひお勧めします。理解すべき実装の詳細はたくさんありますが、ここでの概要はあなたを動かすのに十分なはずです。

始めるための私のハイレベルなアドバイスは次のとおりです(覚えておいてください、私は自分が何をしているのか本当にわからないので、一粒の塩でそれを取ってください):

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

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

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