Compiler analysis of clojure operation principle

Clojure is a compiled language, yet remains completely dynamic — every feature supported by Clojure is supported at runtime. Rich Hickey https://clojure.org/

there runtime refer to JVM,JVM At first, it was for operation Java Designed for language , Now it has developed into a heavyweight platform , except Clojure outside , Many dynamic languages They also choose to be based on JVM To achieve . For a more specific description Clojure Operation principle , There will be two articles to introduce . This is the first article , The main contents involved are ： Compiler workflow 、Lisp The macro mechanism of . The second part will mainly analyze Clojure Program compiled into bytecode How to ensure the characteristics of dynamic language and how to accelerate Clojure Program execution speed , This will involve JVM Class loading mechanism of 、 The reflex mechanism .

A compiled VS. interpreted

SO There is a problem Is Clojure compiled or interpreted, According to the official website quotation at the beginning of this article , explain Clojure It is a compiled language , It's like Java、Scala. however Clojure And Java What's different is ,Clojure You can compile at run time and then load , and Java Clearly distinguish between compile time and run time .

Compiler workflow

It is similar to the interpreter in interpretive language , Compiled languages pass through compilers （Compiler） To compile the source program into bytecode . Generally speaking , The compiler includes Two parts ：

• front end ： Lexical analysis → Syntax analysis → Semantic analysis
• Back end ： analysis 、 Optimize → Target code generation

Clojure Our compiler also follows this pattern , It can be roughly divided into the following two modules ：

• Read Clojure Source program → participle → structure S- expression , from LispReader.java Class implementation
• Macro extension → Semantic analysis → Generate JVM Bytecode , from Compiler.java Class implementation

The above figure shows the input and output of different stages , The specific implementation is explained one by one below .

LispReader.java

Generally speaking , Programming languages with complex syntax will separate lexical analysis and grammatical analysis into Lexer And Parser, But in Lisp In the family , The syntax of the source program is already AST 了 , So the Lexer And Parser Merge into one process Reader, Core code The implementation is as follows ：

for (; ; ) {

    if (pendingForms instanceof List && !((List) pendingForms).isEmpty())
        return ((List) pendingForms).remove(0);

    int ch = read1(r);

    while (isWhitespace(ch))
        ch = read1(r);

    if (ch == -1) {
        if (eofIsError)
            throw Util.runtimeException("EOF while reading");
        return eofValue;
    }

    if (returnOn != null && (returnOn.charValue() == ch)) {
        return returnOnValue;
    }

    if (Character.isDigit(ch)) {
        Object n = readNumber(r, (char) ch);
        return n;
    }

    IFn macroFn = getMacro(ch);
    if (macroFn != null) {
        Object ret = macroFn.invoke(r, (char) ch, opts, pendingForms);
        //no op macros return the reader
        if (ret == r)
            continue;
        return ret;
    }

    if (ch == '+' || ch == '-') {
        int ch2 = read1(r);
        if (Character.isDigit(ch2)) {
            unread(r, ch2);
            Object n = readNumber(r, (char) ch);
            return n;
        }
        unread(r, ch2);
    }

    String token = readToken(r, (char) ch);
    return interpretToken(token);
}

Copy

Reader The behavior of is by the built-in constructor （ There are currently figures 、 character 、Symbol These three categories ） With one called read table The extension mechanism of （getMacro） Driven ,read table Each record in it is provided with a characteristic symbol （ be called macro characters） To specific read behavior （ be called reader macros） Mapping .

And Common Lisp Different , Ordinary users cannot expand Clojure Inside read table. About extension read table The benefits of , You can refer to StackOverflow Upper What advantage does common lisp reader macros have that Clojure does not have?.Rich Hickey stay One Google Group There are explanations that are not open read table The reason of , Here is an excerpt from ：

I am unconvinced that reader macros are needed in Clojure at this time. They greatly reduce the readability of code that uses them (by people who otherwise know Clojure), encourage incompatible custom mini- languages and dialects (vs namespace-partitioned macros), and complicate loading and evaluation. To the extent I’m willing to accommodate common needs different from my own (e.g. regexes), I think many things that would otherwise have forced people to reader macros may end up in Clojure, where everyone can benefit from a common approach. Clojure is arguably a very simple language, and in that simplicity lies a different kind of power. I’m going to pass on pursuing this for now,

By the end of Clojure 1.8 edition , There are nine in total macro characters:

Quote (')
Character (\)
Comment (;)
Deref (@)
Metadata (^)
Dispatch (#)
Syntax-quote (`)
Unquote (~)
Unquote-splicing ([email protected])

Copy

Their specific meanings can be referred to Official documents reader#macrochars.

Compiler.java

Compiler Class mainly has three entry functions ：

• compile, When calling clojure.core/compile When using
• load, When calling clojure.core/require、clojure.core/use When using
• eval, When calling clojure.core/eval When using

These three entry functions will call macroexpand、analyze Method , Generate Expr object ,compile The function also calls emit Method generation bytecode.

macroexpand

Macro There is no doubt that Lisp The Dragon butcher's knife in the world , Can be in Compile time Automatic code generation ：

static Object macroexpand(Object form) {
    Object exf = macroexpand1(form);
    if (exf != form)
        return macroexpand(exf);
    return form;
}

Copy

macroexpand1 Function to do the main extension work , It will be called isMacro Judge the present Var Is it a macro , And this is through inspection var Is it a function , And meta information macro Is it true. Clojure Inside through defmacro Function to create a macro , It will be called var Of setMacro Function to set meta information macro by true.

analyze

interface Expr {
    Object eval();
    void emit(C context, ObjExpr objx, GeneratorAdapter gen);
    boolean hasJavaClass();
    Class getJavaClass();
}
private static Expr analyze(C context, Object form, String name)

Copy

analyze Conduct major semantic analysis ,form Parameters are various data structures after macro expansion （String/ISeq/IPersistentList etc. ）, The return value type is Expr, You can guess ,Expr Subclasses of are the body of the program , Follow the modular programming style , Every subclass knows how to evaluate itself （eval） Or output bytecode（emit）.

emit

What needs to be clear here is ,Clojure The compiler didn't put Clojure The code changes to the corresponding Java Code , But by means of bytecode Operation Library ASM Direct generation can run in JVM Upper bytecode.

according to JVM bytecode The specification of , Every .class Files must consist of classes , and Clojure As a functional language , The body is a function , adopt namespace To encapsulate 、 Isolation function , You may take it for granted that everyone namespace Corresponding to a class ,namespace Each function in the class corresponds to the method in the class , In fact, this is not the case , according to Clojure Official documents , The correspondence is like this ：

• Each file 、 function 、gen-class Will generate a .class file
• Each file generates one <filename>__init Load class for
• gen-class Generate classes with fixed names , Convenience and Java Interaction

Generated bytecode It will be introduced in detail in the second article in this series , Coming soon .

eval

Every Expr All subclasses of have eval Corresponding implementation of method . The following code snippet is LispExpr.eval The implementation of the , Other subclasses implement similar , I'm not going to repeat it here .

public Object eval() {
    IPersistentVector ret = PersistentVector.EMPTY;
    for (int i = 0; i < args.count(); i++)
        //  Here recursively find the value of each item in the list 
        ret = (IPersistentVector) ret.cons(((Expr) args.nth(i)).eval());
    return ret.seq();
}

Copy

summary

See before SICP After the implementation of several interpreters , But they are relatively simple , Through analysis Clojure Compiler implementation , Deepened eval-apply loop The understanding of the , Another point is to uncover the true face of macro , I always thought that macro was a magical thing , In fact, it's just Functions that run at compile time nothing more , The content of input and output is the data structure of the program , It is also inherent in the program AST.

Reference resources

• Decompiling Clojure II, the Compiler
• Clojure Compilation: Parenthetical Prose to Bewildering Bytecode
• The ClojureScript Compilation Pipeline
• Ahead-of-time Compilation and Class Generation
• The Reader