We continue our work on formal verification of Rust programs with our tool coq-of-rust, to translate Rust code to the formal proof system Coq. One of the limitation we had was the handling of primitive constructs from the standard library of Rust, like Option::unwrap_or_default or all other primitive functions. For each of these functions, we had to make a Coq definition to represent its behavior.
ネットワークの計測と解析 インターネットの使われ方やネットワークの挙動を把握する事は、ネットワークを運用し、その技術開発を行う ために欠かせません。しかし、観測で得られるデータ量は膨大ですがノイズが多く、また、観測できるのは極めて限られた部分でしかありません。そこで、膨大なデータから意味のある情報を抽出したり、部分的な観測からより一般的な傾向を推測する事が必要となります。... インターネット基盤技術 速くて、安全で、信頼性が高く、使いやすく、など、インターネットサービスへの要求はますます高まっています。これらの要求に応えるために、インターネットの 基盤技術も日々進歩しています。いまやインターネットはつながるだけのサービスではなく、高度で複雑な機能を備えた社会基盤となりました。IIJ技術研究所は、インターネットの基盤として実現が期待される機能を提供するために、さまざまな技術課題に取り組んで
先週の土日にこのオンラインセミナーに参加してみた。 定理証明支援系 Coq チュートリアル - connpass 定理証明は、名前は聞くけど触ったことはなくて、興味はあるけど本を買うほどのモチベーションはないし、誰か詳しい人が要点だけ教えてくれたりしないかな〜。と思っていたところ、まさにぴったりのイベントが。なんていうか、昔ならこういうのは東京まで行かないと参加できなかった気がするけど、家からオンラインで参加できるようになったのは嬉しいね。 日程は5時間 x 2日という長丁場で、説明だけでなく練習問題もあるのでとっても疲れた!でもこういうのって自分で手を動かさないと「わかったような気になった」だけで終わりがちだから、演習があるのはとてもありがたい。 Coqの感想 これまでいろんなプログラミング言語を触ってきたけど、証明とプログラムが一体になった環境は新鮮で面白かった。「整数」「文字列」みた
最近、定理証明支援のCoqを入門している。というのは、以前の職場にいたときの職場でもCoqをやっている先輩がいて、今回の職場でも定理証明支援系を使っている同僚がいて、しかも最近自分はプログラミング言語実装をやっているためか、Coqや依存型について聞かれることがあるので、一念発起して取り組み始めた。 しかし、案の定、何から始めたらいいのかわからず入門に躓いてしまい、かなり難しいと感じた。しかも一番最初に読み始めた本が、Certified Programming with Dependent Typeという初心者向けではない本だったため、事態は混迷を極めていた。 そんな難関を乗り越えて2ヶ月、ようやく基本的な証明をできるまでたどり着いたので、メモ代わりにどう入門すればよいか残しておこうと思う。 1. 関数型のプログラミング言語を学ぶ 自分は関数型プログラミング言語の処理系を設計・実装したことが
この記事は言語実装 Advent Calendar 2020 の5日目の記事です. 一度でも型推論器を書いたことがあれば,そのあまりの邪悪さ,あるいはその複雑さに恐れ慄いたことでしょう. 参照を用いて単一化を実現しようものなら構文木は参照に汚染され,純粋関数型に実装しようものなら大量の型代入をどのような順序で適用したものか悩まされる. これは Hindley-Milner 型推論器を実装する上での宿命のようなものです. 本記事では,MLのサブセット——型付きλ計算をletと参照で拡張した,let多相をサポートする言語——の型推論器を Coq で実装し,その正当性を証明します. Coq で検証を行うことで我々は型推論器のバグへの恐怖とデバッグの労力から真に解放され,枕を高くして眠ることができることでしょう. もっとも、型付きλ計算を let 多相で拡張した言語の型推論器の正当性は実はすでに証
What is PeaCoq? Over the past year, I have developed a Coq frontend called PeaCoq (not to be mistaken with Yves Bertot’s Pcoq). If you wish to play with it before or while reading this article, I made an online version available here. Note that it will reset after 15 minutes of inactivity, and that it might go down any time! There have been several attempts at improving user interfaces for proof a
This document discusses the Coq proof assistant. It provides examples of defining concepts like booleans, natural numbers, and functions in Coq. It demonstrates tactics for proving properties like De Morgan's laws. It also shows how to define recursive functions over natural numbers like addition and equality testing. The document aims to introduce basic concepts and usage of the Coq system throug
資料: slides (last version): slides addendum about groups: html, pdf (automatically generated) slides (previous versions): [2015-07-24 Fri]: 京都大学の集中講義で使った資料(約14時間): slides (addendum about groups) [2014-12-15 Mon]: 名古屋大学の集中講義 で使った資料(約9時間): slides (addendum about groups) [2014-09-07 Sun]: 日本ソフトウェア科学会 第31回大会のチュートリアル (定理証明支援系Coq入門) で使った資料(4時間): slides Coq/SSReflect/MathCompの設定 参考文献: ssr.bib, coq.bib, it
先日、東京の会社から名古屋の会社に転職された@zakky_devさんの歓迎会がありました*1 。そこで、@zakky_devさんにCoqでリストの結合則を証明するチュートリアルをやってもらいました。 せっかくなので、そのときの台本を公開します。だいたい30分くらいの内容です。 Coqのインストール ぐぐりましょう。 Welcome ! | The Coq Proof Assistant Coq を始めよう Coqとは みなさん、自動化してる・してないなどの違いはあると思うんですが、プログラムを書いたらテストをすると思います。 ただテストはどうしても「こういう入力があったら、こういう出力がある」というのを並べていくことになるので、どうしても有限のパターンしか確認できません。 で、これで十分なこともあるんですが、中にはものすごい信頼性がいるプログラムで、有限のパターンの保証だけではたりない場合
2. Agenda はじめに Part I : 「型の理論」をふりかえる Part II : Curry-Howard対応について Part III: Coq入門 3. はじめに 現在、HoTT(Homotopy Type Theory)と呼 ばれる新しい型の理論とそれを基礎付ける Univalent Theoryと呼ばれる新しい数学理論 が、熱い関心を集めている。 Univalent Theoryは、数学者のVladimir Voevodskyが、論理学者Per Martin-Löfの型 の理論を「再発見」したことに始まる。 この新しい分野は、21世紀の数学とコンピュ ータサイエンスの双方に、大きな影響を与え ていくだろう。
開催勉強会 ProofCafeではいくつかの勉強会を定期開催しています。 詳細は個別のページをご覧ください。 Coqを用いたプログラムの証明について勉強する勉強会です。 コーヒーを飲みながら楽しく証明しましょう。 TAPL-nagoya Types and Programming Laungages(通称TAPL)の読書会です。 ScalaやF#などの静的型付け言語の基礎になっている型理論について学びます。 休日カフェタイム, KCTNagoya 圏論に関する勉強会です。 どえりゃあ Haskell Haskellに関する勉強会です。 サービス Software Foundations(和訳) Benjamin C. Pierce氏による同名のテキストの和訳です。関数プ ログラミグやラムダ計算についてCoqによる実例を交えながら丁寧 に説明されています。 Cochin Coqの定理検索サー
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く