On Mon, 25 Mar 2013, Chris Warburton wrote:
John Carlson <[email protected]> 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
Interesting way to look at datatypes and encoding/parsing. Thanks for that :)
_______________________________________________
fonc mailing list
[email protected]
http://vpri.org/mailman/listinfo/fonc
