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に登場する. 奇数個の値をソートしてa0,a1,...,a2nが得られた時のanを値とする.<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この辺までは簡単の単だ.
0 件のコメント:
コメントを投稿