Thank you for your thought-provoking explorations, for the unwarranted flattery, and for taking the time to respond! Clearly we share an interest in flexible simplicity.
As for S-expressions, I agree that what I wrote above is a pretty minimal definition of S-expressions, but I still think it's valid as a definition of "S-expression", even though you'd use a modified definition in some environments. In particular, I think it successfully analyzes the structure of the S-expressions you use as examples. And I agree that it doesn't match the same strings as those modified versions; for example, it doesn't recognize $ as a symbol, or allow '.
The lexical syntax specified in R⁷RS §7.1.2 is, I think, a lot more complex than S-expressions, and it does not purport to define S-expressions; it includes Unicode, booleans, bytevectors, strings, piped symbols, vectors, circular references, quote, quasiquote, unquote, unquote-splicing, hexadecimal numbers, octal numbers, binary numbers, floating-point numbers, and so on. LISP 1.5 couldn't handle any of these, but I would be very uneasy with the assertion, "LISP 1.5 couldn't read S-expressions."
As an example of a more fleshed-out S-expression language, a few years ago when I wrote Ur-Scheme (a Scheme-subset compiler in the language it compiles), my S-expression parser supported lists (with optional dotted tails), quote, string literals, symbols, comments, signed decimal integers, booleans, and character literals. (Check out the section "Actual Parsing" in http://canonical.org/~kragen/sw/urscheme/compiler.scm.html.) This is evidently enough to conveniently write a compiler in, and I think some of it doesn't really belong to S-expressions per se — quote, comments, and booleans, for example.
One problem of my suggested data model is that, although the language is closed under concatenation (unlike, say, HTML, XML, JSON, or RFC-822), that concatenation is not semantics-preserving. Given these two Jevko documents:
x [y] z
a [b] c
concatenating them changes the label for [b] from "a" to "z\na", and perhaps more damningly, erases the whitespace before "z". But, since none of the alternative formats (except ndjson and I guess plain uninterpreted binary, ASCII, or Unicode) is closed under concatenation, maybe that's less important.
I don't know if you saw the last time this topic came up I linked to https://ogdl.org/, which seems pretty close to a minimal rose-tree notation. They also put some thought into designing a query language for their rose-tree-like data model, which might be adaptable to Jevko — though they label only nodes, and Jevko labels both nodes (with suffixes) and arcs (with prefixes).
Maybe that's the subtitle for Jevko? "A minimal Unicode syntax for ordered trees with labeled nodes and labeled arcs." If that's the intended semantics it would be pretty easy to whip up a diagram in Dot to illustrate it.
> Thank you for your thought-provoking explorations, for the unwarranted flattery, and for taking the time to respond! Clearly we share an interest in flexible simplicity.
Indeed we do! :)
> As for S-expressions, I agree that what I wrote above is a pretty minimal definition of S-expressions, but I still think it's valid as a definition of "S-expression", even though you'd use a modified definition in some environments. In particular, I think it successfully analyzes the structure of the S-expressions you use as examples. And I agree that it doesn't match the same strings as those modified versions; for example, it doesn't recognize $ as a symbol, or allow '.
Other than that it's a indeed lovely minimal definition. And it allows binary strings!
Now if such a definition was accessible as some formal spec and implemented in various languages the way JSON is, I'd probably not be inclined to rolling my own. Or maybe I still would, because it's fun! ;)
> The lexical syntax specified in R⁷RS §7.1.2 is, I think, a lot more complex than S-expressions, and it does not purport to define S-expressions; it includes Unicode, booleans, bytevectors, strings, piped symbols, vectors, circular references, quote, quasiquote, unquote, unquote-splicing, hexadecimal numbers, octal numbers, binary numbers, floating-point numbers, and so on. LISP 1.5 couldn't handle any of these, but I would be very uneasy with the assertion, "LISP 1.5 couldn't read S-expressions."
Sure. So, would you agree that with proliferation of Lisp variants the term "S-expression" became rather vague?
> As an example of a more fleshed-out S-expression language, a few years ago when I wrote Ur-Scheme (a Scheme-subset compiler in the language it compiles), my S-expression parser supported lists (with optional dotted tails), quote, string literals, symbols, comments, signed decimal integers, booleans, and character literals. (Check out the section "Actual Parsing" in http://canonical.org/~kragen/sw/urscheme/compiler.scm.html.) This is evidently enough to conveniently write a compiler in, and I think some of it doesn't really belong to S-expressions per se — quote, comments, and booleans, for example.
Holy moly, this looks very nice! I like the style. Kudos.
> One problem of my suggested data model is that, although the language is closed under concatenation (unlike, say, HTML, XML, JSON, or RFC-822), that concatenation is not semantics-preserving. Given these two Jevko documents:
x [y] z
a [b] c
> concatenating them changes the label for [b] from "a" to "z\na", and perhaps more damningly, erases the whitespace before "z". But, since none of the alternative formats (except ndjson and I guess plain uninterpreted binary, ASCII, or Unicode) is closed under concatenation, maybe that's less important.
Yes, being closed under concatenation is a feature I was aiming for and it indeed does bring with it this issue.
Just something to have in mind when devising formats. A simple solution here is to disallow having anything other than whitespace in the suffix of a Jevko with > 0 children. Then, if a format converts these labels to keys in a map, trimming leading and trailing whitespace, there is no problem. This is how I did it here:
I have experimented with indentation-based syntaxes myself, before settling on brackets.
I have found them to be problematic, at least because:
* For complex structures they become less compact.
* A grammar that correctly captures significant indentation can't really be written in pure *BNF. The way OGDL does it is this:
[12] space(n) ::= char_space*n ; where n is the equivalent number of spaces (can be 0)
[13] block(n) ::= '\' (comment|break) (space(>n) string break)+
I had the same idea. Simple enough, but still. Brackets are simpler to formalize and implement and not harder to explain.
> They also put some thought into designing a query language for their rose-tree-like data model, which might be adaptable to Jevko — though they label only nodes, and Jevko labels both nodes (with suffixes) and arcs (with prefixes).
Yes, that might be interesting to look at, thanks for pointing it out. I have thought about this and came up with some ideas, but haven't decided on anything. I was thinking more along the lines of having the path DSL be simply implemented on top of Jevko, not as a completely separate grammar.
> Maybe that's the subtitle for Jevko? "A minimal Unicode syntax for ordered trees with labeled nodes and labeled arcs." If that's the intended semantics it would be pretty easy to whip up a diagram in Dot to illustrate it.
It's a nice description, but I think a little to detailed and technical to fit into a tagline. Maybe a little explanatory article with the diagram included. Would probably look something like this:
I don't think your revision of the "S-expression" grammar is in accordance with the normal use of the term; it says ()() is an S-expression, when conventionally it's considered to be two of them. If that's what you want, then adding the outer *() is fine, but you should probably drop the leading * on the recursive call *ex, because otherwise the grammar is ambiguous.
If you want to allow binary strings you'd probably want to define the language over bytes rather than Unicode code points, though Markus Kuhn's UTF-8B (implemented in Python as "surrogateescape") can give you the best of both worlds.
Yes, I agree that "S-expression" is rather vague, much like "CSV".
If you disallow having anything other than whitespace in a Jevko with >0 children, Jevko becomes a rose-tree notation, except that the root is unlabeled, so really it's more like a rose-forest notation. If you want a rose-forest notation, you can get it in a less irregular way by declaring that Jevko infers an extra [] following a suffix containing any non-whitespace character, so foo[bar] is equivalent to foo[bar[]], foo[bar[]baz] is equivalent to foo[bar[]baz[]], and a[b]c is equivalent to a[b[]]c[], but foo[bar[] ] is equivalent to foo[bar[]] and not foo[bar[][]].
This change would foreclose the possibility of having significant leading or trailing whitespace in some places but not others, the way I was suggesting.
Rose trees or rose forests are definitely simpler than Jevko's current data model, and they are equally powerful.
Agreed about indentation.
With respect to diagrams, git clone http://canonical.org/~kragen/sw/pavnotes2.git and look at {horse,johnsmith,player}.{jpg,jevko,dot}. For the diagrams I've taken the liberty of ignoring leading and trailing whitespace on arc labels (prefixes), as well as suffixes consisting only of whitespace. johnsmith and horse are your examples, but they just use Jevko as a terser syntax for JSON that suffers a whitespace problem.
player.jevko is an example I cooked up based on Minetest's relational database schema, recast as a hierarchical schema. It also takes advantage of the ordered nature of subJevkos, the possibility of multiple identical prefixes in the same parent node, and the possibility of having both "headers" (subJevkos) and a "body" (suffix) in the same node.
(As far as I’m concerned, everyone is free to redistribute these nine files, in whole or in part, modified or unmodified, with or without credit; I waive all rights associated with them to the maximum extent possible under applicable law. Where applicable, I abandon their copyright to the public domain. To the extent that I wrote them at all, I wrote and published them in Argentina in 2022. Today, in fact. But you wrote horse.jevko and johnsmith.jevko, deriving them from things on Wikipedia, so my abandonment of copyright here shouldn't be construed as claiming that I wrote them.)
> I don't think your revision of the "S-expression" grammar is in accordance with the normal use of the term; it says ()() is an S-expression, when conventionally it's considered to be two of them. If that's what you want, then adding the outer *() is fine, but you should probably drop the leading * on the recursive call *ex, because otherwise the grammar is ambiguous.
You're totally right, sorry! It's an important aspect of S-exps that I overlooked. I forgot that a typical Lisp file is not a valid S-expression, but a concatenation of a bunch of them. Plus maybe some whitespace/comments prepended.
So an S-expression syntax, as normally defined, is not closed under concatenation like Jevko.
To solve that (assuming it's a desirable feature as I do) purely syntactically, without talking about the REPL, you'd need another top-level syntax.
So why not simplify things and make one that meets this criterion by itself?
Which makes me think of another aspect where Jevko is simpler.
The restrictions Jevko puts on a unicode sequence are that the escape character must be followed by itself or a square bracket and that unescaped square brackets must be balanced.
This is pretty much an exhaustive one-sentence description that would allow you to validate or generate a Jevko.
A similarly simple description is impossible to state for S-expressions.
I tried and I came up with (for your minimal defnition of S-exp):
The restrictions S-expr puts on a unicode sequence are that it must conform to one of three alternatives:
* it must be wrapped in parens (list),
* it must be wrapped in quotes (string),
* it must not include whitespace or parens (symbol).
Also:
* If it's a list then different parts of the sequence may conform to one of these three alternatives.
* If it's a string then anything goes, provided that quote is escaped.
I don't think this is exhaustive and certainly not as clear and simple as the Jevko version. Can you come up with a simpler description?
> If you want to allow binary strings you'd probably want to define the language over bytes rather than Unicode code points, though Markus Kuhn's UTF-8B (implemented in Python as "surrogateescape") can give you the best of both worlds.
Yeah, I don't know why I thought your syntax allows binary strings. Clearly, I was confused.
Thanks for the reference, saved.
> Yes, I agree that "S-expression" is rather vague, much like "CSV".
This is an issue I want to avoid with Jevko.
The best syntax in this regard is JSON, with a relatively clear and concise specification. It does have some holes which cause problems, but I don't know anything better.
I'd like Jevko to be better.
> If you disallow having anything other than whitespace in a Jevko with >0 children, Jevko becomes a rose-tree notation, except that the root is unlabeled, so really it's more like a rose-forest notation.
Yes, depending on how you define these terms.
Important thing to note here again is that in accordance with how I intend Jevko to be used, you wouldn't be changing Jevko itself, but defining a format on top of Jevko[0].
The input of the parser/processor for this format is a Jevko syntax tree.
The output would be a rose tree. A nonblank suffix would be a (syntax) error in this format.
> If you want a rose-forest notation, you can get it in a less irregular way by declaring that Jevko infers an extra [] following a suffix containing any non-whitespace character, so foo[bar] is equivalent to foo[bar[]], foo[bar[]baz] is equivalent to foo[bar[]baz[]], and a[b]c is equivalent to a[b[]]c[], but foo[bar[] ] is equivalent to foo[bar[]] and not foo[bar[][]].
> This change would foreclose the possibility of having significant leading or trailing whitespace in some places but not others, the way I was suggesting.
Sure, you could also define a format that works like this.
Input a Jevko tree and output another tree with these extra subtrees "inferred".
The point is that you don't modify Jevko, but use it as a building block.
> Rose trees or rose forests are definitely simpler than Jevko's current data model, and they are equally powerful.
I think defining Jevko in terms of rose trees wouldn't be as straightforward as the inverse, so I disagree. But I wouldn't want to argue about this. I say go with whatever is simpler/more powerful/works for you.
I'd like to put this somewhere on a Jevko-related page(s), giving credit to you, linking to http://canonical.org/~kragen/.
If you prefer a different way of attribution or none at all, please let me know here or send me a gmail at darius.j.chuck
> For the diagrams I've taken the liberty of ignoring leading and trailing whitespace on arc labels (prefixes), as well as suffixes consisting only of whitespace. johnsmith and horse are your examples, but they just use Jevko as a terser syntax for JSON that suffers a whitespace problem.
Makes sense. Trimming whitespace is what is usually wanted, except in markup formats.
Perhaps it would be sensible to devise a very thin format on top of Jevko for making diagrams of this kind. It would take care of the trimming and have explicitly attached the semantics you mentioned before as proposed a tagline for Jevko:
> A minimal Unicode syntax for ordered trees with labeled nodes and labeled arcs.
It could be used as a tagline for this format!
Did you generate these diagrams from Jevko or write them by hand?
A tool to autogenerate diagrams from this format could be a good application for it.
Anyway, just throwing out ideas. Now to implement them...
> player.jevko is an example I cooked up based on Minetest's relational database schema, recast as a hierarchical schema. It also takes advantage of the ordered nature of subJevkos, the possibility of multiple identical prefixes in the same parent node, and the possibility of having both "headers" (subJevkos) and a "body" (suffix) in the same node.
That's a really nice use of suffixes!
This is really awesome work, thanks for caring and putting in the time. I'd love to see more stuff like this, people making use of Jevko. That's what it's made for!
Cheers!
[0] Another important thing to state, which I suspect may be causing some confusion in our discussion is that Jevko by design has no semantics at all. You attach the semantics on the format layer above Jevko.
As for S-expressions, I agree that what I wrote above is a pretty minimal definition of S-expressions, but I still think it's valid as a definition of "S-expression", even though you'd use a modified definition in some environments. In particular, I think it successfully analyzes the structure of the S-expressions you use as examples. And I agree that it doesn't match the same strings as those modified versions; for example, it doesn't recognize $ as a symbol, or allow '.
The lexical syntax specified in R⁷RS §7.1.2 is, I think, a lot more complex than S-expressions, and it does not purport to define S-expressions; it includes Unicode, booleans, bytevectors, strings, piped symbols, vectors, circular references, quote, quasiquote, unquote, unquote-splicing, hexadecimal numbers, octal numbers, binary numbers, floating-point numbers, and so on. LISP 1.5 couldn't handle any of these, but I would be very uneasy with the assertion, "LISP 1.5 couldn't read S-expressions."
As an example of a more fleshed-out S-expression language, a few years ago when I wrote Ur-Scheme (a Scheme-subset compiler in the language it compiles), my S-expression parser supported lists (with optional dotted tails), quote, string literals, symbols, comments, signed decimal integers, booleans, and character literals. (Check out the section "Actual Parsing" in http://canonical.org/~kragen/sw/urscheme/compiler.scm.html.) This is evidently enough to conveniently write a compiler in, and I think some of it doesn't really belong to S-expressions per se — quote, comments, and booleans, for example.
One problem of my suggested data model is that, although the language is closed under concatenation (unlike, say, HTML, XML, JSON, or RFC-822), that concatenation is not semantics-preserving. Given these two Jevko documents:
concatenating them changes the label for [b] from "a" to "z\na", and perhaps more damningly, erases the whitespace before "z". But, since none of the alternative formats (except ndjson and I guess plain uninterpreted binary, ASCII, or Unicode) is closed under concatenation, maybe that's less important.I don't know if you saw the last time this topic came up I linked to https://ogdl.org/, which seems pretty close to a minimal rose-tree notation. They also put some thought into designing a query language for their rose-tree-like data model, which might be adaptable to Jevko — though they label only nodes, and Jevko labels both nodes (with suffixes) and arcs (with prefixes).
Maybe that's the subtitle for Jevko? "A minimal Unicode syntax for ordered trees with labeled nodes and labeled arcs." If that's the intended semantics it would be pretty easy to whip up a diagram in Dot to illustrate it.