本稿は 言語実装 Advent Calendar 2019 の 17 日目の記事です。
前書き： そもそも Paraphrase ってどんな言語？
Paraphrase は 2018 年 2 月より開発を開始した Forth 系のプログラミング言語です（飽きもせず 3 年弱ほどボチボチと開発を続けております）。
Paraphrase の特徴は、
- 数値だけでなくリストや無名関数（無名ワード）などもスタックに積める Forth 系の言語です。
- コードを二重大括弧 [[ と ]] で囲めば複数スレッドで並列実行されます（超簡単）。
- スレッド間はチャネルを用いて通信可能：scatter - gather モデルによる並列処理ができます。
並列処理を用いたプログラムは次のように書けます。このプログラムは 2^5-1 から 2^5000-1 までのメルセンヌ数に対し、それらが素数であるか（＝メルセンヌ素数であるか）否かを並列にチェックするものです。prime? や lucas-lehmer-test-fast および calc-and-print-mersenne というのはユーザーが別のところで定義しているワード（関数のようなもの）です。
// ***** check 5...5000 by multi-thread *****
reset-pipes
// メインスレッドとは別のシングルスレッドで実行される部分(scatter 部)
[ 5 5000 for+ i >pipe 2 step next ]
// マルチスレッドで実行される部分(worker 部）
[[
while-pipe
dup prime? if
dup lucas-lehmer-test-fast if >pipe then
then
repeat
]]
// メインスレッドで実行され、情報を集める部分（gather 部）
while-pipe append repeat { < } sort
0 >r {
r> 1+ dup "No=%2d, " putf >r
calc-and-print-mersenne cr
} foreach
リストも使える Forth 系というと、原田康徳さんの Laplas - https://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/41966/1/130_145-156.pdf が有名です。しかし、Paraphrase は並列処理を念頭に、私なりの好みにより、Laplas とは全く独立に、かつ、勝手に設計・実装している言語です（なので、ところによっては Laplas の劣化コピーにすらなっていない部分もあるかと思います）。
Paraphrase という名前ですが、並列＝parallel ということで、para... で始まる名前にしたかったため、このような名前になりました。また、paraphrase には「言い換え」という意味があるため、Forth のプログラムを Paraphrase のプログラムで置き換える、という意味も込めています。
Forth のような語順でプログラミングを行う言語について、近年では concatenative programming language - 連鎖性言語というカテゴリで語られることも多い気がします。しかし、Paraphrase では、「連鎖的に記述できる」という点のみに限らず Forth のもつモード等にも強い影響を受けているため Forth 系という呼び方をしています。
FaceBook のアカウントが必要となりますが、ユーザー会もあります https://www.facebook.com/groups/219684655627070/。Twitter でも情報発信中です https://twitter.com/paraphrase_lang。興味を持った人は参加もしくはフォローをお願いいたします。GitHub の URL は https://github.com/iigura/Paraphrase です。
参考資料（これまでに書いた Qiita の記事）：
- マルチコア対応 Forth 系言語 Paraphrase の紹介
- Forth ユーザーのための Paraphrase 入門
- Paraphrase での条件分岐の書きかた
- Paraphrase での関数定義（ワード定義）の方法
- Paraphrase でのループ処理の書き方
- Paraphrase の言語システム - 値とワードについて
- [ 最短? ] Paraphrase でスターリンソート [ 結構短い ]
並列処理対応の Forth 系言語を作ろうとした経緯
並列処理にも対応する Forth 系言語を作ろう！…と思ったのは、まつもとゆきひろさんの「言語のしくみ」という本を読んだことがきっかけです。これは後ほど詳しく述べるとして、まずは私と Forth との出会いついて書いてみます。
接触篇
ソフトバンクより出版されていたパソコン雑誌 Oh!MZ の1986 年頃の記事にて Forth を知りました。それ以来、いつの日にか自前の Forth インタプリタを作りたいなぁ、と思ってました。
発動篇
月日は流れ、 Forth に対する想いを 30 年ほど燻ぶらせていましたが、2017 年に職場が変わったことをきっかけに、Forth に関する時間を増やすようにしました。当時は Lua で Forth を作るなどしてリハビリしていました。
参考資料：
- 6 行の Lua プログラムで、Forth の内部インタプリタを作る
- 38 行の Lua プログラムで Forth インタプリタを作る（内部インタプリタ 6 行、外部インタプリタ 32 行）
- Lua で書いた Forth 系言語 F/L について:
「言語のしくみ」との出会い
2017 年の恐らく 11 月中旬頃に、まつもとゆきひろさんの「言語のしくみ」を読みました。私自身はプログラミング言語の研究者ではないのですが、上に挙げた F/L という言語を作った結果、当時の私は言語製作についてもっとよく知りたいと思ったのでしょう。
経緯はともかく、この本にて streem という言語を知ります。パイプを使い、並列で処理を行う言語ということを知りました。そこでふと思ったのです、例えば、処理 A の結果を処理 B に渡し、その結果を処理 C に渡すという処理は、C などでは、
C(B(A()));
などと書かれます。一方、シェルではパイプを用いて
A | B | C
などとも書かれます。処理 A, B, C のみに着目すると、
A B C
となり、これは Forth のプログラムと同じになります。
…ということは、例えば A, B, C が並列に処理を行う Forth 系言語を作成すれば、より自然に、かつ、streem と同じ方向性の言語ができるのではないか！？…という妄想が湧き上がってきました（この妄想が正しいかどうかは別として、まあ、兎に角、そんなことを考えてしまいました）。
マルチコア CPU 時代に対応した、並列処理むけ、もしくは並列処理対応の Forth はどのようなものであるべきなのだろうか？そもそも、そのような言語に意味はあるのだろうか？等、様々な考えが脳裏をよぎりました。
自分なりに色々と考えてみたのですが、これはもう、一度作って、実際に使ってみないことには分からないだろうーという考えに至りました。それに、もし、並列処理が簡単に記述できるスクリプト言語ができれば、自分の仕事にも活かせるかも！？…という期待もありました。昔話で恐縮なのですが、実は CUDA 登場以前に、米国でのインターン中に自作の GPGPU フレームワークも作った経験もあります。また、仕事においても必要に迫られて、プログラムの CUDA 化を行い、数百倍の高速化を実現したこともあります。
並列処理は高いパフォーマンスをもたらすこと。そして、GPU でのプログラミングは様々な制約があること＝CPU による並列処理の方が楽しくプログラミングできること等々…これらを勘案しつつ、並列処理対応 Forth 系言語の開発をスタートさせるに至りました（他には、作品としてのソフトウェアを持っていたかった云々という話もありますが、これはまた別の機会に）。
プログラミング言語 Gorth
最初に作成した並列処理対応 Forth 系言語は Gorth という名前でした。Go で記述された Forth なので安直に Gorth と名付けました。これが Paraphrase の直接の祖先になります。
当時、並列処理なら Go 言語！というように、今よりも Go に対する期待は高かったような気がします。あくまでも私の個人的な感想ですが。私もそのように思っていました。なので、並列処理を行うプログラムを書くなら Go で決まりだ！ということで実際に書いてみました。これが 2017 年の 12 月頃の話です。
Gorth の問題点
Go で並列処理対応 Forth 系言語を作ってはみたものパフォーマンスが全く出ませんでした。当時はベンチマークとして Project Euler No.21 を使っていました。これは 10,000 までの友愛数の和を求めるプログラムなのですが、目標としていた Lua よりも 10 倍遅い状況でした（もちろんシングルスレッドの実行速において、です）。
備考：
Project Euler No.21 については、以下に示す yopya さんの解説が分かりやすいです。
Project Euler 21 「友愛数」 https://qiita.com/yopya/items/cca251dc77431359d7cb
もちろん、私の書き方が悪かったんだと思いますが、何が遅いのか、どこがボトルネックなのかが分からない毎日でした。共用体の実装が悪いのだろうか…と暫く悩んでいたりしましたが、どうにも打開策が見つかりませんでした。
まあ、Gorth というイケていない名前が一番いけなかったのかな、とも思いました。名前がイケていないと、プログラムそのものもイケていない、という典型ですね。
そして Paraphrase へ
パフォーマンス向上のためもがきつつ、2018.02.19 に C++ で全てを書き直すことを決意します。その時の開発メモには、次のように記してありました：
当初 Go で実装していた Gorth であったが、パフォーマンスがなかなか向上しないため、遂に C++ での再実装へと舵を切った。お気楽なガベージコレクションや魅惑的な goroutine に別れを告げて、chan なども全て C/C++ で記述しなければならない。果たして全て作りきることができるのであろうか…。目指すは Lua と同等程度の実行速度である。これは先に実装した Gorth の 10 倍程のパフォーマンスを実現することを意味するのであった…。
C++ で書き直したところで、実行速度が向上するという保証も無いなか、結構不安に思いつつ記述言語を変更したことがみてとれますね。
この C++ で記述された Gorth こそが現在の Paraphrase です。もがき続けた結果、今では、一部のプログラムにおいては Lua よりも 30% 程高速に実行できる言語となりました。
新型 Forth 系言語 - Gorth および Paraphrase - を作る際に考えた様々なこと
とにかく高速であること
日本で FORTH が紹介された頃の文献を紐解くと、当時ブームであった BASIC よりも実行速度が速い言語として記事が書かれていました。そんなこともあり、Forth 系言語であるからには、やはりハイパフォーマンスな言語でありたいと思っています。理想はシングルスレッドでの実行においても高速であること。それが叶わないとしても、せめてマルチスレッドによる力技で、既存の言語よりも高速であって欲しい…と思っています。
高速化にあたり、ver. 0.93.0 では局所変数を導入しました。Forth 系では、スタックの上部の値に対し処理を行っていきます。そのため、複雑な処理ではスタックの奥底の方に必要な値があることがあります。もちろん、このような事態に陥ってしまうのは、Forth 系においてはあまりプログラミングが上手でない場合に発生するわけですが、やはりそれなりの規模のプログラムを書く場合や、気楽にコーディングしていると、どうしてもこのような事態に陥ってしまいます。スタックの奥底にある値をスタック上部に移動させる、もしくはコピーする操作も存在しますが、Paraphrase ではスタックに積める値はもはや整数だけではありません。そのため、これらの操作にはより多くの時間が必要となる状況となってしまいます。
Forth でもプログラムとして変数が用意されています。意味が良くわからないかもしれませんが、例えば Forth における変数 X （のようなもの）は、X というワード（関数のようなもの）に関連したメモリに格納されている値をスタックに積む処理として実現されています。つまり、X というのは、格納されている値をスタックに積むサブルーチンのようなもの、として実現されています。これはただ単に変数の値を得たいだけなのに、サブルーチン呼び出しのようなオーバーヘッドが存在することを意味します。この問題を解消するのが ver. 0.93.0 で導入された局所変数です。本機能を活用することにより、Paraphrase のプログラムはさらなる高速化が実現できました。実装に関してはスタックマシン型 VM の上にレジスタマシン型 VM を搭載するという、VM on VM 方式で実現しております（なお、この局所変数の実装に関する簡単な紹介を「Forth 系言語の簡易な最適化手法の一考察：局所変数と VM 内 VM を用いて」というタイトルにて 2019 年度 電気関係学会 東北支部連合大会 http://www.ecei.tohoku.ac.jp/tsjc/program2019/index.html#ses18 にて報告させていただきました）。
実際のところ、プログラムによっては既に述べた Lua (ver. 5.3.4) や Python (ver. 2.7.15) や Ruby (ver. 2.5.1p57) よりも高速に処理できる場合もでてきました。もちろん、シングルスレッドにおける比較です。シングルスレッドでも Paraphrase の方が速いので、並列処理で書いてしまえば、圧倒的に爆速な場合もあります。とはいえ、これらの言語 - Lua, Python, Ruby - は Paraphrase よりも高機能であり、そのため様々なオーバーヘッドが存在します。それらを考慮せず比較するのも乱暴な話です。でもまあ、ある問題に関してはシングルスレッドでも速い。なおかつ並列処理を駆使すればもっと速い。そんな言語があっても良いのではないかと思い、現在に至っています。
Factor 系か Forth 系か問題
Forth 系という言葉は連鎖性言語に含まれる概念だと思っています。であるが故に Paraphrase も必然的に連鎖性言語に属する言語となります。連鎖性言語においては、Factor - https://factorcode.org/ という有名な言語があります。ブレない設計思想を持ち、なかなか美しい言語だと個人的には感じています。当然、Gorth や Paraphrase を設計する時に、その存在は意識しています。
Factor と Forth の大きな違いは、プログラマの思考法への寄り添い方ではないかと感じています。これはあくまでも私の主観であり、印象です。その思想は特に条件分岐処理に表れており、 Factor では
[ true のときの処理 ] [ false のときの処理 ] if
という書き方をします。
Paraphrase では無名ワード（ラムダ）をスタックに積むことができるため、Factor と同様にプログラムを記述できます。実際、同梱されているサンプルの拡張ライブラリ extFactor では、factor 名前空間に if を定義するため、以下のように分岐処理を記述できます（中括弧 { ... } で囲むとラムダを構成し、スタックに積むことができます）：
{ true のときの処理 } { false のときの処理 } factor:if
ラムダをスタックに積む、Factor 式のこの記述方法は、単純な原理原則に従う美しい方法だと思います。しかし、プログラマがプログラムを記述する場合、このような記述順序は素直なものなのでしょうか。もし〜であれば○○を実行し、さもなければ△△を実行する - こんな思考の方が、プログラマの思考順序に近いのではないか、と私は感じます。
Forth が開発された当時、おそらく無名ワードを構成することは困難だったのではないかと思っています。故に無名ワードへのポインタをスタックに積むこともできず、結果として、
IF true のときの処理 ELSE false のときの処理 THEN
という記述方法を用いたのではないかと推測しています。しかし、結果として、この方法はプログラマの思考順序に沿ったものとなったのではないかと感じています。時は経ち、Paraphrase では無名ワードとして処理手順をスタックに積むことができます。それでも、Factor の方法ではなく、Forth と同様に、
if true-part else false-part then
といった記述方式を採用するに至りました。
インタプリタモードでの制御構造の実現
Forth の場合、条件分岐やループなどを対話的に用いることはできません。一方、拡張された Forth だったり、他の Forth 系言語ではこれらの制限は緩和されています。Paraphrase でもそれらの言語と同様、Forth 系であっても対話的に条件分岐やループを気楽に試せる環境を実現したいと思いました。
この思いは Paraphrase の前身の Gorth からあり、if や for+ などの制御構造に関するワードが入力されたら、自動的に無名ワードブロック（ラムダ）の構成を開始するようにしました。厳密に言えば、全てインタプリタモードで完結する訳ではないのですが、ユーザーの体験としてはインタプリタモードで対話的に条件分岐やループが実現できている、と感じられるようにしました。
少し技術的な話をすれば、制御構造に関するワードが入力されると、自動的にコンパイルモードへ遷移し、ラムダの構成が完了し次第このラムダを実行するーという仕組みです。そのためには無名ワード（ラムダ）の実現が必須となります。開発の順序としては、中括弧 { と } で囲めば無名ワードブロックを構築するようにし、その後「いい感じ」に処理するような仕組みを実装していきました。これにより、インタプリタモードでも、より自然な記述ができるようになりました。
どこまで C に似せるべきか問題
C 言語（この表記が気になる人は適当にプログラミング言語 C などと読み替えて下さい）のヒットにより、C 系言語がいくつも作られ、かつ、それらも十分な数のユーザーを確保しているのは周知の事実です。つまり、C に似せると学習コストが低くなる状況が整っているのが現実です。とは言え、思考停止して何でも C からアイデアを持ってきてしまっても良いのか？という問題もあります。
等価演算子
悩んだ末に現在の仕様となったものに、等価演算子があります。等価演算子には、大きく分けると C 系と Basic 系があるかと思われます。C 系は == と !=、Basic 系は = と <> です。C 系の場合、! は否定を表すので != は意味がよく分かる記号であると思います（!== ではないのか？という気もしないではないですが…）。実際 Gorth では Basic 系の演算子を導入していました。しかし、自分自身が使ってみると、ついつい C 系の演算子を使ってしまうので、Paraphrase では C と同様 == や != というワード名を採用することとしました。
C/C++ 風のコメントの実現
Forth ではコメントの開始はワードとなっていますが、コメント終了の判断は、コメント開始ワードの仕事となっています。この仕組を実現するためには、言語処理系に入力された情報を解釈するインタプリタ部分（Forth の文化では、これを外部インタプリタと呼んだりします）と、コメント開始を担うワードが連携しなければなりません。
Gorth では（それを引き継いだ Paraphrase でも）、ワードと外部インタプリタとの結びつききを弱くしたかったため、新しい実行モード「シンボルモード」を追加しました。シンボルモードはイミディエイトモードなワードであってもシンボルとして判断されるモードです。Gorth / Paraphrase では、従来の標準ワードをレベル 0 とし、イミディエイト属性を持つワードをレベル 1、シンボルモード属性を持つワードをレベル 2 とします。シンボルモードでは、レベル 2 のワードのみが実行され、それ以外のワードはシンボルとしてコンパイルされます。
このような仕組みを導入し、コメントはコメントの開始と終了を担うワードにてーつまり、ワード /* と */ という 2 つのワードにてーコメントの開始処理と終了処理を担うことが可能となりました。大雑把に説明すると、ワード /* にて実行モードをシンボルモードに変更し、ワード */ にてコンパイルされたものを全て破棄し以前の実行モードに復帰します（この辺りの話は「Forth 系言語におけるワード用スキャナ API の廃止と即時実行属性の拡張等について」というタイトルにて 情報処理学会のプログラミング研究会における第 121 回プログラミング研究発表会 https://sigpro.ipsj.or.jp/pro2018-3/program/ で発表させて頂きました）。
余談ですが、コメントの開始と終了をワードで記述できるようになったため、ある程度の文芸的プログラミングも簡単に実現可能となりました。例えば、ワード /* の別名として <html> および </code> を、ワード */ の別名として <code> と </html> を定義すると、HTML 文書を Paraphrase のプログラムとして使用できるようになります。そして勿論、ブラウザにて表示すれば HTML で装飾された文書が表示されることとなります。厳密な意味での文芸的プログラミングとは異なるかもしれませんが、こんなことも実現できます。興味を持たれた方は Paraphrase に同梱される簡易な文芸的プログラミング用の拡張ライブラリ extLP を使ってみて頂ければ幸いです。
述語の接尾辞問題（Lisp の文化を横目でみつつ）
その昔、学生時代に Lisp - 正確には Scheme を学んだとき、述語というのもの生びました。条件判断に使う関数で true や false を返すものだったと思います。で、これらの関数名の最後には p を付けるのが慣例になっていると、担当の先生から教えていただきました（p は述語 = predicate の p だそうです）。
Paraphrase でも、各種の判定用ワードが存在します。これらの名前を「〜p」と Lisp 風にするべきか否かで、少し悩みました。単にワード名の話なので、このあたりは単なるこだわりにしか過ぎないのかもしれませんが、兎に角、決めていかないといけません。言語を作って行くというのは、このように、様々な事柄に決断を下していくことなんだなぁ、としみじみと思いました。
Paraphrase は Forth 系ということもあり、ワード名として様々な記号が使用可能です（Forth 系だから云々、というのは正確ではありませんでした。Lisp でも結構自由に関数名に記号を使用することができたと思います）。要は、疑問符も普通に使用できるので述語系には疑問符を接尾辞として使用することにしました（例： empty? とか）。直感的にも分かりやすくなったのではないかと思います。ちなみに Lisp 系だからといって、述語は必ずしも p で終わるものばかりでもなさそうです。疑問符で終わる関数名もあるようです。なので、色々悩んでいたのに何だかなぁ、という気分になったりもしました。
リスト表記に使用する記号をどのようにするか問題
こちらもエイヤっと決める系の話です。Paraphrase にリストを導入するとき、値としてのリストをどのように記述できるようにするべきかーについて既存の言語の調査を行いました。といっても、ものすごく簡単に調査しただけです。当時のメモがあるので、ここに記しておきます。連鎖性言語として PostScript と Joy について、括弧記号の使い方について簡単に調査しました。
PostScript でのリスト表現
PostScript では、大カッコ [ ] で配列を表現し、中括弧 { } は実行可能な配列（実行可能配列）となる…らしいです。実行可能配列は exec ワードで実行可能とのことでした。
Joy
大カッコ [ ] でリストを表現するようです。こんな感じ（だそうです）：
joy: list.joy
[1 2 3] [4 5 6 7] concat
上記のリストを実行すると、リスト [ 1 2 3 4 5 6 7 ] が得られる（みたい）。
参考： An informal tutorial on Joy
Paraphrase でのリスト表現
結局 Paraphrase では Lisp と同様に少括弧 ( … ) でリストを表現するようにしました。この小括弧 ( および ) もワードです。これらのワードが値としてのリスト構築をになっています。
Paraphrase の今後について
つい先日（2019.12.13）に ver. 0.93.0 をリリースしました。ver 0.93.0 の大きな進化としては、
- 局所変数の導入（これによりスタック操作の軽減が実現されます）
- 末尾再帰の最適化
- 高速化：Python や Ruby と、処理速度比較の土俵に上がれるようになった
- 言語処理系におけるワンライナーへの対応
といったところが目玉かと思います。
とはいえ、この言語に何が必要なのか・何が足りていないのかについては、ある程度の大きさのプログラムを書いてみなければ分からないと思っています。なので、ver.0.94 にむけては、例えば mal - Make A Lisp https://github.com/kanaka/mal/blob/master/process/guide.md などを試してみて、プログラミング言語としての機能を充実させていこうと思っています。おそらくデバッグ関係の機能も必要となってくるのではないかと思っています。
言語仕様以外の部分では、各種の文書を作成していかなければなりません。ざっと思いつくだけでも、
- 初学者のためのチュートリアル
- 言語仕様で不足しているところ
- プリミティブ型に関する情報
- 制御構造の実装に関する仕様（ユーザー独自の制御構造の実現には必須）
などがあります。これらが揃う頃には本家としての Web サイトの整備も必要かと思っています。また、今風に考えると、言語を象徴するためのアイコンやロゴマークなども用意しなければなりませんが、それらについては今後の課題として、少しづつ整備していければと思っています。
以上で、2019 年の言語実装 Advent Calender 17 日目の記事を終わります。
このような長文を読んでいただいてありがとうございました。
もしよかったら、イイネと評価していただければ嬉しいです。
少し早いですが、それでは皆さん、メリークリスマス＆良いお年を！