diff options
| author | Yann Herklotz <git@yannherklotz.com> | 2020-11-26 01:00:41 +0000 |
|---|---|---|
| committer | Yann Herklotz <git@yannherklotz.com> | 2020-11-26 01:00:41 +0000 |
| commit | fa4b252945a870100305c159d20e264be18973ce (patch) | |
| tree | 435cbd07a2af45f3f08dc8ac892fa48044047eeb /docs/proof/Maps.html | |
| parent | 29bee524cccfe08c680f655b1969a4c421e0a969 (diff) | |
| download | vericert-fa4b252945a870100305c159d20e264be18973ce.tar.gz vericert-fa4b252945a870100305c159d20e264be18973ce.zip | |
Add proof documentation
Diffstat (limited to 'docs/proof/Maps.html')
| -rw-r--r-- | docs/proof/Maps.html | 65 |
1 files changed, 65 insertions, 0 deletions
diff --git a/docs/proof/Maps.html b/docs/proof/Maps.html new file mode 100644 index 0000000..296287e --- /dev/null +++ b/docs/proof/Maps.html @@ -0,0 +1,65 @@ +<?xml version="1.0" encoding="utf-8" ?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml" class="alectryon-standalone" xml:lang="en" lang="en"> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> +<meta name="generator" content="Docutils 0.16: http://docutils.sourceforge.net/" /> +<title>Maps.v</title> +<link rel="stylesheet" href="alectryon.css" type="text/css" /> +<link rel="stylesheet" href="docutils_basic.css" type="text/css" /> +<link rel="stylesheet" href="tango_subtle.css" type="text/css" /> +<link rel="stylesheet" href="tango_subtle.min.css" type="text/css" /> +<script type="text/javascript" src="alectryon.js"></script> +<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/IBM-type/0.5.4/css/ibm-type.min.css" integrity="sha512-sky5cf9Ts6FY1kstGOBHSybfKqdHR41M0Ldb0BjNiv3ifltoQIsg0zIaQ+wwdwgQ0w9vKFW7Js50lxH9vqNSSw==" crossorigin="anonymous" /> +<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/firacode/5.2.0/fira_code.min.css" integrity="sha512-MbysAYimH1hH2xYzkkMHB6MqxBqfP0megxsCLknbYqHVwXTCg9IqHbk+ZP/vnhO8UEW6PaXAkKe2vQ+SWACxxA==" crossorigin="anonymous" /> +</head> +<body> +<div class="alectryon-root alectryon-floating"><div class="document"> + + +<pre class="alectryon-io"><!-- Generator: Alectryon v1.0 --><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">From</span> vericert <span class="kn">Require Import</span> Vericertlib.</span></span><span class="coq-wsp"> +</span></span><span class="coq-wsp"><span class="highlight"> +</span></span><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">From</span> compcert <span class="kn">Require Export</span> Maps.</span></span><span class="coq-wsp"> +</span></span><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">From</span> compcert <span class="kn">Require Import</span> Errors.</span></span><span class="coq-wsp"> +</span></span><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">Import</span> PTree.</span></span><span class="coq-wsp"> +</span></span><span class="coq-wsp"><span class="highlight"> +</span></span><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">Set Implicit Arguments</span>.</span></span><span class="coq-wsp"> +</span></span><span class="coq-wsp"><span class="highlight"> +</span></span><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">Local Open Scope</span> error_monad_scope.</span></span><span class="coq-wsp"> +</span></span><span class="coq-wsp"><span class="highlight"> +<span class="sd">(** Instance of traverse for [PTree] and [Errors]. This should maybe be generalised</span> +<span class="sd"> in the future. *)</span> + +</span></span><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">Module</span> <span class="nf">PTree</span>.</span></span><span class="coq-wsp"> +</span></span><span class="coq-wsp"><span class="highlight"> +</span></span><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">Fixpoint</span> <span class="nf">xtraverse</span> (<span class="nv">A</span> <span class="nv">B</span> : <span class="kt">Type</span>) (<span class="nv">f</span> : positive -> A -> res B) (<span class="nv">m</span> : PTree.t A) (<span class="nv">i</span> : positive) + {<span class="nv">struct</span> <span class="nv">m</span>} : res (PTree.t B) := + <span class="kr">match</span> m <span class="kr">with</span> + | Leaf => OK Leaf + | Node l o r => + <span class="kr">let</span> <span class="nv">newo</span> := + <span class="kr">match</span> o <span class="kr">with</span> + | None => OK None + | Some x => + <span class="kr">match</span> f (prev i) x <span class="kr">with</span> + | Error err => Error err + | OK val => OK (Some val) + <span class="kr">end</span> + <span class="kr">end</span> <span class="kr">in</span> + <span class="kr">match</span> newo <span class="kr">with</span> + | OK no => + <span class="kp">do</span> nl <- xtraverse f l (xO i); + <span class="kp">do</span> nr <- xtraverse f r (xI i); + OK (Node nl no nr) + | Error msg => Error msg + <span class="kr">end</span> + <span class="kr">end</span>.</span></span><span class="coq-wsp"> +</span></span><span class="coq-wsp"><span class="highlight"> +</span></span><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">Definition</span> <span class="nf">traverse</span> (<span class="nv">A</span> <span class="nv">B</span> : <span class="kt">Type</span>) (<span class="nv">f</span> : positive -> A -> res B) <span class="nv">m</span> := xtraverse f m xH.</span></span><span class="coq-wsp"> +</span></span><span class="coq-wsp"><span class="highlight"> +</span></span><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">Definition</span> <span class="nf">traverse1</span> (<span class="nv">A</span> <span class="nv">B</span> : <span class="kt">Type</span>) (<span class="nv">f</span> : A -> res B) := traverse (<span class="kr">fun</span> <span class="nv">_</span> => f).</span></span><span class="coq-wsp"> +</span></span><span class="coq-wsp"><span class="highlight"> +</span></span><span class="coq-sentence"><span class="coq-input"><span class="highlight"><span class="kn">End</span> <span class="nf">PTree</span>.</span></span></span></pre> +</div> +</div></body> +</html> |