*sighs*
it is already frustrating enough that most of you can't understand my posts, but not being able to distinguish them from some retarded SF CEO who is borderline technically illiterate and thought they'd proven quantum physics or some shit is another level of stupid
for what's worth, Bend3's consistency proof is simple enough to fit a tweet and and I'm enough to explain it in the most dumbed way possible. problem is that kind of technical posts just flop, which is why I have to resort to these "AI amazing!!" and "AI bad!!" posts to cater to the audience
anyway, below I'll describe, in full extent, how Fable helped me on Bend's consistency proof, why it is incredible and, yes, absolutely valid
first: consistency is basically a word that means: "can we trust this language to formalize mathematics?". or, equivalently, can someone prove a false statement in it? imagine if someone found a proof of 2+2 = 5 in Lean. that person would be able to use this falsehood to perform arbitrary type-level rewrites, and, thus, prove any theorem (even riemann hypothesis!) in a few lines of code. that wouldn't let them $1 million, but would make for a legendary issue on Lean's GitHub, immediately invalidating any proof checked by Lean. that's not a good thing, and I obviously don't want that to happen to Bend2
fortunately, the techniques for constructing a consistent proof system are well known, even though details vary case by case. it usually involves two main parts: first, prove it is sound (i.e., that evaluating an expression can't change this type). honestly, that's just the "show us your implementation is not hopelessly buggy". it is the easy part.
the second part is much more difficult:
"prove every well typed program in your language terminates"
this is necessary because infinite loops allow one to encode "paradoxes" (like "this sentence is false") and, to explain it in a very silly way, these paradoxes "confuse" the type checker, and allow you to prove falsehoods. so, if I want people to trust Bend as a proof language, I must be able to convince them there's no way to express an infinite loop in it. programs like "while (true)" must be, somehow, banned by our compiler. but how?
the way most proof assistants (like Lean) do it is to 1. not have loops to begin with, 2. ban any kind of non-structural recursion. that means that, to call a function recursively, you must ensure that arguments are getting smaller. that's fairly standard, and fairly easy to do.
so, is that it?
unfortunately, that's not enough, because, in functional languages, there's another way for infinite loops to manifest: self-replicating λ-terms. for example, consider the following Python program:
evil = (lambda f: f(f))(lambda f: f(f)) print evil
it hangs forever, even though it has no loops and no recursion. turns out it is very easy to accidentally let some variation of "evil" to creep in, and "evil" allows one to prove falsehoods. for example, the type of types is Type, you can summon evil via Girard's paradox. and if you allow recursive datatypes to store functions, then, you can summon evil via Curry's paradox:
data Evil { bad(f : Evil -> Evil) } // this would break Lean!
that problem is not exclusive to proof languages. a similar paradox once caused a crisis in mathematics itself! in 1901, Russel proposed a legendary proof of a false statement in naive set theory, which was THE foundation of mathematics back then. the news was that math itself was broken, and every proof ever written by humanity would to be untrusted. crazy times! of course, this has since been "patched". today, we call it "naive" set theory for a reason! but this shows how hard it is to design a consistent proof system. humanity failed to do so for millenniums!
in Rocq, Lean and Agda, the way they avoid these self-replicating λ's is via a series of "patches" - i.e., human engineered antibodies to kill the paradoxes we found in the past. for example, the 'Evil' datatype above is syntactically forbidden by disabling certain shapes of recursive datatypes ("positivity checker"), and Girard's paradox is avoided by having an infinite universe of types ("universe hierarchy"). this disables the "does the set of all sets contain itself" paradox, which, in turn, disables the `evil = λf.f(f) λf.f(f)` summoned by it.
this is all solid and stablished, and people are very confident Lean and others are trustworthy. that said - and that's where I tend to change things - I argue that's overkill. while these restrictions indeed avoid paradoxes, they're also very strict, and ban perfectly valid programs. for example, it is impossible to write a fast interpreter (i.e., via HOAS) in these, and alternatives (like PHOAS) are very contrived. this makes these languages substantially less practical. Bend aims to be a proof language that is also viable as a real world programming language, so, it is of my interest to find more permissive termination argument. and that's what I was working on, with the help of Fable
my argument goes like this: first, only allow recursion when arguments decrease. so far, this is the same approach used by Lean and others, nothing new here. now, we must find a way to avoid self-replicating λ-terms (like `λf.f(f) λf.f(f)`) from creeping in. that's where we detour. instead of positivity checker and universe hierarchies, I simply re-use a feature of Quantitative Type Theory (QTT) - which, in short, is an industry standard way to have O(1) arrays in an FP lang, and which Bend *already implements* - to forbid non-linear lambdas. In other words, in Bend, lambdas must be used linearly, and, thus, cannot be cloned, and that's enforced by the already existing QTT system.
this simple addition is sufficient to prevent all incarnations of `evil = λf.f(f) λf.f(f)` in one strike, cutting the evil in the bud, and ensuring Bend is terminating, as it easily exhausts every known way to introduce non-termination:
- infinite loops → there are no loops
- infinite recursion → only allow decreasing recursion
- self-duplicating λ-terms → lambdas can't be cloned
from termination, consistency follows easily.
and that's it. this is *obviously* correct and so easy I'm sure even you're confident you can't write infinite loops in Bend. aren't you?
now, I must be very clear here. these are all *my* design choices. I didn't ask an AI "pls build a consistent proof language". I studied the subject 10 fucking years and used AI to aid me materialize my ideas. this is the antidote I found to AI psychosis. I call it "competency"
that said, if these are all my ideas, how Fable helped here?
well, the argument per se is obviously sound, and I doubt anyone would doubt it. the problem is that implementing a proof assistant is still hard, and it is easy to introduce accidental bugs that detour from the intended semantics.
turns out the way that Bend2 wasn't faithful to my intention, for a reason that is legitimately hard to see, and that Fable identified never the less.
QTT, as described in the original paper, allowed "relaxing" its checks a bit on certain places of the code. this is important for usability, and harmless to proof languages that use QTT (like Idris2), because they don't rely on QTT for termination. but Bend2 does, and these relaxed checks allowed lambdas to be cloned in some circumstances. Fable read my termination argument, studied the QTT paper, audited the implementation, and found that inconsistency, handing me a proof of Falsehood!
if you can't see how incredible this is... I'm sorry for you
as for the solution, Fable proposed a few. all bad. my fix was to split Type in two sorts: one for arbitrary types, and other for lower order values. this lets me have the relaxed checks on positions where lambdas cannot occur, while still ensuring lambdas cannot be cloned and, therefore, self replicate. this is the "elegant proof" I mentioned in the post below!
so, yes, I'm quite sure I'm not falling to AI psychosis, but if you or anyone has a counterpoint, please let me know 🫠
@VictorTaelin You sure youre not falling into ai psychosis?








