Significant Whitespace

[liamoc]

So, this is more intended for discussing the potential implications of implementing significant whitespace.

You said on reddit:

If you want to help with significant whitespace, that would be great. The basics are working over on the whitespace branch with a lexer similar to the one you describe, with INDENT, OUTDENT, and "\n" tokens. The tricky case is the one I mentioned above:

elements.each(el =>
  el.click(event =>
    el.show() if e.active))

The two outer functions need to be closed before the closing parentheses and big OUTDENT occurs. I'm a bit at a loss for how to implement this in the grammar.

If you produced two outdent tokens, that would work. The way to do this is deceptively simple.

Currently, I assume your lexer has some idea of a current indentation level, and if this increases, then an INDENT is produced, if it decreases, an OUTDENT is produced, and otherwise a standard \n is produced.

The way to adapt it is to instead stop caring about indentation and start caring about alignment. This is how haskell does it to great success. Most of my examples in code will not be in ruby but a haskell-like, so hopefully you know haskell.

The way to implement it in your lexer is to have a stack of indentations. Looking at this example:

a
  b
  c
     d
         e
     f
g

This should be grouped like this:

a(b c(d(e)f))g

So, let's follow through with my stack indentation idea and see where that goes.

First we have a, it is at zero indentation level, so we lex that as usual. Next, we have an INDENT of two spaces, so we push 2 to the stack, then emit the indent token as per usual:

2:[] -- stack 
a INDENT

Then, we lex b. c isn't a INDENT or OUTDENT so the stack is unchanged and c is lexed as per usual.

2:[]
a INDENT b NEWLINE c

Then we have an indentation of 3 spaces, so we push 3 to the stack, and emit an indent token as per usual.

3:2:[] -- stack
a INDENT b NEWLINE c INDENT

Then, we have d, which we lex as per normal, then an indent of 4 spaces, so we emit an indent and add to the stack.

4:3:2:[] -- stack
a INDENT b NEWLINE c INDENT d INDENT

Finally, we lex e, and then we have the fun stuff. We first have an outdent of 4 spaces. If this outdent was anything less than 4, we'd throw an error. As it is, it is equal to 4, so that's fine. We subtract 4 from the top of the stack, and get zero.

 0:3:2:[] -- stack
a INDENT b NEWLINE c INDENT d INDENT e 

Then, we pop the zero off the stack, and emit an OUTDENT token. We also lex f as per usual.

3:2:[] --stack
a INDENT b NEWLINE c INDENT d INDENT e OUTDENT f

Finally we hit the major hurdle you were facing. We have an outdent of 5 spaces. So, we generalise the above algorithm and subtract 5 spaces from the whole stack, starting at the left:

0:0:[] -- stack
a INDENT b NEWLINE c INDENT d INDENT e OUTDENT f

Then, for each zero at the top of the stack, we emit an OUTDENT
[] -- stack
a INDENT b NEWLINE c INDENT d INDENT e OUTDENT f OUTDENT OUTDENT

Then, we lex g

a INDENT b NEWLINE c INDENT d INDENT e OUTDENT f OUTDENT OUTDENT g

Note, if i replace INDENT with ( and OUTDENT with ) and NEWLINE with a space, then you get:

 a(b c(d(e)f))g

Which is the exact grouping we wanted.

This way, you get exactly 1 OUTDENT token for every INDENT token. Hope this helps.

[jashkenas]

Thanks for the detailed overview. That was really quite helpful. I'm afraid that the case I mention above is still problematic. The (now two) outdents occur after the parentheses close, and need to be moved inward to make the inner functions compile. Do you have any suggestions for how to accomplish this reliably? There's a hacky rewrite_closing_parens method in the Lexer at the moment, but it isn't at all safe.

[liamoc]

Part of the problem is that you are trying to mix expression and statement grammar. Really, blocks accompany statements not expressions, and adding blocks to expressions is always going to be awkward, particularly with significant indentation.

In this case, there shouldn't be any real reason to pay attention to indentation at all. The lambda style notation you are using for functions feels like an expression, in that multi-line functions feel quite different. If you used separate syntax for function definition and a function expression (as python does) this would solve the problem, but I admit it feels sub-optimal. Really I think this problem should be solved with a better expression grammar that provides a post-fix way of expressing block arguments, eliminating the need to add brackets at the end. Lambda expressions could still be allowed but limited to a single line. (see the other ticket)

[jashkenas]

Right. That's the whole idea -- to get rid of statements to as large an extent as possible. Really, this is something that JavaScript already gets right with respect to functions. There is no difference between a function definition and a lambda expressions -- methods are just lambdas attached to objects, acquiring a "this".

I'm afraid that functions definitely need to be multiline-able. It would be way too much of a straitjacket if they were in some cases and not in others.

I'm still not convinced of the utility of postfix blocks -- they only seem needed in languages whose grammars can't handle a function definition as an argument. At the same time, they limit to you passing just a single function, and force it to be the final argument. The large amount of JavaScript libraries that already provide calls that take multiple functions as arguments mean that we would still have to offer the current alternative:

# API is ajax.request(url, data, on_success, on_failure)

ajax.request('/accounts/create', form_data, (json =>
  account: Accounts.create(json)
  ui.update(account)
.), error => Notifier.show_error(error.message).)

In order to justify a special syntax for an optional block style, blocks would need to be radically more convenient/simpler than just passing a function argument, and I don't think that's the case at the moment.

All of that aside, finding a way to rewrite trailing OUTDENTS to move them inward when a block series is closed abruptly would solve most of the current problems with the significant whitespace branch.

[liamoc]

if you lex your whole stream before you begin parsing, you could do something like this:

1. First check that the number of open parens is the same as the number of close parens, and that open parens occur always before close parens.
2. Then check that the number of indents is the same as the number of outdents, and that outdents only occur after indents.
3. Finally, apply a simple rule across the lexer stream like this:
   • If we see a LPAREN or INDENT, add it to the stack
   • If we see an RPAREN or DEDENT, pop the stack, and replace it with whatever you just popped.

So, for something like:

LPAREN LPAREN INDENT INDENT RPAREN RPAREN DEDENT DEDENT

We see that there are 2 lparens followed by 2 rparens - ok

We see that there are 2 indents folllowed by 2 outdents - ok

Now, we go through the stream, adding all indents and lparens to a stack

INDENT:INDENT:LPAREN:LPAREN:[] -- stack

Now, we hit an RPAREN, but that's not what we expect, so we change it to a DEDENT, and pop the stack:

LPAREN LPAREN INDENT INDENT DEDENT RPAREN DEDENT DEDENT -- stream
INDENT:LPAREN:LPAREN:[] -- stack

Now we apply a similar rule for subsequent tokens, getting

LPAREN LPAREN INDENT INDENT DEDENT DEDENT RPAREN RPAREN -- stream
[] -- stack

Which is what we want :D

Note that without those checks that I specified above, you could do something like:

INDENT RPAREN

and that would be valid, so make sure you do the checks first.

[weepy]

Here's an dog simple idea: how about a single empty newline closes any open blocks. It's a pretty easy rule to learn and the compactness of CS means that there's much less need to add empty newlines for readability.

[liamoc]

Then, how can you close one block but not another?

e.g

blah: a =>
    if a then
        c(d).
    else
        e().
    more_stuff.

With newlines, then that becomes:

blah: a =>
    if a then
        c(d)

    # oh no, all blocks are closed now =(

    else # error

[weepy]

I think you've moved on to wanting to use significant whitespace for closing single blocks. My idea was aimed at avoiding the common case of closing multiple blocks at the end, e.g.

grade: student =>
  if student.excellent_work
    "A+"
  else if student.okay_stuff
    if student.tried_hard then "B" else "B-".
  else
    "C"

As I said it was dog simple :-)

[liamoc]

This problem has already been resolved in a safer way, and is hence irrelevant.

[jashkenas]

kamatsu: Thanks for the algorithm for the stack-based rewriting. It's very clever, and works beautifully, having the effect that closing outdents and parens are interchangeable. There's still some more tweaks that need to be made to the significant whitespace grammar before it goes back to "master", but it's getting close.

[liamoc]

Good to hear!

[liamoc]

Oh, by the way, I know this might be an awful time to add this in, but could we have an alternative syntax in addition to significant whitespace? I think sometimes it can be awkward when generating code, so it'd be nice to be able to do like a one liner or something:

some_object: { x: 5, argXTimes: arg => { for i in [0..x] {alert(arg) } } } 

Syntax could vary, but it makes coffee easier to generate, which might be useful

[jashkenas]

We can consider it -- I don't think that CoffeeScript is ever going to be intended as a target for code generation -- seeing as how it doesn't even have a runtime of its own. But a vanilla version of your example compiles just fine on the "whitespace" branch right now.

some_object: {
  x: 5
  arg_x_times: arg => alert(arg) for i in [0..x]
}

Compiles into:

some_object = {
  x: 5,
  arg_x_times: function(arg) {
    var __a, __b, __c, __d, i;
    __c = [];
    for (__d=0, i=0, __b=x; (0 <= x ? i <= __b : i >= __b); (0 <= x ? i += 1 : i -= 1), __d++) {
      __c[__d] = alert(arg);
    }
    return __c;
  }
};

[liamoc]

Ah, good point, I suppose you can just generate JS if you're generating stuff.

[jashkenas]

There's one little issue left with the whitespace, and I was wondering if you have any ideas. Take this example:

if true
  something()
a: 1

The token stream includes an outdent which closes the if statement, but because there's no newline before the assignment, it fails to parse the if and the assignment as two separate expressions. Adding a newline fixes the error, but I'd like to support this case. We can't just add newline tokens after every outdent, because outdents don't always mark the end of an expression (imagine a longer if/else chain), just in certain cases like the above.

[liamoc]

Oh, also, I realised my paren rewriting is merely a specific case of another problem:

# API is ajax.request(url, data, on_success, on_failure)

ajax.request('/accounts/create', form_data, (json =>
  account: Accounts.create(json)
  ui.update(account)), error => Notifier.show_error(error.message))

We would probably want this to compile. Hm.