Watching Dafny develop has been wonderful. It’s taken a lot of good ideas from 50 years ago and pushed them into the present in modern incarnations.
The predicate transformer semantics (and descendants) approach to proving a program has some properties is far more accessible to the typical programmer than cracking that egg with the sledgehammer of the Calculus of Constructions.
I’ve been a huge fan of calculational proof styles for over a decade now, ever since I did a deep dive into the UT Austin EWD archive. Here[1] is his brief explanation, but to really appreciate the beauty of the method one has to dig deeper into the many practical applications also on that site.
I also recommend looking into Boogie and Z3 for those who are curious about how Dafny does what it does.
[1] https://www.cs.utexas.edu/~EWD/transcriptions/EWD13xx/EWD130...
Indeed, I thought it would die in MSR, alongside Ironclad, instead it took a life of its own.
Thank you for sharing that document! The style is so thoughtful, it’s a delight.
thank you very much for the context!
wrt ewd1300, https://www.cs.utexas.edu/~EWD/ewd13xx/EWD1300.PDF is a scan in the original handwriting. it's been a number of years since i read it, and i'd forgotten most of its contents, though evidently i've incorporated some of them subconsciously. and i'm not sure i finished it last time
i've been using ∨ and ∧ for infix max and min, respectively, which is a generalization of their boolean-algebra use and appropriate to their use in the theory of lattices (the partial-order kind of lattice, of which the usual total order is a special case). unfortunately this clashes rather badly with the use of ∧ in geometric algebra, aka clifford algebra (e.g., https://arxiv.org/pdf/1205.5935) so i've been thinking about changing. dijkstra's choice of ↑ for max (supremum) and ↓ for min (infimum) are tempting
a second unfortunate collision is that recent versions of apl use ∧ and ∨ for infix lcm and gcd, which is also a generalization of their boolean-algebra use and appropriate to their use in the theory of lattices; it's just using a different partial order
i think dijkstra's choice of ';' for relational composition is rather unfortunate, though it's probably a better choice than my choice of simple juxtaposition in binate (http://canonical.org/~kragen/binary-relations) which uses ';' for the relational product, which i think is an equally unfortunate choice. • is the conventional operator for relational composition, and it doesn't introduce such fatal ambiguities when typeset, but it poses human-interface problems with a normal keyboard (how do you know how to type it?) and may be confused with some other kind of infix dot operator when handwritten, such as the infix function-application operator dijkstra explains here
a reasonable alternative is the ∘ conventionally used for functional composition, which is the same thing as relational composition when the relations in question happen to be functions, and so generally introduces no semantic ambiguity, as well as less typographical ambiguity in handwriting. it has the same human-interface problem as •
with respect to quantification, in http://canonical.org/~kragen/sw/dev3/paperalgo i've taken the approach ka-ping yee introduced in python, of treating quantified operators like Σ, Π, ∀, ∃, etc., as ordinary functions whose argument is a set or sequence; then we can notate the sequence with the moral equivalent of a list-comprehension. (the notation i use for such comprehensions in paperalgo unfortunately will not fit in this margin, but the web page displays it well.) dijkstra's choice here of ⟨i: i < 10: i²⟩ privileges dummy variables ranging over consecutive integers, but as he implicitly points out, you can use any logical proposition, such as ⟨i: i ∈ S: i²⟩, and while my choice privileges iterations over concrete sequences, you can similarly iterate over any set
i'm more interested in expressing algorithms, while dijkstra was more interested in proving properties of algorithms, and some of our differences in notational choices reflect this, such as this last one
This is great! Thanks for sharing your approach.
I come at it from the perspective of a working programmer who wants to improve his craft. Mostly I just think through the (pseudo) formalism because frankly most commercial code isn’t terribly complex when properly designed (or it’s such a mess time constraints don’t permit working through it formally). From time to time I work through the proofs though, especially in hard to test code. Also, I’ve been fortunate enough that in my career I’ve done some actual language semantics work in the mechanical checking space.
From that perspective, I kind of like “;” for composition, virtually entirely because it effectively works as a statement separator. E.g.:
if Pred(x)
DoThing(x);
DoOtherThing(x)
end
At a glance it looks like a statement terminator with a special elision rule for the end of a block, but really the body is just a single compound statement with semantics that can be determined from its constituent predicate transformers.I fully recognize how that’s hardly a compelling reason logically, but sometimes things just appeal aesthetically.
Also I guess it might simplify an implementation to be able to assume that every apparent “block” is actually a single, possibly compound, statement. There might be some interesting parsing implications too. I’m practically ignorant of concatenative languages (Lisp is my hammer of choice for playing around with language ideas). Perhaps I should fix that by hacking up a toy Forth inspired by Dafny.
you're welcome! i'm glad you enjoyed it
i agree that ';' as a statement separator is analogous to relational composition for predicate transformer semantics (which is plausibly why dijkstra chose it)
incidentally ';' in ocaml works syntactically in the way you want; it's a two-argument version of lisp progn
the block semantics i find most appealing is the semantics of henry baker's comfy-65/comfy-80, in which each statement has one entry point, which i'll call go, and two (possibly unused) exits, a yes exit and a no exit. (baker's nomenclature differs!) regular computational statements like assignments only use their yes exit, but comparisons transfer control to one or the other depending on whether the comparison succeeds or fails. to build a whole subroutine out of such atomic statements you have four combining operators. baker gives them lisp function names, but we could use infix operators for them instead, and describe how they wire things up with equality constraints:
(a ; b) : go = a.go, a.yes = b.go, yes = b.yes, no = a.no = b.no
(a ∨ b) : go = a.go, a.no = b.go, no = b.no, yes = a.yes = b.yes
(¬a) : go = a.go, no = a.yes, yes = a.no
(while a b) : go = a.go, a.yes = b.go, b.yes = go, a.no = yes, b.no = no
(hopefully that notation i just made up is clear, but let me know if not)baker has a couple of other combining constructs, but they're not fundamental. actually even ∨ is superfluous; (a ∨ b) ≡ ¬(¬a ; ¬b), so statement sequencing is the same thing as logical conjunction. you can add a do-while operator for loops with the loop test at the bottom which is dual to while in the same way
baker implements his compiler as a lisp function (compile statement yes no) which takes memory addresses where yes and no should transfer control, and returns an entry point (go); for the combining forms it recursively invokes itself, so it ends up generating code backward starting from the top of memory. his implementation of while requires inserting an unconditional jump at the end of the loop which is later backpatched to jump to the beginning of the loop
comfy has in common with forth that boolean expressions and blocks of statements aren't non-overlapping magisteria, the way they are in the more mainstream formulations; in forth, both a block of statements like s" x = " type x ? cr and a boolean expression like x @ y @ > are just doing one damn thing after another. but forth handles its booleans in the same way as lisp, c, or pascal, pushing a comparison result on the stack which is consumed by a following conditional-branch word, an approach which in forth results in inefficient and unsafe code for boolean operators because it can't short-circuit them like c's && and ||
while this is very appealing aesthetically, i can't help but feel that it might make proofs of correctness unnecessarily difficult. you can make some statements about control flow dominance: in any of a ; b, a ∨ b, or while a b, you know that b never runs unless a ran previously. but when you get out of a construct, how do you know what ran inside the construct? in a long sequence like a ; b ; c ; d any of the items in the sequence can potentially leap out with a no, skipping the later items
maybe you could consider comfy statements to be pairs of predicate transformers, one for the yes exit and one for the no exit?
Dafny seems really interesting in its own right but every time I come across it I just want the story of its... logo? crest? mascot? https://dafny.org/images/dafny-logo.jpg
it's indeed very startling
For anyone wanting to pick up Dafny (or just build some intuition around formal reasoning of code), this recent book is great: https://mitpress.mit.edu/9780262546232/program-proofs/