Christopher StracheyのGPM

前回はHanoiの塔まで説明した. また続きのマクロを示す.

Fibonacci数

GPMで遊ぶのに適している例題の一つがFibonacci数である.

(define (fib n)
 (cond ((= n 0) 0)
       ((= n 1) 1)
       (else (+
        (fib (- n 1))
        (fib (- n 2))))))

とりあえずGPM風にすると

$def,fib,<$n,
 $def,n,<$+,
  $fib,$1-,n;;,
  $fib,$1-,$1-,n;;;;>;
 $def,1,1;,
 $def,0,0;;>;

+のマクロは基本演算で定義した.

nはもちろん~1にする. <,>が2重に使われているが, 内側のクォートの内部では ~n は>~n< にする.

従って

$def,fib,<$~1,
 $def,~1,<$+,
  $fib,$1-,>~1<;;,
  $fib,$1-,$1-,>~1<;;;;>;
 $def,1,1;,
 $def,0,0;;>;

やってみると

$fib,0; => 0
$fib,1; => 1
$fib,2; => 1
$fib,6; => 8

階乗

次は階乗. マクロ名に!が使えて嬉しい. *は基本演算参照

$def,!,<$~1,
 $def,~1,<$*,>~1<,$!,$1-,>~1<;;;>;,
 $def,0,1;;>;

と簡単だ. 実行例は

$!,0; => 1
$!,1; => 1
$!,2; => 2
$!,3; => 6

中央値

英語ではmedian. TAOCPの7.1.1に登場する. 奇数個の値をソートしてa₀,a₁,...,a_2nが得られた時のa_nを値とする.

<1,0,4,2,3>=2だ. 奇数個の値がfalseとtrueだけとし, false<trueとした時, 中央値は多数決になる. <false,false,true>=false,<true,false,true>=true. 中央値は多数決を一般化したものである.

ここでは3個の値の中央値を見つける.

(define (med a b c)
 (if (< b a)
  (if (< c a)
   (if (< c b) b c)
   a)
  (if (< c b)
   (if (< c a) a c)
   b)))

このGPM版は

$def,med,<$$lt,~2,~1;,
  $def,t,$$lt,~3,~1;,$def,t,$$lt,~3,~2;,$def,t,~3~2~1;,
                                        $def,f,~2~3~1;;;,
                     $def,f,~2~1~3;;;,
  $def,f,$$lt,~3,~2;,$def,t,$$lt,~3,~1;,$def,t,~3~1~2;,
                                        $def,f,~1~3~2;;;,
                     $def,f,~1~2~3;;;;>;

実行すると

$med,0,0,0;,$med,0,0,1;,$med,0,0,2;,$med,0,1,0;,$med,0,1,1;,
$med,0,1,2;,$med,0,2,0;,$med,0,2,1;,$med,0,2,2;,$med,1,0,0;,
$med,1,0,1;,$med,1,0,2;,$med,1,1,0;,$med,1,1,1;,$med,1,1,2;,
$med,1,2,0;,$med,1,2,1;,$med,1,2,2;,$med,2,0,0;,$med,2,0,1;,
$med,2,0,2;,$med,2,1,0;,$med,2,1,1;,$med,2,1,2;,$med,2,2,0;,
$med,2,2,1;,$med,2,2,2;
=>
0,0,0,
0,1,1,
0,1,2,
0,1,1,
1,1,1,
1,1,2,
0,1,2,
1,1,2,
2,2,2

GCD

Euclidの互除法が有名だが, 9までの数を扱うこのGPMの世界では引き算で計算できる.

(define (gcd a b)
 (cond ((= a b) a)
       ((< a b)
        (gcd a (- b a)))
       ((> a b)
        (gcd (- a b) b))))

GPMに書き直す.

$def,gcd,<$~2,
 $def,~2,
  <$$lt,>~1<,>~2<;,
  $def,f,
   <$gcd,$-,>>~1<<,>>~2<<;,>>~2<<;>;,
  $def,t,
   <$gcd,>>~1<<,$-,>>~2<<,>>~1<<;;>;;>;,
 $def,~1,~1;;>;
$gcd,2,4;,$gcd,5,3;,$gcd,6,3; => 2,1,3

この辺までは簡単の単だ.