Karva Notationという木構造を表す記法

Parsing Karva notation in haskell

Karva Notation and K-Expressions

 今日, hylomorphismについて調べていたらKarva Notationという記法に出会った. 上がhylomorphismについてググっていたときに出てきた記事で, 下がKarva Notationの説明の記事.

 一見すると, ポーランド記法のような書き方で, 演算子と識別子(変数?)を並べただけの書き方に見えますが, 例題の木構造とKarva Notationを見比べてみると, ポーランド記法とは全く別物です.

 こんな感じの木構造に対して,
     +
   ┏━┓
   a   *
     ┏━┓
     /   d
  ┏━┓
  b   c

 S式では,

 (+ a (* (/ b c) d))

と書くところを, Karva Notationは,

 + a * / d b c

 と表すようなのです. ポーランド記法だと, + a * / b c d になります.

 この記法では [深さ0の要素(=木構造のトップ)] [深さ1の要素] ... ... [深さnの要素] の順で各深さのレベルにおいて, それぞれ左から要素を記述していくという書き方です.
 上記の例では,

 [(木構造トップの) +] [(深さ1の) a (と) *]  [(深さ2の) / (と) d]  [(深さ3の) b (と) c]

 で, + a * / d b c となるわけです.

 こんな不思議な(可読性の低い)記法が, 何に使われるのかと思ったら, 遺伝的プログラミングでした.

遺伝的プログラミング - Wikipedia

 遺伝的プログラミングは, Wikipediaにもあるように, 遺伝的アルゴリズムをプログラミングへ発展させたもので, プログラムを意味する遺伝子どうしを掛け合わせたり, 突然変異させたりして, プログラム(もしくは関数)を進化させて, 解を得るという手法です. プログラムを木構造(抽象構文木)として表現し, この木構造を遺伝子として扱うことで, プログラムどうしを交叉(遺伝子どうしの配合)させます.

 そして, 普通, プログラム(関数)の遺伝子の表現は, S式など用いて行うわけですが, 上記のような Karva Notationによるプログラムの表現でも遺伝的プログラミングができる, ということのようです.

 そう考えると, なかなか面白い記法ですね. SGAで使われるような0/1の遺伝子の表現と同じような単なる記号列なので, SGAと同じような文字列の1点交叉や2点交叉ができてしまいます.

参考文献
Gene Expression Programming: A New Adaptive Algorithm for Solving Problems