[過去ﾛｸﾞ] 次世代言語11[Rust Swift TypeScript Dart] (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
589(3): デフォルトの名無しさん [sage] 2018/06/18(月) 18:04:53.53 ID:xdRdwSco(1/4) AAS
>>578578(2): デフォルトの名無しさん [] 2018/06/18(月) 15:30:15.87 ID:soq2obRK(2/6) AAS
ところで、またATS2に話を戻すんだけど、
日本語訳もあったしチュートリアルやってみてるんだけど
↓の再帰関数の停止性検査とやらで躓いている
外部ﾘﾝｸ[html]:jats-ug.metasepi.org
特に
fun isevn{n: nat} .<2*n>. (n: int n): bool = if n = 0 then true else isodd (n-1)
and isodd{n: nat} .<2*n+1>. (n: int n): bool = not(isevn(n))
が何故.<2 * n>.と.<2 * n + 1>になるか理解できん…
.<n>.と.<n + 1>.で大丈夫だと思ったんだが…
たぶんまだ、停止性メトリクスとやらが正しく理解できていないんだろうな…
誰か詳しく解説してくれないか？
とある関数呼び出しの定義内に表れる再帰的呼び出しの
停止性マトリクスが、大元の関数呼び出しの停止性マトリクスから辞書順で下降していくことから停止性を担保しようというのが停止性マトリクスの意味。
そして停止性マトリクスの記述に表れる n は issven や isodd の引数そのものだということに注意
iseven、isodd の停止性マトリクスがそれぞれ n、n+1 だと、
iseven n の停止性マトリクス→n
iseven n の定義に出てくる isodd (n-1) の停止性マトリクス→n-1+1=n
減っていないから停止性が担保されない(NG)。
説明にあるように <n, 0> と <n,1> ならば、
iseven n の停止性マトリクス→<n,0>
iseven n の定義に出てくる isodd (n-1) の停止性マトリクス→<n-1,1> (下降している！OK)
isodd も同様に
isodd n の停止性マトリクス→<n,1>
isodd n の定義に出てくる iseven (n) の停止性マトリクス→<n,1> (下降している！OK)
そして<n,0 <n,1> の代わりに n*2, n*2+1 を使っている(この代用が可能なことはわかるよね)。
590: デフォルトの名無しさん [sage] 2018/06/18(月) 18:08:28.85 ID:xdRdwSco(2/4) AAS
>>589
＞停止性マトリクスが、大元の関数呼び出しの停止性マトリクスから辞書順で下降していくことから停止性を担保しようというのが停止性マトリクスの意味。
この説明「下降していく」だと本当に再起をどんどん
実行していくみたいで間違ってるか。
とある関数呼び出しの停止性マトリクスよりも、
その関数の定義に表れる全ての再帰的呼び出しの停止性マトリクスのほうが辞書順で小さい、
というべきか。
591: デフォルトの名無しさん [sage] 2018/06/18(月) 18:09:50.53 ID:xdRdwSco(3/4) AAS
>>589
＞isodd も同様に
＞isodd n の停止性マトリクス→<n,1>
＞isodd n の定義に出てくる iseven (n) の停止性マトリクス→<n,1> (下降している！OK)
最後の行は
isodd n の定義に出てくる iseven (n) の停止性マトリクス→<n,0> (下降している！OK)
の間違いでした
596(1): デフォルトの名無しさん [sage] 2018/06/18(月) 19:23:14.64 ID:xdRdwSco(4/4) AAS
>>595595(2): デフォルトの名無しさん [sage] 2018/06/18(月) 18:58:41.11 ID:soq2obRK(4/6) AAS
>>589
ありがとう
冷静に計算していったら、確かにnとn+1じゃ減ってないからダメで
2*nと2*n+1だときちんと減ってるからOKってところまでは理解できた
でも、一体何を考えて<n,0>と<n,1>のタプル？のメトリクスが出てきたか全然分からない…
> そして<n,0 <n,1> の代わりに n*2, n*2+1 を使っている(この代用が可能なことはわかるよね)。
すまない。俺はバカなんだ。分からないんで教えて下さい。
自分でも自分がどこまで分かっているのかさえよく分かっていないんだが、
たぶん、停止性メトリクスがきちんと減っているかどうかを計算する方法までは理解できたが、
きちんと減っている停止性メトリクスを導き出す方法が分かってないんだと思う
＞すまない。俺はバカなんだ。分からないんで教えて下さい。
辞書順を保ったまま <n, 0 <n,1> をそれぞれ 2*n, 2*n+1 で置き換えられる
3*nとか4nでもいいけど2つしかないから2nで十分
例
fun f
{n:nat} .<3*n>.
(n: int n) : bool =
if n = 0 then true else g (n-1)
and g
{n:nat} .<3*n+2>.
(n: int n) : bool = not (h (n))
and h
{n:nat} .<3*n+1>.
(n: int n) : bool = not (f (n))
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.142s*