kにおけるアルファ当量比較 -- kframework フィールド 関連 問題

Alpha-Equivalence Comparison in K?












0
vote

問題

日本語

は、2つのK用語の間の構造的等価性とアルファ当量比較がありますか?

アルファ変換を行うように見える置換モジュールがあるので、同等のものがあるかどうか疑問に思いました。

ある場合は、特定の構文から抽象化された方法でそのような機能を定義することは可能ですか?たとえば、パーサーのバインダーの注釈を使用して2つの用語を確認してくださいが、文法はそれらを定義します。

英語

Is there a built-in structural equivalence and alpha-equivalence comparison between two K terms?

Since there's a substitution module that appears to do alpha-conversion, I was wondering if there's one for equivalence.

If there isn't one, is it possible to define such a function in a way abstracted from the specific syntax being checked? For instance, using the parser's binder annotations to check any two terms, however the grammar defines them.

</div
  

回答リスト

1
 
vote
vote
ベストアンサー
 

KVAR SORT、置換モジュール、およびバインダー属性を参照しているように見えます。これは、Lambda計算など、これに依存する言語で変数捕獲認識の代替を実装するために使用されます。現在、バインダーを含む用語に関する== kの動作は、2つのバインダーが、それらがバインドされているという名前の同じ名前を持つ場合にのみ比較します。バインダー内の自由変数とバインド変数の発生とは異なり、それらが同じ変数を参照するIFFを比較すると、バインダー自体の変数の名前は(現在)アルファ変換対応ではなく、名前に基づいて比較されます。 。したがって、例えば、 lambda x . x は、 lambda x . x と同じであるが、<コード> lambda y . y 。

と比較します。

言っていると、バインダーを含む式を横断し、その変数の名前を正規化する関数を書くことがないのではありません。その後、2つの異なる用語でこれを呼び出し、== kを使用してそれぞれの結果を比較することができます。その結果、結果の比較は、2つの式が等しいモジュロ名前であるかどうかを比較します。これを行う簡単な方法は、たとえば、 lambda _1 . ((lambda _2 . _2) (lambda _2 . _1)) の下にあるネストされたバインダーのレベルの数ですべてのバインダーの変数の名前を変更することです。

このアプローチを試してクラッシュや行動に遭遇した場合は、githubに問題を送ってください。報告されているバグを修正することを優先します。

 

You appear to be referring to the KVar sort, the SUBSTITUTION module, and the binder attribute, which together are used to implement variable-capture aware substitution in languages which depend on this, such as the lambda calculus. Currently, the behavior of ==K with respect to terms that contain binders is that two binders will only compare equal if they have the same name for the term bound. Unlike free variables and occurrences of bound variables within binders, which compare equal iff they refer to the same variable, the names of the variables in the binders themselves are not (currently) alpha-conversion aware and will be compared on the basis of their names. Thus, for example, lambda x . x will compare equal to lambda x . x, but not to lambda y . y.

With that being said, nothing stops you from writing a function that traverses an expression containing binders and normalizes the names of its variables. You could then call this on two different terms and compare the result from each using ==K. The resulting comparison would then compare whether two expressions are equal modulo renaming. One simple way of doing this is to rename the variable of every binder with the number of levels of nested binders it is under, for example, lambda _1 . ((lambda _2 . _2) (lambda _2 . _1)).

Please feel free to file an issue on GitHub if you try this approach and run into crashes or behavior you think is incorrect. I will prioritize fixing any bugs that are reported.

</div
 
 
 
 

関連する質問

1  ドキュメントを生成するための--pdfフラグをどのように使用しますか?  ( How do we use the pdf flag for generating documentation ) 
http://www.kframework.org /index.php/lesson_4,_lambda:_documentation._LateX_ATTRIBUTES kompile lambda --pdf を使用する必要があるが、実行したとき...

0  連結された用語とは何ですか?  ( What is a concatenated term and in what contexts are they unexpected ) 
私の主な質問は、「予期せぬ連結期間」ということです。私はこの1つを交絡しているかもしれない他の問題のスルーがあるかもしれませんが、私は以下のエラーのためにいくつかの文脈を持っています。 私は bar の用語 foo と bar の Map の bar を持って...

0  kにおけるアルファ当量比較  ( Alpha equivalence comparison in k ) 
は、2つのK用語の間の構造的等価性とアルファ当量比較がありますか? アルファ変換を行うように見える置換モジュールがあるので、同等のものがあるかどうか疑問に思いました。 ある場合は、特定の構文から抽象化された方法でそのような機能を定義することは可能ですか?たとえ...

2  「要求」と「副」の違いの違い  ( Difference between requires and when side conditions ) 
例えば @Inject private Logger log; 0 が私のリストにあるときにルールを加熱したい場合は、ルールを加熱したい場合<コード> 998876621 @Inject private Logger log; 2 または @Inject ...

0  他の種類のプロダクションを正しく再利用する方法は?  ( How to correctly reuse productions in other sorts ) 
構文を持っています: <事前> <コード> syntax Exp ::= Int | Bool | Exp Exp > Exp + Exp [left] > "...

1  K設定セルはタイプチェックされますか?  ( When are k configuration cells type checked ) 
は、トップソートの整形プログラム(例えば<コード> Pgm など)を使用してプログラミング言語の構文を定義し、次に<コード> 99887661 セルを制限するための一般的なK個の慣用句です。 krun によって自動的に渡される特殊 $PGM 変数を使用して、...

0  #asのような#キーワードのためのドキュメント?  ( Documentation for keywords such as as ) 
9988777664 のようなキーワードとそれらの使い方のようなキーワードのどこかにドキュメントがありますか? 特に #as code> ASET は、<コードを含むセル<コード> k のセットまたは等しいセルです。 > S 構文<コード> []...

0  Krunによって出力された構成でKrunを呼び出すことは可能ですか?  ( Is it possible to call krun on the configurations output by krun ) 
kは、外部から処理できる構成の束を生成したいと思います。しかし、それでは、各構成でkを呼び出すことによって計算を再開することをお勧めします。これは可能ですか? site.com/?refuser=USERNAME0 オプションを見てみましたが、必要なもの...

0  kフレームワーク:単純な用語で置換されていませんか?  ( K framework substitution not substituting in simple terms ) 
次のkファイルを持っています: <事前> <コード> require "substitution.k" module PURE imports DOMAINS imports SUBSTITUTION syntax PSort ::...

0  遷移規則の優先順位とkの設定パターンマッチング?  ( Transition rule priority and set pattern matching in k ) 
非決定論的な規則では、他の規則を適用する前にもはや適用できないまで特定の規則を優先する方法はありますか? e.g。以下の規則(疑似コード) <事前> <コード> 1. (S U {P | Q}) => (S U {P, Q}) [prioritise] 2....




© 2022 cndgn.com All Rights Reserved. Q&Aハウス 全著作権所有