Sun Sep 17 2017

適度な複雑さを持った \(\mathbb{N} \to \mathbb{N}\) な関数をランダムに自動生成したい欲求がある.

Primitive Recursive

自然数の \(m\) つ組 \(\mathbb{N}^m\) (\(m\geq 1\)) の上の関数 \(\mathbb{N}^m \to \mathbb{N}\) として、次の5つを認める. ただし \(\mathbb{N}\) と \(\mathbb{N}^1\) は同一視する.

ゼロ関数 (Const)

• \(C : \mathbb{N} \to \mathbb{N}\)
• \(C : x \mapsto 0\)

後続関数 (Successor)

• \(S : \mathbb{N} \to \mathbb{N}\)
• \(S : x \mapsto x+1\)

射影関数 (Projector)

• \(p^i : \mathbb{N}^m \to \mathbb{N}\)
• \(p^i : (x_1,\ldots,x_m) \mapsto x_i\)

ただし \(1 \leq i \leq m\) であること.

合成関数 (Compose)

• \(compose: \mathbb{N}^n \to \mathbb{N}\)
• \(compose(x) = g(h_1(x), \ldots, h_m(x))\)
  • \(g: \mathbb{N}^m \to \mathbb{N}\)
  • \(h_i: \mathbb{N}^n \to \mathbb{N} ~~(i=1,2,\ldots,m)\)

ただしここで \(n\) つ組 \((x_1,\ldots,x_n)\) を簡単のため単に \(x\) と書いた.

再帰関数 (Recursive)

• \(rec : \mathbb{N}^{m+1} \to \mathbb{N}\)
• \(rec(0,x) = g(x)\)
• \(rec(y,x) = h(rec(y-1,x))\)
  • \(g : \mathbb{N}^m \to \mathbb{N}\)
  • \(h : \mathbb{N} \to \mathbb{N}\)

ただしここで \(m+1\) つ組 \((x_1,\ldots,x_{m+1})\) の1つめを \(y\) と、2つめ以降の部分 \((x_2,\ldots,x_{m+1})\) のことを簡単のため単に \(x\) と書いた.

実装 (Rust)

定義

5種の関数を PR という名前の型で enum として定義する

#[derive(Debug, Clone)]
enum PR {
    Const,
    Successor,
    Projector(usize),
    Compose(Box<PR>, Box<Vec<PR>>),
    Recursive(Box<PR>, Box<PR>),
}

パラメータはそれぞれ、評価をする際に必要な情報だけを持っておくことにする. Projector は引数の何番目 (0-indexed) を射影するかを持っている. Compose は、\(g, (h_1,\ldots,h_m)\) をそれぞれ持っておく. 同様に Recursive は \(g, h\) を持つ.

例

いちいち Box に囲む必要がある事情で冗長だが、

{
    let f = PR::Compose(
                Box::new(PR::Successor),
                Box::new(vec![
                         PR::Compose(
                             Box::new(PR::Successor),
                             Box::new(vec![
                                      PR::Const
                             ]))
                ]));
    println!("{:?}", f);
}

Compose(Successor, [Compose(Successor, [Const])])

これは \(S \circ S \circ C = S^2 \circ C\) を表す.

評価

まず自然数 \(\mathbb{N}\) は u32 (符号なし32bit整数) で表現する. 引数は一般に \(\mathbb{N}^n\) であるので Vec<u32> (符号なし32bit整数の配列) ということにする. 出力は \(\mathbb{N}\) に限ってるので単に u32.

実装は定義をほぼそのまま Rust に翻訳するだけ.

fn eval(f: &PR, xs: Vec<u32>) -> u32 {
    // println!("eval {:?} {:?}", f, xs);
    match *f {
        PR::Const => 0,
        PR::Successor => xs[0] + 1,
        PR::Projector(n) => xs[n],
        PR::Compose(ref g, ref hs) => {
            let mut ys = vec![];
            for i in 0..hs.len() {
                let y = eval(&hs[i], xs.clone());
                ys.push(y);
            }
            eval(&g, ys)
        },
        PR::Recursive(ref g, ref h) => {
            if xs[0] == 0 {
                let rest = (1..xs.len()).map(|i| xs[i]).collect();
                eval(&g, rest)
            } else {
                let mut ys = xs.clone();
                ys[0] -= 1;
                eval(&h, vec![eval(&f, ys)])
            }
        },
    }
}

Recursive の解釈では引数 xs の頭 xs[0] がゼロであるかどうかをチェックする. ゼロならば 2 つめ以降の部分を rest として確保し、それを g に渡す. ゼロでないなら 1 だけ減らした引数を mut ys として確保し、これを再帰的に自身 f に渡す (そして h に渡す).

例

先の

Compose(Successor, [Compose(Successor, [Const])])

なる関数 f について

    println!("{:?}", eval(&f, vec![3]));

として引数 3 を渡して解釈した結果を見る.

eval Compose(Successor, [Compose(Successor, [Const])]) [3]
eval Compose(Successor, [Const]) [3]
eval Const [3]
eval Successor [0]
eval Successor [1]
[2]

これは

• \(S \circ S \circ C (3)\)
• \(S \circ S (0)\)
• \(S (1)\)
• \((2)\)

という過程を表している. Compose なんかは正しく動いていそう.

例

Recursive を使う例として、加算を定義してみる. つまり、

{
    let id = PR::Projector(0); // Identity
    let h = PR::Successor;
    let plus = PR::Recursive(Box::new(id), Box::new(h));
    println!("{:?}", plus);
    println!("{:?}", eval(&plus, vec![3, 5]));
}

ここで定義している PR::Projector(0) すなわち \(p^0\) の引数は実は単に \(\mathbb{N}=\mathbb{N}^1\) なので、 単なる恒等関数 \(x \mapsto x\) として振る舞う. 数式で書き改めると

• \(g(x) = x\)
• \(h(x) = x + 1\)
• \(plus(0, x) = g(x) = x\)
• \(plus(y, x) = h(plus(y - 1, x)) = plus(y - 1, x) + 1\)

というわけで \(plus(y,x)=y+x\) なることが \(y\) に関する帰納法から明らか.

上のコードを実行してみると次のように:

Recursive(Projector(0), Successor)
eval Recursive(Projector(0), Successor) [3, 5]
eval Recursive(Projector(0), Successor) [2, 5]
eval Recursive(Projector(0), Successor) [1, 5]
eval Recursive(Projector(0), Successor) [0, 5]
eval Projector(0) [5]
eval Successor [5]
eval Successor [6]
eval Successor [7]
[8]

関数 eval 自体が再帰関数であるので、 y から 1 を減ずる処理 (plus の再帰) が 3 回あってから、そのあと、h で結果に 1 を加える処理が 3 回ある.

例

今の plus を使うと、引数を2倍にして返す \(\mathbb{N} \to \mathbb{N}; x \mapsto 2x\) が定義出来る. すなわち、 id 2つと合成することで \((plus \circ (id,id))(x) = plus(x,x)=2x\) と定義できる. 翻訳すると次の通り (Clone はこのために必要).

{
    let id = PR::Projector(0);
    let h = PR::Successor;
    let plus = PR::Recursive(Box::new(id.clone()), Box::new(h));
    let double = PR::Compose(Box::new(plus), Box::new(vec![id.clone(), id.clone()]));
    println!("{:?}", double);
    println!("{:?}", eval(&double, vec![5]));
}

Compose(Recursive(Projector(0), Successor), [Projector(0), Projector(0)])
eval Compose(Recursive(Projector(0), Successor), [Projector(0), Projector(0)]) [5]
eval Projector(0) [5]
eval Projector(0) [5]
eval Recursive(Projector(0), Successor) [5, 5]
eval Recursive(Projector(0), Successor) [4, 5]
eval Recursive(Projector(0), Successor) [3, 5]
eval Recursive(Projector(0), Successor) [2, 5]
eval Recursive(Projector(0), Successor) [1, 5]
eval Recursive(Projector(0), Successor) [0, 5]
eval Projector(0) [5]
eval Successor [5]
eval Successor [6]
eval Successor [7]
eval Successor [8]
eval Successor [9]
10

自動生成

真面目にやると相当面倒なので、あまり質にこだわらずにやってみる. 要するに 5 種からランダムに選んで関数を作る. それが Compose か Recursive なら、さらにパラメータとなる関数を作る. 単に1/5の確率で選ぶと木が延々深くなって止まらなくなる. (3/5の確率で止まるが、一度爆発すると、全ての枝で 3/5 が選ばれないといけないので、収束は絶望的.) ある程度深くなったら Compose 及び Recursive は選ばなく成る/選ぶ確率が減る、等の工夫は必要.

何も考えずに PR を作るには arity (引数の次数) だけを渡して、5種から選んで再帰的に構築すればよい. 注意点として、 Const Successor の arity は 1 に限る (ということにした) こと. Recursive の arity は 2 以上であること.

fn make_tree() -> PR {
    make_subtree(1, 0)
}

fn make_subtree(arity: usize, depth: usize) -> PR {
    if depth < 5 {
        if arity == 1 {
            match rand::random::<u32>() % 100 {
                0...9 => PR::Const,
                10...19 => PR::Successor,
                20...89 => make_compose(arity, depth),
                _ => PR::Projector(0)
            }
        } else {
            match rand::random::<u32>() % 100 {
                0...34 => make_compose(arity, depth),
                35...69 => make_recur(arity, depth),
                _ => PR::Projector(rand::random::<usize>() % arity)
            }
        }
    } else {
        if arity == 1 {
            match rand::random::<u32>() % 100 {
                0...9 => PR::Const,
                10...79 => PR::Successor,
                _ => PR::Projector(0)
            }
        } else {
            PR::Projector(rand::random::<usize>() % arity)
        }
    }
}

fn make_compose(arity: usize, depth: usize) -> PR {
    let m = 1 +  rand::random::<usize>() % 3;
    let g = make_subtree(m, depth + 1);
    let mut hs = vec![];
    for _ in 0..m {
        let h = make_subtree(arity, depth + 1);
        hs.push(h);

    }
    PR::Compose(Box::new(g), Box::new(hs))
}

fn make_recur(arity: usize, depth: usize) -> PR {
    assert!(arity > 1);
    let g = make_subtree(arity - 1, depth + 1);
    let h = make_subtree(1, depth + 1);
    PR::Recursive(Box::new(g), Box::new(h))
}

結果

for _ in 0..5 {
    let f = make_tree();
    println!("{:?}", f);
    println!("{:?}", eval(&f, vec![3]));
}

f = Compose(Projector(1), [Successor, Compose(Recursive(Compose(Compose(Projector(1), [Successor, Successor, Projector(0)]), [Projector(1)]), Compose(Projector(2), [Const, Compose(Projector(0), [Successor, Successor]), Compose(Const, [Projector(0)])])), [Compose(Projector(1), [Compose(Compose(Projector(0), [Projector(0)]), [Compose(Projector(1), [Projector(0), Successor, Successor]), Successor]), Compose(Recursive(Projector(1), Successor), [Compose(Projector(1), [Successor, Projector(0)]), Compose(Projector(0), [Successor, Successor, Successor]), Const]), Compose(Recursive(Projector(0), Projector(0)), [Compose(Projector(1), [Successor, Successor]), Compose(Projector(0), [Successor]), Compose(Successor, [Successor])])]), Compose(Recursive(Compose(Projector(0), [Successor, Successor]), Compose(Projector(0), [Successor, Projector(0)])), [Compose(Recursive(Projector(1), Successor), [Compose(Successor, [Successor]), Const, Compose(Successor, [Const])]), Compose(Compose(Projector(0), [Projector(2), Projector(0), Projector(2)]), [Compose(Projector(2), [Successor, Const, Successor]), Successor, Const])]), Compose(Successor, [Compose(Compose(Projector(0), [Projector(2), Projector(1), Projector(2)]), [Compose(Projector(0), [Successor, Successor, Successor]), Compose(Successor, [Projector(0)]), Const])])]), Projector(0)])
f 3 = 0
---
f = Compose(Projector(1), [Const, Compose(Projector(0), [Compose(Projector(0), [Compose(Projector(2), [Compose(Projector(1), [Successor, Projector(0), Successor]), Successor, Successor]), Compose(Compose(Projector(0), [Projector(0), Successor]), [Compose(Successor, [Successor])])])])])
f 3 = 4
---
f = Compose(Compose(Recursive(Compose(Compose(Successor, [Projector(1)]), [Projector(0), Compose(Projector(0), [Successor, Successor, Successor])]), Compose(Compose(Projector(0), [Projector(0)]), [Compose(Successor, [Const]), Compose(Projector(2), [Successor, Successor, Successor])])), [Compose(Compose(Compose(Projector(1), [Successor, Successor]), [Compose(Projector(0), [Projector(1), Projector(0), Projector(2)])]), [Projector(0), Projector(1), Projector(1)]), Projector(1)]), [Successor, Compose(Recursive(Recursive(Const, Compose(Projector(0), [Successor, Successor])), Compose(Recursive(Successor, Successor), [Compose(Projector(0), [Successor, Successor, Projector(0)]), Successor])), [Successor, Const, Compose(Compose(Compose(Successor, [Successor]), [Compose(Const, [Projector(0)])]), [Compose(Compose(Projector(2), [Projector(0), Projector(1), Projector(1)]), [Compose(Projector(1), [Projector(0), Successor, Const]), Compose(Projector(1), [Successor, Projector(0), Successor])]), Compose(Compose(Projector(1), [Projector(0), Successor, Const]), [Compose(Projector(1), [Const, Const])])])])])
f 3 = 1
---
f = Compose(Recursive(Compose(Projector(0), [Compose(Recursive(Projector(1), Successor), [Projector(0), Compose(Successor, [Const]), Compose(Projector(0), [Successor, Successor])])]), Compose(Projector(0), [Compose(Projector(0), [Successor]), Compose(Compose(Successor, [Projector(1)]), [Compose(Projector(1), [Successor, Projector(0)]), Successor, Compose(Projector(0), [Successor, Projector(0), Successor])])])), [Compose(Projector(0), [Compose(Recursive(Compose(Projector(2), [Projector(1), Projector(0), Projector(0)]), Projector(0)), [Successor, Successor, Compose(Recursive(Projector(1), Projector(0)), [Successor, Compose(Successor, [Projector(0)]), Compose(Projector(1), [Successor, Successor, Successor])])])]), Compose(Compose(Projector(0), [Successor, Compose(Projector(0), [Compose(Successor, [Successor]), Compose(Projector(0), [Successor, Successor]), Const]), Successor]), [Compose(Recursive(Projector(1), Compose(Successor, [Successor])), [Compose(Compose(Projector(1), [Projector(1), Projector(0)]), [Compose(Projector(0), [Const, Projector(0)]), Compose(Projector(1), [Successor, Successor, Successor])]), Compose(Recursive(Projector(0), Projector(0)), [Compose(Successor, [Successor]), Compose(Projector(0), [Successor])]), Compose(Compose(Projector(0), [Successor, Successor]), [Compose(Projector(0), [Const, Projector(0), Successor])])])])])
f 3 = 9
---
f = Compose(Successor, [Compose(Compose(Compose(Successor, [Compose(Projector(1), [Successor, Successor])]), [Successor]), [Compose(Compose(Recursive(Projector(1), Successor), [Compose(Successor, [Successor]), Compose(Successor, [Successor]), Compose(Projector(1), [Successor, Const])]), [Compose(Compose(Successor, [Projector(0)]), [Projector(0)])])])])
f 3 = 10
---
cargo run  0.07s user 0.02s system 88% cpu 0.095 total