proj-plbook-plPartImplementation

Table of Contents for Programming Languages: a survey

Part V: Implementation of a programming language

This is not a book about how to implement a programming language. However, even at the earliest stages of language design, it is valuable to have some idea of how the certain choices in the design of the language could make the implementation much less efficient or much more difficult to write. For this purpose, we'll provide a cursory overview of implementation topics, touching as we go on some of the language design choices that may have a large impact.

Chapter : the general pipeline

• parsing (and lexing)
• parse tree -> AST
• variable binding?
• what else here?
• typechecking?
• basic blocks, control flow graph (also explain call stack, and possibly scope/block stack, at some point)
  • see also https://en.wikipedia.org/wiki/Extended_basic_block
• what else here?
• runtime

when do we convert to normal forms?

todo

" The first big phase of the compilation pipeline is parsing. You need to take your input and turn it into a tree. So you go through preprocessing, lexical analysis (aka tokenization), and then syntax analysis and IR generation. Lexical analysis is usually done with regexps. Syntax analysis is usually done with grammars. You can use recursive descent (most common), or a parser generator (common for smaller languages), or with fancier algorithms that are correspondingly slower to execute. But the output of this pipeline stage is usually a parse tree of some sort.

The next big phase is Type Checking. ...

The third camp, who tends to be the most isolated, is the code generation camp. Code generation is pretty straightforward, assuming you know enough recursion to realize your grandparents weren't Adam and Eve. So I'm really talking about Optimization...

-- http://steve-yegge.blogspot.ca/2007/06/rich-programmer-food.html

modified from Python's docs:

" The usual steps for compilation are:

    Parse source code into a parse tree
    Transform parse tree into an Abstract Syntax Tree
    Transform AST into a Control Flow Graph
    Emit bytecode based on the Control Flow Graph" -- https://docs.python.org/devguide/compiler.html#abstract

discussions on the benefits of the introduction of a 'Core' or 'middle' language in between the HLL AST and a lower-level, LLVM-ish language:

• https://news.ycombinator.com/item?id=11581863
  • this thread is discussing the following Rust-specific link, which also makes some general points near the beginning: http://blog.rust-lang.org/2016/04/19/MIR.html

some advantages of a core language:

• the core language can allow powerful but unsafe constructs that are not allowed in the HLL (eg for Rust, GOTO, downcasting, changing potentially shared variables conditionally upon some conditions where they have not actually been shared; [1])
• the core language has fewer primitives than the HLL so it is easier to work with than the HLL AST; but compared to a LLL (low-level language) like LLVM, less high-level intent has been lost, so it is easier to write some optimizations, or other analysis like borrow checking, on the core language than on the LLL
• more caching for incremental re-compilation within compilation units
• focuses the designer's mind on what is 'core' for the language

Links:

• http://stackoverflow.com/questions/2135788/what-do-c-and-assembler-actually-compile-to
• https://en.wikipedia.org/wiki/Compiler#Structure_of_a_compiler
• https://en.wikipedia.org/wiki/Compiler#Front_end
• https://en.wikipedia.org/wiki/Compiler#Back_end
• https://en.wikipedia.org/wiki/Compiler_construction
• http://www.montefiore.ulg.ac.be/~geurts/Cours/compil/2014/01-introduction-2014-2015.pdf
• http://www.montefiore.ulg.ac.be/~geurts/Cours/compil/2011/03-syntaxanalysis-1.pdf
• https://web.archive.org/web/20210111064441/https://nicoleorchard.com/blog/compilers
• http://craftinginterpreters.com/a-map-of-the-territory.html
• https://chidiwilliams.com/post/crafting-interpreters-a-review/

todo: somewhere put my observations on LLLs and target languages:

'target' languages include both 'Core languages' and LLLs

goal for:

• HLL: usability
• core: easy compilation from HLL->core; easy manipulation by compiler transformations (implies simplicity). Unlike HLL, verbosity is fine. Unlike LLL, machine sympathy is not necessary.
• LLL: efficiency (for actual assembly languages) OR ease of transformation to backend (and similar enough to actual assembly such that stuff which looks efficient in the LLL remains so after compilation to assembly) (for eg LLVM)

Core languages tend to be: similar to the HLL, except: de-sugared (eg apply various local 'desugar' tranformations) have fewer primitives than the HLL (eg de-sugaring various control flow constructs to GOTO) in safe or prescriptive languages, sometimes the Core primitives are more powerful than the HLL (eg in Rust the MIR core language has GOTO but Rust does not) still retain function calling have explicit types have a bunch of other things that are explicit, so that the LLL is way to verbose for human use, but with a similar control flow to the original HLL like the HLL but unlike LLL, still nonlinear (parethesized subexpressions are still present)

LLLs and 'assembly' languages are more similar to each other than you might expect.

LLL general properties:

• linear, rather than AST (each instruction is at an address; you cannot give a parenthesized subexpression as the argument to a primitive instruction)
• no type polymorphism (would lead to inefficient dispatch)
• fixed sizes for things (eg almost always a max bit width of addresses, often a the max # of arguments that a primitive instruction can take)
• designed along with, and constrained by, an instruction encoding (eg # of registers and addressing modes may be small so as to permit a dense instruction encoding)
• designed along with, and constrained by, internal representations for primitive data types
• often takes multiple instructions to do one 'primitive' thing such as a function call (eg first you must marshal the function arguments into their proper place, then you call the function)
• often LLLs are in a 'canonical form' such as SSA, CPS (eg LLVM is SSA), or if not, often the compiler chooses to transform to a canonical form before the LLL

Main families of LLLs: imperative * stack vs. register machines stack machines (eg JVM, Python's, mb Forth) register machines * 3-operand vs 2- or 1-operand register machines * various calling conventions * addressing modes LOAD/STORE vs addressing modes vs LOAD/STORE with constant argument but self-modifying code explicit constant instructions (eg ADDC) vs constant addressing mode vs LOADK * are registers and memory locations actual memory locations upon which address arithmetic can be done (like in assembly), or just variable identifiers (like in Lua)? functional * eg https://en.wikipedia.org/wiki/SECD_machine combinator * eg Nock

Also, instruction encodings might be fixed-width or variable (most are variable).

Primitive operations in LLLs: not as much variance as you might expect. Generally:

• most everyone has basic arithmetic; addition, subtraction, maybe multiplication, maybe division, various shifts
• some sort of GOTO
• some sort of conditional local branch or skip; possibly with a TEST or COND instruction separated from the branch/skip, possibly not
• possibly bitwise test/set
• possibly bitwise boolean ops
• possibly some composite data structures; some variance here but not a ton
  • cons cells
  • fixed-size vectors
  • variable-length arrays
  • associative arrays
  • strings

Links regarding stack machine vs register machines:

• "Interpreters for virtual stack machines are easier to build than interpreters for register or memory-to-memory machines; the logic for handling memory address modes is in just one place rather than repeated in many instructions." -- [2]
• [3]
• Registers vs stacks for interpreter design says "it's easier to generate code for a stack machine" but goes on to say that register machines may be more efficient.
• Register machines may be faster, according to Virtual Machine Showdown: Stack Versus Registers by Yunhe Shi, David Gregg, Andrew Beatty, M. Anton Ertl.
  • (cites The case for virtual register machines)
• https://en.wikipedia.org/wiki/Stack_machine ([4])
• A Performance Survey on Stack-based and Register-based Virtual Machines
  • discussion: https://news.ycombinator.com/item?id=13154111
• Why have a stack? by Eric Lippert
• https://web.archive.org/web/20200610223140/http://home.pipeline.com/~hbaker1/ForthStack.html

---

Someone's response to the question "Does anyone know if there is research into the effects of register counts on VMs?":

" Someone 1819 days ago [-]

If you can map all VM registers to CPU registers, the interpreter will be way simpler.

If you have more VM registers than CPU registers, you have to write code to load and store your VM registers.

If you have more CPU registers than VM registers, you will have to write code to undo some of the register spilling done by the compiler (if you want your VM to use the hardware to the fullest.)

So, the optimum (from a viewpoint of 'makes implementation easier') depends on the target architecture.

Of course, a generic VM cannot know how many registers (and what kinds; uniform register files are not universally present) the target CPU will have.

That is a reason that choosing either zero (i.e. a stack machine) or infinitely many (i.e. SSA) are popular choices fo VMs: for the first, you know for sure your target will not have fewer registers than your VM, for the second, that it will not have more.

If you choose any other number of VM registers, a fast generic VM will have to handle both cases.

Alternatively, of course, one can target a specific architecture, and have the VM be fairly close to the target; Google's NaCl?