ソフトウェアの基礎(beta)¶ 本ドキュメントは実験中のものです。 安定板は http://proofcafe.org/sf/ を参照してください。 epub版: http://proofcafe.org/sf-beta/software_foundation_1.0.2.epub mobi版: http://proofcafe.org/sf-beta/software_foundation_1.0.2.mobi Contents:
結論 最強のプログラム検証器 最強の関数型言語 最強のプログラム検証器 Coqは最強の表現力を持つ仕様記述言語を使う 仕様記述言語は検証したいこと を記述するための言語 表現力は検証器によって全然違う 表現できる範囲が、検証器の限界 Coqのそれは高階述語論理 ← 最強 最強のプログラム検証器 Coqを使うためにはPhDが必要? 高校生でも練習すればできる (c.f. プログラミングCoq) 最強のプログラム検証器 証明を人間が与えるのが大変? タクティックによる自動化はOCamlでいくらでも可能 型チェッカはタクティックと独立なので安全 既にomegaなどの自動証明アルゴリズムを実装したタクティックあり 最強の関数型言語 Coqは(型の表現力が)最強の関数型言語 型の表現力が最強 型推論は完全ではない 停止性は保証しなければならない 注意: ここでの関数型言語とは (ラムダ計算を基礎とし
この記事は「Theorem Prover Advent Calendar 2013」6日目の記事です。 http://qiita.com/advent-calendar/2013/theorem_prover 神田「野らぼー」にて、地下の薄暗い店内で… 「そう言えばこないだ隣で起こってたポインタオーバーラン、対応大変そうだったですけどちゃんと家に帰れてたんでしょうかね、新婚なのに…」 「ヌルポとかポインタオーバーランとか、どうして無くならないんだろうね。その時はみんな手を抜いてるつもりなんて毛頭なくて、一生懸命考えて大丈夫だと思ってるはずなんだけどね。レビューもして、それでも起こった後でみんなでソース見てみると、なんで気づかなかったんだよ!ってことになる。」 「人間って、そういうの苦手なんでしょうねきっと。ほら、『何かほかにありませんか』って聞かれても出てこないじゃないですか。静的な解析っ
参考:人材獲得作戦・4 試験問題ほか: 人生を書き換える者すらいた。 Lv4に評価されるためには、最短性の完全なチェックが必要だったのでCoqで証明してみた。 まず、accessiblesという関数を定義し、以下の性質を証明した。 ここでplengthはパスの長さを計る関数で、Path x pはpがxを起点としたパスであるという述語。endofはパスの終点を求める関数。 Fixpoint accessibles (start : node) (len : nat) : list path := match len with | O => (PUnit start) :: nil | S n' => div_equiv path_equiv_dec @@ (flat_map expand @@ accessibles start n') end. この関数はstartから始まってlenの長さ
2015/12/10 追記: バグを本気で無くしたい方はこんな良く辺鄙なブログなんて見ずにソフトウェアエンジニアリング系の国際学会に行くなり、そこの論文を読むなりするといいと思います。ICSEなんかは日本語の勉強会資料もあってとっつきやすいでしょう。 バグのないプログラムを作る方法について色々聞きかじったことを, 脈絡なく訳の分からない説明でつらつらと書きならべます. テスト 割と古典的な方法ですね. プログラミングコンテストでもお馴染みの方式です. Java だと JUnit (4) みたいなのを使います. 手作りケース とりあえず試してみるケース コーナーケース ミスの発生しやすそうなところを突くためのケース ランダムケース ランダムに爆撃するためのケース みたいなものを作って, 仕様とマッチするか確認します. 当たり前ですが, 基本的には下手な鉄砲も数撃ちゃ当たる方式なので, 運が悪
(* 注意:今回はCoq 8.1以上を使用。 *) 今回は、らくがきえんじんで、昔 言及されていた、クイックソートに挑戦してみる。 Coqで、再帰する関数を書く場合は、Definitionコマンドではなく、Fixpointコマンドを使う。 しかし、Fixpointによる関数定義では、明らかに停止する構造を持つ必要がある。 Coqでは、必ず停止する関数のみが定義できる、という制限のため、このように再帰する関数を定義するのは難しいが、Coqで作った関数は、必ず停止して結果を返す、という性質を保っている。 しかし、Fixpointによる定義では、簡単に定義できない再帰関数もある。 例えば、次のように、クイックソートの関数を素直にかいてみると、以下のようなエラーになる。 (* クイックソートの定義 失敗例 *) Fixpoint qsort (l : list A) : list A := mat
The Coq Proof Assistant A Tutorial Version 1 Gérard Huet, Gilles Kahn and Christine Paulin-Mohring LogiCal Project 1This research was partly supported by IST working group “Types” Getting started Coq is a Proof Assistant for a Logical Framework known as the Calculus of Inductive Constructions. It allows the interactive construction of formal proofs, and also the manipulation of functional programs
Using Proof Assistants for Programming Language Research or, How to write your next POPL paper in Coq San Francisco, CA January 8th, 2008 A tutorial on the use of the Coq proof assistant in formalizing programming language metatheory. This tutorial will be tailored to people who are familiar with syntactic proofs of programming language metatheory, such as type soundness, but have never used a pro
ネットワークの計測と解析 インターネットの使われ方やネットワークの挙動を把握する事は、ネットワークを運用し、その技術開発を行う ために欠かせません。しかし、観測で得られるデータ量は膨大ですがノイズが多く、また、観測できるのは極めて限られた部分でしかありません。そこで、膨大なデータから意味のある情報を抽出したり、部分的な観測からより一般的な傾向を推測する事が必要となります。... インターネット基盤技術 速くて、安全で、信頼性が高く、使いやすく、など、インターネットサービスへの要求はますます高まっています。これらの要求に応えるために、インターネットの 基盤技術も日々進歩しています。いまやインターネットはつながるだけのサービスではなく、高度で複雑な機能を備えた社会基盤となりました。IIJ技術研究所は、インターネットの基盤として実現が期待される機能を提供するために、さまざまな技術課題に取り組んで
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く