HNHacker News
TopNewBestAskShowJobs

xavxav

1,035 karma · joined February 12, 2012

www.xav.io
submissionscomments
xavxav··on Formalizing 100 Theorems
> Can someone familiar explain why it's difficult, say, in an imperative language, to represent mathematical notation?

Is the question whether you can represent mathematical notation in an imperative language, or whether you can search for mathematical proofs in an imperative language? Or is it a broader question about why theorem provers usually use functional languages?

1. Representing mathematical notation is not any harder in an imperative language than a functional one: it's just an AST. Syntax isn't the hard part however, it's semantics which are tricky. For example, you say "apply random permutations with symbols on either side, check them for truth", but "checking for truth" isn't automatically possible. What if I randomly generated "P = NP", is that true?

2. You can totally write search procedures in an imperative language, generally these programs are earlier than in a functional language, but again there's nothing fundamental about the language choice here. SMT solvers are an example of this.

3. You may notice that many theorem provers incorporate a functional language as 'the language of proofs'. This is due to the 'Curry-Howard Isomorphism', which in short establishes a correspondence between theorems and types, and programs and proofs. For example, I could ask you "does there exist a function from A to A" and you could answer "yes, it's the identity function". You've just proved that there exists an item of type "A -> A". However, this correspondence stops making sense if functions can diverge or have side-effects. You also typically want higher-order closures and pattern matching, and at that point, you've got a functional language.

xavxav··on RZK: Experimental proof assistant for synthetic ∞-categories
wow that's really cool, I wonder what the essential difference is between type-in-type and other classic "nice" inconsistencies in type theories. It seems like it's "almost" consistent.
xavxav··on Google assigns a CVE for libwebp and gives it a 10.0 score
I'm tired and cranky today so this will lack subtlety, but:

    You don't have to use Rust but you **can't** use C. 
There's no reason to be finding these bugs in 2023; period, we can do better and we know how to do better, there's just no reason apart from legacy code (and even then) that you should be using memory unsafe languages in production.
xavxav··on Sucking carbon dioxide out of the sky is moving from science fiction to reality
Yes, but I you cut and store the wood at maturity you could plant fresh trees instead. The point is, trees are an entirely inadequate solution to climate change, at least on the CO2 front.
xavxav··on Sucking carbon dioxide out of the sky is moving from science fiction to reality
It takes ~40 trees to capture one ton per year, with ~40B tons emitted each year, that means planting roughly 160B trees each year. Humans have changed the world in a manner which natural ecosystems cannot recover on their own. We need to cut emissions to 0 and plant trees, establish moors, and other forms of CO2 capture.
xavxav··on DIY ESP32 based chicken coop door. Control based on time, light or via app
A project I've always toyed with in my head is a fancier version that would count / verify the checks have all entered the coop at closing time and warn you if not. With my parents coop occasionally a chicken will decide to brave the night outside, often to disastrous consequences.

Figuring out how to build a low-energy version is challenging, but necessary since the whole system runs off small solar panels and a 12v battery.

xavxav··on A good measurement culture where numbers don’t replace common sense
> It sounds like a profound wisdom and on a very surface level it does make sense, but think of this: if you can assess that a measure is a bad one, this means that you have your own intrinsic preferences, otherwise you wouldn't be able to tell that!

That assumes that the ones working towards a specific KPI are both the ones noticing the metric is bad and that their are noticing it before the negative consequences have destroyed their product / company.

Often when the issue of optimizing to KPI comes up, it seems that exterior people notice the problem but not interior ones, or otherwise the issue is noticed after the fact but not before a meaningful change could be affected.

xavxav··on AST vs. Bytecode: Interpreters in the Age of Meta-Compilation [pdf]
Compiling to C is definitely an option, but there are also plenty of low-hanging fruit that could come before. You could invest in a better interpreter or even some bytecode compilation first.

I don't know where your rules are coming from but I would personally not be super happy with the introduction of a c compiler running user-provided strings in the middle of my application.

xavxav··on The quest for a simple smartwatch
I really want a good health tracker with all the sensors of the Apple Watch but completely inconspicuous as smartwatches are ugly.
xavxav··on NPM won't publish packages containing the word keygen
Unrelated, but your homepage has very bad FPS using firefox on mac due to the animation. Once I manage to scroll it works quite well.
xavxav··on What Vale taught me about linear types, borrowing, and memory safety
They aren’t unless you’re willing to go significantly more complex than this naive translation suggests.

As an example, consider the index_mut function with signature

   fn index_mut(&mut Vec<T>, ix: usize) -> &mut T
How do you represent this?

However, this insight holds for relatively common forms of ownership, and you can see this exploited in electrolysis: https://github.com/Kha/electrolysis

xavxav··on Servo, the parallel browser engine written in Rust
> The borrow checker in Rust might be to important to turn off even sometimes.

Variations of this point come up often, that the main reason rust compile time is slow is typechecking or borrowchecking, but that’s not true, while those operations are expensive, it’s monomorphization (and llvm) that are the main drivers of compile time currently. Building a compiler on top of llvm is unfortunately going to be sluggish for feedback loops , regardless of your type system.

Also, unlike LTO, borrow checking is not just an optimization, turning it off would be like allowing you to add arrays and booleans together: meaningless and wrong. Anyways, you wouldn’t save more than ~10% time.

Apart from the rant above, I do agree that having the ability to tune optimization levels for development vs prod is good, I would like it if it were easier to do stuff like PGO or other stupidly expensive optimizations for releases.

xavxav··on Modern SAT solvers: fast, neat and underused (2018)
Oh right this is just Horn clauses, not CHCs
xavxav··on Modern SAT solvers: fast, neat and underused (2018)
Z3 is actually not a particularly good SAT solver, you really want to use a dedicated tool for pure SAT problems. On the other hand if your problem is in a richer class like QBF or SMT then z3 shines and often you can use encoding tricks to scale problems significantly
xavxav··on Modern SAT solvers: fast, neat and underused (2018)
Wait, this is very relevant to some work I’ve been doing recently, how do you conclude that Horn clauses should be preferred from Schaefer’s theorem?
xavxav··on The Silent (R)evolution of SAT
Indeed, but CreuSAT is actually a high-performance implementation (ie: worst of the best), I should probably just write up a Rust gist of CDCL.
xavxav··on The Silent (R)evolution of SAT
Conflict explanation in CDCL is entirely based around resolution, the idea being to take a conflicting set of clauses and apply resolution a bunch of times to “simplify” the conflict into its most general form.
xavxav··on The Silent (R)evolution of SAT
I almost exclusively use it with quantifiers which makes it equivalent to FOL. But even without quantifiers, theory combinations can introduce undecidability.

There’s the auxiliary problem that decidable but slow can often be equivalent to undecidable.

xavxav··on The Silent (R)evolution of SAT
A fun exercise is to write a series of sat solvers: brute force, DPLL and CDCL you really get an immediate feel for the strength of the algorithms and none of these implementations need to go much beyond 50-100 lines in a modern language.

You can then of course spend months tuning and optimizing the hell out of your code to squeeze a further 10x performance.

If you're really crazy like Sarek, you can also formally verify these implementations: https://sarsko.github.io/_pages/SarekSkot%C3%A5m_thesis.pdf

xavxav··on The Silent (R)evolution of SAT
I wonder if they'll write a followup on the SMT revolution that happened after the CDCL breakthroughs for SAT.

The lazy approach to SMT was a huge step forward, but itself spawned a whole lineage of refinements, alternatives and changed the state of automated reasoning entirely.

A lot of work today seems to be going into theory combinations so that you can efficiently answer problems for example involve arrays and integers in a manner that has dependencies between the two.

'Solving' (it's an undecidable problem) SMT would open up a bunch of new possibilities..

xavxav··on Breakthrough deal to prevent Colorado River from drying up
On its face I'm not against using analogies to explain scale, but its not like i really have an intuitive grasp on the size of a 747 or a football field's volume. It also helps to remember that 1m^3 is 1000L which allows you to transform this into much easier (at least to me) analogies.
xavxav··on ПП-BESM – a Soviet language (1955)
I have a commented example: https://github.com/xldenis/besm/blob/master/examples/chapter...

I tried to transliterate the syntax to ascii but the 'real' syntax uses some characters which are hard to represent in monospace text.

xavxav··on ПП-BESM – a Soviet language (1955)
Indeed, I only provided direct translations of the programs Ershov and Knuth wrote, I never did much in the way work beyond that, my focus was mainly on recreating the compiler itself.

For that I actually copied the pages of the book into the the comments of the code: https://github.com/xldenis/besm/blob/master/compile-pp/src/B...

xavxav··on ПП-BESM – a Soviet language (1955)
I have perused those archives many times, more important than the book (of which I have a translated hardback copy), are the notes which include the hand written (and commented) assembly for every draft of the compiler. The hard part is that its not the same as the final version so you have to interpolate the changes.
xavxav··on ПП-BESM – a Soviet language (1955)
Hi! I'm the author of this project :) Happy to answer any questions, and yes I know I need to finish it.

The project includes a VM for the BESM which I think has pretty sexy visuals: https://twitter.com/xldenis/status/1035557182337499137

I've been meaning to return to it now that I'm finishing my PhD thesis.

xavxav··on The DRAKON Language
Oh I love this project, its very interesting to think about its relation to the family tree of soviet programming languages.

From the start (ie: 1946-48) they conceptualized programming through the notional of 'logical schemas' or 'logical operators' which were a pseudo-textual notation for flow charts. They went so far as to develop entire theories for the analysis, and optimization of these logical schemas.

Another fascinating language was Analitik which was a language for CAS (like Matlab) developped by V. Glushkov in Ukraine.

There exists a fantastic website about programming languages in the ussr: http://www.compiler.su/ekskurs-v-istoriyu-razrabotok-yazykov...

There are also entire journals worth of these papers on PL design from the '50s which have been translated to english and sit rotting in university shelves.

edit: there's actually another post on the front page on my project to recreate the first of those languages: https://github.com/xldenis/besm, though unfortunately I have let it fall aside in recent years.

xavxav··on Telly Is the First TV Paid for by Brands
I couldn't tell if this was satire or not but it seems to be completely serious?
xavxav··on The seven specification ur-languages
On second thought, these are mostly too closely related, I think that if you want to truly find the ur-specification languages this is closely related to Girard's research program. Specification languages are intrinsically tied to a notion of truth and also of proof (method of establishing / showing truth), these are central questions in Girard's work.

I think a revised list should also include proof-nets, and other weirder specification languages like the [flower calculus](http://www.lix.polytechnique.fr/Labo/Pablo.DONATO/drafts/FJ....) or stellar resolution. These also stretch the usual interpretation of language as a syntax tree.

xavxav··on The seven specification ur-languages
Based on the state of academic conferences in formal methods, I would have 4 languages: temporal logic, first order logic, concurrent separation logic and dependent type theory. This categorization provides generalizing powers because tools, techniques and limitations mostly map onto it.

* temporal logic: almost exclusively used by model checkers. Usually propositional, has limited/no support for quantifiers. Also usually only able to express path properties. This for example makes it hard to state “is_sorted”.

* first-order logic: used by deductive (semi-automatic) verifiers. Can reason about complex properties of state (ie : `is_sorted`), harder but not impossible, to reason about temporal properties. Ill-suited to describe properties involving shared state or concurrency. Used by SMT solvers in particular (good automation). Also used by most deductive verifiers and liquid type systems. Examples: Dafny, Why3, SPARK (spec part), liquid Haskell.

* concurrent separation logic: can be either propositional, first-order or higher order. Does much of the same kinds of properties as FOL, but it can reason about shared state and concurrency, in fact it’s quite good for that. This expressivity usually means it’s harder to reason about / prove specifications. Examples: Iris, Viper, Verifast.

* dependent type theory: when you start pondering what it even means to specify something, the gods of CS bestow upon you a vision of the haskell-curry isomorphism and your programs become specifications and your specifications become programs. This is the “ultimate” level of specification, and the foundation for proof assistants. Examples: Coq, Lean

Each of these categories is well represented at conferences and pretty much every paper falls into one of these four buckets. These also map roughly onto verification methodologies and problem domains.

xavxav··on The seven specification ur-languages
This is a good list but is almost more accurately called a list of modeling languages. At the very least it’s a very particular interpretation of specification, which makes sense from a TLA+ expert but is incomplete.

In particular I think there are a few candidate ur-specification languages that could be included:

* first-order logic, this captures what almost every deductive verifier uses, and has a surprisingly rich diversity in features.

* concurrent separation logic, this was a breakthrough development and every language for specifying concurrent programs is some flavor of this now.

* dependent type theory? The big issue is that as the author points out, taxonomies fail. Dependent type theories give rise to languages which are both “specification” and “programming” languages.

← PreviousPage 2 of 5Next →