3

I apologize in advance for the vague title. I didn't want to make it overly verbose, so allow me to explain more in-depth below:

I've currently been developing a strong, statically typed language that compiles down to C++(11) code. Using the answers from How does garbage collection work in languages which are natively compiled? as a guide, I've developed a simple runtime system (written in C++ obviously) for my language that essentially consist of a garbage collector.

The way I designed the GC system is that I first created a base object that all other objects representing specific data types in my language (which currently only include integers and booleans) would inherit from. The GC itself uses a basic references counting algorithm, accessing the field that holds the number of references each object has provide by the base class mentioned above.

The development of the runtime system has come along fine. However, I've just realized somewhat of a problem. Because I have to wrap all data types from my language in their respective objects, this makes the C++ code I generate extremely verbose and clunky for anything bigger than simple expressions. For example, say I had the expression 1 + 2 * (4 - 5) - 6 / (7 + 8). This would roughly be transpiled to the following C++ code by my compiler:

*new Integer(1) + *new Integer(2) * (*new Integer(4) - *new Integer(5)) - *new Integer(6) / (*new Integer(7) - *new Integer(8));

As can clearly be seen, the C++ code that was generated is extremely verbose compared to the original expression written in my language. You could imagine how much worse this would look for even more complex expressions.

My question is: How should a problem like this be dealt with? Is this simply a problem created by my inexperience in creating a runtime system, or is this something that normally occurs when compiling? Obviously this isn't a "problem" in the sense that it's inhibiting me from continuing to develop my compiler, but since I do want my compiler to generate read-able C++ code, this should be something that is solved.

One solution I've thought to this problem is to use a method like three address code to break large expressions into manageable parts, but before I implement it I'd like to understand whether this problem has a better solution.

  • 1
    One possibility that comes to mind: don't wrap data types from your language. Instead, maintain a collection of pointers or references to your bare objects. – Robert Harvey Jan 4 '18 at 22:59
  • I fail to see how three address code helps when your problem is simply that your mapping integer literals to explicit integer construction. You'd just get the same nonsense in the form of many lines of t0:= *new Integer(0) + *new Integer(1);. Three address code gives the nameless temporary object a name, removes the need for parentheses, and makes your order of operations explicit. – candied_orange Jan 4 '18 at 23:01
  • 1
    I'd be tempted to do escape analysis and only GC track objects that live past the basic block they were created in. That will eliminate most of the *new. Then you have a wrapper type around your values, which whilst wordy isn't problematic – Caleth Jan 4 '18 at 23:24
  • 1
    Another thought is internal optimization. * new Integer(n) might be collapsed. Like in C if you do &a[i], which logically says & *(a+i) (as per definition of []). Now you can see that here the & and * cancel out, with the result being just a+i. (Of course, in this example, C has to do this otherwise it'd dereference the array when it shouldn't.) – Erik Eidt Jan 5 '18 at 1:34
  • 1
    As a matter of language design, are you sure you want integers and booleans being on the heap? There is really significant malloc, indirection and GC overhead with that. – Alexander Jan 6 '18 at 17:09
9

How should a problem like this be dealt with?

Generally, it shouldn’t. Do you care how readable the assembly your C++ compiler generates is?

And you do that by making sure your language supports enough (even if it’s a pass through to the lower level language) that nobody looks at the compiled code.

Optimizations can help (but slow your compiler). Three address code can help optimization somewhat, but is just shuffling the deck chairs regarding the generated code. Some formatting and clever naming can help, but don’t meaningfully change the structure of the generated code.

But in the end, if your source language is more expressive than the target language, the generated code will be messier since you need more expression to represent the same information.

  • Yeah, I figured as much. I guess the verbosity doesn't matter that much since my ultimate goal is to get an executable. Anyway, thanks for the answer. +1 – Christian Dean Jan 5 '18 at 3:50
5

I've never seen a code-generating system that produced readable code. All results I've seen were ugly and verbose. So you'd be some kind of pioneer ;-).

But besides readability, I'd like to suggest a change that might improve efficiency.

In your generated code, you create lots of new objects for literal integer values, and repeat that everytime you execute that expression.

What about introducing a literal pool? Then there you'd have all the integer and boolean objects corresponding to all values found literally in your source language code. Then the C++ expression can reference these objects as pre-existing constants (like INT_1) instead of creating new Integers.

And as the values from that pool are meant to be available for the whole lifetime of your program, you can and should exclude them from garbage collection.

And maybe you can go one further step: use primitive C++ ints

I can't tell from the snippet whether the numerical operators you use are still the basic C++ ones or overloaded ones from your classes. If they are the basic ones, then your C++ expression could simply be 1 + 2 * (4 - 5) - 6 / (7 + 8). Only when storing that result you'd need to wrap it into an Integer, e.g. like new Integer(1 + 2 * (4 - 5) - 6 / (7 + 8)), or by overloading the assignment operator.

For more information on this approach, have a look at e.g. Java's boxing and unboxing of primitive types.

  • Thanks, this sounds like a great idea! Yes, I overloaded the basic arithmetic operators for my Integer class, but your idea should still be fairly easily implemented. – Christian Dean Jan 5 '18 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.