J E L L Y E N T
Untangling Mechanized Proofs

Posted
by

Clément Pit-Claudel

on Mon 09 November 2020
in Instruments.

Point out edits or corrections.

Alectryon (named after the Greek god of rooster) is a assortment of tools for writing technical paperwork that mix Coq code and prose, in a vogue generally called literate programming.

Coq proofs are no longer easy to have in isolation: unlike pen-and-paper proofs, proof scripts handiest anecdote the steps to exhaust (induct on x, practice a theorem, …), no longer the states (dreams) that these steps lead to. Due to this, easy proof scripts are if fact be told incomprehensible with out the support of an interactive interface esteem CoqIDE or Proof Frequent.

The most typical skill in this deadline for sharing proofs with readers with out forcing them to urge Coq is to manually reproduction Coq’s output into provide code feedback — a leisurely, error-inclined, and brittle route of. Any text that accompanies the proof will be embedded in feedback, making for a painful editing journey.

Alectryon does better: it robotically captures Coq’s output and interleaves it with proof scripts to assemble interactive webpages, and it enables you to toggle between prose- and code-oriented perspectives on the the same doc so as that you will seemingly be ready to exhaust your celebrated text editing mode for writing prose and your celebrated Coq IDE for writing proofs.

I in reality have a discuss this at SLE2020 on November 16th; you ought to be half of!

Under, you will seemingly be ready to search for 3 examples: in the major one I asked Alectryon to anecdote the outcome of a single Affirm express. Within the 2d, I recorded an error message printed by Coq. Within the third, I recorded a easy proof script — try hovering or clicking on Coq sentences. Within the closing, I’ve passe hidden Inform Proof instructions to order how every tactic participates in constructing a proof term.

bool_ind : forall P : bool -> Prop, P ethical -> P faux -> forall b : bool, P b
The term "ethical" has kind "bool" while it is expected to have kind "nat".


  
  
     reflexivity.
  

A: Form

a: A

l: list A

IHl: rev (rev l) = l


rev (rev (a :: l)) = a :: l

A: Form

a: A

l: list A

IHl: rev (rev l) = l


rev (rev l ++ a :: nil) = a :: l

A: Form

a: A

l: list A

IHl: rev (rev l) = l


rev (a :: nil) ++ rev (rev l) = a :: l

A: Form

a: A

l: list A

IHl: rev (rev l) = l


rev (a :: nil) ++ l = a :: l

A: Form

a: A

l: list A

IHl: rev (rev l) = l


a :: l = a :: l

reflexivity. Qed.
Context (classical: forall A, A / ~ A).

classical: forall A : Prop, A / ~ A


forall A : Prop, ~ ~ A -> A

classical: forall A : Prop, A / ~ A


forall A : Prop, ~ ~ A -> A

classical: forall A0 : Prop, A0 / ~ A0

A: Prop

notnot_A: ~ ~ A


A

(fun (A : Prop) (notnot_A : ~ ~ A) => ?Procedure)

classical: forall A0 : Prop, A0 / ~ A0

A: Prop

notnot_A: ~ ~ A

_A: A


A

(fun (A : Prop) (notnot_A : ~ ~ A) => let o : A / ~ A := classical A in match o with | or_introl _A => ?Procedure | or_intror not_A => ?Goal0 cease)

classical: forall A0 : Prop, A0 / ~ A0

A: Prop

notnot_A: ~ ~ A

_A: A


A

assumption.
(fun (A : Prop) (notnot_A : ~ ~ A) => let o : A / ~ A := classical A in match o with | or_introl _A => _A | or_intror not_A => ?Procedure cease)

classical: forall A0 : Prop, A0 / ~ A0

A: Prop

notnot_A: ~ ~ A

not_A: ~ A


A

elim (notnot_A not_A).
(fun (A : Prop) (notnot_A : ~ ~ A) => let o : A / ~ A := classical A in match o with | or_introl _A => _A | or_intror not_A => False_ind A (notnot_A not_A) cease)
Qed.

Incidentally, I wrote an instructional paper at SLE2020 (November 16) on Alectryon (preprint on my online page since the DOI hyperlink would not resolve yet). It has plenty of cool visualizations and examples, it goes into a long way more depth than this intro, and importantly it has the total associated work, including many of stuff on procedural vs declarative proofs. This blog put up, the paper, and the talk had been all constructed with Alectryon.

If that is your first time on this blog, which that you can presumably must check the very immediate tutorial on navigating these visualizations before persevering with with the rest of this put up.

A immediate tour of Alectryon

The library became written with two scenarios in mind:

  • Making it more uncomplicated to browse Coq trends (even supposing these trends are no longer written in literate vogue) by turning Coq provide info into webpages allowing readers to replay proofs of their browser (the “Proviola” vogue). As a demo, I recorded dreams and responses for a total fabricate of the Flocq library.

  • Writing paperwork mixing Coq provide code and explanatory prose, either ranging from a text file containing special directives (the “coqtex” and “coqrst” vogue, passe in Coq’s reference guide), or ranging from a Coq file containing special feedback (the “coqdoc” vogue, passe in CPDT, Instrument foundations, and loads others.).

    The Alectryon paper, this blog put up, and my SLE talk are examples of the customary (they’re written in reStructuredText, a Markdown-esteem markup language); as one other example, here is a chapter from FRAP and one from CPDT, converted to reStructuredText by hand (trade the URLs to .rst to be aware the sources).

    As a demo of the latter here’s a fleshy fabricate of Logical Foundations.

There is no strengthen for attaching bits of documentation to particular bits of code, esteem definitions, axioms, variables, and loads others. As I’ve written in the previous, I judge that is a definite job (“docstrings”), ideally to be handled by Coq itself (equivalent to the draw in which it tracks the body and placement of definitions). Alectryon also would not strengthen hyperlink Coq terms to their definitions esteem coqdoc can, nonetheless I idea to implement this at closing.

Generating webpages

Alectryon’s foremost cause is to anecdote Coq’s outputs and interleave them with the corresponding inputs to receive an interactive webpage:


l : list nat, dimension (rev l) = dimension l


l : list nat, dimension (rev l) = dimension l


dimension (rev l) = dimension l


dimension (rev nil) = dimension nil


dimension (rev nil) = dimension nil

reflexivity.

n: nat

l': list nat

IHl': dimension (rev l') = dimension l'


dimension (rev (n :: l')) = dimension (n :: l')

n: nat

l': list nat

IHl': dimension (rev l') = dimension l'


dimension (rev l' ++ n :: nil) = S (dimension l')

n: nat

l': list nat

IHl': dimension (rev l') = dimension l'


dimension (rev l') + dimension (n :: nil) = S (dimension l')

n: nat

l': list nat

IHl': dimension (rev l') = dimension l'


dimension (n :: nil) + dimension (rev l') = S (dimension l')

n: nat

l': list nat

IHl': dimension (rev l') = dimension l'


S (dimension (rev l')) = S (dimension l')

n: nat

l': list nat

IHl': dimension (rev l') = dimension l'


S (dimension l') = S (dimension l')

reflexivity. Qed.
rev_length : l : list nat, dimension (rev l) = dimension l

Because that is an interactive webpage, we can practice all kinds of put up-processing to the output, esteem the exhaust of MathJax to originate a math proof a microscopic more readable:


ccForall{n : ccNat{}}{2 occasions ccNsum{i}{n}{i} = n occasions (n + 1)}


ccForall{n : ccNat{}}{2 occasions ccNsum{i}{n}{i} = n occasions (n + 1)}


2 occasions 0 = 0 occasions (0 + 1)


2 occasions 0 = 0 occasions (0 + 1)

reflexivity.

n: ccNat{}

IHn: 2 occasions ccNsum{i}{n}{i} = n occasions (n + 1)


2 occasions (ccSucc{ n} + ccNsum{i}{n}{i}) = ccSucc{ n} occasions (ccSucc{ n} + 1)


2 occasions ccSucc{ n} + 2 occasions ccNsum{i}{n}{i} = ccSucc{ n} occasions (ccSucc{ n} + 1)


2 occasions ccSucc{ n} + n occasions (n + 1) = ccSucc{ n} occasions (ccSucc{ n} + 1)

ring. Qed.

… or the exhaust of the browser’s native strengthen for vector graphics to render Sport of Life boards encoded as lists of Booleans into diminutive photographs:

Definition glider := [[0;1;0;0;0];
                      [0;0;1;0;0];
                      [1;1;1;0;0];
                      [0;0;0;0;0];
                      [0;0;0;0;0]].
= [[[0; 1; 0; 0; 0]; [0; 0; 1; 0; 0]; [1; 1; 1; 0; 0]; [0; 0; 0; 0; 0]; [0; 0; 0; 0; 0]]; [[0; 0; 0; 0; 0]; [1; 0; 1; 0; 0]; [0; 1; 1; 0; 0]; [0; 1; 0; 0; 0]; [0; 0; 0; 0; 0]]; [[0; 0; 0; 0; 0]; [0; 0; 1; 0; 0]; [1; 0; 1; 0; 0]; [0; 1; 1; 0; 0]; [0; 0; 0; 0; 0]]; [[0; 0; 0; 0; 0]; [0; 1; 0; 0; 0]; [0; 0; 1; 1; 0]; [0; 1; 1; 0; 0]; [0; 0; 0; 0; 0]]; [[0; 0; 0; 0; 0]; [0; 0; 1; 0; 0]; [0; 0; 0; 1; 0]; [0; 1; 1; 1; 0]; [0; 0; 0; 0; 0]]; [[0; 0; 0; 0; 0]; [0; 0; 0; 0; 0]; [0; 1; 0; 1; 0]; [0; 0; 1; 1; 0]; [0; 0; 1; 0; 0]]; [[0; 0; 0; 0; 0]; [0; 0; 0; 0; 0]; [0; 0; 0; 1; 0]; [0; 1; 0; 1; 0]; [0; 0; 1; 1; 0]]; [[0; 0; 0; 0; 0]; [0; 0; 0; 0; 0]; [0; 0; 1; 0; 0]; [0; 0; 0; 1; 1]; [0; 0; 1; 1; 0]]; [[0; 0; 0; 0; 0]; [0; 0; 0; 0; 0]; [0; 0; 0; 1; 0]; [0; 0; 0; 0; 1]; [0; 0; 1; 1; 1]]] : list (list (list bool))

… or the exhaust of a graph library to device visualizations that makes it clearer what happens when one builds a crimson-shaded tree with Coq.MSets.MSetRBT.

Module RBT := MSets.MSetRBT.Form Nat_as_OT.
Definition build_trees (leaves: list nat) :=
  Checklist.fold_left (fun trs n =>
        RBT.add n (hd RBT.empty trs) :: trs)
    leaves [] |> Checklist.rev.

= [{ 'tree': { 'kind':'node'; 'color': 'Black'; 'value': '1'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } }}; { 'tree': { 'kind':'node'; 'color': 'Black'; 'value': '1'; 'left': { 'kind': 'leaf' }; 'right': { 'kind':'node'; 'color': 'Red'; 'value': '2'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } } }}; { 'tree': { 'kind':'node'; 'color': 'Black'; 'value': '2'; 'left': { 'kind':'node'; 'color': 'Black'; 'value': '1'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } }; 'right': { 'kind':'node'; 'color': 'Black'; 'value': '3'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } } }}; { 'tree': { 'kind':'node'; 'color': 'Black'; 'value': '2'; 'left': { 'kind':'node'; 'color': 'Black'; 'value': '1'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } }; 'right': { 'kind':'node'; 'color': 'Black'; 'value': '3'; 'left': { 'kind': 'leaf' }; 'right': { 'kind':'node'; 'color': 'Red'; 'value': '4'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } } } }}; { 'tree': { 'kind':'node'; 'color': 'Black'; 'value': '2'; 'left': { 'kind':'node'; 'color': 'Black'; 'value': '1'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } }; 'right': { 'kind':'node'; 'color': 'Red'; 'value': '4'; 'left': { 'kind':'node'; 'color': 'Black'; 'value': '3'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } }; 'right': { 'kind':'node'; 'color': 'Black'; 'value': '5'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } } } }}] : list RBT.t
= [{ 'tree': { 'kind':'node'; 'color': 'Black'; 'value': '2'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } }}; { 'tree': { 'kind':'node'; 'color': 'Black'; 'value': '2'; 'left': { 'kind':'node'; 'color': 'Red'; 'value': '1'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } }; 'right': { 'kind': 'leaf' } }}; { 'tree': { 'kind':'node'; 'color': 'Black'; 'value': '2'; 'left': { 'kind':'node'; 'color': 'Red'; 'value': '1'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } }; 'right': { 'kind':'node'; 'color': 'Red'; 'value': '4'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } } }}; { 'tree': { 'kind':'node'; 'color': 'Black'; 'value': '3'; 'left': { 'kind':'node'; 'color': 'Black'; 'value': '2'; 'left': { 'kind':'node'; 'color': 'Red'; 'value': '1'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } }; 'right': { 'kind': 'leaf' } }; 'right': { 'kind':'node'; 'color': 'Black'; 'value': '4'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } } }}; { 'tree': { 'kind':'node'; 'color': 'Black'; 'value': '3'; 'left': { 'kind':'node'; 'color': 'Black'; 'value': '2'; 'left': { 'kind':'node'; 'color': 'Red'; 'value': '1'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } }; 'right': { 'kind': 'leaf' } }; 'right': { 'kind':'node'; 'color': 'Black'; 'value': '4'; 'left': { 'kind': 'leaf' }; 'right': { 'kind':'node'; 'color': 'Red'; 'value': '6'; 'left': { 'kind': 'leaf' }; 'right': { 'kind': 'leaf' } } } }}] : list RBT.t

Attain these visualizations if fact be told lend a hand? You be the take: here’s how the crimson-shaded tree example appears to be like with easy-text output:

= [Node Black Leaf 1 Leaf; Node Black Leaf 1 (Node Red Leaf 2 Leaf); Node Black (Node Black Leaf 1 Leaf) 2 (Node Black Leaf 3 Leaf); Node Black (Node Black Leaf 1 Leaf) 2 (Node Black Leaf 3 (Node Red Leaf 4 Leaf)); Node Black (Node Black Leaf 1 Leaf) 2 (Node Red (Node Black Leaf 3 Leaf) 4 (Node Black Leaf 5 Leaf))] : list t
= [Node Black Leaf 2 Leaf; Node Black (Node Red Leaf 1 Leaf) 2 Leaf; Node Black (Node Red Leaf 1 Leaf) 2 (Node Red Leaf 4 Leaf); Node Black (Node Black (Node Red Leaf 1 Leaf) 2 Leaf) 3 (Node Black Leaf 4 Leaf); Node Black (Node Black (Node Red Leaf 1 Leaf) 2 Leaf) 3 (Node Black Leaf 4 (Node Red Leaf 6 Leaf))] : list t

Even whilst you occur to don’t exhaust Alectryon’s literate programming aspects, these webpages have one extra advantage previous helpful browsing: because they anecdote both your code and Coq’s responses, they might be able to operate a everlasting anecdote of your trends resistant to bitrot and valid for archival.

Editing literate Coq paperwork

Moreover producing webpages from standalone Coq info, Alectryon can allow you to jot down documentation, blog posts, and all kinds of diverse paperwork mixing proofs and prose. Alectryon’s literate module implements translations from Coq to reStructuredText and from reStructuredText to Coq, which mean you will seemingly be ready to toggle between two just views of the the same doc: one most productive for editing code, and one most productive for editing reST prose. Concretely, Alectryon knows pointers on how to transform between this:

=============================
 Writing dedication procedures
=============================

Right here is an inductive kind:

.. coq:: 

   Inductive Even : nat -> Prop :=
   | EvenO : Even O
   | EvenS : forall n, Even n -> Even (S (S n)).

.. imprint:: 

   It has two constructors:

   .. coq::  unfold out

      Affirm EvenO.
      Affirm EvenS.

… and this:

(*|
=============================
 Writing dedication procedures
=============================

Right here is an inductive kind: 
|*)

Inductive Even :  nat -> Prop :=
| EvenO :  Even O
| EvenS :  forall n, Even n -> Even (S (S n)).

(*|
.. imprint:: 

   It has two constructors: 
|*)

Affirm EvenO.
Affirm EvenS.

Since the transformations are (if fact be told) inverses of every diverse, you wouldn’t must clutch one of those two kinds and follow it (or worse, to retain two copies of the the same doc, reproduction-pasting snippets ). As a change, you will seemingly be ready to freely swap between the exhaust of your celebrated Coq IDE to jot down code and proofs while editing bits of prose within feedback, and the exhaust of your celebrated reStructuredText editor to jot down prose.

The motive for picking reStructuredText because the markup language for feedback is that it is designed with extensibility in mind, which permits me to trot Alectryon into the customary Docutils and Sphinx compilation pipelines for reStructuredText (Sphinx is what the documentations of Haskell, Agda, Coq, and Python are written in). This is how this blog is written, and in reality you will seemingly be ready to secure the sources whilst you occur to’re unfamiliar to be aware what it appears to be like esteem. This will be how I made my SLE2020 slides (press p to be aware the presenter notes) and the draw in which I wrote my SLE2020 paper.

A diminutive Emacs package deal (alectryon.el), lets you toggle swiftly between Coq and reST. The screenshot beneath demonstrates this characteristic: on the left is the Coq search for of an edited excerpt of Instrument Foundations, in coq-mode; on the fine is the reST search for of the the same excerpt, in a rst-mode buffer. The conversion is transparent, so editing either search for updates the the same .v file on disk. Ask the spotlight indicating a reStructuredText warning on all facets:

Side-by-side comparisons of Coq and reStructuredText views of the same document

Alectryon’s syntax-highlighting is carried out with Pygments, nonetheless it completely uses an update Coq grammar with a database of key phrases and instructions extracted at this time from the reference guide (in the terminate, this section ought to be merged upstream, and the database-technology instrument ought to be merged into the Coq reference guide; I will write a separate blog put up about it someday).

Recording Coq’s output and caching it

Alectryon’s collect is proper-attempting modular, so whilst you occur to clutch to must make exhaust of it for diverse functions it is easy to make exhaust of appropriate some parts of it. In explicit, its core is a straightforward API that takes an inventory of code snippets, feeds them to Coq thru SerAPI, and data dreams and messages. This functionality is exposed on the express line (taking json as enter and producing json as output) and likewise as a Python module:

>>> from alectryon.core import annotate
>>> annotate(["Example xyz (H: False): True. ... *) exact I. Qed.", "Print xyz."])
[[CoqSentence(
     sentence='Example xyz (H: False): True.',
     responses=[],
     goals=[CoqGoal(name='2',
                    conclusion='True',
                    hypotheses=[CoqHypothesis(name='H', body=None, type='False')])]),
  CoqText(string=' ... *) '),
  CoqSentence(sentence='exact I.', responses=[], dreams=[]),
  CoqText(string=' '),
  CoqSentence(sentence='Qed.', responses=[], dreams=[])],

 [CoqSentence(sentence='Print xyz.',
              responses=['xyz = fun _ : False => In     : False -> True'],
          dreams=[])]]

Alectryon uses JSON caches to trip up consecutive runs, nonetheless even when efficiency isn’t if fact be told an space caches present an awfully priceless construct of regression sorting out for embedded Coq snippets. Without such checks, it is easy for reputedly innocuous adjustments in a library to interrupt its documentation in refined methods. To illustrate, which that you can presumably need the next snippet:

The feature plus is printed recursively:

plus = repair plus (n m : nat) {struct n} : nat := match n with | 0 => m | S p => S (plus p m) cease : nat → nat → nat Argument scopes are [nat_scope nat_scope]

When you rename plus to Nat.add and add a compatibility notation, that is what your documentation will silently severely change, with no error or warning to allow you to know that something went atrocious:

Notation plus := Init.Nat.add

This became this kind of frequent space in the reference guide that we applied workarounds to make a decision the most egregious cases (where adjustments resulted in snippets to print errors in build of executing efficiently). However whilst you occur to label in Alectryon’s caches into provide alter, then the next will tell up proper-attempting clearly:

  "contents": "Print plus.",
  "messages": [
    {
      "_type": "message",
-     "contents": "plus = nfix plus (n m : nat) {struct n} : nat := …"
+     "contents": "Notation plus := Nat.add"
    }

All these features are exposed through a command line interface documented in Alectryon’s README. This project has been in development for over a year, but there’s still lots of rough bits, so expect bugs and please report them!

Using Alectryon

Standalone usage

The easiest way to get started Alectryon is to use it very much like coqdoc, but using reStructuredText syntax in special comments delimited with (*| and |*), like in this hypothetical even.v document:

(*|
=======
 Title
=======

Prose. *Emphasis*; strong emphasis; ``code``; `coq code`; `link `__.
|*)

Inductive Even : nat -> Prop :=
| EvenO : Even O
| EvenS : forall n, Even n -> Even (S (S n)).

… which can then be compiled into a static webpage using ../alectryon.py --frontend coq+rst --backend webpage even.v -o even.html.

This is what I did for FRAP and CPDT. For Software foundations and Flocq, I used a compatibility layer combining Alectryon to render the code and coqdoc to render the prose:

find . -name *.v -exec alectryon.py --frontend coqdoc --backend webpage {} ;

Authoring tips

There’s a great reStructuredText primer on Sphinx’s website, if you’re new to this markup language (there’s also an official quick-reference guide, which is as ugly as it is comprehensive). reStructuredText is no panacea, but it’s a decent language with a good story about extensibility, and it’s popular for writing documentation (Haskell, Agda, and Coq use it for their reference manuals).

If you use Emacs, you can install alectryon.el, a small Emacs library that makes it easy to toggle between reStructuredText and Coq:

(add-to-list 'load-path "path/to/alectryon/clone/")
(require 'alectryon)

With this, you’ll get improved rendering of (*| … |*) comment markers, and you’ll be able to toggle between reStructuredText and Coq with a simple press of C-c C-S-a. You probably also want to M-x package-install flycheck and pip3 install --user docutils, though neither of these are hard dependencies.

(Hi, reader! Are you thinking “why isn’t this on MELPA?” Great question! It’s because I haven’t had the time to do it yet. But you can — yes, you! In exchange, I promise I’ll sing your praises every time your name comes up in conversation — I might even refer to you as ‘writer-of-MELPA-recipes extraordinaire’.

Alternatively, if you’re a member of this most distinguished category of people who write more grant proposals than Emacs Lisp programs, you should drop me a line: I’m on the academic job market this year, so we should chat!)

Integrated into a blog or manual

Alectryon is very easy to integrate with platforms and tools that support Sphinx or Docutils, like Pelican, readthedocs, Nikola, etc. (In the long run, I hope to migrate Coq’s reference manual to Alectryon. It currently uses coqrst, a previous iteration of Alectryon that I wrote a few years ago based on coqtop instead of SerAPI).

For this blog, for example, I just added the following snippet to our pelicanconf.py:

import alectryon
import alectryon.docutils
from alectryon.html import ASSETS

# Register the ‘.. coq::’ directive
alectryon.docutils.register()

# Copy Alectryon's stylesheet
alectryon_assets = path.relpath(ASSETS.PATH, PATH)
STATIC_PATHS.append(alectryon_assets)
EXTRA_PATH_METADATA[alectryon_assets] = {'direction':  'static/alectryon/'}

# Reproduction a customized Pygments theme with ethical distinction to theme/pygments
for pth in ("tango_subtle.css", "tango_subtle.min.css"): 
    EXTRA_PATH_METADATA[path.join(alectryon_assets, pth)] = 
          {'direction':  direction.be half of('theme/pygments/', pth)}

Identical steps will be wanted for Sphinx, though the exhaust of alectryon.sphinx.register() as an alternative. I hear that there’s work in progress to integrate with diverse blog platforms.

As a library

The preference of reStructuredText is a microscopic arbitrary, so it is not a no longer easy dependency of Alectryon. It can be barely easy to combine it with diverse enter languages (esteem LaTeX, Markdown, and loads others.) — I appropriate haven’t found the time to enact it. There is even an output mode that takes Coq fragments as enter and produces particular person HTML snippets for every, to originate integration more uncomplicated. Ask Alectryon’s README for more data.

To illustrate, I made a compatibility shim for Coqdoc that uses Alectryon to render Coq code, responses, and dreams, nonetheless calls to coqdoc to render the contents of feedback; search for coqdoc in file cli.py of the distribution to be aware the draw in which it works.

Writing Coq proofs in Coq+reST

In reStructuredText paperwork, code in .. coq:: blocks is completed at compilation time; dreams and responses are recorded and displayed alongside with the code. Right here is an example:

Inductive Even : nat -> Prop :=
| EvenO : Even O
| EvenS : forall n, Even n -> Even (S (S n)).

Fixpoint even (n : nat) : bool :=
  match n with
  | 0 => ethical
  | 1 => faux | S (S n) => even n
  cease.


n : nat, even n = ethical → Even n

IHn: n : nat, even n = ethical → Even n


n : nat, even n = ethical → Even n

IHn: n : nat, even n = ethical → Even n


even 0 = ethical → Even 0

IHn: n : nat, even n = ethical → Even n


ethical = ethical → Even 0

IHn: n : nat, even n = ethical → Even n

H: ethical = ethical


Even 0

IHn: n : nat, even n = ethical → Even n

H: ethical = ethical


Even 0

constructor.

IHn: n : nat, even n = ethical → Even n

H: faux = ethical


Even 1

discriminate.

IHn: n0 : nat, even n0 = ethical → Even n0

n: nat

H: even n = ethical


Even (S (S n))

IHn: n0 : nat, even n0 = ethical → Even n0

n: nat

H: even n = ethical


Even n

auto. Qed.

Interacting with the proof

A diminutive bubble (esteem this: ) next to a Coq fragment means that it produced output: you will seemingly be ready to either waft, click on, or tap on the fragment to order the corresponding dreams and messages.

A definite ‘Inform all dreams and responses’ checkbox is added on the origin of the doc, as shown above; its build is also adjusted by including an explicit .. alectryon-toggle:: directive.

These aspects enact no longer require JavaScript (handiest a most up-to-date CSS implementation). Optionally, a diminutive Javascript library is also passe to enable keyboard navigation, which vastly improves accessibility. You would also try it on this page by urgent Ctrl+↑ or Ctrl+↓.

Right here is one other example of highlighting:


(A : Form) (a : A), Some a = None → Faux


match Some a with | Some _ => Faux | None => Dazzling cease

A: Form

a: A

s:=Some a: option A

H: s = None


match s with | Some _ => Faux | None => Dazzling cease

A: Form

a: A

s: option A

H: s = None


match s with | Some _ => Faux | None => Dazzling cease

A: Form

a: A

s: option A

H: s = None


Dazzling

first [exact I].
(λ (A : Form) (a : A) (H : Some a = None), let s := Some a in eq_ind_r (λ s0 : option A, match s0 with | Some _ => Faux | None => Dazzling cease) I H)
Outlined.
= λ (a : ?A) (H : Some a = None), match match H in (_ = y) return (y = Some a) with | eq_refl => eq_refl cease in (_ = y) return match y with | Some _ => Faux | None => Dazzling cease with | eq_refl => I cease : a : ?A, Some a = None → Faux

Customizing the output

Directive arguments and special feedback is also passe to customize the indicate of Coq blocks. The documentation of Alectryon has details, nonetheless here are just a few examples:

  • Plod half of code silently:

    .. coq::  none
    
       Require Import Coq.Arith.Arith.
    
  • Originate with all intermediate states shown, hide selectively:

    .. coq::  unfold
    
       Procedure Dazzling / Dazzling. (.fold *)
         shatter up.
         - (.fold *)
           idtac "hi there". (.no-dreams *)
           practice I.
         - auto.
       Qed.
    
    
      
      
        
        practice I.
       auto.
    Qed.
  • Inform handiest a message, hiding the enter:

    .. coq:: 
    
       Compute (1 + 1). (.unfold .messages *)
    

    Needless to dispute, whilst you occur to are going to hide the enter nonetheless tell some output (as with .no-enter, .messages, or .dreams), you can must add .unfold, since the same old formula to order the output (clicking on the enter) couldn’t be on hand.

The default alectryon.css stylesheet helps two indicate modes: the proviola vogue (two windows aspect by aspect, with code shown on one aspect and dreams on the diverse), and this blog’s vogue (with dreams shown alongside every fragment when the window is broad ample and beneath the enter line otherwise). Both modes strengthen clicking on an enter line to order the output fine beneath it. You would also clutch a mode by placing the

Some attention-grabbing technical bits

  • The overwhelming majority of the processing time in Alectryon is spent parsing and unparsing s-expressions. I wrote Alectryon’s s-exp parser myself to diminish dependencies and obtained it moderately immediate, nonetheless whilst you occur to’re a Python move geek you ought to undoubtedly have a peek (I surprise if cython would lend a hand here — I’m no longer definite how ethical it is at bytestring manipulation). With any luck this space (and the corresponding code) will evaporate once SerAPI helps JSON.

  • The default HTML backend works with out JavaScript — it uses handiest CSS. It stores its train in checkboxes: every enter line is a imprint for a hidden checkbox, whose train controls the visibility of the output thru conditional CSS principles. The doc-broad toggle works the the same formula, overriding all particular person checkboxes. You would also search for the page with out the types by typing javascript:doc.querySelector("hyperlink[href$="alectryon.css"]").exhaust away() into your handle bar (all responses, dreams, and checkboxes will seemingly be displayed, and you will lose the interactivity, in spite of the entire lot).

  • Block feedback in Coq are barely sophisticated: parsers must song no longer appropriate nested feedback nonetheless also nested strings, an oddity we inherited from OCaml (string delimiters in feedback ought to be successfully matched, and observation markers within them are brushed off). The premise there became to originate commenting more grand, so as that wrapping a legitimate bit of code in … *) would constantly work. To illustrate, the next is ample OCaml code:

    let a = "x *) y" in
    let a = "x *) y" in *) a
    

    … though as which that you can have guessed from the damaged syntax highlighting, no longer many tools handle this successfully — this can also happily shatter Emacs’ tuareg-mode, Pygments, and loads others.

    However the total point is moot in Coq, because *) is a moderately frequent token, and it is not disallowed (unlike in OCaml):

    shatter up; (try reflexivity; intros *).
    

    Single-line feedback solve this space properly. I’ve seen options to make exhaust of [] in OCaml and Coq, nonetheless (1) it is moderately defective to kind, (2) it can possibly well shatter every editor that for the time being helps OCaml, and (3) it would not have pure variants ((* is a typical observation and is a coqdoc one; what would a literate variant of [] be? No longer [_A | not_A], since that is the the same as )

    Aloof, single-line feedback will be nice. A pair of years ago I wrote a predecessor of Alectryon for F*, and the exhaust of /// for literate feedback makes it great more uncomplicated to commence unique reST blocks, when in contrast to barely unwieldy (*| … |*) markers. As a bonus, the parsing/unparsing algorithms are a long way more gleaming (it turns out that (* and *) are proper-attempting frequent token in reST as successfully, (esteem *this*), so Alectryon wants to enact some quoting and unquoting in build of treating all text opaquely).

  • The conversion between Coq and reStructuredText retains song of enter positions and carries them during the interpretation, allowing it to annotate output traces with the enter they came from. I exhaust this when compiling from Coq+reST to HTML, to arrangement reStructuredText error messages reduction to the distinctive Coq sources. Furthermore, whilst you occur to will have Flycheck attach in, the alectryon.el Emacs mode uses that to lint the reStructuredText code embedded in Alectryon feedback.

    It if fact be told took me a while to converge on a ethical collect for this. One among the requirements is that the translator ought to be ready to retain the build of no longer less than one point, since we must always retain the patron’s build in the doc when we swap. With a wealthy string kind that is trivial, nonetheless the string kinds in Python (and OCaml, and most languages if fact be told) are moderately minimal. In Emacs Inform, as an instance, we’d receive a “point” marker, and convert the contents of the buffer from Coq to reST or vice-versa by making insertions and deletions into it, which could possibly well movement the marker round robotically.

    This is in a position to work in Python too, nonetheless it completely will be plenty of code to retain for a single utility (including reimplementing regex matching on high of this unique structure), so as an alternative I passe a more gleaming form of strings annotated with build data handiest (in reality, for efficiency, these strings are appropriate views over the distinctive doc, applied as a string and a pair of offsets). Then I section the distinctive doc into a assortment of those views annotated with their kind (prose or code), carve and cube them further to add or exhaust away indentation, ‘.. coq::’ markers, or observation delimiters, and at closing assemble them into a Frankenstein monster of a doc, restful of fragments from the distinctive doc pieced together by just a few added strings (annoyingly, having to flee observation delimiters throws an further complication, since there’s no easy notion of change for these string views (as an alternative, unescaping ( * to assemble (* requires splitting (* into three parts, losing the center one, and stitching the rest two together).

  • The conversion from reST to Coq tries no longer easy to retain as few .. coq:: directives as seemingly. To illustrate:

    reST

    Coq

    Some text
    
    .. coq:: 
    
       Let a := 1.
    
    .. coq::  unfold
    
       Let b := 1.
    
    .. imprint:: 
    
       More text.
    
    .. coq:: 
    
       Let aa := 1.
    
    Closing text.
    
    .. coq:: 
    
       Let bb := 1.
    
    (*|
    Some text
    |*)
    
    Let a := 1.
    
    (*|
    .. coq:: unfold
    |*)
    
    Let b := 1.
    
    (*|
    .. imprint:: 
    
       More text.
    
    .. coq:: 
    |*)
    
    Let aa := 1.
    
    (*|
    Closing text.
    |*)
    
    Let bb := 1.
    

    Inform how two of the .. coq:: directives had been brushed off from the output, and two had been kept (are you able to guess why?). The behavior is basically a compromise between two constraints: the conversion functions ought to be bijective (modulo whitespace), and their composition ought to be idempotent. The good judgment I applied (though I’m definite I forgot one corner case, or 7), is to exhaust away all .. coq:: markers that is also unambiguously reconstructed from the context. This vogue placing off all markers that (1) enact no longer have personalized flags (therefore the major preserved header) and (2) have an indentation (nesting) level matching the straight previous line (therefore the 2d preserved header, or else when changing reduction Let aa := 1 will be nested beneath the .. imprint:: ).

Future work

There are just a few things that can strengthen the fine of the paperwork produced by Alectryon, nonetheless I collect no longer have instantaneous plans to kind out all of them, largely for lack of time:

  • Including a LaTeX backend. This is largely completed.

  • Engaged on diverse developed visualizations, expectantly culminating in a Coq enhancement proposal to have a standardized formula to enact non-textual notations (you’d attach a feature to a form that claims pointers on how to render it as a graph, or a LaTeX system, or an SVG describe, or any diverse construct of rendering). I in reality have early outcomes on this for separation good judgment; please receive in contact whilst you occur to would clutch to listen to more.

  • Extending the machine to diverse languages, doubtlessly starting up with Lean, F*, easyCrypt, and presumably HOL4? It can be attention-grabbing to be aware how successfully this generalizes.

  • Integrating with jsCoq, to allow users to work on the side of the code at this time in the browser (loads of the output will be precomputed, nonetheless users would also be ready to edit the code and recompute the output). For a mock-up of the journey, search for the associated tools that I constructed for F*.

  • Highlighting differences between consecutive dreams, presumably the exhaust of the strengthen that’s now constructed-in in Coq, though search for this space.

  • Replacing the coqrst instrument passe by the Coq refman with a version per Alectryon, which will seemingly require merging SerAPI into Coq (proper-attempting please?). (This would not mean placing off coqdomain.py or changing the syntax passe in the guide, appropriate changing the backend that’s passe to calculate Coq output). Many of the work is carried out: I constructed a prototype for SLE2020.

    Ideally, we’d exhaust this opportunity to generate no longer appropriate highlighted snippets nonetheless also JSON output, as a gigantic regression check (we’d label in the generated JSON, so adjustments will be indicated by git diff and updating the file would appropriate be a matter of committing it).

  • Porting Coq’s field structure algorithm to JavaScript, or appropriate compiling the present implementation with js_of_ocaml, and the exhaust of that to reflow code and messages when page dimensions trade. I judge CSS is terminate to being ready to strengthen this — I do know pointers on how to enact hov boxes (largely), nonetheless I’m no longer definite whether or no longer hv boxes is also completed (and in any case, it can possibly well seemingly be moderately leisurely). It’s droll that proper-attempting-printing is a total subfield of PL, nonetheless now we have by no draw managed to receive implementers of web browsers enthusiastic.

  • Integrating Alectryon with CI to robotically collect annotated listings for all info in a repository.

Let me know whilst you occur to’re drawn to tackling one of those. I’d clutch to work together or provide pointers / pointers.

Read More

4 Commentaires

Leave a Comment

Recent Posts

Small Issues That Made Amiga Gigantic – Datagubbe.se
Tim Cook: This Is the No. 1 Reason We Accomplish iPhones in China
Naomi Wu’s 3DPrintMill CR-30 Now Live on Kickstarter
A Kid, a Minor Bike Accident and a $19,000 Medical Invoice
Penguin Random House Workers Confront Publisher About New Jordan Peterson E book

Recent Posts

Small Issues That Made Amiga Gigantic – Datagubbe.se
Tim Cook: This Is the No. 1 Reason We Accomplish iPhones in China
Naomi Wu’s 3DPrintMill CR-30 Now Live on Kickstarter
A Kid, a Minor Bike Accident and a $19,000 Medical Invoice
Penguin Random House Workers Confront Publisher About New Jordan Peterson E book
fr_FRFrench
en_USEnglish fr_FRFrench