このブログで Ruby の話をほとんどしない、主に「それ以外のプログラミングの話」担当 e.mattsan です。 最近も慣れないプログラミング言語に触れては脳が汗をかくようなことをしています。
今回はその話をしたいと思います。
…が、本題に入る前にこの言語と関係の深い逆ポーランド記法の話から。 どう関係するかは後半で。
逆ポーランド記法 (RPN)
演算子を後置することが特徴の記法です。
| 日常目にする記法 | 逆ポーランド記法 |
|---|---|
1 + 2 |
1 2 + |
(1 + 5) * (3 + 4) は 1 5 + 3 4 + * と記述でき、括弧が不要になるということでも知られています。
記述が単純になるので、実装も簡単です。
- まず、スタックを用意します。
- 次に、RPN で記述された文字列をトークンに分割します。
- そして、各トークンに対して順に次の操作を適用します。
- 数値ならスタックに積む
- 演算子ならスタックから値を取り出し、それらの演算結果をスタックに積む
これだけです。
実際に 1 5 + 3 4 + * を計算してみましょう。
| # | 入力 | 操作 | スタック |
|---|---|---|---|
| 0 | （初期状態） | [] |
|
| 1 | 1 |
1 をスタックに積む |
[1] |
| 2 | 5 |
5 をスタックに積む |
[1, 5] |
| 3 | + |
スタックから値を 2 つ取り出し、それらの和をスタックに積む | [6] |
| 4 | 3 |
3 をスタックに積む |
[6, 3] |
| 5 | 4 |
4 をスタックに積む |
[6, 3, 4] |
| 6 | + |
スタックから値を 2 つ取り出し、それらの和をスタックに積む | [6, 7] |
| 7 | * |
スタックから値を 2 つ取り出し、それらの積をスタックに積む | [42] |
答え 42 を得ることができました。
RPN 計算機 in Ruby
この手順を愚直に Ruby で書いたのが次のコードです。
def rpn(stack, str) str.split.each do |token| case token when %r/\A\d+\z/ stack.push(token.to_i) when '+' a, b = stack.pop(2) stack.push(a + b) when '-' a, b = stack.pop(2) stack.push(a - b) when '*' a, b = stack.pop(2) stack.push(a * b) when '/' a, b = stack.pop(2) stack.push(a / b) end end end
計算してみましょう。
スタックと RPN で書かれた式を与えて結果を確認します。
stack = [] rpn(stack, '1 5 + 3 4 + *') pp stack #=> [42]
個々の操作の入出力はスタックを介してやり取りされるので、操作を分割しても同じように機能するという面白さがあります。
stack = [] rpn(stack, '1 5') rpn(stack, '+') rpn(stack, '3 4') rpn(stack, '+ *') pp stack #=> [42]
次の例は 3 つ値の平均値を取得する操作です。
stack = [] rpn(stack, '41 42 43') rpn(stack, '+ + 3 /') pp stack #=> [42]
ここで '+ + 3 /' を avg3 という名前の変数に入れると、関数を適用しているような見た目になります。
avg3 = '+ + 3 /' stack = [] rpn(stack, '41 42 43') rpn(stack, avg3) pp stack #=> 42
もっともこの「関数」は、実装した処理系の外側で定義したものなので、これを関数と呼ぶのは無理があるかもしれませんが。
さて、これらの話を踏まえて。 ここから最近いじっているプログラミング言語 Factor の話です。
Factor programming language
Factor というプログラミング言語があります。
（※ Factor のサイトは割と頻繁にダウンしていることがあるようです）
FORTH の系譜に連なる言語で、登場してから 20 余年、そこそこ歴史があります。
Factor の構文は、先ほど実装した RPN 計算機と同じように、操作は値の後ろに配置され値は基本的にスタックで受け渡されます。
REPL で動作を見てみましょう。
IN: scratchpad 1 5 + 3 4 + * --- Data stack: 42
ここで IN: scratchpad は REPL のプロンプトで、--- Data stack: 以下は現在のスタックの状態を示しています。
操作を分割して入力してみると、スタックの状態の変化が見えるようになります。
IN: scratchpad 1 5 --- Data stack: 1 5 IN: scratchpad + --- Data stack: 6 IN: scratchpad 3 4 --- Data stack: 6 3 4 IN: scratchpad + * --- Data stack: 42
3 つ値の平均値を計算してみます。
IN: scratchpad 41 42 43 --- Data stack: 41 42 43 IN: scratchpad + + 3 / --- Data stack: 42
先ほど Ruby で書いた RPN 計算機では、処理系の外で avg3 を定義しました。
これを Factor のプログラムで関数として定義します。
関数定義
: avg3 ( x y z -- a ) + + 3 / ;
ここで ( x y z -- a ) は stack effect declaration と呼ばれるもので、スタックの出入りを示しています。
この例では、この関数は 3 つの値を取り出し 1 つの値を積むということを示しています。 ここに書かれた名前は型や変数名を表しているわけではありません。
トークンは空白で分割されます。
空白は改行に置き換えても大丈夫ですが、間の空白を削除すると 1 つのトークンとして識別してしまうので注意してください。
記号（ (, ), ; など）の前後の空白も必須です。
REPL 上で定義します。
IN: scratchpad : avg3 ( x y z -- a ) + + 3 / ;
使ってみます。
IN: scratchpad 41 42 43 avg3 --- Data stack: 42
+ や - といった操作と同じように、入力となる値の後ろに avg3 と記述することで 3 つの値の平均を計算できるようになりました。
制御構文
Factor でも処理の流れを制御する if が用意されています。
if も、スタックに対する操作であることは変わりません。
記法も後置です。
if を使う例として次のような操作を考えます。
- n が偶数の場合、n を 2 で割る
- n が奇数の場合、n に 3 を掛けて 1 を足す
これを Factor で実装すると次のようなコードになります。
: f ( n -- m ) dup even? [ 2 / ] [ 3 * 1 + ] if ;
一つずつ見ていきましょう。
dup
dup はスタックの先頭にある値を複製します。
値を利用するには、値をスタックから取り出さなければなりません。 取り出してしまうので、その値はスタックから消えてしまいます。 利用しても値が残るようにするために、先に値を複製しておきます。
IN: scratchpad 42 --- Data stack: 42 IN: scratchpad dup --- Data stack: 42 42
even?
even? は整数値の奇偶を判定します。
Factor では真偽値は t と f で表されます。
スタックから取り出した整数値が偶数であれば t を、奇数であれば f をスタックに積みます。
IN: scratchpad 42 dup even? --- Data stack: 42 t
[ と ]
一連の操作を [ と ] で囲むと、それらを一つの値として扱えるようになります。
LISP のクオートと同じようなものと思ってもらってよいと思います。
この値は call などで評価することができます。
IN: scratchpad [ 2 3 + ] --- Data stack: [ 2 3 + ] IN: scratchpad call --- Data stack: 5
ここまでの操作を数値 42 に順に適用すると、スタックの状態はこうなります。
IN: scratchpad 42 dup even? [ 2 / ] [ 3 * 1 + ] --- Data stack: 42 t [ 2 / ] [ 3 * 1 + ]
最後に if です。
if
if は、最初にスタックから 3 つの値を取り出します。
取り出した値を、スタックから取り出した順に ,
,
とすると、まず
の真偽を判定し
t であれば を
f であれば を評価します。
上の節の最後に書いた状態のスタックの例では、最初に t, [ 2 / ], [ 3 * 1 + ] の 3 つの値を取り出します。
ここで条件が t なので [ 2 / ] を評価します。
すでに 3 つの値が取り出されているので、スタックの先頭は 42 になっています。
ここに 2 / が適用されるので、スタックから 42 が取り出され、演算結果の 21 がスタックに積まれます。
IN: scratchpad if --- Data stack: 21
定義した関数 f を利用してみましょう。
f の定義を再掲します。
: f ( n -- m ) dup even? [ 2 / ] [ 3 * 1 + ] if ;
42 に f を 2 回、順に適用します。
IN: scratchpad 42 --- Data stack: 42 IN: scratchpad f --- Data stack: 21 IN: scratchpad f --- Data stack: 64
ちなみに。
ご存知の方も多いと思いますが、この関数 f はコラッツ予想に出てくる関数です。
「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する」という予想です。
42 の場合、 f を 8 回適用すると 1 になります。
IN: scratchpad 42 f f f f f f f f --- Data stack: 1
いつもと違う頭の部分が必要になる
ここまで行数を使って話をしてきましたが、その内容は「数値を計算する」「関数を定義する」「処理を分岐する」だけでした。 これだけですけれども、普段使い慣れている言語とは違う頭の使い方が要求される感じです。
それでも、実際には慣れた言語の書き方や考え方に引きずられているはずで、Factor らしい考え方からは程遠いでしょう。 普段は意識に上らない、自分の「思考の癖」に気付かされる瞬間です。
Factor を自由に使いこなせるほど熟達できるかはわかりません。 それでも新しく見つけた頭の使い方は、いつものプログラミングでも役立つことがあると思います。
たまには、いつものプログラミングから離れて、それ以外のプログラミングをしてみるのはいかがでしょうか。
…わたしみたいにそれ以外ばっかりというのもいかがなものかとは思いますが。
ここにも言語好きプログラミング好きが多数所属しています。
この記事を読んで、自分も新しい思考の道具を試してみたいと感じたら、ネットやイベントで、気軽に声をかけてみてください。
