lm is a small low-level language I wrote: static types, explicit memory, no closures, no garbage collector, and four independent backends that emit C, WebAssembly, ARM64 and bytecode for a VM. Its compiler is about 4,400 lines of JavaScript. The obvious next question is whether the language can compile itself, and the obvious first step is the lexer, which is 129 lines.
In lm the same lexer is 355 lines. That ratio is the finding, because almost none of it is lm being a verbose language. Six specific absences account for nearly all of it, and writing them down was a planned milestone rather than an afterthought: the point of porting the lexer first was to find out what the language could not do while the port was still small enough to abandon.
The one that cost the most
src/lexer.js has a single advance(n) that moves pos, line and col together, called from 14 places. lm had no way to take the address of a scalar local, so a function could not mutate a caller's variable, and a function returning three values would need a struct allocated on every call. So advance does not exist. All 14 sites write pos += 1; col += 1; inline, and the newline case writes the three-line variant.
That is the single largest source of the size difference, and it also caused the only correctness bug in the port. Column counting inside a string literal has to skip UTF-8 continuation bytes, and because the logic is inlined rather than centralised there is no one place to fix it. The two comment scanners over-count a column in exactly the same way. They get away with it only because a comment always ends at a newline, which resets the column before anything reads it.
That is worth sitting with. A centralised advance would have been fixed once and been right in all three places. Instead the code is right in one place by correction and in two others by luck, and the luck is load-bearing: change what terminates a comment and two latent bugs become live ones. Duplication did not make the bug; duplication made the fix local when the bug was not.
The other five
No globals or constants. The keyword and operator tables get built inside main at run time, every run. The waste is small; the real cost is that anything needing them takes them as parameters, and the same goes for the one scratch buffer the output helpers share, which has to be threaded through six functions by hand. Without that threading each helper would call alloc itself, and with no free that leaks one cell per call: emitting the token stream for this file is around ten thousand such calls, or 80 KB of unreclaimable heap out of 1 MiB.
No character literals and no hex. Every byte constant is a decimal number. c == 35 for #, c == 92 for a backslash, c == 34 for a quote, + 48 to turn a digit into ASCII, c & 192 == 128 for a UTF-8 continuation byte. The JavaScript writes c === "#". The lm version is correct and close to unreadable, and a comment naming each constant is the only defence.
No string type, so no string comparison. Matching an identifier against fifteen keywords is strlen plus a byte loop per keyword. The JavaScript is KEYWORDS.has(text).
No early exit from a search. break cannot carry a value and there are no labelled loops, so the keyword and operator scans run to completion and guard every iteration with a flag:
for i in 0..34 {
let o = ops[0][i];
if (hit as i64) == 0 && matchesAt(src, pos, o) { hit = o; }
}
That is 34 comparisons where OPERATORS.find stops at the first hit. Correct, slower, and it reads worse than what it replaces.
No growable array. A token list cannot be built, because there is no realloc and every token would own a string, so tokens are streamed to stdout as they are recognised. For a lexer that is arguably the better design; for a parser it is not, and I wrote at the time that this was the item most likely to decide whether the next stage was feasible.
What did not come up
The list above is misleading without this part. Structs, fixed arrays, arrays of pointers, function pointers, for loops, compound assignment, the full integer type set and u64 arithmetic all did what was needed with no workaround at all. The array-of-strings table works exactly as you would write it:
let ops = new([*u8; 34]);
*ops = ["<<=", ">>=", "==", "!=", ...];
The language was not the obstacle. Six specific absences were, and that distinction is the whole value of doing this as a measurement rather than an impression. "The language felt awkward" would have produced a wishlist. Counting what each absence cost produced an ordered one.
The list was ordered, and two of them got built
The recommendation, in the order they pay off, was: address-of on a scalar local, then a growable allocation, then top-level const, then character and hex literals. The first two are now in the language, and the parser, checker and emitter stages that followed all used them.
& carries a cost the original note recorded and I want to repeat, because it is the sort of thing that is obvious only after you have it. An addressed local lives in a frame allocated from the flat region on entry, and there is still no free, so a function that takes the address of its own local and is called N times leaks N frames. That suits a lexer, where main holds the state and passes &pos down; it does not suit a recursive descent parser, where the functions taking addresses are the ones called thousands of times.
The classification was wrong once, and the next stage proved it
I filed "no globals" under merely annoying; in the parser it was a correctness problem.
With no globals, the operator precedence table is either threaded through every call or allocated where it is read, and the parser allocated it: a 54-entry allocation per precedence test, tens of thousands of them, against a heap with no free. One of the test programs simply never finished parsing. The tables live in the parser state now.
So the severity ranking in that document was right about which items cost the most lines and wrong about which one could break a program. Those turn out to be different questions, and the lexer could not distinguish them, because a lexer allocates once per token and a parser allocates inside its hot loop. A single-stage measurement produced a single-stage ranking, and I presented it as though it generalised.
What generalises
Self-hosting is usually described as a milestone, and it is more useful as an instrument. A language's missing features are invisible while you are writing programs that fit on a screen, because you route around each absence in a few lines and forget it. Porting a program you did not write, against a reference implementation you can diff, turns each of those routes into a measurable cost: 14 inlined sites, 34 comparisons instead of 1, 80 KB of unreclaimable heap, one bug that survives on the behaviour of comments.
The gate I set for this milestone was to stop if the list ran long, on the grounds that growing the language to fit is a different project from self-hosting it. Six items with two clear priorities is not long. The judgement that mattered was not "is lm good enough", which is unanswerable, but "which four absences are worth building, in what order", which the port answered on its own.
LIMITS.md is in the repository, with each entry beside the code it cost.
This article was originally published by DEV Community and written by Seth Wheeler.
Read original article on DEV Community