1 Massive refactoring to support better type systems. Read on for more.
3 The previous compiler had a simple pipeline, best outlined as:
4 (1) Parsing and name binding -> AST
5 (2) Storage allocation -> AST
6 (3) Semantic Analysis (SemA) -> AST
7 (4) Bytecode Compilation (BC) -> Code
9 This pipeline, unfortunately, had two problems. First, name binding cannot be performed in one pass if we wish to have multi-file support in the form of modules. Name binding must be two-pass.
11 Second, because SemA was only capable of annotating AST nodes with a single type, most coercion work had to be duplicated in the BC phase, as coercion was not explicit in the SemA output. This made introducing new type rules extremely difficult, and all but precluded concepts like operator overloading (or overloading at all).
13 This patch rewrites most of Keima's backend. Of interest are the following changes:
14 (1) CompileContext has been refactored around future multi-file support.
15 (2) Parsing no longer performs any name binding.
16 (3) The grammar for type-and-name has been changed from:
17 (Label | Identifier)? Identifier
21 Type ::= OldType | NewType
23 NewType ::= Identifier (. NewType)*
26 Although we do not implement the full production for Type yet, this
27 distinction is important. A type identifier is now affixed to the AST
28 as an Expression (right now, always a NameProxy), so it can fully
29 participate in name binding.
31 (4) Immediately after parsing, the AST goes through a NamePopulation phase.
32 This phase creates Scope objects for every scope which declares a name,
33 and if those names are declaring types or functions, a Symbol is created
34 and entered into the scope. Symbols entirely replace the old BoundName
37 (5) After NamePopulation comes NameBinding. This phase performs three steps:
38 (a) Links Scope objects together, to form a tree.
39 (b) Binds any free name to an existing name in the scope chain.
40 (c) Creates and registers any Symbols for names which have not yet been
41 added to the scope (for example, local variables).
43 In accordance, all "allocation" and "binding" concepts have been removed
44 from Scopes, which are now lightweight container classes.
46 (6) SemA now generates bytecode for each statement in the AST. Expression
47 compilation is performed via a separate mechanism called HIR (High-level
48 Intermediate Representation). To analyze an expression, SemA will walk
49 the AST, and produce a HIR object for each node. HIR is typed, and SemA
50 may insert coercion nodes, or even expand an AST node into multiple HIR
51 nodes. The result of evaluating an expression in SemA is therefore the
52 the root of a HIR tree, which SemA then sends to the HIRTranslator, which
53 performs bytecode generation.
55 As before, SemA still performs full semantic analysis. However, not it
56 also produces each function's bytecode.
58 This split allows us to decompose potentially complex semantics into
59 a more fine-grained, AST-like structure, which can have very simple
60 code-generation logic. For example, (1.0 + 5) might look like:
62 HAdd(HFloat(1.0), HConvert(HInteger(5), <Float>))
64 As part of this decomposition, many opcodes have been removed. Rather than
65 using typed jumps, we now expand jumps into longer tests. For example:
72 This simplifies the pipeline, and JITs should be able to melt the added
75 HIR is not used at a statement level, and HIR does not have any concept
78 (7) The old BytecodeCompiler has been removed, as its work is now split
79 between SemA and HIRTranslator.
82 In addition, some minor refactorings have taken place:
84 (1) Opcodes.tbl no longer hardcodes numbers (aaah).
85 (2) Type has been split into smaller, typed structs.
86 (3) BytecodeEmitter no longer relies on Pools or RootScopes.
87 (4) SemA is now responsible for variable/storage allocation.
88 (5) Native table are now global, rather than per-module. As such, native
89 declarations now result in a Native object (which still requires a
90 CALLNATIVE opcode), which is an index into the global table. Natives
91 must be bound globally. This is in preparation for module support.
92 (6) Publics are no longer tracked, but rather registered via a global
93 callback upon module load. This callback can be set by embedders. This
94 is in preparation for multi-file support.
95 (7) The BytecodeEmitter now performs Symbol allocations itself, and it
96 also generates Code objects itself, which removes a good deal of
99 Finally, a test harness has been added. This harness is a python script which finds *.test files, recursively, in the tests folder. For each file it runs the corresponding .sp. The contents of the .test file must match stdout+stderr.
