Term Rewriting with Shared Pointers is a Major Design Decision

A compiler is bookkeeping plus term rewriting. Old compilers were usually full of bookkeeping through the use of tables. They needed to be since resources were scarce and performance was low. As processors evolved and became more powerful, compilers became more declarative and shifted in the direction of term rewriting.

Hi is a declarative language, so naturally, the bootstrap relies little on tables but simply rewrites, massages, the term until it is semantically verified and code can easily be output in a number of steps.

The bootstrap lacked in performance, due to:

1. Wasteful memory representation of the data being worked upon.
2. A slow operational model, combinator rewriting instead of the C calling convention.
3. Lack of imperative constructs.
4. Lack of fast impure containers.
5. Garbage collection.

I could have solved 1., made an effort to fix 2., added 3., and ultimately added 4. (but that only becomes necessary, probably, when processing large, >1MLoc, files) and, in a final last effort, implement features to do 5. fast.

The path of a selfhosting declarative compiler seems to be that you keep on adding imperative features until you've reinvented C. I personally loath the Haskell IO monad and barely agree with Clean's uniqueness types. For Hi, it isn't worth it: The language is fine for small programs, making it fast and selfhosting is a 20-100 man year effort, which I don't have, can fail anyway, and I want to keep the language simple and declarative.

Most people agree we hit the end of Moore's Law, the era of the free lunch is over. We had a 3500x speedup over the last decades since the introduction of the first microprocessor, declarative languages cannot wait anymore for another few decades until they become that fast that people want to use them.

So, I decided to ditch the effort and do it all in C++. Fast interpreter, slow language. If it would ever attract a user base, there are plenty of optimizations left.

But since I have a term-rewriting self-hosting compiler as a design reference, naturally the choice for representing terms comes up. Since I rewrite a tree, or DAG, I basically have two choices: use trees and copy, or use DAGS and support sharing with some form of garbage collection. So, it's either copying or sharing. Both have nonperforming corner cases: trees are fast but you might spend too much time copying, for reference counting the overhead may become large on terms when only rewriting trees and the reference counting degrades to pure overhead.

I made the choice to represent the AST with C++'s shared pointers. After having looked at GCC, which uses a pointer-to-massive-struct copying system internally, I wanted to test performance of a sharing solution on a 500KLoc file, a large list of small declarations, with respect to copying. It spends 40% of its time reference counting.

For industrial compilers this would imply that copying beats sharing; at least, pending the implementation of C++'s shared pointer.

It does 30ms over a small file of 5k declarations, so I'll stick to this scheme of shared pointers. It's just too convenient implementation wise, if a node gets rewritten or falls out of scope in a C routine, it is automagically garbage collected. But boy, oh boy, it is horrific to pay performance for design decisions this early in the implementation stage.

Log 051605

Working on the AST, parsing, and rendering code simultaneously. Verbose, but after I sank my teeth in it, not unpleasant. Dijkstra would hate the manner in which I write code. Ah well, he turned out to be somewhat of an idiot when it comes to software engineering anyway. So, whatever.

Later that day: *poof* After a flurry of activity I managed to get a rudimentary grammar recognizer ready. I immediately did some performance tests. On small files, fine; on a 500KLoc file, not so good. Somehow parsing took 11 seconds but rendering becomes slower as the file grows larger and I broke that off. I blame smart pointers for now.

Ah well. Guess if anyone will be using it it'll take a long while before people start writing 500KLoc files.

Log 051215

A bit of reading while thinking about qualified names and namespaces. Stuff I noticed. Chicken Scheme has a problem with running out of stack space too. There is a nice language named Nim under development, glancing through it, it seems to mostly be an Algol like derivation. But fast and bootstrapped, I like it. Haskell allocates large objects in chunks to keep GC happy. If you compile to straightforward C it's actually quite difficult to keep the GC manager happy due to the fact that at any moment the C routine might ask for memory, which might trigger a collection, and ruin all invariants in the C routine. Using C reference counting completely avoids that problem. (Or you use bytecode, as in Clean, OCaml and Java, and avoid the problem by keeping the complete machine abstract.)

There is a small but major design decision in the Ast representation. Lists or vectors? Lists allow for sharing and a declarative style, vectors might be faster but at the expense of ugly imperative code and copying. After some dabbling I threw up a coin and decided vectors.

I continue with my streak of shooting myself in the foot and am going to implement namespaces no matter what. Though it's academically uninteresting and pretty annoying to get right algorithmically.

I am leaning towards dropping the combinator rewriting system... (But what about OS's where the stack size is a hard limit? No MacOS?).

Eager. Pure. No GC. No combinator rewriting. HM inference. No bootstrapping. No cyclic structures. C semantics. It'll be completely academically uninteresting. But hopefully a great small tool for patching small functional programs. A front-end to LLVM.

(As a side note: Because of the end of Moore's law I expect the next thing to be vertical integration which means Hardware OS's; or since OS's are written in C/C++, language integration. All current research paywalled, unfortunately.)

Log 051015

So you thought you could do term rewriting in C++, ey? I got the idiom for representing ASTs in C++ figured out. Of course, the idiom is well-known, it's an instantiation of this, but it took me a while of struggling with the template library and some googling to get right.

Basically, terms in the datatype derive from an abstract class. Since an abstract class cannot be instantiated, C++ more or less forces you to pass references back as the result of functions. Moreover, since the abstract class doesn't know how to copy objects from the stack to the heap, the solution is to write a copying constructor and clone method for each variant.

This is a lot of cruft, the source code is going to explode on it. It's a very heavy price to pay for not being willing to implement the interpreter/compiler in a functional language such as SML.

But yeah. I chose C++ because reasons.

Log 050915

Moving stuff around in the sources, trying to get an idiom right on how to handle shared pointers in C++, adjusting a provisional lexer such that it will scan a test language, rethinking qualified names and namespaces, thinking about how to represent the parser right in C++. Unmotivating tidbits of engineering.

Type checker in the back of my mind. I am rethinking the ideas I had five years ago. I re-realize that there probably is no subtyping relation on types. Any concrete type can implement multiple interfaces at some given point, and that may be extended. Once extended, all old type derivations remain unchanged. Simply put: any concrete type just gets augmented with a list of interfaces and simple HM inferencing is enough. (Though it would be nice to put arbitrary values sharing interfaces in a container.) Moreover, since the language lacks assignment, there shouldn't be the need for a monomorphism restriction a la ML. Of course, you might want to store stuff at the module level but I would be perfectly happy labeling primitive routines for that 'unsafe'.

Since the language has exceptions I actually think I want RAII too. Which means 'destructors' on garbage collected nodes referring open files, database connections, etc. Which means I am inclined to drop my copying garbage collector and simply reference count everything. Even more wasteful but I can use C++ shared pointers for that and get thread safety for free. Moreover, good enough since the language guarantees that you're rewriting a DAG anyway.

It's just a trivial language. The lack of use cases means I shift between the semantics. If I read on a programmer's language I want to go into the direction of representing bytes, words, longs, etc.; if I read up on scripting languages my mood changes and I want to go for BigInts. Whatever, or not?

Log 050815

So no programming today. Family business, which was a good idea since I am easily mentally worn-out these days. But it remains in my mind.

So, a few random thoughts:

Trading robustness for speed. I rewrite everything to an eager manner of rewriting combinators to avoid stack overflows. I am not sure people willing to use the language will appreciate the, rather enormous, cost in running speed. If I am going to compile to LLVM, or some other JIT since LLVM seems to have performance problems, it becomes 'trivial' to encode to standard function calls. Moreover, a rather large number of optimizations would become feasible, or could easily be done by the LLVM compiler.

But you sacrifice robustness, and after a myriad of stack overflows bootstrapping in OCaml I don't want to go back.

As a side note, I also figured out how to handle closures in that scenario. The function knows when to reduce or push a closure so that's trivial. Exception handling is also enabled by default in the modern processor ABIs so I figure I don't even need to do difficult stuff for that.

Who will ever use this language? This is really a difficult question. FP enthusiasts? They already have a large number of compilers to chose from. SML or Haskell probably will gobble all of them up. I thought numeric computing for a moment, but those favor simple algorithmic languages. I read up on Julia, these programmers think fundamentally different than functional programmers and want optimal speed. I thought about web servers, which may be a target for some people, in which case I need to think about handling threads and shared state. Then I thought that it might be nice to write simple robust GUI applications; but who would choose my language over Python? I need a convincing use case. Some place where you need ridiculously robust software?

But I still like the language.

Compiling to Object files and C/C++ integration. Given a JIT compiling to .o files is automated for you, which is something I really want. But how the hell does the linker know about namespaces? Is there some name mangling going on I don't know about? Answer here, it seems.

Log 050715

So combinator parsing in C++ turns out to be a bad idea, not only is it near impossible to get right most C++ implementations need several seconds for large files whereas the 'dumb' method usually finishes in milliseconds, needed to unlearn the functional style. Back to straight-forward recursive descent with switches on the current token.

I think I got how to write a far more trivial type checker than what I once started on. Straightforward Hindley-Milner with a subtyping relation on types implementing interfaces. It shouldn't be hard, I am also dropping all other ideas I had. Bottom-up HM+subtyping is good enough.

I've got a start of an AST description now going. Going to reference count everything through the use of C++ smart pointers; that's a bit overkill but it beats thinking about copying.

For downcasting it's going to be tag based switches followed by a static cast.

Everything is of course far more verbose than the bootstrap which I am using as a reference implementation.

So far so good. Making progress but this is probably still the easy part.

ADDENDUM: I thought I would share the AST solution I chose for people who might have ended up here by chance.

1) Define tags for your expressions:

typedef enum {
     VAR,
     ABSTRACTION,
     APPLICATION,
} expr_t;

2) Define a base object:

class Expr;
typedef std::shared_ptr<Expr> ExprPtr;

class Expr {
public:
     Expr(expr_t t): _tag(t) {};

     expr_t  tag() { return _tag; }

     virtual ExprPtr clone() = 0;
private:
     expr_t _tag;
}

3) Derive variants, for instance

class ExprApplication: public Expr {
public:
      ExprApplication(ExprPtr e0, ExprPtr e1): Expr(APPLICATION), _left(e0), _right(e1) {}
      
      ExprApplication(const ExprApplication& e) {
          _left = e._left;
          _right = e._right;
      }

      ExprPtr clone() {
          return ExprPtr(new ExprApplication(*this));
      }

      // etc.

private:
    ExprPtr _left;
    ExprPtr _right;
}


It took a lot of googling but the idiom for using shared pointers where you mostly only reference the base class is aptly described here.

Well, that's it. Don't create cycles, as long as your term is a DAG, most likely it will always be a tree, this scheme should work with RAII and might even allow for memory-compact solutions far better than simply copying everything.