Coq: The World's Best Macro Assembler? (2013) [pdf]
159 points by addaon
by addaon
3 subcomments
Poster here. I re-read this paper about once a year. I continue to think that it may be one of the most important papers I've read. As someone who works on high-reliability safety-critical real-time systems (automotive, avionics), being able to work in an environment where I could prove semantic properties of assembly code is pretty close to my dream -- the cost of demonstrating code correct is already so much higher than the cost of writing the code that the incremental cost of going to assembly seems minor, if there's even a small payback in time to demonstrate correctness. In practice, I think my dream language would be a relatively rich macro assembler plus a (guided, greedy) register allocator, designed entirely to simplify and allow semantic proofs. I don't really have a sense as to whether Coq (Rocq) is the right answer today, vs other options; or if there's a newer literature advancing this approach; but I'd truly love to see a deeper focus of making low level languages more useful in this space, rather than moving towards more constrained, higher level languages.
by quanto
0 subcomment
This paper reminds me of a class assignment in grad school where the prof asked the students to write a compiler in Coq for some toy Turning-complete language in a week. Having no background in compiler design or functional programming, I found it daunting at first, but eventually managed it. The Coq language's rigor really helps with something like this.
I wonder if AI's compute graph would benefit from a language-level rigor as of Coq.
It's a bit of an awkward syntax to get a reliable assembler. Does it at least allow you to prove the behaviour of a larger block of assembly? For example, could I use it to prove that a block of assembly is equivalent to a given set of operations?
by asdefghyk
1 subcomments
The x86 architecture and instruction set is complex - so it absolutely needs a powerful assembler to help prevent mistakes.
by anthk
3 subcomments
A Lisp can mimic Prolog and the rigour of Coq with ease.
by Svoka
0 subcomment
This is great. I honestly never thought of computer as a register state and instructions/asm commands as functions applied to it. But that makes so much sense.
Hacker News