3 ms·
The difference between these two is that the first one describes a tree in an extremely consistent form whereby parens represent children and spaces represent s
by sparkie 12y ago
The difference between these two is that the first one describes a tree in an extremely consistent form whereby parens represent children and spaces represent siblings. The latter represent a tree only by means of a special "parser", which converts this sequence of characters into the tree.
What's special about the former one is that it composes perfectly with any other tree structure using the same textural representation of trees, where the latter one is only useful in isolation - one cannot use this representation inside some other arbitrary character sequences which is to be converted to trees, because the means by which it is parsed into a tree does not compose well (unambiguously) with other means of parsing sequences of characters into trees.
Perhaps the cleverest thing about S-expressions is that they were invented before we even had a theory of parsing unambiguously followed by a proof that we cannot compose multiple of these unambiguous parsers in a way which produces another unambigous parser.
- agumonkey 12y agoIt's a bit over my head, not sure I get what you said. But IIRC, Terence Parr wrote an article about composable parsers still being open research problem. But I'll add one delightful trait: sexps split usually complex parsing stage in two simple separate ones: - chars -> sexp - sexp -> meaning (special forms / anticipated mental evaluation). It's like a catalytic system.
- sparkie 12y agoComposible parsers are indeed an open research problem, but it'd be wise to consider them more like the philosophers stone. Even humans find unambiguity in their languages which are quite well structured, yet some people are hanging onto the hope that a machine will be able to take arbitrary combinations of partially structured clauses and produce some kind of unambiguity. It isn't going to happen. At least not with plain text. There's some terrfic research in composing languages - currently the best is Tratt and Diekmann's Language Boxes, which enable arbitrary syntax composition by means of the programmer specifying the syntax boundaries explicitly - which requires a more sophisticated editor than out plain text notepad variants. With language boxes, and their prototype editor Eco, in the end, they're ultimately storing a tree of data in their own custom format - it doesn't matter what encoding is used, just as it doesn't matter whether lisp uses parens, braces or whitespace - what really matters is that you encode things deterministically into trees which can be easily reasoned about without requiring some "magic" (AI) which attempts to create a tree from a sequence of characters unambiguously, when the programmer knows and can specify exactly what he means.
- agumonkey 12y agoOh I remember Eco, it was very exciting to see someone going that path fully. Ah, and I just realized, it wasn't Parr, but Tratt that wrote the paper "Parsing: The Solved Problem That Isn't".
- thomaskrauss 12y agoI was not aware at all of these notions. Thanks for the various pointers!