Live data from Hacker News

Coq: The World's Best Macro Assembler? (2013) [pdf]

nickbenton.name

31–40 of 75 posts

Re: Coq: The World's Best Macro Assembler? (2013) [pdf]

#31
post #18

Earlier quoted context omitted.

> I think that the reason that i386 assembly (or amd64 assembly) is error-prone is something else, something it has in common with very simple architectures and instruction sets like that of the PDP-8. What reason is that? (And, if it's not obvious, what are ARM/RISC-V doing that make them less bad?)

I don't think they're particularly less bad. All five architectures just treat memory as a single untyped array of integers, and registers as integer global variables. Their only control structure is goto (and conditional goto.) If you forget to pass an argument to a subroutine, or pass a pointer to an integer instead of the integer, or forget to save a callee-saved register you're using, or do a signed comparison on…

I have a postit note idea that says simply "typesafe macro assembler".

I've not fleshed this out yet, but I think a relatively simple system would help deal with all the issues you mention in the first paragraph while allowing escape hatches.

Re: Coq: The World's Best Macro Assembler? (2013) [pdf]

#32
post #12

Earlier quoted context omitted.

During the days I was studying/working with Coq, one visiting professor gave a presentation on defense software design. An example presented was control logic for F-16, which the professor presumably worked on. A student asked how do you prove "correctness", i.e. operability, of a jet fighter and its control logic? I don't think the professor had a satisfying answer. My question is the same, albeit more technically r…

You use floating point numbers instead of real numbers in your theorems and function definitions. This sounds flippant, but I'm being entirely earnest. It's a significantly larger pain because floating point numbers have some messy behavior, but the essential steps remain the same. I've proved theorems about floating point numbers, not reals. Although, again, it's a huge pain, and when I can get away with it I'd pref…

I have been curious about this. Where can you find definitions for the basic operations to build up from?

IEE754 does a good job explaining the representation, but it doesn't define all the operations and possible error codes as near as I can tell.

Is it just assumed "closest representable number to the real value" always?

What about all the various error codes?

Re: Coq: The World's Best Macro Assembler? (2013) [pdf]

#33
post #22
post #14

Earlier quoted context omitted.

No, I haven't, but I want to. I haven't had the opportunity to go deep into formal methods for a work project yet, and on personal projects I've mostly played with Ada SPARK, not Coq. I've played with Coq a little (to the extent of re-implementing the linked paper for a subset of a different ISA), but there's definitely a learning curve. One of my personal benchmark projects is to implement a (fixed-maximum-size) MMM…

What's a MMM heap? Is it a typo on min-max heap?

A min-max-median heap, I would assume.

Re: Coq: The World's Best Macro Assembler? (2013) [pdf]

#34
post #12
post #4

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…

During the days I was studying/working with Coq, one visiting professor gave a presentation on defense software design. An example presented was control logic for F-16, which the professor presumably worked on. A student asked how do you prove "correctness", i.e. operability, of a jet fighter and its control logic? I don't think the professor had a satisfying answer. My question is the same, albeit more technically r…

So the answer is that you are proving two things:

1. That the model/specification makes sense. i.e. that certain properties in the model hold and that it does what you expect.

2. That the SUV/SUT (system under verification/test) corresponds to the model. This encompasses a lot but really what you are doing here is establishing how your system interacts with the world, with what accuracy it does so, etc. And from there you are walking along the internal logic of your system and mapping your representations of the data and the algorithms you are using into some projection from the model with a specified error bound.

So you are inherently dealing with the discrete nature of the system the entire time but you can reason about that discrete value as some distribution of possible values that you carry through the system with each step either

- introducing some additional amount of error/variability or

- tightening the bound of error/variability but trapping outside values into predictable edge cases.

Then it's a matter of reasoning about those edge cases and whether they break the usefulness of the system compared against the idealised model.

Re: Coq: The World's Best Macro Assembler? (2013) [pdf]

#35

Earlier quoted context omitted.

You use floating point numbers instead of real numbers in your theorems and function definitions. This sounds flippant, but I'm being entirely earnest. It's a significantly larger pain because floating point numbers have some messy behavior, but the essential steps remain the same. I've proved theorems about floating point numbers, not reals. Although, again, it's a huge pain, and when I can get away with it I'd pref…

I have been curious about this. Where can you find definitions for the basic operations to build up from? IEE754 does a good job explaining the representation, but it doesn't define all the operations and possible error codes as near as I can tell. Is it just assumed "closest representable number to the real value" always? What about all the various error codes?

The standardized operations, e.g. multiplication or square root extraction, are precisely defined, i.e. the result is always defined exactly, by the combination of the corresponding operation with real numbers and by the rounding rule that is applied.

IEEE 754 also contains a list of operations that are recommended, but not defined by the standard, such as the exponential function and other functions where it is difficult to round exactly the result.

For the standardized operations, all the possible errors are precisely defined and they must either generate an appropriate exception or produce as result a special value that encodes the kind of error, depending on how the programmer configures the processor.

The standard is perfectly fine. The support of the standard in the popular programming languages is frequently inconvenient or only partial or even absent. For instance it may be impossible to choose to handle the errors by separate exception handlers and it may be impossible to unmask some of the exceptions that are masked by default. Or you may lack the means to control the rounding mode or to choose when to use FMA operations and when to use separate multiplications.

If you enable all the possible exceptions, including that for inexact results, the value of an expression computed with IEEE 754 operations is the same as if it were computed with real numbers, so you do not need to prove anything extra about it.

However this is seldom helpful, because most operations with FP numbers produce inexact results. If you mask only the exception for inexact results, the active rounding rule will be applied after any operation that produces an inexact result.

Then the expression where you replace the real numbers with FP numbers is equivalent with a more complex expression with real numbers that contains rounding operations besides the explicit operations.

Then you have to prove whatever properties are of interest for you when using the more complex expression, which includes rounding operations.

The main advantage of the IEEE 754 standard in comparison with the pathetic way of implementing FP operations before this standard, is that the rounding operations are defined exactly, so you can use them in a formal proof.

Before this standard, most computer makers rounded the results in whatever way happened to be cheaper to implement and there were no guarantees about which will be the result of an operation after rounding, so it was impossible to prove anything about FP expressions computed in such computers.

If you want to prove something about the computation of an expression when more exceptions are masked, not only the inexact result exception, that becomes more complex. When a CPU allows a non-standard handling of the masked exceptions, like flush-to-zero on underflow, that can break any proof.

Re: Coq: The World's Best Macro Assembler? (2013) [pdf]

#36
post #30
post #5

Earlier quoted context omitted.

I understand and respect the renaming, Coq was a much cooler name though.

It was. Renaming languages to suit American taste really grates. Nimrod to Nim was even worse. Apparently Americans cannot get Biblical references.

What if it was the word for Penis in Japanese or Chinese? I would understand them for changing it.

Re: Coq: The World's Best Macro Assembler? (2013) [pdf]

#37
post #26

A Lisp can mimic Prolog and the rigour of Coq with ease.

i'm a long time lisper, but i don't think this is justified.

implementing prolog/backtracking on top of lisp is certainly possible and not even too hard (see e.g. https://github.com/nikodemus/screamer)

and implementing Coq on top of lisp is also possible.

but IMO the "with ease" phrase is not justified in this context.

if you only mean that lisp will not be in the way if you set out to implement these, then i agree. lisp -- the language and the typical opensource implementation -- will be much less of an obstacle than other languages when chosen as foundations.

Re: Coq: The World's Best Macro Assembler? (2013) [pdf]

#38
post #33
post #22

Earlier quoted context omitted.

What's a MMM heap? Is it a typo on min-max heap?

A min-max-median heap, I would assume.

Yep, that. Just a bit more fiddly than a min-max heap, and though I rarely actually need the median functionality, fiddly is a pro for learning a language at times.

Re: Coq: The World's Best Macro Assembler? (2013) [pdf]

#39
post #10

Earlier quoted context omitted.

Have you found Coq or other formal-methods tooling useful?

I have found huge value in CBMC and KLEE for statically verifying C code for real time safety critical embedded applications. ACL2 is also VERY powerful and capable.

I'd love some examples here.

Re: Coq: The World's Best Macro Assembler? (2013) [pdf]

#40
post #30

Earlier quoted context omitted.

It was. Renaming languages to suit American taste really grates. Nimrod to Nim was even worse. Apparently Americans cannot get Biblical references.

What if it was the word for Penis in Japanese or Chinese? I would understand them for changing it.

then we should change bit(s) because it means dick/penis in french /s
Post reply on HN