Kittenでスタックと戯れる

連結型言語

Concatenative language - concatenative.org(日本語訳)によれば、プログラミング言語の分類の1つにconcatenativeかapplicativeかというものがあるそうです。メジャーなプログラミング言語の多くはapplicativeな言語です。つまり、関数を引数に適用(apply)する形でプログラムを記述します。

h(g(f(x, y, z)))

一方で、concatenativeな言語は関数を連結(concatenate)することでプログラムを記述します。

x | y | z | f | g | h

concatenativeな言語の代表格にしてもっとも有名な言語はForthでしょう。あとはPostScriptもそうです。これらの言語はスタックを操作する命令を連ねてプログラムを記述するため、スタック指向とも呼ばれます。

Kitten

Kittenは静的型付けのスタックベース関数型プログラミング言語です。

KittenはHaskellで実装されています。GitHubにある説明の通りにしてビルドしてください。

ビルドしたら、kittenコマンドでインタプリタを起動しましょう。バイナリと同じディレクトリにPrelude.ktnがあるので、バイナリとは異なるディレクトリから実行するときはPrelude.ktnのあるパスを-Lオプションで指定してください。

スタックに積む

さっそくスタックにデータを積んでみましょう。

~$ kitten 
Welcome to Kitten!
Type ':help' for help or ':quit' to quit.
>>> 1 2 3 "hello"

----
1
2
3
"hello"

コードを入力すると、プログラムが実行された後、スタックの状態が表示されます。表示されている下側がトップですね。リテラルは、その値をスタックに積む関数です。関数を空白で区切って連結すると、左側から順番に実行されます。

積んであるデータはdropで捨てられます。スタックの状態はそのまま残っているので、続けて入力しましょう。

>>> drop drop

----
1
2

REPLでは、:cコマンドでスタックをクリアできます。

>>> :c

逆ポーランド記法電卓

Kittenを逆ポーランド記法電卓として使いましょう。2 * 3 + 4 * 5 なら、2と3とを掛けたものと、4と5とを掛けたものとを足す、なので2 3 * 4 5 * +と書けばいいですね。

スタックトップの2つの値はswapで交換できます。

>>> 2 3 * 4 5 * +

----
26
>>> 9 8 * 7 6 * -

----
26
30
>>> swap

----
30
26
>>> /

----
1

浮動小数点数は別の型です。浮動小数点数に対しては +. -. *. /. といった演算子が用意されています。

関数

コード片を波括弧で括ると関数をスタックに積みます。@を使うことで、スタック上の関数に値を適用できます。

>>> {+}

----
<function>
>>> {* +}

----
<function>
<function>
>>> 3 swap 4 swap 5 swap

----
<function>
3
4
5
<function>
>>> @

----
<function>
23
>>> swap 2 swap @

----
25

関数をスタックに積むと何がうれしいのか? そうです、高階関数が使えます。リストに関数をmapしましょう。

>>> [1, 2, 3] {2 *} map

----
[2, 4, 6]

ローカル変数

スタック操作する関数を合成してポイントフリースタイルをやるのもいいですが、やり過ぎるとやはり可読性の低いプログラムになってしまいます。Kittenには値をローカル変数に束縛する機能が用意されています。

>>> "hello" "world"

----
"hello"
"world"
>>> ->{x y} y x

----
"world"
"hello"

->{x y z} といった記法によって、スタックから値を取り出し、変数に束縛します。変数を書くと、その値がまたスタックに積まれます。取り出す値が1つなら波括弧を省略して ->x のように書くことも可能です。

定義

defキーワードで関数を定義できます。

>>> def sayHello {"Hello!" print newline}
>>> sayHello
Hello!

型注釈も可能です。

>>> def addTwo (Int -> Int) {2 +}
>>> 5 addTwo showInt print newline
7
>>> def pushHello42 (-> [Char] Int) {"Hello" 42}
>>> pushHello42 showInt print print newline
42Hello
>>> def dropTwice (a b ->) {drop drop}
>>> "hello" "world" 42 dropTwice print newline
hello

合成

スタック指向言語では、関数の入力と出力が完全に同じでなくても合成できる分、applicativeな言語よりも柔軟です。たとえば2引数とる関数を合成しようとする場合、Haskellでは(.)でうまく合成できないので、次のようになってしまいます。(dotの定義はPointfree - HaskellWikiを参考にしました。)

isMultiple :: Int -> Int -> Bool
isMultiple = (== 0) `dot` mod where dot = (.) . (.)

Kittenではこう書けます。

def isMultiple (Int Int -> Bool) {% 0 =}

FizzBuzz

FizzBuzzの例です。

0 playFizzBuzz

def playFizzBuzz (Int ->):
  -> x
  \if (x 100 <):
    x ++
    dup fizzBuzz print newline
    playFizzBuzz

def fizzBuzz (Int -> [Char]):
  -> x
  \if (x 15 isMultiple):
    "FizzBuzz"
  else if (x 3 isMultiple):
    "Fizz"
  else if (x 5 isMultiple):
    "Buzz"
  else:
    x showInt

def isMultiple (Int Int -> Bool) {% 0 =}

もっとconcatenativeな言語について色々調べてみます。