Symbolic Mathematics System Evaluators（Richard J. Fateman）

導入

評価器の定義

入力オブジェクト＋環境（束縛情報）→（評価器）→出力オブジェクト

計算機代数固有の事情

値のない自由変数と変数１個からなる式を区別しなければならない。

補助的な事情

評価にあたっては型を考慮する必要もある（同じ式でも結果がまったく異なることがある。例：はxが実数か虚数かで真偽が異なる。）。

言語の構成規準

1. 言語の記法と意味は数学における「直感的な用法」とよく対応付けるべき
＜直観性規準＞

2. 言語の記法と意味はアルゴリズム的プログラミングにはもちろん計算機内の実際のデータ表現から抽象的なレベルまでにおける数学オブジェクトの記述にも適合するべき
＜プログラム記述規準＞

直観性規準に関する問題

u あいまい性、文脈依存性

例：や

既存技術例：StandardForm(Mathematica)

プログラム記述規準と数学の関係

u 数学と似た構文を含むがしばしば意味が異なる（例：x=x+1）

u 数学とは異なり等しいが同一ではない式を区別する（例：2xとx+x）

u 多くのシステムで格納場所の指定をする数学にはない記述があり、計算に副作用がある（格納場所を指定する間接参照の結果）。

u 伝統的な数値計算プログラミング言語の「関数」は離散値の写像に過ぎず、数学的な意味の関数ではない（例：連続性を問うことは意味をなさない）。

文脈と評価

u 同じ名前に対して複数の値を束縛できるようにする。

u 参照される際のスコープで制御すると簡単。

言語の解釈方式

eval関数

評価手順（ボトム・アップ）

以下を評価結果が変わらなくなるまで繰り返す。

u 数→数値

u 定数→定数値

u 変数→束縛されている値

u 演算（関数）項の評価

Ø 引数→引数値。

Ø 評価済みの引数値で演算（関数）を評価する。

問題点

例：subs(x=a, x-x)

xをaに置換する前にx-xが0と評価されるかも知れない。

しかしaが∞や[-1,1]であれば0は正しくないし、ファイル・ディスクリプタのように減算が定義されていないならばエラーになるべき。

複数フェーズ・モデル（AXIOMで採用されている）

評価順序を2段階以上に分ける。

1段目：トップ・ダウンで各演算の型を確認

2段目：ボトム・アップで値を計算する

例：(+ (modulo 5 3) (* 2 2))

u 1段目で(modulo 5 3)の結果が有限体Z₃の値であることがわかるのでその文脈が(* 2 2)にも及ぶ。

u 1段目が１パスでなく反復できるならば、(+(* 2 2) (modulo 5 3))も同様に処理できる。

問題点

u 型の不一致があった場合に2段目で型強制をどうするのかが明らかでない。

ルール・ベース

変換ルールの

オブジェクト指向

共通の問題

トップ・ダウン・モデルの問題

引用、名詞、不活性関数

関数を利用して式を表現したい場合がある。

例１：diff(y, t)=f(t)　diff()が微分を計算する関数だとするとyがtの関数として与えられていない限りf(t)=0の意味になってしまう。

例2：f(x):=if(x>0) then x els –xのplot(f(t), t, -10, 10)という形式によるプロット。f(t)が先に計算されるとtが未定義であるというエラーが起こる。

既存の対策：

u 引用：’をつけたシンボル（関数、変数）は評価しない。（欠点：引用符が不自然。）

u 不活性関数（名詞）：先頭が大文字の関数は特定の評価器によってしか評価されない。（問題：束縛の処理）

配列と行列の混同

u 要素のアクセスは似ている。

u 行列には配列にない演算がある。

u 式によっては要素にアクセスせずとも成り立つ関係がある（例：AA^-1=I）。

無限回評価、不動点、メモ関数

u 簡易化と評価は不動点をアテにしている（変化がなくなるまで再帰的に適用されるから）。

u 不幸にして不動点がない式（例：x:=x+1）があり、有限回でたどり着ける解はない。有限回で終わる場合の回数を決定するのは難しい。

u メモ関数：毎度同じ値にたどり着くならば、引数と結果の組を記憶しておけばよい（例：Maple関数のrememberオプション。）。問題：関数が透過的でない場合、返り値の記憶は不適切。

既存システムの特徴

AXIOM

u 型と値の組を評価する二重構造のeval

Macsyma

u Lispと同じように全てを一度に計算する。

u 違いは値未定の変数xを評価してもエラーにならないこと。

Maple

u 式の扱いに応じて複数種のeval

Mathematica

u モジュールつきのルールーベース・システム。

u 関数も配列も区別がなく、ルールに対するパターンマッチングで実現されている。

u 関数定義内のスコープはモジュールでシミュレートされている（モジュールは長い名前によって実現されている。）。

u 引用の代わりに関数には引数をすぐに評価するかどうかを示す属性が付けられる。

u 演算での精度が保存されている（ある腫の問題では上手く働かない）。

u 「純粋な浮動小数点演算」はコンパイルされ高速に動作する。

u 区関数と級数はカーネルで特別に処理されている。

REDUCE

u Lisp類似の評価モデル（昔はLispで実装されていた。現在はC版もある。）。

u Lisp類似の構文を持ち実装言語レベルのsymbolicモードと対話環境のalgebraicモードがある。

u 未定義の変数は記号として扱われる。

u 未定義の演算子は導入される。

u ユーザーにとって利用モデルの主だったものはletとmatchによるルールの定義

u 簡潔で、小さなLisp処理系でも動く。

u 数学の表記からは遠い。