相互再帰たらいまわし関数をつくるYコンビネータのようなもの

(= Y* ([_ _]
       [fn fs (fn (f) (fn xs (apply (apply f (map (apply (_ _) fs) fs)) xs)))]))
(= tarai
  ((fn (f g) ((Y* f g) f))
   (fn (f g)
     (fn (x y z)
       (if (<= x y) y
         (g (f (- x 1) y z)
            (f (- y 1) z x)
            (- z 1) x y))))
   (fn (f g)
     (fn (x y zx zy zz)
       (if (<= x y) y
         (let z (f zx zy zz)
           (f x y z)))))))

解説

自分自身を引数にすることについて

これは魔法でもなんでもありません。
たとえ無名関数であっても引数には名前が与えられます。
関数が再帰呼び出しをするには自分自身の名前が必要です。
ゆえに再帰呼び出しをするには自分を引数にすればいいのです。

最も単純な例: ([_ _] [_ _])

Arcでは(fn (_) ...)を[...]と略記できます。
なので([_ _] [_ _])は
((fn (_) (_ _)) (fn (_) (_ _)))と同じ意味です。

ベタな例: ([_ _] [fn (n) (if (is n 0) 1 (* n ((_ _) (- n 1))))])

階乗。is を間違えて = と書くのですね、わかります

Yを使う例: (Y [fn (n) (if (is n 0) 1 (* n (_ (- n 1))))])

前の例と比較すると少しだけ短くなりました。
Yの定義は Y f = f (Y f) です。
Arcでは (注意: (fn x (apply ...))で囲んで無限ループを回避する)

(= Y (fn (f) (fn x (apply (f (Y f)) x))))

と書けますが、このように右辺にYが出てくるのが気に入らないなら

(= Y ([_ _] [fn (f) (fn x (apply (f ((_ _) f)) x))]))

と書くのが自然です。ただしこれはTuringの不動点演算子といって
Yコンビネータとは別物のようです。
本物のYコンビネータの定義に従うと

(= Y (fn (f) ([_ _] [f (fn x (apply (_ _) x))])))

となります。これは x x = f (x x) などとやって
最後に f をラムダ抽象すると導出できます。

相互再帰

Y f = f (Y f) のアナロジーで Y2 f1 f2 = ... と考えるのが自然だと思いますが
引数をひとつ増やして
Y2 f1 f2 g = g (Y2 f1 f2 f1) (Y2 f1 f2 f2)
とすれば関数が3個以上の場合にも対応しやすい。
引数がk個の場合

Yk f1 f2 ... fk g = g (Yk f1 f2 ... fk f1)
                      (Yk f1 f2 ... fk f2)
                      ...
                      (Yk f1 f2 ... fk fk)

(= Y* (fn fs (fn (g) (fn xs (apply (apply g (map (apply Y* fs) fs)) xs)))))

参考

• 404 Blog Not Found:最強のたらいまわし
• 不動点オペレータについて