Skip to content

Instantly share code, notes, and snippets.

@hacklex
hacklex / Sandbox.fst
Last active December 21, 2022 16:13
Sequence partial sums lemma
module Sandbox
open FStar.Seq
open FStar.IntegerIntervals
let rec subseq_from_indices (#n: nat) (s: seq nat {length s == n})
(h: seq (under n))
: Tot (seq nat) (decreases length h) =
if length h = 0 then empty
@hacklex
hacklex / FStar.Algebra.Setoid.fst
Created January 8, 2023 21:04
Non-computational setoids
module FStar.Algebra.Setoid
module TC = FStar.Tactics.Typeclasses
module F = FStar.FunctionalExtensionality
open FStar.Tactics
class equivalence_relation a = {
eq : a -> a -> bool;
@hacklex
hacklex / FStar.Algebra.ProofSandbox.fst
Created January 11, 2023 20:17
Proving fold_right/fold_left equivalence for an arbitrary commutative operation
module FStar.Algebra.ProofSandbox
open FStar.Algebra.Classes.Equatable
open FStar.Algebra.Classes.Grouplikes
open FStar.Algebra.Classes.Ringlikes
module LB = FStar.List.Tot.Base
module TC = FStar.Tactics.Typeclasses
#set-options "--z3rlimit 1 --ifuel 1 --fuel 1"
@hacklex
hacklex / FStar.Seq.Partitions.fst
Last active January 17, 2023 18:03
FStar Seq Partition Theory
module FStar.Seq.Partitions
open FStar.Seq
open FStar.IntegerIntervals
(**
This module contains theory for no-duplicates seqence partitions.
We only work with eqtypes here.
Here we call
@hacklex
hacklex / NodeTestSandbox.fst
Created January 29, 2023 17:03
Node reachability theory
module NodeTestSandbox
open FStar.Seq
open FStar.Seq.Base
open FStar.IntegerIntervals
type address = UInt32.t
type address_list = seq address
@hacklex
hacklex / SequenceFilterProperty.fst
Last active February 5, 2023 13:38
Sequence filter respects Seq.append
module SequenceFilterProperty
open FStar.Seq
let uint = UInt32.t
let pair = uint & uint
let rec snds_having_fst (i: uint) (e: seq pair)
: Tot (seq uint)
@hacklex
hacklex / Sandbox.fst
Created February 10, 2023 17:42
seq-based set lemmas
module Sandbox
#set-options "--ifuel 0 --fuel 0 --z3rlimit 1"
open FStar.Seq
open FStar.Seq.Base
//type vertex_id = UInt32.t
@hacklex
hacklex / Sandbox.fst
Last active February 13, 2023 09:19
Properties hold for inner slices if they do for outer ones
module Sandbox
#set-options "--ifuel 0 --fuel 0 --z3rlimit 1"
open FStar.Seq
open FStar.Seq.Base
open FStar.IntegerIntervals
open FStar.UInt32
module U32 = FStar.UInt32
@hacklex
hacklex / ArrayTest.fst
Created May 18, 2023 16:29
Asserted read/write over F* sequences
module ArrayTest
open FStar.Mul
open FStar.Bytes
open FStar.Endianness
open FStar.Seq
open FStar.IntegerIntervals
let block_size = 1024
@hacklex
hacklex / MemorySandbox.fst
Created July 6, 2023 20:37
F* Memory read/write helpers
module MemorySandbox
open FStar.Mul
open FStar.Bytes
open FStar.Endianness
open FStar.Seq
open FStar.IntegerIntervals
type qword = UInt64.t