Sapling notation

[mflatt]

Continued from #117, which accidentally became marked as merged.

[mflatt]

I tried writing the sapling demo with just => and | (so, no special = or : or & as line starters or enders), and I think it's probably a step forward:

https://gist.github.com/mflatt/a390b5cfc35c4ae80562f4ae0cd42212

But it still doesn't work very well for for or something analogous to letrec-syntaxes+values. Maybe it needs one more kind of continuing/grouping.

[gus-massa]

What about ? and ! at the end of identifiers. I'd really miss list? and vector?. (I don't like the trailing P in Mathematica, but something like IsList is not so bad.)

[mflatt]

Opinions will certainly vary, but I'd like to stop having to explain how identifiers in my favorite language have an usual syntax. So, for me, no ? or ! in identifiers. I also prefer is_list over listP. (I've generally used underscores instead of camelcase, because they seem closer to hyphens.)

[mflatt]

I've pushed a revised proposal. It doubles down on => (always spelled that way), drops special treatment of = and &, and changes : to be a new and simple kind of line-starter that doesn't initiate any subgroups.

As a kind of special case that seems to fit nicely with everything else, any operator can continue a group when used as a line-starter, as long as the group is an immediate subgroup of (...). That way, (x + y) can be broken across lines by starting with + on the second line.

[jeapostrophe]

I have a lot of thoughts about this proposal, because I've been thinking about this for so long and so much lately. It's really impossible for me to comment without reference to my recent Lexpr proposal, so I'll just bite the bullet on that and overtly compare them.

I'm writing this from the assumption that there are good ideas in both and we'll slowly spin around these and other ideas until we find something amazing.

Organizing principle: I find your section, "grouping overview" to be very confusing. I think that what appeals to me about Sexprs is that there is a really simple set of rules, "Groups are created by matched parens. Atoms are separated by spaces. There are a few different ways to write atoms." In my proposed designed, I've tried to come up with another very small set of rules and principles that lead to a syntax with more notation and categories, but the same uniformity. For example, Cexprs are something like, "Bodies are made of statements separated by semicolons. Statements are made of expressions separated by spaces. Expressions have a few different ways to write them, such as dotted sequences and embedded groups where () embed expressions, [] embed statements, and {} embed bodies." For Lexprs, it is something like "The line is the unit of discourse. A line is always on one textual line and its final character can influence how the next line is parsed."

I don't understand what the unifying principle of Sapling is. (I recognize that I'm assuming there should be one, which you may disagree with.) It doesn't have the rule that the previous line always controls the parsing of the next. It doesn't have the rule that the start of a line always controls how this line attaches to the previous line. It doesn't say that ()-group contents are always delimited by ,, just that that's "common". My mind is probably warped by my own proposals and expectations.

Another way of looking at it is based on the parsers. I feel like people try to internalize the parser of their language. A parser could be complex by being "deep" (having too many layers where the rules are different), being "wide" (having too many cases in a layer), or being "stateful" (where there is a lot of context sensitivity in parsing.) I think that C++ is perceived as confusing because it is deep and wide. I think that people who find Haskell confusing are picking up on the context-sensitive nature of indentation (because indentation is not ALWAYS attached to a token like : in Python, but also comes from do, where, let, and so on.)

Sexprs are not deep: They have a list level and an atom level. They don't feel wide: the list level has one case, and although the Racket atom level has 16,000 cases, it feels like there are just a few. They are not stateful at all.

I tried to follow that principle with Cexprs/Lexprs. With Cexprs, I basically just said, let's make the list level have a small number of extra cases. With Lexprs, I made it a little deeper (line, group, unit, atom) but each level is not very wide (most have six options) and there is only one kind of state, which is the what expectation the next line has to follow if it is going to be included in the previous line.

In contrast, I feel like Sapling is very shallow, moderately wide, and highly stateful. From the code perspective, I think this is reflected by the 15 keywords to next (state), the lack of different recursive consuming functions (shallow), and 11 cases (not very wide).

Binding sensitive grouping: Sapling doesn't specify an infix system and the group that it does provide is loose enough, that I think it is necessary for extra enforestation to be provided by the next layer. Lexprs could work like this by removing the infix rules, dropping the specialness of ,, and maybe by removing the lists created by things like |.

I think you know this, but I personally do not like binding-sensitive grouping. As for why, I think my explanation are isomorphic to the complaints that norms have about macros in general. They say stuff like, "It is hard enough to understand other people's functions; with macros, when I look at their code, there are no rules!" I think bindings influencing where groups are created is likely to be very confusing and hard to get right. I am worried about the situation where you can't figure out where an inner group starts & stops inside a bigger group without looking at the implementation of the outer group. An analogous problem is how with existing Racket macros, if you see (f (+ 1 2)), you cannot really know that it is the same as (f 3) because f might be a macro that inspects its argument is does something strange with it. I feel like grouping is something fundamental that the language needs to pin down. However, I don't think this is an objectively determinable point; although it is definitely more powerful to do it the Honu way, I don't think that more power is also better (e.g. assembly.)

Bikeshedding on =>: I don't find => to be suggestive of "the things that are after this are inside it" the way you do. ML pattern matching blocks are structured like that, but in them the thing on the left binds information that goes into the context of the thing on the right, so the right is "inside" because it is the body of a let. In your examples, => is used to bind things. I find this to be very strange and it looks alien to me. In contrast, I think that Lexpr's : is suggestive of containing because that's how you often refer in prose to a list or quotation that follows. (I know that you previously had arbitrary "arrows" which would have solved this problem, but I vastly prefer having just one way of writing things.)

Identifier syntax: You are clear that you want 1+1 to be the same as (1 + 1) and presumably a-b to be the same as (a - b). I think that a syntax proposal needs to explain how a Racket2 program can refer to drracket:language:simple-module-based-language->module-based-language-mixin. I agree that people often write a+1 when they mean a + 1, but all of our proposals put extra restrictions on the way to write things; for example, mathematicians invent new opener-closer pairs as is convenient and are not rigorous about writing f(a, b) versus f (a, b) (i.e. sometimes there are spaces and sometimes not.) I think that our heritage has exciting identifier names and we'll be hosed if it is too inconvenient to use Greg Hendershott's AWS library function, multipart-put/file.

*Bikeshedding on keywords:: I think your keyword encoding is strange. I think that keywords as an atom type are a by-product of Racket1's limited notation and in Racket2, we'll communicate keywords via a different syntax on function application/definition. I don't see value in having a way to write down the keyword atom in the syntax rather than mandating string->keyword when talking about them meta.

Quotations: I think you need to explain how macros can talk about the structure of what they expect to see in their syntax at a meta-level. In Lexprs, there is traditional ' quotation for expressions, as well as a new kind of quotation with []s to quote lines (the new unit in Lexprs). This is key for line macros because they need to specify what kinds of lines they expect to see.

Text: All of my proposals have included built-in support for an @-style reader. I think that @ is one of the best things we've discovered in Racket and we should be using it more. I believe that you don't think this is necessary because you think that with binding-sensitive grouping, you can write enough macros that allow the body of the macro to look like anything.

Different kinds of applications: In C++ and Java, there are different meanings for things that look like application: new List<Int>, m[1, 2], and f(a, b). I think it is useful to have something like that. Part of my mindset for our new syntax is to add the ability of macro authors to prescribe certain syntactic shapes so they can put more information in the notation.

[gus-massa]

Perhaps the discussion about identifier syntax can be moved to it's own issue. I think it's possible to reach a 99% agreement on that, independent of the rest of the syntax. (There are some details like the character for comments, how to escape, ... that must be revised later, but most of it should be independent.) I think ineroperability in both ways and the ability to use the current (and future) libraries (in both ways) is important.

Perhaps add another issue for numbers. Numbers in racket are weird. For example this monstrosity #e#x+e#s+e-e#l-e was a number until 7.3 (attributed to @elibarzilay ). Moreover, perhaps it's better to extend the definition of numbers. It is weird that 1+2i and 1/2 are numbers but 1+2 is a symbol. (If anyone is using 1+2 in the current version of rackek s/he deserve to get an incompatibility problem.)

[gus-massa]

Lina 114 is

define make_adder(n) =

Is that a typo / leftover of the previous versions?

Why the space after lambda? Can't #%call just do the right thing when the function is a special form or a macro? This can be a problem for macros that pretend to be functions, for example the functions with keywords.

[jeapostrophe]

@gus-massa I agree that Racket numbers are really weird and we should drastically pare them down.

[gus-massa]

I proposed to pare them up :), but a good reduction may be even better.

[mflatt]

A simpler number syntax is probably something we all agree on!

[otherjoel]

I'm just a plebe, but I want to say I really like being able to use -, ?, *. + and / in identifiers, and the conventions built up around their use in existing Racket. I’ve found it makes it much easier to name things well (one of the famous two hard problems), and to grok the use of newly encountered functions/macros. If we can’t do so in the new language I will be sad.

[mflatt]

@jeapostrophe Thank you for your thoughts!

Organizing principle: I don't think the notation is as complex or stateful as you suggest. The next function has 15 arguments because it's an indenter that I hacked to double as a parser, and I didn't know what I was trying to write for either job when I started. Meanwhile, it sounds like the prose explanation should be a lot better; sorry about that, and I can try again if it seems worthwhile.

I've now pushed a separate parser. It's still deeper than S-expressions and more shallow than Lexprs, because it has 3 levels: group sequence, nested group sequence, and group (as reflected in the parser by three functions). It's a little narrower than Lexprs, as you say. And it's only a little more stateful, with up to 4 pieces of state: the current group's line number, whether we're immediately in parentheses/brackets, whether we've seen a |, and which closer we expect. (To be clear for those who aren't reading read the code of the various parsers, this is "state" in the sense of arguments threaded through.)

Binding sensitive grouping: Yes, I agree that Lexprs versus saplings conflates the group-by-lexeme versus group-by-binding choice with other choices. There's a nearby design point to either by flipping that choice.

I remain interested in grouping-by-binding, in part, because it seems like good support is necessary to acommodate the notations in use by other languages. Racket experience won't be convincing to other communities if we don't try live with those kind of parsing issue. But my personal preference is a little more grouping-by-parsing, just like my personal preference is often a little more macros, so maybe that motivates my reasoning about research transfer.

At the same time, there's a lot to be said for grouping-by-lexeme, both for understanding code and manipulating code, especially in proportion to the amount of code involved. For those reasons taken together, I find the hybrid approach attractive. There's still a risk that even sapling-level grouping is too much to make our results compelling to other language communities, but I'm hopeful that it can point the way to flexible sublanguages, freeing macro systems from the the AST-as-intermediate design that some have adopted.

Bikeshedding on arrow: I have no strong attachment to =>. In the interest of minimality, it was a symbol that worked well enough for me, but maybe there's a better all-purpose symbol, or maybe a little variety is a good idea here.

Identifier syntax: As @gus-massa says, this seems important but mostly orthogonal to everything else. For C-like variable names, interoperability is certainly a concern, and I agree that a full proposal would need to address the problem of keeping or converting existing names.

Bikeshedding on keyword: I'm uncertain about the role of keywords, and I agree that they may be a holdover here from thinking in Racket notation.

Quotations: I don't understand this comment. The quote of a sapling can be be the syntax object that parse produces, the same as with S-expressions or Lexprs. Exactly which operators act as quote and unquote can be up to the language that uses sapling notation.

Text: Adding @-notation makes sense to me. In the interest of supporting conventional notation, I don't think we should throw out " strings, but add @ too.

Different kinds of applications: I've backed off the idea that function calls are distinguished from other kinds of adjacent things. In the interest of not imposing spacing constraints unnecessarily, I'm now inclined to leave it to convention that a space is omitted when you mean a function call—which is an improvement over #lang racket, where there's no difference even by convention. But I could still go either way. I would apply the apply the same reasoning to square brackets and angle brackets.

@gus-massa: This is why I put a space after lambda: because it's not a function. But in a notation that distinguishes function calls from other forms, the question of whether a binding is implemented as a macro seems orthogonal to whether it is used in a function position or not.

[sorawee]

This is why I put a space after lambda: because it's not a function. But in a notation that distinguishes function calls from other forms, the question of whether a binding is implemented as a macro seems orthogonal to whether it is used in a function position or not.

Having a single whitespace to determine semantics (function call vs macro invocation) seems really brittle IMO. I would prefer using different kind of paren shape (function call uses parens, macro invocation uses brackets) or something like that.

On the bigger picture, I feel there are two opposing forces. One is, it should be clear from the code which is macro invocation and which is function application, as @jeapostrophe mentioned above:

if you see (f (+ 1 2)), you cannot really know that it is the same as (f 3) because f might be a macro that inspects its argument is does something strange with it.

And on the other hand, we have a desire to make it possible to imitate function calls with macro invocations, as @gus-massa mentioned above.

How do we resolve them?

[cloudhan]

@sorawee I suggest use angle bracket. Potentially unify the generic syntax in other language...

[mflatt]

@sorawee I think you are confusing terminology with "function" versus "macro". For example, is dict-ref a function or a macro? It's both. It's a macro, because it has a contract and that's how contracts are implemented, but it's a function because the value of dict-ref in any expression position is a function. So, I think you mean "function" versus "syntactic form".

To whatever degree the notation distinguishes among function calls, infix operations, and other syntactic forms, any of those should be able to trigger macros — and that's straightforward. I hope this explains why I don't see any conflict to resolve.

[jeapostrophe]

Parser: I understand the parser a lot better now; thanks. I think a prose explanation that followed the parser could help me, but maybe not others. Or that demonstrated the special cases and rules with little one-off examples.

Binding sensitive grouping: You mention being compelling to other language communities a few times. Personally, I don't really care about their opinions, but I want to take what I personally like from their notations are try to apply it. I like the observation of Haskell and Python that programmers "see" indentation. I like the observation of C and Java that normal math notation is great for most programs. I like the observation of C++ that different kinds of brackets are very useful. I like the observation of Shells and (IMHO) C/C++ that keywords attach to each other without any notation except for spaces.

When I think about grouping-by-binding, I don't really see that in other languages in well-formatted code. For example, in C, I don't feel like ifs are used this way. Yes, technically the if gets to consume one statement and maybe an else and another statement, but I feel like most C linters and coding standards warn programmers about writing code that doesn't rigorously following a formatting standard like "Always indent the bodies and use braces; if you indent but don't use braces, you're a monster." In other words,

if (e)
  s1
else
  s2;
  s3;

is immoral and dangerous, so we should always try to write

if (e) {
  s1
} else {
  s2;
  s3;
}

even though it makes us write

if (e) {
  s1
} else {
  s2;
}

sometimes.

Bikeshedding on arrow: I think : is the thing that makes sense at the end of the line and & makes sense at the beginning, with \ to extend and | as an aligner.

Quotations: Since Sapling groups may be undelimited, how do you refer to an undelimited group in a quoting context? Is it that because parens are invisible '(a b c) is the same as the undelimited a b c?

Macros: @sorawee I was not saying that we should be able to tell macro invocations and function calls apart. I was saying the opposite. In Racket, you cannot tell the difference and this is a complaint people often make because you can't perform substitution on Racket programs because (f (+ 1 2)) might not be the same as (f 3). They think macros are terrible because they think you can't reason about your program without understanding the implementation of every library you import. I am saying that this is the way that I feel about grouping-by-binding, because I don't want to have to understand the implementation of every import to understand how to group my code. I feel this way for my own sake and for editors'.

[jackfirth]

I feel like most C linters and coding standards warn programmers about writing code that doesn't rigorously following a formatting standard like "Always indent the bodies and use braces; if you indent but don't use braces, you're a monster."

@jeapostrophe Would it help if we put together a list of well-known style guides, linters, and autoformatters used in other languages?

[mflatt]

@jeapostrophe

Binding sensitive grouping: The if form is grouping-by-lexeme in C only because if is considered a special lexeme in the same sense as { or ;. Nothing else groups the if with its one-to-three parts, and simply requiring curly braces around the "then" and "else" parts doesn't change that. We've seen where the if-as-special-token design can lead, which is to a language that may support some extension, but not the ability to introduce syntax with the same status as built-in forms.

(I accept that you don't care about other languages. I just object to the suggestion that adding curly braces alone would solve the problem.)

Bikeshedding on arrow: I'm not sure how you have in mind dealing with =>-like things that I wrote at the start or middle or lines. I'm guessing that you would change the line breaks. Are you interested in this direction enough to demonstrate what you mean with a revision of "demo.sap"? (You might instead mean the suggestion as a prelude to "and, also, use indentation sensitivity", which is certainly fair.)

Quotations: Curly braces are the silent ones in the current implementation — so, yes, but with curly braces in place of parentheses.

[jeapostrophe]

@mflatt I think we are talking past each other and we might mean different things by "grouping-by-binding."

My point about if is that I imagine in a "grouping-by-binding" world we want to allow patterns like a C-style if to emerge out of the binding of if. In other words, there would be a stream like if e s1 else s2 s3 s4 and you would be able to get it to enforest to (if e s1 (begin s2 s3)) or (if e s1 s2) or (if e s1 (begin s2 s3 s4)) depending on how if is implemented.

When I read you write, "I remain interested in grouping-by-binding, in part, because it seems like good support is necessary to acommodate the notations in use by other languages", this is what I think you mean. You want someone to be able to write an if macro in Racket2 that can decide what among s2 s3 s4 are part of it and the only way I can find out is by reading the implementation. If I am nervous, which I am, then I will be putting {}s everywhere because I won't trust the macros. At that point, I feel like I am back in Sexpr world, except there are complicated macros and extra words everywhere.

[mflatt]

@jeapostrophe We're using "grouping-by-binding" in the same way. Otherwise, I guess we are talking past teach other, but I'm pretty sure I understand the arguments in favor of grouping-by-lexeme (even though I'm inclined toward a different trade-off).

[gus-massa]

Some proposal for modifying the proposal. (Sorry if I asked to move in the opposite direction a few days ago. I'll change my mind again in a few days anyway :).)

• I'd like to keep the | as a magic character for case and match. But I'd like the & as a magical character for let and for. [I'm worried about for/fold that is weird.]

• I'd like to keep the parenthesis only for applications like f(1, 2) and functions definitions with the "MIT" notation like define f(x, y):. [I'm not sure about the lambda (x, y). I'm not sure about named lets. [I like named lets.]]

• I'd like to replace some of the => with the pythonic :. Keep the => when there is a binding like in let and for, but use : every time the expression has a body ... part. (But allow the body to be in the same line.)

Something like:

define pi => 3.14

define mul(a, b):
  a * b

define div(a, b): a / b

define norm =>
  lambda (x, y):
    sqrt((x * x) + (y * y))

let & x => read()
    & y => something():
  display(x + y)
  newline()

for & x => in-range(10, 20)
    & y => in-list(iota(10)):
  diplay(list(x, y))
  sleep(1)

[mflatt]

@gus-massa I tried adopting your suggestions, but I ended up at an intermediate point:

• The proposal now uses : everywhere in place of => and & in place of the old :. Those operators do seem to work better (although this & isn't the use you suggested). For now, the proposal still allows : at the start of a line to continue the previous line, but it would make sense to remove that (more choice for a programmer vs. consistency and slightly more complex parser to rule out line-starting :).

• The examples still use = for binding like non-function-shortcut define and let clauses. I think Jay's right that => doesn't work there.

• The examples still use parentheses for lambda, because I like the arguments to lambda specified the same way as arguments in the function-shorthand form.

• Since parentheses are used for grouping bindings as function arguments, then it still seems natural to me to use them for bindings in let and for. I think I see where you're going with the suggestion to use &, but making that work would add an extra layer of grouping precedence. Also, parentheses help with the colon at the end of the let bindings, at least to me. And it does work nicely with named let.

[jeapostrophe]

It is a lot more beautiful to me than before. I put a lot of value on the uniformity and I would go without the line-starting : rule.

I think you should add something like @ expressions.

I accidentally started a review rather than just making a comment, sorry.

[mflatt]

The latest revision :

• Removes a line-starting : as a way to continue the previous line's group.

• Makes & behave like @gus-massa's suggestion. That change introduces more "precedence" in grouping operators, but it seems to be a good tradeoff.

• Doesn't add @ to the prototype implementation, but mentions in the Alternatives section that at-expressions should be included.

• Replaces the indenter implementation.

[gus-massa]

Some random comments:

In the Guide-level explanation add "Indentation is not meaningful for grouping." just in case someone (i.e. me) has a doubt about it.

Blank lines as a very meaningful separation token is unusual. Let's see how it works.

Can I write this?

display(f(very-long-argument,
          another-long-argument))

Can the association of () and [] to , and the association of {} to ; be mandatory? (I'm not sure if the current option or the restricted option is more useful than the other.)

Typos in 0005-sapling.md, line 167 and 175, and in demo.sap line 195 and 204.

I hope this is illegal without additional parenthesis:

 cond x
 | number?(x): if (x = 0)
               | "zero"
               | "non-zero"
 | else: "other"

Are the parenthesis around the test part of the if mandatory? (I think no, but all the examples have them and IIRC they are mandatory in C.)

[gus-massa]

Why () and [] must be different than {}?

Is it possible to write curly function applications like

f{1, 2}

and curved functions definitions like

define f{x}: (
  x * x
)

I think that for the final language it is better to be more strict and force the correct use of () and {}, but perhaps the first parsing pass can be more generic. (Again, I'm not sure what is better.)

[mflatt]

@gus-massa

Yes, you can write the example with long arguments.

For associating , to () and [] versus ; to {}, my guideline has been to impose constraints only as necessary for indentation or grouping. Since associating , to (), etc., doesn't seem useful for that goal, I've left it as a choice up to a language that is written in sapling notation. That's just a guideline, though, and I don't have a strong opinion. Still, I can imagine that a language might want ; with [] — which again suggests that making ; and {} silent is a bad idea, and since I'm more and more convinced if that, I'll go change it in the proposal.

Yes, parentheses are needed in that example, assuming that you mean the obvious thing. If you paste the code into stdin for racket indent.rkt (and hit Ctl-d or Ctl-z), it reformats as

cond x
| number?(x): if (x = 0)
| "zero"
| "non-zero"
| else: "other"

which I would say accurately reflects the parse. Whether parentheses are needed for (x = 0) is up to the language that defines if, but sapling notation doesn't require it. I don't think I'd require them in a sapling-based language, but that goes back to the at-least-some-grouping-by-binding idea.

Unlike the original sapling proposal, the use of () for function calls is not built into the current proposal. A language that uses sapling notation might use or allow {} for function calls.

The current proposal+prototype treats { a little differently than ( and [ for indentation, and maybe that's a bad idea. I'll look at making them all behave like { does, and then your last example would indent as you wrote it.

[gus-massa]

Feature request: Make DrRacket complain when the indentation is wrong. (I prefer the version where there appears a color mark in one side of the line, not the version that opens a modal message box.)

Feature request II: Make it optional, because it may be annoying :). Perhaps with some modes like "strict"/"something"/"disabled".

Now I'm understanding why the parenthesis around the test conditions are necessary most of the time. I'll try to think if they can be removed using some rule that makes sense.

IIUC an exception is when the test condition is just an identifier (or constant), for example in

define show(value, nl?):
  display(value)
  if nl?
  | newline
  | void

[mflatt]

@gus-massa I very much agree about having DrRacket highlight incorrect indentation and having levels of strictness on indentation at the reader level.

I'm not sure what you mean about parentheses around test conditions. In case it helps, I've removed parentheses form "demo.sap" where I think they shouldn't be necessary (and where they definitely aren't necessary at the sapling-notation level).

[gus-massa]

The problem is if the new-if macro is will eat one or three things before the |.

In an imaginary implementation, where it is not necessary to escape the |:

(define-magical-syntax-rule (new-if test | then ... | else ...)
  (if test (begin then ...) (begin else ...)))

or

(define-magical-syntax-rule (new-if test ... | then ... | else ...)
  (if (infix-expression test ...) (begin then ...) (begin else ...)))

or

(define-magical-syntax-rule (new-if x f y | then ... | else ...)
  (if (apply f (list x y 42)) (begin then ...) (begin else ...)))

The spirit in racket/scheme/lisp/clojure is to trust the writer of the macro not to write something like the third version. Stupid macros are possible, and there is only a layer of trust as protection.

The second is more nice, an it doesn't need parenthesis. The if will eat everything until the next | (or raise an error in case there is a blank line before the |). Is it possible to write all build-in macros / special forms like this, and make this style the recommended style? [Note: I like the parenthesis around the argument list of a lambda. The recommended style must have a few cases.]

In the fist, the test must be a single expression, so it needs parenthesis. A macro can use magical-syntax-case/parse to peek into the parenthesis and do weird things. (For example, like the current version of for with in-range.) But we trust the macro writers.