Feedback requested: indentation sensitive grammars

[pdubroy]

As part of the upcoming Ohm v17 release, I've been working on a new feature — support for indentation-sensitive grammars. I'd love to get some feedback on what I've got so far.

You can try this out by installing the latest prerelease (npm install ohm-js@17.0.0-alpha.1). Below is some documentation to get you started. Any and all feedback is welcome!

Parsing indentation sensitive languages

As of v17, Ohm supports indentation-sensitive languages. This means that it's possible to write Ohm grammars for languages like Python and YAML.

Background

Ohm language is based on parsing expression grammars (PEGs), and pure PEGs can't express indentation sensitivity. The usual trick is to pre-process the input and insert explicit indent and dedent tokens, then parse the modified output. While this works, it has a few downsides:

• Error messages can be confusing, as they refer to the modified input rather than the original input
• You can't use the "real" syntax in the Ohm Editor — your examples inputs need to be pre-processed
• The preprocessing step is trickier than you might think!

For these reasons, we decided to add built-in support for indentation sensitive languages.

Making indentation-sensitive grammars

To define an indentation-sensitive language, create a grammar that inherits from IndentationSensitive. For example, here is a grammar for language support nested lists of bullet points:

import * as ohm from 'ohm-js';

const outline = ohm.grammar(
  String.raw`
    Outline <: IndentationSensitive {
      Items = Item+
      Item = "-" label indent Items dedent  -- withChildren
          | "-" label  -- leaf

      label = (~newline any)* eol

      eol = newline | end
      newline = "\r\n" | "\r" | "\n"
      spaces := (~newline space)*
    }
`,
  {IndentationSensitive: ohm.IndentationSensitive}
);

Implementation details

The indent and dedent rules are primitive rules defined by IndentationSensitive. You can think of them as special characters that automatically inserted at the appropriate points — except that they take up no width in the input stream. They are inserted immediately after the associated indentation characters at the beginning of the line. For example, here is some Python code, with comments indicating where the indents and dedents are inserted:

if col == 3:
  if row == 4: #   # <~~ indent at position 2 on this line
    print("bingo") # <~~ indent at position 4
  print("done")    # <~~ dedent at position 2

There is also final dedent at the end of the input.

Examples

See examples/indentation-sensitive for an example you can experiment with.

Notes and open questions

• The current implementation only works with spaces (not tabs). Among the indentation-sensitive languages (Python, YAML, Elm, etc.) there are small difference in what characters they allow and how they treat them. We probably want to make this customizable in some way.
• Should any be able to consume an indent or dedent?
  • On one hand, one would generally expect the expression any* to consume all of the remaining input. This wouldn't be true anymore if any failed on indent/dedent.
  • But, if it succeeds, what should it consume? Is it weird if any succeeds, but consumes no actual input characters?
  • Also, it seems like a grammar smell if you're using any to consume indent/dedent; you should probably consume those explicitly.

[joshmarinacci]

This looks really cool. Have you made a Python parser yet?

Are there any white space sensitive languages that use tabs over spaces? Aren't tabs usually implementation dependent?

[joakim]

I can't think of any. But I am considering requiring tabs for indentation (spaces for alignment) in a data notation format and programming language I'm working on. Indentation and alignment are semantically distinct in indentation-sensitive languages. It's possible to distinguish between the two, but having a distinct token for indentation does simplify things.

It's obviously a controversial choice, but I don't exactly expect mass adoption of my language either :)

Rationale

I think it just makes sense. Your keyboard has one key for space (ASCII char 20) and one key for indentation (ASCII char 9). ASCII char 9 exists for indentation (well, tabulation, but indentation when used in code). I think we should use it.

The best argument for tabs is accessibility. It's not about saving bytes, that's a strawman.

The argument that spaces are more popular is moot. Modern IDEs and programming languages seem to favour spaces (Go is an honorable exception), and people generally use whatever the project, language or IDE prescribes. Your IDE will emulate tabs if set to use spaces. So why not use tabs in the first place?

One issue that can arise is when people coming from spaces also use the tab key for alignment. The solution is to either have your IDE fix your mistake (a setting/formatter that automatically converts misused tabs into spaces), or learn to not make the mistake (use the tab key for indentation and spaces for alignment). If it helps, set your IDE to render whitespace as a visual aid.

End of rant!

[pdubroy]

Thanks Josh! I haven't made a Python parser yet, but plan to soon (there is a PEG grammar for Python 3 so it should be pretty straightforward).

Good question about tabs. I did a quick investigation when I kicked off this work, and here's what I found:

• Python2 & ReST - tab is converted to variable # of spaces (tab stops, mult of 8). Other whitespace treated as one space. (source)
• Python3 - "In Python 3, a tab is only equal to another tab"
  • The actual documentation seems a bit misleading, but I can see how it's consistent with the reading above.
• SASS - not allowed to mix tabs and spaces. Otherwise sounds similar to Python. (source)
• Elm - tab is an error
• Nim - spaces only (source)
• Coffeescript - looks like it just treats a tab like a space? (source)
• YAML: tabs forbidden

The only one I know of that uses tabs specifically is makefiles.

[joakim]

As a proponent of tabs (not religiously though, purely rational), I hope it will be possible to use tabs for indentation.

[pdubroy]

Thanks for the feedback! As I wrote above, "we probably want to make this customizable in some way". Before I release, I plan to add at least basic support for tabs (tabs-only, or Coffeescript-style where a tab is treated just like any other whitespace character).

Python will be the tricker one to support; I'll have to think about how to make that possible from userland.

[pdubroy]

@joshmarinacci Any thoughts on the question about whether any should consume an indent/dedent or not?

[pdubroy]

I'm leaning towards making any able to consume indent/dedent — it will just consume 0 chars of the actual input in that case. E.g. this.sourceString === '' inside the any semantic action.

[joshmarinacci]

yeah, I think any should consume indents and outdents.

[Efnilite]

See examples/indentation-sensitive for an example you can experiment with.

Is this example still available? I can't really figure out how the example in this post works, so having an example to experiment with will help a lot :)

[pdubroy]

@Efnilite Thanks for pointing this out — it's currently still on a branch: https://github.com/harc/ohm/tree/indentation-sensitive/examples/indentation-sensitive

[rtoal]

Initial thoughts from the write up (I'll get to trying it out in a couple days)

• Truly excellent idea to use Ohm's grammar inheritance mechanism to allow simply inheriting from IndentationSensitive to make this happen.
• Positioning the indent and dedent “special” tokens is definitely the way to go (there’s no other solution, really)
• Is one final dedent token at the end of the input enough? (I haven't tried yet but am wondering what happens if a program ends at a deeply nested level? Would it matter?)
• Regarding tabs, there are indentation-sensitive languages in which tabs are straight-up illegal. Elm is (or was?) one of those. Roc makes them illegal too. So does Zig. The Zig authors wrote “Maybe someday, we'll switch to tabs for indentation, spaces for alignment and make it a compile error if they are incorrectly mixed. But if we did that today, writing Zig code would be too hard. For now your options are to configure your editor to insert spaces when you press the tab key, or configure your editor run zig fmt on save (recommended).“ I think the problem is hard (or at least messy), and seriously, mixing tabs and spaces in one’s source code is just asking for trouble. But I see the need: we want people to use for any language, including those that are designed (unwisely) to allow its users to mix tabs and spaces in their source code. Ohm probably should be general-purpose enough to handle it, but in the meantime there is nothing wrong with an early version saying “not yet!”
• I would say (and this might be controversial!) let any consume indent and dedent but have Ohm give a very strong warning if it sees an any that is not prefixed with ~(indent|dedent) or equivalent. Just a thought!

[elviejo79]

On this excellent talk "The Post JavaScript Apocalypse" by Douglas Crockford (creator of json.org and author of "Javascript the good parts").

https://www.youtube.com/watch?v=NPB34lDZj3E

His main point is that in a well designed system it should be obvious how to do the right thing.
And to get rid of "clutter" in programming language.
What is clutter?
Things that as Marie Kondo would say "don't spark joy"

And thing that "don't spark joy" are the ones that lead to conflict.
he uses several examples, but for the purpose of this disscussion he proposes

• Tab vs Spaces :: Get ride of tabs there will be peace.
• camelCase vs snake_cas :: Neither we need to have identfiers that can be multiple words.

I think that he misses the mark.
If we are going to use "space" as a right associative operator to create identifiers to get ride of "camelCase".
Then we must keep TABS as the only mechanism to code indentation.

So my vote is for TABS for code nesting.

And also I recommend watching the talk.