nathanrf · HackerTrans

hace 9 mesesdiscuss

GADTs let you do similar things in the simplest cases, they just don't work as well for complex constraints.

Like, append: Vector n t -> Vector m t -> Vector (n+m) t. With GADTs you need to manually lift (+) to work on the types, and then provide proofs that it's compatible with the value-level.

Then you often need singletons for the cases that are more complex- if I have a set of integers, and an int x, and I want to constrain that the item is in the set and is also even, the GADT approach looks like:

doThing :: Singleton Int x -> Singleton (Set Int) s -> IsInSet x s -> IsEven x -> SomeOutput

Which looks reasonable, until you remember that the Singleton type has to have a representation which is convenient to prove things about, not a representation that is convenient/efficient to operate on, which means your proofs will be annoying or your function itself will hardly resemble a "naive" untyped implementation.

Dependent types fix this because your values are "just" values, so it would be something like

doThing :: (x : int) -> (s : set int) -> so (is_in s x) -> so (even x) -> SomeOutput

Here, x and s are just plain values, not a weird wrapper, and is_in and event are ordinary (and arbitrary) library functions.

nathanrf

hace 9 mesesdiscuss

In the style of the linked post, you'd probably define a generic type (well, one of two generic types):

type ExactlyStatic : (0 t: Type) -> (0 v: t) -> Type

type ExactlyRuntime : (0 t: Type) -> (v: t) -> Type

Then you could have the type (ExactlyStatic Int 9) or the type (ExactlyRuntime Int 9).

The difference is that ExactlyStatic Int 9 doesn't expose the value 9 to the runtime, so it would be fully erased, while (ExactlyRuntime Int 9) does.

This means that the runtime representation of the first would be (), and the second would be Int.

> Also how to handle runtime values? That will require type assertions, just like union types?

The compiler doesn't insert any kind of runtime checks that you aren't writing in your code. The difference is that now when you write e.g. `if condition(x) then ABC else DEF` inside of the two expressions, you can obtain a proof that condition(x) is true/false, and propagate this.

Value representations will typically be algebraic-data-type flavored (so, often a tagged union) but you can use erasure to get more efficient representations if needed.

nathanrf

hace 9 mesesdiscuss

The two commands affect the same account balance, so they don't commute, so these commands conflict. Every EPaxos worker is required to be able to determine whether any two commands are conflicting, in this case it would be something like:

def do_commands_conflict(c1): return len(write(c1) & read(c2)) > 0 or len(write(c2) & read(c1)) > 0 or len(write(c1) & write(c2)) > 0

Whenever an EPaxos node learns about a new command, it compares it to the commands that it already knows about. If it conflicts with any current commands, then it gains a dependency on them (see Figure 3, "received PreAccept"). So the commands race; the first node to learn about both of them is going to determine the dependency order [in some cases, two nodes will disagree on the order that the conflicting commands were received -- this is what the "Slow Path" is for].

The clients don't coordinate this; the EPaxos nodes choose the order. The cluster as a whole guarantees linearity. This just means that there's at least one possible ordering of client requests that would produce the observed behavior; if two clients send requests concurrently, there's no guarantee of who goes first.

(in particular, the committed dependency graph is durable, even though it's arbitrary, so in the event of a failure/restart, all of the nodes will agree on the dependency graph, which means that they'll always apply non-commuting commands in the same order)

nathanrf

hace 10 mesesdiscuss

This is the (pre-print) paper produced from that project - i.e. it is a self-contained, complete description of the work completed so that it can be reviewed, and then cited.

The underlying result has not changed, but the presentation of the details is now complete.

nathanrf

hace 10 mesesdiscuss

It is as simple as: the person who contributed the proofs/implementations chose Rocq.

I did some small proofs in Dafny for a few of the simpler deciders (most of which didn't end up being used).

At the time, I found Dafny's "program extraction" (i.e. transpilation to a "real" programming language) very cumbersome, and produced extremely inefficient code. I think since then, a much improved Rust target has been implemented.

nathanrf

hace 10 mesesdiscuss

Here's a high level overview for a programmer audience (I'm listed as an author but my contributions were fairly minor):

[See specifics of the pipeline in Table 3 of the linked paper]

* There are 181 million ish essentially different Turing Machines with 5 states, first these were enumerated exhaustively

* Then, each machine was run for about 100 million steps. Of the 181 million, about 25% of them halt within this memany step, including the Champion, which ran for 47,176,870 steps before halting.

* This leaves 140 million machines which run for a long time.

So the question is: do those TMs run FOREVER, or have we just not run them long enough?

The goal of the BB challenge project was to answer this question. There is no universal algorithm that works on all TMs, so instead a series of (semi-)deciders were built. Each decider takes a TM, and (based on some proven heuristic) classifies it as either "definitely runs forever" or "maybe halts".

Four deciders ended up being used:

* Loops: run the TM for a while, and if it re-enters a previously-seen configuration, it definitely has to loop forever. Around 90% of machines do this or halt, so covers most.

6.01 million TMs remain.

* NGram CPS: abstractly simulates each TM, tracking a set of binary "n-grams" that are allowed to appear on each side. Computes an over-approximation of reachable states. If none of those abstract states enter the halting transition, then the original machine cannot halt either.

Covers 6.005 million TMs. Around 7000 TMs remain.

* RepWL: Attempts to derive counting rules that describe TM configurations. The NGram model can't "count", so this catches many machines whose patterns depend on parity. Covers 6557 TMs.

There are only a few hundred TMs left.

* FAR: Attempt to describe each TM's state as a regex/FSM.

* WFAR: like FAR but adds weighted edges, which allows some non-regular languages (like matching parentheses) to be described

* Sporadics: around 13 machines had complicated behavior that none of the previous deciders worked for. So hand-written proofs (later translated into Rocq) were written for these machines.

All of the deciders were eventually written in Rocq, which means that they are coupled with a formally-verified proof that they actually work as intended ("if this function returns True, then the corresponding mathematical TM must actually halt").

Hence, all 5-states TMs have been formally classified as halting or non-halting. The longest running halter is therefore the champion- it was already suspected to be the champion, but this proves that there wasn't any longer-running 5-state TM.

nathanrf

el año pasadodiscuss

I'm not involved in this rewrite, but I made some minor contributions a few years ago.

TSC doesn't use many union types, it's mostly OOP-ish down-casting or chains of if-statements.

One reason for this is I think performance; most objects are tagged by bitsets in order to pack more info about the object without needing additional allocations. But TypeScript can't really (ergonomically) represent this in the type system, so that means you don't get any real useful unions.

A lot of the objects are also secretly mutable (for caching/performance) which can make precise union types not very useful, since they can be easily invalidated by those mutations.

nathanrf

hace 2 añosdiscuss

The quoted paragraph is correct as written. E.g. if

f: ∀A, B. A -> B -> A

Then we have poly type π = "∀A, B. A -> B -> A".

The monotype μ = Str -> Int -> Str is a specialization of π, so we are also permitted to judge that f has type μ.

The type specialization operator "looks backwards", where we write sorta "π ≤ μ" because there's a kind of "subtyping" relationship (though most HM type systems don't actually contain subtyping) - anywhere that a term of type μ is used, a term of type π can be used instead because it can be specialized to μ.

I think this is a good complementary article: https://boxbase.org/entries/2018/mar/5/hindley-milner/ (it also links to three more academic sources for more context/detail)

nathanrf

hace 2 añosdiscuss

The paper defines them as programs in a process calculus (which is fairly standard as far as theory for protocols is involved):

  Definition 1 (Asserted protocols) Asserted protocols, or just protocols for short, are
  ranged over by S and are defined as the following syntax rules:
  S ::=
      |p.S                action prefix
      | +{ l_i : Si }_i∈I branching
      | µt.S              fixed-point
      | t                 recursive variable
      | end               end
      | assert(n).S       assert (produce)
      | require(n).S      require
      | consume(n).S      consume

Process calculi are "fundamental" descriptions of computation analogous to lambda calculus but oriented around communication instead of function calls. (As far as paper structure, I find that usually the important "basic" definitions in programming language research papers are usually in Section 2, since Section 1 serves as a high-level overview).

Basically, a protocol consists of a a sequence of sends/received on a particular channel, mixed with some explicit logic and loops/branches until you reach the end. There's some examples in Section 2.1 which are too complicated to reproduce here.

As a general note on reading protocols- for (good, but industry-programmer-unfriendly) technical reasons they're defined and written as "action1.action2.action3.rest_of_program" but mentally you can just rewrite this into

  {
    action1();
    action2();
    action3();
    ... rest_of_program ...
  }

(in particular, making "the rest of the program" part of each statement makes specifying scope much easier and clearer, which is why they don't just use semicolons in the first place)

nathanrf

hace 2 añosdiscuss

Feral != Native. There are no honeybee species native to North America; all honeybees, including the feral ones, are descended from colonies imported from Europe (e.g. the "Western honeybee" apis mellifera).

There are a lot of non-honeybee bee species native to North America though, and they now face competition from feral domesticated honeybees. It's unclear exactly how much impact they have- some research does treat honeybees as a harmful invasive species (similar to many other human-introduced species).

Native bee species have a harder time getting good PR because they don't directly work for us, even though they are important pollinators for some native plants.

nathanrf

hace 2 añosdiscuss

It is a good thing that cppfront lets you do that, then!

Cppfront generates #line pragmas which tell the generated .cpp file which source lines to "blame" for each piece of generated code. This isn't something new and fancy for cppfront, it's a bog-standard pragma that your debugger already understands. So it will work the exact same as your current debugging workflow even if you mix cpp and cpp2 source files.

nathanrf

hace 2 añosdiscuss

Unfortunately, C++ uses ++ and -- for iterators, many of which cannot reasonably implement += or -=. This distinction is baked into the type system to tell whether or not an iterator supports efficient "multiple advance" (e.g. a linked list iterator doesn't have += but a pointer into a contiguous vector does).

There's no way to fix this in a reverse-compatible way for existing code (which is one of the constraints of cpp2- it must work with all existing C++ so that it is possible for existing projects to migrate regardless of size).

nathanrf

hace 3 añosdiscuss

The distortion comes from trying to map R^2 onto the surface of the mesh, since they have different curvature, so they only "match" near the origin.

But the random-walk algorithm doesn't actually need to happen in R^2; I think it should be relatively straightforward to adapt to walk directly on the mesh.

Instead of tracking an "angle", you just need to track the forward tangent vector. And then walk in very small steps using the geodesic walk algorithm, turning the tangent at each point proportional to the derivative and normal at the new location.

It will probably be slower, but it means it will be distortion-free, since you're no longer trying to force flat coordinates onto a non-flat surface.

Dealing with intersection is more complicated, though - I think you could probably just use an octree structure for acceleration (like the spatial tree in 2D). Since the segments can be each placed (almost) exactly on planar triangle faces, you can just project onto one/both of the segments' containing faces to check for intersection.

nathanrf

hace 3 añosdiscuss

`const`-as-comment is specifically limited to pointers and references - `const` on objects definitely does change semantics (it is always UB to attempt to modify a `const` object).

Another good example is string literals (except when initializing a non-const `char[]` variable), which are often allocated in read-only data in the same way, since they are const objects too.

nathanrf

hace 3 añosdiscuss

That is saying exactly the same thing that I said; the qualification of the pointer is irrelevant; you get UB when modifying a const object. In the code snippets above,

   int x; // not a const object, so can be freely modified
   const int y; // is a const object, so cannot be modified

C/C++ pointer provenance doesn't include information about constness, so it doesn't matter "how" you got a mutable pointer to `x`: you're always allowed to modify `x` through that pointer, even if the pointer "came from" a const reference.

The reason for mentioning a "non-const access path" is that the type system forbids you from modifying through a const access path in the first place, so the program would already be rejected if you tried that.

I'm not saying it's a good idea to go around dropping const qualifications; `const_cast` is mostly evil and should be avoided. But at the level of the abstract machine, it's a no-op, even when going from const -> non-const, other than changing the type of the provided pointer.

The benefit of `const` is that if you don't use C-style casts that discard constness, and you don't use `const_cast`, and you don't use `mutable` or other type-unsafe or const-unsafe features, it's not possible to accidentally obtain a non-const pointer to a const object. Thus C++ actually helps you avoid this UB pretty well. But the fact that general conversion from const to non-const is permitted reduces the kinds of optimizations that can be performed.

nathanrf

hace 3 añosdiscuss

In C and C++, `const` on pointers/references is basically just a comment to programmers - it is part of the type, but doesn't "mean" anything to the abstract machine; the rules don't treat const / regular references/pointers differently, they just say that the types only let you mutate through a mutable pointer.

Obviously, good code should treat it as more than just a comment - using `const` correctly clarifies intent and makes it possible to stay sane as a C++ developer, but the abstract machine doesn't care.

In C++, you can basically always `const_cast` a `const T&` into a `T&` and then modify it without causing UB. A function that accepts a `const T&` is just pinky promising that it will be polite and probably not do that.

It is only UB if the underlying object is "actually const", and even then, it doesn't cause UB until you actually perform the mutation; creating the mutable reference itself is perfectly fine.

For example, the following is perfectly legal:

    int& upgrade_to_mut(const int& x) {
      return *const_cast<int*>(&x);
    }

    int x = 5;
    const int& x_ref = x;
    int& x_ref_mut = upgrade_to_mut(x_ref);
    x_ref_mut = 6;

it's only invalid if the object that is pointed at is const, as in:

    int& upgrade_to_mut(const int& x) {
      return *const_cast<int*>(&x);
    }

    const int y = 5;
    const int& y_ref = y;

    int& y_ref_mut = upgrade_to_mut(y_ref); // it is actually legal to produce y_ref_mut, but we cannot modify it


    y_ref_mut = 6; // this is UB: cannot modify a const object 'y'

The difference is that in Rust, "mutation capabilities" are part of references, and so you cannot create them out of nowhere, that would be UB. But in C++, mutation capabilities are part of the object being pointed at, so as long as they happen to be there when you perform the mutation (e.g. you're not modifying a string literal or a variable declared `const`) then there's no problem.

nathanrf

hace 3 añosdiscuss

It is unsound to transmute `&'a T` into `&'static T`, but it is not UB - as long as all of the subsequent uses of the transmuted reference obey the "real" lifetime of the original reference:

    fn example<'a>(r: &'a mut i32) -> &'static mut i32 {
        unsafe { std::mem::transmute(r) }
    }
    
    
    fn main() {
        let mut x: i32 = 5;
        let ptr: &'static mut i32 = example(&mut x);
        *ptr = 6;
        println!("{x}");
    }

(because it's unsound, it's considered wrong to do this - you should not intentionally write functions whose types are lies, and this one definitely lies, so it should be marked `unsafe` - but this is not automatic UB)

https://play.rust-lang.org/?version=stable&mode=debug&editio...

You can run through Miri and confirm there's no UB even though we're modifying `ptr`, whose lifetime has been extended beyond the length of the function.

However, Rust does have extra guarantees here which make this irrelevant to the pessimization problem in the linked article - you cannot ever legally convert a `&T` into a `&mut T` - this is always UB. This means that Rust guarantees that `example` does not modify `x` (unless e.g. it contains an `UnsafeCell`, like a `Mutex`'s contents), and so it does not need to defensively reload its value.

That is to say: Rust, just like C++, makes it legal (but frowned upon) to "leak" a reference beyond the stated lifetime it's provided as. But unlike C++, it is (always!) illegal to "upgrade" a `&T` into a `&mut T`, and thus the fact that it escapes does not hinder other optimizations.

comments