言語実装 Advent Calendar 2022 の今日の分が空いていたので書いてみた。
この記事の内容
- 397 行の C++ のプログラムで tiny basic のインタプリタを実装する
- ソースコードは記事中に示す（1 ファイルのみで完結）
- 実装したタイニーベーシックのインタプリタ上で遊べる Hit & Blow というゲームも紹介
元ネタは、Peter Chapman さんの tinybasic.c ( https://gist.github.com/pmachapman/661f0fff9814231fde48 )。これを少々書き換えただけである。高度なことはしていない。
言語的にはコメントを付け加えるコマンド rem を追加している。元ネタは C であり、こちらは C++ を使っているので、vector や map を使って、若干コード量が減っているという感じ。行数を減らすため、改行を減らし、適度にコードの密度を上げている。
記事の作り方としては、以前書いて少々話題にして頂いた、「120 行で vi っぽいエディタを作る」https://qiita.com/iigura/items/678aca225956272bdc10 と似たような感じ。
閑話休題。
ちなみに元ネタの方のコメントに、
OMG! This code from the book "C Power User's Guide" by Herbert Schildt, anno 1988, was the peice of code that inspired me to start coding!とあるように、1988 年に出版された "C Poer User's Guide" という本に掲載されているものがオリジナルのようだ。
全ソースコード
開発は macOS 上で行った。以下のファイルを tinyBasic.cpp などと保存しておき、g++ -std=c++20 tinyBasic.cpp とすれば a.out ができ、a.out test.bas などとして実行する。test.bas は、このインタプリタ上で動かしたい BASIC のソースプログラムである。
// TinyBasic397 ( 397 lines tiny basic by Koji Iigura, 2022.)
// original : https://gist.github.com/pmachapman/661f0fff9814231fde48
// to build : g++ -std=c++20 tinyBasic.cpp
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <string>
#include <vector>
#include <map>
enum Config { NumOfLabels=100, LabelLen=10, NumOfGosubNest=25, ProgSize=10000, };
enum Type { Invalid, Delimiter, Variable, Number, Command, String, Quote, };
enum Keyword { INVALID, PRINT, INPUT, IF, THEN, GOTO, FOR, NEXT, TO, GOSUB, RETURN,
END, REM, EOL, FINISHED, };
enum Error { SyntaxError, Parentheses, NoExp, NoEqualSign, NotAVariable, DupLabel,
NoSuchALabel, NoThen, NoTo, MismatchNext, MismatchReturn, SystemError };
struct LoopInfo { int counterVarID; int targetValue; char *loopTopPos; };
char *gProgPos; // holds expression to be analyzed
int gVariables[26]={ 0 };
char gToken[80]; Type gTokenType; Keyword gTokVal;
bool isDelim(char inChar) {
return strchr(" ;,+-<>/*%^=()",inChar)!=0
|| inChar=='\t' || inChar=='\r' || inChar=='\n' || inChar=='\0';
}
bool isWhite(char inChar) { return inChar==' ' || inChar=='\t'; }
std::map<Error,const char*> gErrDict={
{ MismatchReturn, "RETURN without GOSUB" }, { NoTo, "TO expected" },
{ Parentheses, "unbalanced parentheses" }, { NoThen, "THEN expected" },
{ NoEqualSign, "equals sign expected" }, { DupLabel, "duplicate label" },
{ MismatchNext, "NEXT without FOR" }, { SyntaxError, "syntax error" },
{ NoSuchALabel, "undefined label" }, { NoExp, "no expression present" },
{ NotAVariable, "not a variable" }, { SystemError, "system error" },
};
void error(Error inErrorID) {
if(gErrDict.find(inErrorID)==gErrDict.end()) {
fprintf(stderr,"SYSTEM ERROR (no such error ID).\n"); exit(-2);
}
printf("%s\n",gErrDict[inErrorID]); exit(-1);
}
auto gFStack=std::vector<LoopInfo>(); // loop info for FOR-NEXT
void fpush(LoopInfo inLoopInfo) { gFStack.push_back(inLoopInfo); }
LoopInfo fpop() {
if(gFStack.size()==0) { error(MismatchNext); }
LoopInfo loopInfo=gFStack.back(); gFStack.pop_back(); return loopInfo;
}
auto gGStack=std::vector<char*>(); // call stack for GOSUB-RETURN
void gpush(char *inProgPos) { gGStack.push_back(inProgPos); }
char *gpop() {
if(gGStack.size()==0) { error(MismatchReturn); }
char *progPos=gGStack.back(); gGStack.pop_back(); return progPos;
}
std::map<std::string,Keyword> gMap={
{ "print", PRINT }, { "input", INPUT }, { "if", IF }, { "then", THEN },
{ "goto", GOTO }, { "for", FOR }, { "next", NEXT }, { "to", TO },
{ "gosub", GOSUB }, { "return", RETURN }, { "end", END }, { "rem", REM },
};
Keyword lookUpCommand(char *inToken) {
return gMap.find(inToken)==gMap.end() ? INVALID : gMap[inToken];
}
auto gLabelTable=std::map<std::string,char*>();
bool isUniqueLabel(char *inLabel) {
return gLabelTable.find(inLabel)==gLabelTable.end();
}
char *findLabel(char *inLabel) {
return gLabelTable.find(inLabel)==gLabelTable.end() ? NULL : gLabelTable[inLabel];
}
char *loadProgram(char *inFileName) {
FILE *fp=fopen(inFileName,"rb");
if(fp==NULL) { return NULL; }
char *bufTop=(char *)malloc(ProgSize);
if(bufTop!=NULL) {
char *p=bufTop;
for(int i=0; feof(fp)==0 && i<ProgSize; p++,i++) { *p=getc(fp); }
*(p-2)='\0'; // null terminate the program
}
fclose(fp);
return bufTop;
}
Type getToken() {
gTokenType=Invalid; gTokVal=INVALID;
char *dest=gToken;
if(*gProgPos=='\0') { // end of file?
*gToken='\0'; gTokVal=FINISHED; gTokenType=Delimiter; goto leave;
}
while( isWhite(*gProgPos) ) { ++gProgPos; }
if(gProgPos[0]=='\r' && gProgPos[1]=='\n') { // crlf?
gProgPos+=2; gToken[0]='\r'; gToken[1]='\n'; gToken[2]='\0'; gTokVal=EOL;
gTokenType=Delimiter; goto leave;
}
if(*gProgPos=='\n') { // lf?
gProgPos++; gToken[0]='\n'; gToken[1]='\0'; gTokVal=EOL;
gTokenType=Delimiter; goto leave;
}
if( strchr("+-*^/%=;(),><",*gProgPos) ) { // delimiter?
*dest=*gProgPos; gProgPos++; *(++dest)='\0'; gTokenType=Delimiter; goto leave;
}
if(*gProgPos=='"') { // quoted string?
gProgPos++; while(*gProgPos!='"' && *gProgPos!='\r') { *dest++=*gProgPos++; }
if(*gProgPos=='\r') { error(Parentheses); }
gProgPos++; *dest='\0'; gTokenType=Quote; goto leave;
}
if( isdigit(*gProgPos) ) { // number?
while(isDelim(*gProgPos)==false) { *dest++=*gProgPos++; }
*dest='\0'; gTokenType=Number; goto leave;
}
if( isalpha(*gProgPos) ) { // var or command?
while(isDelim(*gProgPos)==false) { *dest++=*gProgPos++; }
gTokenType=String;
}
*dest='\0';
if(gTokenType==String) { // see if a string is a command or a variable
gTokVal=lookUpCommand(gToken); // convert to internal rep
gTokenType = gTokVal==INVALID ? Variable : Command;
}
leave: return gTokenType;
}
// return a token to input stream.
void putBack() { for(char *t=gToken; *t!='\0'; t++) { gProgPos--; } }
int findVar(char *inToken) {
if(isalpha(*inToken)==0) { error(NotAVariable); }
return gVariables[toupper(*gToken)-'A'];
}
// find value of number or variable.
int primitive() {
int ret=-1;
switch(gTokenType) {
case Variable: ret=findVar(gToken); getToken(); break;
case Number: ret=atoi(gToken); getToken(); break;
default: error(SyntaxError);
}
return ret;
}
int unary(char inOp,int inX) { return inOp=='-' ? -inX : inX; }
int arith(char inOp,int inRight,int inLeft) {
int ret=-1;
switch(inOp) {
case '-': ret=inRight-inLeft; break;
case '+': ret=inRight+inLeft; break;
case '*': ret=inRight*inLeft; break;
case '/': ret=inRight/inLeft; break;
case '%': ret=inRight%inLeft; break;
case '^': ret=(int)pow(inRight,inLeft); break;
}
return ret;
}
void level2(int *outResult);
// process parenthesized expression.
void level6(int *outResult) {
if(*gToken=='(' && gTokenType==Delimiter) {
getToken();
level2(outResult);
if(*gToken!=')') { error(Parentheses); }
getToken();
} else {
*outResult=primitive();
}
}
// is a unary + or -.
void level5(int *outResult) {
char op=0;
if(gTokenType==Delimiter && (*gToken=='+' || *gToken=='-')) {
op=*gToken;
getToken();
}
level6(outResult);
if(op!=0) { *outResult=unary(op,*outResult); }
}
// process integer exponent.
void level4(int *outResult) {
level5(outResult);
if(*gToken=='^') {
getToken();
int hold; level4(&hold);
*outResult=arith('^',*outResult,hold);
}
}
// multiply or divide two factors.
void level3(int *outResult) {
level4(outResult);
char op;
while((op=*gToken)=='*' || op=='/' || op=='%') {
getToken();
int hold; level4(&hold);
*outResult=arith(op,*outResult,hold);
}
}
// add or subtract two terms.
void level2(int *outResult) {
level3(outResult);
char op;
while((op=*gToken)=='+' || op=='-') {
getToken();
int hold; level3(&hold);
*outResult=arith(op,*outResult,hold);
}
}
int getExp() {
getToken();
if(*gToken=='\0') { error(NoExp); }
int result; level2(&result);
putBack();
return result;
}
void assignment() {
getToken(); // get the variable name
if(isalpha(*gToken)==0) { error(NotAVariable); }
int var=toupper(*gToken)-'A';
getToken(); // get equal sign
if(*gToken!='=') { error(NoEqualSign); }
gVariables[var]=getExp();
}
// find the start of the next line.
void findEol() {
while(*gProgPos!='\n' && *gProgPos!='\0') { ++gProgPos; }
if( *gProgPos ) { gProgPos++; }
}
// find all labels
void scanLabels() {
char *progPosBackup=gProgPos; // save pointer to top of program
getToken();
if(gTokenType==Number) { gLabelTable[gToken]=gProgPos; }
findEol();
do {
getToken();
if(gTokenType==Number) {
if(isUniqueLabel(gToken)==false) { error(DupLabel); }
gLabelTable[gToken]=gProgPos;
}
if(gTokVal!=EOL) { findEol(); } // if not on a blank line, find next line
} while(gTokVal!=FINISHED);
gProgPos=progPosBackup;
}
void execPrint() {
char lastDelim;
int len=0;
do {
getToken(); // get next list item
if(gTokVal==EOL || gTokVal==FINISHED) { break; }
if(gTokenType==Quote) { // is string
printf("%s",gToken);
len+=strlen(gToken);
getToken();
} else {
// is expression
putBack();
int answer=getExp();
getToken();
len+=printf("%d",answer);
}
lastDelim=*gToken;
if(*gToken==';') { // compute number of spaces to move to next tab
for(int spaces=8-(len%8); spaces>0; spaces--) { printf(" "); }
} else if(*gToken==',') { /* do nothing */
} else if(gTokVal!=EOL && gTokVal!=FINISHED) { error(SyntaxError); }
} while(*gToken==';' || *gToken==',');
if(gTokVal==EOL || gTokVal==FINISHED) {
if(lastDelim!=';' && lastDelim!=',') { printf("\n"); }
} else {
error(SyntaxError);
}
}
// execute a simple form of the BASIC INPUT command
void execInput() {
getToken(); // see if prompt string is present
if(gTokenType==Quote) {
printf("%s",gToken); // if so, print it and check for comma
getToken();
if(*gToken!=',') { error(Parentheses); }
getToken();
} else {
printf("? "); // therwise, prompt with
}
char var=toupper(*gToken)-'A'; // get the input var
int i; scanf("%d",&i); // read input
gVariables[var]=i;
}
void execGoto() {
getToken();
char *pos=findLabel(gToken);
if(pos==NULL) { error(NoSuchALabel); /* label not defined */ }
gProgPos=pos;
}
void execGosub() {
getToken();
char *pos=findLabel(gToken);
if(pos==NULL) { error(NoSuchALabel); }
gpush(gProgPos);
gProgPos=pos;
}
void execReturn() { gProgPos=gpop(); }
void execIf() {
int x=getExp(); // get left expression
getToken(); // get the operator
if(strchr("=<>",*gToken)==0) { error(SyntaxError); }
char op=*gToken;
int y=getExp();
// determine the outcome
int cond=0;
switch(op) {
case '<': cond = x<y ? 1 : 0; break;
case '>': cond = x>y ? 1 : 0; break;
case '=': cond = x==y ? 1 : 0; break;
}
if(cond!=0) { // is true so process target of IF
getToken();
if(gTokVal!=THEN) { error(NoThen); }
// 'else' program execution starts on next line
} else {
findEol();
}
}
void execFor() {
getToken(); // read the control variable
if(isalpha(*gToken)==0) { error(NotAVariable); }
LoopInfo loopInfo; loopInfo.counterVarID=toupper(*gToken)-'A';
getToken(); // read the equals sign
if(*gToken!='=') { error(NoEqualSign); }
int value=getExp();
gVariables[loopInfo.counterVarID]=value; // get initial value
getToken();
if(gTokVal!=TO) { error(NoTo); }
loopInfo.targetValue=getExp(); // get target value
// if loop can execute at least once, push info on stack
if(value>=gVariables[loopInfo.counterVarID]) {
loopInfo.loopTopPos=gProgPos;
fpush(loopInfo);
} else { // otherwise, skip loop code altogether
while(gTokVal!=NEXT) { getToken(); }
}
}
void execNext() {
LoopInfo loopInfo=fpop(); // read the loop info
gVariables[loopInfo.counterVarID]++; // increment control variable
if(gVariables[loopInfo.counterVarID]>loopInfo.targetValue) { return; } // all done
fpush(loopInfo);
gProgPos=loopInfo.loopTopPos; // loop!
}
void execRem() { for(getToken(); gTokVal!=EOL; getToken()) { /* empty */ } }
std::map<Keyword,void (*)()> gCmdMap={
{ PRINT,execPrint }, { INPUT, execInput }, { GOTO,execGoto }, { IF, execIf },
{ GOSUB,execGosub }, { RETURN,execReturn }, { FOR, execFor }, { NEXT,execNext },
{ REM, execRem },
};
int main(int argc,char *argv[]) {
if(argc!=2) { fprintf(stderr,"usage: tinybasic <filename>\n"); exit(-1); }
gProgPos=loadProgram(argv[1]);
if(gProgPos==NULL) { fprintf(stderr,"can not load program.\n"); exit(-1); }
scanLabels(); // find the labels in the program
do {
gTokenType=getToken();
if(gTokenType==Variable) { // check for assignment statement
putBack(); // eturn the var to the input stream
assignment(); // must be assignment statement
} else {
if(gTokVal==END) { break; }
if(gCmdMap.find(gTokVal)!=gCmdMap.end()) { gCmdMap[gTokVal](); }
}
} while(gTokVal!=FINISHED);
return 0;
}
簡単な解説
このインタプリタは BASIC のソースプログラムをメモリ上に一気に読み込んでおき、現在実行中のプログラムの位置を大域変数 gProgPos で示している。実行に際しては都度 getToken() で gProgPos の位置からトークンを読み込み、それらを用いて処理を逐次的に行う。
getToken 関数では、gToken にトークンの文字列を格納し、gTokenType にトークンのタイプ - 変数であるとか、数値であるとか - を格納し、gTokVal にトークンの値を格納する。トークンの値は print コマンドを示す PRINT という値などである。詳細は列挙型 Keyword のところを見てもらえれば分かると思う。
起動すると、最初に引数として与えられたファイルを読み込み、ラベルの処理を行う。ラベルとは goto や gosub の行き先として指定するもので、どうやらこの tiny basic では行頭の整数値をラベルとして扱うようだ。ラベルの値 - といってもラベルとして用いられている行番号の数値ではなく、ジャンプ先の値という意味である（ああ、ややこしい）- は、BASIC のソースコード中の位置である。元のプログラムでは構造体を定義し、その配列を用いて管理していたが、本プログラムは C++ で記述しているので、map 型の gLabelTable を用いて手短に処理が記述できている。
その他、C++ の機能を用いてコード量を削減している部分は、for - next ループの情報を情報を保持する部分と、gosub - return の情報を保持するところである。それぞれ、for ループを占めす f と gosub を示す g を用いて、fpush や gpush などといった関数名で記述されている（ここは元ネタと同じ）。
for ループ用のスタック機構と、gosub - return 用のスタック機構は、vector に丸投げすることにより、コード量の削減を実現している。
式の評価部分が結構な部分を占めている（そりゃまあそうだよね）。getExp 関数が式の評価処理の入り口なので、興味のある人は読んでみると良いと思う。式を項に分解して〜という一連の処理は level2 〜 level6 とレベル分けされた関数で処理されている。個人的には、それぞれのレベルの処理結果を引数として与えている int へのポインタを用いて格納しているところが気になる点である。素直に return で値を返すように変更できないのかな…と思いつつ、今回はリファクタリングを見送った。
サンプルプログラム Hit and Blow
筆者が小学生の時に、学校で非常に人気となったゲームにヒット＆ブローというものがあった。紙と鉛筆でできる対戦型のゲームであるが、そのソリテア版を本 tinyBasic インタプリタのサンプルプログラムとして示す。
ちなみに圧縮すれば、7 行の C プログラムとして記述できる。
「7 行でゲーム（ヒット＆ブロー、または 3 桁 MOO）を作る」https://qiita.com/iigura/items/7cd5d6b355515be936a3
Hit & Blow はボールが 3 つのマスターマインドのようなものである。MOO とか Cow & Bull とも呼ばれているようである https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/papers/gpw96.pdf 。
ゲームとしては、まずコンピュータが 3 桁の数値を考える。012 など、最初に 0 が来ても良い。ただし、各桁が全て異なる数値という制限がある。そのため、001 や 565 などといった数値にはならない。
このコンピュータが考えた数値を、ヒットとブローという情報を元に推測するのがこのゲームの目的である。ちなみに、本 tinyBasic（397 行なので tinyBasic397 と呼ぶ）には乱数生成関数が存在しないので、最初に乱数の種値を入力し、擬似乱数を発生させる。
ヒット数
コンピュータが考えた数（正解）と、ユーザーが入力した数（推測値）において、桁も種類も合っているものの個数をヒットという。正解が 123 であり、推測値が 103 の場合は、1 桁目と 3 桁目が合っているのでヒット数は 2 となる。これを H=2 などと表現する。
ブロー数
ヒット数は位置（桁）も種類（数値）も合っているものであったが、こちらのブロー数は場所（桁の位置）は間違っているが、数字の種類は合っているものの個数を示す。ただし、ヒットした数値はブローの数には入れない。例えば、正解が 123 で推測値が 130 の場合は、130 の 2 桁目の数値 3 のみがブローとして数えられる（最初の 1 も種類は合っているが、位置もあっており、この数値はヒットとして取り扱われるのでブローには計上されない）。
ブローは B で表され、上の例でいえば、正解 123 に対して、推測値 130 を入力すると H=1, B=1 という結果となる。
ゲームの終了
何度か推測値を入力して、全ての桁の数値を当てる、つまり H=3 となる状態となればゲームは終了する。遊び方としては、まずは正解を推測し、慣れてきたたらできるだけ少ない回数で正解を得ることを試みると良いと思う。
ちなみに以下に示すプログラムでは、推測値として負の数を入力すると、ギブアップしたこととなり、正解を表示してゲームは終了する。
サンプルプログラムのソースコード
rem =============================================
rem Hit and Blow by Koji Iigura, 2022.
rem =============================================
print "=== HIT and BLOW ==="
input "input random seed: ",s
gosub 100 rem generate random number (u,v,w)
10 rem game loop
gosub 400 rem user inout (a,b,c)
gosub 500 rem calc H and B
print "H=",h," B=",l
if h=3 then goto 99
goto 10
99 print "Great answer!"
print "YOU WIN!"
end
rem -----------------------------------
100 rem Random, answer is u,v,w
x=s
110 rem retry
for i=1 to 100
x=48271*x
next
x=x%1000
if x<0 then x=-x
z=x
gosub 200 rem Decompose into individual digits
gosub 300 rem Check constraint
if r=1 then goto 190
goto 110 rem retry!
190 rem found number
print ">>> random value is ready."
u=a v=b w=c
return
rem -----------------------------------
200 rem Decompose: z -> a,b,c
a=(z/100)%10
b=(z/10)%10
c=z%10
return
rem -----------------------------------
300 rem Check constraint: a,b,c -> r
rem if ok, r=1 otherwise r=0
r=-1
if a=b then r=0 return
if b=c then r=0 return
if c=a then r=0 return
r=1
return
rem -----------------------------------
400 rem Get user input -> a,b,c
410 rem retry
input "guess the number: ",y
if y<0 then goto 999 rem Give Up
z=y gosub 200 gosub 300
if r=1 then return
print "invalid number. guess again."
goto 410 rem retry
rem -----------------------------------
500 rem Calc H and B
h=0 rem reset Hit
if a=u then h=h+1
if b=v then h=h+1
if c=w then h=h+1
l=0 rem reset Blow
if a=v then l=l+1
if a=w then l=l+1
if b=u then l=l+1
if b=w then l=l+1
if c=u then l=l+1
if c=v then l=l+1
return
999 rem Give Up!
print "--- GAME OVER ---"
print "the anser is ",x
end
ゲーム中の様子
=== HIT and BLOW ===
input random seed: 7
>>> random value is ready.
guess the number: 012
H=0 B=1
guess the number: 345
H=1 B=0
guess the number: 678
H=0 B=0
guess the number: 067
H=0 B=0
guess the number: 167
H=0 B=0
guess the number: 240
H=0 B=1
guess the number: 230
H=0 B=2
guess the number: 239
H=1 B=2
guess the number: 329
H=3 B=0
Great answer!
YOU WIN!
おわりに
ちいさな言語処理系を書くのは楽しい。これまでに作成したものでは、lua を用いて 40 行程で Forth のインタプリタを記述できる。
「38 行の Lua プログラムで Forth インタプリタを作る（内部インタプリタ 6 行、外部インタプリタ 32 行）」
https://qiita.com/iigura/items/a9b0fff73f7f9639ca3c
今回は、元ネタとして挙げた、コンパクトな BASIC インタプリタの実装を見つけたため、C++ でよりコンパクトに記述できないだろうかと試みてみたが、あまり上手くいったとは言えない。行数は半分以下にできたが、改行を取り除いただけのような部分もあり、作者としては納得がいっていない。
Lispy - 「((Pythonで) 書く (Lisp) インタプリタ)」http://www.aoky.net/articles/peter_norvig/lispy.htm - のように、美しく簡潔なものが提示できれば良かったのだが、なかなか難しい。
それはともかくとして、Python で tiny basic を記述するのも面白そうである。
tiny basic のインタプリタを、（できるだけ可読性を有しつつ）どこまでコンパクトに記述できるのか。また機会があれば挑戦してみたいと思う（よりコンパクトな tiny basic の処理系の情報などを見つけた場合はコメント欄に書いてくれれば…と思う）。
おわり。