LoginSignup
90
55

More than 1 year has passed since last update.

言語実装Advent Calendar 2021Day 4
@9_ties(中村 晃一)

機械語手書きから言語処理系をブートストラップする

Last updated at Posted at 2021-12-04

この記事は言語実装のカレンダー | Advent Calendar 2021 - Qiita
https://qiita.com/advent-calendar/2021/lang_dev
の4日目の記事です。

はじめに

昔、アセンブリ言語のみから出発し、GC・継続・オブジェクトシステムなどを持つ比較的高級な言語までブートストラップするということをやりました。いつか再挑戦してみたいと思っていて、正月休みにやりましたら思いのほか動くものになりましたが、死蔵させたまま1年経ってしまいました。勿体無いのでこの機会に紹介して供養します。

前回作ったAmberという処理系はこちら
- リポジトリ: https://github.com/nineties/amber

今回はアセンブリ言語じゃなく ELFファイルの手書き から出発してみたいと思います。ただのお遊びで、そんなことしても役には立ちません。が、計算機と直接対話している感じがして、とても楽しいですよ。あとは、制約の厳しい状況でコードを書くと何か学びがあるかもしれないですね。

リポジトリ: https://github.com/nineties/planckforth

書くのが大変なので非常に小さな実装である必要がありますが、一方でそこそこ使えるものにはしたいです。そこで

  1. 自己拡張機能を持つ非常に小さなインタプリタを開発する。
  2. これを自己拡張する事によって使える言語まで成長させる。

というやり方をすることにします。この手の事はForthでよくやられていることなので何番煎じかわかりませんが、私も同じようにやる事にします。

処理系名称

最初に作るForthの処理系名称は PlanckForth としました。小さいという気持ちの命名です。

(その前に考えた名称 microforth, nanoforth, picoforth, femtoforth, attoforth, zeptoforthは全て存在しました。yoctoforthはなさそうでしたがyocto linux関係と誤解を与えそうなので採用をやめました。アルファベット一文字+Forthも検討しましたがaforthからzforthまで全て存在しました。Forthは作るのが簡単なので大量に実装がありますね。)

動かしてみましょう

手書きバイナリはx86 linux環境向けです。以下の手順で動きます。 ビルド(?)に必要なのは xxd のみ です。

% git clone https://github.com/nineties/planckforth.git
% cd planckforth
% make
xxd -r -c 8 planck.xxd > planck
chmod +x planck

実行ファイルはちょうど 1KB です。

% wc -c < planck
1024

planck.xxd がソースコード(?)です。xxd -rは変換時に右側を無視してくれるので、コメント的に使ってます。

% cat planck.xxd
00000000: 7f45 4c46 0101 0100   # planckforth -
00000008: 0000 0000 0000 0000   # Copyright (C) 2021 nineties
00000010: 0200 0300 0100 0000   ET_EXEC,EM_386,EV_CURRENT
00000018: 7480 0408 3400 0000   e_entry=0x08048074,e_phoff=<phdr>
00000020: 0000 0000 0000 0000   e_shoff,e_flags
(略)

小さな処理系ですので、最初はショボいプログラムしか動かせません。
例えばHello Worldは
kHtketkltkltkotk tkWtkotkrtkltkdtk!tk:k0-tk0k0-Q
というプログラムになります。

% cat example/helloworld.fs
kHtketkltkltkotk tkWtkotkrtkltkdtk!tk:k0-tk0k0-Q
% ./planck < example/helloworld.fs
Hello World!

bootstrap.fs がこれをまともに使えるところまでブートストラップするプログラムです。これの実行後は以下のようにREPLが起動し普通のプログラムが実行できます。

% ./planck < bootstrap.fs
Welcome to PlanckForth 0.0.1 [i386-linux-handwritten]
Copyright (c) 2021 Koichi Nakamura <koichi@idein.jp>
Type 'bye' to exit.

." Hello World!" cr
Hello World!

1234 5678 + . cr
6912

: fib dup 2 < unless
    1- dup recurse
    swap 1- recurse
    +
  then
;

30 fib . cr
832040

ファイルを入力に取ることもできます。

% cat example/fib.fs
: fib dup 2 < unless 1- dup recurse swap 1- recurse + then ;
20 fib . cr
% ./planck < bootstrap.fs example/fib.fs
6765

機械語で手書きされたインタプリタといえども、言語そのものとbootstrap.fsはできるだけマシン/OSに依存しない様に作られています。
従って、他の言語でもランタイムを実装する事ができて、例としてC言語バージョンとPython 3バージョンを用意しました。x86 linux以外の環境でもこちらの実装を使って動かすことができると思います。

% make c
gcc -Wall -O2 others/planck.c -o planck -DCOMPILER="gcc (Debian 8.3.0-6) 8.3.0"
% ./planck < bootstrap.fs
Welcome to PlanckForth 0.0.1 [gcc (Debian 8.3.0-6) 8.3.0]
Copyright (c) 2021 Koichi Nakamura <koichi@idein.jp>
Type 'bye' to exit.

." Hello World!" cr
Hello World!

(Pythonバージョンは起動するまで数分かかります。)

% make python
cp others/planck.py planck
chmod +x planck
% ./planck < bootstrap.fs
Welcome to PlanckForth 0.0.1 [Python 3.7.3]
Copyright (c) 2021 Koichi Nakamura <koichi@idein.jp>
Type 'bye' to exit.

." Hello World!" cr
Hello World!

他言語での実装例、プルリク歓迎です。

ブートストラップの様子

自己拡張によるブートストラップの様子を見てみましょう。最初は言語としての表現力が弱いので bootstrap.fs の冒頭はこんな感じで、全く読めない記号列のプログラムになっています。

% head bootstrap.fs
h@l@h@!h@C+h!k1k0-h@$k:k0-h@k1k0-+$h@C+h!ih@!h@C+h!kefh@!h@C+h!l!
h@l@h@!h@C+h!k1k0-h@$k h@k1k0-+$h@C+h!ih@!h@C+h!kefh@!h@C+h!l!

h@l@ h@!h@C+h! k1k0-h@$ k\h@k1k0-+$ h@C+h!
    i       h@!h@C+h!
    kkf     h@!h@C+h!
    kLf     h@!h@C+h!
    k:k0-   h@!h@C+h!
    k=f     h@!h@C+h!
    kJf     h@!h@C+h!

しかし、末尾では読めるプログラムが書けるようになっています。このように bootstrap.fs の実行中に処理系の自己拡張が行われています。

% tail bootstrap.fs
        next-arg dup argv @ !
        included
    else
        ." Welcome to PlanckForth " version type
        ."  [" runtime type ." ]" cr
        copyright
        ." Type 'bye' to exit." cr
        s" /dev/tty" included
    then
; execute

1st Stage Interpreterの実装

小さなForthというと例えば、バイトのフェッチ、ストアとコールの3命令しかない3-INSTRUCTION FORTHみたいなやつがありますが、これは起動後にユーザープログラム側で機械語を記述していくやり方になるので、マシン/OSに強く依存したユーザープログラムになります。
もちろん、マシン/OSに依存した機能を呼び出すという場面は必ず出てきますが、ある程度高級な言語に育ってからそういう事をしたいです。コアの部分は特定環境に依存しない言語体系にします。

開発にあたってjonesforthを参考に、より小さな言語を考えていきました。まずメモリ領域として

  • Dictionary
  • Data Stack (下位アドレスに伸びる)
  • Return Stack (下位アドレスに伸びる)
  • User Memory

を用意します。Data Stack, Return Stackの要素やアドレスなどのバイト長は4バイト以上の定数(以下 CELL)としました。

Builtinのwordは全てascii 1文字としました。そうすれば起動時には1文字専用のInputとDictionary Lookupがあれば良いので文字列の比較など面倒な実装が不要になります。空白の処理やコメントなども言語仕様から省きます。

また、Forthの文字列はPascal文字列(length-prefixed string)である場合が多いですが、C文字列(null terminated string)にしました。これは個人的な趣味です。従って、多くのForth実装とは互換性がありません。

組み込みのワードセット

以上のようなことを考えながら、ワードセットを考えていくと以下の37ワードを組み込みで用意すれば良さそうだとなりました。

code name stack effect semantics
Q quit ( n -- ) Exit the process
C cell ( -- n ) The size of Cells
h &here ( -- a-addr ) The address of 'here' cell
l &latest ( -- a-addr ) The address of 'latest' cell
k key ( -- c ) Read character
t type ( c -- ) Print character
j jump ( -- ) Unconditional branch
J 0jump ( n -- ) Jump if n == 0
f find ( c -- xt ) Get execution token of c
x execute ( xt -- ... ) Run the execution token
@ fetch ( a-addr -- w ) Load value from addr
! store ( w a-addr -- ) Store value to addr
? cfetch ( c-addr -- c ) Load byte from addr
$ cstore ( c c-addr -- ) Store byte to addr
d dfetch ( -- a-addr ) Get data stack pointer
D dstore ( a-addr -- ) Set data stack pointer
r rfetch ( -- a-addr ) Get return stack pointer
R rstore ( a-addr -- ) Set return stack pointer
i docol ( -- a-addr ) Get the interpreter function
e exit ( -- ) Exit current function
L lit ( -- n ) Load immediate
S litstring ( -- c-addr ) Load string literal
+ add ( a b -- c ) c = (a + b)
- sub ( a b -- c ) c = (a - b)
* mul ( a b -- c ) c = (a * b)
/ divmod ( a b -- c d ) c = (a mod b), d = (a / b)
& and ( a b -- c ) c = (a & b)
| or ( a b -- c ) c = (a | b)
^ xor ( a b -- c ) c = (a ^ b)
< less ( a b -- c ) c = (a < b)
u uless ( a b -- c ) c = (a unsigned< b)
= equal ( a b -- c ) c = (a == b)
{ shl ( a b -- c ) c = a << b (logical)
} shr ( a b -- c ) c = a >> b (logical)
) sar ( a b -- c ) c = a >> b (arithmetic)
v argv ( -- a-addr u ) argv and argc
V version ( -- c-addr ) Runtime infomation string

Dictionary Lookupを行う find だけはループを回す必要がある複雑なワードですが、それ以外は非常に単純なprimitiveのみとなりました。通常Forthでは here と latest はそれらの値を返すwordとして定義されますが、hとlはそれらの値の格納されているcellのアドレスを返すものとして実装されているので注意してください。

1st Stage Interpreter

起動直後のインタプリタはkey, find, executeを順に繰り返し実行するものとします。

  1. 1文字読む (key)
  2. そのexecution tokenを探す (find)
  3. それを実行する (execute)
  4. 1に戻る (jump -4*CELL)

という動作です。4 wordだけの非常に小さな実装です。
これを 1st Stage Interpreter と呼ぶことにします。

冒頭のHello World kHtketkltkltkotk tkWtkotkrtkltkdtk!tk:k0-tk0k0-Q を読んでみましょう。
これを1st stage interpreterで実行すると、まず k が読み込まれ、そのexecution tokenを探して実行します。word k のexecution tokenは key なので、次の1文字 H が読み込まれData stackに積まれます。続いて t が読み込まれ、そのexecution tokenである type が実行されますので、stack topにある H が出力されます。

これを繰り返していって、Hello Worldが出力され最後に Q でプログラムの実行が停止します。途中の k:k0-は':'と'0'の文字コードを引き算して改行コード(10)を作る処理です。

エントリーポイントまで

いきなりバイナリエディタで書き始めるのはしんどいので、asciiで書いてxxd -rで変換することにしました。以下がコードのレイアウトです。

A1DFC4C8-79B7-4147-9211-F93F6E9A0E3C.jpeg

まず、ELF Header, Program Headerを書きます。全体が決まらないと埋められない箇所(アドレス値やファイルサイズなど)は一旦 xxxx xxxx とかで埋めておいて後からfillするみたいな進め方になります。

プログラムをロードするアドレスは 0x08048000 としました(p_vaddr)。
p_offset=0, p_filesz=<file size> なのでファイル全体が 0x08048000 にロードされます。したがって、左端に書いてあるオフセット + 0x08048000 が実際のアドレスになります。

面倒なので、プログラム全体を1つのセグメントにし(e_phnum=1)、読み書き実行の全てが可能なメモリ空間(p_flags=PF_X|PF_W|PF_R)を128KB (p_memsz) 確保しました。

続いて、必須の変数である here, latest 用、argv用に起動時のespを保存しておく領域の3CELLを確保。その後に1st Stage Interpreterのプログラム(key,find,execute,jump,offset)の領域を5CELL分用意。

その次がこのプログラムのエントリポイントとなります。ここではプログラムカウンタとReturn Stack Pointerの初期化、espの保存を行い、Forthプログラムへジャンプしています。
ここまでの136バイトがインタプリタの実装で、残り888バイトはこのインタプリタが使用するDictionaryです。色々サボった実装ではありますが、たしかにForthインタプリタはとても小さく作ることが出来ますね。

間接スレッディング

コメントのところに next と書いてあるものの実体(adff20)は 

lodsl
jmp *(%eax)

です。これは次のようにプログラムカウンタの指すCELLから2回loadした先にジャンプするという動作をします。

  1. Program Counter(%esi)の指すcellからアドレスを %eax にload
  2. Program Counterを1 cell進める
  3. %eax からジャンプ先のアドレスをloadしそこにジャンプ

これがForthの代名詞といっても過言ではない 間接スレッディング(Indirect Threading) です。たった3バイトで書けるんですね。

Dictionaryの実装

その次からBuiltin Word Setを定義するDictionaryとなります。
Dictionaryの各エントリは以下のような構造をしています。

F7BB5B5D-338F-4E7D-A056-C8A98027B5B6.jpeg

まず全体がLinked Listになっており、最初のcellがlink pointer。次の1 byteがWord名の長さとフラグ。Flagは

  • 8bit目: IMMEDIATE bit
  • 7bit目: SMUDGE bit

とします。従って識別子の長さは6bit分、つまり最大で63です。その次に、Wordの名前が埋められます。CELL byte境界でアラインし、次のCELLにCode Pointerと言って飛び先のコードへのアドレスを埋めます。Code PointerのあるCELLをCode Fieldと言って、そのアドレスをCode Field Address(CFA)と言います。

x86命令のコーディングは、以下を見ながら書きました。

各wordの実装は非常に割り切ったものになっています。例えばkeyは1byte毎にsystemcallを呼んでいます。Bufferingの実装が面倒だからです。またEOFに達したらexitします。

00000261: 31c0 50ba 0100 0000   (key) xorl %eax,%eax; pushl %eax; movl $1,%edx;
00000269: 89e1 31db b803 0000   movl %esp,%ecx; xorl %ebx,%ebx (STDIN=0);
00000271: 00cd 8085 c076 ccad   movl $SYS_READ,%eax; int $0x80; test %eax,%eax;
00000279: ff20 0000 0000 0000   jbe 0x08048244(-52); next;

メモリ読み書き命令はアドレスの範囲チェックをしていませんので、間違ったプログラムを書くとすぐにSEGVになります。
また、findはlink pointerのnullチェックをしてませんので、DictionaryにないwordをlookupしてもSEGVになります。

00000160: 4881 0408 0166 0000   f: find
00000168: 6c81 0408 8a24 24b0   movb (%esp),%ah;movb $1,%al;
00000170: 018b 0d58 8004 088b   movl latest,%ecx;<1>movl 4(%ecx),%ebx;
00000178: 5904 6639 c374 048b   cmpw %ax,%bx;je 2f;movl (%ecx),%ecx
00000180: 09eb f483 c108 890c   jmp 1b(-12);<2>addl $8,%ecx;movl %ecx,(%esp)
00000188: 24ad ff20 0000 0000   next;

後に自己拡張を進めて、こういったエラー処理のないサボったwordはより安全なものに置き換えます。

コード全体

以上のような感じでコード(?)を書いていった結果940バイトになりましたので、Copyright文字列とかを埋めてちょうど1024バイトにしました。十分手書き可能なバイト数に収まりました。(実際に手で書きました。)

00000000: 7f45 4c46 0101 0100   # planckforth -
00000008: 0000 0000 0000 0000   # Copyright (C) 2021 nineties
00000010: 0200 0300 0100 0000   ET_EXEC,EM_386,EV_CURRENT
00000018: 7480 0408 3400 0000   e_entry=0x08048074,e_phoff=<phdr>
00000020: 0000 0000 0000 0000   e_shoff,e_flags
00000028: 3400 2000 0100 0000   e_ehsize,e_phentsize,e_phnum,e_shentsize
00000030: 0000 0000 0100 0000   e_shnum,e_shstrndx,<phdr>p_type=PT_LOAD
00000038: 0000 0000 0080 0408   p_offset,p_vaddr=0x08048000
00000040: 0000 0000 0004 0000   p_paddr,p_filesz
00000048: 0000 2000 0700 0000   p_memsz(128KB),p_flags=PF_X|PF_W|PF_R
00000050: 0010 0000 0084 0408   p_align, <here>
00000058: 3882 0408 0000 0000   <latest:init="V">, <sp0>
00000060: c080 0408 f080 0408   <interpreter>key, find
00000068: fc80 0408 d880 0408   execute, jump
00000070: f0ff ffff be60 8004   -16, movl $interpreter, %esi
00000078: 08bd 0080 0608 8925   movl $0x08068000,%ebp; movl %esp,sp0;
00000080: 5c80 0408 adff 2000   next;

00000088: 0000 0000 0151 0000   Q: quit
00000090: 4482 0408 0000 0000
00000094: 8880 0408 0143 0000   C: cell
0000009c: 4c82 0408 0000 0000
000000a0: 9480 0408 0168 0000   h: &here
000000a8: 5182 0408 0000 0000
000000ac: a080 0408 016c 0000   l: &latest
000000b4: 5982 0408 0000 0000
000000b8: ac80 0408 016b 0000   k: key
000000c0: 6182 0408 0000 0000
000000c4: b880 0408 0174 0000   t: type
000000cc: 7b82 0408 0000 0000
000000d0: c480 0408 016a 0000   j: branch
000000d8: 9182 0408 0000 0000
000000dc: d080 0408 014a 0000   J: 0branch
000000e4: 9682 0408 0000 0000
000000e8: dc80 0408 0166 0000   f: find
000000f0: 9f82 0408 0000 0000
000000f4: e880 0408 0178 0000   x: execute
000000fc: bf82 0408 0000 0000
00000100: f480 0408 0140 0000   @: fetch
00000108: c282 0408 0000 0000
0000010c: 0081 0408 0121 0000   !: store
00000114: c982 0408 0000 0000
00000118: 0c81 0408 013f 0000   ?: cfetch
00000120: d082 0408 0000 0000
00000124: 1881 0408 0124 0000   $: cstore
0000012c: d882 0408 0000 0000
00000130: 2481 0408 0164 0000   d: dfetch
00000138: df82 0408 0000 0000
0000013c: 3081 0408 0144 0000   D: dstore
00000144: e382 0408 0000 0000
00000148: 3c81 0408 0172 0000   r: rfetch
00000150: e782 0408 0000 0000
00000154: 4881 0408 0152 0000   R: rstore
0000015c: eb82 0408 0000 0000
00000160: 5481 0408 0169 0000   i: docol
00000168: fd82 0408 0000 0000
0000016c: 6081 0408 0165 0000   e: exit
00000174: 0583 0408 0000 0000
00000178: 6c81 0408 014c 0000   L: lit
00000180: 0e83 0408 0000 0000
00000184: 7881 0408 0153 0000   S: litstring
0000018c: 1383 0408 0000 0000
00000190: 8481 0408 012b 0000   +: add
00000198: 1c83 0408 0000 0000
0000019c: 9081 0408 012d 0000   -: sub
000001a4: 2383 0408 0000 0000
000001a8: 9c81 0408 012a 0000   *: mul
000001b0: 2a83 0408 0000 0000
000001b4: a881 0408 012f 0000   /: divmod
000001bc: 3383 0408 0000 0000
000001c0: b481 0408 0126 0000   &: and
000001c8: 3e83 0408 0000 0000
000001cc: c081 0408 017c 0000   |: or
000001d4: 4583 0408 0000 0000
000001d8: cc81 0408 015e 0000   ^: xor
000001e0: 4c83 0408 0000 0000
000001e4: d881 0408 013c 0000   <: less
000001ec: 5383 0408 0000 0000
000001f0: e481 0408 0175 0000   u: uless (unsigned less)
000001f8: 6183 0408 0000 0000
000001fc: f081 0408 013d 0000   =: equal
00000204: 6f83 0408 0000 0000
00000208: fc81 0408 0128 0000   (: shl
00000210: 7d83 0408 0000 0000
00000214: 0882 0408 0129 0000   ): shr
0000021c: 8583 0408 0000 0000
00000220: 1482 0408 0125 0000   %: sar
00000228: 8d83 0408 0000 0000
0000022c: 2082 0408 0176 0000   v: argv
00000234: 9583 0408 0000 0000
00000238: 2c82 0408 0156 0000   V: version
00000240: a483 0408 0000 0000

00000244: 5bb8 0100 0000 cd80   (quit) popl %ebx; mov $SYS_EXIT,%eax; inx $0x80

0000024c: 6a04 adff 2000 0000   (cell) pushl $4; next;

00000251: 6854 8004 08ad ff20   (&here) pushl $here; next;

00000259: 6858 8004 08ad ff20   (&latest) pushl $latest; next;

00000261: 31c0 50ba 0100 0000   (key) xorl %eax,%eax; pushl %eax; movl $1,%edx;
00000269: 89e1 31db b803 0000   movl %esp,%ecx; xorl %ebx,%ebx (STDIN=0);
00000271: 00cd 8085 c076 ccad   movl $SYS_READ,%eax; int $0x80; test %eax,%eax;
00000279: ff20 0000 0000 0000   jbe 0x08048244(-52); next;

0000027b: ba01 0000 0089 e189   (type) movl $1,%edx; movl %esp,%ecx;
00000283: d3b8 0400 0000 cd80   movl $1,%ebx (STDOUT=1);movl $SYS_WRITE,%eax;
0000028b: 83c4 04ad ff20 0000   int $0x80; addl $4,%esp; next;

00000291: 0336 adff 2000 0000   (branch) addl (%esi),%esi; next;

00000296: 5885 c074 f6ad adff   (0branch) popl %eax; test %eax,%eax;
0000029e: 2000 0000 0000 0000   je 0x08048292(-10); lodsl; next;

0000029f: 8a24 24b0 018b 0d58   (find) movb (%esp),%ah;movb $1,%al;
000002a7: 8004 088b 5904 6639   movl latest,%ecx;<1>movl 4(%ecx),%ebx;
000002af: c374 048b 09eb f483   cmpw %ax,%bx;je 2f;movl (%ecx),%ecx
000002b7: c108 890c 24ad ff20   jmp 1b(-12);<2>addl $8,%ecx;movl %ecx,(%esp); next;

000002bf: 58ff 2000 0000 0000   (execute) popl %eax; jmp *(%eax)

000002c2: 588b 0050 adff 2000   (fetch) popl %eax; movl (%eax),%eax;push %eax; next;

000002c9: 585b 8918 adff 2000   (store) popl %eax; popl %ebx; movl %ebx,(%eax); next

000002d0: 580f be00 50ad ff20   (cfetch) popl %eax; movsbl (%eax),%eax; next;

000002d8: 585b 8818 adff 2000   (cstore) popl %eax; popl %ebx; movb %bl,(%eax); next;

000002df: 54ad ff20 0000 0000   (dfetch) movl %esp,%eax; pushl %eax; next;

000002e3: 5cad ff20 0000 0000   (dstore) popl %eax; movl %eax,%esp; next;

000002e7: 55ad ff20 0000 0000   (rfetch) pushl %ebp; next;

000002eb: 5dad ff20 0000 0000   (rstore) popl %ebp; next;

000002ef: 8d6d fc89 7500 83c0   <docol>rpush %esi; addl $4,%eax
000002f7: 0489 c6ad ff20 0000   movl %eax,%esi; next;

000002fd: 68ef 8204 08ad ff20   (docol) pushl $docol; next;

00000305: 8b75 008d 6d04 adff   (exit) rpop %esi next;
0000030d: 2000 0000 0000 0000

0000030e: ad50 adff 2000 0000   (lit) lodsl; pushl %eax; next;

00000313: ad56 01c6 adff 2000   (litstring)lodsl; pushl %esi; addl %eax,%esi; next;

0000031c: 5801 0424 adff 2000   (add) popl %eax; addl %eax,(%esp); next;

00000323: 5829 0424 adff 2000   (sub) popl %eax; subl %eax,(%esp); next;

0000032a: 585b 0faf c350 adff   (mul) popl %eax; popl %ebx; imul %ebx,%eax
00000332: 2000 0000 0000 0000   pushl %eax; next;

00000333: 31d2 5b58 f7fb 5250   (divmod) xorl %edx,%edx; popl %ebx; popl %eax
0000033b: adff 2000 0000 0000   idiv %ebx; pushl %edx; pushl %eax; next;

0000033e: 5821 0424 adff 2000   (and) popl %eax; andl %eax,(%esp); next;

00000345: 5809 0424 adff 2000   (or) popl %eax; orl %eax,(%esp); next;

0000034c: 5831 0424 adff 2000   (xor) popl %eax; andl %eax,(%esp); next;

00000353: 585b 39c3 0f9c c00f   (less) popl %eax; popl %ebx; cmpl %eax,%ebx
0000035b: b6c0 50ad ff20 0000   setl %al; movzbl %al, %eax; pushl %eax; next;

00000361: 585b 39c3 0f92 c00f   (uless) popl %eax; popl %ebx; cmpl %eax,%ebx
00000369: b6c0 50ad ff20 0000   setb %al; movzbl %al, %eax; pushl %eax; next;

0000036f: 585b 39c3 0f94 c00f   (equal) popl %eax; popl %ebx; cmpl %eax,%ebx
00000377: b6c0 50ad ff20 0000   setl %al; movzbl %al, %eax; pushl %eax; next;

0000037d: 5958 d3e0 50ad ff20   (shl) popl %ecx; popl %eax; shll %cl,%eax;next;

00000385: 5958 d3e8 50ad ff20   (shr) popl %ecx; popl %eax; shrl %cl,%eax;next;

0000038d: 5958 d3f8 50ad ff20   (sar) popl %ecx; popl %eax; sarl %cl,%eax; next;

00000395: 8b05 5c80 0408 8d58   (argv) movl sp0,%eax; leal 4(%eax),%ebx
0000039d: 0453 ff30 adff 2000   pushl %ebx; pushl (%eax); next;

000003a4: 68b0 8304 08ad ff20   (version) pushl $version; next
000003ac: 0000 0000 0000 0000   padding

000003b0: 6933 3836 2d6c 696e  i386-lin
000003b8: 7578 2d68 616e 6477  ux-handw
000003c0: 7269 7474 656e 3a63  ritten:C
000003c8: 6f70 7972 6967 6874  opyright
000003d0: 2028 6329 2032 3032   (c) 202
000003d8: 3120 4b6f 6963 6869  1 Koichi
000003e0: 204e 616b 616d 7572   Nakamur
000003e8: 6120 3c6b 6f69 6368  a <koich
000003f0: 6940 6964 6569 6e2e  i@idein.
000003f8: 6a70 3e00 0000 0000  jp>

2nd Stage Interpreterへ

現時点のPlanckForthプログラムはとても読めた物じゃないので、ここからUser Program側で自己拡張して、次の世代のインタプリタを実装し乗り換えます。
以後 bootstrap.fs の中身を解説していきます。
Forthの自己拡張はDictionaryにWordを追加していくことによって行われます。

空白・改行の処理

起動直後は空白・改行すら扱えませんので辛いです。方針は2つあります。

  • kを空白・改行をスキップするように再実装する
  • ' 'と'\n'をNo-Operationを表すWordとして定義する

前者はループ処理を書く必要があって面倒なので、一旦今のフェーズでは後者を選択しました。
以下がコードです。1行目が '\n'、2行目が ' 'をDictionaryに追加するコードです。

h@l@h@!h@C+h!k1k0-h@$k:k0-h@k1k0-+!h@C+h!ih@!h@C+h!kefh@!h@C+h!l!
h@l@h@!h@C+h!k1k0-h@$k h@k1k0-+!h@C+h!ih@!h@C+h!kefh@!h@C+h!l!

1行目の定義によって '\n' が扱える様になったので、一行目末尾で改行することが出来ます(!)最初の行から処理系の拡張が行われているわけですね。
全く読めないと思うので、手書きで失礼しますが2行目を例に解説します。

B9991BC2-CC1B-4620-BAB7-9E3A90381B46.jpeg

here がUser Memoryの現在の書き込み位置を表す変数なので、これをインクリメントしながらDictionaryのエントリを追加し、最後に latest 変数を今作ったwordを指すように更新します。整数リテラルがない為 k で読んだ文字コードを引き算して整数値を作ります。
この行を実行する事で以下のようなエントリがDictionaryに追加されます。

| link (CELL byte) | 1 | ' ' | 0 | padding(CELL-3 byte) | docol (CELL byte) | exitのCFA (CELL byte) |

ユーザー定義関数は必ずCFAに docol という特別なコードのアドレスを埋めます。docol は

  1. return stackにprogram counterを積む
  2. program counterを docol が埋められている場所の次にセット
  3. next

という処理を実行します。今の例では docol の次は exit ですので何もせず呼び出し元に戻ります。つまり空白を読んだら単に無視するというWordです。

一行コメント

続いてコメントを書けるようにします。このように可読性が極めて低いプログラムでコメントが書けないのはとても辛いです。
こちらもkの再定義じゃなくこのフェーズでは \ を改行まで入力をスキップするWordとして定義する事で実現することにします。

以下がそのコードです。先程と違ってプログラムの構造がかなりわかりやすいですね！空白・改行が使えるってありがたいですね。

h@l@ h@!h@C+h! k1k0-h@$ k\h@k1k0-+$ h@C+h!
    i       h@!h@C+h!
    kkf     h@!h@C+h!
    kLf     h@!h@C+h!
    k:k0-   h@!h@C+h!
    k=f     h@!h@C+h!
    kJf     h@!h@C+h!
    k0k5-C* h@!h@C+h!
    kef     h@!h@C+h!
l!

1行目と最後の行はさっきと同じなので説明を省きます。\ のエントリを作るコードです。

頻出している h@!h@C+h!はstack topをhereの指すアドレスに書き込み、hereをインクリメントする処理で、いわゆるCOMMA operatorです。
User Programの本体は最初に i (docol) を埋めた後に、他のwordのCFAを並べ、最後に e (exit)で抜けます。CFAは f (find)で見つける事ができるので kXf でXのCFAを取ってきてCOMMAで埋めるという形のコードが並びます。

CFAじゃない部分は

  • L (lit)の次の k:k0- は定数10つまり、改行 \n の文字コードです
  • J (0jump)の次の k0k5-C* は -5*CELL でジャンプのオフセットです

つまり \ の動作は

  1. k で入力を積む
  2. 10(\n)を積む
  3. = で比較する
  4. not equal (0)ならば 1に戻る。そうでなければexit

つまり \ を読んだら改行まで読み進める処理となります。

2nd Stage Interpreterの方針

コメントすら書けないという状態は抜けたので、 2nd Stage Interpreter を目指して実装していきます。2nd Stageでは
まず何よりも 複数文字のWord が使えるという所を目指したいです。
そして、自己拡張を助ける機能である immediate modeとcompile mode を導入したいと思います。

これを実現する為に、以下のwordを作って行きます。

  • W ( "name" -- c-addr ): 空白・改行をスキップし、文字列を読み、文字列のアドレスを返す
  • F ( c-addr -- w ): Dictionaryからwordを検索する
  • G ( w -- xt ): WordからCFAを計算
  • M ( —- a-addr ): state変数
    • immediate mode = 0
    • compile mode = 1

とは言ってもいきなりこれらを書くのは大変なので、道具を準備します。

Wordを定義するための命令群

まず頻出のパターン h@h!h@C+h! を,としてDictionaryに登録します。実装は以下のようになります。docolとexitの間にh@!h@C+h!のCFAを順番に並べただけなので簡単です。

\ The COMMA operator
\ ',' ( a -- )  Store a to 'here' and increment 'here' CELL bytes.
h@l@ h@!h@C+h! k1k0-h@$ k,h@k1k0-+$ h@C+h!
    i   h@!h@C+h!   \ docol
    \ store 'a' to here
    khf h@!h@C+h!
    k@f h@!h@C+h!
    k!f h@!h@C+h!
    \ here <- here + CELL
    khf h@!h@C+h!
    k@f h@!h@C+h!
    kCf h@!h@C+h!
    k+f h@!h@C+h!
    khf h@!h@C+h!
    k!f h@!h@C+h!
    \ exit
    kef h@!h@C+h!
l!

続いて,こちらも頻出である kXf を'として登録します。k, f を並べるだけなので簡単ですが、今定義した,を使う事ができ少しコード量が減りました。

\ TICK-like operator
\ '\'' ( "c" -- xt )    Get execution token of following character
\ NB: This definition is different from the usual definition of tick
\ because it does not skip leading spaces and can read only a single
\ character. It will be redefined in later stage.
h@l@, k1k0-h@$ k'h@k1k0-+$ h@C+h!
    i, kkf, kff, kef,
l!

さらに頻出である

h@l@, k1k0-h@$ k<文字>h@k1k0-+$ h@C+h!

の処理を c として登録します。COLON operatorを使う場面ではありますが、compile modeがまだ存在せずCOLONのsemanticsとはかけ離れているので : という記号の使用は避けます。

\ Utility for defining a word
\ 'c' ( "c" -- w )
\ Read character, create new word then push its address.
\ 'latest' will not be updated.
h@l@,
k1k0-h@$ kch@k1k0-+$ h@C+h!
    i, 'h, '@, 'l, '@, ',,
    'L, k1k0-, 'h, '@, '$,                  \ fill 1
    'k, 'h, '@, 'L, k1k0-, '+, '$,          \ fill "c"
    'L, k0k0-, 'h, '@, 'L, k2k0-, '+, '$,   \ fill "\0"
    'h, '@, 'C, '+, 'h, '!,
l!

Stack操作命令

以上の道具を使って、よく使うwordを定義していきます。例えばDROPは以下の様になり、大分シンプルに書けるようになりました。

\ '_' ( a -- ) DROP
c_ i, 'd, 'C, '+, 'D, 'e, l!

ちなみに現時点での動作確認は k でstackに積んで t でプリントする方法でできます。

kA kB _ t \ -> A

同様にしてよく使うDUP、OVER、TOR、FROMR、SWAPを定義しました。

code name stack effect
_ DROP ( a -- )
# DUP ( a -- a a )
o OVER ( a b -- a b a )
{ TOR ( a -- R:a )
} FROMR ( R:a -- a )
~ SWAP ( a b -- b a )

ForthではUser Functionからの戻りアドレスを積むReturn Stackを直接操作する事が出来ます。これにより例外機構を作ったりとか色々できます(簡単に壊れたプログラムも作れます)。また、Return Stackに普通の値を積む事もできるので、一時的な値の退避場所として使う事もできます。TOR,FROMRはその為に使用します。

文字列を扱う為の命令

文字列を扱う命令を作っていきます。使える文字が減ってきたので、必要最低限のものだけです。

  • B: COMMAの1byte版(C-COMMA)
  • m: 複数バイトのCOMMA
  • z: strlen
  • a: 整数のCELLバイト境界への切り上げ
  • A: hereのCELLバイト境界への切り上げ
  • E: 2つの文字列の比較

E はこれまでで最も複雑な命令ですが、上で定義したStack操作命令のお陰で比較的シンプルに書けました。だんだん難しいものが書けるようになり面白いです。(ジャンプのオフセットを定数値で埋めるかhereの差分から計算するか悩みましたが、ただでさえ可読性の低いコードが
より読めなくなるので、ここでは定数で埋めました。)

\ 'E' ( c-addr1 c-addr2 -- flag ) STR=
\ Compate null-terminated strings.
\ Return 1 if they are same 0 otherwise.
cE i,
\ <loop>
    'o, '?, 'o, '?,         \ ( c-addr1 c-addr2 c1 c2 )
    'o, '=, 'J, k=k0-C*,    \ goto <not_equal> if c1<>c2
    'J, kAk0-C*,            \ goto <equal> if c1==0
    'L, k1k0-, '+, '~,      \ increment c-addr2
    'L, k1k0-, '+, '~,      \ increment c-addr1
    'j, k0kC-C*,            \ goto <loop>
\ <not_equal>
    '_, '_, '_, 'L, k0k0-, 'e,
\ <equal>
    '_, '_, 'L, k1k0-, 'e,
l!

複数文字のreadとfind

いよいよ、複数文字のreadとfindを実装します。
まず、入力から空白をスキップした後文字列を読む W を作ります。
Dictionaryのlenフィールドが6bitなので、最大63文字です。ただ、現時点の記述性ではエラー処理が面倒なので、文字列長のチェックは省きます。(毎度の事ながら後のステージでより良い実装を用意し、W は辞書から除いて使えなくします)

静的なバッファを作る為には、以下の様に here を進めて領域を確保し、そのアドレスを L (lit) によって定数としてコード中に埋めるというやり方をします。

D7464946-1F33-4A9F-AC81-0EF09A324E8A.jpeg

また2nd stage用のfind F を実装します。これはすでに定義した E を使って作ることができます。smudge-bitが立っているwordは検索の時に無視するように作ります。

immediate modeとcompile mode

Forthの多くの実装はimmediate modeとcompile modeというモードを持ちます。まず、実行モードを表す変数 M を作ります。いわゆるstate変数です。Forthでは変数もWordとして定義します。
以下の様に、確保した変数用領域のアドレスを返す関数として実現されます。

\ 'M' ( -- a-addr)
\ The state variable
\ 0: immediate mode
\ 1: compile mode
h@ k0k0-,   \ allocate 1 cell and fill 0
cM~ i, 'L, , 'e, l!

2nd Stage Interpreterのメインループ

以上で必要な部品が揃ったので、2nd Stage Interpreterのメインループを作ります。Wordを読んで、immediate modeであるかimmediate-bitが立っている時(immediate wordの時)にexecute, それ以外はcompileするというものです。

\ 'I'
\ The 2nd Stage Interpreter
cI i,
\ <loop>
    'W,                 \ read name from input
    'F,                 \ find word
    'M, '@,             \ read state
    'J, kAk0-C*,        \ goto <immediate> if state=0
\ <compile>
        '#, 'C, '+, '?, \ ( w len+flag )
        'L, k@k@+, '&,  \ test immediate bit
        'L, k0k0-, '=,
        'J, k5k0-C*,    \ goto <immediate> if immediate-bit=1
        'G, ',,         \ compile
        'j, k0kE-C*,    \ goto <loop>
\ <immediate>
        'G, 'x,         \ execute
        'j, k0kI-C*,    \ goto <loop>
l!

Interpreterの乗り換え

I を実行して1st Stageから2nd Stageにスイッチします。

I           \ Enter 2nd Stage
} _         \ Drop 1st stage interpreter from call stack

I を実行した直後から、1文字単位のインタプリタから空白区切りword単位のインタプリタに切り替わりますので、次の行は rC+R と書けない事に注意。また、1st Stageの環境に戻ることは2度とないので、Return StackをPopして捨てます。

3rd Stage Interpreterへ

COLONとSEMICOLON

2nd stage interpreterからcompile modeが使える様になったので、COLONとSEMICOLONを実装することができます。

(これらの前に、TICK 'を1文字版から複数文字版に再定義していますが、説明は省略)

まず、immediate modeとcompile modeをスイッチする [ と ] を定義します。
compile modeからimmediate modeにスイッチする [ はimmediate wordである必要があります。

\ [ immediate ( -- )
\ Switch to immediate mode
c [ i , ' L , k 0 k 0 - , ' M , ' ! , ' e , l !
\ Set immediate-bit of [
l @ C + # { ? k @ k @ + | } $

\ ] ( -- )
\ Switch to compile mode
c ] i , ' L , k 1 k 0 - , ' M , ' ! , ' e , l !

これらを使って、COLON : とSEMICOLON ; を定義します。
: new-word ... ; の様に記述すると、...の部分はcompile modeで実行されます。compile modeでは並んでいるワードを順番にcompileしていってくれるので、これまでのように ' <word> , という書き方は不要です。new-word は ; に達するまで、smudge-bitが立てられた状態になり、dictionary lookupで引っかかりません。ただ、 latest は : の時点で更新されるので latest を参照すれば定義中の word を参照することができます。

\ : ( "name" -- ) COLON
\ Read name, create word with smudge=1,
\ compile 'docol' and enter compile mode.
c : i ,
    ' A ,                   \ align here
    ' h , ' @ ,
    ' l , ' @ , ' , ,       \ fill link
    ' l , ' ! ,             \ update latest
    ' W ,                   \ read name ( addr )
    ' # , ' z , ' # ,       \ ( addr len len )
    ' L , k @ , ' | ,       \ set smudge-bit
    ' B ,                   \ fill length + smudge-bit
    ' m ,                   \ fill name
    ' L , k 0 k 0 - , ' B , \ fill \0
    ' A ,                   \ align here
    ' i , ' , ,             \ compile docol
    ' ] ,                   \ enter compile mode
' e , l !

\ ; ( -- ) SEMICOLON
\ Compile 'exit', unsmudge latest, and enter immediate mode.
c ; i ,
    ' A ,               \ align here
    ' L , ' e , ' , ,   \ compile exit
    ' l , ' @ ,
    ' C , ' + , ' # , ' ? ,
    ' L , k [ k d + ,   \ 0xbf
    ' & , ' ~ , ' $ ,   \ unsmudge
    ' [ ,               \ enter immediate mode
' e , l !
\ Set immediate-bit of ';'
l @ C + # { ? k @ k @ + | } $

ようやく : ... ; でwordが定義できる様になりました。まずは、上のコードで複数回出てきたimmediate-bitを立てる操作の定義をしました。整数リテラルがまだありませんので、最初の3つは [ ... ] でimmediate modeに移って直接lit命令をcompileしています。

: immediate-bit [ ' L , k @ k @ + , ] ; \ 0x80
: smudge-bit    [ ' L , k @ , ] ;       \ 0x40
: length-mask   [ ' L , k o k 0 - , ] ; \ 0x3f

\ ( "name" -- )
: set-immediate
    W F C + # { ? immediate-bit | } $
;

Builtin Wordのリネーム

その後いくつかutilityを作った後、 alias-builtin というwordを定義して、builtin wordの別名を作りました。これで一気に可読性が向上しますね。

alias-builtin bye       Q
alias-builtin cell      C
alias-builtin &here     h
alias-builtin &latest   l
alias-builtin key       k
alias-builtin emit      t
alias-builtin branch    j
alias-builtin 0branch   J
...

普通 new-word を old-word の別名として定義するには new-word を old-word を呼び出す命令として定義すれば十分です。

: new-word old-word ;

ただし、ジャンプオフセットや定数値をオペランドとして持つ j J L S の4命令はこの方法では名前を変えられません。そこで old-word のcode pointerを new-word のcode fieldにコピーする alias-builtin new-word old-word を定義して使っています。この方法でのリネームは、docol を用いるForth Wordに対しては使えません。
毎度の事ながら、bootstrapが一通り完了した後にこういう直接使用されるべきでないwordはdictionaryから削除します。

入力関数の間接呼び出し

このタイミングで、入力関数には一段の間接参照を入れました。
現在の key は1文字毎にsystem callを呼び、EOF(-1)を返さずに終了してしまうというものなので、いずれ再実装した際に
実装を入れ替えられるようにしておきます。

: allot-cell &here @ # cell + &here ! ;

alias-builtin key-old   k

allot-cell : &key  [ ' L , , ] ;
allot-cell : &key! [ ' L , , ] ;

: key   &key @ execute ;    \ ( -- c ) Push -1 at EOF
' key-old &key !

: key!  &key! @ execute ;   \ ( -- c ) Throw exception at EOF
' key-old &key! !

3rd Stage Interpreterの方針

さて、次のステップである3rd Stage Interpreterをどうするか考えますが、 整数リテラル が最も欲しいですね。k o k 0 - みたいな書き方はもうしたくないです。

標準のForthの仕様に従うと、整数リテラルは以下のprefixを持つことができます。prefixがない場合は base という変数の値を底として使用します。(グローバル変数で指定するのどうかと思いつつも一般的なForthの仕様に従うことにしました。)

  • &...: 10進数
  • #...: 10進数
  • $...: 16進数
  • %...: 2進数
  • 0x...: 16進数
  • '. or '.': 文字コード

これを実装する為には、そこそこ複雑な 制御構造 をかける必要があります。また 変数 base を定義する仕組みが必要です。制御構造を実装していく為には、各種 コード生成 のための命令が欲しいです。整数リテラルを作るならついでに 文字列リテラル も欲しいですね。その辺を順に実装していきます。

コード生成命令

コード生成のための命令群を作っていきます。

literal

以下の literal という命令はコンパイル時に n を受け取ってコードを生成します。生成されたコードは実行時に n をpushするものです。

\ compile: ( n -- )
\ runtime: ( -- n )
: literal
    lit lit ,   \ compile lit
    ,           \ compile n
; immediate

このコードよくわからないかもしれないので解説すると、 literal のbodyは以下のようなcellの並びになります。2つ目のlitは1つ目のlitのoperandなので注意。

| lit | lit | , | , |

よって以下の様に実行されます

  1. stackに n が積んである状態で呼び出される
  2. lit 命令が実行され、そのoperandである lit がstackに積まれる
  3. 次の , 命令で lit がcompileされる
  4. 次の , 命令で n がcompileされる

つまり生成されるコード列は| lit | n | つまり n をpushするという命令になります。

この literal を使って例えば 0 というwordを以下の様に定義しています。(まだ整数リテラルがないので、必要な整数値をwordとして定義しています。)

: 0     [ key 0 key 0 - ] literal ;

[ と ] に囲まれた [ key 0 key 0 - ] の部分はimmediate modeになるので 0 の定義時に実行されstackに整数0が積まれます。続いて literal はimmediate wordなのでこれも 0 の定義時に実行され、定数0をpushするコードが生成されます。

直接 lit を使う

: 0 [ ' lit , key 0 key 0 - , ] ;

という書き方も可能ですが、これは lit 命令の次のoperandに 0 が書かれているという実装の詳細を直接記述したものなので望ましくないです。 literal はこれを隠蔽してくれる命令ですね。

[compile]とcompile

他にも例えば [compile] と compile というツールを使います。これらの定義自体の説明は割愛しますが、以下のコードを例に挙動を説明すると g がimmediate wordであるとき

: f
    g
    [compile] g
    compile g
;
  • g: f の定義時に g が実行される (immediate wordなので)
  • [compile] g: f の実行時に g が実行される
  • compile g: f によって生成されたコードの実行時に g が実行される

となります。

スタック操作命令

よく使う命令群を定義していきます。この辺は特に難しいところはないですが、普通のForthのプログラムと全く同じ感じで記述できる様になりましたのでコードを一部掲載。

: drop  sp@ cell+ sp! ;     \ ( w -- )
: dup   sp@ @ ;             \ ( w -- w w )

: >r rp@ rp@ @ rp@ cell - dup rp! ! ! ;         \ ( w -- R:w )
: r> rp@ cell + @ rp@ @ rp@  cell + dup rp! ! ; \ ( R:w -- w)

: swap  sp@ cell + dup @ >r ! r> ;  \ ( a b -- b a )
: rot   >r swap r> swap ;           \ ( a b c -- b c a )
: -rot  swap >r swap r> ;           \ ( a b c -- c a b )
: nip   swap drop ;                 \ ( a b -- a )
: over  >r dup r> swap ;            \ ( a b -- a b a )
: tuck  dup -rot ;                  \ ( a b -- b a b )
: pick  cells sp@ swap + cell + @ ; \ ( wu ... x0 u -- xu ... x0 xu )

制御構造

これらを使って、制御構造を実装していきます。 if や else など、それぞれ単一のwordとして定義され、 if ... else ... という文法があるわけではありません。従って、これらの不整合を起こす事ができるので、多くのforth実装ではstack上にcontextを示すタグを置いて、整合性のチェックを行いますが、今回の実装ではそこまではやりません。

ifとthenの実装は次のようになります。if のコンパイル時はジャンプ先がわかりませんので、場所(orig)をstackに保存しておいて、 then のコンパイル時にバックパッチします。

\ compile: ( -- orig )
\ runtime: ( n -- )
: if
    compile 0branch
    here 0 ,    \ save location of offset, fill dummy
; immediate

\ compile: ( orig -- )
\ runtime: ( -- )
: then
    here        \ ( orig dest )
    over -      \ ( orig offset )
    swap !      \ fill offset to orig
; immediate

create

続いて変数を定義できるようにする為に create というものを定義します。これは

create new-word

と書くと new-word という新しいwordを作ります。new-wordを実行すると new-word 定義完了時の here の値が帰ります。そこで

create new-word <メモリを確保する命令>

という様な書き方をすると、確保された領域のアドレスを new-word で参照する事ができるというものです。これを使って、 variable という命令を定義できます。

: variable create 0 , ;

variable x と書くと0で初期化された1 cell分の領域を持つ変数 x が定義されます。

does>

せっかくなので does> も作りました。これは実行時にwordの定義を書き換えるという、おもしろいsemanticsを持ちます。

create new-word (code1) does> (code2) ;

と書くと create new-word (code1) の部分までは上で書いたような処理が実行されます。つまり変数 new-word を定義し (code1) で領域の確保や初期化が実行されます。その後 does> (code2) ; の実行によって new-word の定義が「スタックに確保した領域のアドレスがある状態で (code2) を実行しexitする」と言うものに書き換えられます。

例えばこれを使って constant 命令を簡単に定義できます。constant 命令とは

value constant new-word

の様にかくと、new-word が value をpushする命令として定義されます。
これの定義は以下の様になっています。

\ ( n "name" -- )
: constant create , does> @ ;

つまり create , で new-word のエントリを作った後1 cell確保しそこに value を書き込むという初期化を行った後、new-word の定義を「確保した領域のアドレスから値をロード(@)する」と言うものになります。

実装方法は色々ありそうですが、私は以下の様に create が生成するコードには何もしない nop 命令を埋めておき、 does> が呼ばれた時にここを (code2) のCFAに書き換えるという方法で作ってみました。

7B001E72-C3C4-4B0B-87AA-B35978B4E984.jpeg

例外機構

エラー処理が必要欲しいので、例外機構もここで作ることにしました。return stackを直接操作できる為、普通の命令として例外を実装できます。
以下のように命令 f を呼ぶ代わりに、そのexecution tokenを　catch に渡して実行すると、どこかで <error-code> throw が呼ばれると catch の箇所まで巻き戻り <error-code> が返ります。

' f catch

現在の環境をreturn stackに保存して、 throw が呼ばれた場合は巻き戻すというわかりやすい実装なので解説は省略します。

整数リテラル、文字列リテラル

以上の道具を使って整数リテラルやついでに文字列リテラルに関する命令を定義していきます。ここら辺はただ書くだけなので解説は省略します。

3rd Stage Interpreter

以上で定義した諸々を使って3rd Stage Interpreterを書く事ができました。(上で説明した以外にもいろいろ実装してますが、その辺は bootstrap.fs を読んでみてください。)

( === 3rd Stage Interpreter === )

create word-buffer s" 64" >number drop cell+ allot drop

: interpret
    word                    \ read name from input
    \ ( addr )
    dup word-buffer strcpy  \ save input
    dup find                \ lookup dictionary
    ?dup if
        \ Found the word
        swap drop
        state @ if
            \ compile mode
            dup cell+ c@ immediate-bit and if
                \ execute immediate word
                >cfa execute
            else
                \ compile the word
                >cfa ,
            then
        else
            \ immediate mode
            >cfa execute
        then
    else
        >number unless
            UNDEFINED-WORD-ERROR throw
        then
        \ Not found
        state @ if
            \ compile mode
            [compile] literal
        then
    then
;

: main
    rdrop   \ drop 2nd stage
    begin
        ['] interpret catch
        ?dup if
            \ lookup error code
            error-list @
            begin ?dup while
                \ ( error-code error-entry )
                dup error>code
                2 pick = if
                    error>message type
                    ." : "
                    word-buffer type cr
                    bye
                then
                error>next
            repeat
            ." Unknown error code: " . cr
            bye
        then
    again
;

main

これで、文字列リテラルや整数リテラルを解釈できるようになりましたので、以下の様な普通のプログラムがかける様になりました。

$ cat bootstrap.fs - | ./planck
." Hello World!" cr
123 456 + . cr

一番最初のHello World
kHtketkltkltkotk tkWtkotkrtkltkdtk!tk:k0-tk0k0-Q
からは隔世の感がありますね。以下はフィボナッチ関数の例です。とても分かりやすくなりましたね(?)

: fib dup 2 < unless 1- dup recurse swap 1- recurse + then ;
30 fib . cr

4th Stage Interpreterへ

4th stage interpreterの方針

3rd stageではまあまあ普通のForthプログラムが書けるようになりました。4th stageでは標準入出力だけじゃなく ファイル入出力 をできる様にしたいです。そうすると included を実装する事ができるので、プログラムを複数ファイルに分割する事ができるようになります。そこまで行けば、 bootstrap.fs から離れ、様々なユーザープログラムを処理したり、ライブラリの拡充していくという事が出来る状態になるはずです。

ファイル入出力をどうやって実装するか？

PlanckForthが元々持っている命令の組み合わせではファイル入出力などOSの機能を呼び出す命令を実装する事はできません。従って実装方法は以下のいずれかになると思います。

  1. コンパイラを書いて次の世代の実行可能ファイルとして高機能なものを生成する
  2. 一番最初の処理系自体に新しい命令を追加する
  3. 実行時に機械語のコードを生成し、それを使って必要な命令を定義する

1だと色々綺麗になったバイナリを新たに生成できるので理想ですが、それをやる為にもファイル入出力等の機能が欲しいです。機械語手書きで2はしんどいです。と言うわけで、今のフェーズでは3で実装し、将来のステージで1をやってスッキリさせるという感じになるかと思います。

しかし、せっかく既にバイナリ手書き、C、pythonの3つの実装があるので、どれでも動かせるように作りたいです。その為には、3で書くことになる環境依存のコードを切り分ける、C言語で言う #if ... #endif みたいなものが必要です。Forthの場合は、条件に応じて読む部分を変える [if] ... [then] という命令がこれに相当します。

が、入力ストリームを操作するという処理をするにはこれまでの入力の処理の実装は単純すぎます。そこで、入力ストリームの高機能化をするわけですが、ファイル入力も同じインタフェースで扱いたいですね。これからファイル入出力を作ろうとしているのに、その実装の為にファイル入出力のインタフェースが欲しいという循環になってしまいます。

といっても別に難しい問題ではなく、fileオブジェクトのインタフェースだけ定めてやって、そのインタフェースに従ってもろもろを実装してやれば良いですね。

  1. file オブジェクトのインタフェースを定義する
  2. 最初は今ある key , type を使って stdin, stdoutの仮実装を与える
  3. ファイル入出力命令を使って、 インタプリタを書き直し [if] ... [then] や include 等を実装する
  4. それらを使ってファイル入出力等の環境依存命令を実装する。
  5. 仮実装をより良い実装に置き換える。

こうすれば、3で作ったものを後から再実装する必要がなくなりますね。こういった実装の隠蔽はプログラミングでは当たり前のようにやる事ですが、ゼロからブートストラップで作っているとありがたみが違います。

構造体

というわけで、fileオブジェクトを作る為、まずは構造体struct ... end-struct を作ります。といっても、先頭アドレスからのオフセットに対して名前を付けるというだけのものなので実装は簡単ですので説明は省略。

fileオブジェクト

以下のような感じで file% オブジェクトを作り、その中に write read flush など具体的な実装への参照を入れます。write-file 等の命令はこの間接参照を通して実際の命令を呼び出すように作ります。

\ File
struct
    cell% field file>fd     \ file descriptor
    cell% field file>read   ( c-addr u fd -- n )
    cell% field file>write  ( c-addr u fd -- n )

    char% field file>fam
    char% FILENAME-MAX * field file>name

    (省略)
end-struct file%

(省略)

\ Write bytes from c-addr u to file, return error-code.
: write-file ( c-addr u file -- e )
    dup writable? unless WRITE-FILE-ERROR exit then
    over 0<= if 3drop WRITE-FILE-ERROR exit then

    dup write-buffer-content BUFSIZE swap - ( space )

(省略)

そして、既にある key を使った stdin の仮実装を与えます。

input-stream

作ったfileオブジェクトを使って、input streamのスタックを作ります。そして仮実装の stdin_ をこれに積んでおきます。

\ input stream stack
struct
    cell% field input>next
    cell% field input>file
    cell% field input>lineno
end-struct inputstream%

variable inputstreams
0 inputstreams !

: push-inputstream ( file -- )
(省略)
;

: pop-inputstream ( -- file )
(省略)
;

stdin_ push-inputstream

4th Stage Interpreterへの乗り換え

入力としてinput streamを使用する様にインタプリタを再実装します。まず、 key や word などの入力を読む命令をinput streamから読むように再定義します。これらは上で一段階の関節参照を入れてますので、中身を入れ替えます。

まず key の新実装を用意し

\ New version of 'key'.
: new-key ( -- c )
    source-buffer-pos @ source-buffer-end @ = if
        \ the buffer is empty
        0 source-buffer-pos !
        0 source-buffer-end !
        increment-lineno

        source-buffer BUFSIZE inputstreams @ input>file @ read-line throw
        if
            \ reached end of line
            dup 0= if
                drop '\n' exit \ empty line
            then
            source-buffer-end +!
        else
            \ reached EOF
            dup 0= if
                drop EOF exit
            then
            source-buffer-end +!
        then
    then
    source-buffer source-buffer-pos @ + c@
    1 source-buffer-pos +!
;

word や4th Stage Interpreterの実装を行い、 以下の箇所で key の実装を入れ替変えた後に 4th Stage Interpreterにスイッチします。

:noname
    rp0 rp! \ drop 3rd stage
    ['] new-key &key !

    ['] interpret-outer catch bye
; execute

[if]

環境依存コードを書く準備が整いましたので、まずはC言語の #if に相当するものを作っていきます。これはジャンプ命令で実装できないので、条件に応じて入力を読み飛ばすプログラムとして実装します。以下のように書いた場合 [if] を見つけたらstack topを見て、真だったら [else]まで実行してその先を [then] まで読み飛ばす、といった感じです。ネストして書ける様に深さを管理します。実装は簡単なので省略。

これによって、以下の様に条件によって命令の定義を切り替える事ができるようになりました。

true [if]
    : f ." true case!" cr ;
[else]
    : f ." false case!" cr ;
[then]

f   \ => true case!

以下のような書き方もできます。

: f
    [ <condition> ] [if]
        ." true case!" cr ;
    [else]
        ." false case!" cr ;
    [then]
;

環境依存命令の実装

さて、もろもろ準備ができたので環境依存のコードを書いていきます。planckforthの V(version)命令にランタイムの情報が入っているので、これを読んで実装をスイッチするように作っています。

( === Environment Dependent Code === )

runtime  s" i386-linux-handwritten" streq [if]

(i386手書きランタイム用の環境依存コード)

[then] \ End of environment dependent code

この中で必要最小限なシステムコール群 (open) (close) (write) (read) などを動的にコードを生成することによって実装していきます。
C や Python などの他言語実装の場合には、わざわざ動的にコード生成する意味ないのであらかじめ処理系にこれらを実装しておきました。
そして、need-defined という命令を用意して、ランタイムによって異なる環境依存なwordがちゃんと用意されているかチェックするようにしています。

need-defined (open)
need-defined (close)
need-defined (write)
need-defined (read)

: open-file ( c-addr fam -- file e )
    2dup (open) dup -1 = if
        ( c-addr fam fd )
        3drop 0 OPEN-FILE-ERROR exit
(省略)
;

i386-linux向け実行時コード生成

こんな感じで、アセンブラを実装していきます。
例えば、以下の部分はレジスタ等のオペランドのエンコーディング。

%000 constant eax immediate
%001 constant ecx immediate
%010 constant edx immediate
%011 constant ebx immediate
%100 constant esp immediate
%101 constant ebp immediate
%110 constant esi immediate
%111 constant edi immediate

: mod-reg-r/m ( mod reg r/m -- u )
    0
    swap 0x7 and or
    swap 0x7 and 8 * or
    swap 0x3 and 64 * or
;

: scale-index-byte ( scale index byte -- u )
    0
    swap 0x7 and or
    swap 0x7 and 8 * or
    swap 0x3 and 64 * or
;

以下は movl 命令のアセンブル

\ movl disp(reg1), reg2
: movmr ( disp reg1 reg2 -- )
    0x8b c, \ opcode
    swap dup %100 = if \ if reg1=esp
        \ ( disp reg2 reg1 )
        %01 -rot mod-reg-r/m c,
        %00 %100 %100 scale-index-byte c,
    else
        \ ( disp reg2 reg1 )
        %01 -rot mod-reg-r/m c,
    then
    c, \ displacement
; immediate

以下がアセンブラ。: <word> ... ;asm と書くと中身をコンパイルした後にコードフィールドをDFAで上書きします。
つまり、<word> が呼ばれると生成された機械語コードに直接ジャンプします。

\ overwrite code field by DFA
: ;asm
    [compile] ; \ finish compilation
    latest dup >dfa swap >cfa !
; immediate

これを使ってシステムコールを呼び出す命令を用意し

: syscall0 ( n -- e )
    eax pop
    int80
    eax push
    next
;asm

以下のようにシステムコール命令を実装します。

: (open) ( c-addr fam -- fd )
    swap SYS-OPEN syscall2
;

ファイル入出力を実装する為にはバッファをヒープメモリに確保できるようにする必要があるので、それらも実装します。

included

以上で元々の目的であって、ファイル入出力や included 等の実装が進められる様になりました。
included の実装は以下の様にファイルを開いてinput streamに積み、インタプリタを実行し、終わったらpopしてファイルを閉じるという感じの簡単な実装でやっています。(本当はファイルの内容をバッファに読んでしまった方が良いのでしょうけど)

: included ( c-addr -- )
    R/O open-file throw
    push-inputstream
    ['] interpret-outer catch drop
    pop-inputstream close-file throw
;

: include ( "name" -- )
    word throw included
;

boostrap.fs の役割完了

上に書いた以外にも他にもいろいろ実装しています。(exportとかprivateとか)
が、以上で大体初期的なbootstrapが完了したので、いよいよ bootstrap.fs を離れます。
その為に、まず一番最初のインタプリタや途中の実装の為に用意したエラーチェック皆無のあぶないwordや今後使わないwordをDictionaryから削除しています。

そして、今後も言語コアに機能追加はあると思うので、それらは今実装した include を使って lib/core.fs という別のファイルに切り出しました。今は中身はあまり無いですが。

そして、もうこの環境に戻ってくる事はないので rdrop で環境を捨てて、引数で与えられたファイルを実行するか標準入力を実行します。

include lib/core.fs

:noname
    rdrop
    argc @ 1 > if
        next-arg dup argv @ !
        included
    else
        ." Welcome to PlanckForth " version type
        ."  [" runtime type ." ]" cr
        copyright
        ." Type 'bye' to exit." cr
        s" /dev/tty" included
    then
; execute

まとめ

以上、機械語の手書きで小さなインタプリタを実装して、そこそこのところまでブートストラップしてみるという試みでした。

今後については、ある程度高級なところまで育てたら、何らかの言語のコンパイラを実装し、さらにそれをセルフホストすることによって積み上げたものから切り離すという事をしたいです。その為ちまちまと lib 以下に配列を実装したりハッシュテーブルを実装したりというのをやっていますが、正月休みとかに息抜きでやるという程度なので、進捗はめちゃくちゃ遅いか止まってしまってしまうと思います。

とりあえずとても楽しかったです。ぜひ皆さんもこういう遊びをしてみてください。

90
55
1

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
Sign upLogin
90
55