プログラミング言語の型と証明を検討する
プログラミング言語における型、文脈、証明の見方。
Kelvin Qian, Scott Smith, Brandon Stride, Shiwei Weng, Ke Wu
― 1 分で読む
目次
この記事では、コアプログラミング言語とその拡張について話すよ。主な焦点は、タイプをどう定義するか、これらのタイプがどのように関連しているか、そして言語を支配するルールについて。言語の構造、タイプの概念、そしてそれらが私たちのシステムでどう相互作用するかを説明するね。
プログラミング言語のタイプ
タイプはプログラミング言語で重要だよ。変数が正しい種類の情報を保持することを保証するから。例えば、数字を保持するための変数が文字列を値として取ってはいけない。この記事では、さまざまなタイプとその使い方を定義するよ。
タイプの定義
私たちの言語にはいくつかのタイプがあるよ。整数やブール値のような基本的なタイプや、関数やレコードのような複雑なタイプもある。各タイプには、その値がどんなものであるべきかに関する独自のルールがあるんだ。
基本タイプ
- 整数: これは1、2、-3のような整数。
- ブール値: これは真偽値で、真または偽のいずれか。
複雑タイプ
- 関数: 関数は入力を受け取り、出力を生成するコードの塊だよ。パラメータで定義される。
- レコード: レコードはキーと値のペアのコレクション。関連する情報をグループ化できる。
タイプのサイズ
タイプのサイズは、その構造によって異なることがあるよ。例えば、単純な整数はサイズが1だけど、レコードは含まれるフィールドの数に依存したサイズを持つことがある。タイプのサイズを理解することはメモリ管理にとって重要なんだ。
コア言語
コア言語はすべての基盤だよ。プログラムを書くための基本的な構文とルールを紹介する。どのようにこの言語が機能するかを話すね。
構文
コア言語の構文は、宣言、式、文などのさまざまな要素から構成される。一般的なプログラムは、変数を宣言してから計算を行ったり、関数を呼び出したりするよ。
操作的意味論
操作的意味論は、私たちの言語の文がプログラムの実行にどのように影響するかを説明する。各操作はプログラムの状態を変化させることになっていて、プログラムがどのように動くのかを理解するために不可欠なんだ。
コア言語の証明
証明は私たちの言語が期待通りに動くことを確保するために重要な役割を果たすよ。特定の性質が真であることを示すことで、言語内の操作の整合性を保証できるんだ。
基本ケース
証明では、よく基本ケースから始めるよ。これはルールが複雑な条件なしに適用される最も単純なシナリオなんだ。基本的な構造のために特定の性質が真であることを示すことができるよ。
帰納ステップ
基本ケースを証明した後、帰納ステップに進む。ここでは、私たちの性質が小さいサイズや単純なケースに対して成り立つと仮定して、それが大きい場合やより複雑なケースにも成り立つことを示す。この方法は、再帰関数や構造の動作を証明するのに役立つんだ。
コンテキストと置換
焦点を当てるエリアの一つは、言語内でのコンテキストと置換がどう機能するかだよ。コンテキストについて話すときは、式が評価される環境を指してる。置換は、式の一部を他の式や値で置き換えることを指すよ。
コンテキスト
コンテキストには変数や値のプレースホルダーが含まれることがある。例えば、特定の位置で整数値を期待するようにコンテキストが設定されることもある。値を代入すると、そのコンテキストは新しい値に合わせて変わる。
置換
値が式に置換されるとき、それはタイプのルールに従わなきゃいけない。ブール型が期待されるところに整数を代入すると、エラーが出るよ。
拡張言語機能
コア言語に基づいてさらに拡張機能を導入することで、より複雑なプログラミングタスクが可能になるよ。これらの拡張では新しいタイプや操作が追加され、より柔軟で強力になるんだ。
精緻化
精緻化は、タイプを使用する際に特定の条件が満たされていることを保証する方法だよ。ある値は特定のタイプであるだけでなく、追加の基準を満たさなきゃいけない。例えば、数値が正でなければならないこともある。
多態性
多態性は、関数が異なるタイプの値で動作しつつ、タイプの安全性を維持できるようにするんだ。この意味は、単一の関数が整数やブール値など、異なるタイプを扱えるってこと。
拡張言語の証明
コア言語と同様に、拡張機能のために証明を確立する必要があるよ。これにより、言語の新しい部分が正しく動作することを保証するんだ。
完全性
完全性は、特定のタイプを導出できるなら、それを私たちの言語で使う方法も見つけられることを意味する。あるタイプが生成できると主張するなら、それをすべてのコンテキストで正しく使えるようにしなきゃいけない。
健全性
健全性は完全性の逆だね。それは、私たちのシステムでタイプがチェックを通った場合、実行中にエラーを引き起こさないことを保証するよ。この特性は、言語で書かれたプログラムの整合性を維持するのに役立つんだ。
結論
要するに、私たちはプログラミング言語とその拡張の基本的な側面を探求してきたよ。タイプ、コンテキスト、そして証明は、言語がどのように機能するかを理解するために不可欠なんだ。これらの概念を基に、プログラマーが頑強で柔軟なアプリケーションを作成できるように、より複雑な機能を導入していくよ。完備性と健全性を確保することで、開発者に信頼できるフレームワークを提供するんだ。
タイトル: Semantic-Type-Guided Bug Finding
概要: In recent years, there has been an increased interest in tools that establish \emph{incorrectness} rather than correctness of program properties. In this work we build on this approach by developing a novel methodology to prove incorrectness of \emph{semantic typing} properties of functional programs, extending the incorrectness approach to the model theory of functional program typing. We define a semantic type refuter which refutes semantic typings for a simple functional language. We prove our refuter is co-recursively enumerable, and that it is sound and complete with respect to a semantic typing notion. An initial implementation is described which uses symbolic evaluation to efficiently find type errors over a functional language with a rich type system.
著者: Kelvin Qian, Scott Smith, Brandon Stride, Shiwei Weng, Ke Wu
最終更新: 2024-09-20 00:00:00
言語: English
ソースURL: https://arxiv.org/abs/2409.13896
ソースPDF: https://arxiv.org/pdf/2409.13896
ライセンス: https://creativecommons.org/licenses/by/4.0/
変更点: この要約はAIの助けを借りて作成されており、不正確な場合があります。正確な情報については、ここにリンクされている元のソース文書を参照してください。
オープンアクセスの相互運用性を利用させていただいた arxiv に感謝します。
参照リンク
- https://archive.softwareheritage.org/swh:1:cnt:6b61de06aa8d945714c9a31cdd4fd0b17f1d0f6a;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/lang-jayil/ast.ml
- https://archive.softwareheritage.org/swh:1:cnt:9079b3d3ddd04c930645e94fc4bfbe6b41436bef;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/evaluator.ml;lines=75
- https://archive.softwareheritage.org/swh:1:cnt:54694433d1e7c0bd80916a0b2c849e975a51b702;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src-vendor/sudu/z3_api.ml;lines=82-85
- https://archive.softwareheritage.org/swh:1:cnt:09f8afbc874ac8f6108bd78ba6f293a1091a92f8;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/from_dbmc/solve/riddler.ml;lines=11-84
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/from_dbmc/solve/riddler.ml;lines=280-305
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/from_dbmc/solve/riddler.ml;lines=97-135
- https://archive.softwareheritage.org/swh:1:cnt:d7daef5e3497108f8e4f8115be9ef37de4c84556;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/concolic_key.ml
- https://archive.softwareheritage.org/swh:1:cnt:f3037b9e2b16697538dac8e248a86a66d06594ab;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/session.ml;lines=147-151
- https://archive.softwareheritage.org/swh:1:cnt:227eaae664f89cca38bf5497ddcf4d26d69565b8;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.mli
- https://archive.softwareheritage.org/swh:1:cnt:074a434052dae6b7480806c5a60199bee440e3b6;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.ml;lines=173
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.ml;lines=306-310
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.ml;lines=121
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.ml;lines=242
- https://archive.softwareheritage.org/swh:1:cnt:897738a3ab8aea12cc16d0b20930e9dd779a7e84;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/target.ml
- https://archive.softwareheritage.org/swh:1:cnt:291d602ef65d8c9e74b06fc54cddd971cdac3450;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/target_queue.ml;lines=162
- https://archive.softwareheritage.org/swh:1:cnt:e197f8b7eb409c418809d912562dd567082c337a;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/symbolic_session.ml;lines=71-105
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.ml;lines=334
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/session.ml;lines=10
- https://archive.softwareheritage.org/swh:1:cnt:b6ee1c07f731325af6eacf974c7149f4b96604fa;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/symbolic_session.mli
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/session.ml;lines=69-177
- https://archive.softwareheritage.org/swh:1:cnt:23ea05d9ac6d359a439a8f6905bbd0f5d49d81a9;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:81fd6589252aaad05bc3c267a92ae267cb1757f9;anchor=swh:1:rev:50074785b0709bdac21cc4dd4acc9eea7b159d76;path=/src/dbmc/concolic/concolic_driver.ml;lines=54
- https://archive.softwareheritage.org/swh:1:cnt:6309abee6f2a3d2711c4e72dd54fe9b1f79c3384;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/driver.mli;lines=21
- https://archive.softwareheritage.org/swh:1:cnt:008d588a1586fe2b546e49167e7ae89a99786b8c;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/options.ml;lines=5
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/options.ml;lines=20
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/options.ml;lines=48-95
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/evaluator.ml;lines=324
- https://archive.softwareheritage.org/swh:1:cnt:26396b1f23ecffce5c8f579c6f227b16fae20f7a;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src-test/concolic/test_concolic.ml;lines=13
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/symbolic_session.ml;lines=288
- https://archive.softwareheritage.org/swh:1:cnt:a8776bcbcd5da0f645b952dfb8a316875422db0e;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/benchmark/concolic/cbenchmark.ml;lines=62-118