John Carlson <yottz...@gmail.com> writes: > So is anyone looking at binary parser generators? It would seem like > something like this would have been done ages ago.
Brings to mind "Every Bit Counts". It's a library for serialising and deserialising datatypes by using each bit as a yes/no answer, eg. we might create a 4 bit encoder/decoder for the following datatype: data Foo = A | B | C Bool The first bit would tell us if it's a C, the second bit would tell us if it's an A or a B, or the value the Bool, depending what the first bit was. The library is composable, so when we define higher-order types: data Bar a = Good a | Bad a We only have to implement the "Good or Bad" part; the encoding/decoding of the parameter "a" will be carried out by existing parsers. It works by representing datatypes as binary trees with values at the leaves. To encode/decode we make a path from the root to a leaf, where left = 0 and right = 1 (or vice versa). The paths are prefix-free codes, which is why I took an interest in Binary Lambda Calculus, Binary Combinatory Logic and Every Bit Counts a few years ago (BLC and BCL are prefix-free as well). Prefix-free languages are interesting since they're suitable for "Universal Search" (AKA "Levin Search"), which is a theoretically-optimal-yet-practically-useless search algorithm[2]. [1] research.microsoft.com/en-us/people/dimitris/every-bit-counts.pdf [2] http://www.idsia.ch/~juergen/mljssalevin/node4.html Regards, Chris _______________________________________________ fonc mailing list fonc@vpri.org http://vpri.org/mailman/listinfo/fonc
