What a Language Needs to Know Before It Can Compile Itself

Introduction to the Lambda (lm) Language

Lambda (lm) is a small low-level language designed for demonstrating and researching various programming concepts. This language stands out with its static typing, explicit memory management, lack of closures, and absence of a garbage collector. lm has four independent backend versions that produce code in C, WebAssembly, ARM64, and machine code for a virtual machine.

An important part of any language is its compiler. For lm, the compiler is written in JavaScript and consists of approximately 4,400 lines of code. However, the most intriguing part is the initial attempt to make the language capable of compiling itself. In this article, we will explore the problems that arise from this and how they are resolved.

Self-Compilation: First Steps

The first step towards making the language capable of self-compilation was rewriting its lexer. The lexer is the part of the compiler that breaks down the source code into tokens. In lm, the lexer comprises 355 lines of code, whereas in the original code, it only contains 129 lines. The size difference is explained by several key features of the language.

Lack of Scalar Local Value Addressability

One of the main differences between lm and many other languages is the lack of the ability to obtain an address of a scalar local value. This means a function ca

ot directly modify a variable in its calling module. Instead, every function returning three values must use a structure that is created on each function call.

// Original lm code example
function foo() {
    return [1, 2, 3];
}

// lm code example
struct Result {
    int val1;
    int val2;
    int val3;
}

Result foo() {
    Result result = {1, 2, 3};
    return result;
}

Column Management Inside String Literals

Another important feature of lm is the lack of support for UTF-8 inside string literals. This necessitates handling UTF-8 byte continuations inside string literals.

// Original lm code example
console.log("Hello, world!");

// lm code example
console.log("\x48\x65\x6c\x6c\x6f, \x77\x6f\x72\x6c\x64\x21");

Optimization and Testing

When rewriting the lexer, the initial goal was to identify functions that ca

ot be implemented in lm and test them before the code becomes too large to change. In src/lexer.js, the function advance(n) is used to move the position, line, and column together. This function is called from fourteen places.

// Original lm code example
function advance(n) {
    pos += n;
    col += n;
    line += Math.floor(n / 80);
}

// lm code example
function advance(n) {
    for (let i = 0; i < n; i++) {
        let ch = buffer[pos++];
        if (ch === '\n') {
            line++;
            col = 0;
        } else {
            col++;
        }
    }
}

Conclusion

Rewriting lm's lexer showed that the language ca

ot support some features that exist in other languages. This helped the team understand the boundaries of the language and improve its design. Although the process was complex and required significant effort, it led to a more understandable and efficient language.

Practical Tips

• When developing your own language or compiler, it is important to define the language's boundaries early on.
• Using testing early in the development process can help identify issues and improve design.
• Ensuring full compatibility with other languages may require additional effort, but it enhances the adaptability of your language.

SEO and Metadata