A Program That Translates and a Program That Runs

In one line

A compiler is a program that translates a program into a program in another language without running it, and an interpreter is a program that runs it right away as it reads. The two share the same front end (turning characters into tokens, tokens into a tree, and checking the meaning of the tree) and part ways at the end, over "do we compute now, or leave behind code to compute later?"

Why this was needed

A CPU cannot read x = (a + 1) * 2. All it can read are instructions such as add and imul and register numbers. Someone has to bridge the distance between text that is good for people to write and instructions a machine can run, and there are two moments at which to bridge it.

• Once, before running (a compiler). Translation takes time, but the translated result runs fast any number of times. A good share of errors — a missing variable, a mismatched type, unbalanced parentheses — can be caught before the user even runs the program.
• Every time, while running (an interpreter). It runs immediately without waiting for translation, but if it runs the same line a million times, it interprets it a million times. In exchange, the implementation is simple and it is easy to look into the running state.

In practice the two are mixed. Python compiles source into bytecode (the .pyc in __pycache__) and then interprets that bytecode. In Java, javac produces bytecode, and the JVM first interprets it and then compiles to machine code only the methods that run often (JIT). So "where is each stage done, and when" is a more accurate question than "is this a compiled language?"

How it works

A compiler is not one lump but a line of stages. The output of one stage becomes the input of the next, and this course's modules follow that line exactly.

소스 글자 ──렉서──▶ 토큰 ──파서──▶ 트리(AST) ──의미 분석──▶ 검사된 트리
   (2모듈)            (3모듈)              (4모듈)
                                              │
            ┌─────────────────────────────────┼──────────────────────────┐
            ▼                                 ▼                          ▼
     트리를 걸으며 실행               바이트코드 + 스택 VM        중간 표현 → 최적화 → x86-64
        (5모듈)                            (6모듈)                  (7·8·9모듈)

gcc also runs the same line as several separate programs. Normally it is hidden behind the single line gcc hello.c, but with options you can stop it at each stage.

Option to stop at	What it did	Output
-E	Preprocess — expand #include and substitute #define	.i (still C)
-S	Compile — C to assembly	.s (text)
-c	Assemble — assembly to machine code	.o (a relocatable object file)
(none)	Link — join object files and libraries	An executable

An object file still contains names whose addresses have not been fixed. The printf that hello.o calls is in libc, so nm hello.o prints U (undefined) in front of that name. The linker fills in that blank. This is why there are errors ("undefined reference to …") that occur only at the link stage — compiling looks at one file, and linking looks at everything.

You also have to check separately that the interpreter and the compiler keep the same meaning. The calculator in this lab truncates division toward 0 like C (-7 / 2 is -3). Python's // rounds down (-4), so if you write the interpreter in Python and use //, the same program gives different answers in the interpreter and in the compiled executable. Whether the meanings of two implementations match is not preserved automatically; you only know by running and comparing. That is also why this course's grader compares against a reference implementation with random inputs in almost every step.

What it looks like in the field

• The build works but the link does not. A header (#include) gives only declarations, so compilation passes, and if you leave out from the link line the library that holds the definitions, you get undefined reference. If you know at which stage of the table above it occurred, where to fix it (the source or the build configuration) splits right away.
• "Python is an interpreted language, so it is slow." The reason it is slow is not that it does not compile but that each individual bytecode instruction checks types at run time. If you recompile the hot spots at run time (JIT), as PyPy or the JVM do, the same source can get tens of times faster.
• Build caches in CI. Because compilation finishes per file and linking is separate, an incremental build that recompiles only the changed files and just relinks is possible.

The language you build throughout this course is "Mini." It has 64-bit integers and booleans, let, print, if, while, fn, return, and roughly twenty operators with precedence, and that is all. It is small, yet enough to follow a single line from the lexer to x86-64 code, and the grader can actually run every stage.

What you will do in the next lab

You stop /opt/fixtures/mini/c/hello.c at each stage with gcc to make four outputs, and look at the blanks of the object file with nm. Then you build an RPN calculator twice in a single rpn.py — an interpreter that splits into tokens and computes directly with a stack, a checker that does not run but only follows the stack depth, and a compiler that writes C doing the same computation and bakes it with gcc. Finally, you compare whether the two paths give the same answers with random programs, and measure which is faster and when.