Forth-like な言語を作ってみたことによる考察

by Akihiko Koga
22th Apr. 2019 (Update)
10th Apr. 2019 (First)

計算機(主にソフトウェア)の話題 へ
ホームページトップへ戻る

内容

  1. 趣旨
  2. 概略
  3. 言語実装の概要と考察
  4. あとがき
  5. 後日談および試作用の言語仕様
  6. 参考文献

趣旨

この2週間位,Forth っぽい言語のインタープリタをいくつか作って遊んで いた.本当は,何か他のシステムに組み込んで,機能拡張用のスクリプト言語として 使えればよいなと思いつつ,作っていたのだが,今のところ,「今後はこれを使って行こう」と いう気にまではならなかったので,ただ,遊んでいたというだけである.

でも,ただ遊んでいただけでは 今後に繋がらないので,考えたこと,調べたこと,測定してみたことなどをまとめておくことにした.タイトルも,「〇〇を作ってみた」というホームページはよくあるので, 「作ってみたことによる考察」と申し訳程度に考察を入れている.

言い忘れたが,Forth は 1970 年代に公開された,スタックベースのとても小さな プログラミング言語である.処理系がとても小さいので組み込み機器の制御に使われる ことがある.マニアも結構いる.「えっ? 計算ってこんなに簡単なプロセスで進んで 行くの?」ということを考えさせられる言語であると思う.


概略

今回,5つか6つ作ったが(そのうち3つくらいは ruby を使った原理実験),最後に作ったものは次のような言語である.

  1. Forth に似た言語(Forth 自身やそのサブセットではない)

  2. C 言語で実装.中間語へのトランスレータとインタープリタからなり, 全部で650行程度.

  3. 主な特徴・機能は以下の通り.とりあえず,エラトステネスの振るいで素数を見つける プログラムが書ける程度を目指した(ということは以下でも述べるが配列が使える)

    1. スタックを直接ユーザが認識して引数を渡したり,ローカル変数の 領域がわりにする
    2. 扱うデータ構造の基本型は整数のみ.文字列も使えるが 主に出力用で, 連結や検索など本格的な文字列操作は組み込んでいない
    3. 名前を付けることができる変数としてはグローバル変数のみ
    4. 配列は使えるようにした
    5. 制御構造は,if 文while 文複数の文のブロック化(再帰)関数呼び出し

この言語の実装自体は公開していない.どちらかと言えば失敗作に近いので,ソースプログラム そのものを公開するより,仕様,その仕様での使い勝手,実行速度や処理系の各部分の 規模の測定,短く作るためにはどうすればよいかの考察などが価値があると思ったので, ここにはそういう結果を載せた.


言語実装の概要と考察

ここでは,今後の言語設計や言語処理系の作成の参考になるように,

  1. 言語の仕様
  2. 実験環境(PC の仕様など)
  3. プログラムを書いてみた感想
  4. 実行速度などの測定
  5. 処理系の書き方と行数
    ... 表. 言語処理系の行数 ...
    ... switch 文と関数ポインタ方式の速度比較
    ........ プログラムリスト
    ........ 測定結果
について整理しておく.

言語仕様

まず,ここで作った言語の仕様を述べる.Forth に似ているけど,Forth ではない. 似て非なるもので申し訳ない.Forth について知りたい人は 参考文献にドキュメントや 処理系の探し方を書いたので参照してほしい.

Forthy* の言語仕様

  Program        ::= (Definition | Statement) ...
  Definition     ::= def Word Statement ... ;
  Statement      ::= Word | String | Integer | IfStatement |
                       WhileStatement | BlockStatement
  IfStatement    ::= if Statement Statement Statement
  WhileStatement ::= while Statement Statement
  BlockStatement ::= { Statement ... }

  注意
 ・「...」は直前のものの 0 個以上の繰り返し
  ・String は " から始まって " で終わる文字列.ただし," を入れたいときは
   その前に \ を入れる
  ・Integer は,数字の列で,先頭に + あるいは - が1個ついても良い
  ・Word は,{, } 以外の文字列で String, Integer, Real でないもの
   (以下の実装ではなんとなく :, ;  は1文字でワードとしている)
  ・関数定義は def から始まるようにしてあるが,Forth と同様に : も使える
    ようにしてある.ただ Forth と区別がつけにくくなるのでここでは def で書く.
  ・// から行末まではコメントとして無視する
* Forth に似ているので,自分の中での内部名称を Forthy と名付けていた.

どんな言語か感じをつかめるように簡単な例題をあげておく.

def fact // argument is given as a number on the stack top
  if {0th 2 <} {
    pop 1
  } {
    0th 1 - fact *
  }
;

def fib // argument is given as a number on the stack top
  if {0th 2 <} {
      pop 1
  } {
      {0th 1 - fib}
      {swap 2 - fib}
      +
  }
;

def start 10 fib . cr ;

デフォルトでは start という関数から始まるように設定してある. 上のプログラムでは fib だけしか起動されない.fact はおまけで書いてあるだけである. ところどころ,{, } が入っているが,これは単語を続けて書くと見にくくなるので, 文をブロック化できる機能を使って,意味的な単位を区切るためにも使っている. コンパイルすればこれらの括弧は消えるのでオーバーヘッドはない.空白や改行は単に 単語と単語の間を区切る意味しか持たないので,一行に続けて書いても構わない.

このプログラミング言語で書いたプログラムが実行される基本的な環境は次のように 1つのデータスタックがあり,ここには整数あるいはアドレスが置かれる,もう一つ, 名前の表があり,ここには関数やグローバル変数が置かれる.簡単のため,グローバル変数は $が先頭についた文字列とする.

例えば,上の例の fib では,スタックトップに引数が与えられることを想定していて, それを 0th でコピーしてスタックに積み,それと 2 を比較して,2 が大きければ, if 文の二番目のブロック {pop 1} にいき,スタップトップをポップして,その代わりに fib の値である 1 を積む.

もし,2 との比較でスタックトップが 2 以上なら,3番目の ブロックを実行する,といった具合に計算は進む.この3番目のブロックには, 2か所に fib が表れているが,これらは再帰呼び出しである.あと,サンプルに 現れる文で,想像がつきにくいものとしては,「.」はスタックトップの数をポップして 表示し,「cr」は改行を出力する文である.

上に書いた図の右側にあるのは,プログラム中の 名前を管理する表で,グローバル変数はここで管理される.プログラムのコンパイル結果なども ここにあるが,ユーザが認識するのはほぼグローバル変数だけである.プログラムの中でグローバル変数への値の出し入れをする組み込みの関数が用意されている.その他にも配列を管理する 領域などがあるが,煩雑になるので,ここでの説明はこれくらいにしておく.

次に組み込みの関数や構文の意味について簡単に説明しておく.

組み込みのワード(Word)

  1. 0th, 1th, th, pop, swap
    1. 0th ... スタックトップをもう一度プッシュする
    2. 1th ... スタックトップから1つ下のデータをプッシュする
    3. th ... スタックトップ+1番目の要素をスタックトップと置き換える
      つまり,0th は 0 th と同じである

    4. pop ... スタックをポップする
    5. swap ... スタックトップとスタックの1番目のデータを入れ替える

  2. ., .%, cr
    1. . ... スタックトップをポップして,それを整数として出力する
    2. .% ... スタックトップをポップして,それを文字列として出力する
    3. cr ... 改行する

  3. readint
    1. readint ... 端末から整数を読み込んで,それをスタックにプッシュする

  4. +, -, *, /, %
  5. <, <=, =
  6. not
  7. isqrt
    スタックからそれぞれの演算に必要ないくつかのデータを取り出し,それらに演算を施し,その結果をスタックに プッシュする.演算子(関数)が <, <=, +, - などの二項演算子の場合はスタックは次のようになる.

    また,演算子が not や isqrt のように一項であるときはスタックは次のようになる.

    論理値に関しては,偽は 0,真はそれ以外とする. not は論理的な否定を返し,isqrt は整数の範囲での平方根を返す.

  8. 自然数, 文字列
    自然数はその値がスタックに積まれ,文字列はそのアドレスがスタックに積まれる.

  9. @, !
    グローバル変数の値の参照と値の設定を行う.意味は以下の例を参照のこと.
      $a @              // 変数 $a の変数番号がスタックから取り除かれ,
                        // その代わりに $a の値をスタックトップにプッシュする
      10 $a !           // 変数 $a に 10 を入れる.スタックは 10 の部分まで
                        // 取り除かれた状態になる.
    

  10. array, free, a@, a!
    配列の生成,削除(解放),要素の参照,要素の設定を行う文.この言語では 配列は配列番号で管理される.それぞれの意味は以下の例を参照のこと.
      100 array         // 整数が 100 個入る配列を生成し,その配列番号をスタック
                        // トップにおく.
    
    生成した配列番号を記憶しておくためにはグローバル変数に入れると良い.
      100 array $a !    // $a に生成した配列の番号を設定
      300 $a @ 5 a!     // $a に入っている配列番号の配列の 5 番目の要素と
                        // して 300 を入れる
      $a @ 5 a@         // $a に入っている配列番号の5番目の要素をスタック
                        // トップに置く
      $a @ free         // $a に入っている配列番号の配列を解放する
    

  11. if, while
    これはワードというより構文である.if は後ろに3つの文を取る.文は ワードかブロック文({ と }で囲まれた文の列)である.最初の文は 条件として使われ,この文を実行した結果,スタックトップが真(0 以外) なら,第2の文が実行され,偽(0)なら第3の文が実行される.分岐の前に スタックトップにある真偽の値はポップされる.

    while は後ろに2つの文をとる.最初の文は条件として扱われ,これを 実行した結果が真なら第2の文が実行され,再度 while の文が実行される. ここで,条件判定結果はスタックからポップされることに注意.

  12. :, def, ;
    : と def は同じ意味である.def の後ろにはワードが来て,そのワードの 次から ; までのワードの列が : の直後のワードの内容として定義される. このように定義されたワードが他のところで参照された場合,その定義の内容と 置き換えられる.この定義機能は再帰定義も可能である.そのまま定義している ワードをその定義の中で書けばよい.

  13. {, }
    文のブロックを作るために使われる.{ 文 文 ... 文 } は1つの文として 扱われる.if や while の後に1つしか文が書けないところに複数の文の 列を書きたいときに,このようにブロックにして書くことができる.また, コンパイルしてしまえば,{, } を挟むことはオーバーヘッドにはならないから, ワードの列で意味のある単位ごとに区切るためにも使うことができる. 例えば,通常の式で f(10) + g(2, 5) は,

    10 f 5 2 g +

    と書くより

    {10 f} {5 2 g} +

    と書いた方が分かりやすいだろう.

  14. exit
    プログラムを停止する.

  15. clock
    ミリ秒単位でシステム起動から呼び出されるまでの時間を返す.速度計測のため.


実験環境(PC の仕様など)

あとで言語の処理系の性能評価などが出てくるので,使った PC の 性能などを書いておく.だいぶ古い PC であるが多くの端子がついているなど 高機能な PC である.例えば,RS232C とか :-).

  1. 計算機 : Panasonic CF-S10

  2. CPU : Core i5 2520M 2.5GHz/2コア

  3. メモリ容量 : 4 GB

  4. OS : Windows-10 64bit 版 (もとは Windows-7)

  5. gcc : gcc version 4.8.1 (GCC) thread model: win32 on mingw

  6. ruby : ruby -v では次のように出力される
    ruby 2.3.3p222 (2016-11-21 revision 56859) [x64-mingw32]


プログラムを書いてみた感想

次の3つのプログラムを書いてみた感想を述べる.

  1. フィボナッチ数を求めるプログラム
    ごく単純な再帰プログラムの例

  2. ハノイの塔の問題の再帰的なプログラムを作る
    沢山の引数を持った再帰関数の例

  3. エラトステネスの振るいで素数表を作る
    配列を使ったプログラムの例

これらを選んだ理由は基本的に(再帰)関数呼び出し,条件分岐,ループがあれば 計算理論的には任意の関数が作れること.ただし,計算理論で扱うZは無限長の理想的な整数で, これを使って配列を作ることができるので,別途,配列を使ったプログラムを作ってみる. また,関数呼び出しの時,引数が複雑になったときに人間がどれくらいの負荷を感じるか知りたい, という理由である.

これらのソースプログラムは次のようになる.

def fib {
    if {0th 2 <} 
    {pop 1} 
    { {0th 1 - fib} {swap 2 - fib} + }
}
;

def hanoi // n c b a
  if {0th 1 <} {
    pop pop pop pop
  } {
    0 th $n !
    1 th $c !
    2 th $b !
    3 th $a !
    $a @ $c @ $b @ $n @ 1 - hanoi
    0 th $n !
    1 th $c !
    2 th $b !
    3 th $a !
    "move " .% $a @ .% " to " .% $b @ .% cr
    $c @ $b @ $a @ $n @ 1 - hanoi
    pop pop pop pop
  }
;

def prime
  $n !                   // upperbound
  $n @ isqrt $m !        // $m := isqrt($n)
  $n @ array $primes !   // set an array of size $n to $primes
  "1. Set all elements to 1\n" .%
  1 $i !
  while { $i @ $n @ < } {
    1 $primes @ $i @ a!   // $primes[$i] = 1
    $i @ 1 + $i !
  }

  "2. Sieve\n" .%
  2 $i !
  while { $i @ $m @ <= } {
    if {$primes @ $i @ a@} {
        {$i @ $i @ +} $j !
        while {$j @ $n @ <} {
            0 {$primes @} {$j @} a!
            {{$j @} {$i @} +} $j !
        }
    } endif
    {$i @ 1 +} $i !
  }
  "3. Output\n" .%

  2 $i !
  0 $count !
  while {$i @ $n @ <} {
    if {$primes @ $i @ a@} {
        $i @ . " " .%
        $count @ 1 + $count !
    } endif
    $i @ 1 + $i !
  }
  "\nCount = " .% $count @ . cr
  "End\n" .%
;

def start-fib 10 fib . cr ;
def start-hanoi "a" "b" "c" 4 hanoi ;
def start-prime 1000 prime ;
def start start-fib ;

各プログラムを書くとき感じた感想は以下の通りである.

  1. fib
    def fib {
        if {0th 2 <} 
        {pop 1} 
        { {0th 1 - fib} {swap 2 - fib} + }
    }
    ;
    
    def start 10 fib . cr ;
    

    1. 全般的な書きやすさについて
      これは特に難しくは感じなかった.スタックの上2つはきちんと頭の中に 入れていなければならないので,最初はちょっと「これで良いかな」という 不安はあったが,すぐ慣れた.

      ここでの if 文は,else-part を省略できず,

          if { ... } { ... } { ... }
      
      のようになるので,
      1. 同じ形の { ... } が then-part なのか else-part なのか,一見して分かりにくい.
      2. ここでは else-part を省略できないが,世の中には省略できる言語が多いので, つい,
            if {...} {...}
            次の文
        
        のようにやってしまい,次の文が if の else-part として取られることがあった. これは,
            def endif ;
        
        と定義しておいて,if を
            if {...} {...} {...} endif
            if {...} {...} endif
        
        という使い方を推奨することで防げると思う.余計な endif の分だけオーバーヘッドは あるので,まったく効果を持たないキーワードを定義できるようにしても良いかもしれない.

    2. 視認性について
      上では,式の単位を見やすくするために {, } を使っている.これは可読性を 向上するのに役に立つと感じた.例えば,上のプログラムを
      def fib {
          if {0th 2 <} 
          {pop 1} 
          {0th 1 - fib swap 2 - fib + }
      }
      ;
      

      と書くこと,あるいは,もっと複雑な文の列を区切らずに書くことと 比べてみればわかると思う.同様の効果は,「,」をまったく効果を持たない キーワードとして,視認性を挙げる目的で導入しても得られる.

      def fib {
          if {0th 2 <} 
          {pop 1} 
          {0th 1 - fib, swap 2 - fib, + }
      }
      ;
      

    3. if の条件文の位置について
      我々の言語では,if 文の条件文を if の後に書くことにした.本物の Forth では,特に 条件文を書くところは指定されておらず,if 文に到達したところの スタックトップの値を ポップして条件分岐するだけである.つまり,
      1. Forth
        条件文 if THENにあたる文の列 else ELSE にあたる文の列 then

      2. 我々の言語
        if 条件文 THENにあたる文 ELSEにあたる文
        通常,文1つでは用をなさないので
        if {...} {...}

      となる.私が if をこの仕様にしたのは,while 文との整合性を 考えてである.while の場合は,条件文を while の後に書かせないと,while 文の最後に もう一度同じ条件文を書かなければならなくなる.例えば,
          条件文1 while {...実行文... 条件文1}
      

      こんな感じである.同じ条件文1 を二回書くのは,間違えの元であるので,結局

          while 条件文 {... 実行文...}
      

      の形にした.if 文の構文を決めるときは,この while 文との整合性を保つために if の 後ろに書くようにしたわけである.これは同時に条件文を {, } で囲むことを強要することになり, 視認性には貢献したように思う.

    4. 本物の Forth との差
      ・ここに出てきた関数の名称の差(ここの言語 <=> Forth)
      0th <=> dup
      1th <=> over
      pop <=> drop

      ・Forth の if-文と ループの書き方

      1. 条件分岐
        ... if ... then または ... if ... else ... then
      2. ループ
        境界値 ステップ do ...実行文... loop
        begin ...条件... while ...実行文... repeat
        begin ...実行文... until
        begin ...実行文... again

  2. hanoi
    これはハノイの塔の問題を解くプログラムである.

    def hanoi // n c b a
      if {0th 1 <} {
        pop pop pop pop
      } {
        0 th $n !
        1 th $c !
        2 th $b !
        3 th $a !
        $a @ $c @ $b @ $n @ 1 - hanoi
        0 th $n !
        1 th $c !
        2 th $b !
        3 th $a !
        "move " .% $a @ .% " to " .% $b @ .% cr
        $c @ $b @ $a @ $n @ 1 - hanoi
        pop pop pop pop
      }
    ;
    
    def start "a" "b" "c" 4 hanoi ;
    

    このプログラムは結構難しかった.上のプログラムはグローバル変数 $n, $a, $b, $c を使っているが,これは別に使わなくとも,スタックに 蓄積されているデータを使えばできる.しかし,計算や再帰呼び出しの ために,取り出した値を再度スタックに積むので,いま,スタックがどうなっているか 想像するのがかなり難しい.もちろん,1つスタックに積んだら,取り出す位置が 1つ増えることを忠実に計算すればわかるのだろうが,これが中々難しい. 我々の言語ではスタックトップから n 番目 の要素をスタックに積むには, 例えば, n = 3 の時は,

    3 th

    と掛ける.さらにそれより一つ下のデータをその上に積むには,

    5 th

    となる.それでは,つぎに最初 2 番目にあったものを上に積むには ? th に なるだろうか? 実は私はすでに分からなくなっている.こんなことを続けて, スタックに積んでいくのは至難の業だと思う.とても正しいプログラムが 作れるような気がしない.

    という訳で,ここではグローバル変数を使っている.いったん,$n, $a, $b, $c に 入れてしまえば,あとはこれらを参照して正しくスタックに積めるのではあるが, こちらはこちらで,このグローバル変数は再帰呼び出しの間に変えられてしまう可能性が あるので,再帰呼び出しの後に再度設定しなければならない.これも誤りを誘発する 要因になり得る.

    また,hanoi の関数は,スタックに問題となるデータが積まれ,その問題を解いた後, スタックからその問題をポップしなければならない.それが上のプログラムで

    pop pop pop pop

    となっているところであるが,これをどこに置かないといけないのかは良く考えないと ポップしなかったり,余計にポップしてたりと,バグの発生の要因となり得る.

    以上をまとめると,プログラマのスタック操作だけで,引数を渡したり, ローカル変数を実現させるのはとても分かりにくく,危険である. 近代の言語がパラメータ渡しやローカル変数を発明してくれて,とても 楽になったと実感した.

    もう一つ,ここではグローバル変数の機構

    1. 宣言は特に必要なく $ で始まる名前を書けばよい(ruby と同じ)
    2. 参照 $n @ で値がスタックトップにプッシュされる
    3. 設定 $n ! でスタックから値がポップされ,それが変数に設定される

    を導入しているが,やはり,この書き方は結構間違いやすい.ここは文法的には 実際の Forth と殆ど同じである.Forth ではまず,変数の宣言がいるが,我々は $ で始まる名前は宣言されているものとして使って良い.Forth でも我々の言語でも 変数がプログラムに現れたら,その変数を表すもの,我々の言語では変数の番号が スタックに積まれ,Forth では変数のアドレスがスタックに積まれる.後は,@ で スタックトップの変数の値を参照,! で,スタックの2番目のデータをスタック トップの変数に設定する.どちらにしても,変な変数番号,変なアドレスが スタックに積んであれば,システムを壊してしまう操作が行われる.非常に危険 である.これは C 言語のポインタでも同じような危険性があるが,この言語と Forth の場合は,それが起こりやすい.ここでの教訓は次のようなものだろうか.

    1. 参照,設定の安全性をプログラマ自ら保障しなければならないのは 辛い.特に,それ以外のところでも,分かりにくく,注意力が分散 される状況下ではとても大変な作業のように思う.
    2. これと裏返しのことだが,それをシステムが保証してくれたり, チェックしてくれたりする機構はありがたい

  3. prime
    これは配列や二重ループの使い勝手の評価を念頭においている.
    def prime
      $n !                   // upperbound
      $n @ isqrt $m !        // $m := isqrt($n)
      $n @ array $primes !   // set an array of size $n to $primes
      "1. Set all elements to 1\n" .%
      1 $i !
      while { $i @ $n @ < } {
        1 $primes @ $i @ a!   // $primes[$i] = 1
        $i @ 1 + $i !
      }
    
      "2. Sieve\n" .%
      2 $i !
      while { $i @ $m @ <= } {
        if {$primes @ $i @ a@} {
            {$i @ $i @ +} $j !
            while {$j @ $n @ <} {
                0 {$primes @} {$j @} a!
                {{$j @} {$i @} +} $j !
            }
        } endif
        {$i @ 1 +} $i !
      }
      "3. Output\n" .%
    
      2 $i !
      0 $count !
      while {$i @ $n @ <} {
        if {$primes @ $i @ a@} {
            $i @ . " " .%
            $count @ 1 + $count !
        } endif
        $i @ 1 + $i !
      }
      "\nCount = " .% $count @ . cr
      "End\n" .%
    ;
    
    def start 1000 prime ;
    

    これを実行すると次のような出力がでる.

    1. Set all elements to 1
    2. Sieve
    3. Output
    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997
    Count = 168
    End
    

    プログラムの最初の

    $n !

    はスタックトップで与えられた整数を $n に入れているのだが, $n に何を入れているか分かりにくい.例えば,何もしない関数 arg を 作って,

    arg $n !

    とした方が分かりやすいかもしれない.

    次に配列の生成だが,この言語では例えば,

    100 array

    で,要素が整数で大きさが 100 の配列が生成され,その配列番号が 100 をポップして,スタックトップにプッシュされる.ここで配列番号と 述べたが,この言語では配列を管理するテーブルがあり,そのテーブル 内の番号で配列を識別している.これは実際の Forth では直接アドレスを 置いているように思われる.したがって,Forth の場合は配列は,その 先頭を指すポインタとして扱われ,n 番目の要素の参照設定は,ポインタから 要素分だけアドレスを増やした場所への参照(@),設定(!)と解釈される.

    1. Forth での配列の生成・設定・参照
      var sixteen
      create sixteen 16 cells alloc
      51 sixteen 3 cells + !
      sixteen 3 cells + @

      cells は1つのデータのサイズ.上のコードは, 16 cells の配列を生成して それを変数 sixteen にいれ, 51 をその 3 番目に入れ, その 3 番目を参照するコードである.

      sixteen はアドレスなので,それに 3 cells 分足したところに ! すれば,そのアドレスにデータを設定できる.参照も同様である.

    2. 我々の言語での配列の生成・設定・参照
      16 array $sixteen
      51 $sixteen @ 3 a!
      $sixteen @ 3 a@

      こちらではグローバル変数の宣言は必要ないので,直接 配列を生成するところから始まっている.まず 16 個の 整数を格納できる配列を生成して,その配列番号をグルーバル 変数 $sixteen に入れている.次にその配列の 3 番目の要素に 51 を入れるところだが,少し,実際の Forth と異なる. こちら側では,

      $sixteen @

      としないと,その配列番号が取り出せない.また,取り出せたのは 配列番号であり,アドレスではないため,そこに直接 ! はできない. そのため,こちらでは配列の n 番目の要素にデータを入れると言う 新たな操作 a! を導入している.参照も同様に専用の参照の操作 a@ が使われている.

    上で見てきたように,配列のアドレスを直接使うか,配列番号を使うかで 記述法に若干の違いがある.アドレスを使う方は何で + なんだと思うかもしれない. 配列番号を使う方は,配列を保持している変数からの値の取り出しと,!, @ 以外の 値の設定・取得捜査 a!, a@ が導入され,プログラマは頭を悩ませる.

    実は,この設定と参照は,自分自身結構悩んだ.上のエラトステネスのプログラムを 作るのは,処理系をデバッグ中だったこともあり,午前中半日位使っている. 配列の分かりやすい操作を行うことはプログラミング言語設定で重要だと感じた.

他のトピックスとしては,構造体が必要かやそのほか近代的なプログラミング言語の 概念の評価があると思うが,ここでは非常に小さな仕様の言語開発を考えているので, それらの概念についての評価までは進まず,これで終わる.


実行速度などの測定

どのような実装をすれば,どのくらいの効率が達成されて,それは他の 言語の利用とどちらが効率が良いかを把握しておくのは重要なことだと思う.ここでは 今回,この言語を実装した方法とプログラム実行の速度の関係を整理しておく.C 言語の プログラムを使う時は,gcc -O のオプションでコンパイルしている.使った PC の性能などは 実験環境を参照のこと.

fib(35) の実行に掛かる時間

No. プログラム 処理時間(秒)
1 本言語のインタープリタ 2.656
2 本言語のインタープリタ
(VM のループでフラグの参照を1つ除去)
2.364
3 ruby の再帰プログラム1.541
4 C 言語で書いた最小限度の VM 上で
ハンドコンパイルした fib を実行
(ソースプログラムを後掲)
1.604
5 同上(pc, csp, dsp を局所変数化)1.224
6 C 言語での再帰プログラム0.062

上の No.2 の説明は言葉たらずかもしれない.No.1 は今回作ったインタープリタだが, この仮想コードの解釈実行の差異に,一つのグローバル変数を参照していて,それが 立っていたら,1命令ごとにユーザに継続を聞くようになっている.つまり, 1命令実行するごとに,そのフラグへのアクセスが発生する訳だ.これのフラグを 見ないようにしたものが,No.2 である.この変数の参照を取るだけで,10% ほど 速くなっているので,命令実行の方にはそれほどオーバーヘッドは無いのではないかと 思われる.

No. 4 あるいは No. 5 は,機械語に変換しないで,仮想マシンのコードに変換する 限り,出し得る最高のスピードであるはずと思う(補足1).これでも,C で書いた fib より, 20 ~ 30 倍遅い.また, No.4 は ruby のコードより遅い.実を言うと, ruby の コードがこれだけ速いのは私にとって意外だった.

補足1
この後,命令セットを拡張するなどしていろいろいじっていたら,0.6秒程度まで 高速化できた.例えば,命令列 pop, push value の代わりに,スタックトップを value に置き換える 命令として set value を追加するなど.かなり場当たり的にやったので,こちらは公開しない.

上記 No. 4のソースコード

(C 言語で書いた最小限度の VM 上でハンドコンパイルした fib を実行する方式)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define CMAX 10000
#define DMAX 10000

enum {c_push, c_pop, c_dup, c_swap, c_add, c_sub, c_less,
    c_jmp, c_jmpz, c_call, c_ret};

struct _INSTRUCTION {
    int code;
    void *arg;
}
code[] = {                             // hand-compiled fib
    {c_dup},                           // 0
    {c_push, (void *) 2},
    {c_less},
    {c_jmpz, (void *) (code + 7)}, 
    {c_pop},
    {c_push, (void *) 1},
    {c_jmp,  (void *) (code + 16)},
    {c_dup},                           // 7
    {c_push, (void *) 1},
    {c_sub},
    {c_call, (void *) (code + 0)},
    {c_swap},
    {c_push, (void *) 2},
    {c_sub},
    {c_call, (void *) (code + 0)},
    {c_add},
    {c_ret},                           // 16
};

struct _INSTRUCTION *cstack[DMAX];
int                  dstack[DMAX];
struct _INSTRUCTION **csp, *pc;
int *dsp;

int main() {
    int n = 35, tmp, t1, t2;

    t1 = clock();
    csp = cstack - 1;
    dsp = dstack - 1;
    *(++dsp) = n;
    *(++csp) = code - 2;
    pc = code;
    while (pc >= code) {
//        printf("pc = %p, code = %d, *dsp = %d\n", pc, pc->code, *dsp);
        switch (pc->code) {
          case c_push: *(++dsp) = (int) pc->arg; break;
          case c_pop:  dsp--; break;
          case c_dup:  *(dsp+1) = *dsp; dsp++; break;
          case c_swap: tmp = *dsp; *dsp = *(dsp-1); *(dsp-1) = tmp; break;
          case c_add:  *(dsp-1) += *dsp; dsp--; break;
          case c_sub:  *(dsp-1) -= *dsp; dsp--; break;
          case c_less: *(dsp-1) = ((*(dsp-1)) < *dsp)?1:0; dsp--; break;
          case c_jmp:  pc = ((struct _INSTRUCTION *) (pc->arg)) - 1; break;
          case c_jmpz:
            if ((*(dsp--)) == 0)
                pc = ((struct _INSTRUCTION *) (pc->arg)) - 1;
            break;
          case c_call:
            *(++csp) = pc;
            pc = ((struct _INSTRUCTION *) (pc->arg)) - 1;
            break;
          case c_ret: pc = *(csp--); break;
        }
        pc++;
    }
    t2 = clock();
    printf("fib(%d) = %d, %d mili sec\n", n, dstack[0], t2 - t1);
}

No. 5 は,このコードで,変数 pc (プログラムカウンタ), csp (コントロールスタック), dsp (データスタック) をレジスタに割り付けられるように 局所変数にしたものである.

ruby で書いた fib の再帰プログラムも念のために書いておく.

def fib(n)
  if n < 2 then 1
  else
    fib(n-1) + fib(n-2)
  end
end

処理系の書き方と行数

この言語およびその処理系を作ってみたのは,できるだけ少ない行数で,そこそこの 書きやすさと性能を持った言語ができないか検討するためである.極端に言えば, 200 行位で,何かそれなりに動く言語処理系が作れるとありがたい.そのとき, yacc などコンパイラコンパイラの類は,そのインストールから必要になるので, できるだけ使わないで済ませたい.その処理系のソースプログラムを扱うだけで メンテナンスできるのが好ましい.今回は 650 行位になってしまい,200 行は 中々無理そうな雰囲気になってしまった.言語の機能を落とせば,配列の機能を 入れて,300 行位ならもしかしたら可能かもしれないが,今思いつく中では, アセンブラとあまり変わらないものになりそうな気がする.

私は大昔, グラフィックエディタをフリーウェアとして出したことがあり,そのとき, そのエディタをカスタマイズするのにスクリプト言語を組み込めたらなと 考えていたことがある.LISP もどきなら楽かなとも思ったが,多くの人が 分かりにくいし,インタープリタだと性能も出ないしで諦めたことがある.

前置きが長くなったが,今回,色々試作して,処理系の書き方のパターンやそれが どのくらいの行数を必要とするのかをまとめておいた方が,次回考えるとき 役に立つだろうと思って,この章を起こした.なお,ここでの関心事はあくまで, C言語の普通の書き方で(読みやすさを無視して全部一行に詰め込むなどしないで) 何行でできるかという,言ってみればセコイ話である.

以下,実装の規模の説明をするために,実装方式をある程度説明する.ソースプログラムの 短さを第一に考えたこともあり,かなり下手だと思うので,こういう実装をすると このくらいの規模になるのかということの見当のための 他山の石として活用してほしい

まず,およその処理方式を説明しておく.

ここで作った言語処理系の概要

まず,処理系が使うデータを大まかに説明しておく.

左側に囲ったものが主にコンパイル(構文解析とコード生成)用のデータである. 主にと書いたのは,名前表は,システムやユーザの関数定義,変数の定義とその値の保持 にも使っていて,実行時も使うからである.

左の枠内には次の3つがある.

  1. 名前表
    これはトークンや関数名,変数名を管理するために使っている.また,実行時は 関数のアドレスを保持したり,変数の値を保持するためにも使っている. この表のフィールドは次の5つである.
    1. 名前
      トークンの文字列である.

    2. 種別
      トークンの種別である.以下のものを設けた.
      1. TKN ... "{", "}", "if" など文法上予約されている文字列

      2. SYS1 ... システム関数1.10 20 + の 「.」のように仮想コードの 解釈実行系の中で識別して解釈実行するもの

      3. SYS2 ... システム関数2.というかライブラリ関数と呼ぶべき かもしれない.この表の関数アドレスのところに呼ぶ関数の アドレスを設定しておいて,仮想コードの解釈実行系の中で は,直接解釈実行をするのではなく,そのアドレスを呼び出す だけにする.

      4. USR ... ユーザ関数.トークン番号のところに,そのコンパイル結果の アドレスを入れる.

      5. VAR ... グローバル変数.今回は ruby のように最初の文字が $ とした.

      少し,設計上の反省を書いておく.

      1. 表としては同じ名前の関数と変数を許したが,結局変数は$で 始まるものとしたのでこのような状況は生じない.変数の 値領域と関数のアドレスは共有しても良かったかもしれない.
      2. ユーザ関数のコンパイル結果のアドレスをトークン番号の ところに入れるようにしたが,これは関数アドレスの 方が良かったかもしれない.

    3. トークン番号
      文法上の予約語や実行系が直接解釈実行するものには異なる番号を 振った.システム2関数(ライブラリ関数),変数には単に識別子を 表す T_ID としている.ユーザ関数では,上に書いたように,T_ID でも なく,このフィールドは別の用途に使ってしまった.

    4. 関数アドレス
      システム2関数(ライブラリ関数)の関数ポインタ.この関数がユーザの プログラム内で呼ばれたときは,この関数ポインタを呼ぶ.


    5. 変数の実行時の値を保持する領域.

    通常の実装では,これは検索が効率よく出来るようにハッシュなどの方法を 使って実装するのだろうが,ここではソースプログラムを短く書くことを 第一の目的にしたことと,コンパイル時に多少遅くなる可能性はあるが,実行時には 速度的な問題はないことから線形探索を使う最も素朴なものとした.

  2. トークン入力用の文字列バッファ
    トークンリーダが文字列読み込みのために使う文字列領域.

  3. 構文解析用のスタック
    この言語は単純だが,ブロック構造をもったり,if や while の構造を持つ 文脈自由文法であるので,これを構文解析するためのスタック.

右側はコンパイルされたコードを実行するためのデータである.これは次の4つからなる.

  1. コードエリア
    ユーザの関数をコンパイルした結果の仮想マシンのコードがここに入る. 各命令語は,命令のコード番号と引数を1つもつことができる. ジャンプ命令やコール命令は直接このエリアのアドレスを引数のところに 格納するようになっている.ただし,ユーザがプログラムを作るとき, 前方参照や相互再帰など,呼び出す先のアドレスが決まらないときの ことも考えて,引数として文字列を参照するジャンプ命令やコール命令も 用意した.これらは実行時に名前のアドレスが決まったら,アドレスを直接 参照する命令に置き換えられる.

  2. データスタック
    プログラムが実行中に参照するスタック.ここでは整数のスタックにした. ただし,文字列などのアドレスも整数として載せられるようにした. これはアドレスが 64bitで,整数が 32 bit の環境に持っていくときは注意が 必要である.

  3. コントロールスタック
    関数の戻り値のスタックである.

  4. 配列管理表
    配列を生成したときにそのデータを管理するための表である.

これらのデータの用意のもとに,プログラムの処理は次のように進む.

Forth はユーザが入力した命令を即座に実行するモードがあるが,今回はそのモードは 作らなかった.それを作る場合は少し,read-eval-print loop (REPL) を作るために コーディングが必要になってくる.

上記のデータ構造と処理の流れを踏まえて,処理系の主なパートとその行数を 纏めておく.読みやすさのために適当に開けた空行をどこに含めるかなど, 数えるときの揺れがあるかもしれないので,あくまで大雑把な値としてみて欲しい.

表. 言語処理系の行数
No. パート 内容 行数行数
先頭のコメント - 66
インクルード - 77
関数プロトタイプ - 66
名前表管理 定数定義 1 94
トークン種別定義 (enum) 2
トークン番号定義 (enum) 11
名前表の型定義 8
名前表の初期データ定義 45
名前表アクセス関数とマクロ
search(), intern(), clone_string()
27
コードエリア管理 定数 148
型および変数定義 8
コードの記号表示(逆アセンブル) 39
解釈実行 定数定義 2171
スタックなどのデータ宣言 6
本体(巨大 switch 文(30 case))
163
実行時関数 配列:定数定義 171
配列:管理用の型と変数宣言 8
配列:生成関数 23
システム2関数の実行時登録関数 8
諸実行時関数
f_push_clock,f_isqrt, f_readint, f_th
31
コンパイル
(構文解析+コード生成)
定数定義 2209
型と変数宣言 2
コンパイルファイル処理 13
構文解析+コード生成 124
トークンリーダ 68
エラー処理 - 55
main 初期化 55
main (内 argv[] の処理が 20 行) 3232
合計 - -655

で,この表はどうつかうかというと,

全体で C 言語 200 行に抑えるためには,どこをどのくらいに抑える必要があるかな? 配列は作れるかな?
などと思いを巡らせるために使うのである.ちなみに C 言語 200 行でできる可能性が あるかというと,if, while 無しの超簡易アセンブラレベル,変数無し,配列無しの 言語だと,320 行で書いた実績はある.このレベルで昔の TECO (Text Editor and Corrector) の ように1文字コマンドにして,なんとか,チューリング完全で 200 行前後にならんだろうか? もう,殆ど趣味の領域だけど.

以下,「実行系」と「構文解析+コード生成」について個別に議論する.

実行系

仮想機械の実行系は典型的には,次のように switch 文のお化けにするか, あるいは,その次に書いたように,命令のコードや引数から呼び出す関数を決定して それを呼び出すか,あるいは,その融合かになると思う.第3の融合方式はとりあえず置いておき,前者を前2つの方式で処理系のサイズがどうなるかを考えてみよう,ここでは 仮に,前者を(1)巨大 switch 文方式,後者を(2)関数ポインタ方式と呼ぶことにする.

(1)巨大な switch 文の実行系

int exec(start) {
    初期化処理;
    pc = start;
    while (pc が有効な値) {
        switch (pc->code) {
          case I_PUSH:
              push(pc->arg);
              break;
          case I_POP:
              pop();
              break;
            ...
        }
        pc++;
    }
}

この書き方だと,

  1. 1つの機能を実装するのに必要な行数
    処理を case I_... と break; で挟むので,必要な行数は実質的な処理の行数に,
    2×機能数
    加えた行数になる.

  2. 各機能呼び出しのオーバーヘッド
    各機能に飛ぶのは,トークン番号で飛ばすのでそれほどオーバーヘッドは大きくない.

  3. 解釈実行ルーティンの見通し
    解釈実行ルーティンは巨大なswitch 文になるため,見通しが悪い.

  4. 他システムへのスクリプト言語としての組み込み容易性
    何か C で書いた関数を呼び出そうとすると,解釈実行ルーティンを変更しなければ ならないので,別のシステムに組み込み,その機能を呼び出して制御する スクリプト言語としては使いにくい.

(2)関数ポインタを使った実行系

int exec(start) {
    初期化処理;
    pc = start;
    while (pc が有効な値) {
	(*instruction[pc->code])(pc);
        pc++
    }
}

  1. 1つの機能を実装するのに必要な行数
    それぞれの機能で関数定義をしなければならないので,"f() {" と "}" それと 次の改行の 3 行が必要になる.欲を言えば,関数プロトタイプも欲しいので 4 行.ということで,このスタイルだと,機能を実際に実現する行数に
    4×機能数
    加えた行数が必要になる.

  2. 各機能呼び出しのオーバーヘッド
    各機能の呼び出しは,呼び出される関数のアドレスが命令後の引数の部分に 書いてあったとしても,関数呼び出しになるので,上の switch 文よりは オーバーヘッドが生じる.

    また,例えば,ジャンプ命令を実現しようと思うと,呼ばれた関数から どうやって,仮想機械のプログラムカウンタへアクセスするかが問題になる. プログラムカウンタを大域変数にとると,レジスタに割り当てられなくなり 遅くなる恐れがある.

  3. 解釈実行ルーティンの見通し
    解釈実行ルーティンは非常にすっきりした書き方ができる.

  4. 他システムへのスクリプト言語としての組み込み容易性
    解釈実行ルーティンを修正せずに,実行時に関数を登録できるので 他のシステムに組み込み,そのシステムの機能を制御するスクリプト言語として 使いやすい.

上記のことから,今回作成した言語では両方の呼び出しをサポートし,別のシステムに 組み込むときは,実行時にその関数を組み込めるようにした.このとき,どれだけを 解釈実行ルーティンのswitch文で処理するのが良いのかは,言語設計・実装の ポイントとなる.

今回は,switch で 30 個の機能を実装し,171 行になった.どんなものを実装したかを 一応,載せておく.これは,今後,ここでどんな機能が必要になるかを考えるときの 材料になると思うからである.分かりにくい命令は簡単に説明を書いている.

    スタック操作

  1. fi_push int_value
  2. fi_pop
  3. fi_0th ... スタックトップをプシュ
  4. fi_1th ... スタックの2番目をプッシュ
  5. fi_swap ... スタックの上2つを交換

    比較演算

  6. fi_less ... スタックの上2つを取り除きそれらの比較結果をプッシュ
  7. fi_lesseq
  8. fi_eq

    論理演算

  9. fi_not

    算術演算

  10. fi_add ... スタックの上2つを取り除きそれらの演算結果をプッシュ
  11. fi_sub
  12. fi_mult
  13. fi_div
  14. fi_mod

    変数の参照・設定

  15. fi_ref ... スタックをポップし,それで指定されている変数の値をプッシュ
  16. fi_set ... スタックの上2つポップし,それらで指定される変数に値を設定

    配列の基本操作

  17. fi_array ... 配列を生成
  18. fi_free ... 配列を解放
  19. fi_aref ... 配列の要素参照
  20. fi_aset ... 配列の要素設定

    分岐

  21. fi_if ... 条件分岐
  22. fi_jump ... jump

    関数呼び出しと復帰

  23. fi_calls ... 関数呼び出し(文字列で)
  24. fi_call ... 関数呼び出し(アドレスで)
  25. fi_call_sys ... C で作った関数の呼び出し(関数ポインタ方式との融合部分)
  26. fi_pr ... スタックをポップして整数として表示
  27. fi_ret ... 関数呼び出しからの復帰

    出力

  28. fi_pr_str ... スタックをポップして文字列として表示
  29. fi_nl ... 改行を出力

    プログラムの終了

  30. fi_exit ... プログラムの終了

解釈実行における switch 文と 関数ポインタの呼び出しの速度比較

ちょっと長くなるが,巨大な switch 文にした場合と,命令を関数ポインタにして 呼び出した場合の速度比較もしておきたい.そのためのテストプログラムを 次にあげておく.

switch 文と 関数ポインタの呼び出しの速度比較
/*
  Comparison between exec of a switch and exec of function pointers
  for 32bit model
  */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N (100*1000*1000)

#define SLEN 1000

enum {fi_push, fi_sub, fi_jmp, fi_jmpz, fi_end};

struct _INST1 {
    int code;
    void *arg;
}  code1[] = {
    {fi_push, (void *) N},
    {fi_jmpz, (void *) (code1 + 4)},
    {fi_sub,  (void *) 1},
    {fi_jmp,  (void *) (code1 + 1)},
    {fi_end},
};

void fun_push();
void fun_jmpz();
void fun_sub();
void fun_jmp();
void fun_end();

struct _INST2 {
    void (*f)();
    void *arg;
}  code2[] = {
    {fun_push, (void *) N},
    {fun_jmpz, (void *) (code2 + 4)},
    {fun_sub,  (void *) 1},
    {fun_jmp,  (void *) (code2 + 1)},
    {fun_end},
};

int stack[SLEN];
int *sp;

struct _INST1 *pc1;
struct _INST2 *pc2;
int endp;

void exec1(struct _INST1 *code) {
//    register struct _INST1 *pc1; // remove the first // for optimized test
//    register int endp, *sp;      // same as above
    
    pc1 = code;
    sp = stack - 1;
    endp = 0;
    while (!endp) {
        switch (pc1->code) {
          case fi_push: *(++sp) = (int) (pc1->arg); break;
          case fi_sub: *sp -= (int) (pc1->arg); break;
          case fi_jmp: pc1 = (struct _INST1 *) (pc1->arg); continue;
          case fi_jmpz:
            if ((*sp) == 0) {
                pc1 = (struct _INST1 *) (pc1->arg);
                continue;
            }
            break;
          case fi_end: endp = 1;
        }
        pc1++;
    }
}

void fun_push(struct _INST2 *c) {
    (*(++sp)) = (int) (c->arg);
}
void fun_sub(struct _INST2 *c) {
    (*sp) -= (int) (c->arg);
}
void fun_jmpz(struct _INST2 *c) {
    if ((*sp) == 0)
        pc2 = ((struct _INST2 *) (c->arg)) - 1;
}
void fun_jmp(struct _INST2 *c) {
    pc2 = ((struct _INST2 *) (c->arg)) - 1;
}
void fun_end(struct _INST2 *c) {
    endp = 1;
}

void exec2(struct _INST2 *code) {
    pc2 = code;
    endp = 0;
    sp = stack - 1;
    while (!endp) {
        (*(pc2->f))(pc2);
        pc2++;
    }
}

int main(void) {
    int t1;

    t1 = clock();
    exec1(code1);
    printf("time of exec1 = %d mili sec\n", clock() - t1);

    t1 = clock();
    exec2(code2);
    printf("time of exec1 = %d mili sec\n", clock() - t1);
    return 0;
}

exec1() は switch 文で命令の動作を分岐しており,exec2() は,命令の code 部分に 命令を実装する関数ポインタがあるとして,命令語を引数にその関数を呼ぶだけの プログラムである.どちらも実行するプログラムは 100,000,000 から 1 ずつ引いていって 0 になったら終わるプログラムである.命令の関数呼び出しの部分以外で差が出ないように exec1() のループではわざわざ大域変数の, pc1, sp, endp を参照するようにしている. 計測はこの条件で exec1() と exec2() を実行したものと,それから,上で 述べた変数 pc1, sp, endp を exec1() ではレジスタ割り付けできるようにしたもの の3つを比較する.最後のものは,exec1 の最初のコメント記号 // を外して, レジスタ変数 pc1, sp, endp を有効にすればよい.実行環境は今までと 同じである.

表. switch 文と関数ポインタ方式の速度比較
方式 時間(ミリ秒)
exec1() swtch文で分岐 896
exec2() 関数ポインタで呼び出し 1229
exec1() で pc1, sp, endp をレジスタ割り付けしたもの 562

この表を見ると関数ポインタの実装でもそこまで遅くないように思うが, この測定では関数ポインタを呼ぶ分だけを測っている訳ではないから, 解釈実行のループ部分のオーバーヘッドが少なくなれば,もう少し差は開くはずである. 3つ目の測定値を見ると, その他の部分,つまり,プログラムカウンタ pc1 ,データスタック sp ,終わりの判定の endp をレジスタ割り付けできるとずいぶんと速くなっている.


変換系(パーサ,トランスレータ)

今回は,パーサは yacc などのツールを使わずに手でゴリゴリ書いた. やはり,色々なところでコンパイルして使うのに,いちいちパーサジェネレータを まずインストールしてというのは,自分がやるのも人にやらせるのも好きでない. それでパーサの書きやすさと言語仕様の人間への優しさとが,ある折衷案に落ち着くことに なる.ここで言えば,

if {...} {...} {...} v.s. if {...} then {...} else {...}

などだろうか? この例はどちらも人間に優しくないかもしれないが.

どちらにしても,この程度のパーサとコード生成で, 表.言語処理系の行数 に示すように,124 行掛かっている. ここでは if の後に文を3つ読んで,それぞれコード生成を行わないといけないので, パーサのスタックに積む状態として,S_IF1, S_IF2, S_IF3 を用意しておき,関連情報と 一緒にパーサのスタックに積み,3つの文を読むごとに,これらの if の状態を進めていく 処理をしている.

今回開発した言語では,if 以外に, while {...} {...} もあるので,このパーサスタック上の 状態遷移はほぼ2倍になる.これは次回はある程度,状態遷移表のような表を解釈する 形にした方が良いかもしれない.また, ここではスタックを使って非再帰的なプログラムにしたが,もしかしたら,再帰プログラムの 方が簡単に書けるかもしれない.そのうちやってみてうまく行ったらここに書くことにする.


あとがき

ここでは,スタックマシンの系統の仮想機械で実現されるプログラミング言語の 実装方法を検討した.趣味の領域であるが,ツールを使わずに,普通の C 言語で できるだけ短く書くための下になる検討や測定結果を載せた.

Forth を初めて知ったのは,1982 年位だったと思う.大学の4年までは数学専攻 だったが,5年生で初めて計算機の方に方向変えした.そのとき,一緒のゼミに 参加していた友達が確かシャープの MZ なんたらという PC だったと思うが, そういうものを持っていて,「こんな面白い言語があるよ」と教えてくれた. そのときは,「へー,面白いね」と言ったきり,実際には Forth を覚えたわけでは ないので,概念的には知ってるけど,使ったことがないので,どんな使い勝手か まったくわからない言語だった.

それを今回,gForth を使ってみたり,Forth もどきの言語を作ってみたりして 実感としてどんなものか大分分かってきた.んー,スタックがどうなっているか すぐわからなくなる.ハノイの塔の問題でさえ,私にはスタックだけでは うまくプログラミングできない.C 言語みたいに,パラメータを明示する プログラミング言語の有難さがしみじみ分かってくる.

でも,これも処理系が短くできる技なので,なにか他の技法と合わせれば,もっと 使いやすくなるかもしれない.今回は,たまたまやってみて,「どんな使い勝手なんだろう?」 という今までのもやもやした疑問が解消できてよかった.また,すごく小さな言語を 作るのは純粋に興味深い.


後日談および試作用の言語仕様

このページを書いてからも,もう一度,このページに書いたような言語の トランスレータおよびインタープリタを書いている.このバージョンは コンパイラというか構文解析を再帰的に書いたので少し短くなり,440 行で できた.

で,結構,これはいろいろ挑戦してみるのに面白い題材なので,挑戦するための システムの仕様を書いておく.

  1. 言語の仕様
    1. 条件文,ループ,ブロック文があること

    2. 関数定義/呼び出し (再帰関数可能)ができること

    3. データタイプ
      整数,文字列,(実数を実現すればよりポイントが高い)

    4. データスタックあるいは(再起呼び出しで使える)局所変数どちらかがあること

    5. コメントが書けること
      // ... 改行 でも /* ... */ でも,どちらのタイプでもよい.とにかく 実行されない文が書けて,プログラムの説明がプログラムの中に書き込めること

    6. ある程度の演算/操作が用意されていること
      数の演算: +, -, *, /, %
      スタックを使うなら,必要な操作: データのpush, pop, dup, swap, i番目のデータを取得する
      入出力機能: 整数の入出力,文字列の出力
      そのほか:好みに応じて(私は速度計測のためにミリ秒でシステム立ち上げからの時間を返す clock を追加した)

    7. 大域変数があること
      質は問わない.とにかく名前で値の格納域のアクセスができること. 変数名に制限があっても構わない.

    8. 配列があること
      質は問わない.とにかく数で格納域のアクセスができること. 上で書いたものはほとんど裸の malloc 程度の機能しかない.

  2. 処理系の記述言語および処理系が備えている機能
    1. C 言語で記述し,通常のようにインデントされた読みやすいプログラムに なっていること.インデントのスタイルはいろいろあるし,読みやすさの判断は 人によるので,これはあいまいな基準だが,作者自身からみて無理な詰め込み方を していないこと.ただし,作者が通常はやらない凝ったマクロ定義とかで内部 ドメイン特化言語を作るなどは良いとする.たぶん,こういうところがこの 挑戦のだいご味なので.

    2. 言語を実行することができること.行数はこの実行機能まで含んでいること. (1)言語の直接の実行でもよいし, (2)トランスレータ/インタープリタからなっていてもよい. また,(3)機械語に直接変換し,コンピュータで直接実行してもよい.

    3. 速度的にはそれほど遅くないこと.これは単に努力目標.上の 440 行版での fib の再帰プログラムは C 言語で作ったものの 40 ~ 50 倍遅い.

この仕様でもう少し短く, 300 行台には行きそうな気はするのだが(やってないけど),また, 継続してやってみようと思う.

また,言語のとても短い実装として参考文献にも挙げたが

dyama's page
VTL (Very Tiny Language)の実装を七行プログラミングで挑戦してみました
というページを見つけた.直接リンクはしないが,上のタイトルでぐぐれば見つかるだろう. VTL は Basic -like な非常に簡単な言語である.7行といっても,最初の2行にインクルード文 があり,あとは,80 カラムまで詰めて良いみたいなので,80文字 × 5 行 = 400 文字に インクルード文を入れた 430 文字くらいのプログラムである.goto が無いので,その人も 言っているが,「変数が使える電卓」レベルのものだが,私にはなかなかできそうにない.
2019年 4 月 22 日(月)

参考文献

リンク切れを気にしたくないので,直接のリンクは張らないことが多い.申し訳ないが, そこに書いてある名称などで検索していただきたい.


計算機(主にソフトウェア)の話題 へ

圏論を勉強しよう へ
束論を勉強しよう へ
半群論を勉強しよう へ
ホームページトップ(Top of My Homepage)