Skip to content

Instantly share code, notes, and snippets.

@hacklex
hacklex / FStar.Algebra.Classes.Equatable.fst
Last active May 12, 2022 16:00
Experiments with custom equivalence relation
module FStar.Algebra.Classes.Equatable
module TC = FStar.Tactics.Typeclasses
class equatable (t:Type) = {
eq: t -> t -> bool;
reflexivity : (x:t -> Lemma (eq x x));
symmetry: (x:t -> y:t -> Lemma (requires eq x y)
(ensures eq y x));
transitivity: (x:t -> y:t -> z:t -> Lemma (requires eq x y /\ eq y z)
@hacklex
hacklex / Sandbox.fst
Created June 18, 2022 03:00
Simple key-based search in a seq of key-value pairs
module Sandbox
open FStar.Seq
let under (x: nat) = z:nat{z<x}
let index_for #t (x:seq t) = under (length x)
let rec select_by_key (#key_type: eqtype)
(#value_type: Type)
@hacklex
hacklex / Sandbox.fst
Created August 9, 2022 19:56
Huge verification freeze on this, see the last definition @ line 315
module Sandbox
type binary_op (a:Type) = a -> a -> a
type unary_op (a:Type) = a -> a
type predicate (a:Type) = a -> bool
type binary_relation (a: Type) = a -> a -> bool
[@@"opaque_to_smt"]
let is_reflexive (#a:Type) (r: binary_relation a) = forall (x:a). x `r` x
[@@"opaque_to_smt"]
@hacklex
hacklex / ColorConverter.cs
Created October 12, 2022 10:08
Universal Color Converter for Avalonia
using System;
using System.Globalization;
using Avalonia;
using Avalonia.Data;
using Avalonia.Media;
namespace Avalonia.Data.Converters;
public class ColorConverter : IValueConverter
{
@hacklex
hacklex / PhoneWaveCollection.cs
Created November 2, 2022 06:36
Transaction-aware collection support for PhoneWave
public class PhoneWaveCollectionChangeAggregator<T> : TransactionChange
{
List<(bool isRemove, int index, T item)> _changes = new();
ObservableCollection<T> _target;
public PhoneWaveCollectionChangeAggregator(ObservableCollection<T> target)
{
_target = target;
@hacklex
hacklex / FStarFreeze.fst
Created November 4, 2022 17:17
Performance issue
module FStarFreeze
let unbounded (f: nat -> int) = forall (m: nat). exists (n:nat). abs (f n) > m
assume val f : (z:(nat -> int){unbounded z})
let g : (nat -> int) = fun x -> f (x+1)
let find_above_for_g (m:nat) : Lemma(exists (i:nat). abs(g i) > m) =
assert (unbounded f); // apply forall to m
eliminate exists (n:nat). abs(f n) > m
@hacklex
hacklex / PigeonPrinciple.fst
Created November 7, 2022 20:03
Pigeon Principle for setoids
module PigeonPrinciple
open FStar.IntegerIntervals
open FStar.Seq
type binary_relation (a: Type) = a -> a -> bool
[@@"opaque_to_smt"]
let is_reflexive (#a:Type) (r: binary_relation a) = forall (x:a). x `r` x
@hacklex
hacklex / Sandbox.fst
Created December 2, 2022 12:03
Inductive types, recursion and fuel in F*
module Sandbox
#set-options "--ifuel 0 --fuel 0 --z3rlimit 1"
type unat =
| Z : unat
| S : (prev: unat) -> unat
#set-options "--ifuel 1 --fuel 0"
let rec unat_to_nat (x: unat) : nat =
@hacklex
hacklex / Sandbox.fst
Created December 3, 2022 15:59
Fixed what was broken, or so it seems
module Sandbox
open FStar
open LowStar.Buffer
open LowStar.BufferOps
open FStar.HyperStack.ST
module Buffer = LowStar.Buffer
unfold let test_pre (b r: buffer UInt32.t) (h: FStar.HyperStack.mem): Type0 =
@hacklex
hacklex / Sandbox.fst
Created December 6, 2022 22:01
F* Self-contained setoid test
module Sandbox
// no complications or wasted verification time is permitted below this line.
#set-options "--ifuel 0 --fuel 0 --z3rlimit 1"
type binary_op (a:Type) = a -> a -> a
type unary_op (a:Type) = a -> a
type predicate (a:Type) = a -> bool
type binary_relation (a: Type) = a -> a -> bool