線形

Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)

ここのところ，行き帰りのバスの中で，上の本を読んでScalaというプログラミング言語を勉強しています．Rubyが国産・純オブジェクト指向・スクリプト言語として名を馳せたのに対して，このScalaはJavaとの相互運用性を持つ・オブジェクト指向&関数型言語，といったところのようです．
Groovy，Gauche，Erlangと，プログラミング言語の解説書を読んできましたがいずれも挫折．Scalaのこの本は，タイトル通りstep-by-stepで言語独特の技法と既存言語との違いを学べて，長続きしそうです．
プログラムはまだ書いていません．「_」の文字がいろいろな意味で使われていて，いまいちしっくりきません．それと，どの辺がscalableなのか，まだ分かっていません．
ともあれ読み進めていくと…

scala> def simplifyAdd(e: Expr) = e match {
         case BinOp("+", x, x) => BinOp("*", x, Number(2))
         case _ => e
       }
<console>:10: error: x is already defined as value x
        case BinOp("+", x, x) => BinOp("*", x, Number(2))
                           ^

これが失敗するのは，Scalaがパターンを線形(linear)なものに制限しているからである．パターン変数は，パターンの中で1度しか登場させることができない．しかし，リスト15.14のように，パターンガード(pattern guard)を使って書き換えればエラーは起きない．
リスト15.14 パターンガードを持つマッチ式

scala> def simplifyAdd(e: Expr) = e match {
         case BinOp("+", x, y) if x == y =>
	   BinOp("*", x, Number(2))
         case _ => e
       }
simplifyAdd: (Expr)Expr

パターンガードはパターンの後ろに付けて，ifから始める．(略)
(pp.260-261)

パターンとかマッチとかいうと，正規表現を連想してしまいがちですが，上の記述はそうではなく，あるオブジェクト（上の例ではsimplifyAddメソッドの引数e）がマッチする条件に応じて，返す値が異なるという仕掛けです*1．match〜caseはRubyのcase〜whenに似ています．「case _ =>」はRubyでいう（caseにおける）else，あるいはシェルスクリプトのcase〜esacの中に書く「*)」に相当します．
私が関心を寄せたのは，実はそこではありませんでした．「線形(linear)」という言葉の使い方です．
大学では，線形代数だとか，微積分や応用解析の中で線形性が出てきます．時間計算量がO(n)のものは，線形時間と言います．線形リストというデータ構造も，学びました．
上記引用の「線形」は，これのどの意味とも異なります．項の中に，同一の変数が2回以上現れないことを言います．実際，「BinOp("+", x, x)」では，変数xが2回現れているのでダメ，というわけです．
この意味の線形性は，授業ではなく研究をしていて知りました．

いきなりですが問題です．
(略)
この問題は，私が大学院に入り暗号の研究をすると決めたときに，教授から研究の大まかな目標（項書換え系を用いて暗号プロトコルの安全性を検証できるようにすること）を聞いた上で，「まず考えてみなさい」と言われた課題です．

例題から始めよう - わさっき

このあたりの話題から離れて10年になりますが，調べ直すと，項書換え系ではよく出てくる概念のようで，例えばhttp://www.sakabe.i.is.nagoya-u.ac.jp/~sakai/papers/tokai03-okamo.pdfにも，『どの変数も高々1回しか現れない項は線形であるといい，どの書換え規則の右辺も線形なTRSは右線形であるという．』とあります．
なぜ暗号で線形なのかというと，対称暗号における暗号化と復号の関係式，

D(x,E(x,y))→y

です．これは「平文yを鍵kで暗号化したもの（E(x,y)）に対して，それを鍵kで復号する（左辺）と，元の平文y（右辺）が得られる」という意味です．「→」の左側，すなわち左辺には変数xが2回出現するので，この項は線形ではありません（言ってみれば，左線形性を持たないということです）．しかし右辺は線形な項です．直感的には，右線形でない書換え規則を適用すると，式のコピーができるのですが，その後そのコピーが別々に書き換えられると，同一性を保持できない（同じものだから同じように書き換えていってもらわないと!）ため都合が悪い，だったと記憶します．
ついでなので，「いきなりですが問題です」の答えを書いておきます．

D(D(K(c),E(K(c),D(K(a),E(K(a),r)))),E(r,m)) ⇒* m

という関係によって，安全でないという結論になります．AliceでもBobでもないがmを知りたいユーザをCharlieとして，Trentと鍵K(c)を共有するものとします．「E(K(c),D(K(a),X))」の部分は，TrentにX, a, cを渡すと帰ってくる情報です．
左辺に対して「D(x,E(x,y))」にマッチする箇所を見つけてそこをyに置き換えて行く操作を繰り返せば，最終的にmになります．「⇒*」は，「→」を0回以上適用してできる，項の関係です．

*1:この章を読んで，パターンすなわちcaseの条件の中に，match節よりも外にある変数の値を参照するには，どうすればいいか，少し考えました．15.2.3.1項には，『先頭が小文字になっている単純名はパターン変数』(p.254)とあります．だから，いったんパターン変数で書いて，パターンガードの中で，そのパターン変数と，外の変数を==で結べば，いいのでしょうか…．