The Design and Implementation of an Extensible System Meta-Programming Language

In this section we describe the design and implementation of Sysmel, a System Metaprogramming Language, with a design inspired mostly in Smalltalk, Lisp and C/C++. With the objective of unifying system and non-system programming, with an extensible compiler and metaprogramming facilities we take strong inspiration on these three important historical languages: 1) from Lisp, we take important the concepts of macros as function from AST into AST (Steele and Gabriel, 1996), meta-circular evaluation (Reynolds, 1972), and the Meta Object Protocol used for defining an Object Oriented Programming environment (Kiczales et al., 1991); 2) from Smalltalk, we take object-oriented programming via message passing, blocks as closures, the importance of a minimalistic syntax, and reflection as a mechanism for meta-circular definition; 3) and from C/C++, we take primitive types, pointers and direct memory access. We infer a concept of using static primitives types as a mechanism for definining translational. These type defined semantics facilitate a direct to machine operation mental-model.

From these influences we distill the following feature wishlist that we want to support in a single programming language, even if there are conflicting between them:

1. (1)

   Minimalistic convenient to use flexible syntax.

2. (2)

   Everything should look like an object at the syntax level.

3. (3)

   Everything must be typed. Dynamic typing is realized via static typing.

4. (4)

   Type inference support. The minimum is supporting the local type inference like the C++ auto keyword. Stronger type inferences algorithms like Hindley-Milner (Hindley et al., 1969)(Milner, 1978) are desirable, but not required.

5. (5)

   Block closures.

6. (6)

   Arbitrary compile time evaluation support.

7. (7)

   Lisp style macros which are functions from AST into AST functions.

8. (8)

   Primitive types which are directly supported by the target machine.

9. (9)

   Pointers and direct memory accesses.

10. (10)

    Manual memory management support.

11. (11)

    Optional automatic memory management via garbage collection support.

12. (12)

    Compile time and optional runtime reflection.

13. (13)

    The ability for extending and modifying all of the compilation pipeline stages.

The Sysmel syntax is strongly based on the syntax from Smalltalk, but there are additions and changes taken from C/C++ to facilitate supporting different programming styles. Sysmel syntax is minimalistic and it is based around the concepts of message sending, function application, and the construction of commonly used data structures. Everything is an expression and returns a value with a specific type. See Listing 1 for a postcard that illustrate the whole Sysmel base syntax. Higher-level syntactical constructs are realized via composing these base syntax elements, and by using metaprogramming techniques that manipulate the AST during compilation time.

The scanning and parsing stages can be done by using traditional approaches such as manually written recursive descent parsing, or by using more extensible approaches like parser combinators. Parsing produces nodes which conform to the Meta Object Protocol. The top level nodes respond to the #analyzeAndEvaluateWithEnvironment: message. This single message is used for simultaneous analysis and evaluation of the top-level parsed source code. The environment received by it is used for looking identifier values. Lambda nodes are evaluated into closure objects, which are composed of two parts: a capture vector, and a function definition object which contains analyzed arguments and body nodes. The analysis of the elements of a function definition are performed by sending the #analyzeWithEnvironment: message onto the argument, result type and body nodes. This message is responsible of returning a newly analyzed node where its value type is solved, and its children nodes are also analyzed recursively. Once a function definition is analyzed, it can be evaluated via two different mechanisms: 1) direct interpretation of the analyzed node, supported through the #evaluateWithEnvironment: message. 2) compilation into a bytecode or an IR that can be further optimized and compiled into machine code. We support these two mechanisms. In summary, the AST node semantic analysis MOP is composed of the following messages: #analyzeAndEvaluateWithEnvironment:, #analyzeWithEnvironment:, #evaluateWithEnvironment:, #compileBytecodesDirectlyWith: and #generateSSAValueWith:.

AST nodes are defined as ordinary class instances inside of Sysmel. New AST nodes can be defined by just subclassing from ASTNode and then overriding the required methods. New AST nodes can be exposed in the language through macros. In fact, the local variable definition AST node is not present in the sysmel language syntax, but we expose it through two different mechanism: 1) macros like #let:with: and #let:type:with; and 2) the let metabuilder (See Section 2.3).

Function applications are analyzed in two phases: first as an unexpanded function application, where the functional object can be a macro. The macro is invoked with the non-analyzed parameter nodes as arguments. The node returned by the macro is analyzed recursively. In the case of expanded function applications, the analysis of the application node is delegated onto the functional object type. This allows treating any object or value as a functional object. In the case of ordinary functions, its evaluation is performed by constructing an activation environment with the evaluated arguments. In other cases, the #applyWithArguments: message is sent to the functional object. One important optimization is always performed if possible. We define functionally pure functions in terms of observable external side effects, so we allow programmers to perform internal definitions through impure imperative mechanisms. For this reason any function can be marked as pure function. A pure function application that only uses literal nodes is always evaluated in compile time, and the application node is replaced by a literal node with the evaluation result. This application of referential transparency for pure functions is mandatory, and we use it for constructing derived type literals.

In the case of message sends, there are also multiple analysis phases. First, the receiver node is analyzed, and the actual message send analysis is delegated onto the receiver node type. The receiver type first analyses the message selector. If the analyzed selector is a literal, then the corresponding macro or method is looked up through multiple dictionaries. If the found method is a macro, then it is expanded by receiving the receiver and argument nodes as parameters. If the method is not a macro, then there are two cases: if the method does not require dynamic dispatch (i.e., it cannot be overriden by a subclass), then the message send node is converted into a function application node which is analyzed recursively. If dynamic dispatch is required, then the remaining analysis of the message send is delegated onto the method type. If no method was found, if the receiver is not a dynamic type a semantic error is raised, otherwise a generic analysis is performed for the arguments of dynamic message sends.

The type system is another important side of the MOP. Types are also objects, and they are in fact instances of the class Type. The analysis of some AST nodes is delegated into specific types. This facilitates defining type specific translational semantics, binding message sends to methods statically, and defining type specific macros. We also use the type system for constructing pointer and reference types. C++ style references are used for constructing mutable variables. A reference type is constructed by responding to almost no message, except for #:= used for assignments, and address used for converting a reference into pointer. Pointers can be converted into references through the _ message. With these messages we support the semantics of the C pointer operators (&, *). The type system MOP is much larger than the MOP used for AST nodes. The following is a non-exhaustive list of some messages that are part of the MOP exposed in Type: #methodDictionary, #lookupSelector:, #analyzeAndEvaluateMessageSendNode:forReceiver:withEnvironment:, #analyzeMessageSendNode:withEnvironment:, #analyzeAndTypeCheckFunctionApplicationNode:withEnvironment:, #analyzeAndTypeCheckSolvedMessageSendNode:withEnvironment:, #ref, #pointer.

The optimization and code generation pipeline unlike the semantic analysis is a much more traditional process. We perform code generation and optimization successive translation from the analyzed AST into different intermediate representations (IR). We first translate the AST into a high-level SSA based IR with a design inspired by LLVM (Lattner and Adve, 2004), where we model our base language operation semantics like function applications, message sends, local variable allocation (alloca), pointer and object slot load and stores. At this level we represent primitive type intrinsics as function calls. In our current implementation we perform some optimizations like constant propagation, control flow simplification and inlining. We are planning on having many more optimizations at this level.

The high-level SSA form is translated into a mostly portable middle-level three address code IR which is also in SSA. The instructions of this IR is composed by tuples that contain a single machine primitive operation and its operands. We use this IR for performing lower-level optimizations like combining comparison with branches, and register allocation. We also compute the stack frame layout computation, and some phases of debug information generation during this stage before generating the next stage which is assembly.

Our low-level IR is assembly code. We use this IR for final machine code generation, and also for generating object files with included debug information. A subset of the program object graph is serialized into the data segment of the resulting object file, and references between objects are annotated with the required relocations. We are capable of generating platform specific relocatable ELF, COFF and Mach-O object file. Since we do not implement a linker, we rely on the standard linker provided by each operating system for constructing actual standalone executable programs.