Great paper. I remember actually physically printing it off and putting it in a folder when I was in undergrad. I still actually look at it again every few years just because I liked the idea so much.
First read the paper last week, though heard the concept in 2014 from a colleague who implemented it [1] (for fun I assume).
Recently revisited his little demo interested in the parser design; this time re-reading, the translation between Boolean logic expressions and TCP checksum calculations finally clicked for me.
My current mental model of it is coercing a calculator, which “only” performs addition and subtraction, into evaluating complicated conditional logic expressions. Not sure how a category theorist would describe it; is it an equivalence of two different categories (evaluation of logic expressions/abstract syntax trees) <> (bitwise negation & addition on integer arrays which represent Boolean matrices)?
In a practical engineering sense, I like to think the core concepts illustrate performance optimization principles for representing branching code as branch-free code. I think branching code is likely faster evaluating single expressions, but branch free representations could be useful for SIMD vectorization, e.g., to increase throughput for evaluating a large number or stream of expressions (such as evaluating security policy rules against operating system events).
2 comments
[ 3.8 ms ] story [ 10.7 ms ] threadRecently revisited his little demo interested in the parser design; this time re-reading, the translation between Boolean logic expressions and TCP checksum calculations finally clicked for me.
My current mental model of it is coercing a calculator, which “only” performs addition and subtraction, into evaluating complicated conditional logic expressions. Not sure how a category theorist would describe it; is it an equivalence of two different categories (evaluation of logic expressions/abstract syntax trees) <> (bitwise negation & addition on integer arrays which represent Boolean matrices)?
In a practical engineering sense, I like to think the core concepts illustrate performance optimization principles for representing branching code as branch-free code. I think branching code is likely faster evaluating single expressions, but branch free representations could be useful for SIMD vectorization, e.g., to increase throughput for evaluating a large number or stream of expressions (such as evaluating security policy rules against operating system events).
[1] https://github.com/bninja/parasitology