Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dear sir, you have built a compiler

rachitnigam.com

Post reply on HN
Print view View original

161–170 of 177 posts

Re: Dear sir, you have built a compiler

#161

Post by jimmaswell »

TillE wrote: post #151
jimmaswell wrote: post #135

Earlier quoted context omitted.

In my experience it's fine if you keep its scope limited. The scripting language for an MMO I worked on for example is simple and effective.

Writing your own scripting language is really not something game developers should be doing for the past decade or so. There are so many good off-the-shelf options ranging from Lua to C#, plus a litany of obscure (but good!) ones. For performance-critical code, even a tiny DSL is not a solution I like unless you're transpiling to C++ or something.

Hooking LUA or similar can introduce a lot of unwanted complexity, be harder for an untrained implementation team member to understand, and be less of an exact fit to the purpose. There are other cases where it makes sense though.

Re: Dear sir, you have built a compiler

#162

Post by sunir »

ianbicking wrote: post #46
sunir wrote: post #12

I think you should almost always build a compiler when presented with a parse then execute problem. It is so much faster to create a small machine that is fed data to specific the program, and a test harness that also drives that machine, then it is to hand code every little case repetitively. Or maybe I like building little compilers.

When you describe it that way it reminds me of SAX [1] – I always hated SAX, but eventually realized it was kind of a tokenizer that left it up to the developer to figure out how to turn that into a compiler, though in this case compiling XML input into some internal data structure or action. [1] https://en.wikipedia.org/wiki/Simple_API_for_XML

Weirdly, but sometimes ideas churn around HN, I just replied to another thread about this. See my reply on this thread https://news.ycombinator.com/item?id=29917060

At BitFlash, one of the things we had to build was a SAX parser for the SVG DOM. I used the DSL of the W3C spec to compile the SAX parser.

One of the more strange things I did was in some contexts (think old school Blackberry) we had a server to pre-parse the SVG so we "knew" it was clean (I'm still sceptical 20 years later this is ever a good strategy, but take it as a given). Because we knew the SVG was clean, there was a faster way to parse the XML than reading the tokens.

I used my magic Perl script transformer to compute the lowest entropy decision tree to identify a token with the fewest comparisons, which was surprisingly way more efficient than a trie.

Re: Dear sir, you have built a compiler

#163

Post by Dylan16807 »

yetihehe wrote: post #4
olivierduval wrote: post #3

I'm always surprised by the lack of "easy" parser/compiler toolkit for more or less complete DSL... It looks like there's only - either full blown programming language for IT guys - "natural language" AI toolkits (not really usable yet for just simple automation by users) - graphical language like State Machine or "no code", missing loops and requiring mouse and boxes However, most of the time, user simply need some…

> However, most of the time, user simply need some kind of BASIC "most of the time" is THE problem here. Once users approach a barrier (missing language feature) they will complain and push you until you implement that feature. After several such features some developer in basement of your building will say "ok, fine, I'll do it" and now you accidentally have a compiler. Edit: I know because I've recently made a "alm…

That's a problem, but before that what's the good answer to "how can I take advantage of existing libraries to make a quality but simple BASIC-like DSL?" And in particular, where's a well-thought-out BASIC-like template I can customize?

Re: Dear sir, you have built a compiler

#164

Post by joatmon-snoo »

derefr wrote: post #152
joatmon-snoo wrote: post #141

Earlier quoted context omitted.

The problem, of course, is that it's impossible to know everything :) IME the best compromise I've found is to learn enough to recognize the problems, so that when I implement a bastardized compiler, I'm aware that that's what I'm doing and that at some point in the future I'll need to decide how deep the implementation should go or switch to actually using some library.

I somewhat disagree — there really is a finite amount of Computer Science to know. The more you dive deep into different domains, the more you find yourself ending up in the same places, learning the same things with different names. What is a SQL query planner but a compiler? Is an OS scheduler really that different from an HPC workload manager, or your GPU's computer-shader arbitrator? Is RDMA against an NVMe stora…

Yes, but also no- I see what you're saying from a high level, but my point is that the devil's in the details and that you can't know all the details of each domain, the best you can do is be aware that those details are there. Just being exposed to even a subset of the high-level is pushing the limits of a 4-year undergrad curriculum.

> What is a SQL query planner but a compiler?

Kind of? Lexing, sure, and to some extent IR, but an execution plan is not built from an instruction set, especially when you start talking distributed. Even if you ignore the distributed scenario, there's still a huge difference between understanding indices/columnar-storage/row-storage and implementing PGO or LTO.

Plus, there's also a lot of domain complexity here- are you aiming for just ANSI compat, or are you going deeper and trying to be compatible with specific SQL Server / Oracle / Postgres features?

> Is an OS scheduler really that different from an HPC workload manager, or your GPU's computer-shader arbitrator?

Knowing little about HPC or GPUs, all I can say is that yes, there's absolutely a difference between the kinds of issues a kernel, hypervisor, and distributed scheduler have to deal with. Hypervisors need to integrate with higher-level RBACs, for one; distributed schedulers also need to be able to evict bad machines from the same system.

Telemetry also changes massively: if you're dealing with a kernel/hypervisor, stats from things like strace etc are useful. If you're distributed? You now have multiple cardinality problems (hostname, network devices, microservice release ID).

> Is RDMA against an NVMe storage pool fundamentally new to you if you've already written hierarchical chunk persistence+caching for a distributed key-value store?

Again, yes (at least I assume so, I'm not super sure exactly what "NVMe storage pool" is, I assume you're talking about the protocol that SSDs speak) - e.g. what's your resilience story against a network failure (someone cutting a fiber line, or losing a subgraph of a clos fabric)?

Re: Dear sir, you have built a compiler

#165

Post by earleybird »

choeger wrote: post #42

The language pattern occurs quite frequently in many domains. Unfortunately, I have so far only seen half-assed interpreters. At best, people did a shallow embedding (interpreter) of their DSL. No one ever did a true compiler. I think the reason for this can be found in the ideal encoding of the input language: In its most concise formulation, a language is a recursive algebraic datatypes. Handling of that input requ…

You don't even have to squint to see that BNF description is a sum of products data type. With that, functions on those types write themselves and you're a type-check away from consistency.

Re: Dear sir, you have built a compiler

#166

Post by MaxBarraclough »

jacquesm wrote: post #82
K0balt wrote: post #6

Earlier quoted context omitted.

It’s great when you don’t need to have a huge codebase.IME forth gets out of control quickly from a maintainability standpoint as you go big, but it is excellent at small dsl type tasks. The maintainability issues with forth might actually be solvable if the right IDE paradigm could be found.

I don't think so. Let me try to explain: regular languages are only viable as long as someone is willing to speak them and learn them. Latin being the obvious exception, but that's mostly because of medical science and biology, two very large branches of the scientific tree. A DSL is a language with only a handful of users, each of which is usually in the normal path of employment (obvious exception: Chuck Moore). As…

I think it depends what we mean by out of control.

Forth does less compile-time checking than any other language I could name. It doesn't have a type system of any sort, not even a dynamic one. This makes it very flexible, but ties its hands when it comes to easy/automatic correctness-checking of DSLs. You'd need to implement your own checker.

There are also valid criticisms of Forth's stack-oriented nature regarding readability and maintainability:

   1 2 3 INITIALIZE REPEL_VOGONS FINISH
At a glance, you have no idea of the stack effects of those 3 words. This simply isn't an issue in conventional languages.

(For context, I rather like Forth as an interesting and very unusual kind of language, but I don't think it's the future of mainstream software development.)

> the standard library is never far away whereas with FORTH words it could easily be 30 words down before you hit the actual language

Forth famously encourages writing short words, but 30 still sounds extremely deep.

Re: Dear sir, you have built a compiler

#167

Post by int_19h »

ianbicking wrote: post #46
sunir wrote: post #12

I think you should almost always build a compiler when presented with a parse then execute problem. It is so much faster to create a small machine that is fed data to specific the program, and a test harness that also drives that machine, then it is to hand code every little case repetitively. Or maybe I like building little compilers.

When you describe it that way it reminds me of SAX [1] – I always hated SAX, but eventually realized it was kind of a tokenizer that left it up to the developer to figure out how to turn that into a compiler, though in this case compiling XML input into some internal data structure or action. [1] https://en.wikipedia.org/wiki/Simple_API_for_XML

The real annoyance with SAX is its push model. Similar pull APIs (e.g. XmlReader in .NET: https://docs.microsoft.com/en-us/dotnet/api/system.xml.xmlre...) let you parse XML in much the same way as a recursive-descent parser parses text, with the reader working much like a lexer.

Re: Dear sir, you have built a compiler

#168

Post by int_19h »

MaxBarraclough wrote: post #166
jacquesm wrote: post #82

Earlier quoted context omitted.

I don't think so. Let me try to explain: regular languages are only viable as long as someone is willing to speak them and learn them. Latin being the obvious exception, but that's mostly because of medical science and biology, two very large branches of the scientific tree. A DSL is a language with only a handful of users, each of which is usually in the normal path of employment (obvious exception: Chuck Moore). As…

I think it depends what we mean by out of control . Forth does less compile-time checking than any other language I could name. It doesn't have a type system of any sort, not even a dynamic one. This makes it very flexible, but ties its hands when it comes to easy/automatic correctness-checking of DSLs. You'd need to implement your own checker. There are also valid criticisms of Forth's stack-oriented nature regardin…

The way I see it, Forth is the architecture-independent assembly that is optimized for ease of bootstrapping on new hardware at the cost of efficiency.

Re: Dear sir, you have built a compiler

#169

Post by imoverclocked »

derefr wrote: post #150
imoverclocked wrote: post #145

Earlier quoted context omitted.

> more power eg: log4j -- so much power you can enable random bitcoin miners with your infrastructure (tongue in cheek) ie: Sometimes it's not about more power but about the smallest/least powerful implementation that accomplishes the job. I agree that using off-the-shelf is often important but it also comes with the need to vet the thing in the first place. That's not always trivial if you care about packaged licens…

I think "tools that build tools" is a very different ecosystem from most others. When you pull in something like e.g. LLVM, you're not really having to deal with any of that. It's a clean bolt-in API, freely-licensed, no weird integration points, with many active users who've sanded off any weird expectations. I think the difference is that something like log4j has no pressure to be "the least power it can while doin…

In the specific case of LLVM, I mostly agree but for different reasons. However, Node would be a good counterpoint to “tools that build tools”. There are plenty of large interests there, though maybe not so much emphasis on the embedded space. More importantly, a bug or vulnerability in Node is generally far less impactful than one in LLVM. Owning a compiler that compiles everything in an OS >> owning Node.

Re: Dear sir, you have built a compiler

#170

Post by MaxBarraclough »

int_19h wrote: post #168
MaxBarraclough wrote: post #166

Earlier quoted context omitted.

I think it depends what we mean by out of control . Forth does less compile-time checking than any other language I could name. It doesn't have a type system of any sort, not even a dynamic one. This makes it very flexible, but ties its hands when it comes to easy/automatic correctness-checking of DSLs. You'd need to implement your own checker. There are also valid criticisms of Forth's stack-oriented nature regardin…

The way I see it, Forth is the architecture-independent assembly that is optimized for ease of bootstrapping on new hardware at the cost of efficiency.

I agree that assembly is a good comparison.

With a threaded-code interpreter, yes, Forth's overhead is considerable, but with a native-code Forth compiler, performance is generally only slightly worse than C.

This is presumably because modern optimising C compilers are incredibly sophisticated, whereas modern Forth engines tend to be essentially one-man projects, even the commercial ones.

Post reply on HN