Programming Your Own Language in C++ | Hacker News Reader

Programming Your Own Language in C++

accu.org

110 pointsetrevino23 comments

This article shows a lot of the silliness in both a) writing compilers in C++ and b) re-creating well-worn compilers tools like parsers from scratch.

1. Their definition of values in the language (unfortunately called "Variables") is a product (class) over all possible types:

  class Variable {
    ...
    double numValue;
    string strValue;
    vector<Variable> tuple;
    string action;
    string varname;
    Constants::Type type;
  };

This means each value at runtime has a large memory footprint, as each instance of a value contains slots for all possible types even though only one will ever be filled. Sum types solve this problem.

2. The author intermixes parsing and code generation. This makes it difficult to implement any kind of optimizations, even for an interpreter. For example, in order to do function inlining in the author's language, you would have to manually inline calls in every single part of the code generator instead of having IR transformations as separate modules (see: LLVM). It also tightly couples the two pieces of the compiler, making it difficult to change parsing strategies without rewriting the code generator for instance.

3. It took the author nearly 5000 lines of C++ to write an interpreter for a simple Javascript-like scripting language. Some of this is due to the verbosity of C++, and some is due to the needless effort of reimplementing parsing from scratch. I implemented a similar language in <1k lines of Rust [1], and I'm sure that others could do even better in Haskell or OCaml. On top of that, the author's claimed benefit of extensibility requires writing large amounts of boilerplate.

[1] https://github.com/willcrichton/lia

Some people make things while other discuss the theory. Each has their place. There would be nothing to improve if people don't try.

At the risk of stating the obvious -- in C and C++, unions solve that problem.

You still need to roll your own tagged unions by hand. Algebraic data types solve that problem.

But can you have a union of string and numeric data? It's been awhile since I've used them, but how would that work?

Union of numeric and character pointer.

They solve the memory issue, although they are inconvenient to use vs. pattern matching and aren't type safe. Additionally, I've had no luck using classes (e.g. string) inside of unions because the compiler reasonably complains about initializers. I believe this is somewhat solved with boost::variant (and that's also getting put into C++17, iirc), but ideally it would be a part of the type system.

Replace the type (e.g. std::string) by the pointer type (e.g. std::string*) in the union.

union is a max-size-fits-all solution. a better solution is inheritance.

Which would introduce the overhead of a vtable, which would vary depending on how deep your inheritance goes. I haven't read the article, but I would maybe use an enum if this is just use to parse variable declarations.

Generally the vtable is not much slower. I believe around the cost of an extra pointer derefence vs the alternative of branching. Also the compiler can sometimes optimize the cost to be the same as a normal call(e.g. final)

This is a toy example - one needs to have a lot of values for that whale of a Variable class to create a problem.

Cached version, since we appear to have hugged their database to death.

http://web.archive.org/web/20160616053900/http://accu.org/in...

I just love how sites get unavailable after getting to the top of the HN. :)

If you are serious about making your own programming language, I would strongly suggest to target the LLVM.

If in C++, LLVM + Flex/Bison still the most productive for me. I've tried lots of other compiler compilers, but they're still the best once you learn them. If anybody is bored, I put together a simple word count example a long time ago that has taken on a life of its own: https://github.com/jonathan-beard/simple_wc_example

> If you are serious about making your own programming language, I would strongly suggest to target the LLVM.

Strange advice given the state of LLVM on platforms such as windows. Both Swift and Crystal, LLVM based don't run on windows for instance. LLVM gives you more quickly but at the cost of portability.

LLVM works fine on Windows.

How does this contrast with recursive descent parser?

ANTLR generates a recursive descent parser. The value is, it's easier to compare (hopefully) your EBNF to the antlr spec than it is to compare your EBNF to lower level code.

Doesn't ANTLR usually generate a bottom-up parser? I've never used ANTLR but it would be very odd to generate a recursive descent parser; LR grammars are parsed bottom-up (presumably the ‘LR’ in ‘ANTLR’).

Bottom-up parsers are nigh unreadable by mortals.

ANTLR generates top down parsers which use a few different algorithms, including Parr's LL(star) algorithm and the new ALL(star) algorithm for antlr 4:

https://scholar.google.com/scholar?cluster=11340764028758422...

https://scholar.google.com/scholar?cluster=70305927860962254...

The ANTLR acronym is explained here and doesn't have anything to do with LR grammars: http://www.antlr.org/

antlr's c++ backend is pretty good for complex projects

Reply on news.ycombinator.com