salmacis: タプルと引数についての設計上の問題

趣味の言語設計、http://d.hatena.ne.jp/propella/20101220/p1 の続きの独り言です。

復習

いよいよ逆転パーサーを実装する事にした。呼びにくいのでコードネーム salmacis という事にする。ただ、今はパーサーの仕事をしてないので、単にパターンマッチの勉強という事にして出来るだけパターン以外の部分は普通に作る事にした。例えば let を使えるようにして、リストを最初の n 番目で二つに分ける関数は次のように書く(コロンはリスト構築子、Haskell と違ってパターンマッチは必ず後ろから前に(一般ケースを先に)動く約束)。

-- 例: first ("hello", 3) の答えは ("hel", "lo")
first = (x:xs, n) ->
  let (xs', ys') = first (xs, (n - 1))
  in  (x:xs', ys')

first = (xs, 0)   -> ([], xs)

のように書ける。逆にこの逆関数、二つのリストを受け取ってくっつけた物と一つ目のリストの要素数は次のように書ける。

-- 例: first~ ("hel", "lo") の答えは ("hello", 3)
first~ = (x:xs, ys) ->
  let (xs', n) = first~ (xs, ys)
  in (x:xs', n + 1)

first~ = ([], ys)   -> (ys, 0)

let の代わりにパターンマッチを使うと、関数 first と逆関数 first~ を一つの表記で次のように書けるだろう。<-> という表記は、関数の時は左から右へ、逆関数の時は右から左へ読む事とする。簡潔だけどパターンマッチがネストすると読みにくい。パズルとしては面白いけど、読むには let を使った普通のプログラムの方が良いかも。

first  = (first' (x, first (xs, ys))) <-> (x:xs, ys)
first  = (xs, 0)                      <-> ([], xs)

first' = (x:xs, n)                    <-> (x, (xs, pred n))

ちなみに、これは Haskell で書くとこのようになるつもり。

{-# OPTIONS -XViewPatterns #-}

first (xs, 0)   = ([], xs)
first (first' -> (x, (first -> (xs, ys)))) = (x:xs, ys)
first' (x:xs, n) = (x, (xs, pred n))

first_ ([], xs) = (xs, 0)
first_ (x:xs, ys) = first_' (x ,first_ (xs, ys))
first_' (x, (xs, n)) = (x:xs, succ n)

タプルと引数についての設計上の問題

実装してて詰まったのが一要素のタプルが必要かどうかだ。

salmacis では、どの関数でもパターン(逆関数)として使えるように関数の引数も返り値も一つのタプルだと言う事にしたい。例えば二つのリストを繋げる append とその逆関数はこんな風に書く。

-- 例: append ("Hello ", "World) の答えは ("Hello World")
append = ((x:xs), ys) <-> (x : append (xs, ys))
append = ([], ys)     <-> (ys)

この場合、返り値は一つなので (ys) を ys と書きたい所だが、それを許して良いものだろうか。別の言い方をすると、一要素タプルとスカラを同一視しても良いだろうか?

一要素のタプルがあると文法が問題になる。括弧は普通優先順位の表記に使われるので、(3 + 4) * 5 と言った時にこの (3 + 4) はタプルなのかスカラなのかが曖昧になる。解決法はタプルに括弧以外の記号を使うと、関数適用が append{"Hello ", "World"} のような見慣れない形になってしまう。

一方で、一要素のタプルが無い、または一要素のタプルとスカラを同一視する事にすると、("Hello World") を "Hello World" と書けるし、優先順位との混同は無くなる。問題は、同一視によって表現が弱まる可能性だ。ここでふと思い出すのが scheme の事。scheme の関数も部分適用が無いので、概念上 scheme の引数は常に一つのリストという風に考えられる。面白いのが、scheme では引数まとめて全部を一つの変数で受けられる事。例えば普通の関数は

((lambda (arg) (print arg)) "hello")
> "hello"

だけど、引数のリストを全部受けて

((lambda arg (print arg)) "hello")
> ("hello")

((lambda arg (print arg)) "hello" "world")
> ("hello" "world")

のような事が出来る。これは可変長引数に便利な技だ。これはスカラと一要素リストが違うから出来る事だ。私は可変長引数が嫌いだし、そもそもタプルは固定長なので不要かもしれないけど、まだ自信が持てない。

まあでも自分が可変長引数を嫌いな事を思い出し、結論としてはとりあえず、一要素タプルとスカラを同一視しようと思う。