12
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?

More than 3 years have passed since last update.

言語実装Advent Calendar 2020

Day 7

並列処理対応 Forth 系言語 Paraphrase の 2020 年の開発状況

Posted at

※ この文章は 2020 年の言語実装アドベントカレンダー 12 月 7 日目のために書かれたものです。

はじめに

 この記事では 2020 年 1 月から 2020 年 12 月までの、Paraphrase 開発状況をまとめています。なお、現在は Paraphrase ver.0.94 の開発中であり、ここでまとめられた事柄は、おそらく ver.0.94 に反映されることとなります。

実行速度の高速化について

 結論から言えば、現在開発中の次期 Paraphrase はシングルスレッドでも更に高速になっています。作成するプログラムに依存しますが、Python や Ruby よりも高速に処理できる場合もあります(比較対象の Python や Ruby の具体的なバージョン等については後述します)。

 Paraphrase は、並列処理が簡単に記述できる Forth 系言語として開発が始まっています。何のために並列処理に着目しているのかといえば、それは高速な処理を実現するために他なりません。

 並列で処理をすれば、シングルスレッドで処理を行う他のスクリプト言語よりも高速になるのは当たり前(と言われても仕方ありません)です。見方によっては公平な基準ではないと思われるかもしれません。そこで、現在公開中の Paraphrase ver.0.93 ではシングルスレッドでもある程度の速度が出るよう工夫を行っています(スタックマシン型 VM 上にレジスタマシン型 VM を搭載したハイブリッド型 VM とする等)。

現在開発中の次期 Paraphrase ver.0.94 でもこの方向性は維持されており、あるプログラム(注1)においては Python 3.7.2 や Ruby 2.6.3p62 などよりも高速に処理できるような状況が確認されています。

注1:
以下のページを参考にし、同等の Paraphrase 版のコードを作成し、実行速度を比較しました。

【プログラミング言語速度比較】Collatz数列ベンチマークを言語別比較しよー!
https://rheotommy.hatenablog.com/entry/2020/07/18/205343

新たな機能やワードの追加

相互参照のサポート

 Paraphrase には前方参照の機能はありません。これは現在開発中の ver.0.94 でも変わりはありません。しかし、既に参照しているワードの中身を再定義するワード update を追加しましたので、次に示す使用例のように前方のコードにて実装を記述できるようになりました。

使用例:次の例では、hello というワードの実質的な実装を、hello を呼び出すワード test の後に行っています。なお、左端の不等号は Paraphrase インタプリタのプロンプトを示しています(注2)。

注2: 本文書では、ワード定義などでは対話モードを想定せずに記述する場合もあるため、必ずしも左端に不等号が記載されていない場合もあります。

> "hello" : "NOT IMPLEMENTED" .cr ;
  ok.
> "test" ; hello ;
  ok.
> "hello" { "HELLO" .cr } update
  ok.
> test
  HELLO ok.

ワードの仮引数のサポート

 Forth ではワードの引数などはサポートされず、スタックに積んだ値を利用するのが一般的です(なのでカリー化も簡単にできる)。Paraphrase では既にローカル変数もサポートしていますが、今年 1 月の作業にてワードの仮引数機能を追加しました。使用方法はこんな感じです:

"testXY" :
    ( x y ) >param    // x と y という仮引数を定義
    "x=" . `x , .cr   // x の値を表示
    "y=" . `y , .cr
; 

使い方は、

> ( 1 2 ) testXY
x= 1
y= 2
ok.

です(一番左側の不等号 > は Paraphrase インタプリタのプロンプトを表しています)。

 なお、仮引数を指定するときに、仮引数名を括弧で括ると(ただし括弧の前後に空白は入れない)省略可能なオプションとして解釈されます。また、... とピリオドを 3 つ続けた仮引数名とすると、残りの引数をリストに格納した引数となります。

// 3 番目以降を仮引数 ... として格納する場合
"test" : ( x y ... ) >param
    // ワード test の処理
;

ループ処理の一貫性を向上

 for+ 〜 next ループと while 〜 repeat ループなどの内部実装を見直し、ループ処理で使用できるワードに一貫性をもたせるようにしました。

switch 〜 dispatch ブロックの仕様変更

 条件を記述する際にワード case が必要となりました。これは将来的にユーザー定義の条件分岐ブロックを実現するため、ワード -> や ->> と対をなすワードとしてワード case を定義したためです。また、ワード default も追加しました。このワードは全ての条件に合致しなかった場合の処理を記述するためのワードです(C 言語における default と同様の機能となります)。

使用例:以下の例ではワード case の使い方を示しています

"FizzBuzz" :
    switch
        case 15 % 0? -> "FizzBuzz" break
        case 5 % 0? -> "Buzz" break
        case 3 % 0? -> "Fizz" break
    dispatch
;

基本型として連想配列を追加

 任意の基本型をキーおよび値として使用可能な連想配列型を追加しました。関連してこれまでリストと配列に対応していたワード set および get も連想配列に対応するようにしました。

使用例:

 > new-assoc
 ok.
 > "Xevious" "NAMCO" @set
 ok.
 > show
      +---------------------------+
TOS-->| assoc ( <Xevious,NAMCO> ) |
DS:-----------------------------------
 ok.

その他、連想配列に関するワード(例えば、指定したキーが存在するかを確認するワード)を追加しました。

アスペクト指向プログラミング(AOP=Aspect Oriented Programming)機能の追加

 ワードの実行部分を差し替える各種ワード set-worded-docol-callee 等を追加し、AOP を可能としました。

使用例:
 このサンプルコードは、ワード呼び出しの前後に、 文字列を表示する myDocol を定義し、 それが機能している様子を確認します。

以下のサンプルコードで定義されるワード hello は、 文字列 HELLO を出力するのみのワードです。

このワード hello の docol として、myDocol を呼び出す worded-docol-caller を設定することにより、 ワード hello を実行すると、hello には定義されていない 処理が hello の実行前後に実行される様子が確認できます。

"myDocol" :
    "IN:myDocol" .cr
    "targetWord=" . word-name .cr

    docol

    "OUT:myDocol" .cr
;

"myDocol" >word set-worded-docol-callee

"hello" : "HELLO" .cr ;

"hello" >word worded-docol-caller set-code


> hello 

 IN:myDocol
 targetWord= user:hello
 HELLO
 OUT:myDocol

 ok.

属性の追加

 ワードに属性を追加できるようになりました。属性の実態は連想配列であり、複数のキーと値を保持できます。詳しくは次の例をご覧ください。

使用例:
 次の例では、hello というワードの属性として、 "logLevel" という文字列の属性と、その属性値として整数値 5 を設定しています。

> "hello" ; "HELLO" .cr ;
  ok.
> "hello" >word "logLevel" 5 set-attr
  ok.
> "hello" >word show-attr
(logLevel,5)
  ok.

デバッガの追加

 AOP (Aspect Oriented Programming) を活用して、デバッガ機能を追加しました。デバッガでは以下の基本的な機能が使用可能です:

  • ブレークポイントの設定・解除
  • 次に実行される内部コードのステップ実行(next, step-over)
  • ワード呼び出し時に呼び出されるワード内へのステップ実行(step-in)
  • 実行(continue)

なお、これらの機能も全てワードで実現されています(例えばブレークポイントの設定は set-breakpoint (省略形 _b)ワード等)。デバッガの実態はデバッガ用の外部インタプリタであり、通常の Paraphrase インタプリタ同様の対話的な処理が可能です(スタックの状況を表示させたり、計算させたり、ワードを呼び出したり、等)。

また、スタックトレースを表示する show-trace や、エラー発生時にスタックトレースを表示するモードを切り替えるワード tron および troff を実装しました。

テスト用機能として疑似標準入出力を追加

 標準入力から得た情報を処理するプログラムをテストできるよう、疑似標準入出力を追加しました。擬似標準出力は mock-stdout と、疑似標準入力は mock-stdin と呼ばれます。以下の使用例では、疑似標準入力に "hello" という文字列を追加し、標準入力から 1 行文字列を読み込む get-line でそれが取り出される様子を示しています。

使用例:

> "hello" >mock-stdin
  ok.
> get-line .
  hello ok.

擬似標準出力へ出力する場合は use-mock-stdout ワードを実行し、mock-stdout から文字列を読み込む場合は get-line-from-mock-stdout ワードを使用します。

return ワードを追加しました

 ワードの実行を途中で抜け出す return なるワードを追加しました。

正規表現を用いた文字列検索

 ワード search を追加し、正規表現による文字列検索に対応しました。search の使用例を以下に示します:

> "441-3124" '^\d{3}-\d{4}$' search .
  (size=1 data=0x7f8770600288)
  [0]=441-3124
ok.

ユーティリティワードの追加

 複数の定数を定義するワード enum や、算術用ワード max などを追加しました。

文字列処理関連ワードの強化

 文字列の n 番目の文字を取得するワード at など、文字列処理に関するワードをいくつか追加しました。

基本型として無効型を追加

 ワード invalid を始めとする無効型に関するワードをいくつか追加しました。

仕様が変わった機能やワード

ループ関連ワードの仕様変更

for{+|-} 〜 next の終値の解釈変更

 これまではループ終了の値まで含む仕様でしたが、終了の値を含まないように仕様を変更しました。0 10 for+ ... next で 0 から 10 までループするのではなく、0 から 9 (以下)の値までループするようになりました。

while ループの条件確認処理に関する変更

 これまでのワード while では、while の書かれている場所で TOS の値が true であるか否かを確認していました。しかし、この方法では、while 〜 repeat ループを継続するか否かの処理を while ループに入る前と、ループ内の 2 箇所に書く必要があり、コードとして不格好でした。

今回はワード do を再度導入し(以前存在していた Forth 由来の do とは異なります)、この同じ処理を 2 度書くという状況を回避できるようになりました。具体的には while と do の間に while ループを継続するか否かの処理を記述すれば、それで十分になります。詳しくは次の使用例をご覧ください。

使用例:次の例では、10 から 0 までの値を表示します

> 10 while dup 0 >= do dup . 1 - repeat drop
  10 9 8 7 6 5 4 3 2 1 0 ok.

while 〜 do の間に記述された部分がループを継続するか否かの確認のための処理部となります。この部分のコードを実行した結果 true であればループは再度繰り返され、false であれば repeat 以降に処理を移します。

接頭語 @ 付きワード名への変更

 参照型の接頭語(ただしこれはシステムとして定められているものではなく単に名前付けの慣習)を @ としたため変更しました。例:valid? を@valid? に変更など。

 また、ユーティリティワードとしてワード i の仕様を変更しました。これまでワード i は for{+|-} 〜 next ブロック内でのみの使用を想定していましたが、次期 Paraphrase では map, filter, find, reduce といったワードでも利用できるようになりました。これらのワードでは、現在処理対象となっている要素の リスト内での位置(インデックス値)を スタックに積みます。

その他

各種デバッグ

 いくつかのバグ修正を行いました。

出力書式の変更

 ワード . (ドット)におけるリスト表示などで、表示がより見やすくなるような変更を行いました。

まとめ

 この記事を書いている時はまだ 2020 年 12 月初頭なので、2020 年を総括するには若干早い気もします。とはいえせっかくの機会ですので、まとめとして現在感じている事をここに記しておきたいと思います。

 Paraphrasse の開発は、(確か)2018 年の 2 月より始まっています。これまでおそよ 3 年間開発を続けている状態です。当初は足りない機能ばかりでしたが、今年は念願だったデバッガの実装ができました(とはいえ、まだ最低限度の機能しかありませんが)。その他、AOP やワードへの属性情報の追加など、なんとなく言語としては最低限の機能が揃ったような気がしています。

これら多くの進展は、 kanaka さんの mal - Make a Lisp (注 3)を参考に Paraphrase で Lisp インタプリタを実装している際に得た気づきによる部分が大きいです。まだ Step 4 の実装の途中ですが、Lisp のような、より実践的なプログラムを実装することで、より実用的な言語になれるのではないかと期待しています。

注 3: MaL - Make a Lisp
https://github.com/kanaka/mal/blob/master/process/guide.md

 おそらく本文書に記した機能にて ver.0.94 はリリースすることになりそうです。基本機能としてまだ不足しているものとしてはソースレベルデバッガでしょうか。現在は中間コードレベルでのデバッグ機能しか有していないので、(最適化をオフにした場合は)ソースレベルデバッグを可能にしたいところです。この辺りは次次期リリース(つまり ver.0.95)で実現という感じでしょうか。

 …とまあ、こんな感じで様々な改良を行っている Paraphrase ですが、なんとなく ver.1.0 の正式リリースも視野に入ってきた感があります。ver.1.0 のリリース時には、ある程度の入門書というかガイドブック(Programming Language Paraphrase とか?)が用意されているべきかと思います。なので、それらを執筆しつつ、機能や仕様の不具合を修正し、文書一式が揃ったところで ver.1.0 のリリースになるのではないかと思っています。

 来年はどこまで開発が進むのか分かりませんが、まずは今年度中に次期 Paraphrase である ver.0.94 のリリースを実施すべく、あと 3 ヶ月程頑張っていきたいと思います。乞うご期待。

12
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
12
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?