Bend creator Victor Taelin says the formal consistency proof for Bend3 fits within a single tweet

*sighs*

it is already depressing enough that most of you can't understand my posts, but not being able to distinguish them from some technically illiterate SF CEO who thinks they'd proven quantum physics or some shit is another level of stupid

problem is, when I write too technically, it tends to just flop, which is why I have to resort to these "AI good!" and "AI bad!" posts that, I admit, may sound a bit over-excited sometimes. that said, the proof is simple enough to be explainable in a way you all can appreciate, so, I'll give it a shot. with you, in its full glory, how Fable contributed to Bend's consistency proof, why it was incredible and, yes, very 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 (like riemann's hypothesis!) trivially, in a few lines of code. that wouldn't net them $1 million, but it would make for a legendary issue on Lean's GitHub, immediately invalidating any proof checked by Lean and undermining the language's credibility. 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, if the set of all sets contains itself, 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" and then got flattered into thinking I'm a genius. I studied the subject 10 fucking years and used AI to aid me materialize and double check my ideas. this is the antidote I found to AI psychosis. I call it "competency"

that said, if the solutions are mine, how Fable helped here?

well, the argument per se is obviously sound, and nobody serious would contest it. the problem is that implementing a proof assistant is 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! full proof below ↓

that was Fable's contribution, and, if you can't see how incredible this is, I don't know what could possibly impress 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!

*sighs*

it is already depressing enough that most of you can't understand my posts, but not being able to distinguish them from some technically illiterate SF CEO who thinks they'd proven quantum physics or some shit is another level of stupid

problem is, when I write too technically, it tends to just flop, which is why I have to resort to these "AI good!" and "AI bad!" posts that, I admit, may sound a bit over-excited sometimes. that said, the proof is simple enough to be explainable in a way you all can appreciate, and I like talking about it, so, I'll give it a shot. with you, in its full glory, how Fable contributed to Bend's consistency proof, why it was incredible and, yes, very 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 (like riemann's hypothesis!) trivially, in a few lines of code. that wouldn't net them $1 million, but it would make for a legendary issue on Lean's GitHub, immediately invalidating any proof checked by Lean and undermining the language's credibility. 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, if the set of all sets contains itself, 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" and then got flattered into thinking I'm a genius. I studied the subject 10 fucking years and used AI to aid me materialize and double check my ideas. this is the antidote I found to AI psychosis. I call it "competency"

that said, if the solutions are mine, how Fable helped here?

well, the argument per se is obviously sound, and nobody serious would contest it. the problem is that implementing a proof assistant is 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! full proof below ↓

that was Fable's contribution, and, if you can't see how incredible this is, I don't know what could possibly impress 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!