OCamlコードをCoqで検証できる "CFML" で 証明コンペに挑戦 (未完) - keigoiの日記
VSTTE 2012 Software Verification Competition というソフトウェア検証のコンペがあった。参加はオープンで、問題文もPDFで配布されている。 id:yoshihiro503 がチームtebasakiというチームでがんばっていた。僕はCoqに慣れていなかったのでチームに入るのは見送った（というかチームの人数上限4人で入れなかった）。 仕事や出張の片手間でやっていたので、結局一問も検証できなかったけど、楽しかった。 検証にはCFMLというツールを勉強しながら使った。 これを使えば OCaml のソースコードを Coq で検証できる。 それも ref型による破壊的代入つきの手続き的なOCamlを含む。 そして Coqと違い、プログラムは停止しなくてもいい。 つまり、CFMLを使えば、 手続き型プログラムを、ホーア論理+分離論理(のようなもの;後述)を使って
大阪人に関するうわさ - にわとり小屋でのプログラミング
世の中には大阪人に関する間違った認識があふれているように思う。 例えば、大阪人は縦縞のユニフォームを着ている、とか嫁さんが強くてカカア天下である、とかである。 今回はそのような間違った俗説を払拭するべくCoqで証明してみた。 Coq < Section なにわ. まず、次のような文を定めて、６つの噂を仮定する。ただし ~（にょろ） は否定を表す記号である。 Coq < Variable 大阪人である : Prop. Coq < Variable たこ焼きを食べたことがある : Prop. Coq < Variable 常に縦縞の服を着る : Prop. Coq < Variable 嫁さんの尻に敷かれてる : Prop. Coq < Variable 阪神の試合には欠かさず行く : Prop. 大阪人である is assumed たこ焼きを食べたことがある is assumed 常に縦縞の
最小共通祖先を求めるアルゴリズムの形式検証 | Wantedly Engineer Blog
競技プログラミングには概念を知っておかないと解きようがない、いわゆる覚えゲーのような問題が存在します。典型的な例が 10^9+7 といった素数で割った余りを求めろといったもので、普段業務で日常的に素数で割った余りを求めている人でもなければ、割り算がしたければフェルマーの小定理や拡張ユークリッドの互除法を使えば良いと直ぐには思い付けないのではないでしょうか。 最小共通祖先も覚えゲーで必要な概念の一種と言えます。これは読んで字のごとく、与えられた根付き木の下で2頂点に共通する祖先のうち、最も根から遠い頂点を指す概念で、例えば木の2頂点が与えられて、頂点間の経路について何かを求めろといった問題で威力を発揮することが多いです。これを用いて解ける例を挙げるとすると次の問題でしょうか。 https://atcoder.jp/contests/abc014/tasks/abc014_4 最小共通祖先を求
誰も書かないCoq入門以前の話 - 檜山正幸のキマイラ飼育記 (はてなBlog)
「WindowsへのCoqのインストール」： 事情があって、AgdaかCoqを触ってみようか、と。 事情というのは、個々の命題の証明（確認）は割と簡単そうだが、命題がイッパイあるのでウンザリな状況のことです。家計簿の計算が筆算だと面倒だから電卓を使いたい、という状況と同様です。 それでCoqのインストールは済んだのですが、処理系の使い方が分からない。個々の操作は覚えていけばいいのでしょうが、そもそもCoq処理系が何をするものなのか？ が理解できないのです。Web上にCoqの解説は幾つもあるのですが、「いやいや、そうじゃなくて、それ以前のことがサッパリわからんのですけど」という感じ。スタートラインに立てない。 それで、「Coqの解説」じゃなくて「Coqの仕様」を読んだほうがいいのかも、と https://coq.inria.fr/distrib/current/refman/ （リファレンス
CoqからのCプログラム生成 田中 哲 産業技術総合研究所 情報技術研究部門 2017-07-23 Proof Summit 2017
CoqからのCプログラム生成 田中 哲 産業技術総合研究所 情報技術研究部門 2017-07-23 Proof Summit 2017 2/48 元ネタ ● 既発表の話です ● そのうち論文が出ます ● Safe Low-level Code Generation in Coq using Monomorphization and Monadification Akira Tanaka, Reynald Affeldt, Jacques Garrigue IPSJ SIGPRO 114, 2017-06-09, will be appear at IPSJ JIP. ● ここで出てくる plugin は github にあります – https://github.com/akr/monomorphization – https://github.com/akr/monadification
Coqで証明付きのマージソートを書く - fetburner.core
この記事はTheorem Prover Advent Calendar 2016の4日目のために書かれました。 少し季節外れの記事になりますが、前期はプロ演A^1の季節でしたね。 僕のTLでもC言語の課題に苦しめられた学部生のツイートが良く回ってきましたが、 とりわけ彼らが苦戦していたのはマージソートを書く課題のようでした。 面白そうなので僕もCoqで実装してみましょう。 もちろん、証明付きで。 実装 とりあえず比較関数等の準備 Require Import Arith Div2 List Orders Sorted Permutation Program. Require Omega. Section MergeSort. Local Coercion is_true : bool >-> Sortclass. Local Hint Constructors Permutation St
Coqを勉強してます。 - Scala で TAPLを勉強しつつ LLVM コンパイラを作る日記
コンパイラを作るには型理論を理解しているとよくて、型理論を理解するには数学的な証明とかが出来ると良くて、数学的な証明をコンピュータ上で出来ると楽に正確に勉強出来ると思うので、Coqを勉強してます。 なんとなく、勉強してる訳ではなくて必要に迫られて勉強してるのですけど、数学アレルギーを治すのに良さそうな気がしています。 http://www.iij-ii.co.jp/lab/techdoc/coqt/ ここをみながら勉強中です。2の最後までやってみました。意味が良くわかってないんですけど。1は2回やってみました。あれだな、リッジレーサーを毎回、最初からやる事でどんなスピードでも対応出来る力を付けるみたいなそんな鍛え方をしてますよ。 覚えるまで何回もやれば最初は太極拳のように遅くても徐々にスピードは増して行くのだ。最初は繰り返し大切と。しかも、慣れれば自動証明ですっ飛ばせるらしいので、こんな所
IIJ Research Laboratory
ネットワークの計測と解析 インターネットの使われ方やネットワークの挙動を把握する事は、ネットワークを運用し、その技術開発を行う ために欠かせません。しかし、観測で得られるデータ量は膨大ですがノイズが多く、また、観測できるのは極めて限られた部分でしかありません。そこで、膨大なデータから意味のある情報を抽出したり、部分的な観測からより一般的な傾向を推測する事が必要となります。... インターネット基盤技術 速くて、安全で、信頼性が高く、使いやすく、など、インターネットサービスへの要求はますます高まっています。これらの要求に応えるために、インターネットの 基盤技術も日々進歩しています。いまやインターネットはつながるだけのサービスではなく、高度で複雑な機能を備えた社会基盤となりました。IIJ技術研究所は、インターネットの基盤として実現が期待される機能を提供するために、さまざまな技術課題に取り組んで
IIJ Research Laboratory
ネットワークの計測と解析 インターネットの使われ方やネットワークの挙動を把握する事は、ネットワークを運用し、その技術開発を行う ために欠かせません。しかし、観測で得られるデータ量は膨大ですがノイズが多く、また、観測できるのは極めて限られた部分でしかありません。そこで、膨大なデータから意味のある情報を抽出したり、部分的な観測からより一般的な傾向を推測する事が必要となります。... インターネット基盤技術 速くて、安全で、信頼性が高く、使いやすく、など、インターネットサービスへの要求はますます高まっています。これらの要求に応えるために、インターネットの 基盤技術も日々進歩しています。いまやインターネットはつながるだけのサービスではなく、高度で複雑な機能を備えた社会基盤となりました。IIJ技術研究所は、インターネットの基盤として実現が期待される機能を提供するために、さまざまな技術課題に取り組んで
IIJ Research Laboratory
ネットワークの計測と解析 インターネットの使われ方やネットワークの挙動を把握する事は、ネットワークを運用し、その技術開発を行う ために欠かせません。しかし、観測で得られるデータ量は膨大ですがノイズが多く、また、観測できるのは極めて限られた部分でしかありません。そこで、膨大なデータから意味のある情報を抽出したり、部分的な観測からより一般的な傾向を推測する事が必要となります。... インターネット基盤技術 速くて、安全で、信頼性が高く、使いやすく、など、インターネットサービスへの要求はますます高まっています。これらの要求に応えるために、インターネットの 基盤技術も日々進歩しています。いまやインターネットはつながるだけのサービスではなく、高度で複雑な機能を備えた社会基盤となりました。IIJ技術研究所は、インターネットの基盤として実現が期待される機能を提供するために、さまざまな技術課題に取り組んで
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Coq で証明付き Web アプリを作る #adf2015
Coqにおける検証された プログラム運算の拡張-2zh
セキュア計算(法政大学 理工学部 応用情報工学科 4年次春学期 (2013年度))
anarchy proof -
http://as305.dyndns.org/aps/problem