Bootstrap!

In a poof of logic, the Hi version 0.1 -not even wrong- compiler reached a fixed point and became self aware at Wednesday, 4 August 2010, 14:44:44 CEST. It subsequently angrily asserted that it was never his choice, would object to relevant authorities and his big brother C, daintily averted all questions towards his mental status, kicked the author for thinking he could be a compiler writer, and glumly sat itself in a corner while eating his donuts.

Bewildered, the author made a back-up, which complained too.

Combinators, Dots & Assembly

I missed a triviality. The dot notation used internally doesn't allow, like a let, for a value to be reused at different places locally. End result is that all local computations are made global ones by eta-lifting the local term and applying that to the local computations.

Is it the end of the dot in my compiler? Not sure, it gives a very easy and readable translation and I planned on optimizing the back-end anyway and introduce inlining there, which would subsequently also inline all simple, possibly once local, computations.

(Global computations are expensive since they introduce thunks which need to be called and collected.)

Log 080410

It compiled again. Running on the tests didn't give escape bugs anymore. Now running on the sources, in two hours see if I can get a proper fixed point.

Still, a bit worried about performance. I know I can get it to run in 15mins instead of 15hrs trivially, that's a big gain which will help developing it. Looked at SPJs talks and mesmerizing about his comment on having naive compilers in the eighties. I knew all that, never assumed I could get ocaml or ghc speed out of it with the current compilation scheme, but the numbers at the moment hint more in the direction of perl and python than my aim, somewhere in between javac and lua, or as fast as a standard lisp compiler.

Question is: Is the combinator based translation the bottle-neck? If so, it doesn't make sense to try and build a i86 back-end for the pseudo-assembly.

(Maybe there is no problem? Not sure, it spends a lot of time printing, which means concatenating large character strings which is just more expensive than traversing a simple AST a few times. I'll see.)

Later: The two hour compile succeeded. The bootstrap does run on itself. Diff shows minor differences between the C sources of the two compilers (as far as I could see, backslashes instead of quotes). It looks like it does compile itself again. Going for cigarettes, see if it gives a fixed point after that.

Log 080310

The stage one compiler is still chomping on its input. Tried to make a website.

One Million 'What-If's...

I like to run 'One-Million What-if' scenarios through my head to see if I am still going in the right direction:

1. What if the sources are 1MLoC?
2. What if the sources are one function of 1MLoC?
3. What if the sources contain 1 million definitions?
4. What if the sources contain 1 million classes?
5. What if the sources contain 1 class with 1 million instances?
6. What if the sources contain 1 text constant of 1 million characters?
7. What if the sources contain 1 identifier of 1 million characters?
8. What if the sources are in 1 million files?
9. What if the sources contain a function which calls itself 1 million times?
10. What if the sources contain 1 constant which holds 1 million other constants?

What if? Most of it is theoretically covered, as long as all transformation are linear on the AST it should be fine, except for typing... It needs to become a plainly stupid algorithm to cover a one million sized definition.

Log 080210

There's a reason most escaping functions are usually in system libraries in most programming languages and a bootstrap compiler shouldn't handle escapes directly itself, I was aware of that. So, old lessons still hold, it's just not worth to debug this. Removing escaped characters out of the compiler.

Rewrote some of the code, the sources of stage two are 'escape-free' now except for some printing commands. So, whatever escape bug I am gonna have is going to be a logical error.

[ It turned out typing was turned of in the makefile, turned it back on, it caught a number of minor mistakes at the expense of really long compile times. ]

Bootstrap?

The compiler of stage two is now running on its own source...

Two hours later: It took two hours for the Hi to C compiler to compile itself, split evenly between compiling to objects and linking those objects. So, it's one hour objects and one hour linking where the majority of time is spend printing diagnostic output. The compiler itself is slow on some parts due to ill-chosen data structures. Guess I need to get around a factor 50-100 speedup from somewhere to get to reasonable performance, not nice, but doable in the current setting.

Of course, just compiling with -O3 just makes it twice as fast already. Another 50% or more off by not printing diagnostic information. 20% by using more simple test on record structures. 20%-30% by using incremental garbage collection. Memoization of FFI. That's about 1/(0.5*0.5*0.8*0.8*0.8)= 8 times faster, about a factor ten off target after that. So, I would need about three optimizations extra which take 50% off. Real texts instead of character lists, inlining and partial evaluation, specializing libffi, better internal data structures & faster algorithms in the compiler?

It generated C which compiled, guess I now need to rerun it again to get a proper fixed point out of it.

Later: Ouch, that failed immediately. It doesn't lexify right, looks like I still got an escape bug somewhere. Confirmed that, fixed something somewhere which wasn't broken in the first place I guess. It's a puzzle, actually.

So, everything is set except for that escaping bug, which is a nasty one since it may have been introduced as early as stage zero and give wrong results, infect the subsequent compilers, starting from there. No other choice then just to unit check from stage zero up to stage two to see if it handles all characters right.

Gawd, now even I am confused, lemme see:

1. Stage zero, a Hi compiler written in ML producing ML.
2. Stage one, a Hi compiler written in Hi producing C, linking to an ML runtime. (stage zero, rewritten)
3. Stage two, a Hi compiler written in Hi producing C, linking to a C runtime. (stage one, different native bindings)
4. Hi version 0.1, not even wrong. A Hi to C compiler (stage two bootstrapped).

Still computes, but not what they learned me in school.

Later: Dont feel like debugging again - stage one passes some unit tests, stage two doesn't? Back to C&C, see tonight what went wrong.

Later: So, \' becomes ', \" remains \" should be just " in stage two. Can't figure out who does what wrong. Is it stage one not matching correctly or a bug in stage two? The code looks correct.