The Compilation Passes

How many parser / compiler passes should be considered "many"?

The Tuplex compiler has four. Or five. Or seven... What do we count? You could count the lexical and syntax parsing as two separate passes. Or just as two parts of a single one since they combine into a single linear pass over the source text.

The semantic analysis has four distinct steps. But they don't all traverse the full program so do they count as separate passes?

Lexical Analysis

The lexical analysis scans the source text, removes comments and white space, and transforms it into a sequence of tokens, e.g. '+' or 'variable_name'.

The lexical scanner of Tuplex is written using Flex.

Syntax Analysis

The syntax analysis processes the token sequence and matches it to the grammar rules. Each matched grammar rule typically produces a node in the Abstract Syntax Tree (AST).

The syntax parser is written using Bison.

The grammar of Tuplex is a context-free, deterministic LR grammar.

Semantic Analysis

The semantic analysis is where it gets really interesting! This is where the meaning of the program is processed. The design and internal model of the semantic analyzer is unique for each language, although it will have conceptual similarities with compilers of other high-level languages in the same genre.

An important part of the vision for Tuplex is that all the core constructs be first-class citizens, general, and orthogonal. This puts a lot of complexity on the semantic analyzer. It's been remodeled and refactored a number of times, mostly driven by of the demands of the type resolution system.

Since Tuplex supports declaring types and fields in any order, the semantic analysis needs to be divided into two separate passes.

1 - The Declaration Pass

The declaration pass traverses the entire AST from start to finish and builds the namespaces and their symbol tables. It essentially maps each and every AST node to a scope in the namespace hierarchy, along with registering all declaration attributes and and flags together with the declaration names.

2 - The Resolution Pass

The resolution pass traverses the entire AST a second time. Since the declaration pass has completed before this, all the names are known and can be cross-referenced (resolved). The compiler can now create the internal representation of all the program entities - types, fields and functions.

This is where three major semantic operations are performed:

• AST transformations that depend on knowledge of the types / fields being used - e.g. inlining and special semantics for certain constructs like references and constructors.
• Type derivations - setting up the internal representation of all the types defined in the program.
• Type specializations - reinterpreting (copying and re-analyzing) of the AST sub-trees of the generic (parameterized) types that are being specialized with concrete type arguments.

2b - Deferred Type Resolutions

Certain parameterized type definitions are semantically recursive, even while being legal and well defined. Consider the definition of the Enumerable interface:

public interface Enumerable< E derives Enumerable<E> >

The constraint on the E parameter refers to the type being declared by this statement, and in addition the constraint refers to the parameter itself. To resolve such definitions the compiler works with a deferred ("lazy") resolution model. At the point where the type is defined a proxy is created for it, and put on the type resolution queue to be fully instantiated and laid out later.

2c - Data Type Layout

When all types are resolved they are mapped to static data types. The static data types are the distinct data types that will actually be used in runtime. They get assigned a distinct type id, a v-table entry, and tuples get their instance data laid out.

Code Generation

This pass invokes the LLVM API to generate LLVM IR for the program.


Theoretically the compiler could probably be condensed into two start-to-end passes over the source, with some lazy evaluation in the mix. However this would be very difficult to work with, even if the language was completely defined to begin with! These passes have evolved over the compiler development process and do make for effective separations of concern for different parts of the compilation.

On Uniformity of Syntax

One of the core philosophies behind Tuplex is to have a syntax that is as uniform and consistent as possible. This means that any semantic production should have the same syntax regardless of where it is placed. This has the benefits of:

• Regular grammar - easier to learn, read, and write
• Orthogonal semantics - helps keep semantic concepts independent and possible to recombine without "exceptions to the rule"
• Making copy-paste easier - reduces need for editing copied/moved code and the associated risk of bugs

Consider the core language elements of function, type, and value expressions. If these are written the same way regardless of the form of statement they are part of, we've come a long way towards uniformity.

Functions, being one of the most complex constructs both syntactically and semantically, are a good illustration of how well a language achieves uniformity. Examine your favorite language and how many distinct function, method, lambda, and function pointer syntaxes it has...

The following Tuplex program shows how function type declaration, global and local functions, instance methods and lambdas, all have identical syntax, and also are fully interchangeable in assignment, function argument passing, and invocation.

My favorite aspect of this is how instance methods, free functions and lambdas all are handled equivalently and for example can be passed as argument to another function without that function caring about the difference. Closure capturing, when needed, is fully transparent.


type FuncType : ( a : Int )->Int;

square( a : Int )->Int { return a * a; }

## these are equivalent:
aFunction : ( a : Int )->Int = square;
bFunction : FuncType         = square;
cFunction                   := square;


type Multiplier {
    b : Int;

    self( b : Int ) { self.b = b; }

    mul( a : Int )->Int { return a * self.b; }

    higher( f : FuncType )->Int {
        return f( self.b );
    }
}

main()->Int {
    localFunc := ( a : Int )->Int { return a * 2; };

    value : ~Int = 2;  ## ~Int means mutable 32-bit integer

    ## global function invocation:
    value = square( value ); ## 4

    ## local function assignment and invocation:
    tmpFn : ~FuncType = localFunc;
    value = tmpFn( value );  ## 8

    ## global function assignment and invocation:
    tmpFn = aFunction;
    value = tmpFn( value );  ## 64

    ## instance method assignment and invocation:
    mulObj := Multiplier(2);
    tmpFn = mulObj.mul;
    value = tmpFn( value );  ## 128

    ## higher order function and inline lambda:
    value = value + mulObj.higher( ( a : Int )->Int { return a+1; } );

    return value;  ## process returns 131
}

Quick Example

A reader might be curious about the syntax. This is a very short example program.



module my

type AType<S> {
    memref : Ref<S>;             ## default is private
 
    public self( s : Ref<S> ) {  ## constructor
        self.memref = s;
    }

    public getter()->Ref<S> {    ## Ref<S> can also be written &S
         return self.memref;
    }
}

main()->Int {
    obj := new AType<Int>( 42 );
    ret := obj.getter();
    return ret;
}

Spring Progress Update

How should one spend one's time...

I've focused on implementation since january and have regretfully not posted any progress updates. This is what's been done since then:

• Symbol table rewrite - DONE
• Central compiler "driver" routine incl options handling - DONE
• Modules and import handling - DONE
• Generic (parameterized) types except for reentrant code generation - DONE
• Proper integer literal type handling, range checking and conversion - DONE
• Bool type and boolean expressions - DONE
• Polymorphism (virtual lookup) for static members - DONE
• Function objects retaining their closure (e.g. 'self') - DONE
• Preserve type information in references - DONE
• 'self' implicit method argument - DONE
• Virtual methods - DONE
• 'new' operator and heap allocation - DONE
• Initializers / constructors - DONE
• super() constructor invocation; super.method() invocation - DONE

My next todos are:

• Generic type instance fields support
• Interfaces
• Checked type casts (with special if statements)

But before that I need to do an important refactoring. Finding a clean way of modeling the grammar nodes, symbols, fields and types becomes rather difficult when name overloading and generic types are part of the mix. I think I've finally found the proper dimension along which to achieve separation of concern / modularization. (And as so often, in retrospect the solution looks rather trivial.)

Essential Language Features

Added a static page called Essential Features. It attempts to describe on a single page what characterizes the Tuplex language - it's raison d'être so to speak!

Not all of them will be properly supported in the initial versions, but most are under way.

Currently I'm working with the generics implementation. It has turned out that even for doing a basic thing like a printf-style function, a lot of core semantic and code generation systems are needed.

Consider a simple String type:

public type String<L> derives Array<Char,L> {

  public static func length() UInt { return L }

  public func is_empty() Boolean { return self[0] == 0 }

}

It's just a handful of lines, but it requires a working version of all these systems, and generics is the one that isn't sufficiently capable yet:

• Symbol tables and namespaces
• Arrays
• Objects
• Static and non-static (instance) fields and methods
• Inheritance/polymorphism
• Generics (parameterized types)

Note btw how the length() method is both static and constant. In Tuplex the length is part of the array type, so it can be statically determined. In fact, type parameters are accessible directly (and why shouldn't they be, the information is there anyway!) so the method can be circumvented entirely:

  mystring := "foo"

  print( mystring.L )

--> 3