やっするやっする。
42 Tokyo advent calendar 2022 16日目を担当する @snara-42 でございやする。
メリークリスマス申し上げやする。

本日は、42のrush(たまに開催される期間限定のつら楽しい課題)にて題材として扱った、
yasl 言語を使って、brainf**k interpreter を作るまでをご紹介しやする。

(文末が「やする」では書く方も読む方も疲れやする。以降はですます調やである調を使いやするのであります)

yasl って？

　yasl でぐぐると見つかる Yet Another Scripting Language とは異なります。

　ヤスル でぐぐると見つかるやすりとも異なります。

課題に添付されていた man を抜粋します。

$ man yasl.0

NAME
     Y.A.S.L. — Multiple‐Stack paradigm language

DESCRIPTION
     YASL is a interpreted language based on a multiple‐reversed‐stack paradigm.  
It has first been design for high‐level accounting and financial operations by non‐IT‐specialist users.
YASL stands for Yasl is an Accounting Stack Language.

YASLは逆スタック指向のインタープリター言語である。非IT専門職のユーザーが財務・会計業務で扱うため開発された。(ほんとに…？~~C言語のほうがまだ簡単そうでやする~~)

Multiple Reversed Stack CONCEPT
     Yasl runtime machine disposes of a specific amount of stack (default is 10). 
Each stack is reversed : it grows up, and push or pop operations are made at the base of the stack.

            "Hello"
            "World"
            17
            1.0
            ‐‐‐‐‐‐‐
    Then push another integer value 11 :

            "Hello"
            "World"
            17
            1.0
            11
            ‐‐‐‐‐‐
     Each stack accepts four different types of data :  integer, string, float and list. 
The Yasl operations are provided to operate on stack elements.
     Some cross‐type operations are allowed, usually the type of the first element will be the result type. 
If a cross‐type operation is meaningless, an error occurs and stops the program.

yaslランタイムマシンはデフォルトで10個のスタックを持っている。各スタックは上方向に伸び、push・popなどの操作は下部で行われる。
各スタックは、整数・文字列・浮動小数点数・リスト(配列) の4種類の型のデータを格納できる。
異なる型どうしの演算が可能な場合は、最初の引数の型と演算結果の型は同じになることが多い。(若干javascript感)
演算できない組み合わせの場合は、ランタイムエラーが発生しプログラムが終了する。(>_<)

PUSH OPERATION
     You can simply push information on a stack. 
A single element alone indicates you want to push it on a stack.

     <integer>
     will push that integer on the current stack.

     "<string>"
     will push the quoted string on the stack.

     <float>.<point>
     will push this floating point number on the stack.

     It is not possible to directely push a list element on the stack.

整数・文字列・浮動小数点数の値を単独で記述することで、その値をスタックに積むことができる。
配列を直接コード中に記述することはできない。

OPERATORS
     To perform operations on the stacks, the folowing operators are available :
     −   + ‐ * / % : the five classic operator. They uses two arguments on the
         input stack, and may not work for all combination of element types.
         In that case, runtime is stopped with an error.
     −   # : count. Add to the output stack the number of elements in the input stack.
     −   ! : drop. Delete the first argument on stack.
     −   = : dup. Duplicate the first argument on stack.
     −   < > <= >= == != : the comparison operators. They use two arguments on stack.
     −   ^ !^ : roll and unroll. The first argument integer N is poped, and
         then the N folowing arguments are rolled or unrolled by one position.
     −   && || ~~ : logical operators. AND and OR uses the first two arguments, NOT only the first one.
     −   << >> : left and right shifts. The second argument is shifted by the first argument times.
     −   & | ~ : binary operators. AND and OR uses the first two arguments,  NOT only the first one.
     −   [] : list. The first argument represents the number of following arguments on stack to put in the list.
     −   ][ : unlist. The first argument is exploded on the stack. The count of created elements is then pushed.
     −   [#] : list count. The number of elements within the first argument on stack is pushed.
     −   ]#[ : get list item. The first argument on stack is the index in the
         second argument of the element to extract.

演算子の説明では push=積む、pop=消費する　と表現することにした。
後置記法なので、演算子の優先度は存在しない。

+ - * / % : おなじみの演算子。2つの引数を消費し、演算結果を積む。数値型の演算はCとほぼ同じ。
（文字列文字列 +はC言語で言うところの strcat()した文字列が、文字列文字列 -は strcmp()結果の整数が、数値文字列 +は sprintf()した文字列が、文字列数値 +は strtol(),strtod()の数値が積まれる。たぶんそんな感じ)

< > <= >= == != : 比較演算。2つの引数を消費し、0 または 1 を積む。
&& || ~~ : 論理演算。AND OR は引数2つを、NOT (Cの!) は引数1つを消費し、0 または 1 を積む。
& | ~ << >> : bit演算。NOT は引数1つ、それ以外は2つを消費し、結果を積む。

# : 個数。引数を消費しない。stackの要素数を積む。
! : 削除。stackの先頭要素を消費する。
= : 複製。引数を消費しない。stackの先頭要素を複製して積む。

^ : 回転。1つの引数nを消費し、stackのn番目の要素を先頭に持ってくる。
!^ : 逆回転。1つの引数nを消費し、次の要素をstackのn番目に持っていく。

[] : 配列化。1つの引数nを消費し、続くn個の要素を消費し1つの配列lstにまとめて積む。
][ : 配列分解。1つの配列(または文字列) lstを消費し、lstの各要素を別々に積み、最後にlstの要素数nを積む。

[#] : len(lst) 配列の要素数。引数を消費しない。先頭の配列lstの要素数nを積む。
]#[ : lst[n] 配列から取り出す。2つの引数nとlstを消費し、lstのn番目の要素を積む。

OPERATION MODIFIERS
     Two modifiers are available in yasl for almost all operations :

−   # : this modifier pop the first argument of the input stack, expects an strictly positive integer, and then repeat the folowing operation this number of times.

−   % : this modifier keep the parameters needed by the operation on the stack, rather than pop them.  It does not affect the # operation modifier.

     Modifiers are inserted before the operation :
     <modifier><operation>

2つの演算修飾子がある。
# : for。1つの引数nを消費し、修飾された演算をn回繰り返す。nは 0より大きい 整数でなければならない。
% : 引数を消費せずに修飾された演算を行う。#演算修飾子には影響しない。

CONTROL STRUCTURE
     A test control structure, and a loop control structure are provided.

− The test structure is defined using the ? operator and the optional : operator :
      ? <operation>
      ? <operation> : <operation>
Depending if the first argument on stack is true, the folowing operation is done. 
If present, the second operation is done when false.

− The loop structure is defined by the @ operator :
      @ <operation>
The operation will be repeated until the first argument on stack becomes false.

制御構造が用意されている。
? : if。1つの引数cを消費し、cが「真」(0や空配列でない)なら後続する演算を行う。
? : : if else。1つの引数cを消費し、cが「真」なら? に後続する演算を行い、cが「偽」なら: に後続する演算を行う。
@ : while。「1つの引数cを消費し、cが「真」なら後続する演算を行う」動作を、cが「偽」になるまで繰り返す。
これのおかげでチューリング完全。

SUBSET AND FUNCTION
     A subset can be created by placing an arbitrary number of operations
     inside parenthesis.
     ( <operation> [<operation> ...] )

     A function can be created by placing an arbitrary number of operations
     inside braces, followed by a function name.
     { <operation> [<operation> ...] } <function_name>

     A previously defined function can be called from anywhere in the same scope,
     by simply mentionning the function name, that will act like other operators.
     The subset and the function are a unique operation in their own scope.

( ... ) で一連の演算を定義できる。
{ ... } name で一連の演算に関数名をつけられる。
(関数の引数や返り値などという概念は言語仕様にないので、こちらでアセンブリみたいな呼び出しルールを決める必要があるかも)

STANDARD LIBRARY
     Yasl comes with a bunch of standard predefined functions.

     −   print : prints out the first stack argument.
     −   read : reads a line from standard input. Does not work in interactive mode.
     −   eval : parse and execute the first string argument.
     −   exit : ends the program, first argument as shell exit code.

標準ライブラリ関数が ~~たったこれだけ~~ 用意されている。
print : 1つの引数を消費し、標準出力する。
read : 標準入力から1行を改行文字まで読み取り、文字列と文字数を積む。
eval : 1つの引数strを消費し、strをyaslコードとして実行する。
exit : 1つの引数nを消費し、終了ステータスnでプログラムを終了させる。
print_stack : 引数を消費しない隠しコマンド。

hello world

いくつか例を載せておきます。
(syntax highlight は js にしています。#が演算子であるような言語をご存知の方は教えてください)

"hello world!\n" // 文字列を stack に積む
print // stack の先頭を消費して出力

"hello " print 
"world!" print 
"\n"     print

// stack は LIFO なので逆順に積む
"\n"
"world!"
"hello " 
3 #(print) // 3回 (pop して出力)

echo

! ! # %? #(print " " print) "\n" print

// 初期状態で stack0 にコマンドライン引数の個数、プログラム名、引数が順に入っている
// stack0: [argc, argv[0], argv[1:]...]
! ! // argc, argv[0] を pop
#   // プログラム名を除いた引数の数 n=argc-1 をpush
// stack0: [n, argv[1:]...]
%? #( // n が0でないなら、n回繰り返す (# で引数を消費)
  print " " print   // 引数と空白を出力 
)
"\n" print  // 最後に改行を出力

最後の空白邪魔 == ? 気にしない : 仕様です

brainƒ_¢k

お待たせしました。やっと本題です。

まずは、入出力の助けになる byteを扱う関数を用意します。
yaslでは、文字列の各要素を1文字の文字列で表します。pythonに似ています。

to_byte: 0〜255に収まるようにする。
c_to_i: "A" との差分を求め、A の ascii code = 65 を足して1文字を数値に変換する。
i_to_c: why, yasl !! 数値→byte 変換は byte列を用意するしかなさそう。
for (i=0; i<256; i++) printf("%c", i); をちょっとescapeして出来上がり。

{ 256 + 256 % } to_byte
{ "A" - 65 + } c_to_i
{
".\t\n\v\f\r !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~ ¡¢£¤¥¦§¨©ª«¬®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ."
	2 ^ ]#[
} i_to_c

brainƒu‹k処理系を実装するには変数がいくつか必要ですが、
変数を演算に使いたいときは stack の先頭に持ってくる必要があります。
よって、よく使う順にstackの先頭から配置していこうと思います。

5...: arr[]
4: ptr
3: str
2: i
1: str[i]

変数を利用したいときに先頭に持ってくるための関数と、あったところに戻すための関数を作ります。

get/set_ptr: ptr を stack 4番目から先頭に持ってくる / 先頭から4番目に戻す。
inc/dec_ptr : ptr の値に ±1する。必要なら arr の先頭/末尾に要素 0 を追加する。
get/set_arr: ptr の指す先 = arr の ptr番目 = stack の ptr+4番目を、先頭に持ってくる / 先頭から元の場所に戻す。

// [1:str[i], 2:i, 3:str, 4:ptr, 5...:arr[]]
{ 4 ^ } get_ptr
{ 4 !^} set_ptr

{ 1 + = # 5 - >= ? (0 # !^)} inc_ptr
{ 1 - = 0 < ? (1 + 0 5 !^) } dec_ptr

{ get_ptr  4 + %^  2 ^ } get_arr
{ 2 !^ %!^ 4 - set_ptr } set_arr

ここまでで、><+-., で使うための関数は実装できたと言っていいでしょう。

最後の難関が[]です。コード中で遭遇したときは、対になる 相手を探す必要があります。
そのためには一時的にもう1つ変数 depth が必要になります。
ここで ptr arr は必要ないので、いまptr のあるところ = stack 4番目に置くことにします。

6...: arr[]
5: ptr
4: depth
3: str
2: i
1: str[i]

get/set_dep: depth を stack 4番目から先頭に持ってくる / 先頭から4番目に戻す。
jump_forward: [ があったとき、対になる ] まで i を進める。
jump_backward: ] があったとき、対になる [ まで i を戻す。
[ に遭遇したら 1 +を、]に遭遇したら 1 -をして、depth が0になったら対が見つかったのでループを抜ける。

// [1:str[i], 2:i, 3:str, 4:dep, 5:ptr, 6...:arr[]]
{ 4 ^ } get_dep
{ 4 !^} set_dep
{ 
	1 set_dep 1
	@( ! 1 + %]#[ 
		= "[" == ? (get_dep (1 +) set_dep)
		= "]" == ? (get_dep (1 -) set_dep)
		get_dep %? (set_dep 1) : (set_dep 0)
	)
	get_dep !
	! ""
} jump_forward
{ 
	-1 set_dep 1
	@( ! 1 - %]#[ 
		= "[" == ? (get_dep (1 +) set_dep)
		= "]" == ? (get_dep (1 -) set_dep)
		get_dep %? (set_dep 1) : (set_dep 0)
	)
	get_dep !
	! ""
} jump_backward

最後に、main のループで使うための関数を用意します。

init : main ループが始まる前に stack を [len,0,argv[1],0,0,0] に初期化する。
get_len : strの長さを先頭に積む。

// [1:len(str), 2:i=0, 3:str=argv[1], 4:ptr=0, 5:...arr[2]]
{
	! !
	[#]
	0 2 !^
	0 4 !^
	2 #(0 # !^)
} init
{ = 3 ^ [#] 2 ^ 4 !^ } get_len

完成！

// [1:str[i], 2:i, 3:str, 4:ptr, 5...:arr[]]
{
init
@ ( %]#[
  = ">" == ? (get_ptr (inc_ptr) set_ptr) 
  = "<" == ? (get_ptr (dec_ptr) set_ptr) 
  = "+" == ? (get_arr (1 + to_byte) set_arr) 
  = "-" == ? (get_arr (1 - to_byte) set_arr) 
  = "." == ? (get_arr (= i_to_c print) set_arr) 
  = "," == ? (get_arr (! read ! 0 ]#[ c_to_i) set_arr) 
  = "[" == ? (get_arr %? set_arr : (set_arr jump_forward) )
  = "]" == ? (get_arr %? (set_arr jump_backward) : set_arr) 
  (! 1 + get_len <)
) // while (++i < len(str))
} main

main

> ./yasl bf.yasl "+++++++++[>++++++++<-]>+++++.<+++++++++[>++<-]>++++++.<+++++++++[>+<-]>++++..+++++++.<+++++++++[>---------<-]>--------.<+++++++++[>+++<-]>++++++++.<+++++++++[>++++<-]>+.<+++++++++[>+<-]>+.<+++++++++[>-<-]>.<+++++++++[>+<-]>+.+.-------.<+++++++++[>-<-]>---.<+++++++++[>++<-]>.<+++++++++[>-----------<-]>------."
Merry Christmas

> ./yasl bf.yasl "+++++++++[>+++++++<-]>+++++++.<+++++++++[>++++<-]>++++++++.<+++++++++[>+++++++++<-]>.<+++++++++[>-<-]>----.<+++++++++[>--------<-]>------.++++.---.------.+++++.<+++++++++[>--------<-]>.<+++++++++[>+++++<-]>+.<+++++++++[>+++<-]>++++++.<+++++++++[>+++++++++<-]>+++.<+++++++++[>--<-]>------.<+++++++++[>-------<-]>.<+++++++++[>----------<-]>--------."
Fröhlich Noël

参考

brainƒµ¢‹ を実装するにあたって、Wikipedia やこちらの記事が参考になりました。

最後に

最後まで読んでいただき感謝いたしやする。
まだまだ荒削りですが、これからも技術をきめ細かく磨いてつやを出していきたいですね。やする・polish だけに。
… 急に寒くなってきましたので皆様ご自愛ください。

明日は @t0r さんが「String.Formatメソッドを再実装してみる」記事を書いてくださるそうです。お楽しみに！

EOF