16 ms·

Compilers are hard

206 points by sidcool 6y ago

svnpenn 6y ago
Typo in literally the second sentence. C'mon man.
cperciva 6y ago
On the topic of compilers being hard: In my repositories I'm carrying around a 5 year old workaround (https://github.com/Tarsnap/libcperciva/commit/92e666e59503de37b958c7e70e56ae71b281b036 https://github.com/Tarsnap/libcperciva/commit/92e666e59503de...) for a 6 year old bug (https://bugs.llvm.org/show_bug.cgi?id=21183 https://bugs.llvm.org/show_bug.cgi?id=21183) in clang/LLVM. You might think that "incorrect code gets generated" would be a maximum-priority must-fix-before-the-next-release bug in a compiler, but apparently not.
- thegrandpoobah 6y ago
  Actually shocked to hear this considering the number of people and companies currently working on LLVM.
  - drivebycomment 6y ago
    Not that surprising given that it seems specific to asan mode and only in the presence of setjmp/longjmp. I.e. this cant be that important unless the same bug shows also in non-asan Setjmp/longjmp case. Setjmp/longjmp are often a source of trouble for the register allocator or related optimization due to its unique properties. Often the optimizing compilers treat set/longjmp as "give up almost everything around those functions" but maybe llvm is trying hard to model it precisely and failing. But I haven't personally looked at the relevant code in llvm so this is mostly a speculation.
    - h_anna_h 6y ago
      Regarding asan bugs, if you do not free all of your memory before exiting main it will complain about stuff and end up calling _exit I think which does not flush the buffers.
    - cperciva 6y ago
      The bug shows up without asan. We literally tripped over it in production with code compiled with "clang -O2".
      - drivebycomment 6y ago
        Then I agree that this is surprising. That means clang/llvm is not modeling set/longjmp correctly in general and that is not acceptable as a C compiler.
      - scatters 6y ago
        That's apparent from your ticket (which is marked as a duplicate) but on the one you linked to, all the offending compiler lines contain asan. Is there a chance this is impacting prioritization?
        cperciva 6y ago
        Could be. I'm not an LLVM developer so I don't know how they prioritize issues.
  - jcranmer 6y ago
    The code in question is related to setjmp/longjmp. As a general rule of thumb, this is something where the gut reaction to any bug report is going to be "you're doing it wrong"--the C standard actually provides a lot less guarantees here than most people believe it does. I haven't read the verbiage and the bug report in question in enough detail to ascertain if this is true or not, but it isn't in the least bit surprising that most people see setjmp/longjmp and immediately table the issue as being low-priority.
    - usefulcat 6y ago
      Having read the comments in the llvm bug report, it seems pretty clear that it is a real bug and that they have at least an idea of where the bug is.
- titzer 6y ago
  No, performance is maximum priority.
  - naikrovek 6y ago
    That's a "great on the surface, bad when you think about it" thing if I've ever seen one. Who cares how fast the code is, if it isn't the correct code?
    - xmprt 6y ago
      I have solved the halting problem. Every program you write compiles and executes as HALT; and therefore it's possible to determine if a program halts! It might not be correct but it sure is fast!
      - mrybczyn 6y ago
        https://en.wikipedia.org/wiki/Full_employment_theorem https://en.wikipedia.org/wiki/Full_employment_theorem You've broken the full employment theorem for compiler writers.
    - qznc 6y ago
      If people cared about correctness, they would use CompCert instead of GCC or Clang.
      - tobylane 6y ago
        CompCert doesn’t guarantee these two functions will work. Thanks, didn’t know about that project.
      - pjmlp 6y ago
        Or create OSes where applications are all written in managed languages, and the use of GCC and clang is gate keeped to the OS vendor and native libraries, just an idea.
        6y ago
- ubadair 6y ago
  Wow, this is the first time I've seen the computed goto extension. Delightfully gross! https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
  - KMag 6y ago
    Computed gotos are commonly used in main loops of bytecode interpreters to get a separate dispatch (indirect jump) at the end of handling each bytecode, so the CPU's branch target buffer has a better chance of predicting the indirect jump target for the next bytecode based on the previous bytecode. For instance, CPython's dispatch loop uses computed goto on supported platforms, and Erlang's BEAM VM (in non-JIT mode) uses computed branch labels to convert bytecodes into branch addresses at bytecode load time. I suppose, for twice the latency, CPU designers could implement (a hash of) the previous branch address from the source instruction pointer as part of the BTB tag, similar to using the global branch history as part of the state in the branch predictor. Presumably, the global branch history could also be used in the BTB tag to give some hint as to which bytecode we've just finished executing. Though, where it really counts, interpreter writers are already often using computed gotos, reducing the reward to cost ratio for implementing such specialized BTB improvements. On the other hand, while (1) { switch (...) { ... } } is probably rare enough (and almost certainly in a hot loop) that a very specific optimization flag might be better than a syntactic extension. Granted, an optimization flag doesn't work for Erlang's threaded code use case.
  - __s 6y ago
    You'll also find them used in CPython's ceval.c I use them in both my C befunge implementations: https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60dac740a1de3bf1f1bf6f/marsh.c#L83 https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60... https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60dac740a1de3bf1f1bf6f/bejit.c#L232 https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60...
- vintagedave 6y ago
  Are you sure it's not fixed? https://reviews.llvm.org/D11495 https://reviews.llvm.org/D11495 was fixed on 29/7/2015.
  - cperciva 6y ago
    That's marked as being Asan-specific, and the bug isn't. So... I don't think so?
FnControlOption 6y ago
> I recently saw a PR to Scala that’s a great demonstration of exactly this. The private and sealed keywords have been in Scala forever and someone only just recently came up with the realisation that private classes are effectively sealed. Scala’s been in existence for 16 years! Slight correction: someone came up with the realisation 7+ years ago[1] but someone else came up with a fix only recently 1: https://github.com/scala/bug/issues/6159?orig=1 https://github.com/scala/bug/issues/6159?orig=1
- zackmorris 6y ago
  Oh man, that's cool and everything, but IMHO the concept of "final" or "sealed" (popularized by Java I think and cargo-culted by C#) is an anti-pattern. A simple proof of how this makes certain use cases impossible is: imagine you want to do reactive programming by watching for when a class variable changes and then running a function to handle that event. The simplest way to do this in something like C# is to create a child class and override the getter/setter for the variable. Then pass that child class to any method that accepts the base class. But if it's sealed you can't do that. To make matters worse, many developers don't understand that if you want to use final/sealed, then you need to provide an interface for your class. That allows users to write their own classes that implement that interface, but still be drop-in replacements for the original classes. If your class is sealed, and you don't write an interface, then there is simply no way to do reactive programming with your class. A workaround is to manually write an interface for the class (in situations that allow that). But even if you get that working, your code is no longer future-proof, because the burden of updating the interface falls on you instead of the original author. A better solution would be to provide an automatically-generated interface for all classes at the language level (something like MyClass::interface). Then additional methods to extend that interface, if desired. Sadly/shockingly, I'm not aware of any language that does that. Now this wouldn't seem to be all that important, but it hit me when I was trying to write a Unity library. I want to be notified when classes like GameObject and Mesh change, so that I can perform additional functionality (like updating metadata associated with the class instance). But since those classes are sealed, there is simply no way to do that: https://forum.unity.com/threads/detect-changes-to-sealed-class-like-mesh-reactively.759248/ https://forum.unity.com/threads/detect-changes-to-sealed-cla... When a language makes an opinionated decision blocking the user from implementing a common use case like this, it becomes a toy language. I lost weeks trying to find a workaround in Unity before being forced to give up. So I'm saddened to see Scala make the mistake of adopting a conceptual flaw in the name of an implementation detail like performance. If someone has a workaround for the Unity example I gave, maybe using components or MeshFilter or something, I'd love to hear it. Please don't respond with explanations of inheritance vs composition, because I've already heard them.
dwohnitmok 6y ago
There's a few things I'll nitpick in this article. > I mean more the type systems in languages like Scala and Haskell, think features like existential and dependent types. Type systems like Java’s and Typescript’s are great! They add value! But you can be an order of magnitude or two more safe with more advanced type systems and it’s profoundly beneficial when you learn how to make good use of them. > Unfortunately, type-safety didn’t help me very much when developing my big feature.... I feel like the author is unintentionally reinforcing certain stereotypes around type systems. Typescript actually has an insanely powerful type system, in many ways much more advanced than Scala's type system and certainly more advanced than "vanilla" Haskell (i.e. something like Haskell2010). What often gives people the impression that a type system like Haskell is "strong" (or in the even more extreme case a type system like Elm, which has a reputation also for being "advanced" but is actually one of the simplest possible type systems with polymorphism) is that other features (mainly stuff around immutability) combine with the type system to enhance the guarantees that the type system can give. Very roughly speaking it is very hard to "go behind the type system's back" in these languages. However, the actual type system is not terribly advanced. It's also weird to mention dependent types here because dependent types would have precisely solved the example the author brings up (this is leaving aside other issues that current dependently typed languages have). For example in Idris you could write something like firstCharOfString : String -> Maybe Char firstCharOfString = ... processData : (firstNameLetter : Maybe Char) -> (name : String) -> (firstCharOfString name = firstNameLetter) -> Result processData = ... Now you can't do this in Scala (although you can achieve something like dependently typed smart constructors with path-dependent types in Scala, but it's very fragile and I wouldn't recommend it) so I agree that this may not be the way you want to do things in Scala. To go back up a level, the way that non-dependent types of the sort you'd find in Scala help you when writing a compiler is when you split your compiler into different passes. You can write a statically typed representation at the end of each pass to act as an "anchor" to cut down on certain classes of bugs both between two successive passes, but also to ensure that certain bugs can't span multiple passes. I suspect the reason that the author wasn't getting a lot of mileage out of the Scala type system is due to a monolithic "compiler" design. If everything is a single giant pass then you get a lot less lift from the Scala type system (but this is true even if you substitute human understanding for a type system). > This is provenance. It doesn’t sound that hard but in practice it was surprisingly challenging to implement. Provenance is indeed very difficult, especially in the presence of things that change your representation, but not your semantics. It can really muck up your code to have to carry around a lot of baggage that's unrelated to your final result, but also has to be updated through the various stages of data transformation your result goes through as well. > I recently saw a PR to Scala that’s a great demonstration of exactly this. The private and sealed keywords have been in Scala forever and someone only just recently came up with the realisation that private classes are effectively sealed. Scala’s been in existence for 16 years! I feel like this kind of misrepresents the situation. The original bug was filed 9 years ago and only just now fixed because it was very low priority (which makes me think a lot of people have come to the same realization and just not really bothered about it). Regardless the original sentiment that different options intersect in a combinatorial explosion is something I can get behind. > Would the code just do the exact same thing but with more boilerplate using IORefs or huge StateT stacks? Would Haskell be so efficient in its optimisation that a more straight-forward FP approach would be sufficiently fast? When comparing Haskell and Scala the answer is generally yes, functional idioms tend to run a lot faster in GHC than with scalac. Not necessarily IORef (which can be actually surprisingly slow due to boxing issues), but StateT (and by extension State) is way faster in GHC than in scalac. Similarly IO in Haskell is faster than the attempts to emulate it with cats-effect or ZIO. You pay an overhead for FP in Scala that you don't always have to in Haskell. That being said I still prefer to write performance sensitive FP code, that is still performance-tolerant enough to be conceivably written in something like Java or Go, in Scala if the only choices were Scala or Haskell. As the author mentions, mutability contained entirely within functions isn't really all that icky to me and my mental model for low-level unboxed array hacking in Scala or Java is more robust than my mental model for intricately weaving Haskell code to make sure all the requisite GHC optimizations fire in terms of being fairly confident what the overall optimization process would look like.
teleforce 6y ago
Very nicely written article. Kudos to the Shipreq team for having close to 100% offline or local-first feature, is Shipreq utilizing automerge library to do that? It's mentioned in the article that Go has a very fast compilation time and the same can be said of D language. The reason they are fast to compile because the languages' authors design the languages to be compiler friendly unlike C++. One of the main tricks to being fast to compile is by avoiding symbols look-up table. For one of the feasible solutions, perhaps Petri net is better than graph. It is a generic state machine mechanism and here are a few examples of having a compiler design using Petri Net approach[1][2]. [1] ZINC: a compiler for “any language”-coloured Petri nets, https://www.ibisc.univ-evry.fr/~fpommereau/publis/2018-01-01-zinc-a-compiler-for-any-language-coloured-petri-nets.html https://www.ibisc.univ-evry.fr/~fpommereau/publis/2018-01-01... [2] Model, Design, and Evaluation of a Compiler for a Parallel Processing Environment, https://ieeexplore.ieee.org/document/1702471 https://ieeexplore.ieee.org/document/1702471
- pjmlp 6y ago
  While it is true, C++ can also be quite compiler friendly, provided one is willing to invest into it. "Lucid Energize Demo VHS 1993" https://www.youtube.com/watch?v=pQQTScuApWk https://www.youtube.com/watch?v=pQQTScuApWk Which makes use of a Lisp like image for C++. https://dreamsongs.com/Files/Energize.pdf https://dreamsongs.com/Files/Energize.pdf Visual Age for C++, version 4.0, tried the same approach. Both failed, due to the hardware requirements for the day. C++ Builder was the survivor with some of this ideas and its specific C++ packages. However, now with modules, incremental compilation and linking, expect modern C++ IDEs to finally come back to it. This appears to be the ongoing roadmap for Visual C++, as per blog posts and some of their conference talks. I expect other C++ IDE/compiler vendors to follow along.
amir734jj 6y ago
Third year PhD student in compilers here. Yes, compilers are hard but they are fun and addicting. No regrets switching from cryptography in masters to compilers in PhD. Lattice based cryptography is actually very hard and that's why I couldn't continue.
- txdv 6y ago
  Always wanted to ask an academic about this. Compilers take input source and libraries and maybe some configuration parameters (in C you can pass preprocessor definitions, etc) and produce an output. No network calls, no conditional file IO - the only side effects that are needed have to be done at the beginning, when you load source files and other libraries. Why are so many compilers not utilizing more pure functional paradigms? Focusing on transformations of input to output instead of doing side effects. It seems like such a perfect fit.
  - girvo 6y ago
    Anecdotally: because my compiler was surprisingly slow following a purely functional architecture. Though that was likely my own idiocy more than anything anyone else can draw a conclusion from :)
    - mhh__ 6y ago
      What language? When I write functional code (the compiler can enforce purity) in D I can usually get it running fairly quickly, but because of various things (memory locality, memory usage, etc.) I can see it being a problem in problem in the more traditional functional languages. Ultimately for single-threaded applications avoiding state is usually just slower, however, it also buys correctness. Eliminating mutable state in composition can also massively improve the parallelism available to the programmer without making changes to the implementation.
  - pharmakom 6y ago
    In academia many compilers are written in functional languages, particularly OCaml. Unfortunately, the programming community has come to this bone-headed idea that to be a serious language, its compiler must be implemented in itself. As a result, compiler implementation languages follow popular language trends. I’m sure a much faster TypeScript compiler could be written in OCaml or Rust, for instance.
amelius 6y ago
Good garbage collectors are harder.
JayeshSidhwani 6y ago
there is a minor typo in "Some recent experience hsa provided ........."
truth_seeker 6y ago
I am not okay with the kind of changes the article suggests in the code and test suite. At least IMHO it defeats the purpose of using richly typed language. The Approach i would take is smartly dividing the code into namespace and libraries : 1. Spend more time in design process and isolating the low level concerns. 2. Seperate the business logic code into multiple namespace or perhaps libraries 3. extract the common utility classes, interfaces, enums in separate namespace, also the common layers like ORM, HTTP networking etc. 4. Test suite must be separate and can also adopt above 3 points mentioned internally 5. Provide enough configuration in build file so that the Independent or Semi-Independent modules or libraries can be compiled in both parallel through using multiple CPU cores and incremental manner through last compiler output cache.
z29LiTp5qUC30n 6y ago
But compilers are not hard but simple state machines. If you don't believe me, look at cc_x86 https://github.com/oriansj/stage0/blob/master/stage2/High_level_prototypes/cc_x86/cc_core.c https://github.com/oriansj/stage0/blob/master/stage2/High_le...
- userbinator 6y ago
  ...or in other words, "they're hard only because you make them hard". That said, I think C4 makes a better example of how simple it can be: https://github.com/rswier/c4/blob/master/c4.c https://github.com/rswier/c4/blob/master/c4.c (Previously on HN at https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822 and https://news.ycombinator.com/item?id=22353532 https://news.ycombinator.com/item?id=22353532)
- gregorygoc 6y ago
  You can say that about everything. "But X is not hard. It's just number theory" - while X is Fermat's Last Theorem
Someone 6y ago
I sort-of disagree. Compilers that produce small and/or fast code and good error messages for complex languages are hard, but simple ones for simple languages aren’t. Also, creating a toy one for a simple language is a fun educational exercise. We shouldn’t deter people from having a go at that by making them think “compilers are hard”. For many simple languages (e.g. a language doesn’t need to have strings, multiple numeric types, operator precedence, or even have expressions containing multiple operators), writing a one pass compiler that always spills back operation results to memory isn’t too hard. Its assembly output can fairly easily be matched to the source, and it will provide a decent speed-up compared to a naive interpreter. From there, the first few steps (peephole optimizations to remove store-load pairs, then a slightly more advanced register allocator) aren’t too difficult, either, and bring nice speed ups. ‘Real’ compilers are ‘just’ thousands more of such steps, each either extending the language or improving code generation, up from there. And yes, things do become very hairy somewhere along that route.
- chrisseaton 6y ago
  > e.g. a language doesn’t need to have strings, multiple numeric types, operator precedence, or even have expressions containing multiple operators Can't you make anything look easy by reducing it to an unrealistically limited example? Building an F1 car is hard. Building a soap box car is easy. Building Google is hard. Building a simple web scraper and grep is easy. Seems like a redundant thing to point out. When people say something is hard they obviously mean 'for a useful actual application I care about'.
  - recursive 6y ago
    Some things are irreducibly difficult. Writing a compiler isn't one of them.
  - aidenn0 6y ago
    Writing a c 89 compiler is something you could do in under a year of evenings and weekends. Maybe that's overly reduced, but at least it's more like a model T than a soap box car?
- 6y ago
devilduck 6y ago
This comment section is pure HN hubris and I am here for it.
juanbyrge 6y ago
If a project management app is the hardest code you've ever written, this sounds like overengineering**2. Just use lists of lists like every other project management app.
0xbadcafebee 6y ago
Everything is hard until you know how to do it. Some things are hard after you know how to do it. But there's usually an easier way to do it, you just have to find and use it. If you find yourself going "boy this is hard" a lot, you probably just aren't doing it the easy way.
carapace 6y ago
(This might sound snarky and I apologize for that, I don't have time to write a big long thing here. I'm seriously FWIW.) If writing the compiler is hard your language is too complicated; also, use Prolog. I've been writing a compiler in Prolog for Joy (a concatinative language, and one that I suspect may be the simplest useful language) and (other than my own idiocy) it's been a breeze. Last month I started in on Make-a-Lisp using Nim. I like both of those languages but now that I'm used to Joy and Prolog they both seem painfully over-designed and over-engineered. Not bad just woefully baroque. I couldn't go on. Perhaps this is just a personal problem, I acknowledge that, but I have a feeling that my experience generalizes, that we're working too hard, making things too complicated.

206 points by sidcool 6y ago

Typo in literally the second sentence. C'mon man.

On the topic of compilers being hard: In my repositories I'm carrying around a 5 year old workaround (https://github.com/Tarsnap/libcperciva/commit/92e666e59503de37b958c7e70e56ae71b281b036 https://github.com/Tarsnap/libcperciva/commit/92e666e59503de...) for a 6 year old bug (https://bugs.llvm.org/show_bug.cgi?id=21183 https://bugs.llvm.org/show_bug.cgi?id=21183) in clang/LLVM. You might think that "incorrect code gets generated" would be a maximum-priority must-fix-before-the-next-release bug in a compiler, but apparently not.

thegrandpoobah 6y ago
Actually shocked to hear this considering the number of people and companies currently working on LLVM.
- drivebycomment 6y ago
  Not that surprising given that it seems specific to asan mode and only in the presence of setjmp/longjmp. I.e. this cant be that important unless the same bug shows also in non-asan Setjmp/longjmp case. Setjmp/longjmp are often a source of trouble for the register allocator or related optimization due to its unique properties. Often the optimizing compilers treat set/longjmp as "give up almost everything around those functions" but maybe llvm is trying hard to model it precisely and failing. But I haven't personally looked at the relevant code in llvm so this is mostly a speculation.
  - h_anna_h 6y ago
    Regarding asan bugs, if you do not free all of your memory before exiting main it will complain about stuff and end up calling _exit I think which does not flush the buffers.
  - cperciva 6y ago
    The bug shows up without asan. We literally tripped over it in production with code compiled with "clang -O2".
    - drivebycomment 6y ago
      Then I agree that this is surprising. That means clang/llvm is not modeling set/longjmp correctly in general and that is not acceptable as a C compiler.
    - scatters 6y ago
      That's apparent from your ticket (which is marked as a duplicate) but on the one you linked to, all the offending compiler lines contain asan. Is there a chance this is impacting prioritization?
      - cperciva 6y ago
        Could be. I'm not an LLVM developer so I don't know how they prioritize issues.
- jcranmer 6y ago
  The code in question is related to setjmp/longjmp. As a general rule of thumb, this is something where the gut reaction to any bug report is going to be "you're doing it wrong"--the C standard actually provides a lot less guarantees here than most people believe it does. I haven't read the verbiage and the bug report in question in enough detail to ascertain if this is true or not, but it isn't in the least bit surprising that most people see setjmp/longjmp and immediately table the issue as being low-priority.
  - usefulcat 6y ago
    Having read the comments in the llvm bug report, it seems pretty clear that it is a real bug and that they have at least an idea of where the bug is.
titzer 6y ago
No, performance is maximum priority.
- naikrovek 6y ago
  That's a "great on the surface, bad when you think about it" thing if I've ever seen one. Who cares how fast the code is, if it isn't the correct code?
  - xmprt 6y ago
    I have solved the halting problem. Every program you write compiles and executes as HALT; and therefore it's possible to determine if a program halts! It might not be correct but it sure is fast!
    - mrybczyn 6y ago
      https://en.wikipedia.org/wiki/Full_employment_theorem https://en.wikipedia.org/wiki/Full_employment_theorem You've broken the full employment theorem for compiler writers.
  - qznc 6y ago
    If people cared about correctness, they would use CompCert instead of GCC or Clang.
    - tobylane 6y ago
      CompCert doesn’t guarantee these two functions will work. Thanks, didn’t know about that project.
    - pjmlp 6y ago
      Or create OSes where applications are all written in managed languages, and the use of GCC and clang is gate keeped to the OS vendor and native libraries, just an idea.
      - 6y ago
ubadair 6y ago
Wow, this is the first time I've seen the computed goto extension. Delightfully gross! https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
- KMag 6y ago
  Computed gotos are commonly used in main loops of bytecode interpreters to get a separate dispatch (indirect jump) at the end of handling each bytecode, so the CPU's branch target buffer has a better chance of predicting the indirect jump target for the next bytecode based on the previous bytecode. For instance, CPython's dispatch loop uses computed goto on supported platforms, and Erlang's BEAM VM (in non-JIT mode) uses computed branch labels to convert bytecodes into branch addresses at bytecode load time. I suppose, for twice the latency, CPU designers could implement (a hash of) the previous branch address from the source instruction pointer as part of the BTB tag, similar to using the global branch history as part of the state in the branch predictor. Presumably, the global branch history could also be used in the BTB tag to give some hint as to which bytecode we've just finished executing. Though, where it really counts, interpreter writers are already often using computed gotos, reducing the reward to cost ratio for implementing such specialized BTB improvements. On the other hand, while (1) { switch (...) { ... } } is probably rare enough (and almost certainly in a hot loop) that a very specific optimization flag might be better than a syntactic extension. Granted, an optimization flag doesn't work for Erlang's threaded code use case.
- __s 6y ago
  You'll also find them used in CPython's ceval.c I use them in both my C befunge implementations: https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60dac740a1de3bf1f1bf6f/marsh.c#L83 https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60... https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60dac740a1de3bf1f1bf6f/bejit.c#L232 https://github.com/serprex/Befunge/blob/c97c8e63a4eb262f3a60...
vintagedave 6y ago
Are you sure it's not fixed? https://reviews.llvm.org/D11495 https://reviews.llvm.org/D11495 was fixed on 29/7/2015.
- cperciva 6y ago
  That's marked as being Asan-specific, and the bug isn't. So... I don't think so?

FnControlOption 6y ago

> I recently saw a PR to Scala that’s a great demonstration of exactly this. The private and sealed keywords have been in Scala forever and someone only just recently came up with the realisation that private classes are effectively sealed. Scala’s been in existence for 16 years! Slight correction: someone came up with the realisation 7+ years ago[1] but someone else came up with a fix only recently 1: https://github.com/scala/bug/issues/6159?orig=1 https://github.com/scala/bug/issues/6159?orig=1

zackmorris 6y ago
Oh man, that's cool and everything, but IMHO the concept of "final" or "sealed" (popularized by Java I think and cargo-culted by C#) is an anti-pattern. A simple proof of how this makes certain use cases impossible is: imagine you want to do reactive programming by watching for when a class variable changes and then running a function to handle that event. The simplest way to do this in something like C# is to create a child class and override the getter/setter for the variable. Then pass that child class to any method that accepts the base class. But if it's sealed you can't do that. To make matters worse, many developers don't understand that if you want to use final/sealed, then you need to provide an interface for your class. That allows users to write their own classes that implement that interface, but still be drop-in replacements for the original classes. If your class is sealed, and you don't write an interface, then there is simply no way to do reactive programming with your class. A workaround is to manually write an interface for the class (in situations that allow that). But even if you get that working, your code is no longer future-proof, because the burden of updating the interface falls on you instead of the original author. A better solution would be to provide an automatically-generated interface for all classes at the language level (something like MyClass::interface). Then additional methods to extend that interface, if desired. Sadly/shockingly, I'm not aware of any language that does that. Now this wouldn't seem to be all that important, but it hit me when I was trying to write a Unity library. I want to be notified when classes like GameObject and Mesh change, so that I can perform additional functionality (like updating metadata associated with the class instance). But since those classes are sealed, there is simply no way to do that: https://forum.unity.com/threads/detect-changes-to-sealed-class-like-mesh-reactively.759248/ https://forum.unity.com/threads/detect-changes-to-sealed-cla... When a language makes an opinionated decision blocking the user from implementing a common use case like this, it becomes a toy language. I lost weeks trying to find a workaround in Unity before being forced to give up. So I'm saddened to see Scala make the mistake of adopting a conceptual flaw in the name of an implementation detail like performance. If someone has a workaround for the Unity example I gave, maybe using components or MeshFilter or something, I'd love to hear it. Please don't respond with explanations of inheritance vs composition, because I've already heard them.

dwohnitmok 6y ago

There's a few things I'll nitpick in this article. > I mean more the type systems in languages like Scala and Haskell, think features like existential and dependent types. Type systems like Java’s and Typescript’s are great! They add value! But you can be an order of magnitude or two more safe with more advanced type systems and it’s profoundly beneficial when you learn how to make good use of them. > Unfortunately, type-safety didn’t help me very much when developing my big feature.... I feel like the author is unintentionally reinforcing certain stereotypes around type systems. Typescript actually has an insanely powerful type system, in many ways much more advanced than Scala's type system and certainly more advanced than "vanilla" Haskell (i.e. something like Haskell2010). What often gives people the impression that a type system like Haskell is "strong" (or in the even more extreme case a type system like Elm, which has a reputation also for being "advanced" but is actually one of the simplest possible type systems with polymorphism) is that other features (mainly stuff around immutability) combine with the type system to enhance the guarantees that the type system can give. Very roughly speaking it is very hard to "go behind the type system's back" in these languages. However, the actual type system is not terribly advanced. It's also weird to mention dependent types here because dependent types would have precisely solved the example the author brings up (this is leaving aside other issues that current dependently typed languages have). For example in Idris you could write something like firstCharOfString : String -> Maybe Char firstCharOfString = ... processData : (firstNameLetter : Maybe Char) -> (name : String) -> (firstCharOfString name = firstNameLetter) -> Result processData = ... Now you can't do this in Scala (although you can achieve something like dependently typed smart constructors with path-dependent types in Scala, but it's very fragile and I wouldn't recommend it) so I agree that this may not be the way you want to do things in Scala. To go back up a level, the way that non-dependent types of the sort you'd find in Scala help you when writing a compiler is when you split your compiler into different passes. You can write a statically typed representation at the end of each pass to act as an "anchor" to cut down on certain classes of bugs both between two successive passes, but also to ensure that certain bugs can't span multiple passes. I suspect the reason that the author wasn't getting a lot of mileage out of the Scala type system is due to a monolithic "compiler" design. If everything is a single giant pass then you get a lot less lift from the Scala type system (but this is true even if you substitute human understanding for a type system). > This is provenance. It doesn’t sound that hard but in practice it was surprisingly challenging to implement. Provenance is indeed very difficult, especially in the presence of things that change your representation, but not your semantics. It can really muck up your code to have to carry around a lot of baggage that's unrelated to your final result, but also has to be updated through the various stages of data transformation your result goes through as well. > I recently saw a PR to Scala that’s a great demonstration of exactly this. The private and sealed keywords have been in Scala forever and someone only just recently came up with the realisation that private classes are effectively sealed. Scala’s been in existence for 16 years! I feel like this kind of misrepresents the situation. The original bug was filed 9 years ago and only just now fixed because it was very low priority (which makes me think a lot of people have come to the same realization and just not really bothered about it). Regardless the original sentiment that different options intersect in a combinatorial explosion is something I can get behind. > Would the code just do the exact same thing but with more boilerplate using IORefs or huge StateT stacks? Would Haskell be so efficient in its optimisation that a more straight-forward FP approach would be sufficiently fast? When comparing Haskell and Scala the answer is generally yes, functional idioms tend to run a lot faster in GHC than with scalac. Not necessarily IORef (which can be actually surprisingly slow due to boxing issues), but StateT (and by extension State) is way faster in GHC than in scalac. Similarly IO in Haskell is faster than the attempts to emulate it with cats-effect or ZIO. You pay an overhead for FP in Scala that you don't always have to in Haskell. That being said I still prefer to write performance sensitive FP code, that is still performance-tolerant enough to be conceivably written in something like Java or Go, in Scala if the only choices were Scala or Haskell. As the author mentions, mutability contained entirely within functions isn't really all that icky to me and my mental model for low-level unboxed array hacking in Scala or Java is more robust than my mental model for intricately weaving Haskell code to make sure all the requisite GHC optimizations fire in terms of being fairly confident what the overall optimization process would look like.

teleforce 6y ago

Very nicely written article. Kudos to the Shipreq team for having close to 100% offline or local-first feature, is Shipreq utilizing automerge library to do that? It's mentioned in the article that Go has a very fast compilation time and the same can be said of D language. The reason they are fast to compile because the languages' authors design the languages to be compiler friendly unlike C++. One of the main tricks to being fast to compile is by avoiding symbols look-up table. For one of the feasible solutions, perhaps Petri net is better than graph. It is a generic state machine mechanism and here are a few examples of having a compiler design using Petri Net approach[1][2]. [1] ZINC: a compiler for “any language”-coloured Petri nets, https://www.ibisc.univ-evry.fr/~fpommereau/publis/2018-01-01-zinc-a-compiler-for-any-language-coloured-petri-nets.html https://www.ibisc.univ-evry.fr/~fpommereau/publis/2018-01-01... [2] Model, Design, and Evaluation of a Compiler for a Parallel Processing Environment, https://ieeexplore.ieee.org/document/1702471 https://ieeexplore.ieee.org/document/1702471

pjmlp 6y ago
While it is true, C++ can also be quite compiler friendly, provided one is willing to invest into it. "Lucid Energize Demo VHS 1993" https://www.youtube.com/watch?v=pQQTScuApWk https://www.youtube.com/watch?v=pQQTScuApWk Which makes use of a Lisp like image for C++. https://dreamsongs.com/Files/Energize.pdf https://dreamsongs.com/Files/Energize.pdf Visual Age for C++, version 4.0, tried the same approach. Both failed, due to the hardware requirements for the day. C++ Builder was the survivor with some of this ideas and its specific C++ packages. However, now with modules, incremental compilation and linking, expect modern C++ IDEs to finally come back to it. This appears to be the ongoing roadmap for Visual C++, as per blog posts and some of their conference talks. I expect other C++ IDE/compiler vendors to follow along.

amir734jj 6y ago

Third year PhD student in compilers here. Yes, compilers are hard but they are fun and addicting. No regrets switching from cryptography in masters to compilers in PhD. Lattice based cryptography is actually very hard and that's why I couldn't continue.

txdv 6y ago
Always wanted to ask an academic about this. Compilers take input source and libraries and maybe some configuration parameters (in C you can pass preprocessor definitions, etc) and produce an output. No network calls, no conditional file IO - the only side effects that are needed have to be done at the beginning, when you load source files and other libraries. Why are so many compilers not utilizing more pure functional paradigms? Focusing on transformations of input to output instead of doing side effects. It seems like such a perfect fit.
- girvo 6y ago
  Anecdotally: because my compiler was surprisingly slow following a purely functional architecture. Though that was likely my own idiocy more than anything anyone else can draw a conclusion from :)
  - mhh__ 6y ago
    What language? When I write functional code (the compiler can enforce purity) in D I can usually get it running fairly quickly, but because of various things (memory locality, memory usage, etc.) I can see it being a problem in problem in the more traditional functional languages. Ultimately for single-threaded applications avoiding state is usually just slower, however, it also buys correctness. Eliminating mutable state in composition can also massively improve the parallelism available to the programmer without making changes to the implementation.
- pharmakom 6y ago
  In academia many compilers are written in functional languages, particularly OCaml. Unfortunately, the programming community has come to this bone-headed idea that to be a serious language, its compiler must be implemented in itself. As a result, compiler implementation languages follow popular language trends. I’m sure a much faster TypeScript compiler could be written in OCaml or Rust, for instance.

amelius 6y ago

Good garbage collectors are harder.

JayeshSidhwani 6y ago

there is a minor typo in "Some recent experience hsa provided ........."

truth_seeker 6y ago

I am not okay with the kind of changes the article suggests in the code and test suite. At least IMHO it defeats the purpose of using richly typed language. The Approach i would take is smartly dividing the code into namespace and libraries : 1. Spend more time in design process and isolating the low level concerns. 2. Seperate the business logic code into multiple namespace or perhaps libraries 3. extract the common utility classes, interfaces, enums in separate namespace, also the common layers like ORM, HTTP networking etc. 4. Test suite must be separate and can also adopt above 3 points mentioned internally 5. Provide enough configuration in build file so that the Independent or Semi-Independent modules or libraries can be compiled in both parallel through using multiple CPU cores and incremental manner through last compiler output cache.

z29LiTp5qUC30n 6y ago

But compilers are not hard but simple state machines. If you don't believe me, look at cc_x86 https://github.com/oriansj/stage0/blob/master/stage2/High_level_prototypes/cc_x86/cc_core.c https://github.com/oriansj/stage0/blob/master/stage2/High_le...

userbinator 6y ago
...or in other words, "they're hard only because you make them hard". That said, I think C4 makes a better example of how simple it can be: https://github.com/rswier/c4/blob/master/c4.c https://github.com/rswier/c4/blob/master/c4.c (Previously on HN at https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822 and https://news.ycombinator.com/item?id=22353532 https://news.ycombinator.com/item?id=22353532)
gregorygoc 6y ago
You can say that about everything. "But X is not hard. It's just number theory" - while X is Fermat's Last Theorem

Someone 6y ago

I sort-of disagree. Compilers that produce small and/or fast code and good error messages for complex languages are hard, but simple ones for simple languages aren’t. Also, creating a toy one for a simple language is a fun educational exercise. We shouldn’t deter people from having a go at that by making them think “compilers are hard”. For many simple languages (e.g. a language doesn’t need to have strings, multiple numeric types, operator precedence, or even have expressions containing multiple operators), writing a one pass compiler that always spills back operation results to memory isn’t too hard. Its assembly output can fairly easily be matched to the source, and it will provide a decent speed-up compared to a naive interpreter. From there, the first few steps (peephole optimizations to remove store-load pairs, then a slightly more advanced register allocator) aren’t too difficult, either, and bring nice speed ups. ‘Real’ compilers are ‘just’ thousands more of such steps, each either extending the language or improving code generation, up from there. And yes, things do become very hairy somewhere along that route.

chrisseaton 6y ago
> e.g. a language doesn’t need to have strings, multiple numeric types, operator precedence, or even have expressions containing multiple operators Can't you make anything look easy by reducing it to an unrealistically limited example? Building an F1 car is hard. Building a soap box car is easy. Building Google is hard. Building a simple web scraper and grep is easy. Seems like a redundant thing to point out. When people say something is hard they obviously mean 'for a useful actual application I care about'.
- recursive 6y ago
  Some things are irreducibly difficult. Writing a compiler isn't one of them.
- aidenn0 6y ago
  Writing a c 89 compiler is something you could do in under a year of evenings and weekends. Maybe that's overly reduced, but at least it's more like a model T than a soap box car?
6y ago

devilduck 6y ago

This comment section is pure HN hubris and I am here for it.

juanbyrge 6y ago

If a project management app is the hardest code you've ever written, this sounds like overengineering**2. Just use lists of lists like every other project management app.

0xbadcafebee 6y ago

Everything is hard until you know how to do it. Some things are hard after you know how to do it. But there's usually an easier way to do it, you just have to find and use it. If you find yourself going "boy this is hard" a lot, you probably just aren't doing it the easy way.

carapace 6y ago

(This might sound snarky and I apologize for that, I don't have time to write a big long thing here. I'm seriously FWIW.) If writing the compiler is hard your language is too complicated; also, use Prolog. I've been writing a compiler in Prolog for Joy (a concatinative language, and one that I suspect may be the simplest useful language) and (other than my own idiocy) it's been a breeze. Last month I started in on Make-a-Lisp using Nim. I like both of those languages but now that I'm used to Joy and Prolog they both seem painfully over-designed and over-engineered. Not bad just woefully baroque. I couldn't go on. Perhaps this is just a personal problem, I acknowledge that, but I have a feeling that my experience generalizes, that we're working too hard, making things too complicated.