A blog about computer science, logic and programming. Occasionally other topics reasonably consistent with the rest.
Where do you put your unwanted objects? The objdump What is Marie Kondo’s favorite tool? Clang-tidy What wizard reduces binary size? The wizard of Oz Why didn’t Frodo understand the ring? He doesn’t readelf Why did a prison hire a compiler? To do escape analysis What does an elf use to move houses? Relocations What does the program say when it jumps to an invalid address? Every day we stray…
I’ve been working on system-level software for Linux for some time now, which is a job that makes you much more likely to encounter the odd corner of an operating system than higher level development. For all practical purposes, Linux has succeeded as an operating system. Billions of web queries are being served from Linux servers every day, and it’s running on billions of mobile devices. But of…
With the unprecedented en vogue 1 right now, I have taken the unprecedented step of trying out Emacs after having been a loyal Vim user for years. This is not going to be another charge in the endless Editor War 2 . Rather more uncontroversially, this is going to focus on note-taking and how technology can (and cannot) help. If how this relates to Emacs is a mystery, just trust me that this will…
DISCLAIMER : Let me say this first. Google’s regular expression implementations are known for not implementing features that make them, well, not regular. Both re2 and Golang’s regexp do not support backreferences. Otherwise, the things done here would be hard, or impossible. I may not be Golang’s biggest fan in general (lack of generics, verbose syntax, simplistic type system, etc), but I’ve…
Hello, I am Florian and you might remember me from posts such as Turing Completeness . Today I am going to return to the topic of Turing Completeness, in a post in similar vein. Today’s post explores the arguments Zed Shaw presents in Learn Python The Hard Way on why Python 3 is the inferior version of the language; in particular, how the concept of Turing Completeness is abused to make a point…
The other day I was asked to take a look at code I had written years ago that basically allowed the user to build up logical formulas while always keeping them in CNF (conjunctive normal form – that is, a logical formula where the outermost connective is always a conjunction). This was done by building a class hierarchy with an abstract class Expr on the top level, two classes ExprAnd and ExprOr…
The subtle difference between incompleteness (of a theory), completeness (of a proof system) and indecidability (of a logical system) are a common source of confusion. How come Gödel proved both completeness and incompleteness? How can a proof system be complete (there exists a proof for every true sentence) when the underlying logical system is undecidable (it is impossible to find a proof for…
This paper is about detecting a user’s keypresses using the interference the movements of the fingers cause in WiFi signals. This sounds scary and like something out of a cheesy spy movie; nevertheless it is not quite time to get out your tinfoil hat, as (at least as demonstrated) this is only accurate in controlled conditions where equipment is specifically set-up and the user is instructed not…
This is one of my pet peeves: I have heard many people describe Turing-complete as “a language you can do everything with”. That is untrue and this is a very short post to set this right. Turing-complete means a language can be used to express a (probably non-proper – if you manage to find a system that is more expressible than the Turing machine, I am sure there is a Turing award or two waiting…
It has been a long time since I last posted one of those, apologies! I have been fairly busy with various things and the time I had for this blog I spent on non paper-related posts to mix things up a bit. The paper I read for this post is about GraphLab which is a framework for expressing parallel computations based on a graph model that allows to exploit the sparse structure of machine learning…
I recently got the book What is the Name of this Book? by the excellent Raymond Smullyan, who is also the author of a book about Gödel’s Incompleteness Theorems I could not praise highly enough. The book I purchased is a collection of logical riddles. While recreationally solving logical puzzles oneself can be very rewarding, when I got the book I considered that it would be interesting to try and…
For some reason that is not completely clear to me either, I decided to go about and implement the sequent calculus technique for theorem proving this weekend. Because that alone would be a rather dull exercise, I decided to do it in a language I do not know very well. I first thought about trying to implement it in OCaml, but then decided to go with Haskell because there I at least know some…
Even though week-ish is an intentionally vague concept, I should apologize for this week-ish to take particularly long. The last month has been very busy and exhausting for me, so even though I read a paper, I never got to finish this post until now. This paper presents no original insights, but is a very readable introduction into the Curry-Howard isomorphism and concepts related to it. It does…
The paper in question covers something that I have been meaning to read up for months: the arithmetical hierarchy, which was sadly not covered in the university courses I have attended. If you are into theoretical computer science, you might have come across things like or ; I have, and while I knew that they had something to do with the arithmetical hierarchy (which I did not know what exactly it…
This paper was more discovered than chosen. I decided to write this week-ish’s post sitting in a train without Internet connection, so I scanned my Download folder for the random papers I have accumulated over the months. I discovered this paper, which seemed interesting and brief enough so I could finish reading it on the train. It is, as is fairly obvious, about Brewer’s conjecture. To be…
I have been meaning to read this paper for quite some time, but for some reason, even though its entire point is proposing an understandable consensus algorithm, Paxos’ (the canonical consensus algorithm previous to this paper) reputation for being impossible to understand kept me from reading this paper whenever I was short on time – that is to say always. Probably I was assuming that an…
Looking around for papers to cover in this series, I remember a talk about folding algorithms one Erik Demaine gave at my former university as the annual Vienna Gödel Lecture, where once a year major contributors to the field of computer science (other guest lecturers were Don Knuth and Peter Norvig) are invited to give a talk about their work. I skimmed through his very impressively long list of…
So, I feel like cheating a bit again as this paper is only three pages long, but I guess it is an ACM Turing Award lecture paper, so it deserves a spot here, at least for historical significance. Also, the paper is written by the highly influential (well – which goes without saying considering the Turing Award) Ken Thompson. In the introduction he argues that while people may expect him to talk…
First of all, sorry for the delay! I have moved this weekend (with a few complications) and am currently without Internet at home, and Three are actively trying to prevent me tethering from my phone (and I don’t want to violate the contract). This is actually, for computer science, a fairly old paper, written by no less than Stephen Cook, about whom you might have heard, for instance regarding the…
First, I will, for the coming few weeks, reduce the frequency of these posts to one a fortnight – for one, fortnight is an amazing word, and also I am rather busy with moving (and working), so I will resume to the usual frequency after I have settled a bit. With this out of the way, now on to talking about papers! This week’s paper was published by Cynthia Dwork (the co-inventor of differential…