Fil-C on Nix

Filnix wiki

the formal campaign

rocq/backend/Pizlonate.v

# Pizlonation

As pizlonate.pl's pizlonate_module/2: from the unchecked IR to the checked IR, the form the backend compiles. Each access at a p address becomes a check, whose class a result is the proven address, and the raw access that reads it; each pure pointer operation becomes a flight; and every edge to a block at or before its source in block order becomes a poll edge. The table at the head of pizlonate.pl gives each row.

The pass is on terms, as the Prolog one is, and for the same reason: it rewrites a handful of instruction forms and leaves every other term as it is, whatever it is. So a function with an instruction the model has no constructor for is pizlonated like any other, and Transport.v's decode_module then keeps it as its checked term (IOutside), the very term Prolog gives. The unchecked stage needs no inductive of its own.

What pizlonate.pl does besides is left out, because the module the backend compiles has no context items:

pizlonate_module gives None where pizlonate_module/2 fails or throws: an item, block or jump of no known shape, a jump to a label no block has, or two blocks of one function with one label. The gate (tests/pizlonate.sh) holds the result to the term nanofilpizlonate − terms prints.

From Stdlib Require Import String ZArith List Bool
From Nanofil Require Import Term Maps Semantics Validate
From Backend Require Import Text
Import ListNotations
Open Scope string_scope
Open Scope Z_scope

String equality, written as Prolog's ==.

42Notation a == b ≔ String.eqba b (at level 70)

Small terms

Whether the term t is the atom a.

47Definition is_atoma : string t : term : bool ≔
match t with
⇒
a == b
_
⇒
false

Whether the list xs has n terms: the arity of a compound.

51Definition arityn : nat xs : listterm : bool ≔
Nat.eqblengthxs n

The temporary named q, as ir.pl writes it: tmp(Q).

54Definition tmpq : term : term ≔
TApp"tmp" q

The name d when the term t is tmp(D).

57Definition tmp_namet : term : listterm ≔
match t with
TAppf d
⇒
f == "tmp"
→
d
else
[ ]
_
⇒
[ ]

The size and alignment of an access

As narrow_type/3: the bytes of the narrow integer type a.

63Definition narrow_bytesa : string : optionZ ≔
a == "sw" || a == "uw"
→
Some4
a == "sh" || a == "uh"
→
Some2
a == "sb" || a == "ub"
→
Some1
else
None

As cas_type/1 and cas_bytes/2: the bytes a cas of type t compares and swaps.

71Definition cas_bytest : term : optionZ ≔
match t with
⇒
a == "l" || a == "p"
→
Some8
_
⇒
None

As the first answer of access_size_align/3: a load of type x or a store of width x accesses so many bytes at an address that must be so aligned: 8 for a pointer, whose capability is in the aux word of its 8-byte slot, the width for a cas, else 1. No x has two answers.

82Definition size_alignx : term : optionZ × Z ≔
match x with
⇒
a == "p"
→
Some8, 8
a == "x"
→
Some10, 8
a == "b"
→
Some1, 1
a == "h"
→
Some2, 1
a == "w" || a == "s"
→
Some4, 1
a == "l" || a == "d"
→
Some8, 1
else
option_mapλn ⇒ n, 1 narrow_bytesa
TAppf t
⇒
f == "cas"
→
option_mapλn ⇒ n, n cas_bytest
else
None
_
⇒
None

An access and its check

A list of memory effects, as pointer_memory_effects/2 writes it.

100Definition effectses : liststring : term ≔

pointer_memory_effects(load, Es).

103Definition load_effects: term ≔
effects"aux_read"; "lower_resolve"; "address_read"

pointer_memory_effects(store, Es).

106Definition store_effects: term ≔
effects"aux_ensure"; "lower_barrier"; "rooted_reload"; "lower_write"; "address_write"

pointer_memory_effects(local_load, Es).

110Definition local_load_effects: term ≔
effects"aux_read"; "address_read"

pointer_memory_effects(local_store, Es).

113Definition local_store_effects: term ≔
effects"lower_write"; "address_write"

let(tmp(Q), a, check(0, Size, Rights, Align), [A]): the check of an access of size bytes at the address a, whose proof is q.

118Definition check_instq size rights align a : term : term ≔
TApp"let" tmpq; TAtom"a"; TApp"check" TInt0; size; rights; align; TLista

check_inst for a size and alignment that size_align gave.

122Definition check_sizedq : term size : Z rights : string align : Z a : term : term ≔
check_instq TIntsize TAtomrights TIntalign a

let(tmp(Q), a, check_local(X, Off, Size, Rights, Align), []): the check of an access to the local x at the offset off.

127Definition check_local_instq x off : term size : Z rights : string align : Z : term ≔
TApp"let" tmpq; TAtom"a"; TApp"check_local" x; off; TIntsize; TAtomrights; TIntalign; TList[ ]

let(D, p, raw_load_pointer(0, Es), [tmp(Q)]).

132Definition raw_load_pointerd q es : term : term ≔
TApp"let" d; TAtom"p"; TApp"raw_load_pointer" TInt0; es; TListtmpq

raw_store_pointer(0, V, tmp(Q), Es).

136Definition raw_store_pointerv q es : term : term ≔
TApp"raw_store_pointer" TInt0; v; tmpq; es

let(D, K, raw_load(T, 0), [tmp(Q)]).

140Definition raw_loadd k t q : term : term ≔
TApp"let" d; k; TApp"raw_load" t; TInt0; TListtmpq

raw_store(W, 0, V, tmp(Q)).

144Definition raw_storew v q : term : term ≔
TApp"raw_store" w; TInt0; v; tmpq

As checked_access/4, a clause for each row of pizlonate.pl's table: when the instruction i is an access, its check, defining tmp(Q), and its raw access, for the fresh name q it is given. None for an instruction that is not an access.

150Definition checked_accessi : term : optionterm → listterm ≔
match i with
TAppf xs
⇒
f == "let"
→
match xs with
d; k; TAppo t; TListargs
⇒
let pointer ≔ is_atom"p" k && is_atom"p" t in
o == "load"
→
match args with
a
⇒
pointer
→
Someλq ⇒ check_sizedq 8 "read" 8 a; raw_load_pointerd q load_effects
else
match size_alignt with
Somesize, align
⇒
Someλq ⇒ check_sizedq size "read" align a; raw_loadd k t q
None
⇒
None
_
⇒
None
o == "atomic_load"
→
match args with
a
⇒
pointer
→
Someλq ⇒ check_sizedq 8 "read" 8 a; raw_load_pointerd q effects"atomic_read"
else
None
_
⇒
None
o == "cas"
→
match args with
e; n; a
⇒
match cas_bytest with
Somesize
⇒
Someλq ⇒ check_sizedq size "write" size a; TApp"let" d; k; TApp"raw_cas" t; TInt0; TListtmpq; e; n
None
⇒
None
_
⇒
None
else
None
_
⇒
None
f == "store"
→
match xs with
w; v; a
⇒
is_atom"p" w
→
Someλq ⇒ check_sizedq 8 "write" 8 a; raw_store_pointerv q store_effects
else
match size_alignw with
Somesize, align
⇒
Someλq ⇒ check_sizedq size "write" align a; raw_storew v q
None
⇒
None
_
⇒
None
f == "atomic_store"
→
match xs with
w; v; a
⇒
is_atom"p" w
→
Someλq ⇒ check_sizedq 8 "write" 8 a; raw_store_pointerv q effects"atomic_write"
else
None
_
⇒
None
f == "access"
→
match xs with
k; a; size; align
⇒
Someλq ⇒ check_instq size k align a; TApp"touch" tmpq
_
⇒
None
f == "call"
→
match xs with
res; TAppg p; args
⇒
g == "tmp"
→
Someλq ⇒ TApp"let" tmpq; TAtom"f"; TAtom"check_function"; TListtmpp; TApp"raw_call" res; tmpq; args
else
None
_
⇒
None
f == "local_load"
→
match xs with
d; k; t; x; off
⇒
match size_alignt with
Somesize, align
⇒
Someλq ⇒ check_local_instq x off size "read" align; if is_atom"p" t then raw_load_pointerd q local_load_effects else raw_loadd k t q
None
⇒
None
_
⇒
None
f == "local_store"
→
match xs with
w; v; x; off
⇒
match size_alignw with
Somesize, align
⇒
Someλq ⇒ check_local_instq x off size "write" align; if is_atom"p" w then raw_store_pointerv q local_store_effects else raw_storew v q
None
⇒
None
_
⇒
None
else
None
_
⇒
None

Flights

As flight_inst/2: the flight of the pure pointer operation i, which is add or sub of an offset, a copy of a temporary or a constant, or itop, which has no lower. A copy of a symbol calls its getter and stays as it is.

264Definition flight_insti : term : optionterm ≔
match i with
TAppf d; k; TAtomo; TListargs
⇒
f == "let" && is_atom"p" k
→
let flight o args lower ≔ TApp"flight" d; TAtomo; TListargs; lower in
let of_pointer o p rest ≔ flighto TApp"address" p :: rest TApp"lower" p in
o == "add" || o == "sub"
→
match args with
p; x
⇒
Someof_pointero p x
_
⇒
None
o == "copy"
→
match args with
TAppg _ as v
⇒
g == "tmp" || g == "const"
→
Someof_pointero v [ ]
else
None
_
⇒
None
o == "itop"
→
match args with
x
⇒
Someflight"copy" x TAtom"none"
_
⇒
None
else
None
else
None
_
⇒
None

Fresh names

The name d when the term r is result(tmp(D), K).

289Definition result_defr : term : listterm ≔
match r with
TAppf t; _
⇒
f == "result"
→
else
[ ]
_
⇒
[ ]

As cfg.pl's inst_def/2: the names of the temporaries the instruction i defines; a call can define several.

294Fixpoint inst_defsi : term : listterm ≔
match i with
TAppf xs
⇒
f == "let" || f == "flight"
→
match xs with
d; _; _; _
⇒
_
⇒
[ ]
f == "local_load"
→
match xs with
d; _; _; _; _
⇒
_
⇒
[ ]
f == "call" || f == "raw_call"
→
match xs with
r; _; _
⇒
match r with
⇒
g == "tuple"
→
flat_mapresult_def rs
else
[ ]
_
⇒
[ ]
f == "uses"
→
match xs with
j; _
⇒
_
⇒
[ ]
f == "asm_fixed"
→
match xs with
_; _; TListouts
⇒
flat_map
λ o  ⇒
match o with
TAppm _; t
⇒
m == "-"
→
else
[ ]
_
⇒
[ ]
outs
_
⇒
[ ]
else
[ ]
_
⇒
[ ]

The text of the name n when it could be a proof's name: an atom that begins chk.

327Definition chk_namen : term : liststring ≔
match n with
⇒
prefix"chk" a
→
a
else
[ ]
_
⇒
[ ]

As func_temp_names/3, kept to the names a fresh one could be: of the temporaries that the function with the parameters params and the blocks defines, as a parameter, a phi or an instruction's result, those whose name begins chk.

334Definition defined_chksparams : term blocks : listterm : liststring ≔
let chks ns ≔ flat_mapchk_name ns in
let param p ≔
match p with
TAppg _; t
⇒
g == "param"
→
else
[ ]
_
⇒
[ ]
in
let phi p ≔
match p with
TAppg d; _; _
⇒
g == "phi"
→
else
[ ]
_
⇒
[ ]
in
let listed g : term → liststring t : term ≔
match t with
⇒
flat_mapg ts
_
⇒
[ ]
in
applistedparam params
flat_map
λ b  ⇒
match b with
TAppg _; phis; insts; _
⇒
g == "block"
→
applistedphi phis listedλi ⇒ chksinst_defsi insts
else
[ ]
_
⇒
[ ]
blocks

As fresh_name/4: the name chkI for the least I from n on that is not among names, and I + 1. Each name passed over is another of names, so a fuel of their number is enough: when it is spent, every one of them has been passed over.

356Fixpoint freshfuel : nat names : liststring n : Z : string × Z ≔
let q ≔ String.append"chk" decimaln in
match fuel with
O
⇒
q, n + 1
Sfuel′
⇒
existsbString.eqbq names
→
freshfuel′ names n + 1
else
q, n + 1

Instructions

Whether the instruction i is a loc(File, Line) marker.

366Definition is_loci : term : bool ≔
match i with
TAppf _; _
⇒
f == "loc"
_
⇒
false

A step of checked_insts/11, in filc mode: the count of fresh names and the instructions so far, last first, with the instruction i after them: an access as its check and raw access (checked_access), a pure pointer operation as its flight (flight_inst), and any other as it is.

374Definition inst_stepnames : liststring fuel : nat st : Z × listterm i : term : Z × listterm ≔
let 'n, out ≔ st in
match checked_accessi with
Someaccess
⇒
let 'q, n′ ≔ freshfuel names n in
n′, rev_appendaccessTAtomq out
None
⇒
n
match flight_insti with
Somej
⇒
j
None
⇒
i
::
out

Jumps

As polled_target/4: the target l of a jump from the block at the index from: poll(L) when the block l is at or before it in block order (index), and l as it is when it is later, or is a poll edge already. None for a label no block has.

390Definition polled_targetindex : nmapZ from : Z l : term : optionterm ≔
let plain ≔
match nm_findl index with
Someto
⇒
Some
to ≤? from
→
TApp"poll" l
else
l
None
⇒
None
in
match l with
TAppf _
⇒
f == "poll"
→
Somel
else
plain
_
⇒
plain

As polled_jump/4: the jump j that ends the block at the index from, with a poll edge for each target at or before it, so that every cycle of the function polls.

404Definition polled_jumpindex : nmapZ from : Z j : term : optionterm ≔
match j with
TAppf xs
⇒
f == "goto"
→
match xs with
l
⇒
option_mapλt ⇒ TApp"goto" t polled_targetindex from l
_
⇒
None
f == "branch"
→
match xs with
v; l1; l2
⇒
match polled_targetindex from l1, polled_targetindex from l2 with
Somet1, Somet2
⇒
SomeTApp"branch" v; t1; t2
_, _
⇒
None
_
⇒
None
f == "ret" || f == "rets"
→
match xs with
_
⇒
Somej
_
⇒
None
else
None
⇒
a == "ret" || a == "unreachable"
→
Somej
else
None
_
⇒
None

Functions

Each block's label with its place in block order, from i on, added to m. None when a term is not a block or two blocks have one label, where list_to_assoc/2 throws.

433Fixpoint label_indexi : Z bs : listterm m : nmapZ : optionnmapZ ≔
match bs with
[ ]
⇒
Somem
TAppf l; _; _; _ :: rest
⇒
f == "block" && negbnm_meml m
→
label_indexi + 1 rest nm_addl i m
else
None
_ :: _
⇒
None

As pizlonated_blocks/7: the blocks bs, the first at the index i in block order, their loc markers dropped when drop is set, their instructions by inst_step in filc mode and their jumps by polled_jump. n counts the fresh names, across the blocks.

447Fixpoint pizlonated_blocksfilc drop : bool names : liststring fuel : nat index : nmapZ i n : Z bs : listterm : optionlistterm ≔
match bs with
[ ]
⇒
Some[ ]
TAppf l; phis; TListinsts; j :: rest
⇒
f == "block"
→
let insts ≔
drop
→
filterλx ⇒ negbis_locx insts
else
insts
in
let 'n′, insts′ ≔
filc
→
let 'n′, out ≔ fold_leftinst_stepnames fuel insts n, [ ] in
n′, rev'out
else
n, insts
in
match polled_jumpindex i j with
Somej′
⇒
match pizlonated_blocksfilc drop names fuel index i + 1 n′ rest with
Somerest′
⇒
SomeTApp"block" l; phis; TListinsts′; j′ :: rest′
None
⇒
None
None
⇒
None
else
None
_ :: _
⇒
None

As pizlonated_item/4 for the function func(Name, Linkage, Ret, Params, Blocks).

472Definition pizlonated_funcfilc drop : bool name lk ret params blocks : term : optionterm ≔
match blocks with
⇒
let names ≔ defined_chksparams bs in
match label_index0 bs nm_empty with
Someindex
⇒
option_mapλbs′ ⇒ TApp"func" name; lk; ret; params; TListbs′ pizlonated_blocksfilc drop names lengthnames index 0 0 bs
None
⇒
None
_
⇒
None

The mode and the stage of a module

As ir.pl's pointer_inst/1: the instruction i makes, stores, passes or calls through a p value, or converts one.

489Definition pointer_insti : term : bool ≔
match i with
TAppf xs
⇒
f == "let"
→
match xs with
_; k; o; _
⇒
is_atom"p" k || is_atom"x" k || is_atom"a" k || is_atom"f" k
||
match o with
⇒
a == "ptoi"
TAppg ys
⇒
g == "setjmp" && arity1 ys || g == "raw_load_pointer" && arity2 ys
_
⇒
false
_
⇒
false
f == "store"
→
match xs with
w; _; _
⇒
is_atom"x" w || is_atom"p" w
_
⇒
false
f == "call"
→
match xs with
r; callee; args
⇒
match r with
TAppg _; k
⇒
g == "result" && is_atom"p" k
TAppg _
⇒
g == "tuple"
_
⇒
false
||
match args with
⇒
existsb
λ a  ⇒
match a with
TAppg k; _
⇒
g == "arg" && is_atom"p" k
_
⇒
false
ts
_
⇒
false
||
match callee with
TAppg _
⇒
g == "tmp"
_
⇒
false
_
⇒
false
f == "atomic_store" || f == "raw_call"
→
arity3 xs
f == "raw_store" || f == "raw_store_pointer" || f == "flight" || f == "local_store"
→
arity4 xs
f == "local_alloc"
→
arity2 xs
f == "local_load"
→
arity5 xs
else
false
_
⇒
false

The blocks of the item it when it is a function.

534Definition func_blocksit : term : listterm ≔
match it with
TAppf _; _; _; _; TListbs
⇒
f == "func"
→
bs
else
[ ]
_
⇒
[ ]

The instructions and the jump of the term b when it is a block.

542Definition block_partsb : term : optionterm × listterm × term ≔
match b with
TAppf _; phis; TListinsts; j
⇒
f == "block"
→
Somephis, insts, j
else
None
_
⇒
None

As ir.pl's pointer_item/1: the item it has class p somewhere, or is an alias, a weak function, or read-only, weak, external or thread-local data, which only filc mode models.

552Definition pointer_itemit : term : bool ≔
match it with
TAppf xs
⇒
f == "func"
→
match xs with
_; lk; r; ps; _
⇒
is_atom"weak" lk || is_atom"p" r
||
match r with
TAppg _
⇒
g == "tuple"
_
⇒
false
||
match ps with
⇒
existsb
λ p  ⇒
match p with
TAppg k; _
⇒
g == "param" && is_atom"p" k
_
⇒
false
ps
_
⇒
false
||
existsb
λ b  ⇒
match block_partsb with
Somephis, insts, _
⇒
match phis with
TListphis
⇒
existsb
λ p  ⇒
match p with
TAppg _; k; _
⇒
g == "phi" && is_atom"p" k
_
⇒
false
phis
_
⇒
false
||
existsbpointer_inst insts
None
⇒
false
_
⇒
false
f == "alias"
→
arity3 xs
f == "data"
→
match xs with
_; lk; _; items
⇒
match lk with
TAppg _
⇒
g == "ro" || g == "tls" || g == "extern"
⇒
a == "weak"
_
⇒
false
||
match items with
⇒
existsb
λ i  ⇒
match i with
TAppg k; _
⇒
g == "item" && is_atom"p" k
_
⇒
false
ts
_
⇒
false
_
⇒
false
else
false
_
⇒
false

As ir.pl's module_mode/2: the module of the items is in filc mode when an item is a pointer_item, or a function calls a symbol that no function of the module defines. A plain module's addresses are not Fil-C pointers.

610Definition module_filcitems : listterm : bool ≔
existsbpointer_item items
||
let funcs ≔
fold_left
λ m it  ⇒
match it with
TAppf n; _; _; _; _
⇒
f == "func"
→
nm_addn tt m
else
m
_
⇒
m
items
in
existsb
λ it  ⇒
existsb
λ b  ⇒
match block_partsb with
Some_, insts, _
⇒
existsb
λ i  ⇒
match i with
TApph _; TAppg callee; _
⇒
h == "call" && g == "global" && negbnm_memcallee funcs
_
⇒
false
insts
None
⇒
false
items

As ir.pl's module_stage/2, on terms: the module of the items is in the checked stage when a function uses a word of it.

632Definition module_checkeditems : listterm : bool ≔
existsb
λ it  ⇒
existsb
λ b  ⇒
match block_partsb with
Some_, insts, j
⇒
None
⇒
false
items

Modules

Whether the item it is a context(Name, Records).

643Definition is_contextit : term : bool ≔
match it with
TAppf _; _
⇒
f == "context"
_
⇒
false

As pizlonated_item/4: a function by pizlonated_func, data and an alias as they are.

648Definition pizlonated_itemfilc drop : bool it : term : optionterm ≔
match it with
TAppf xs
⇒
f == "func"
→
match xs with
name; lk; ret; params; blocks
⇒
pizlonated_funcfilc drop name lk ret params blocks
_
⇒
None
f == "data"
→
arity4 xs
→
Someit
else
None
f == "alias"
→
arity3 xs
→
Someit
else
None
else
None
_
⇒
None

As pizlonate_module/2, without the context items: the module m with every check explicit and a poll on every edge to a block at or before its source. In a plain module only the polls are added. The loc markers of an unchecked module are dropped, as legacy_context/2 drops them; a checked module keeps its own.

668Definition pizlonate_modulem : term : optionterm ≔
match m with
TAppf TListitems
⇒
f == "module"
→
let filc ≔ module_filcitems in
let drop ≔ negbmodule_checkeditems in
option_mapλits ⇒ TApp"module" TListits map_optionpizlonated_itemfilc drop filterλit ⇒ negbis_contextit items
else
None
_
⇒
None

Examples

A load: a read check of the type's size, then the raw load of the proven address.

685Example load_word: option_mapλk ⇒ kTAtom"chk0" checked_accessTApp"let" tmpTAtom"d"; TAtom"w"; TApp"load" TAtom"sw"; TListtmpTAtom"p" = Somecheck_sizedTAtom"chk0" 4 "read" 1 tmpTAtom"p"; TApp"let" tmpTAtom"d"; TAtom"w"; TApp"raw_load" TAtom"sw"; TInt0; TListtmpTAtom"chk0"
Proof 1 step Qed
reflexivity

A pointer store: a write check of 8 bytes at an 8-aligned address, then the raw store with the store's effects.

696Example store_pointer: option_mapλk ⇒ kTAtom"chk0" checked_accessTApp"store" TAtom"p"; tmpTAtom"v"; tmpTAtom"a" = Somecheck_sizedTAtom"chk0" 8 "write" 8 tmpTAtom"a"; TApp"raw_store_pointer" TInt0; tmpTAtom"v"; tmpTAtom"chk0"; store_effects
Proof 1 step Qed
reflexivity

A pointer's offset is a flight of its address and its lower.

704Example add_flight: flight_instTApp"let" tmpTAtom"q"; TAtom"p"; TAtom"add"; TListtmpTAtom"p"; TApp"const" TInt8 = SomeTApp"flight" tmpTAtom"q"; TAtom"add"; TListTApp"address" tmpTAtom"p"; TApp"const" TInt8; TApp"lower" tmpTAtom"p"
Proof 1 step Qed
reflexivity

A fresh name passes over the names the function defines.

713Example fresh_passes_over: fresh2 "chk1"; "chk0" 0 = "chk2", 3
Proof 1 step Qed
reflexivity

A loop: the back edge polls, the forward edge does not, and the load in a module with a pointer gets its check.

718Example loop_module: pizlonate_moduleTApp"module" TListTApp"func" TAtom"f"; TAtom"export"; TAtom"w"; TListTApp"param" TAtom"p"; tmpTAtom"a"; TListTApp"block" TAtom"top"; TList[ ]; TListTApp"let" tmpTAtom"x"; TAtom"w"; TApp"load" TAtom"w"; TListtmpTAtom"a"; TApp"branch" tmpTAtom"x"; TAtom"top"; TAtom"out"; TApp"block" TAtom"out"; TList[ ]; TList[ ]; TApp"ret" tmpTAtom"x" = SomeTApp"module" TListTApp"func" TAtom"f"; TAtom"export"; TAtom"w"; TListTApp"param" TAtom"p"; tmpTAtom"a"; TListTApp"block" TAtom"top"; TList[ ]; TListcheck_sizedTAtom"chk0" 4 "read" 1 tmpTAtom"a"; TApp"let" tmpTAtom"x"; TAtom"w"; TApp"raw_load" TAtom"w"; TInt0; TListtmpTAtom"chk0"; TApp"branch" tmpTAtom"x"; TApp"poll" TAtom"top"; TAtom"out"; TApp"block" TAtom"out"; TList[ ]; TList[ ]; TApp"ret" tmpTAtom"x"
Proof 1 step Qed
reflexivity