1. 5

    Oh man, that makes me feel old. I interned there exactly 20 years ago (which would make it 30 years old at the time :) )

    In summer 2000, from about June to August, I was biking from Stanford campus past that Xerox PARC sign in the first pic every day!! Although I recall my crappy used bike got a flat and I ended up getting a ride or walking for the last few weeks. AMA.

    1. 9

      Tangent/clarification: the regex slowness issue is almost certainly due to using Perl-style exponential time regexes (which are required by Sublime syntax definitions) rather than “regular languages”.

      The syntect library mentioned uses fancy-regex, which is explicitly different than Rust’s default regex crate, in that it supports regex constructs that require exponential backtracking:

      https://github.com/fancy-regex/fancy-regex

      In particular, it uses backtracking to implement “fancy” features such as look-around and backtracking, which are not supported in purely NFA-based implementations (exemplified by RE2, and implemented in Rust in the regex crate).

      I think “regexes” have gotten bad name so I call them “regular languages” now. That is, RE2, rust/regex, and libc are “regular language” engines while Perl/Python/PCRE/Java/etc. are “regex” engines.

      In my experience, lexing with regular languages can beat hand written code. In the case of Oil vs. zsh, it’s beating hand-written C code by an order of magnitude (9-10x).

      http://www.oilshell.org/blog/2020/01/parser-benchmarks.html

      https://lobste.rs/s/77nu3d/oil_s_parser_is_160x_200x_faster_than_it_was


      First, TextMate / Sublime style syntax highlighting is not really all that great. It is quite slow, largely because it grinds through a lot of regular expressions with captures

      pedantic: I think the issue is probably more lookahead than captures ? You can do captures quickly in a “regular language” engine.

      It may be surprising just how much slower regex-based highlighting is than fast parsers. The library that xi uses, syntect, is probably the fastest open source implementation in existence (the one in Sublime is faster but not open source). Even so, it is approximately 2500 times slower for parsing Markdown than pulldown-cmark.

      (copy of HN comment)

      1. 12

        fancy-regex only uses backtracking when “fancy” (principally, look-around and backreferences) features are used. Idk what proportion of syntax regexes actually use said fancy features though.

        Also, I’m pretty sure syntect has only just recently switched to using fancy-regex. It was using Oniguruma (Ruby’s regex engine) for a long time. I haven’t been playing especially close attention, but IIRC, fancy-regex didn’t really improve things much. Not sure what’s going on, but it sounds potentially interesting. I definitely wouldn’t leap to the “it’s exponential” explanation immediately.

        pedantic: I think the issue is probably more lookahead than captures ? You can do captures quickly in a “regular language” engine.

        In the RE2 ancestry of regex engines, no, you cannot. Resolving capturing groups is a known sore point because it needs to use either the bounded backtracking or PikeVM regex engines, which are much slower (~order of magnitude) than a DFA in common implementations. One of my major goals over the next few years is to fix this.

        In my experience, lexing with regular languages can beat hand written code. In the case of Oil vs. zsh, it’s beating hand-written C code by an order of magnitude (9-10x).

        I think before throwing this around, one needs to consider the viability of using such a technique with syntax highlighting. I’ve never invested significant effort into syntax highlighting, but the two immediate problems that jump out at me are 1) the size of the state machines and 2) whether the lexer framework on its provides enough “power” for quality syntax highlighting.

        1. 5

          I think there is a subtlety here – even if fancy-regex doesn’t do backtracking for regexes that don’t require it, the author of syntect points out here that a speed problem with Sublime’s parsing model is repeatedly reading the the same bytes.

          https://news.ycombinator.com/item?id=23665341

          So I say there that in an “regular language” engine you can just | the patterns together and avoid this (which I do in Oil). But that composition doesn’t hold or is more complex for Perl-style regexes.


          About captures I think the last time we talked about it I pointed to this re2c paper: https://arxiv.org/abs/1907.08837

          However I haven’t actually done anything with it, and Oil’s lexer doesn’t use captures. (I am sort of curious to benchmark some Sublime-ish workloads with re2c but I probably won’t have the time).


          Yes you need more power than regular languages to do syntax highlighting. String interpolation syntax, shell here docs, Rust/Lua multiline strings, etc. are a major reason.

          In Oil I simply add a tiny layer of “lexer modes” on top to solve that problem:

          http://www.oilshell.org/blog/2017/12/17.html

          It’s utterly trivial but solves all the lexing problems. So my point is that Sublime should not have based its parsing model on Perl-style regexes. It could have used regular languages plus some trivial state machine on top.

          Vim syntax highlighting does something like that as far as I know. It goes line by line and I think there’s an extra “state” variable for each line, outside the regex state.

          1. 6

            About captures I think the last time we talked about it I pointed to this re2c paper: https://arxiv.org/abs/1907.08837

            Right. But that blows up the size of the automaton. IIRC, the author of re2c is specifically on record as saying that these aren’t good techniques for general purpose regex engines like RE2 because of the size requirements. Remember, RE2 doesn’t do full DFA compilation. Now maybe it is good enough for the syntax highlighting use case. I don’t know. Maybe you can afford on-demand full compilation, but there are probably a of details to work out.

            I don’t have enough knowledge about the syntax highlighting domain to debate the particulars unfortunately. I would guess that there are other trade offs. e.g., ease of writing syntax highlighting rules.

          2. 3

            I remember reading from a pretty authoritative source (I can’t for the life of me remember where, but it was a deep dive into regexes by one of the creators/main implementers) that the algorithms you need to use to support the PCRE features drastically increase the runtime cost.

            1. 10

              Yes. I wrote Rust’s regex engine. PCRE and its ilk are implemented with backtracking, which takes worst case exponential time. That isn’t really the issue here. Whether that’s the root cause of the performance problems requires a deeper analysis, and my instinct says “probably not, or at least, it’s only part of the story.”

              People like to jump on time complexity guarantees very quickly, which tends to over simplify the matter. Sometimes it is indeed the right explanation. But in practice, there are many different kinds of performance cliffs in regexes.

              1. 4

                Hm all my experience disagrees with this. I would say that computational complexity is essentially the only thing that the user of a regex engine cares about regarding performance (or should care about).

                In other words, backtracking is the number one performance problem in practice with regexes and backtracking is a computational complexity issue.

                Computational complexity isn’t sufficient analysis for all situations (e.g. https://news.ycombinator.com/item?id=23363165) but it’s never steered me wrong when dealing with regular expressions.

                In other words, I don’t really care if it’s NFA or DFA. Both RE2 and rust/regex do submatch extraction without backtracking right? If so, that’s the high level bit that matters, and the rest are just details from a user’s perspective.

                Yes I am probably sweeping a lot of your hard work under the rug :) I’m sure there are hundreds of things you know about regexes that I don’t because you’ve implemented a regex engine. But I still disagree with your assessment from a user perspective, based on years of experience in many applications.

                Reviewing the benchmark I wrote last time [1], I remember I hit the 8MB hard-coded limit in RE2. But I still think that’s a non-issue for any application I know of. Its usage is proportional to the pattern size as far as I remember.

                https://news.ycombinator.com/item?id=23665569


                I’ve used a variety of regex engines in a variety of applications for 15+ years:

                • lexing programming languages in C, Python, and JavaScript (The lack of the sticky /y bit in ES3 caused regex-based lexers to be O(n^2), which was one reason I gave up programming JS for awhile)
                • big data, e.g. running MapReduce-style jobs over Google’s web indices. I used RE2 when it was first developed at Google and experienced its power firsthand.
                • I borrowed the trigram index technique Cox wrote about in one of my programs shortly after he wrote it (and before he published any of those articles)
                • years and years of shell and command line stuff (grep, sed, awk)
                • web server config files (Google had an internal network outage due to a backtracking regex in proxy.pac back in the day, a very common bug.)

                Here are several examples:


                If anyone disagrees, I would like to hear specific examples of:

                • applications where the regex gave you linear-time performance (no backtracking), but the performance still wasn’t good enough. I don’t know of any. (I guess there is the DPI stuff by Hyperscan, though again I think one of their main wins is to compile thousands of patterns into a single DFA, much like what I used RE2 for with big data)
                • applications where backtracking was applied to big data and didn’t blow up in your face after years of usage.
                1. 9

                  Oof. I’m sorry, but I just don’t have the energy to do this back and forth with you again. The last time we did this, I felt like we were talking at cross purposes for a long time, and I’m getting that feeling again.

                  I’ll just leave it at this: the HN comment you’re linking to isn’t strong evidence of your conclusion IMO. More details are needed.

                  Hyperscan, though again I think one of their main wins is to compile thousands of patterns into a single DFA

                  No. Their main wins were the development of several novel SIMD algorithms that have good scaling properties and are otherwise exceptionally clever. They certainly do not generate one giant DFA. They’ve written papers about it.

                  1. 10

                    I’ve also been reluctant to engage this thread, because it reminds me of an LL(1) recursive descent parser before left-factoring the grammar. But I can’t resist going into what my kids call “lecture mode” for a bit.

                    Andy seems to be hyperfocusing on one aspect of the parsing task, backtracking, while there’s little evidence that this is the main drawback to TextMate style highlighting. He seems to be proposing a highlighting scheme which is generally similar to TextMate but has faster low-level lexing based on actual regular languages. I fully grant that such a thing is possible, but find it an uninteresting point in the space of highlighting engines.

                    First, the Perl-style regexes are actually quite useful for handling a variety of important real-world lexing tasks. One of my favorite examples is Rust raw strings, which cannot be parsed by a regular language, but are easily expressed by backreferences. If you take these away, you’ll need to add another mechanism to restore the lost power.

                    But let’s take a step back. A good highlighting engine should fulfill (roughly) these goals:

                    • Fast
                    • Accurate
                    • Incremental
                    • Easy to write syntax definitions
                    • Support embedded sublanguages

                    TextMate scores poorly on the first, meh on the second, and pretty good on the last three (the incrementality comes from line-at-a-time processing, which impacts accuracy). Andy has acknowledged that pure regular languages are inadequate, and proposes “lexer modes”, which I understand to be a stack. TextMate also has a stack, with explicit “push” and “pop” operations.

                    So let’s work from principles. Obviously we want to touch every byte of the input once, in a single pass. A regular language gets us most of the lexical structure, but we also need a stack to capture more of the grammar, and also handle embedded sublanguages. Can we invent a parsing scheme that somehow combines these two?

                    The answer is of course that there is a rich and deep literature on exactly this topic, we’ve just described an LR parser, and the invention was done by Knuth in 1965. Pure LR parsing is not powerful enough to handle real languages, but there’s been a lot of work on how to make it more powerful, including GLR. Even better, we know how to make such a parser incremental, thanks to Tim Wagner’s PhD and related work. Writing such a parser by hand would be tedious, but thankfully there is also a rich literature of parser generators (of which lex and yacc are classical, but there have been improvements since).

                    So now we’ve basically described tree-sitter, which is shipping in Atom and Github, and has been reimplemented as Lezer, which is shipping in CodeMirror. There are a few dozen grammars, covering the most popular languages (as opposed to hundreds for TextMate).

                    So. How would a “regular language” variant of TextMate stack up? I’ll leave that to the reader.

                    1. 5

                      Thanks for that summary. :-) Appreciate it!

                      1. 1

                        Obviously we want to touch every byte of the input once, in a single pass.

                        The answer is of course that there is a rich and deep literature on exactly this topic …

                        We’re in 100% agreement. I’ve watched all the treesitter talks (and I put a TODO on my list to write a R grammar using it, which I unfortunately never got around to).

                        My point is the same one that RSC made in his articles (which are awesome but I think too dense to sink into a general programming audience):

                        With respect to regexes, using good theory leads to good programs. https://swtch.com/~rsc/regexp/regexp1.html

                        And Treesitter is a great example of that. On the other hand, matching 20 Perl-style regexes in sequence at the same character position is a counterexample. That is my point, and I’m not sure why that would be controversial to state!


                        Lexer modes are another possible model to maintain linear time and get more power, but there are many possible models to drive them, e.g. another state machine or something more complex. Treesitter has some related lexing mechanisms apart from the GLR stuff to deal with the same problems: https://tree-sitter.github.io/tree-sitter/creating-parsers#lexical-analysis

                        Pretty much all such parser generators have grown some ad hoc lexing mechanisms (Flex lexical states, etc.) to solve the problems that kind of fall in the gap between theory and practice.

                      2. 1

                        What I remember is that I was pointing out a computational complexity issue (scaling with respect to number of “simultaneous” patterns, not length of input) – and I observed it in practice on ripgrep:

                        https://news.ycombinator.com/item?id=23665569

                        And I wasn’t saying that you should be doing something differently. My point was that Aho-Corasick can fall out for free in a regex engine, and that appears to hold up in practice, with some caveats I noted there (and in the original thread).

                        No. Their main wins were the development of several novel SIMD algorithms that have good scaling properties and are otherwise exceptionally clever. They certainly do not generate one giant DFA. They’ve written papers about it.

                        I went back and looked at the paper. They don’t make a single DFA, but they are absolutely solving the scaling with respect to patterns problem. That is their #1 claim in the abstract. The SIMD stuff is the #2 claim.

                        https://www.usenix.org/system/files/nsdi19-wang-xiang.pdf

                        In this paper, we present Hyperscan, a high performance regex matching system that exploits regex decomposition as the first principle. Regex decomposition splits a regex pattern into a series of disjoint string and FA components

                        I am solving it here using the straightforward method of alternation (notice all the constant strings and regexes):

                        https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_devbuild/tmp/osh-lex.re2c.h

                        So they are doing better by taking advantage of the fact that some strings are constant. They are building on top of the “read every byte once” O(n) property. Getting the computational complexity right is table stakes. (in this case, scaling with respect to patterns, not length of input)

                        That applies directly to syntect. The author claims it’s slower than SublimeText’s engine because it doesn’t do the alternation efficiently:

                        https://news.ycombinator.com/item?id=23665778

                        the reason Sublime’s built-in highlighter is the fastest is they wrote a custom regex engine which basically does the equivalent of or-ing them together but unlike all other regex engines handles captures and information about which one matched properly while doing so. The custom engine doesn’t do backtracking

                        1. 5

                          What I remember is that I was pointing out a computational complexity issue (scaling with respect to number of “simultaneous” patterns, not length of input) – and I observed it in practice on ripgrep:

                          We’ve been through this soooooo many times. Our last conversation on this was me trying over and over again to explain to you that RE2 and its ilk do not use DFAs. They use a combination of NFA simulation (“PikeVM”), bounded backtracking (“bitstate backtracker”) and a hybrid NFA/DFA (“lazy DFA” and sometimes confusingly just called “DFA”) that computes the DFA at match time. None of those techniques scale with the number of regexes. This is by design and this is why re2c’s match time performance does scale: it builds full DFAs. This is also a niche where Hyperscan excels, because it specifically targets the niche of building large pattern databases. The Hyperscan folks have benchmarked the scaling properties of Hyperscan vs RE2, and Hyperscan totally destroys RE2. This is an amazing engineering accomplishment, but neither the Hyperscan nor RE2 authors (I assume, I wasn’t) were surprised by this result.

                          re2c occupies a really important niche, and that’s the niche where you can not only afford to build mammoth sized DFAs, but that you can do it in an offline process. Neither of these things are true in the context where something RE2 operates, and the dramatic effect this has on the implementation of the regex engine cannot be understated.

                          Listen, I’ve written the regex engine. I don’t need to be told its computational properties. I know what they are. I wouldn’t normally hold this against anyone, but we’ve had conversations before, and it still feels like you’re trying to lecture me about this shit. Years ago, I set out with the explicit design decision that all matching should be linear in the size of the input when I built the regex crate.

                          This is why we are talking at cross purposes. This whole thing started out with me expressing a little bit of skepticism at a leap towards blaming computational complexity for the performance problems of syntect. That’s it. Just look at what I said:

                          Also, I’m pretty sure syntect has only just recently switched to using fancy-regex. It was using Oniguruma (Ruby’s regex engine) for a long time. I haven’t been playing especially close attention, but IIRC, fancy-regex didn’t really improve things much. Not sure what’s going on, but it sounds potentially interesting. I definitely wouldn’t leap to the “it’s exponential” explanation immediately.

                          There’s a lot of circumspection there. Instead of just saying, “Yeah good point, more investigation needed,” you’ve snowballed this into some crazy conversation that makes it look like I’m somehow denying the importance of computational properties. When in reality, the last several years of my life have been dedicated to a project that affirms precisely the opposite. Please do not mistake my rigid adherence to trade offs—all regex engines have them—for some kind of ignorance of basic facts. I mean, the fact that you’re linking rsc’s articles in this conversation with two people who have actually built regex engines that are direct descendants of RE2 is just… whacky. As if I haven’t read those articles dozens of times. As if anyone seriously involved in building regex engines hasn’t read those articles.

                          On the other hand, matching 20 Perl-style regexes in sequence at the same character position is a counterexample. That is my point, and I’m not sure why that would be controversial to state!

                          No, it isn’t. You’ve taken a small amount of skepticism on my part for a very specific problem diagnosis and blown it up into general statement about computational complexity.

                          My point was that Aho-Corasick can fall out for free in a regex engine

                          It does not. We’ve been over this. Aho-Corasick is solving a more constrained problem and therefore has both a simpler and faster construction process. The only way “Aho-Corasick can fall out for free in a regex engine” is true is if your regex engine compiles full DFAs ahead of time. That’s true for re2c, but not true for any production grade general purpose regex engine that I know of.

                          I went back and looked at the paper. They don’t make a single DFA, but they are absolutely solving the scaling with respect to patterns problem. That is their #1 claim in the abstract. The SIMD stuff is the #2 claim.

                          Yes, I explicitly mentioned scaling. Hyperscan does not have the scaling properties of a single large DFA. There is a point at which a DFA compiled by re2c will be faster than Hyperscan. I don’t know what that point is or if it’s even practical to reach, but it almost certainly exists.

                          That applies directly to syntect. The author claims it’s slower than SublimeText’s engine because it doesn’t do the alternation efficiently

                          Yes, that’s one piece of the puzzle. But capture groups and the extent to which “fancy” features are being used inside the syntax highlighting regex definitions are some of the other pieces.


                          Listen, I love your work and I love your blog posts. I am positive we could have some really stellar conversations. I bet it would be much better if we were talking in person with a whiteboard, since I’m sure there is a lot being lost in this sort of online discourse. But please, in the future, please please try not to blow things way out of proportion. If you’ve found yourself in a place when I am somehow denying basic computational facts, then please back up and reconsider how you got there. It’s almost certainly not the case.

                          1. -1

                            Yes we are talking at cross purposes. I’m making a very specific claim that should help users with regexes (based on 15+ years of using multiple engines in all sorts of applications), and you’re talking from the implementer’s perspective.

                            The claim is often ignored and shows up in practice.

                            I believe you’re making it more complicated than it needs to be for users. Computational complexity is the thing that matters for users of regexes regarding performance. I challenge someone to point out specific applications and use cases where that’s not the case – I gave a whole bunch of examples.

                            If you’re not naming those use cases, then you’re not getting my point.

                            Writing the regex engine doesn’t mean you’ve used it in a wide variety of applications. I explicitly said you know hundreds of things about regexes that I don’t – I’m pointing out the high-level bits for users.

                            And you are contradicting yourself, saying it does not “fall out”, except when it does fall out for re2c. I’m not saying ripgrep should scale like this – I’m pointing out a difference in theory that’s observed in practice.


                            I think you are trying to play “the expert” because you wrote it. But ironically users often have different insights into software than the author. That is why I write all these tests, benchmarks, and benchmarks against Oil. Simply writing the software doesn’t give me complete authority on it – it has to be observed from the outside, which tests and benchmarks accomplish.

                            https://www.oilshell.org/release/0.8.pre6/

                            Moreoever, it has to be situated in applications. I specifically look at how users use the shell, e.g. Linux distros and autocompletion scripts. Observing it from the inside isn’t enough. It gives you a limited view of the software, even if you wrote every line of it.


                            Also, Egg expressions are explicitly designed to help users with this problem. They make syntax and semantics correspond (to the degree possible), and computational complexity is essentially the most important semantic aspect of regular expressions. Linear time and constant space is why I use them, and it improves real software (Oil’s parser vs. bash and zsh).

                            In other words, I’m not making a big deal out of it just for fun, or because I have a beef with you. It’s part of the Oil project and something I’ve been working on for many years.

                            1. 9

                              I am not a moderator on lobste.rs, but if I were, I would have a word with you. Accusing burntsushi of “playing the expert” is hostile and aggressive, and completely unwarranted. We are gifted that he is willing to share his deep study and understanding with us, both as world-class libraries and in conversation.

                              1. 4

                                Computational complexity is the thing that matters for users of regexes regarding performance.

                                Not only have I never disputed this, I’ve never said anything that even remotely comes close to disputing it. Like I said, you’re generalizing my comments to give it a lot more scope than what I had actually written. To be clear, I absolutely agree with this generalized advice to end users. That’s why I wrote a regex engine that descends from RE2.

                                I don’t really know what to say to the rest of your comment. But if you’re only point is that “understanding computational complexity is really important for end users writing regexes,” then I’m going say, “yeah, so? What in the heck does that have to do with what I said?”

                                I don’t know what it is I’ve said that has caused you to dig into this rabbit hole. I really don’t. I just re-read my comments and I just cannot understand how we got here.

                                And I don’t mean to “play the expert” as in “respect my authority.” I brought up my credentials as if to say, “no, actually, you don’t need to explain the basic computational properties of regexes to me.”

                                1. -2

                                  Yeah I think we’re disagreeing on the intuition. And while I respect your unique viewpoint as the implementer of an engine (and acknowledge I learned many things from the discussion), I disagree with a lot of the intuition you laid out.

                                  At least 3 times in this discussion when I go back to the sources, my intuition has panned out. I may have said some things that are incorrect around the edges, but they turned out to be more correct than the nitpicking.

                                  You and other seems to be eager to nitpick when I offer general advice. The advice is aimed at casual users of regex who may get the false impression that they are slow. My point is that they are applicable to more situations than most people think (including syntax highlighters, used appropriately).

                                  Examples:

                                  • I suspected backtracking was the issue. A few people rejected it. When I asked for clarification (and I was open to new information) it was stated that the reason that Sublime’s engine is faster than the syntect one is because it doesn’t backtrack outside the engine. That’s a different form of backtracking, so sure you can jump on it, but I already acknowledged the difference. I think we both acknowledge the same possibilities but our intuition is different, and you seem to think yours is more correct.
                                  • When I say “fast” capture matching, I meant linear time. Again you’re eager to say “no you can’t do that”. I’m still interested to hear the applications where linear time matching is too slow. I never saw a text editor where anyone complains about editing small files. Even the worst web-based editor can edit a small file. It’s always complaining about editing big files, which indicates a scaling problems. [1]
                                  • I was technically wrong about Hyperscan building a DFA, and you’re eager to jump on that. But when I went back to the source the #1 claim is simultaneously matching patterns and constant strings, so again I think my intuition is more correct than the nitpicking. It’s similar to stuff I’ve done before, but I didn’t go look at the details.
                                  • I didn’t go back and read the old lobste.rs conversation, but I’m pretty sure you didn’t think the scaling I showed with re2c was actually implemented anywhere. In other words I had to go do it to convince you.

                                  So basically we’re just thinking about it from different perspectives. I think your perspective is valuable but your intuitions don’t line up with mine, and that doesn’t mean I’m wrong.

                                  [1] To give another example of this, I recall Rob Pike complaining 10+ years ago that GNU grep is 10x too slow when LANG!=C. It was a longstanding performance bug in one of the most deployed programs in the world. But basically nobody cares, and the bug persisted because it’s still linear time. I’m still interested in applications where people care about a 10x constant factor. I’m sure some exist but it’s not something I’ve hit in 15 years of using many engines.

                                  Most software is slow, and regexes are fast. I’m thinking about it from a systems perspective, where you get 10x constant slowdowns all over the place, in multiple components.

                                  It’s similar in spirit to what I wrote here:

                                  https://old.reddit.com/r/ProgrammingLanguages/comments/gyf1l6/is_implementing_a_bytecode_interpreter_in_an/fta56fh/

                                  Using Python is an order of magnitude constant factor slower. It matters in some systems, and doesn’t matter in others. The nitpicking there, which is missing the point, is reminiscent of this thread!


                                  In both cases, I’m offering people rules of thumb for performance, based on experience. You can always nitpick a rule of thumb. It doesn’t mean it’s useful to do so, or even directionally correct. I’m happy to acknowledge inaccuracies as I have in every case.

                                  1. 5

                                    When I say “fast” capture matching, I meant linear time. Again you’re eager to say “no you can’t do that”.

                                    Ug. No I didn’t. I didn’t nitpick any rules of thumb. I was commenting on one specific instance.

                                    I am specifically going to avoid talking to you about regexes from now on. Conversing with you has been by far the most unpleasant part of my day. I’m not going to repeat that mistake.

                      3. 3

                        No, I meant that a lot of the algorithms fundamentally add time-cost to the other operations, too. In retrospect it sounds incorrect, I wish I could remember where I read it.

                        1. 9

                          It depends on the implementation. In the case of fancy-regex, it is a true hybrid. If there are no fancy features, then it defers to a fully finite automaton based regex engine. In the case of other regex engines, it depends. For a simple alternation of literals, any regex engine could pretty easily just use Aho-Corasick to avoid the much slower backtracking implementation. As things get more complex, if you aren’t a true hybrid, then yes, you will definitely pay for it.

                          There is give and take here. I hope to some day have a reasonably comprehensive regex benchmark where I could just point you to examples and make this conversation much simpler. :)

                  1. 0

                    This is super refreshing to read. I think the trend towards self hosting, Linux from Scratch, and designing your own processors, motherboards, and firmware are all fascinating and laudable pursuits, but there is value for many people in being able to treat infrastructure as composable building blocks.

                    1. 2

                      I would say those are orthogonal issues.

                      • Control vs. outsourcing
                      • proprietary vs. open source
                      • composable vs. ???

                      In other words people don’t self-host because they want something “noncomposable”. And open source stuff is usually more composable anyway, so I’m not sure what you’re getting at.

                      They self-host because they want control (and sometimes cost, which may or may not be accurate etc.)

                      1. 2

                        n other words people don’t self-host because they want something “noncomposable”. And open source stuff is usually more composable anyway, so I’m not sure what you’re getting at.

                        I’m getting at the value of helpful abstractions that allow people who would not otherwise be able to to build complex and interesting systems.

                        Have you ever run an ElasticSearch cluster? It’s not easy and it’s REALLY easy to think you can and lose all your data.

                        A managed service not only encapsulates ease of installation but also best practice around operational safety, backups, etc.

                        1. 1

                          Sure, that is a reasonable opinion… but I have trouble getting there from the original comment. Whether ElasticSearch is hosted or not doesn’t affect “composability”

                          1. 3

                            You’re right that was a poor choice of words. I’ll try to think up the perfect turn of phrase.

                            1. 1

                              I think it may come down to containerization or not. For better or worse, containers are more composable because the state is more isolated.

                              Hosted services are also isolated in that you can’t peek inside (again, for better or worse). But it seems like most people are self-hosting with containers these days. There’s a spectrum.

                              I agree composability is a desirable property but I aim to achieve that without relying on too many cloud services. I guess one way to do that is to only use cloud services with commodity interfaces, e.g. web hosting, SQL, etc. Rather than services which there is only of like BigQuery, etc.

                              1. 2

                                Containerization is one useful abstraction that can definitely help people achieve solutions quickly, but depending on the nature and operational characteristics of the system being containerized, that abstraction only gets you one step of the way towards solving your problem.

                                I’m sure there’s an ElasticSearch container, but will that help you understand how to operate it with 100% confidence when you can lose your entire data set if you unintentionally perform certain operations when you don’t have sufficient quorum?

                      2. 2

                        I think that’s a pretty ridiculous take. Nobody is proposing you should build your own operating system just that you can’t build a business just gluing other people’s products together.

                        1. 2

                          I think your response is also a straw man. For most software businesses, the value is not in having their own high-availability DB setup or load balancer or any of the other things that the big IaaS providers provide, but in the application that they develop on top of those services.

                          1. 1

                            I think the trend towards self hosting, Linux from Scratch, and designing your own processors, motherboards, and firmware

                            This is the straw man. :)

                            For most software businesses, the value is not in having their own high-availability DB setup or load balancer or any of the other things that the big IaaS providers provide, but in the application that they develop on top of those services.

                            Nobody is saying make your own load balancer, but RUN your own load balancer.

                            1. 1

                              But even just running your own load balancer, replicated DB, etc. has a cost that can often be better spent focusing on the application itself.

                          2. 1

                            I was using an extreme case to illustrate a point.

                            Wow the negativity bias around this topic is stunning :)

                            1. 2

                              The major providers are / are bound up in entities that exercise power on the scale of nation-states, and an unfathomable number of lives are affected by how their eating of the entire economic possibility space plays out. Meanwhile, it slowly begins to dawn on much of the heretofore quite privileged technical class that their lives are just as contingent and their livelihoods will not be spared once the machinery they’ve helped build finishes solving for the problem of their necessity.

                              So, like, of course there are negative feelings.

                              1. 1

                                You’ve invented quite the end game for yourself there!

                                Will there be job reductions and resultant economic pain as a result of the move away from the data center and towards more cloud/managed services? Hell yes there will be!

                                But those who want to work in this business will find ways to adapt and continue to add value.

                                I’ve been working in technology for ~32 years. This doesn’t make me magical or omniscient or even smart but what it does make me is a witness to several waves of seismic change.

                                I came into the job market in the early 90s when DEC was imploding, PCs were ascendant, and the large expensive workstations vendors were dead companies walking but didn’t realize it yet.

                                Everyone thought the world would end and we’d all be out of work too.

                                Will it be hard? Yes. Will there be a lot of people who can’t or don’t want to adapt and will be left behind? Undoubtedly. Is that bad? Yes. However it’s the way our industry works and has since its inception.

                                We are all turning the crank that drives the flywheel of increased automation, whether we administer our own database clusters or not. The move to managed and cloud definitely represents a notable pinch point, and we’ll see how painful the transition will be, but it’s one paradigm shift in an industry that creates paradigm shifts for a living.

                                I’ve actually thought for a while that in the longer term, as compute at scale becomes quite a bit smaller and even cheaper, we could see a move back away from cloud because when you can host your company’s compute cluster in a cube the size of a printer and we have algorithms that can encode and enact services at scale in an operationally safe way, the value cloud adds will dwindle.

                                I love my job, and I love this industry, and plan to continue playing in this pool until I die, whether someone’s willing to pay me for it or not.

                                I assert that the constant negativity many of us exhibit is neither necessary nor desirable and represents a kind of immaturity that we will eventually grow out of as our industry continues to mainstream.

                                We’ll see.

                                1. 1

                                  However it’s the way our industry works and has since its inception.

                                  I’d gently suggest this is sort of an admission that it’s not an endgame I’ve invented.

                                  I’ve actually thought for a while that in the longer term, as compute at scale becomes quite a bit smaller and even cheaper, we could see a move back away from cloud because when you can host your company’s compute cluster in a cube the size of a printer and we have algorithms that can encode and enact services at scale in an operationally safe way, the value cloud adds will dwindle.

                                  I’ve had similar thoughts, at various points along the winding path to where we are now, but I think in practice that it’s not just where the hardware lives but who owns it. And in practice the amount that the hardware’s owners are the hardware’s users instead of the companies that control the ecosystem is perpetually decreasing. Hobby-level undertakings of various sorts are vastly easier than they were a few decades ago, and an amazing range of tech is available to small-scale operators, but somehow none of this seems to be decreasing the net concentration of power.

                                  I assert that the constant negativity many of us exhibit is neither necessary nor desirable and represents a kind of immaturity that we will eventually grow out of as our industry continues to mainstream.

                                  I would in many ways prefer to see our industry destroyed and the ashes thoroughly salted, so I suppose it is safe to say that we fall on very different sides of this question. :)

                                  1. 1
                                    However it’s the way our industry works and has since its inception.
                                    

                                    I’d gently suggest this is sort of an admission that it’s not an endgame I’ve invented.

                                    Forgive me but I don’t understand! I’m saying this ISN’T an endgame! Merely part of a larger cycle that we are in the throes of and have been forever.

                                    Sorry if I’m missing your point.

                                    1. 2

                                      Forgive me but I don’t understand! I’m saying this ISN’T an endgame! Merely part of a larger cycle that we are in the throes of and have been forever.

                                      Sorry, I think I should have been more clear. I’ve encountered the view that things are cyclical among a lot of the long-timer technical people I know, and I recognize its validity. I share it to a degree. I haven’t been in the game as long as you have (or most probably with anything like the depth of experience), but anyone who’s lived through a handful of major technical paradigm shifts along whatever axis should probably be able to recognize cycles in the system. All the stuff that was considered The Future when I was getting my start has been The Dead Past for long enough now that some of it’s coming back around in different costume for the 2nd or 3rd time.

                                      Two things, though:

                                      1. For an individual, the endgame is that the cycle will eventually dispose of you, your hard-won understandings, and the things that you have built, whether it takes one iteration or a dozen. To a first approximation, it will do this with no regard for the value of any person or thing. On one level that’s just the nature of life, but the technical economy has by now overdriven this process to an absurdly pathological extent. It burns people out and churns their work into dust at a rate and on a scale that is frankly anti-human, and it’s a reality that means ruthless mercenary calculation and a deep mistrust of the systems and cultures and communities we work within are more or less requirements for paying the rent.

                                      2. Once upon a time, I made a just-barely-workable and fairly satisfying living building some desktops, fixing some printers, running a mailserver, and hacking some e-commerce code. That job, that class of job, hasn’t utterly vanished, but it’s an endangered species. I probably wouldn’t know where to find one now if I needed it. I’ve been lucky and connected enough to migrate to other tiers of abstraction in other corners of things. But every thousand of that job that went away wasn’t replaced by a thousand jobs like I have now, and it definitely wasn’t replaced by a thousand jobs working on the stuff that made most of it obsolete from the point of view of the people who used to pay for it. In fact, a lot of the people who used to pay for it also don’t have those jobs now because instead they’re sharecropping for Amazon in an enclosed market that will eventually find them unnecessary.

                                      I guess what I’m saying just boils down to: The cycles operate within something larger. The something larger has a direction. The direction is one I have come to generally fear and loathe.

                                      1. 2

                                        There are still loads of generalist sysadmin/IT department jobs for places that aren’t tech-focused.

                          3. 1

                            The way people use “incorrect” here is really frustrating. What precisely about my statement does someone deem “incorrect” - the bit about Linux from Scratch being a laudable pursuit or the bit about being able to treat managed services as building blocks?

                            It doesn’t say “I disagree” it says “incorrect”.

                          1. 4

                            I think where it ends up is right:

                            In practice you would probably just compile a version that was passed a pointer to the type information, because the type information gives you size, alignment, and pointer information all in one place with only a single argument.

                            But, just as a curiosity, I think you could do a copy with only a size. The only member besides size that the typedmemmove source accesses is ptrdata, which, though the name sounds super general, only says how far into the object you need to look to be sure you’ve found all the pointers. Using that instead of the object size here seems to be an optimization: if ptrdata is 1, for instance, the runtime can quit worrying about possible pointers in an object after the first word, and if it’s zero it needn’t scan at all. You could write memmove code to conservatively act as if any word of the object might be a pointer, you’re just potentially wasting some effort.

                            The detailed data about which words of the allocation have pointers/need scanning comes from a GC bitmap that’s set up at allocation time. (You can just use an address to look a word up in this bitmap.) But that means that to allocate you need pointer/(no)scan information to set the bits. If allocating just to copy data you could in theory copy the GC bitmap from source to dest before you copy the data, but you’d still need the type’s alignment to get a properly aligned slot in memory and…yeah, maybe at that point we just pass a type pointer around instead.

                            This all makes me wonder what choices the team will make about compilation of generics: max speed of compiled code (by compiling as many optimized versions of the code as needed) vs. a dynamic implementation to avoid hurting compile time or binary size (so the resulting machine code looks like if you’d used interfaces). I can see the case for either: maybe these are a specialized tool for max performance for sorts, collections, etc. or maybe they’re mostly to make source better-checked and clearer. Or maybe we start with the dynamic approach (possibly quicker to implement?) then tune the generated output over future releases. Haven’t followed discussions super closely; if someone knows what has been said about this I’m interested.

                            1. 2

                              Yeah I wonder if there will be any implementation problems due to the combination of monomorphized generics and a potential explosion of GC bitmaps per type.

                              I think most of the languages monomorphized generics like C++ and Rust don’t have GC. Although I guess D is an exception. Not sure what they do exactly, but it probably helps that they have their own back end and not LLVM.

                              Not sure what C# does either. I think it has more VM support.

                              1. 2

                                .NET generics use monomorphization for value types and a shared instantiation for reference types.
                                The new() constraint is handled with reflection.

                                1. 1

                                  This might provide useful background on the topic.

                                2. 2

                                  I believe they were intentionally careful not to specify so that they could experiment & potentially offer multiple compile-time options.

                                  1. 2

                                    Yes, the design document’s implementation section explicitly leaves the question open (and is worth reading).

                                    Curious what they do!

                                  2. 1

                                    Besides reducing the code bloat and avoiding the need for a special intermediate representation of compiled but unspecialized generics, the dynamic approach has the added benefit (at least from the POV of Go’s goals) that it discourages excessively fine-grained abstractions (e.g., how Arc and Mutex have to be separately applied to get Arc<Mutex<T>> in Rust), because it would have too much runtime overhead.

                                  1. 13

                                    Huh? For 10 users you need a separate database and for 100 users you need 2 web servers??? I’m not sure if those numbers are meant to be taken literaly, but they’re off by orders of magnitude.

                                    We’re going to take our new photo sharing website, Graminsta, from 1 to 100k users.

                                    Yeah this seems totally wrong. I think back in the day imgur did this all on one box, and that’s how they were able to economically provide free photo hosting for so long (it seems to have gone south now, but in the early days it was very good).

                                    1. 8

                                      At $big_streaming_company we got to ~1M users with a few servers before needing to do anything clever.

                                      1. 4

                                        Totally agreed – though it does depend a bit on what he means by “N users”. Is it “N users who are using your site flat-out at the same time” or “N users in your database, but only 1 or 2 use the site once a month or so”. Those are very different, but even for the first option I suspect he’s still out by an order of magnitude.

                                        At a previous company we didn’t really have users, but we handled millions of page views on a single, relatively small database and a monolithic application with about 10 server nodes. We could handle about 300 requests per second if I recall correctly.

                                        1. 3

                                          I think it really depends on what you’re doing.

                                          At home, I just made https://droid.cafe/starlink. It’s running off a free f1-micro instance from google. Each page load takes roughly 40 microseconds of cpu time and is just serving up a few static files. Eyeballing it I think I could probably get rid of cloudflare (which I added out of curiosity not necessity) and still handle more than 10m daily users (computers are really fast these days). By upgrading to a faster instance, and minimizing the html/css/js, I bet I could push that to well over a billion a day. Of course at those scales I’d be paying a lot for geocoding services, but it would be 1 server managing to serve a webpage to most of the world every day.

                                          At work I don’t know that anyone has counted, but I bet we have roughly 1 production server per user (user defined as someone who directly interacts with our apps), that’s because each of our users gives our servers a lot of work to do, and our servers provide that users company a lot of value.

                                          Anyways, the real point is to not focus on the numbers.

                                          1. 2

                                            Yeah, we’ve got a particularly slow rails app serving 6 million users/day. It runs on 6 AWS instances, but we could just buy a server 4x or 8x bigger and skip the load balancing.

                                            1. 1

                                              At the bottom of the article it mentions:

                                              This post was inspired by one of my favorite posts on High Scalability.

                                              If you read the High Scalability post, you can see that a lot of the numbers given were ranges, not hard limits. In “Scaling to 100k Users”, the headings are:

                                              • 1 User: 1 Machine
                                              • 10 Users: Split out the Database Layer
                                              • 100 Users: Split Out the Clients
                                              • 1,000 Users: Add a Load Balancer.
                                              • 10,000 Users: CDN
                                              • 100,000 Users: Scaling the Data Layer - caching, read replicas

                                              High Scalability’s article has:

                                              • 1 User - 1 machine
                                              • Users > 10 - Separate DB and app server
                                              • Users > 100 - Store data on RDS
                                              • Users > 1000 - Elastic Load Balancer with 2 instances , multi AZ for app servers, standby database in another AZ
                                              • Users > 10,000s - 100,000s - Read replica, CDN, maybe caching, autoscaling
                                              • Users > 500,000+ - Autoscaling groups, caching, monitoring, automation, decouple infrastructure, maybe Service Oriented Architecture (SOA)
                                              • Users > 1,000,000+ - Requires Multi-AZ, Load balancing between tiers, SOA, S3+CloudFront for static assets, caching in front of DB.
                                              • Users > 10,000,000+ - Data partitioning/sharding, moving some data to specialised DBs
                                              • Users > 11 Million - More SOA, Multi-region, deep analysis of entire stack.

                                              If you read Scaling to 100k Users with a > instead of an = then it is slightly more understandable (though splitting out the clients at 100 users doesn’t make a lot of sense to me).

                                              1. 6

                                                Right now - today - you can comfortably serve > 11 million users off one server in a good colo.

                                                There are smaller systems with decade+ uptime using this approach.

                                                IMO most of these practices are about altering your risk profile rather than your performance profile (which is also important!). The risk profile of a single server in a single DC is unacceptable for many, many businesses.

                                            1. 0

                                              I’m still quite concerned that some unchecked over engineering is going on. There may be good reasons other shells didn’t need to be translated from python to c++ to run at efficient speeds.

                                              1. 2

                                                But HTML5 parsers were translated from Python to C++. The main challenge was to specify it, not to implement it. I think HTML5 is the project most analogous to Oil.

                                                1. 1

                                                  Wow I didn’t know that HTML5 parsers were translated from Python! That is very related. Do you which browsers/engines did that? I couldn’t find anything after several queries like “html5 parser prototype python”

                                                  Another analogy I would make is that it’s a common goal for languages not to be defined by their implementation. Languages like PHP and Perl 5 are essentially defined by one implementation. But Rust has an effort to make a canonical version of the grammar:

                                                  https://github.com/rust-lang/wg-grammar

                                                  For comparison, Go has a grammar in its spec, but it’s non-executable (and it’s also a simpler language syntactically).

                                                  So both OSH and Oil should be independently implementable, and the combination of DSLs re2c + ASDL + Python for OSH and pgen2 for Oil ensures that the languages don’t get tied to a particular implementation. Hand-written parsers written in C tend to grow a lot of unintentional hairs on them. (strings as buffers vs. strings as values)

                                                  1. 1

                                                    Hmm, I can see how it might have helped with rapid prototyping.

                                                  2. 1
                                                    1. 1

                                                      @andyc Regardless, if you’re interested in performance, the first idea that comes to mind is it might be worth the added code to implement some popular and relatively simple external programs like cat and ls as shell builtins; fork + exec is very expensive, and many shell scripts I feel don’t make it a point to avoid this as much as possible.

                                                      Plus, in the case of ls, you’ve got Python to help out with the cross-platform bits, so most of the battle is already won. Although another major pain point here is that many rely on parsing the output format of these programs… then the BSD vs GNU vs POSIX implementations bite you. Multiple paths you could take here: implement all three and autodetect platform to branch, or standardize on “The Oil Shell ls” and make it a feature switch, introduce Oil-specific APIs to expose this kind of information, etc.

                                                      1. 1

                                                        I never said it was. I just feel that if you had written it in C++ from the start, you could have skipped a lot of code that exists for no other reason. I guess saying that doesn’t help much, but its my honest opinion.

                                                        1. 1

                                                          Please read the FAQ I linked. It was started in C++ – second sentence.

                                                          Also read the bit about implementations not being specifications: https://lobste.rs/s/ct9kgg/oil_0_8_pre6_pure_bash_c#c_yekrzz

                                                    1. 2

                                                      Very cool, I went to try this out. osh 0.8.pre6 compiled easily.

                                                      Seems osh’s read builtin is not yet up to feature parity with bash (4+? not sure); I tried running my own icd-bash and of read -rsN1, osh doesn’t like -s or -N (it says it doesn’t accept those flags). However, posix icd works well.

                                                      In a similar vein there’s also fff which osh dies on:

                                                      $ osh ./fff
                                                            ((BASH_VERSINFO[0] > 3)) &&
                                                            ^~
                                                      ./fff:1102: fatal: Expected array or assoc in index expression, got value.Undef
                                                      

                                                      Also, the most complicated bash (4.4+) program I’m currently aware of is bashtop. Granted, it’s not pure bash; it requires python3 psutil and GNU sed. @andyc, if you can get osh to run that, that would be extremely impressive.

                                                      1. 1

                                                        Thanks for testing! I made note of the icd issue here:

                                                        https://github.com/oilshell/oil/issues/770

                                                        BASH_VERSINFO is a common incompatibility, and I usually just edit it out. I think Crestwave has tested fff as well, but I don’t think it works entirely yet.

                                                        I just edited out version checks for bashtop, and then ran into the similar associative array / array usage issues.

                                                        https://www.oilshell.org/release/0.8.pre6/doc/known-differences.html#values-are-tagged-with-types-not-cells

                                                        I think bashtop could run just like mal Lisp does. The patches would be very similar and improve the program! If you or anyone has time for that I would help out on Zulip :) If the error messages are confusing or there are interpreter bugs I can fix them.

                                                        bashtop does look quite substantial and I will add it here: https://github.com/oilshell/oil/wiki/The-Biggest-Shell-Programs-in-the-World

                                                        Although neofetch is more like twice as big at 10K lines and it runs under OSH :) After minor patches


                                                        Added an issue for bashtop: https://github.com/oilshell/oil/issues/776

                                                        more such issues: https://github.com/oilshell/oil/labels/should-run-this

                                                        1. 1

                                                          Yep, I did indeed see that osh was able to run neofetch (congratulations!). By complicated, I didn’t mean LoC… bashtop certainly does a lot more complicated drawing, at least. I’d assume neofetch is mostly a bunch of conditionals and platform-specific acrobatics.

                                                      1. 1

                                                        Is there a comparison somewhere of Oil vs Rc?

                                                        1. 2

                                                          Well rc is not POSIX or bash compatible, and Oil is, so that’s a huge difference. If you’re doing something in particular with rc that you’d like to do with Oil, I’m interested.

                                                          1. 1

                                                            As I understand it, Oil as a program implements POSIX and bash languages, but also implements a new language that is meant to be better (which is basically the point of the project).

                                                            Rc is currently the main thing I see pointed to if you want to write shell scripts but have the language be more sane. So I guess I’m wondering about comparison of Rc the language to the “new” Oil language.

                                                        1. 2

                                                          @andyc, I don’t know if it’s encouraging for you or not, but the longer this project goes, the more excited I am to use it. Right now I think it’s still a bit “raw” for me, but I’m really looking forward to using it.

                                                          1. 3

                                                            Thanks, yeah it’s not super surprising to me that it’s raw for end users. It’s sort of like if you build a C compiler from scratch – compiling libc is the bare minimum that somebody needs to do anything with it, but being able to so is a huge amount of work over writing a basic compiler!

                                                            Distros do a significant amount of work to make shells “usable”, including adding autocompletion, and that has to be done for OSH too. This isn’t hard because it’s very bash compatible, but it’s still work that someone has to do.

                                                            That said, it’s easy to test it out on real shell scripts now, and such tests often shake out good bugs. Obligatory “help wanted” :)

                                                            http://www.oilshell.org/blog/2019/12/09.html#help-wanted

                                                            https://github.com/oilshell/oil/issues?q=is%3Aissue+is%3Aopen+label%3A%22help+wanted%22


                                                            I’m still looking for a “killer feature” and I think that could be tracing or debugging (better than sh -x). However I think that naturally comes after speeding up the interpreter.

                                                            I think the interactive use will take a bit longer, since it has to bubble up through distro authors as mentioned, and eventually people writing tens of thousands of lines of shell code like oh-my-zsh, powerlevel10k, etc. In other words it takes a lot of people to make something that people can just use and mostly forget about!

                                                            Of course, the other “killer feature” was the Oil language, which exists and you can try it (in the slow implementation). However I think it will take many months to translate to C++, whereas OSH is within reach in 2020. So I’m looking for a different killer feature besides the Oil language to do first :)

                                                            I think using it continuous builds may be a good one, since they are often a mix of shell and YAML that is very difficult to debug. I wrote an alternative job runner in shell for Oil that works very well:

                                                            http://travis-ci.oilshell.org/jobs/

                                                          1. 33

                                                            This is starting to look like bullying. I think the post is fine, but posting it here to point and gawk isn’t. :(

                                                            1. 25

                                                              If someone makes bold claims about a project, then there’s nothing wrong with pointing out when those claims aren’t accurate.

                                                              1. 36

                                                                If we had a post for every software project that was still shit in spite of bold claims, the frontpage would be worthless.

                                                                1. 13

                                                                  It’s fair to say we don’t need a post for every piece of software that isn’t living up to its claims, but that doesn’t make this bullying.

                                                                  1. 17

                                                                    I think there are two differences here:

                                                                    1. @cadey wrote it but didn’t post it. I’m assuming @calvin shared it because he thought it was genuinely interesting content, not to bully V.
                                                                    2. It’s not just that V is still shit in spite of bold claims, it’s that V is still shit in spite of bold claims and incredibly toxic behavior by its community. The interplay between all three- toxicity, grandiosity, vaporware- makes this analysis especially interesting to me.
                                                                    1. -8

                                                                      What toxicity are you talking about?

                                                                      If V is vaporware then how are so many of us using it for our projects? https://github.com/vlang/v

                                                                      Here’s a cool one: a first-person shooter game bot https://github.com/EasyHax/Vack

                                                                      1. 16

                                                                        What toxicity are you talking about?

                                                                        You, in this thread, right now.

                                                                        This is the only time I’m going to reply to you. And I only replied because nobody else has explicitly called out your hostility.

                                                                        1. -4

                                                                          Defending V from misleading attacks – so misleading that the author has just retracted her original post – is not exactly a defensible definition of “toxic”.

                                                                          I don’t like seeing slander against important projects I care about. Surely you can understand!

                                                                          1. 13

                                                                            All I can see here is that the V community lives up to its infamy by bullying someone into taking down a critical piece on it.

                                                                            1. 15

                                                                              I retracted the post because of people like you. It wasn’t just you, but I just wanted an end to it.

                                                                              1. -5

                                                                                If your post would have been factual then I wouldn’t have criticized it…

                                                                                I hope you are in a better headspace for your future posts. I’m sure many of us would love to read more articles about WasmCloud, which is honestly one of the coolest projects I’ve ever heard of; would solve many important problems at once, and do so without reinventing the wheel.

                                                                                (Dear readers: FWIW I didn’t ask for the post to be taken down. I was arguing against its content.)

                                                                    2. 3

                                                                      Did I miss some drama about this project?

                                                                      1. 3
                                                                      2. -3

                                                                        Which claims aren’t accurate, specifically?

                                                                        1. 8

                                                                          As far as I can tell, compiling 1.2 million lines of code in a second (second bullet point). I would also like to see some citations backing up the safety guarantees with respect to C to V translation. C has way too many gotchas for a bold claim like that. Also, the safety guarantee with the C and Javascript backends.

                                                                          1. -1

                                                                            You can download the project, generate 1 million lines of code using tools/gen_1mil.v and build it in 1 second with v -x64 x.v

                                                                            “ safety guarantee with the C backend” makes no sense, because you write the code in V, not in C. V won’t allow you globals, or shadowing etc. C can be thought of as an assembly language.

                                                                            1. 5

                                                                              If only this benchmark actually worked. First I compiled the generator using:

                                                                              ./v -prod cmd/tools/gen1m.v
                                                                              

                                                                              This already takes 1.3 seconds. I then ran the resulting binary as follows:

                                                                              ./cmd/tools/gen1m > big.v
                                                                              

                                                                              The size of the resulting file is 7.5 megabytes. I then tried to compile it as follows:

                                                                              ./v -prod big.v
                                                                              

                                                                              This takes 2.29 seconds, produces 7 errors, and no output binary. This is the same when using the -64 option, and also when leaving out the -prod option.

                                                                              Even a simple hello world takes longer than a second in production mode:

                                                                              v $ cat hello.v
                                                                              fn main() {
                                                                                  println("Hello world")
                                                                              }
                                                                              v $ time ./v -prod hello.v
                                                                              
                                                                              ________________________________________________________
                                                                              Executed in    1,44 secs   fish           external
                                                                                 usr time  1372,26 millis  350,00 micros  1371,91 millis
                                                                                 sys time   64,93 millis   28,00 micros   64,90 millis
                                                                              

                                                                              In debug mode it already takes 600 milliseconds:

                                                                              v $ time ./v hello.v
                                                                              
                                                                              ________________________________________________________
                                                                              Executed in  666,51 millis    fish           external
                                                                                 usr time  613,46 millis  307,00 micros  613,15 millis
                                                                                 sys time   52,61 millis   26,00 micros   52,59 millis
                                                                              

                                                                              With -x64 a debug build takes about 2 milliseconds.

                                                                              Based on the above I find it hard to believe V would really be able to compile over a million lines of code in less than one second; even without optimisations enabled. I hope I am wrong here.

                                                                              The hardware used is as follows:

                                                                              • CPU: AMD Ryzen 5 1600X
                                                                              • RAM: 4x Kingston KHX2400C15D4/4G, a total of 16GB
                                                                              • SSD: Samsung 860 EVO 250GB
                                                                      3. 13

                                                                        maybe, but as icefox said I also feel like christine is giving V too much PR with it

                                                                        1. 5

                                                                          I agree that it’s unnecessary, though I can’t decide if it’s really bullying.

                                                                          I’ve heard about V two times since the last post hit lobste.rs. One time I posted Christine’s observations, one time someone else did. I think the message is out there, and at this point, it’s really only noteworthy if something changes.

                                                                          1. -5

                                                                            What message is out there? That the misleading attacks on V continue?

                                                                          2. 5

                                                                            Yeah there is some interesting technical content in the post, but the tone is offputting.

                                                                            1. 7

                                                                              Abuse that gets a lot of “positive engagement” is deemed entertainment.

                                                                              1. 3

                                                                                I was amused to see it tagged “performance”, wonder if the pun was intentional on the submitter’s part.

                                                                              1. 27

                                                                                I am a very vocal person about systemd.

                                                                                With that said, I find the articles opening statements to be quite fair in all regards- However, it does seem to fall right into the trap of comparing systemd with sysvinit.

                                                                                Without fail whenever someone extolls virtues and waxes poetic on the subject of systemd being “easy” it is always with the preconceived notion that sysvinit was the alternative.

                                                                                My typical argument against systemd is precisely in that it’s so complex and ever changing as to be effectively a closed system; integration with systemd specifics ensures that there can never be a successor, we are locked in to systemd forever more. So it had better be damned near perfect architecturally; and given the compromises and nature of exploits I do not have faith that it is.

                                                                                evidenced by the lengthy but great run down of the events surrounding systemd and the recent system-down exploit.

                                                                                There were alternatives; runit being a good example, but now swapping out your init for any other will cause many bits of useful software (notably gnome, but more as time goes on) to no longer work.

                                                                                1. 13

                                                                                  Even without comparing it with anything. What valid reason is there to increase the scope of what is generally percieved as an init system by some 1000%?

                                                                                  I, like most people, like being able to define services just by creating a 4 line unit file rather than having those silly ad hoc old init scripts. But why not doing just that? Why do I all of the sudden need an application just to check logs?

                                                                                  1. 5

                                                                                    Counterpoint: with systemd the logs are now collected in a pretty consistent way instead of spread eccentrically around /var/log. I find it convenient that I don’t need to define what my logfiles are going to be called or what rotation will occur, etc. Those aren’t interesting problems to me.

                                                                                    1. 5

                                                                                      the logs are now collected in a pretty consistent way

                                                                                      Few adjectives are missing: error-prone, inefficient, insecure. You can insert them after pretty and then your sentence is 100% spot on.

                                                                                      Links:

                                                                                      If you ask me if I want to trade the previous logging stack to this, I would say no.

                                                                                      1. 2

                                                                                        That’s your prerogative. I have not experienced any of those issues but have experienced issues with the traditional approach. In any case, all systems have faults.

                                                                                  2. 7

                                                                                    Most likely a system such as systemd is not correct or even possible to implement correctly because they’re not doing any formal verification to ensure every D-bus component conforms to their agreed upon interface.

                                                                                    I’m just waiting for a cardhouse to fall.

                                                                                    1. 2

                                                                                      many bits of software, you mean

                                                                                      1. 1

                                                                                        Did any distros actually use runit?

                                                                                        I used daemontools for a tiny project for awhile, and while it’s very elegant, I got the sense that you were also swimming upstream. It was more a thing I used on top of a distro (on top of sysv init or systemd), not really a replacement.

                                                                                        I don’t know the details but I’d hope and expect that the projects that integrate with systemd would accept patches for non systemd inits.

                                                                                        1. 8

                                                                                          Did any distros actually use runit?

                                                                                          Void uses it, Artix recently added it as an option, and Project Trident recently switched over to Void as their base so I believe they also use Runit now too.

                                                                                          I don’t know the details but I’d hope and expect that the projects that integrate with systemd would accept patches for non systemd inits.

                                                                                          I doubt it. Most programs I’ve seen that depend on systemd often have it as a hard requirement. Which forces users to use tools like elogind or consolekit or eudev, or patch the program themselves to not use systemd. It’s a trivial thing when using a distro like Gentoo, but I’m sorry for those who use distros like Debian because it’s near impossible to escape from systemd there.

                                                                                      1. 1

                                                                                        I like how the page says “Wuffs is a memory-safe programming language and a standard library written in that language.”, and the README for Wuffs says “…while technically possible, it is unlikely that a Wuffs compiler would be worth writing entirely in Wuffs.”.

                                                                                        1. 2

                                                                                          I don’t see any contradiction there. There are many reasons that the stdlib could be suitable for Wuffs but the compiler itself isn’t. Most compilers are not bootstrapped for years, e.g. Go took 8-10 years I think. The compiler was written in C but the stdlib was in Go.

                                                                                          1. 1

                                                                                            You’re completely right, I completely thought I read something else.

                                                                                        1. 2

                                                                                          This is really cool, but also doesn’t answer the question of why in the world you care about pretty-printing the output of your compiler at all…?

                                                                                          1. 4

                                                                                            I assume to make debugging the intermediate output easier.

                                                                                            1. 4

                                                                                              Not following – have you ever worked with a code generator that outputs say everything on one line?

                                                                                              Those code generators quickly get fixed, or don’t get used at all.


                                                                                              edit: Looking more closely, I think the issue is that they wrote the original compiler assuming that its output would be run through a separate pretty printer. That is, they wrote it without regard to formatting.

                                                                                              So it’s reasonable to ask why they wouldn’t just fix the original code to output indented text.

                                                                                              In other words, I think that code generators should always output readable code (within the constraints of the problem, e.g. parse tables). But that doesn’t mean they should be pretty-printed with a separate tool!

                                                                                              1. 2

                                                                                                Maybe a better question is why would you care about the performance of your compiler in “pretty-print-mode” when the default should be “fast mode” and pretty mode is only used when you’re sending the compiler output to something other than another compiler?

                                                                                                1. 2

                                                                                                  Having two modes is overkill – who is going to bother to set that up in their build system?

                                                                                                  That said, I agree the architecture described in this post is kinda weird:

                                                                                                  The ‘unformatted’ C code, by construction, already has line breaks in sensible places. The formatter only needs to fix up the horizontal formatting (i.e. indentation) due to nested {} braces and () parentheses.

                                                                                                  I don’t think it’s that hard to output correctly indented code in the first place. I’ve done this in several code generators. It might be annoying if your meta-language doesn’t have multiline strings… I think theirs is Go, and it might not?

                                                                                                  Wrapping code is a little trickier, but also not hard to reasonable job in the tool itself. I found a nice language-independent heuristic in a code generator I borrowed.

                                                                                                  1. 2

                                                                                                    Go definitely has multiline strings, via backticks.

                                                                                                  2. 2

                                                                                                    If the user wants the output pretty printed during debugging for example they can just pipe it through their favourite formatter. No modes necessary.

                                                                                                  3. 2

                                                                                                    Not following – have you ever worked with a code generator that outputs say everything on one line?

                                                                                                    One line? no, but the output of most code generators isn’t particularly pretty.

                                                                                                    Most code generators only have output to assist debugging serious issues, and most users don’t care too much about the output of code generators – to the point that they often never even materialize the generated code, and just feed it directly into the compiler. (This is, essentially, what a macro system like Lisp’s, Rust’s, or even the C preprocessor does)

                                                                                                1. 5

                                                                                                  If you’ve read this far and are thinking “If Redo is so great, how come it hasn’t taken over?”

                                                                                                  I want a build system that can help me with the following:

                                                                                                  • build variants – e.g. don’t do “make clean” between debug / release / ASAN builds. GNU make has some tortured support for this, but it requires you to use it correctly, and I haven’t seen many people do it (I think it’s VPATH or something). AFAIK redo doesn’t help you with this any more than GNU make does – probably less.
                                                                                                  • Writing correct incremental builds, e.g. specifying all your dependencies. I don’t want a tradeoff between fast builds and correct builds. GNU make doesn’t help you with this enough, and neither does redo AFAIK.
                                                                                                  • Correct parallel builds. I think apenwarr’s redo does better here, but the original redo doesn’t. But I haven’t seen a real convincing demonstration of that in any case. I think the declarative graph model helps you analyze bottlenecks in your build (critical paths), but redo’s non-declarative model may thwart that to some extent.

                                                                                                  In other words the whole point of a build system is to let you write something that’s fast and correct (which is not easy), and neither GNU make or redo helps enough with that.


                                                                                                  FWIW I sort of made fun of the Android build system circa 2015 here for using GNU Make (they no longer use it):

                                                                                                  https://lobste.rs/s/znrsap/tech_notes_success_failure_ninja#c_l04v6d

                                                                                                  ButI didn’t mention that it was a very parallelizable build. It was much more parallelizable than Firefox’s build as I recall. Android was building much more but it could saturate 32 cores easily. Other build systems do not do this – you have to try to get a really parallelizable build, and that’s what I want a build system to help me with.

                                                                                                  As I mentioned there, I’m probably going to switch the build to Ninja + a shell or Python generator. This recent post was very cool

                                                                                                  https://lobste.rs/s/952gdv/merkle_trees_build_systems

                                                                                                  I think that architecture has a lot of potential for hard build problems in the future. Some context on Oil’s problem here: https://github.com/oilshell/oil/issues/756


                                                                                                  In other words I think redo is fine and cool but it doesn’t help enough with hard build problems. You could make an analogy to Forth. Sure it’s more elegant for certain problems, but if it falls down for harder problems, then it’s not a net win. It has its place, but it’s not surprising that it’s not more popular.

                                                                                                  1. 3

                                                                                                    build variants – e.g. don’t do “make clean” between debug / release / ASAN builds. GNU make has some tortured support for this, but it requires you to use it correctly, and I haven’t seen many people do it (I think it’s VPATH or something). AFAIK redo doesn’t help you with this any more than GNU make does – probably less.

                                                                                                    The easiest way to do this is to have something like

                                                                                                    .PHONY: %.var
                                                                                                    .PRECIOUS: %.var
                                                                                                    %.var:
                                                                                                    	@echo "$($*)" | cmp -s - "$@" || echo "$($*)" > $@
                                                                                                    
                                                                                                    %.o: %.c CC.var CFLAGS.var
                                                                                                    	$(CC) $(CFLAGS) -c -o $@ $<
                                                                                                    

                                                                                                    This will 100% work, but it takes some discipline to specify all used variables as dependencies.

                                                                                                    Writing correct incremental builds, e.g. specifying all your dependencies. I don’t want a tradeoff between fast builds and correct builds. GNU make doesn’t help you with this enough, and neither does redo AFAIK.

                                                                                                    Yeah, to do something like this in make you have to do something like

                                                                                                    $(OBJS) := # ...
                                                                                                    $(DEPS) := $(OBJS:.o=.d)
                                                                                                    
                                                                                                    %.o: %.c
                                                                                                    	$(CC) $(CFLAGS) -MMD -c -o $@ $<
                                                                                                    
                                                                                                    -include $(DEPS)
                                                                                                    

                                                                                                    but of course this only works for C files. For a more comprehensive treatment of this problem, have a look at tup. It puts an overlay FUSE filesystem on your source directory to track what objects use what files. One downside may be that its limited syntax makes it less useful as an all-in-one config/build tool than make is. If you use tup, you may end up needing to use something like autotools/cmake/meson to generate your tupfiles.

                                                                                                    Correct parallel builds. I think apenwarr’s redo does better here, but the original redo doesn’t. But I haven’t seen a real convincing demonstration of that in any case. I think the declarative graph model helps you analyze bottlenecks in your build (critical paths), but redo’s non-declarative model may thwart that to some extent.

                                                                                                    I believe if you have proper dependency tracking, then this becomes trivial to do. Well-written makefiles tend to parallelize extremely well, but only if the author has included all the dependency info.

                                                                                                    1. 2

                                                                                                      Yeah, the short way to say it is that the build should fail if the Makefile is broken. Bazel has that property, and the linked Merkle tree post describes a system that appears to have it as well.

                                                                                                      In other words, the build tool should help you write a correct build config. GNU make doesn’t help you at all – instead you are left with a bunch of obscure rules that you’re not sure if you followed.

                                                                                                      You can state the rules, and maybe follow them yourself, but if I give you 5,000 lines of someone else’s Make, then good luck.

                                                                                                      On top of that, make can’t be statically parsed, so you can’t write a lint-type tool for it. I don’t think redo can be either. You can statically parse shell (which is what Oil does) but redo has semantics on top of shell, that occur after runtime substitutions.

                                                                                                      1. 2

                                                                                                        I tried tup, and liked it initially, but was ultimately put off by it. I don’t like that it requires a fuse module (heavy dependency, doesn’t work well on platforms that aren’t linux, kind of hacky). It also broke its promise to never screw up a dirty build.

                                                                                                        I don’t know what the solution is for projects that require complicated builds. I try to keep mine simple—list of source files converted to objects—so plain make can handle it, but sometimes that’s just not practical. Meson is decent, but not great. Cmake and autotools are hell. Language-specific build systems (cargo, dub, …) tend to be good, but inflexible.

                                                                                                        1. 1

                                                                                                          I tried tup, and liked it initially, but was ultimately put off by it. I don’t like that it requires a fuse module (heavy dependency, doesn’t work well on platforms that aren’t linux, kind of hacky). It also broke its promise to never screw up a dirty build.

                                                                                                          Yeah, I primarily mention it because it’s sort of the natural end-point of something like redo. I wonder if one could do something like this with ptrace. Does windows have an api for that? I wonder what the performance is like when compared to fuse.

                                                                                                          Cmake and autotools are hell.

                                                                                                          I agree. CMake does make windows builds better, but at the cost of its awful configuration language. I think there’s an urge to reach for a tool like them whenever one starts to have significant configuration for a project. I think Kconfig does a pretty good job, now if only it could get recursive dependencies :)

                                                                                                      2. 2

                                                                                                        but redo’s non-declarative model may thwart that to some extent

                                                                                                        It is non declarative, but after a full build, you get .dep.$name files that declare the build tree, which redo-dot or others implementation’s tools can make use of.

                                                                                                        Writing correct incremental builds, e.g. specifying all your dependencies. I don’t want a tradeoff between fast builds and correct builds. GNU make doesn’t help you with this enough, and neither does redo AFAIK.

                                                                                                        I fail to see how either fails at doing so: as soon as the full dependency graph is there, it is a problem that is solved by both?

                                                                                                        1. 2

                                                                                                          It’s easy to introduce bugs in Makefiles simply by leaving off a dependency. You add a dependency to the code but forget to update the Makefile. (the gcc -M stuff helps for C/C++ code only, though it’s not exactly a great mechanism)

                                                                                                          So the build still works in the sense that you’ll get some output file and will exit status 0, but the incremental build is subtly broken, and may remain that way for a long time.

                                                                                                          What I’m thinking of is more along the lines of what’s described here:

                                                                                                          https://lobste.rs/s/952gdv/merkle_trees_build_systems

                                                                                                          • Using something like bubblewrap to run build steps in a deterministic environment / lightweight container. If you leave off a dependency, you get a build error – file not found. Bazel does this and it’s very effective at enforcing the correctness of the build.
                                                                                                            • For speed, there could be an option to run without containers / chroots. But for changing the build description, the enforcement is very valuable.
                                                                                                          • Directory trees, not files, as dependencies. For many problems I suspect this coarse-grained solution may work better. Checking every file is tedious and causes a lot of stat() traffic on the file system.
                                                                                                          1. 1

                                                                                                            So not only about reproducing related files according to logical rules, but the entire directory tree with hashing to reproduce a filesystem image reproducibly (which might be a software project working directory), then provide a hash of the whole build.

                                                                                                            Sure, then Make and redo might be used for doing this, but it is not their doing nor default behavior.

                                                                                                            On a side note, redo tracks changes in dependencies with hashes put in .dep.$filename, but not of a whole directory hierarchy and just of the individual files.

                                                                                                        2. 1

                                                                                                          I’ve been using CMake for the past year and a half exactly because it checks all the boxes. I recommend using the Ninja generator alongside it - it’s parallel by default and significantly faster than Make.

                                                                                                          The one drawback of CMake is that you essentially have to treat the build system as its own part of the software that needs maintenance. I believe this tradeoff is well worth for larger projects.

                                                                                                        1. 1

                                                                                                          This is essentially the same idea behing Nixos and also my own package manager / package build tool - https://github.com/andrewchambers/hermes

                                                                                                          1. 2

                                                                                                            Yeah I think what it comes down to is who actually builds a quality package ecosystem. The build / package software is one thing, but building a high quality repository is 1000x more work.

                                                                                                            As mentioned in chat, Nix does have a lot of packages, but they don’t have a great story for Python packages on top of native packages (or R, node.js, OCaml, etc.). The Nix build for Oil is sort of in limbo because of that issue.

                                                                                                            All those language package managers have no connection to the native package manager. They just treat it as a Docker-like blob (which is why people use Docker – it doesn’t require them to fix other people’s crazy build systems. They can just paper over the problem).


                                                                                                            I followed the last link in the article and found this post (which I will submit as a top level post)

                                                                                                            http://blog.williammanley.net/2020/05/25/unlock-software-freedom-one-by-using-better-tools.html

                                                                                                            The challenge is the sheer amount of software to be packaged is tremendous. Having a complete view of the build graph requires converting every package to the same build system.

                                                                                                            The reason Docker is popular because it doesn’t require solving that. The convention in Google’s Bazel (mentioned in the article) is to throw out all the autoconf and GNU make and rewrite the build system from scratch. That works pretty well for C++ and code you wrote yourself, but not well for code that already has a quirky build system.

                                                                                                            Nix doesn’t require you to throw out everything, but I think it’s a little further toward that end of the spectrum.


                                                                                                            As usual the problem with changing a software ecosystem is a strong network effect… People are using Debian and Red Hat images, so developers write their build systems to work on those kinds of machines. They don’t work as well on Nix images – there’s more work you have to do to make it work. So whenever new people want to use those packages, they use whatever system the build system works on, which is something that looks like Debian or Red Hat.

                                                                                                            1. 2

                                                                                                              Oh I don’t think it’s really the same, because they mention they’re using apt2ostree:

                                                                                                              https://github.com/stb-tester/apt2ostree

                                                                                                              So it’s not totally a source build, and I think that’s actually a good way to start. It’s a middle ground to get something working.

                                                                                                              In other words, the ideal solution for build and deployment to me is something that’s as easy to use as Docker but as “correct” as Nix or presumably Hermes. But those two properties are in conflict. There are a bunch of tradeoffs to be made, and what I see in this post is pretty encouraging (I still need to try it)

                                                                                                              Other good links from the post:

                                                                                                              When I made an attempt at this problem 5+ years ago I looked at such tools, e.g. I remember Project Atomic. But it’s great to see the state of the art advancing. Ninja + OSTree seems like a promising combo. I think OSTree does the differential compression part, which is not easy.

                                                                                                              1. 1

                                                                                                                One thing to realize is the Nixos model would work with ‘regular’ packages if you just set DESTDIR to $out instead of PREFIX. You just need an extra mounting step with fuse to actually use the package.

                                                                                                                So yes, it is the same model. The way Nixos works is totally compatible with this approach without changing anything in the design of the package manager tool. This is something I hope to experiment with in hermes as an alternative package tree.

                                                                                                              1. 8

                                                                                                                Isn’t there a difference between functional code and side-effect-free code? I feel like, by trying to set up all of the definitions just right, this article actually misses the point somewhat. I am not even sure which language the author is thinking of; Scheme doesn’t have any of the three mentioned properties of immutability, referential transparency, or static type systems, and neither do Python nor Haskell qualify. Scouring the author’s websites, I found some fragments of Java; neither Java nor Clojure have all three properties. Ironically, Java comes closest, since Java is statically typed in a useful practical way which has implications for soundness.

                                                                                                                These sorts of attempts to define “functional programming” or “functional code” always fall flat because they are trying to reverse-engineer a particular reverence for some specific language, usually an ML or a Lisp, onto some sort of universal principles for high-quality code. The idea is that, surely, nobody can write bad code in such a great language. Of course, though, bad code is possible in every language. Indeed, almost all programs are bad, for almost any definition of badness which follows Sturgeon’s Law.

                                                                                                                There is an important idea lurking here, though. Readability is connected to the ability to audit code and determine what it cannot do. We might desire a sort of honesty in our code, where the code cannot easily hide effects but must declare them explicitly. Since one cannot have a decidable, sound, and complete type system for Turing-complete languages, one cannot actually put every interesting property into the type system. (This is yet another version of Rice’s theorem.) Putting these two ideas together, we might conclude that while types are helpful to readability, they cannot be the entire answer of how to determine which effects a particular segment of code might have.

                                                                                                                Edit: Inserted the single word “qualify” to the first paragraph. On rereading, it was unacceptably ambiguous before, and led to at least two comments in clarification.

                                                                                                                1. 7

                                                                                                                  Just confirming what you said: Did you say that Haskell doesn’t have immutability, referential transparency, or a static type system?

                                                                                                                  1. 3

                                                                                                                    I will clarify the point, since it might not be obvious to folks who don’t know Haskell well. The original author claims that two of the three properties of immutability, referential transparency, and “typing” are required to experience the “good stuff” of functional programming. On that third property, the author hints that they are thinking of inferred static type systems equipped with some sort of proof of soundness and correctness.

                                                                                                                    Haskell is referentially transparent, but has mutable values and an unsound type system. That is only one of three, and so Haskell is disqualified.

                                                                                                                    Mutable values are provided in not just IO, but also in ST and STM. On one hand, I will readily admit that the Haskell Report does not mandate Data.IORef.IORef, and that only GHC has ST and STM; but on the other hand, GHC, JHC, and UHC, with UHC reusing some of GHC’s code. Even if one were restricted to the Report, one could use basic filesystem tools to create a mutable reference store using the filesystem’s innate mutability. In either case, we will get true in-place mutation of values.

                                                                                                                    Similarly, Haskell is well-known to be unsound. The Report itself has a section describing how to do this. To demonstrate two of my favorite examples:

                                                                                                                    GHCi, version 8.6.3: http://www.haskell.org/ghc/  :? for help
                                                                                                                    Prelude> let safeCoerce = undefined :: a -> b
                                                                                                                    Prelude> :t safeCoerce
                                                                                                                    safeCoerce :: a -> b
                                                                                                                    Prelude> data Void
                                                                                                                    Prelude> let safeVoid = undefined :: Void
                                                                                                                    Prelude> :t safeVoid
                                                                                                                    safeVoid :: Void
                                                                                                                    

                                                                                                                    Even if undefined were not in the Report, we can still build a witness:

                                                                                                                    Prelude> let saferCoerce x = saferCoerce x
                                                                                                                    Prelude> :t saferCoerce
                                                                                                                    saferCoerce :: t1 -> t2
                                                                                                                    

                                                                                                                    I believe that this interpretation of the author’s point is in line with your cousin comment about type signatures describing the behavior of functions.

                                                                                                                    1. 4

                                                                                                                      I don’t really like Haskell, but it is abusive to compare the ability to write a non-terminating function with the ability to reinterpret an existing object as if it had a completely different type. A general-purpose programming language is not a logic, and the ability to express general recursion is not a downside.

                                                                                                                      1. 3

                                                                                                                        A “mutable value” would mean that a referenced value would change. That’s not the case for a value in IO. While names can be shadowed, if some other part of the code has a reference to the previous name, that value does not change.

                                                                                                                        1. 1

                                                                                                                          Consider the following snippet:

                                                                                                                          GHCi, version 8.6.3: http://www.haskell.org/ghc/  :? for help
                                                                                                                          Prelude> :m + Data.IORef
                                                                                                                          Prelude Data.IORef> do { r <- newIORef "test"; t1 <- readIORef r; writeIORef r "another string"; t2 <- readIORef r; return (t1, t2) }
                                                                                                                          ("test","another string")
                                                                                                                          

                                                                                                                          The fragment readIORef r evaluates to two different actions within this scope. Either this fragment is not referentially transparent, or r is genuinely mutable. My interpretation is that the fragment is referentially transparent, and that r refers to a single mutable storage location; the same readIORef action applied to the same r results in the same IO action on the same location, but the value can be mutated.

                                                                                                                          1. 1

                                                                                                                            The value has been replaced with another. It is not quite the same thing as mutating the value itself.

                                                                                                                        2. 2

                                                                                                                          From your link:

                                                                                                                          When evaluated, errors cause immediate program termination and cannot be caught by the user.

                                                                                                                          That means that soundness is preserved–a program can’t continue running if its runtime types are different from its compile-time types.

                                                                                                                          1. 1

                                                                                                                            If we have to run the program in order to discover the property, then we run afoul of Rice’s theorem. There will be cases when GHC does not print out <loop> when it enters an infinite loop.

                                                                                                                            1. 1

                                                                                                                              Rice’s theorem is basically a fancier way of saying ‘Halting problem’, right?

                                                                                                                              In any case, it still doesn’t apply. You don’t need to run a program which contains undefined to have a guarantee that it will forbid unsoundness. It’s a static guarantee.

                                                                                                                      2. 5

                                                                                                                        Thank you for bringing up this point. Unfortunately, “functional programming” is almost-always conflated, today, with lack of side-effects, immutability, and/or strong, static, typing. None of those are intrinsic to FP. Scheme, as you mentioned, is functional, and has none of those. In fact, the ONLY language seeing any actual use today that has all three (enforced) is Haskell. Not even Ocaml does anything to prevent side-effects.

                                                                                                                        And you absolutely can write haskell-ish OOP in e.g., Scala. Where your object methods return ReaderT-style return types. It has nothing at all to do with funcitonal vs. OOP. As long as you do inversion of control and return “monads” or closures from class methods, you can do all three of: immutable data, lack of side-effects, and strong types in an OOP language. It’s kind of ugly, but I can do that in Kotlin, Swift, Rust, probably even C++.

                                                                                                                        1. 2

                                                                                                                          Scheme, as you mentioned, is functional, and has none of those.

                                                                                                                          Why is Scheme functional? It’s clearly not made of functions:

                                                                                                                          Lisp Is Not Functional

                                                                                                                          A functional language is a programming language made up of functions

                                                                                                                          What defun and lambda forms actually create are procedures or, more accurately still, funcallable instances

                                                                                                                          I would say Haskell and Clojure are functional, or at least closer to it, but Scheme isn’t. This isn’t a small distinction…

                                                                                                                          1. 2

                                                                                                                            That’s a good point and I actually do agree completely. The issue, I think, is that most programmers today will have a hard time telling you the difference between a procedure and a function when it comes to programming. And it’s totally fair- almost every mainstream programming language calls them both “function”.

                                                                                                                            So, Scheme is “functional” in that it’s made up of things-that-almost-everyone-calls-functions. But you’re right. Most languages are made of functions and procedures, and some also have objects.

                                                                                                                            But with that definition, I don’t think Clojure counts as functional either. It’s been a couple of years, but am I not allowed to write a “function” in Clojure that takes data as input and inside the function spawns an HTTP client and orders a pizza, while returning nothing?

                                                                                                                            It would appear that only Haskell is actually a functional language if we use the more proper definition of “function”

                                                                                                                            1. 1

                                                                                                                              But with that definition, I don’t think Clojure counts as functional either. It’s been a couple of years, but am I not allowed to write a “function” in Clojure that takes data as input and inside the function spawns an HTTP client and orders a pizza, while returning nothing?

                                                                                                                              Hey, the type for main in Haskell is usually IO (), or “a placeholder inside the IO monad”; using the placeholder type there isn’t mandatory, but the IO monad is. Useful programs alter the state of the world, and so do things which can’t be represented in the type system or reasoned about using types. Haskell isn’t Metamath, after all. It’s general-purpose.

                                                                                                                              The advantage of Haskell isn’t that it’s all functions. It’s that functions are possible, and the language knows when you have written a function, and can take advantage of that knowledge. Functions are possible in Scheme and Python and C, but compilers for those languages fundamentally don’t know the difference between a function and a procedure, or a subroutine, if you’re old enough. (Optimizers for those languages might, but dancing with optimizers is harder to reason about.)

                                                                                                                            2. 1

                                                                                                                              That article is about Common Lisp, not Scheme. Scheme was explicitly intended to be a computational representation of lambda calculus since day 1. It’s not purely functional, yes, but still functional.

                                                                                                                              1. 2

                                                                                                                                If anything that underscores the point, because lambda calculus doesn’t have side effects, while Scheme does. The argument applies to Scheme just as much as Common Lisp AFAICT.

                                                                                                                                Scheme doesn’t do anything to control side effects in the way mentioned in the original article. So actually certain styles of code in OO languages are more functional than Scheme code, because they allow you to express the presence of state and I/O in type signatures, like you would in Haskell.

                                                                                                                                That’s probably the most concise statement of the point I’ve been making in the thread …

                                                                                                                                1. 2

                                                                                                                                  I take it we’re going by the definition of ‘purely functional programming’ then. In that case, I don’t understand why Clojure, a similarly impure language, gets a pass. Side-effects are plentiful in Clojure.

                                                                                                                                  1. 2

                                                                                                                                    Well I said “at least closer to it”… I would have thought Haskell is very close to pure but it appears there is some argument about that too elsewhere in the thread.

                                                                                                                                    But I think those are details that distract from the main point. The main point isn’t about a specific language. It’s more about how to reason about code, regardless of language. And my response was that you can reap those same benefits of reasoning in code written in “conventional” OO languages as well as in functional languages.

                                                                                                                                    1. 1

                                                                                                                                      That’s fair. It’s not that I disagree with the approach (I’m a big fan of referential transparency!) but I feel like this is further muddying the (already increasingly divergent) terminology surrounding ‘functional programming’. Hence why I was especially confused by the OO remarks. It doesn’t help that the article itself also begs the question of static typing.

                                                                                                                          2. 2

                                                                                                                            Isn’t there a difference between functional code and side-effect-free code?

                                                                                                                            It depends on who you ask to. :)

                                                                                                                            You may be interested in the famous Van Roy’s organization of programming paradigms: https://www.info.ucl.ac.be/~pvr/VanRoyChapter.pdf. Original graphical summary: https://continuousdevelopment.files.wordpress.com/2010/02/paradigms.jpg, revised summary: https://upload.wikimedia.org/wikipedia/commons/f/f7/Programming_paradigms.svg.

                                                                                                                            (reposted from https://lobste.rs/s/aw4fem/unreasonable_effectiveness#c_ir0mnq)

                                                                                                                            1. 1

                                                                                                                              I like your point about the amount of information in type signatures.

                                                                                                                              I agree that the type can’t contain everything interesting to know about the function.

                                                                                                                              I do think you can choose to put important information in the type. In Haskell it’s normal to produce a more limited effect system, maybe one for database effects only, and another for network effects only, and then connect those at the very top level.

                                                                                                                              So, you can put more in the type signature if you wish, and it can be directly useful to prevent mixing effects.

                                                                                                                            1. 6

                                                                                                                              I mostly agree but I would say that OO is evolving toward FP and they aren’t that far apart (at least in certain circles, maybe not in 20 year old code).

                                                                                                                              Good OO is also principled about state and I/O, just like FP.

                                                                                                                              Related comment I wrote on “How to Avoid the Assignment Statement”

                                                                                                                              https://news.ycombinator.com/item?id=22835750

                                                                                                                              Older comment on “Disadvantages of Purely Functional Programming”

                                                                                                                              https://news.ycombinator.com/item?id=11841893

                                                                                                                              So while I agree with the general gist, I would add the caveat that it’s easier to do FP in OO languages than OO in functional language. And the former is pretty natural.


                                                                                                                              Another way I think about it is “dependency inversion of state and I/O”, which I wrote about here:

                                                                                                                              http://www.oilshell.org/blog/2020/04/release-0.8.pre4.html#dependency-inversion-leads-to-pure-interpreters

                                                                                                                              And I also think in many programs it’s useful to “cheat” a little to get it working, and then refactor to a more principled architecture.

                                                                                                                              1. 9

                                                                                                                                There’s a fundamental difference between OO and FP. With FP the core idea is to keep data and code separate. Programs are written as pipelines of functions that you pass data through, and get another piece of data at the other end. In modern FP, data is also immutable, so the functions are referentially transparent. The big advantage here is that data is inert by nature because it doesn’t have any behaviors associated with it, and it’s transparent. What you see is what you get because it’s just data.

                                                                                                                                And you operate on this data by combining a common set of functions from the standard library. Once you learn how these functions work, it becomes trivial to transform any kind of data using them. It’s akin to having a bunch of Lego pieces that you can put together in many different ways to accomplish different tasks.

                                                                                                                                On the other hand, objects are state machines that have some internal state with the methods as the API for interacting with that state. An application written in OO style ends up being a graph of opaque interdependent state machines, and this tends to be quite difficult to reason about. This is why debugging is such a big part of OO development. It’s impossible to reason about a large OO application because there’s just too many things that you have to keep in your head. So, the only thing you can do is put a break point, get the application in the desired state, and try to figure out how you got there.

                                                                                                                                Meanwhile, classes are really ad hoc DSLs, each class defines its own custom API and behaviors in form of its methods, and knowing how one class works tells you absolutely nothing about the next class. The more classes you have in your program, the more stuff you have to keep in your head to work with it effectively.

                                                                                                                                This also makes it much more difficult to learn APIs for libraries. When you call a method, and you get an object graph back, now you have to learn about each of these objects, and how they behave. When your API is data driven, this problem doesn’t exist. You call a function, get some data back, and that’s the end of the story.

                                                                                                                                Rich Hickey describes this problem here very well, and that matches my experience very closely.

                                                                                                                                1. 6

                                                                                                                                  No, that is sort of an old way of thinking about OO. There are a lot of people who don’t write it that way, including me. You can do something much closer to FP in a OO language.

                                                                                                                                  That is the point of the linked comments. Exceprt:

                                                                                                                                  I use “functions and data” (a la Rich Hickey).

                                                                                                                                  Except my functions and data are both CLASSES. Data objects are basically structs, except they can do things like print themselves and answer simple queries based on their values, which helps readability (e.g. 1 liners, like word.AsFuncName() ).

                                                                                                                                  Function objects are simply classes with configuration passed to constructors. That usually have a single method, but multiple methods are also often useful. Calling this method is basically equivalent to calling a curried function. But this is supremely useful for both compilers and servers, because often you have config/params that is constant once you reach main(), and then you have params that vary per request or per file processed. Many functions depend on both, and it’s cleaner to separate the two kinds of params.

                                                                                                                                  So both “functions and data” are effectively and usefully implemented as classes.

                                                                                                                                  The Oil interpreter started out maybe 60% in this style, and is approaching 90% of that style. It’s tens of thousands of lines of code, so it’s not a small change.

                                                                                                                                  There are a few classes that are state machines, but they are explicitly limited to about 10% of the interpreter, just as you would do in a functional language. Most of it is parsing, which has “local” mutable state inside and an interface that’s basically a function.

                                                                                                                                  Again, from the comments, the thing I found funny is that for lexing and parsing, languages like OCaml just borrow the exact same mutable algorithms from C for lexing and parsing (LALR parsing and DFAs for regexes). The mutable escape hatch of of OCaml is essential.

                                                                                                                                  Lexing and parsing are inherently stateful. As long as it’s localized, it’s no problem. FP and OO both agree on that.

                                                                                                                                  1. 1

                                                                                                                                    Thing is that in practice you rarely pass functions around in Clojure. Vast majority of the time you’re passing around plain data, you pass that data through different functions to transform it, and get new kind of data back. There is very little reason to pass functions around in my experience. So, yes you can do similar stuff to OO with functions and closures, but that’s not generally how you end up structuring your applications.

                                                                                                                                    And yes, you can write FP style code in OO languages, but then you’re really not making the most out of the paradigm the language was designed for. You’re much better off doing FP in an actual FP language.

                                                                                                                                  2. 3

                                                                                                                                    This also makes it much more difficult to learn APIs for libraries. When you call a method, and you get an object graph back, now you have to learn about each of these objects, and how they behave. When your API is data driven, this problem doesn’t exist. You call a function, get some data back, and that’s the end of the story.

                                                                                                                                    It creates another problem though: exposing implementation details. Your clients may start assuming things about the data structure that need to be changed. This article tells the story of an API that exposed a list [1]. It turned out the list was too slow, and they wanted to change it. Unfortunately the API’s clients assumed it was a list. The solution given in the article? Hide the data behind a constructor and selectors. That’s basically a class definition.

                                                                                                                                    1: https://itnext.io/information-hiding-for-the-functional-programmer-b56937bdb789

                                                                                                                                    1. 2

                                                                                                                                      Not really because I choose what data I return from the API functions in a library. Meanwhile, your anecdote could’ve happened just as easily using OO API. In fact, I would argue that it’s a far more common problem in OO since you return a graph of objects, and if you ever need to change any of them down the line you’ll be breaking the API for all your users.

                                                                                                                                      Having been working with Clojure for around a decade now, I can tell you that this problem has yet to come up for me in practice.

                                                                                                                                      1. 1

                                                                                                                                        In fact, I would argue that it’s a far more common problem in OO since you return a graph of objects, and if you ever need to change any of them down the line you’ll be breaking the API for all your users.

                                                                                                                                        One of the core tenets of OOP is to program to the interface, not the implementation. If you change the implementation but keep the interface unchanged, you are guaranteed to not break the downstream consumers.

                                                                                                                                        1. 1

                                                                                                                                          Interfaces only address the problem partially, because if the interface ever changes that will still create a breaking change. My experience is that changes to interfaces in OO happen far more regularly than changes to the shape of the data in functional APIs.

                                                                                                                                          1. 1

                                                                                                                                            As per the Java Language Spec,[1]

                                                                                                                                            …here is a list of some important binary compatible changes that the Java programming language supports: … Adding new fields, methods, or constructors to an existing class or interface.

                                                                                                                                            (Among others)

                                                                                                                                            This is similar to making an additive change to the shape of data, e.g. adding a new field to a map which is consumed by a function that doesn’t use the field.

                                                                                                                                            [1] https://docs.oracle.com/javase/specs/jls/se7/html/jls-13.html

                                                                                                                                            1. 1

                                                                                                                                              Having worked with Java for around a decade, I’m well aware of how interfaces work. Yet, my experience is that breaking changes in a language like Java happen far more frequently than they do in a language like Clojure. So, while there are mitigating factors in theory, I don’t find they translate to having stable APIs in practice. That’s just my experience though.

                                                                                                                                        2. 1

                                                                                                                                          How does you choosing what data you return from the API prevent you from exposing implementation details? Or are you saying you just don’t care because you can change the API interface whenever you feel like it?

                                                                                                                                          1. 1

                                                                                                                                            I don’t really follow your question. When I write a function, I explicitly what data it returns, and the shape of that data. The shape of the data is explicitly part of the API contract.

                                                                                                                                            1. 1

                                                                                                                                              The shape of the data is explicitly part of the API contract.

                                                                                                                                              Because the approach forces you to do that even when the shape of the data is an implementation detail that you don’t want to expose.

                                                                                                                                              1. 1

                                                                                                                                                That statement doesn’t make sense. The shape of the data is explicitly part of the contract provided by the API. It is not an implementation detail.

                                                                                                                                                1. 1

                                                                                                                                                  Every implementation choice that is not relevant to the API’s core functionality is an implementation detail. For example, it’s not relevant for an iterator to know the data structure of a collection. All the iterator cares about is that it can iterate over the elements. The concrete shape of the collection (list, set, map, queue, stack, whatever) is an implementation detail from the point of view of the iterator.

                                                                                                                                                  Just because you decide to make an implementation detail a part of the API’s contract, that doesn’t mean it’s not an implementation detail anymore. That’s essentially the problem in the article that I linked.

                                                                                                                                                  1. 1

                                                                                                                                                    In Clojure, you have a seq interface, so any function can iterate over any collection. The same way as it works with Java interfaces. So, no you’re not leaking any more implementation details than you wold with OO API. You’re just arguing a straw man here.

                                                                                                                                                    1. 1

                                                                                                                                                      Just because iteration in Clojure does not depend on the implementation details of the data structure, that doesn’t mean the API’s clients can’t write code that does depend on such details. So, that does not contradict my point at all.

                                                                                                                                                      I don’t know Clojure that well, so I can’t give you an example in Clojure. However, I’m pretty confident that even Clojure does not magically solve the problem of leaking implementation details (otherwise, why would it have interfaces in the first place).

                                                                                                                                                      1. 1

                                                                                                                                                        Again, there’s no difference between FP and OO here. Both Clojure and Java have collection interfaces. If you have an OO API that says it returns a collection, that collection is backed by a concrete implementation, such as a list, internally. That’s an implementation detail. OO doesn’t magically do away with collections. And this is why I find your whole line of argument completely absurd.

                                                                                                                                                        Also, having actually used Clojure for a around a decade now professionally, I can tell you that what you’re describing has never ever come up in practice. So, forgive me if I’m not convinced by your arm chair analysis here.

                                                                                                                                                        1. 1

                                                                                                                                                          Again, there’s no difference between FP and OO here. If you have an OO API that says it returns a collection, and that collection is backed by a list internally, that’s an implementation detail. OO doesn’t magically do away with collections.

                                                                                                                                                          I don’t follow this argument at all. Yeah, in the OO case there is an implementation detail. However, as you pointed out with the word internally: that implementation detail is not exposed to the client. Meaning, the API owner can change that list to a map or a tree or any other data structure at any time without having to worry about the client’s code at all.

                                                                                                                                                          It’s also a little bit of a straw man because this discussion was not about OO vs FP. It was about your statement that APIs should produce/consume raw data rather than objects.

                                                                                                                                                          Having actually used Clojure for a around a decade now professionally, I can tell you that what you’re describing has never ever come up in practice. So, forgive me if I’m not convinced by your arm chair analysis here.

                                                                                                                                                          So, you’re telling me that, in a whole decade, you’ve never had to make changes to an API because a data structure turned out to be wrong? Given that I could pretty easily find an article that showed people having exactly that problem, forgive me if I conclude that either you’re not remembering correctly, or you’re an extraordinary programmer.

                                                                                                                                                          1. 1

                                                                                                                                                            The implementation detail is exposed to the client in exactly the same way. In both cases you have an interface that abstracts the type of collection used from the client. The API owner can change the implementation in EXACTLY the same way. If my API returned a list and then I change it to return a vector, the client does not need to make any changes because both of them support the seq interface.

                                                                                                                                                            The discussion is about OO vs FP because my whole point is that in OO you end up interacting with object graphs in your API, while in FP you end up interacting with plain data. I’m simply telling you that your argument is incorrect in the context of Clojure because collections conform to interfaces. I’m starting to get the feeling that you don’t understand how interfaces work.

                                                                                                                                                            So, you’re telling me that, in a whole decade, you’ve never had to make changes to an API because a data structure turned out to be wrong?

                                                                                                                                                            Correct, I’ve never had to make a change to an API because I changed the implementation of the backing data structure that conformed to the same interface.

                                                                                                                                                            And please do link me an article of this happening in Clojure since you claim you claim that can easily find that. Perhaps what you failed to consider is that the article you found deals with the problems in a specific language as opposed to a general FP problem that you extrapolated from it.

                                                                                                                                                            It frankly amazes me that somebody who openly admits to knowing nothing about the subject can have such strong opinions on it based on an article they find.

                                                                                                                                                            1. 1

                                                                                                                                                              The implementation detail is exposed to the client in exactly the same way. In both cases you have an interface that abstracts the type of collection used from the client. The API owner can change the implementation in EXACTLY the same way. If my API returned a list and then I change it to return a vector, the client does not need to make any changes because both of them support the seq interface.

                                                                                                                                                              As I said, only because Clojure happens to have a seq interface. This reply tells me that you didn’t really get the point I made, and I don’t know how to explain it to you at this point. It seems you just don’t want to see it.

                                                                                                                                                              Correct, I’ve never had to make a change to an API because I changed the implementation of the backing data structure that conformed to the same interface.

                                                                                                                                                              Then your API is not producing/consuming raw data, it’s producing/consuming interfaces. It seems you’re contradicting your own position.

                                                                                                                                                              And please do link me an article of this happening in Clojure since you claim you claim that can easily find that. Perhaps what you failed to consider is that the article you found deals with the problems in a specific language as opposed to a general FP problem that you extrapolated from it.

                                                                                                                                                              So, I searched “Clojure information hiding”, and the first hit literally repeats my whole point. Maybe you understand this explanation then:

                                                                                                                                                              One of the goals of information-hiding is to hide implementation details, so that programmers cannot write programs that depend on those details. (If they do so and those implementation details change, then those programs must also be changed, driving up software maintenance costs.) Clojure thus does not give us any good way to hide implementation details.

                                                                                                                                                              https://cs.calvin.edu/courses/cs/214/adams/labs/08/clojure/

                                                                                                                                                              1. 1

                                                                                                                                                                Clojure having a seq interface clearly disproves your point. I’m not sure what else there is to say here.

                                                                                                                                                                Then your API is not producing/consuming raw data, it’s producing/consuming interfaces. It seems you’re contradicting your own position.

                                                                                                                                                                If you think that then you didn’t understand my position. My original point was that data is immutable, transparent, and it doesn’t have behaviors associated with it. Having interfaces doesn’t invalidate any of that. Your whole argument is just a straw man.

                                                                                                                                                                So, I searched “Clojure information hiding”, and the first hit literally repeats my whole point. Maybe you understand this explanation then:

                                                                                                                                                                There is no information hiding in Clojure because data is part of the API. That’s my whole point of the difference between OO and FP. The claim that this is at odds with hiding implementation details is incorrect however, and I’ve already explained repeatedly why it’s incorrect.

                                                                                                                                                                Seeing how this discussion just keeps going in circles I’m going to leave it here. You can feel free to continue believing what it is that you want to believe, I’ve explained all I can.

                                                                                                                                                                Have a good day.

                                                                                                                                                                1. 1

                                                                                                                                                                  My original point was that data is immutable, transparent, and it doesn’t have behaviors associated with it. Having interfaces doesn’t invalidate any of that.

                                                                                                                                                                  Okay, that changes things…

                                                                                                                                                                  I guess I didn’t understand that at all from reading your comments. There is a paragraph in your initial post where you talk about “classes being ad hoc DSLs” and a bunch of other stuff that applies equally to interfaces. You know, in C++ you make interfaces as pure virtual classes. Then, in the next paragraph you make a contrast between that situation and just data. So, I thought you were talking about concrete data structures not hidden behind any interface.

                                                                                                                                                                  Also, in your first counterargument, you’re countering with this graph of objects that’s hard to change. However, if that was a graph of interfaces, that problem would still be there (as you pointed out in another comment). So, this reinforced the understanding in me (and also others, it seems) that you were talking about concrete “interface-less” data structures.

                                                                                                                                                                  Anyway, if what you’re arguing for includes the ability to return only interfaces from APIs, then I agree the problem that I brought up doesn’t really apply.

                                                                                                                                                                  1. 1

                                                                                                                                                                    The problem with graphs of objects is primarily with objects being opaque and having behaviors. This is completely tangential to the discussion around interfaces.

                                                                                                                                                                    When you have a data driven API backed by immutable data, then what you see is what you get. You can see the the data returned in the API, and it doesn’t have any behaviors associated with it. All the interfaces achieve here is abstracting over the concrete implementation, so you don’t have to worry about the specific backing data structure affecting the API semantics.

                                                                                                                                                                    1. 1

                                                                                                                                                                      Alright, that’s great! I actually share the view that state can turn into a nasty thing. It’s just that you seemed to be arguing against the idea of data abstraction. This kind of triggered me because my experience tells me the code I work with professionally would never survive without it.

                                                                                                                                                                      I guess it’s words like transparent and opaque that cause some confusion for me. They are very generic words so they can be misinterpreted easily. For example, an interface is also opaque in the sense that you can’t see the implementation details.

                                                                                                                                                                      1. 2

                                                                                                                                                                        Glad we’re on the same page. Unfortunately, this kind of thing happens quite often. We all use the same words, but we attach subtly different meanings to them in our heads based on our existing knowledge and experience. So, it’s really easy to end up talking past each other and not even realize it. :)

                                                                                                                                      2. 2

                                                                                                                                        I basically agree with everything you said about what makes a program good or bad, but I disagree with your conclusion: that functional programming leads to good programs and oop leads to bad programs (in some general sense, let’s not nit-pick or talk about absolutes).

                                                                                                                                        But I disagree. In almost all languages, you are perfectly allowed to mutate inputs into functions. This includes basically all (quasi-popular) functional languages that are not named Haskell or Clojure. You are also allowed to cause side effects in your functions in all functional languages that are not named Haskell. This means that I can write input-mutating, side-effecting functional code in OCaml, LISP, Scheme, Rust, etc, etc. Some languages discourage it more than others.

                                                                                                                                        My point is that I agree that making 100 opaque state machines to interact with is a bad idea for a program. But that ad-hoc, crappy, DSL is also perfectly easy to write in a functional way.

                                                                                                                                        I have little doubt that a very strict OOP language that does not allow input arg mutation and side-effects in methods is possible to create and would probably work just as well as good functional languages. The only difference would be a coupling of the data to the functions. That is the only actual difference between FP and OOP in any strict sense, IMO.

                                                                                                                                        1. 5

                                                                                                                                          Both major ML dialects (Standard ML and OCaml) keep a typed distinction between immutable and mutable data. I find this to be good enough to tell which operations can mutate data that I care about at any given moment. Moreover, modules allow you to easily implement ostensibly immutable abstract data types that internally use mutation. (The operating word here is “easily”. It is possible in Haskell too, but it is a lot more painful.)

                                                                                                                                          I would not call Rust a “functional language”, but, for similar reasons, its ability to track what data can be safely mutated at any given moment is good enough to get most of the advantages of functional programming. And then, some of the advantages of non-functional programming.

                                                                                                                                      3. 3

                                                                                                                                        Hopefully on-topic: My experience in functional programming has led to heavy use of composition.

                                                                                                                                        One thing that’s always frustrated me about Python is that instance methods do not return “self” by default, but instead return “None”. I once hacked up a metaclass to make that happen, and suddenly Python felt much more functional! SmallTalk and some of the heavy OO languages do return “self” or “this” by default, I find that fits the Haskell part of my brain better.

                                                                                                                                        What’s the zen koan? Objects are a poor man’s closures, and closures are a poor man’s objects? In Haskell I use partial application to give me roughly what object instances give me. It’s neat, try it out!

                                                                                                                                        1. 4

                                                                                                                                          One thing that’s always frustrated me about Python is that instance methods do not return “self” by default, but instead return “None”.

                                                                                                                                          Yes! It makes it much harder to do simple (list|dict|generator) comprehensions when mutations return None.

                                                                                                                                          In Haskell I use partial application to give me roughly what object instances give me. It’s neat, try it out!

                                                                                                                                          I (ab)use functools.partial for this in python. Very helpful when you have a defined interface and you want to stick extra parameters in as well.

                                                                                                                                        2. 3

                                                                                                                                          Even principled object oriented code hides race conditions. If you connect two systems in an OO language, it may produce an incorrect result while separately systems would run just fine.

                                                                                                                                          Another problem is that partial evaluation for an OO language is not obvious. If you intend to write abstract code like people can do with FP it introduces structure that may need to be contracted away.

                                                                                                                                          1. 2

                                                                                                                                            You don’t get a guarantee from the language, but you can absolutely structure your OO code so composition is thread-safe, and unsafe combinations are obvious.

                                                                                                                                            When I say dependency inversion of I/O and state, I mean that they are all instantiated in main(). And all other code “modules” are also instantiated in main (as classes), and receive state and I/O as parameters.

                                                                                                                                            If you pass the same state to two different modules, then you have to be careful that they are not run concurrently.

                                                                                                                                            If they don’t accept the same state as parameters, then they are safe to run concurrently.

                                                                                                                                            There are zero mutable globals. That is how the Oil interpreter is written.

                                                                                                                                            It helps as I mentioned to have some classes that are like functions, and some classes that are like data. Data and functions are both usefully and easily expressed as classes. (In Oil I use ASDL to make data-like classes, for example)


                                                                                                                                            tl;dr You can make state and I/O parameters in an OO language, and then you get a lot of the reasoning benefits of functional programs, along with some other flexibility (like using a mutable style inside referentially transparent functions, mentioned in my comments and in the article)

                                                                                                                                            1. 1

                                                                                                                                              Could you expand on your first point? What kind of systems and connection between them do you have in mind?

                                                                                                                                              1. 3

                                                                                                                                                An example, a simple one:

                                                                                                                                                class A {
                                                                                                                                                  int x;
                                                                                                                                                  mutate_x (int v) { x = v };
                                                                                                                                                  sendto (B receiver) {
                                                                                                                                                    int y = x + 10;
                                                                                                                                                    while (x < y) { receiver.receive(x); x += 1 }
                                                                                                                                                  }
                                                                                                                                                }
                                                                                                                                                

                                                                                                                                                Depending on whether a receiver here has a separate access to A and gets to mutate_x when sendto is going on, this code is either fine, or then it’s not.

                                                                                                                                                1. 1

                                                                                                                                                  That makes sense. Thanks for elaborating!

                                                                                                                                            2. -1

                                                                                                                                              Can you please paste you replies here, so I don’t have to make another click?

                                                                                                                                            1. 1

                                                                                                                                              What went wrong with Python’s speed? PHP managed to improve its speed a lot just by refactoring its codebase, and it’s not even a JIT yet. Python remained so slow, that it’s just accepted as a fact now.

                                                                                                                                                1. 1

                                                                                                                                                  My understanding is that the VM avoids doing too many optimizations to keep the implementation simple. It’s a philosophical choice on the part of the designers.

                                                                                                                                                1. 1

                                                                                                                                                  Very cool! OSTree and Ninja sounds like a good combo.

                                                                                                                                                  I have a use case for continuous builds and building distros with Oil here:

                                                                                                                                                  https://github.com/oilshell/oil/issues/756

                                                                                                                                                  If anyone is interested in chatting about it let me know :) I’ve only played a little with NInja and OSTree a very long time ago