Hacker News Reader

Comment by afavour | Hacker News Reader

I do kind of love the idea of Git using ASTs instead of source code. It makes a ton of sense.

Even just in the immediate term I wish I could make Git(hub) tabs/2 spaces/4 spaces/whatever agnostic. Seems crazy to me that in 2021 we still have to make opinionated choices across orgs about what to use... why can't we pull the code down, view it in whatever setup we want, then commit a normalized version?

[whispers] this is actually something tabs allow you to do natively by setting custom tab widths in text editors but I've given up trying to sell people on tabs at this point and just want to be able to do my own thing

View on HN

It's not that you're going too far, it's that you're not going far enough!

It's not a Git question, it's a programming language question. There's no reason source code need to be stored as plain text[1]! Editors show it as text, we edit it as text, but why wouldn't it be _stored_ as an AST? Not only does formatting becomes an editor concern, but code could even be edited as a tree, as a graph, as whatever you want

[1] - well, actually there's plenty of reasons: chiefly because plaintext is very interoperable

"but why wouldn't it be _stored_ as an AST?"

It profoundly is. You can't store "an AST". You can only store a serialization of it. The official language grammar is a serialization of the AST custom crafted for that language. It is as much an "AST" as any other serialization would be; all such alternative representations would all produce isomorphic memory representations if parsed from a proper library.

At a high level it may sound useful to try to then provide a cross-language AST representation, but it's one of those things that sounds great at a high level but as soon as you actually tried to implement it for, say, Python and C++, you'd rapidly discover that in practice there's not as much opportunity for "generic AST operations" as you may think.

The problem isn't that it isn't "stored as an AST" but that $YOUR_LANGUAGE apparently doesn't have good libraries or mechanisms for getting at it. Go, for instance, ships with the relevant bits of the compiler exposed, and as a result there are tons of tools that operate on Go code as ASTs and not textually, because it's readily available and supported by the core language team. I use this only as an example I know personally, there are other languages that have similar sorts of support as well.

I feel like you're picking a strawman here. The AST serialization everyone is implying is one where you don't need to token/lex but can just load it directly & manipulate it (i.e. implying the on-disk version is a valid AST or one who's validity can be trivially validated without needing to have the entire language syntax & grammar). First, that makes the compiler much faster because tokenization/lexing is moved to the "save" phase which happens infrequently at human scale vs the compile/processing phase which happens in an automated fashion where the overhead can be notable. Additionally, if you mmap the AST from disk into memory, you can use finer-grained caching to memoize expensive analysis that happens for faster compiles of code that's only changed slightly (e.g. changing whitespace/comments wouldn't recompile anything).

More importantly for advocates, it avoids needing to ship the deserialization library and makes tooling simpler. That's really why the idea of a simple AST format is so attractive. Typically compiler frontends are typically very tightly coupled to the underlying middle & back end. There's some work in some languages to decouple this (e.g. LSPs & Idea's failable parsing approach), but the efforts are still very immature & it's still not clear to me that it's worth it (see the last paragraph).

The main underlying challenge with making sure the on-disk contents is well-formed according to the syntax rules is that frequently you want to pause work at an intermediate stage. This means you either have to make sure that whatever state the user saves is a valid AST via editor tricks (although I think this also typically means you have to design the language around it), you reject saves, every tooling library has to be capable of parsing malformed ASTs, or you save a dirty transformation to apply to the last known saved version so you can have the user resume editing but otherwise tooling uses the "last known good" version. That's the real challenge with having a serialized version that's amenable to 3p tooling for interop.

Finally, all the "serialize the AST" solutions ignore the problem of wanting to grep the codebase. This means you need to change out several decades of line-oriented manipulation tools in favor of new ones that are AST-based & likely more complicated to write/maintain as compared with one-line regular expressions. At least I've yet to see any AST manipulation libraries that aren't drastically different from existing text manipulation tools if clang-tidy and Rust macros are any indication about what good solutions to the problem look like today.

I think eventually we'll get AST serialization, but I think it will be packaged into an entirely new language (like Rust did with ownership) that also considers the tooling aspect end-to-end rather than as a retrofit into existing languages. Once that's successful, then I think we'll see retrofits because the space will have been better explored & other languages will benefit from the R&D into what a successful path would look like.

> that makes the compiler much faster because tokenization/lexing is moved to the "save" phase which happens infrequently at human scale

For dynamic languages like Ruby or Python, storing a pre-parsed representation makes it a little faster. But for compiled languages, lexing and parsing tend to be swamped by the codegen step

If you think about it more broadly where you can memoize expensive results of AST -> code gen transformation or AST -> AST simplification, then this will help significantly for codegen, especially for incremental builds but also clean builds if you have your CI cluster sharing build cache information with your local devs.

Also, for a language like Rust, I'm not sure that there isn't a significant amount of time spent validating ownership & doing type inference. These are the kinds of analysis you could save into the AST & thus save a significant amount of build time when talking about large projects. I agree for smaller projects a lot of these optimizations are probably unimportant.

For rust in particular, there is just such an intermediate representation called MIR that has desugared AST, control flow graph, type inference and lifetime information baked into it so it can be reused to speed up incremental builds.

But that's pretty far from what the programmer wants to interact with. In the context of the thread where we're discussing whether the source code is just a serialized version of the AST.

(Also, with Rust, type checking and borrow checking are expensive, but codegen still dominates)

Yup. I’m not claiming anyone has successfully applied the general concept of memoizing expensive compiler operations at the AST level. There’s all sorts of practical complexities that come up with such a design but conceptually I think it should be doable. Using your “the text is the serialized AST” argument, we see primitive tools around this concept that operate just on the text contents and codegen end-result with ccache/sccache/bazel/etc.

However, using a richer AST representation and knowledge about what expensive operations the compiler performs should let you retain cache acceleration even when the high-level text->compiled code fails. Heck, one could imagine that some AST processing could end up being agnostic to a codebase so that the compiler ends up memoizing certain results across all code bases since code is very similar and have similar constructs that should generate very case similarly.

I think everyone may be interested in: https://github.com/afnanenayet/diffsitter

Github having an option to have their PR GUI use an AST diff like this could be a fun and useful option.

> This means you need to change out several decades of line-oriented manipulation tools in favor of new ones that are AST-based

I wonder if a generic binary->text tool/library could solve this. Grep could check the file mime type then call the tool to convert from the binary format to the text format if available. I could see this being useful for a lot of binary formats.

I've always thought a nifty way to deal with this would be to use a FUSE filesystem. So you'd have a directory structure like:

    /workspace
      /ast
        /module-1.ast
      /fuse-src
        /module-1.txt

where opening and modifying "module-1.txt" would cause "module-1.ast" to be updated, and vice-versa. I actually think I've seen this approach used in some experimental language or another. I'm sure there would be a LOT of tricky edge cases and/or synchronization bugs to address, but it seems like it's not very far outside the realm of feasibility.

And this is why I love Python. It forces people to use the same coding standard in some regards, and it forces people to indent properly.

I really don't care anymore what that standard might be (well, ok, I do prefer tabs) but I do care that it be consistent. And I do DEMAND that proper nested indentation be respected. Source code is meant to be human readable.

Python is not unique nor innovative in that respect. Even FORTRAN and COBOL programs from the early days had very strict rules about indentation and blocks.

The thing is, there's no reason we have to store the code like text. Even the punch card got this right: the program wasn't stored as text, it was stored as physical holes in paper. A very experience programmer could often look at a card with just the holes and have a rough idea what it encoded, provided they knew if it was EBCDIC or ASCII or whatever, but the computer didn't care. The printed representation across the top line of the card was just that: a representation.

> Even the punch card got this right: the program wasn't stored as text, it was stored as physical holes in paper.

We still do that, storing executable programs as executable binary rather than text. What else could you do?

We store them as serialized text. We could store them as nodes in an AST; we could store them as OLE/CFBF structures like older versions of Microsoft Word, or do what Ted Nelson suggested decades ago: T. H. Nelson, “Complex information processing: a file structure for the complex, the changing and the indeterminate,” in Proceedings of the 1965 20th national conference, New York, NY, USA, Aug. 1965, pp. 84–100. doi: 10.1145/800197.806036.

We do not store executables as serialized text, unless they are meant to be executed by an interpreter.

In the context of this thread, where we are discussing Git as a medium for storing the form of the programs in a format that is meant to be read and maintained by humans, we do store the programs in text.

No, in the context of this thread we are storing programs as punch cards, which are not meant to be read or maintained by humans. They are the executable form of the software, that's all.

No, punch cards are not the binary. Punch cards contain source which is compiled.

I didn't claim that Python is unique nor innovative. However, FORTRAN and COBOL are not modern languages in the sense that one can reasonably expect a large selection of first- and third- party libraries for most common situations, and their availability on e.g. servers is far more limited, thus learning them just for scripting is not as good a choice as is Python.

> It profoundly is. You can't store "an AST". You can only store a serialization of it. The official language grammar is a serialization of the AST custom crafted for that language. It is as much an "AST" as any other serialization would be; all such alternative representations would all produce isomorphic memory representations if parsed from a proper library.

But a code file isn't coming out of a serializer when you hit save. It has all kinds of idiosyncrasies beyond the AST it turns into, and the user expects them all to be preserved. That makes it pretty profoundly not an AST.

And often it doesn't even parse.

What do you call “an AST plus the additional information (such as whitespace info) needed to recover the original text the AST was parsed from” (if that has a name)? I think I saw it mentioned somewhere as having a name.

I’ve seen “concrete syntax tree,” delightfully.

Thanks, that term came up with good search results. I appreciate it.

Storing everything in plain text is better. But there's no reason source code needs to be edited as plain text.

Serializing structured data into ASCII streams makes it very hard to then deserialize and re-structure.

Plain text might be the lowest common denominator for Unix/shell tools, but we can do far far better in how structured data is exchanged, which would make it much easier to programmatically manipulate & process.

You might be interested in https://unisonweb.org/

> There's no reason source code need to be stored as plain text

The same can be said for lots of different documents, and it's been true for programs like Word for a long time. See also [1]T. H. Nelson, “Complex information processing: a file structure for the complex, the changing and the indeterminate,” in Proceedings of the 1965 20th national conference, New York, NY, USA, Aug. 1965, pp. 84–100. doi: 10.1145/800197.806036.

That's some cool discussion!

Don't forget bugs. Bugs in git is nightmare scenario. There are so many complexities with just plaintext, there's no way AST diffs get broad support. Also, AST needn't always be simpler than plaintext, e.g. C++ macros.

[whispers] don't give up! There's quite a bunch of us. Our day will come! Long live glorious tabs!

I'm fine with using tabs, but my tab width will be set to 8... be sure to obey line length limits with that in mind.

anything beyond 2 is heresy, and some days I'm tempted to go down to 1

Heretic! From the book of Linus [0], chapter one:

> Tabs are 8 characters, and thus indentations are also 8 characters. There are heretic movements that try to make indentations 4 (or even 2!) characters deep, and that is akin to trying to define the value of PI to be 3.

[0] https://www.kernel.org/doc/html/latest/process/coding-style....

of course PI isn't 3, it's 1 (from a distance)

Only if you're a cosmologist.[0]

0: http://xkcd.com/2205/

Cursed April fools update: tabs are now π spaces wide.

Math trivia: there are cases on which it is sensible, in sufficiently advanced mathematics, to define pi as 3 (or whatever other number).

I don't use tabs, but if I'd say that the biggest advantage of using tabs is that everybody can configure their own editor to make them as large as they wish.

Three shall be the number of the counting and the number of the counting shall be three. Four shalt thou not count, neither shalt thou count two, excepting that thou then proceedeth to three. Five is right out.

There are no line limits. That is what word wrapping is for.

Tabs do work as long as they aren't fixed width (I don't know what you mean by "custom").

For instance, in many languages, one will sometimes have to split a function call to many lines, and in most languages function names aren't of fixed length, thus in order to get a correct alignment for parameters, the tab width at that point will have to match the function name length.

    #include<stdio.h>

    int main(int argc, char* argv[]) {
        printf("%s %s %s %s\n",
               __FILE__,
               __LINE__,
               __DATE__,
               __TIME__);

        return 0;
    }

I agree with your idea of storing a normalized version of the code in the repo: it wouldn't then matter whether that version contains characters to align the code properly, it would just be inserted by the editor/linter as needed. The difficulty is that sometimes linting isn't enough, and some manual formatting is needed. Or perhaps the formatting rules are under specified?

Another issue with AST diffing is when languages allow some form of syntactic sugar as preprocessing: the compiler might just see the simplified tree, not the one with the "sugary" forms. A tool capable of parsing such languages should also be able to handle these extensions.

> the tab width at that point will have to match the function name length.

This is a non-issue. Use tabs for indentation and spaces for alignment.

That is the kind of problem solution that ends up with you now having 2 problems. New problem(s); having tabs and spaces, having to think when to use them, having to train/document everyone in usage, having to debate that usage, having to correct code and chastise people who get usage wrong.

Use a automatic code formatter with minimal options. Automate either running code formatter on commit or denying commits that change when code formatter is run on them.

Absolutely, I wouldn't dream of doing any kind of fancy alignment by hand, only with an auto-formatter.

If I had to break arguments onto multiple lines without an auto-formatter I would just keep it simple and use another level of indentation instead of aligning them with the function name.

Better yet, just never do alignment.

Obviously readability is subjective, but personally I find alignment is never valuable outside of tables of data, and I'd argue generally having tables of data embedded in your code isn't ideal.

    #include<stdio.h>

    int main(int argc, char* argv[]) {
        printf(
            "%s %s %s %s\n",
            __FILE__,
            __LINE__,
            __DATE__,
            __TIME__
        );

        return 0;
    }

Reads better to me and avoids the issue entirely. It also plays more nicely with traditional diff tools anyway.

Yes, that was more or less the argument I was trying to do by the end of my comment: diffing is meant to be space agnostic (the -B option of diff(3)), but since code is committed with formatting, formatting will interfere.

Interesting idea.

This will work with C (for now), but it will fail with language like C++ where you can have lambdas. When a lambda is a function parameter, it will need to be aligned to other parameters, but the lambda body will require indentation.

Of course, there are ways of avoiding the problem, eg. by using a variable for the lambda, yet isn't this sweeping things under the rug?

The whitespace and formatting are not significant to the compiler, but they can provide a lot of information to the reader of the code.

You can often see where the writer put the most effort and thought by just seeing how they wrote it. This can help analyzing a codebase considerably.

If everything is normalized, you lose those valuable cues.

You can also write git hooks to turn their spaces into your tabs & vice versa.

That's not a good solution - every commit with an author (well technically committer I suppose) whose opinion differs to the last will be horrendous.

There won't be any difference. OP will run the script when they checkout, work with their tabs, then run the script when they commit. Spaces in, spaces out.

Oh ok, sure. But then that's just a weak version of what's being requested - an entirely neutral more agnostic, abstract format that stores the meaning without any formatting at all.

fwiw, this is what we do in Dark [1]. We store (serialized) ASTs, then then we pretty print them in the editor. This converts the AST into tokens that you see on your screen, complete with configurable* indentation, line-length, etc. Code would be displayed according to your config* and the same code displayed differently to a different developer looking at the same code.

[1] https://darklang.com

* I haven't actually enabled users to configure this, but it's just some variables called 'indent' and `lineLength` in the code

One of the practical issues here is, if your code fails to compile in CI with an error like

    /home/ci/src/foo.c:123:45: error: use of undeclared identifier 'a'

    /home/ci/src/bar.py:50: syntax error in type comment

or crashes in production with an error like

    java.lang.NullPointerException
        at com.example.Baz.doThings(Baz.java:1337)

you really want to be able to find line 123 column 45, line 50, or line 1337 in your editor, and have that be the same line as what your CI compiled and deployed.

On its own, tabs vs. spaces only affects columns, and you can probably figure things out without columns (although it's a shame to lose it). But different tab sizes affect how long your lines are, and line wrapping is a thing that people care about at least as much as tabs vs. spaces (people with different size monitor or fonts will easily see too-long or too-short lines on their display; if your spaces are equivalent to the tab stop, the distinction is literally invisible). And once you start rewrapping lines, everyone's line numbers are different.

I think it's possible to solve this by using some sort of AST-based index into the file and teaching IDEs to let you seek based on that, but it's suddenly a more complex problem.

This is already a very common problem with a solution: transpiled JS already needs source maps to display errors correctly.

No, I don't think that's the same problem / the same solution. A source map translates between a layout checked into the code and a format generated at build time. I'm talking about translating between a layout in a developer's local workspace and the layout checked into the code.

Since the developer can choose whatever formatting options they want, there isn't a single source map that can be referenced in the compiled version of the code, so backtraces etc. So the transformation cannot be done at the point the error is displayed (compiler output or backtrace output), it has to be done in the context of the developer's local workspace.

I think source maps could probably be inspiration for solving this problem, but I don't think they would work directly - and even if they did, the real problem here is not designing a solution, it's getting everyone's IDEs to work properly with it. Source maps work largely because the major browsers know how to deal with source maps in JS. You'd have to extend this to all the other ecosystems, at the very least.

No, it's literally the same thing.

We don't ship source maps on production apps. This is for JS apps but also similar with executables and debug files.

All the logging is done trough some service like Sentry, but exactly where the error happened is opaque in the client-side. Sentry is responsible for doing the sourcemap translation.

The only difference is that with "personalized" formatting, the source mapping would be done based on the user that is logged to Sentry.

That's it.

Of course there are other workflows such as support getting errors displayed directly to customers via copy-paste, or reading server logs to look for those errors, but for apps where you have a logging solution you don't need to rely on those.

Yes, but only if it falls back to text diff as soon as there is the smallest doubt it can't provide a good AST diff.

If you append `?w=1` to the diff view URL on a pull request it makes it whitespace agnostic just FYI

having presentation by flexible and different than the underlying model is a great idea for code

but admit it, tabs are fragile and a pretty weak implementation

> admit it, tabs are fragile and a pretty weak implementation

Could you elaborate? I don't have a personal opinion here and have only worked in orgs that require spaces, but I'm not familiar with the criticisms of tabs.

For me the problem happens as soon as tabs are used for alignment, instead of just indent. The benefit of tabs is custom tabstop. If anyone does anything that undermines that benefit, you might as well use spaces to avoid all the problems caused.

Consider the following code:

    if (x)
    {
        SomeMethod(paramater1,
                   paramater2,
                   parameter3);
    }

If done "properly", it is:

    if (x)
    {
    <tab>SomeMethod(paramater1,
    <tab><spaces...>paramater2,
    <tab><spaces...>parameter3);
    }

What I often see, that totally breaks the entire point of tabs:

    if (x)
    {
    <tab>SomeMethod(paramater1,
    <tab><tab><tab><space><space>paramater2,
    <tab><tab><tab><space><space>parameter3);
    }

The same thing happens if you are trying to align table-style code:

    var badMixedTypeArrayExample = [
        [ "some",          true,        128,  x                 ],
        [ "long strings",  true,          8,  someLongVariable  ],
        [ "and",           false,     16384,  x                 ],
        [ "short",         true,   12345678,  anotherVariable   ],
    ];

If tabs are used between fields, it will look like a hot mess to anyone with a different tabstop than the author.

Which is the reason for the very common stance "tabs for indentation, spaces for alignment".

Which is easy to say, but hard to make everyone do correctly. First you need to ensure that everyone uses an editor with a "visible whitespace" option, and turns it on, so they can see whether they have the right whitespace. Then you get to spend precious programming time turning one kind of whitespace into another since most editors will get it wrong when they auto-indent.

Either use spaces everywhere so you have total control over the layout or forego alignment (other than block indentation). Mixing tabs and spaces is a path to madness.

This is part of the reason why editors for programmers and editors for general text editing are not the right thing.

I have F11 in emacs bound to whitespace-cleanup, which takes care of it all for me. And supertabs mode in general works just the way it should with tabs-indent/spaces-align.

Then there's also clang-fmt, possibley used as a post-receive hook in git (and some other VCS) which makes irrelevant what the programmer's editor did, mostly.

Can whitespace-cleanup really differentiate between places where you want a tab for indentation, and places where you want spaces for alignment, where the number of spaces may be greater than the tab width? After all, the only way to differentiate is to guess what you might be trying to align to by looking at surrounding lines… but from a quick search, whitespace.el looks less complex than that.

You're entirely correct. Sorry, i forget, whitespace-cleanup is there so that I can remove dangling whitespace from the end of lines.

supertab mode is the tab-to-indent/space-to-align magic.

    if (x)
    {
        SomeMethod(paramater1,
                   paramater2,
                   parameter3);
    }

You simply should not write this code. It's unclear, and performs nonsense indentation. You could do:

    if (x)
    {
        SomeMethod(
            paramater1,
            paramater2,
            parameter3
        );
    }

If you need your function to use line breaks.

I totally agree; I personally hate this style of code! However, people still write it (in the same way they screw up tabs+spaces), and in some code bases it's "the style" they use.

I've also seen a lot of SQL and LINQ (C#) written in this way, as well as things like:

    var longString = "Line 1\n" +
                     "Line 2\n" + 
                     "Line 3";

Personally, I'd go as far to say that `alignment` is an anti-pattern.

Setting up an automatic formatter and using tabs is personally the best for all worlds. Space-like alignments like

    var someReallyLongVar = 5;
    var x                 = 10;

Are the worst!

The main supposed advantage of tabs is that everyone can set their own custom preferred tab-width and be done with it, but this advantage doesn't actually play out in practice:

* There's usually a maximum line length restriction as well, so you need to know what the tab-width is to figure out if a line needs to be broken into multiple lines.

* There are also cases where you need exact-column alignment, even across multiple indent widths. A simple example is as follows:

  module whatever {
    fn long_function_name_whatever(arg1: type1,
                                   arg2: type2,
                                   arg3: type3,
                                   etc:   etc4,
                                   do:     you,
                                   get:     my,
                                   point:  now);
  }

So in practice, tab width for a project is actually fixed to a particular value. And then you discover that wrong-tab-width code becomes quite annoying to read. I hate reading GNU style guide code, which uses 8-space-tabs but indent-width of 4, because the indenting is unreadable unless I mess with the tab spacing for an individual file I'm reading.

Alignment can just be done with spaces. This can then be enforced by a style checker.

But the maximum line length problem is real. I would be 100% for tabs if it wasn't for this issue and imo it's the only real criticism you can make that doesn't have a good solution.

The alignment in the comment above doesn't work with tabs: your initial line is going to be tab-indented, which means if you want those next lines to align with it you don't have any options for it to work.

Now, I tend to find it's better to just avoid that kind of alignment in your code style completely (just push the first arg to a new line so you're not space-ing everything out a mile to match the function call open paren) but if that's your style then you can't really do it with actually variable tab widths.

"Alignment done with spaces" would look like this for that code.

  module whatever {
  ->fn long_function_name_whatever(arg1: type1,
  ->...............................arg2: type2,
  ->...............................arg3: type3);
  }

It works just fine - tabs for indentation and spaces for alignment.

Oh duh... I don't know why I didn't think of that.

The good solution to the line length problem is to not be strict about them. My line length rule is usually "stay roughly within 100 spaces, 120 is too long." If you are seriously undermined by lines being too long, then your text editor choice/setup might be worth revisiting.

> 120 is too long

That sounds a lot like a hard limit. The difference between 2-space and 8-space tabs is huge, so you still have to specify what tab width you're using and someone who prefers a narrow tab width could still accidentally blow past the hard limit if they're not careful.

My solution to the maximum line length problem is simple: if a piece of code has more than 3 level of indentation, I start to think about refactoring, and never let it have more than 5.

I find that any reasonably complex code with 5 levels of indentation becomes difficult to read, and with more levels the difficulty grows exponentially.

At least with languages I have significant experience, keeping the levels of indentation low never was a problem. But I never did serious amount of coding in LISP or Python, for example, so I don't know if this is practical in such languages.

it only works for initial indentation, so people that like columnar layouts are kinda screwed. auto-tabbing tools will take n-spaces and turn them into a tab, which screws up stuff.

lets just take the whole idea one step further and either use tools that reformat based on agreed upon styles (meaning a developer could reasonably take the source, preject it into their preferred style and project it back out again).

or store the canonical version as structured data in a database and always project it into some text for viewing.

broader adoption of formatters has drastically reduced the number of pointless and emotional formatting arguments I've gotten into. lets push that further.

Reply on news.ycombinator.com