Comment by jblow

10 years ago

Please read this with a grain of salt as it does not seem practical or necessary. It seems like the kind of thing written by a young person who is excited but doesn't really have much experience. Most of the ideas would not be real-world-useful as stated.

Excitement is nice to feel, but it takes some experience to know when excitement is really aimed in a productive direction. Otherwise we end up with the kind of motivation that so often produces over-complex and mis-aimed software: having a "cool idea" for "exciting technology" and then looking for places to apply it, and the applications don't really fit or don't really work, but we don't want to notice that, so we don't.

To pull examples: an entire one of these essays is on "paren matching" and how it would be really great if you monoidized (ugh) and parallelized that ... the basic idea of which is instantly shot down by the fact that language grammars are just more complicated than counting individual characters. Hey bro, what if there is a big comment in the middle of your file that has some parens in it? The author didn't even think of this, and relegates this to a comment at the end of that particular essay: "Jonathan Tomer pointed out that real parsing is much more interesting than just paren matching." Which is a short way of saying "this entire essay is not going to work so you probably shouldn't read it, but I won't tell you that until the bottom of the page, and even then I will only slyly allude to that fact." Which in itself is contemptuous of the reader -- it is the kind of thing that happens when you are excited enough about your ideas that the question of whether they are correct is eclipsed. This leads to bad work.

There's the essay about the scrollbar -- if you have a 100k-line text file, do you really want a really long line somewhere in the middle to cause the scrollbar to be narrow and tweakyin the shorter, well-behaved majority of the file? No, you probably don't! But this shoots down the idea that you might want to do a big parallel thing to figure out line length, so he declines to think about it. In reality what you probably want is the scrollbar to be sized based on a smooth sliding window that is slightly bigger than what appears on the screen (but not too much).

Besides which, computers are SO FAST that if you just program them in a straightforward way, and don't do any of the modern software engineering stuff that makes programs slow, then your editor is going to react instantly for all reasonable editing tasks.

I don't want to be too overly critical and negative -- these sorts of thoughts are fine if they are your private notes and are thinking about technical problems and asking friends for feedback. It becomes different when you post them to Hacker News and/or the rest of the internet, because this contains an implicit claim that these are worth many readers' time. But in order to be worth many readers' time, much more thought would have had to go in ... and as a result, the ideas would have changed substantially from what they are now.

I didn't read past essay 4, so if it gets more applicable to reality after that I don't know!

Hi Jon! Great to see you here. Much of what I wrote is speculative, especially paren matching based on monoids. What actually went into xi editor is much more conservative. I didn't actually intend this to be posted to HN, but am not too surprised it did.

As to being a young person, I don't know if you remember, but I was already of drinking age when you and me and Adam Sah hung out a bit and talked about the "rush" language.

I admit to being excited, but because I think "modern" editors really are too bloated and slow and it causes a thousand paper cuts throughout the day, and I think that can be fixed.

  • Oh you're that Raph! Hi.

    Sorry for presuming age + experience level, it's how this came across to me. Actually I think Rush is a prime example of "excited about general ideas that turn out not to be right or relevant to much". But we were students, and I guess that is what students often do.

    I agree modern editors are too slow and bloated. I would write one if I didn't have way too many other things happening. But I don't think they are slow and bloated due to a lack of computer science concepts. I think they are slow because most of the world, over the last 25 years, has lost the art of writing software that is remotely efficient.

    If I were to write an editor, it would store text as arrays of lines (since lines are what you care about) with maybe one level of hierarchy, such that each 10k lines of the file are in one array. I think that would be fine and if it ran into problems with very large files, relatively minor modifications would take it the rest of the way. (Of course this is untested but I feel pretty confident about it). Rather than calling malloc all the time, a specialized allocator would be in play.

    I do think it's a good idea to make a better editor so I wish you good luck with that (dude I am so sick of emacs).

    • I used an array of lines in gzilla[0]. It's not bad, but it _is_ exporting details of the representation up to clients, which gets worse once you add some hierarchy. To me, the nice thing about ropes is that they appear to the client as just a string, with some fancy added methods such as creating a cursor that can advance to the next or previous line efficiently. Of course, to make this work, you need a good programming language; an implementation of ropes in C would be painful.

      As I said elsewhere on the thread, the good thing about ropes is their worst case performance. Super-long line? Rope still efficient. 10 million line file? Rope still efficient. Massive sequence of edits relative to the pristine file? Rope still efficient. It's pretty easy to write code which works well in the common cases but then degrades when things get interesting. I'm not going to apologize for caring about that.

      [0] http://www.levien.com/free/gzilla-tour.html

      3 replies →

    • What other than computer science concepts can save us from slow software? Computer science concepts (Amdahl and Moore, maybe Dennard, maybe-maybe Landauer) have proven that hardware improvements cannot. Is there some aspect of the software performance that can only be understood through another domain of human endeavor?

      10 replies →

the basic idea of which is instantly shot down by the fact that language grammars are just more complicated than counting individual characters

I'm sure someone overly excited is at this very moment trying to make this a mathematically precise statement so they can see if you're right, and if so, if there's a way to change the author's approach to support more complicated computations on the text. Maybe you can help them along if you're not just guessing.

  • There was a link to the Wikipedia article on the Dyck language [1] somewhere, which lead me to the Chomsky–Schützenberger representation theorem [2], which says that every context-free language can be represented by a homomorphism applied to the intersection of a Dyck language (possibly with multiple different kinds of parentheses) with a regular language.

    The Dyck language can be recognized by a monoid as described. The regular language can be recognized by a monoid whose elements are functions between states of the recognizing automaton, each symbol being identified with the transitions the automaton performs when reading the symbol. The intersection should be describable by the product of monoids. (If such a thing exists, anyway. My abstract algebra is a bit rusty.)

    The hard part is dealing with the homomorphism that turns the intersection of the two languages into the context-free language. I'm guessing that the general construction might require turning parentheses into empty strings, which would destroy the simplicity of the monoidal construction.

    Anyway, I'm unfortunately not excited enough to see whether I can get it to work, at least not right now. But maybe it helps point someone else in the right direction.

    [1] https://en.wikipedia.org/wiki/Dyck_language [2] https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenb...

  • To get the parentheses right, you have to parse the language.

    There is an extensive body of literature on parsing that goes back decades. Most of it I don't think is that useful. But some of it is about parallel parsing. If you are interested, there are quite a number of people with something to say about it. However, the speed wins in practice are not very big.

    On the other hand, if you just write the parser so that it's fast to begin with, you don't really have a problem. The language I am working on parses 2.5 million lines of code per second on a laptop, and I have only spent a couple of hours working on parser speed. To do this it does go in parallel, but it goes parallel in the obvious way using ordinary data structures (1 input file at a time as a distinct parallel unit). So it's not "parallel parsing" in the algorithmic sense.

    • Why do you need to parse the language to get parens correct? For most languages, comments and strings will need to be considered, but neither of these requires doing a full parse.

      Of course, I don't disagree with your point that a fast parser makes making a distinction here less useful. However that number sounds interestingly large, without context, do you have more info I can read about it?

      3 replies →

First, to the immediate point: Ropes are not talked about much outside of whitepapers and undergrad data structure courses. This is a shame, even if ropes are only useful on very long strings. More discussion, more documentation, and more attempts to use ropes are not a bad thing, even if nothing "practical or necessary" comes of it. (And I would say that a text editor is quite practical!)

Second, it's completely reasonable to imagine data-structure-driven improvements to the task of writing source code. Imagine, for example, an AST editor. There are tools like org-mode and paredit which are halfway to true AST editing, and plenty of languages have tooling sufficient to support it, if there were demand. An AST editor would, of course, generalize the lessons here about ropes to pretty-printed ASTs, but there's no innate reason why it couldn't be done.

Third, a meta-comment, to address your comment elsewhere in the thread: "There are, of course, computer science concepts that are very smart. But we don't need these to save us from slow software, because today's slow software problem is just the result of people doing bad things in layer upon layer. We have to stop doing all the bad stuff and dig us out of the hole we're in, just to get back to neutral. Once we are back at neutral, then we can try thinking about some computer science smarty stuff to take us forward."

There are assumptions here about the nature of CS. CS is a science of abstractions. Complaining about layers in CS is complaining about the very nature of CS. Software is slow and insecure and hard to use because the tasks that we demand of software are extremely complex and our human processes for creating code are not sufficiently high-level, powerful, and expressive enough for us to design good systems on the first try.

Whenever somebody says, "I have removed a useless abstraction," they usually forget to also say, "By replacing it with a useful abstraction."

  • Only replying to one point in your post, but if you think org-mode and paredit take you halfway to AST editing, try abo-abo's lispy. It's closer to the ideal by half again, at least.

  • I've found the best removals of abstractions I've done have gone back to essentially bare code. That is, I put back the abstraction either I or a coworker originally avoided.