Calc が代数操作用の組込みコマンドをいくら提供しようと関係なく、 レパートリー外の要求は常に発生します。 そのため、Calc は 書替え規則(rewrite rule) システムを提供し、 ユーザー自身の代数操作を定義できるようにしています。
次の三角関数の式を簡単化したいとしましょう。
1: 1 / cos(x) - sin(x) tan(x)
.
' 1/cos(x) - sin(x) tan(x) RET s 1
私達が手動でこれを簡単化するとすれば、 多分まず `tan' を `sin/cos' で置換えて、 次に共通分母にまとめようとするでしょう。 前者の操作を行う Calc コマンドはありません。 また、a n という代数コマンドは後者を行いますが、 ここでは練習のため書替え規則を使って両方を行います。
書替え規則は `:=' 記号を使って書かれます。
1: 1 / cos(x) - sin(x)^2 / cos(x)
.
a r tan(a) := sin(a)/cos(a) RET
(Calc において「割付け演算子」`:=' にはいくつか用途があります。 式 `tan(a) := sin(a)/cos(a)' は単独では何もしませんが、 これが a r コマンドに与えられると書替え規則として解釈されます。)
左辺 `tan(a)' は パターン(pattern) と呼ばれます。 Calc はスタック上の式から、パターンにマッチする部分を探します。 書替えパターン中の変数は メタ変数 と呼ばれ、 パターンマッチの際にはメタ変数が部分式にマッチできます。 ここでは、メタ変数 `a' が現実の変数 `x' にマッチしました。
書替え規則のパターン部が式の一部分にマッチすると、 その部分は右辺に置換されます。 このとき全てのメタ変数はそれぞれマッチしたものに替えられます。 それで結果は `sin(x) / cos(x)' となります。 そしてこの結果と残りの部分に Calc 基本の簡単化が加わります。
共通分母についてまとめるために、もうひとつの簡単な規則が使えます。
1: (1 - sin(x)^2) / cos(x)
.
a r a/x + b/x := (a+b)/x RET
この規則は書換えパターンの面白い特徴をいくつか指摘します。 第1 に、パターン中に同じメタ変数が複数使われている場合、 それは全ての個所で同じものにマッチしなければなりません。 ここでは同じメタ変数 `x' が両方の分母に使われているので、 この規則は共通分母を検出します。
第2 に、メタ変数名はターゲット式の変数名と独立です。 ここではメタ変数 `x' が部分式 `cos(x)' にマッチすることに 注目してください。 2つの `x' の意味を Calc が取り違えることはありません。
そして第3 に、書替えパターンは式の代数的性質についてある程度知っています。 パターンは 2つの商の和を要求しましたが、 Calc はそれを、 `a = 1', `b = -sin(x)^2', `x = cos(x)' とすることで 2つの商の差にマッチさせることができました。
規則を `a/x - b/x := (a-b)/x' と書くこともできました。
これでも例外無く正しく機能します。
(`+' だけ、あるいは `-' だけに規則を適用させたかったら、
plain 記号が使えます。
この例は、書替え規則の代数的性質 参照 。)
もうひとつの規則でこの課題は完結します。 公式 `sin(x)^2 + cos(x)^2 = 1' を使いたいのですが、 もちろん式にマッチするようにあらかじめ公式を変形しなくてはなりません。 明白に働くであろう規則は `1 - sin(x)^2 := cos(x)^2' ですが、 少し考えれば規則 `sin(x)^2 := 1 - cos(x)^2' でもうまく働くことが判ります。 後者のほうがより一般的なパターンなので、 他の多くの状況下でも機能するでしょう。
1: (1 + cos(x)^2 - 1) / cos(x) 1: cos(x)
. .
a r sin(x)^2 := 1 - cos(x)^2 RET a s
どうせ毎回タイプしなければならないのなら、 どうしてより一般的な規則を使うのか不思議に思うかもしれません。 それは、 書替え規則を変数に保存しておいて、 a r コマンドの中でそれを使うことができるからです。 実のところ、それが書替えを使う望ましい方法です。 例えばある規則がいったん必要になったら、 後でまた必要になる見込みは高いでしょう。 それから、 もし規則が思い通りに動かなかったら、 単に Undo して変数を編集すれば、 書替えをやり直すときタイプしなおす手間が省けます。
' tan(x) := sin(x)/cos(x) RET s t tsc RET
' a/x + b/x := (a+b)/x RET s t merge RET
' sin(x)^2 := 1 - cos(x)^2 RET s t sinsqr RET
1: 1 / cos(x) - sin(x) tan(x) 1: cos(x)
. .
r 1 a r tsc RET a r merge RET a r sinsqr RET a s
変数を編集するには、 s e と変数名をタイプします。 必要に応じて通常の Emacs 編集コマンド群を使ってください。 そして M-# M-# または C-c C-c をタイプして、 編集結果を変数に書き戻します。 s e は新しい変数を作るときにも使えます。
ちなみに規則を初めて使ったとき、 Calc は短く "compiling" というメッセージを出します。 パターンマッチエンジンは規則をそのまま使わずに、 特殊な最適化パターンマッチ言語に変換します。 これにより a r は比較的複雑な規則であっても極めて効率的に適用します。 規則が変数にストアされると、 Calc はそれを一回だけコンパイルしてその結果をストアします。 これは「規則をその場その場で入力するよりも、変数にストアして使う」ことの、 もう一つの納得できる理由です。
(*) 練習問題 1. m s と押して symbolic モードにしてから、 `(2 + sqrt(2)) / (1 + sqrt(2))' を入力してください。 この式の分母分子に共役 `1 - sqrt(2)' を掛けて簡単化する操作を、 書替え規則を使って行いなさい。 結果は分配法則によって展開しなければなりませんが、 それも書替え規則を使って行いなさい。 書替え 練習問題 1 解答「共役を掛ける」 参照 . (*)
a r コマンドは、 書替え規則群のベクトル(リスト)や、それをストアした変数も受け付けます。
1: [tsc, merge, sinsqr] 1: [tan(x) := sin(x) / cos(x), ... ]
. .
' [tsc,merge,sinsqr] RET =
1: 1 / cos(x) - sin(x) tan(x) 1: cos(x)
. .
s t trig RET r 1 a r trig RET a s
式のあらゆる部分に与えた規則群の適用を試み、 それ以上変形できなくなるまで繰り返します。 (書替えを試みる正確な順序はちょっと複雑ですが、 ここで与えたような単純な規則では順序は問題になりません。 Nested Formulas with Rewrite Rules 参照 .)
与えた規則集合が万一無限ループに陥ったら、 Calc は 100回で書替えを打ちきります。 a r に接頭引数を与えてこの上限を指定することができます。 特に、M-1 a r とすれば 1回だけ書換えを行います。
1: 1 / cos(x) - sin(x)^2 / cos(x) 1: (1 - sin(x)^2) / cos(x)
. .
r 1 M-1 a r trig RET M-1 a r trig RET
無制限に書替えを行いたい場合は、M-0 a r とタイプします。
書替え規則は条件付きにすることもできます。 規則の後に `::' 記号をつけて、続けて望ましい条件を入力するだけです。 例えば、
1: exp(2 pi i) + exp(3 pi i) + exp(4 pi i)
.
' exp(2 pi i) + exp(3 pi i) + exp(4 pi i) RET
1: 1 + exp(3 pi i) + 1
.
a r exp(k pi i) := 1 :: k % 2 = 0 RET
(思い出してください。`k % 2' は `k' を 2 で割った余りです。 これは `k' が偶数であるときのみゼロになります。)
面白いのは規則中の変数 `pi' と `i' が、 メタ変数としてではなく文字どおりにマッチされたということです。 これは、それらが特別な定数変数であるからです。 特別な定数 `e', `phi' なども文字どおりにマッチします。 書替え規則でよくやる特記すべきエラーを挙げると、 例えば 5つの引数を持つ `f' にマッチさせようとして `f(a,b,c,d,e) := g(a+b+c+d+e)' としても、 実際は 5番目の引数が文字どおり `e' であるときしかマッチしません!
書替え規則は、ユーザー自身の関数を定義する面白い方法を提供します。 n 番目のフィボナッチ数を生成する関数 `fib(n)' を 定義したいとしましょう。 フィボナッチ数列の初めの 2つはそれぞれ 1 で、 後の数は直前の連続する 2つの数を合計することによって作られます。 これは 3つの規則集合で簡単に表現されます。
' [fib(1) := 1, fib(2) := 1, fib(n) := fib(n-1) + fib(n-2)] RET s t fib
1: fib(7) 1: 13
. .
' fib(7) RET a r fib RET
書替えが試みられる順序について保証されていることの 1つは、 どんな部分式に対しても、 規則集合において前の規則が後の規則よりも優先して試されるということです。 それで、1番目と 3番目の規則が両方とも `fib(1)' にマッチしても、 1番目が優先的に使われることが判ります。
この規則集合には危険なバグがあって、 もしこれを式 `fib(x)' に適用したら...? (実際に試さないでください。) 3番目の規則は `fib(x)' にマッチして、 `fib(x-1) + fib(x-2)' に置換します。 次にそれぞれの項が置換されて `fib(x-2) + 2 fib(x-3) + fib(x-4)' となり、 それを繰り返して無限に展開します。 求める動作は、 `n' が 2より大きな整数の時だけ第3 の規則を適用することです。 s e fib RET とタイプして、 第3 規則を次のように編集してください。
fib(n) := fib(n-1) + fib(n-2) :: integer(n) :: n > 2
さあ、
1: fib(6) + fib(x) + fib(0) 1: 8 + fib(x) + fib(0)
. .
' fib(6)+fib(x)+fib(0) RET a r fib RET
これで新しい関数 fib と、
「この式の全ての fib 呼出しを評価せよ」という意味の
新しいコマンド a r fib RET ができました。
さらに使いやすくするために、
Calc にこの規則集合を自動的に適用するよう指示することができます。
特別な変数 EvalRules に規則群をストアすれば良いのです。
1: [fib(1) := ...] . 1: [8, 13]
. .
s r fib RET s t EvalRules RET ' [fib(6), fib(7)] RET
:: remember 機能`n' が大きい時、 この規則集合は必要量をはるかに越えた仕事をしてしまうという問題が顕在化します。 `fib(6)' を計算する初めの数ステップを考えてみましょう。
fib(6) = fib(5) + fib(4) = fib(4) + fib(3) + fib(3) + fib(2) = fib(3) + fib(2) + fib(2) + fib(1) + fib(2) + fib(1) + 1 = ...
ここで `fib(3)' が 3回出てきたことに注意してください。
Calc の代数的簡単化エンジンが多数の `fib(3)' に気付いてまとめない限り
(そしてそれが起こってもそうしないので)、
この規則集合は多くの不必要な再計算を行います。
問題を直すために、
s e EvalRules とタイプして
(単に s E としても EvalRules を編集する短縮形になります)
規則を編集し、条件を追加してください。
fib(n) := fib(n-1) + fib(n-2) :: integer(n) :: n > 2 :: remember
ある規則のどこかに `:: remember' 条件がある場合、
その規則が書替えに成功したら Calc は規則集合の前部にそのマッチを記述した規則を追加します。
(remember はどんな規則集合ででも動作しますが、
技術的な理由により EvalRules において最も効率的です。)
例えば、その規則が `fib(7)' を 13 に評価される何かに書替えたら、
規則 `fib(7) := 13' が規則集合に追加されます。
' fib(8) RET とタイプして 8番目のフィボナッチ数を計算したあとで、 再度 s E とタイプして規則集合に何が起こったか見てください。
remember 機能により、
この規則集合はいまやたった n ステップで `fib(n)' を
計算できるようになりました。
その過程で n までの全てのフィボナッチ数のテーブルができます。
特定の n について計算した後は、
たった 1ステップでその結果(および n 以下の全ての結果)を
呼び戻すことができます。
EvalRules が何らかの規則を含んでいるとき、Calc の演算は幾分遅くなります。
s u EvalRules RET をここでタイプして、この変数の内容を破棄してください。
(*) 練習問題 2. しばしば可能なのは、
問題を式変形してそれを解くのに必要な再帰量を減らすことです。
remember 機能に頼らずに、およそ n ステップで
`fib(n, 1, 1)' を `fib(1, x, y)'
に置換する規則を作りなさい。
ただし x と y はそれぞれ n番目と n+1番目の
フィボナッチ数です。
この規則はちょっと使いにくいので、さらに規則をいくつか追加して
前のバージョンと同じユーザーインターフェイス
(`fib(n)'を入力してその値を返す)
を構築しなさい。
書替え 練習問題 2 解答「フィボナッチ規則の別解」 参照 . (*)
書替えにはもっと多くの機能があります。 例えば `&&&' や `|||' というパターン演算子は、 複数の規則を「かつ」や「または」で組合せます。 非常に単純な例として、 フィボナッチの最初の 2つの規則をこのように組み合わせることができました。
[fib(1 ||| 2) := 1, fib(n) := ... ]
その意味は、「1 または 2 にマッチする数の fib は 1 に書きかえる。」
メタ変数を opt で包む事によって optional にすることもできます。
例えばパターン `a + b x' は `2 + 3 x' にマッチしますが、
`2 + x' や `3 x' や `x' にはマッチしません。
パターン `opt(a) + opt(b) x' はこれら全ての形式にマッチして、
`a' がゼロであることによる欠落や、
`b' が 1 であることによる省略を補います。
(*) 練習問題 3. 友人の Joe はスタックに `2 + 3 x' を置いて、 規則 `opt(a) + opt(b) x := f(a, b, x)' を適用しようとしました。 どうなったでしょう ? 書替え 練習問題 3 解答「opt(a) + opt(b) x の書替え」 参照 . (*)
(*) 練習問題 4. 正の整数 a を初期値とし、 a が偶数なら2で割り、奇数ならば 3 a + 1 を計算します。 そしてこのステップを何度も何度も繰り返します。 有名な未証明の推測に、 「初期値 a が何であれ、数列はやがて 1 に到達する。」 というものがあります。 与えられた式 `seq(a, 0)' を `seq(1, n)' に変換する 書替え規則群を書きなさい。 ただし n は数列が 1 に到達するまでのステップ数です。 さらに規則を改良し、 初期値として `seq(a)' 形式を受付けるようにし、 かつちょうど n ステップめで止まるようにしなさい。 結果得られた a から 1 への数列はベクトルにしてください。 (式 `x|y' は 2つのベクトル x と y を結合します。) 例えば `seq(6)' を書替えると、 ベクトル [6, 3, 10, 5, 16, 8, 4, 2, 1] が得られるようにしてください。 書替え 練習問題 4 解答「整数の数列」 参照 . (*)
(*) 練習問題 5. 書替え規則を使って、 x が和ならその項の数を、 和でなければ 1 を返す関数 `nterms(x)' を定義しなさい。 (この場合の和とは、 1つ以上の和でない項が `+' または `-' 記号で 接続されているものであって、 2 - 3 (x + y) + x y は 3つの項の和です。) 書替え 練習問題 5 解答「和の項の数」 参照 . (*)
(*) 練習問題 6. Calc は 式 0^0 を「未定義」と考え、 評価せずに残します(今では無限大モードでないとしています)。 人によっては 0^0 = 1 と定義して、 恒等式 x^0 = 1 があらゆる x について安全に成立するのを好みます。 Calc をこの慣習に従わせる方法を見つけなさい。 その状態で m i とタイプして無限大モードにしたらどうなるでしょう? 書替え 練習問題 6 解答「0^0 = 1 を定義する」 参照 . (*)
(*) 練習問題 7. ある関数の Taylor 級数は無限級数で、 x = 0 の周辺で関数値に厳密に一致します。
cos(x) = 1 - x^2 / 2! + x^4 / 4! - x^6 / 6! + ...
a t コマンドは、例えば x^2 より高次の項を切捨てて得られる 略式 Taylor 級数を生成します。 Calc は略式 Taylor 級数を x の多項式として表します。 数学者らはしばしば、 どこから先を省略したか示す「big-O」表記法を使って略式級数を表します。
cos(x) = 1 - x^2 / 2! + O(x^3)
O(x^3) の意味するところは、 「x がゼロに近づくにつれて x^3 が無視し得る程小さくなると考えるなら、 この量も無視し得る程小さい」というものです。
では、`多項式 + O(var^n)' で表されたべき級数の 和や積を簡単化する書替え規則を作れ、というのが問題です。 例えば、 `1 - x^2 / 2 + O(x^3)' と `x - x^3 / 6 + O(x^4)' が スタック上に与えられている時、* を押すと `x - 2:3 x^3 + O(x^4)' が得られるようにしたいのです。 和の項の順序が違ったり、書替えの後 a s が必要でも構いません。 (これは幾分手が焼けます。 この章の最後にある解答は 6つの書替え規則を使っています。 ヒント: `constant(x)' という条件テストは `x' が数字かどうか調べます。) 書替え 練習問題 7 解答「略式 Taylor 級数」 参照 . (*)
書替え規則の全貌は、書替え規則(Rewrite Rules) 参照 。
Go to the first, previous, next, last section, table of contents.
利用度数