sh上で動くスタック指向言語を作った

shの戻り値が貧弱すぎる問題ついて考えているうち、shにスタック指向言語らしきものを埋め込んでいた。後半見るように文字列の戻り値を返す方式さえあれば、shにコレクション型もレコード型も後から追加可能である。

コード例

$ , 1 , 2 p
, 1 , 2
$ plus , 3 , 1 p
, 3 , 3 , 1
$ minus mul p
, 6

説明

• "," は次の値をスタックにプッシュすることを表す。
• "p" はforthの "." のようにスタックの状態を表示する。
• "plus" はスタックを2つ取って和をスタックに積む。"minus" (差), "mul" (積)も同様。

仕組み

いきなり残念なお知らせだが、shは適用型言語なので行の最初はコマンドであり、データではない。何が言いたいかというとforthのような以下のコードはかけない。

1 2 + 3 1 - *

しかも、shellには型がないのでコマンドと文字列を判別する方法がない。そのため、引数をデータだとみなす関数を一つ作成する。

$ func 1
$ p
, 1

要するにこれはpushである。プッシュが行われるとスタックの1番目を表す変数STACK1に1がセットされる。push関数に対しaliasを張り "," コマンドを作成する。

$ , 1
$ p
, 1

あとは改行なしにコマンドを繋げることができればよい。

$ , 1 , 2

上記のコードでは "," コマンドの第２引数以降に残りのコマンドが渡るので、第２引数以降をevalすればよい。

$ , 1 , 2 plus , 3 , 1 minus mul p
      ---------------------------- この部分をeval

コレクション型

コレクション型をスタックするコマンド ",[" を追加する。

$ ,[ apple , "'apple'" , "red apple" ] p
, apple \'apple\' 'red apple' 
$ , 1 index p
, 'apple'
$ unit p
, \'apple\' 
$ , orange cons p
, orange \'apple\' 
$ , banana add p
, orange \'apple\' banana 
$ , 2 drop p
, banana 

mapもfilterもある。
※"cmd1" は引数にスタックを1つ分加えて実行する。

$ ,[ apple , "'apple'" , "red apple" ] , 'dup cmd1 echo' map
apple
'apple'
red apple
$ ,[ apple , "'apple'" , "red apple" ] , 'dup , "* *" match' filter p
, 'red apple' 

以下のコードは連想リスト的なものを作成してlookupする。

$ ,[[ apple , 150 ] ,[ orange , 98 ] ,[ banana , 100 ]] , orange lookup p
, 98

レコード型

レコード型を定義する関数 "data" を追加する。

$ data human name age blood_type

これにより、human型データをスタックするhuman関数が作成される。
※"var_" はスタックを引数に代入するコマンドである。

$ , taro , 18 , A human
$ var_ human1
$ , "$human1" name p
, taro
$ pop , "$human1" , jiro set_name p
, human jiro 18 A

別のレコード型で同一フィールド名を使用しても適切にディスパッチされる。

$ data animal type weight length
$ data bird weight length
$ , snail , 50 , 10 animal var_ snail
$ , 1000 , 25 bird var_ bird
$ , "$bird" weight p
, 1000
$ pop , "$snail" weight p
, 50

##適用型スタイル
いちいちスタックに置くのもまどろっこしいものは引数として渡せる。
通常の関数は最後に "_" をつけると適用型スタイルで呼び出せる。

$ , 1 + 1 x 3 p
, 6
$ unit add_ A map_ 'dup cmd1 echo'
6
A
$ popall
$ human_ taro 18 A  set_age_ 19 p
, human taro 19 A 

##関数合成
aliasで関数合成ができる。

$ alias sqrt='dup mul'
$ , 2 sqrt p
, 4

##再帰
再帰用にlinrec、tailrec、binrecを用意している。

###階乗

$ , 5 , 'dup le_ 1' , '' , 'dup - 1' , mul linrec p
, 120

###フィボナッチ数列

$ , 6 , 'dup le_ 2' , 'pop , 1' , '- 1 dup - 1' , plus binrec p
, 8

ただし

速度は20分の1になる。