News for hackers. Stuff that matters.
Re:The C standard formalized in Coq by pron on Monday November 30, 2015 @02:20PM (#10651127)
> For instance, in higher-order set theory a (very strong) form of the axiom of choice asserts that there is a function "epsilon : set -> set", such that "epsilon x \in x" for x not empty

Such higher-order statements are easily expressible in TLA+ as long as you specify the domain of the sets on which you operate, which you should always be able to do when specifying real programs, even higher-order programs. Here it is in TLA+:

     ∃ epsilon ∈ [SUBSET S → S] : ∀x ∈ SUBSET S : epsilon[x] ∈ x
You just need to specify S (or parameterize it).

> Saying "I'll just use ZFC" is exactly the same as a programmer exclaiming "I'll just use COBOL".

I don't think it's the same at all, considering that 99.9% of math is done with "just ZFC". I don't doubt that type theory may let us explore other logics, but as a practical way for specifying real programs today I fail to see a case in favor of dependent types. Sure, I believe dependent types may let you define all sorts of modal logic, but in practice, temporal logic has proven a good way to specify algorithms. So I think that a more suitable analogy would be, "Why confine your thinking to von-Neumann machines when you can use a meta-logic to specify programs for Quantum computers and other computational models". In that case, "I'll just use a von-Neumann machine" seems like a very reasonable choice for any work that isn't theoretical.

Re:The C standard formalized in Coq by fmap on Monday November 30, 2015 @03:00PM (#10651380)
I am honestly unconvinced on "most of mathematics" being just ZFC. You see this claim a lot, but when reading formal developments in mathematics I often see justifications involving "small categories" or statements which should hold in ZFC with "enough universes a la Tarski".

But this is missing the point. There is a lot of active research work on program logics for reasoning about e.g., concurrent programs in weak memory models. You may be able to encode the model of something like Iris (http://plv.mpi-sws.org/iris/) in TLA, but the challenge lies in doing this in a usable format...

Re:The C standard formalized in Coq by pron on Monday November 30, 2015 @11:41PM (#10653667)
I am working on specifying a weak memory model system in TLA+ right now, and have yet to encounter any issue.
Re:The C standard formalized in Coq by fmap on Tuesday December 01, 2015 @02:00AM (#10653997)
Neat! Do you have some pointers to your work? I would be especially interested in example verifications of lock free data structures and in comparing the proof effort to logics custom built for this purpose.

All the constructions I know use at least second order logic and something like Iris is - as far as I know - most elegantly described internal to the topos of trees. If you have found a good way to avoid this complexity then that's a significant contribution.

Re:The C standard formalized in Coq by pron on Tuesday December 01, 2015 @03:50AM (#10654241)
> Do you have some pointers to your work?

At the moment we're not open-sourcing the spec (I'm an engineer, not an academic) but we might in the future. We've opted not to even try to prove the system's correctness, as that might take decades (it's far more complex than, say, seL4). Instead, we're just formally specifying it, and model-checking it with a finite model. The software in question, however, is itself open-source and is described here: http://blog.paralleluniverse.co/2012/08/20/distributed-b-tre...

> All the constructions I know use at least second order logic

Concurrent algorithms are specified with TLA+ (in the industry, I mean) quite frequently. Also, specifying the memory consistency properties does require second order logic, but as I've shown in another comment, TLA+ handles second-order logic gracefully and in a very straightforward matter (trivially, I would say). You simply write:

∃ ordering ∈ [operations → SequenceOf(Op)] : ConsistencyProperty(ordering[operations])

Re:The C standard formalized in Coq by pron on Tuesday December 01, 2015 @05:58AM (#10654559)
Sorry, that should be:

    ∃ epsilon ∈ [SUBSET S → S] : ∀x ∈ SUBSET S : x ≠ {} ⇒ epsilon[x] ∈ x
As a matter of fact, TLA+ also allows unbounded quantifications, so you could write:

    ∃ epsilon : ∀x : x ≠ {} ⇒ epsilon[x] ∈ x
However, this form is rarely used because TLC, (TLA+'s model checker, which only supports a subset of TLA+), doesn't support unbounded quantifiers, and they are not necessary when modeling real programs. I'm not sure about TLAPS (the proof assistant), but I believe it handles it fine.