(モデル理論アプローチによるシミュレーション)
言語CASTで漸化式を解く

　例題として，漸化式
　　f(0)=100, 
　　f(n)=0.9×f(n-1)   (n≧1)
で定義される数列 f(1),f(2),f(3),... を求めるためのCAST言語のユーザ関数を示す．

1  初等再帰的関数

　教科書 p.161の初等再帰的関数として定義すると，

　　func([f]);
　　f(n)=y <-> (n=0) -> (y:=100) otherwise ( y:=0.9*f(n-1) );

となる．実は，同じ関数を次のようにも記述できる．

　　func([f]);
　　f(0)=100;
　　f(n)=0.9*f(n-1);

数式をそのまま書いているので分かりやすい．
しかし，これで求められるのはf(28)までである．
n > 28に対してはシステムがフリーズする（Segmentation fault）．
原因は不明である．

2　関数defListによる解法

　関数defListを使って数列のリストL(n) = [f(1), f(2),..., f(n)]を求める方法を示す．

　　func([L]);
　　L(n)=Ps <-> y.g:=100, Ps:=defList(p(z,x,[]), member(genIndex(1,n)));
　　p(z,x,[]) <-> z:=0.9*y.g, y.g:=z;

したがって，リストの最後の要素をとりだせば f(n) が得られる．

　　fn:=project(L(n),0);

これなら，nが大きくても計算できる．f(10000)が計算できることを確認した．
教科書p.162の非再帰的な方法がこれである．

【解説】defList　---------------------------------------------------------

　defList(p(z,x,[補助変数]),member(x,Xs)) は，
述語pを満足するzを並べてリストを作成する関数である．
Xsをインデックス集合と呼ぶ．
述語p(z,x,[補助変数])はインデックス集合の要素xと並べるべき要素zを関係づける述語である．
たとえば，教科書p. 156のように，

    Ps:= defList(peven(z,x,[]),member(x,[1,2,3,4,5,6]))
    peven(z,x,[]) <-> x%2=0, z:=x;

と定義すれば，偶数のリストPs=[2,4,6]が得られる．システム内部では，
    peven(z,1,[])を満足するz ＝ [],
    peven(z,2,[])を満足するz ＝ [2],
    peven(z,3,[])を満足するz ＝ [],
    peven(z,4,[])を満足するz ＝ [4],
    peven(z,5,[])を満足するz ＝ [],
    peven(z,6,[])を満足するz ＝ [6],
を連接(append)してリストPs=[2,4,6]を得ている．
集合Xsの要素xを「先頭から順に代入して」性質pevenが成り立つzを求めているのである．

　以下では，教科書には未記載の「裏技」を紹介する．ここで注目したいことは，
「defLIstはインデックス集合の要素の数｜Xs｜だけ仕事をする」という点である．
したがって，極端に言えば，xとzが無関係であっても｜Xs｜回の仕事をさせることができる．
たとえば，

    Qs:=defList(p1(z,x,[]),member(x,[6,7,8]))
    p1(z,x,[]) <-> xwriteln(0,"Hallo");

と定義した場合，Dialogウインドウに"Hallo"が3回表示される．
述語 xwriteln(0,"Hallo") は，x=6,7,8とまったく無関係であるうえに，変数zの定義さえしていない．
しかしながら，3回の仕事「真偽チェック」をしているのである．
（xwriteln(0,"Hallo")のような入出力命令は，それが成功する限り常に「真」である．）
したがって，手続型言語の「繰り返し命令」のような仕事をさせることができる．

　その他，裏技としてグローバル変数を使う例を紹介する．
例えば，

    y.g:=100,
    Qs:=defList(p1(z,x,[]),member(x,[6,7,8]))
    p1(z,x,[]) <-> z:=0.9*y.g, y.g:=z;

と定義した場合，zはy.gのみに依存して決定されるので，x=6,7,8とzは互いに無関係である．
しかしながら，3回の真偽チェックを行ない，
    初期値はy.g=100,
    p1(z,6,[])を満足するz ＝ [90], そのとき y.g=90,
    p1(z,7,[])を満足するz ＝ [81], そのとき y.g=81,
    p1(z,8,[])を満足するz ＝ [72.9]
であるから，Qs=[90,81,72.9]が得られる．

述語p1は並べるべき値z:=0.9*y.gを決定し，
ついでにグローバル変数をy.g:=zに書き換える仕事をしている．したがって，
　　f(0)=100,
　　f(n)=0.9*f(n-1)
という漸化式を初期値から順番に計算し，
リストQs=[f(1),f(2),f(3)]を作成していると考えることができる．

　さらに，もしもRs=[f(11),f(12),f(13)] を計算したいときは，次のように定義すればよい．

    y.g:=100,
    Rs:=defList(p2(z,x,[]),member(x,genIndex(1,13)))
    p2(z,x,[]) <-> z:=0.9*y.g, y.g:=z, x>10;

述語p2ではインデックスを使ってx>10と指定しているので，
11回目の計算結果からRsの要素に採用されていく．
しかし，10回目まで計算は行なわれていることに注意したい．
10回目まで「計算は行なわれている」がRsの要素として採用されないことに特徴がある．
###
 ただし x>10 は右端に記述する必要がある．
例えば　x>10, z:=0.9*y.g, y.g:=z と書くと，10回までの計算は実行されない．
その理由は，システムは，偽である x>10 を見つけると，それより右の項の真偽チェックをしないからである．
記述の順序に気をつける必要がある．
###

　その他，
defListの結果にリスト演算子sumを適用すると，数列の和（シグマ：Σ）を計算できる．
defListを2つ使って，行列（リストのリスト）を作成することもできる．


　また，リストではなく集合を作る関数としてdefSetがあるが，
これはdefListを行なったあとに「集合」化したもの，
つまり，defSet(...) = distinct(defList(...))と考えることができる．

　　　　　　　　　　　　　　　　　　　　　　　　東洋大学　旭貴朗