Computer Science✓

Parsing expressions by recursive descent

'The purpose of abstraction is not to be vague, but to create a new semantic level in which one can be absolutely precise' - Edsger Dijkstra

Conceptually you define sinh in terms of exp, but numerically it's better to compute exp in terms of sinh.

'Premature abstraction is as bad as premature optimization.' -- Luciano Ramalho

The Euclidean algorithm is not optimal among uniform processes

The Church numeral for a non-negative integer n is λxy. x^n y

How much can Boolean expressions be simplified?

“Having functional programming as an ideal doesn’t imply that programs should never have side-effects. It just means that they should have no more than necessary.” — @paulg, On Lisp

'One person's data is another person's program.' -- Guy L. Steele, Jr.

How a programmer might reinvent the projective plane

'One of the main causes of the fall of the Roman Empire was that-lacking zero-they had no way to indicate successful termination of their C programs.' — Robert Firth

Machine learning by satisfiability solving

Does DNA have the equivalent of IF-statements, WHILE loops, or function calls?

Every cellular automaton is a local automaton. -- Curtis Hedlund Lyndon theorem

RT @lemire: Decades ago, people tried to formally verify code. Essentially, you prove that the code is correct using math. It was an approach promoted by people like Dijkstra, who observed that “program testing can be used to show the presence of bugs, but never to show their absence” (1970). It did not work. It was too difficult. You can do it for a function, maybe a small piece of code… but for anything useful, it was just too much work, and the result was too weak. Classic examples include the seL4 microkernel, about 8,700 lines of C requiring ~200,000 lines of Isabelle proof and roughly 20 person-years of verification effort. But times are changing. So it appears that we can formally verify code these days. Or, at least, there is now a ton of startups and academic initiatives that say it is possible and maybe practical. Take your C code, have your AI prove that it is a correct implementation of the specification. Among other things, it would prove that the code is correct with respect to memory usage, but that’s the least of what it could do. The most obvious application is cryptography and anything that must be unbreakable. Have your AI prove that the system cannot be hacked. You should not get too excited. These will remain mathematical models. They have to make assumptions all over. But I am pretty excited about what this could enable. I'd love to have more formal analysis of my code. In fact, I have a few projects in mind right now, to formally verify heuristics that I have been using. Recent examples of startups: •&Truth (launched Oct 2026, ~$70M seed): Building a “universal verification machine” for any language. •Harmonic (Aristotle): Announced support (late Oct 2026) for formal verification of C software and Verilog hardware.

'Security is both a feeling and a reality. And they’re not the same.' -- Bruce Schneier

Four views of multisets

RT @lukeigel: An ad for an expensive computer in 1951

'Beware of bugs in the above code; I have only proved it correct, not tried it.' -- Donald Knuth

'Sometimes, the elegant implementation is a function. Not a method. Not a class. Not a framework. Just a function.' -- John Carmack

Gray code