Compiler 2 Part 9: Assembly Primer

Assembly is a huge topic and there are entire classes dedicated to the subject. It would be impossible to teach assembly in a single post but what I hope to achieve is enough of an overview to make the C code that’s going to be output by the compiler, and the C runtime, make some sense.

This article will be concerned with the x86 instruction set and architecture. There are several different syntax’s (Intel and AT&T for example) for assembly but I’ll try and keep the code as language agnostic as possible.

Sizes

Everyone ought to be familiar with a byte.

A byte is made up of a number of bits which represent the smallest unit of information. The vast majority of modern desktop PCs have 8 bit bytes. A single bit has two states: 1 or 0. A single 8 bit byte has 256 different combinations of bits.

Since a bit has two states, grouping multiple bits together can determine how many different combinations can be achived. In the case of an 8 bit byte, we calculate it by raising two to the power of eight, like so: 2^8 = 256. Therefore, a single byte has the ranges: -128 to 127 (signed) or 0 to 255 (unsigned). It is represented by a ‘b’.

A word is two bytes. In C this is the short type. It has 2^16 combinations or byte*byte. It has the ranges -32,768 to 32,787 or 0 to 65,535. It is represented by a ‘w’.

A long is two words or four bytes. In C this is usually the int or long type. It has 2^32 combinations and is represented by an ‘l’ (lower case L).

A quad is two longs, four words or eight bytes. In C it is usually the long long type. It has 2^64 combinations and is represented by a ‘q’.

Registers

There are eight basic, general purpose registers and they are follows:

Register	Name	Example Usage
ax	accumulator	arithmetic, return value
bx	base	data pointer, temporary storage of intermediate value
cx	counter	loops
dx	data	temp storage
sp	stack pointer	points to the top of the current stack frame
bp	base pointer	points to the bottom of the current stack frame
si	source index	source array index
di	destination index	destination array index

These registers can be accessed in various sizes (byte, word, long and quad). A quad sized (64 bit) register has an ‘r’ prefix, a long sized (32 bit) register has an ‘e’ prefix and both the word and byte sized registers have no prefix. The target architecture restricts which registers are available. As an example, 64 bit registers are not available on 32 bit machines.

The four registers ending in x can also have their hi and low bytes accessed for storing byte sized information. In these cases, the x is replaced by an h for the high byte and an l for the low byte.

Using the ax register as an example:

Register	8	7	6	5	4	3	2	1	Desc.
al	-	-	-	-	-	-	-	Y	byte (low)
ah	-	-	-	-	-	-	Y	-	byte (high)
ax	-	-	-	-	-	-	Y	Y	word
eax	-	-	-	-	Y	Y	Y	Y	long
rax	Y	Y	Y	Y	Y	Y	Y	Y	quad

The numbers 1 through 8 represent the bytes accessed.

64 Bit General Purpose Registers

In 64 bit mode, the registers R8 through R15 are also available. The eight general purpose registers discussed above constitute the first eight registers, 0 through 7. In 64 bit mode we have access to these additional eight registers, 8 through 15.

To access the 32-bit version of these registers requires the D (double-word) suffix (r8d), a W for 16-bit (r8w), and a B for byte access (r8b).

As an example of usage of these registers, the version of GCC installed on my machine will use the rcx, rdx, r8 and r9 registers as the 1st, 2nd, 3rd and 4th arguments to functions, respectively, when compiling for 64 bit.

Instructions

There are a lot of instructions but here are the ones needed to do some basic arithmetic.

Instruction	Action
mov a, b	Copies the data stored in a to b
add a, b	Add b to a and store it in b
sub a, b	Subtract b from a and store it in b
mul a, b	Multiply b by a and store it in b
div a, b	Divide b by a and store it in b

Depending on the language, the operands might be reversed (mov might copy a into b in one language but b into a in another). The way the registered are addressed in one assembly language or another might be different but rest assured if you understand one you shouldn’t have much trouble figuring out another.

An example of 2+3 in pseudo-code:

mov 3, eax (set eax to 3)
mov 2, edx (set edx to 2)
add edx, eax (add 2 to 3 and store it in eax)

Each instruction might have a specific size it operates on. So the mov function would have either b, w, l or q appended to the instruction name (movb, movw, movl and movq), as would the arithmetic operations.

Fun Fact: Another name for an instruction is opcode. Opcodes are mnemonics for an instruction code. Movl is actually the number 0x89.

Segments

There are six segment registers:

ss	stack segment, holds the address of the stack
cs	code segment
ds	data segment
es	extra segment
fs	extra segment (e+1 = f)
gs	extra segment (e+2 = g)

You don’t really have to worry about these too much. The stack segment is the only one we’ll be dealing with, and indirectly at that.

Stack

It took me some time to really wrap my head around how the stack works.

The stack segment holds a pointer to the first address in the stack. It doesn’t matter where this memory came from. It works like any other memory.

The stack space is separated into segments called frames. A frame is used to hold all the data needed for a function. This includes, but isn’t limited to, local variables, the return address of the function and a pointer to the previous frame.

The sp register, the stack pointer, holds the address of the top-most location on the stack. This is the top of the current, or active, frame. The bp register, the base pointer, holds the address of the bottom of the frame. The active frame is the address space between the sp and bp registers.

Stack Frame

In a stack data structure you push (add) and pop (remove) elements to and from the stack. I would describe manipulating the stack in assembly as more fluid or elastic.

A push or pop instruction will push a single element to the stack but that element might not necessarily be the same size as another element. Depending on other instructions you may need to align the stack pointer to the nearest 16 bits.

You can also request stack memory without a push or pop instruction at all. You simply take what you need and mark off the area with the bp and sp registers.

Caution

Assembly will let you do pretty much anything. It will hand you the gun, load a bullet into the chamber and hold your hand while you shoot yourself in the foot.

When adjusting the stack or base pointers, for example, you can set them to whatever memory addresses you want. Nothing will stop you from trying. That’s not to say it won’t have disastrous effects but it’ll let you do it.

Assembly has no notion of types. Want to add a character to a memory address? Ok! Want to overwrite part of a 64 bit value with a 16 bit value? Ok! It doesn’t care. It will obediently do what you tell it to. Consider this your forewarning.

Use extra, extra caution when programming in assembly.

Purpose

Why am I telling you all this?

Well, you might want to compile directly to assembly in your own project and this serves as a short primer on the subject. More importantly, as already stated, it is going to serve as a basis for the C runtime that has been provided.

As it turns out, assembly is useful for compiling languages. For one, it deals with data in a type agnostic way. As previously stated, assembly deals with values and memory addresses but it has no notion of type. It’s all just bits and bytes.

Additionally, the way registers work and how the stack is accesses is also of use. I won’t get into any details right now but passing arguments and handling variables is much easier than trying to translate them into a proper C equivalent function prototype.

Consider this: A language like Python is dynamically typed. C is statically typed. How do you translate a Python function prototype into a C prototype without knowing the value of the variables being passed at runtime a priori?

One answer is to use the void pointer type but I think a better answer to not use parameters at all.

I can’t say I’ve really done assembly much justice. There are heaps more to understand before I think you can really “get” assembly. If you’re interested in the subject, I highly recommend doing some searches.

Compiler 2 Part 8: Parser

After an annoyingly long time, I am finally getting the next installment of this series out.

The parser hasn't so much as changed as grown. If the abstract syntax tree is any indication, there is a lot of work that needs to be done in the parser!

Before we get to that though, I thought I’d take a quick moment to talk a little bit about the parser in general. I pointed out a few questions in Part 1 of the Calc 1 series I didn't understand when I first started to learn about compilers. I’ll try and answer a couple of them now.

Parsing

In the previous series, I dove right in to creating the parser but I didn't really explain much about parser technology.

To be blunt, I don’t think I'm the right person to teach you. I'm not an authority on parsing nor parser technology.

What I can do is point you in what I hope is the right direction and explain a little about this particular parser.

Top-Down, Predictive, Recursive Descent

The Calc parser is a top-down parser. It tries to figure out the overall structure prior to breaking down the smaller parts. In parsing a single file it resolves the file object, then broadly looks at global expressions like function declarations and so on until it gets down the smallest parts, usually a variable or basic literal.

It is also a recursive descent parser, which is a sub-type of a parser family called LL parsers. As the name suggests, it recursively descends from the top of the grammar tree down to the bottom. The parseGenExpr method is called recursively to determine the different types of expressions in the Calc language.

More specifically, it is a predictive recursive descent parser. I believe you would call it an infinite look-ahead, LL(*), parser, By virtue of how function parameters are parsed, the parser must continually look ahead an infinite number of tokens to discover the type of each parameter.

You don’t need to understand any of this to write a parser but I've always prescribed to the school of knowing WHY something works rather than just HOW it does it.

Let’s move on to look at the specific changes that happened in Calc 2. I'm going to go quite quickly and only focus on changes which may be non-obvious.

Parsing Files

Rather than take the source code of the file and parse it, ParseFile now takes a pointer to a token.FileSet. It now must go through the work of opening the file, reading the source, parsing it and adding the file to the fileset.

Parsing Directories

ParseDir fulfils the multiple source file requirement. It opens the supplied path, reads all the files in the directory and attempts to parse each file in turn.

In this incarnation, the calls to ParseFile happen in a linear fashion but is a perfect spot to use some of Go’s concurrency primitives to speed up parsing on a multi-core system. I chose not to implement it in Calc 2.

Parser Struct

A couple new fields have been added to the parser object. The listok field is used to determine if an ExpressionList is allowed when parsing expressions. More on that a bit later. The other to fields hold the current and top Scopes.

The curScope field is the most important to us. It tracks the current, active scope as the parser transitions between different expressions.

Initialization and Errors

Both addError and init were updated to accommodate the changes made to error facilities and new parser fields, respectively.

Scope

openScope creates a new scope using the current scope as the parent for the new scope.

Conversely, closeScope reverts back to the previous scope.

Assignment

Unfortunately, nothing too exciting is going on in parseAssignExpr, either. By virtue of look-ahead, we know to expect an ASSIGN token. The expect method is used to get the position to ensure nothing funny happened and to advance the scanner in one step.

Our grammar then tells us we expect an identifier so that’s what we attempt to parse. From there, we can receive any kind of expression from a basic literal to a binary expression or even a function call.

Finally, we expect to find a closing parenthesis and finish off the expression.

Basic Literals

A minor change was made to ensure the parser is always advanced after parsing the literal.

Calling Functions

Again, another small method. The first thing we expect to find is the name of the function being called so we parse an identifier.

This should be followed by a list of arguments for the call and capped off with a right parenthesis.

Note that types are not checked here nor are the number of arguments to the parameters in the function being called. That’s because the function may not be declared yet.

Calc 2 does not state that a function must be declared in lexical order as it would in C. Calc, like Go, let’s you declare a function anywhere in the source code and can therefore be called prior to it’s declaration.

Function Declarations

The fun really begins here.

At first, parseDeclExpr is pretty straight forward up until we hit the call to openScope. This scope is the scope of the function itself. The parameters of the function are unique to the function call and can’t be accessed outside of it. Same is true of any variables declared within the function body.

Once open, we parse the parameter list, adding any parameters found into the newly opened scope. The code for this will be looked at a little later.

Next, we require the return type.

Last, the body of the function is parsed via a call to a method called tryExprOrList, finally closing the whole thing of with another right parenthesis.

tryExprOrList will be discussed later but the purpose of this function is to determine if the body of the function is a simple expression or a list of expressions.

The object for the declaration is created as normal but you can see that an ast.Object is also created, taking the declaration as an argument.

After the function’s scope is closed, the object pointing to the function declaration is inserted into the current scope.

Expressions

The listok field of the parser comes into play here. If we’re allowed to parse an expression list we attempt to do so. If not, we continue on as normal.

The other new expressions that we need to parse have been added and their respective methods are called.

Expression List

parseExprList merely tries to parse a list of expressions and appends it to the list.

GenExpr

Very little changed here. Parsing an identifier as a basic expression has been added and you’ll note that listok has been assigned as false. That’s to ensure we don’t keep trying to parse a list.

File

The only thing that really changed here is that the ast.File now only has a Scope rather than an Expr field. A file must have at least one declaration in it. In the compiler stage, we’ll ensure that it’s a declaration called “main”.

Parameter Lists

If you recall in parseDeclExpr I said I’d come back to parsing the parameters. Well, here we are!

Each parameter needs a type. However, a type is the last thing in the list to be listed. So, we need to keep parsing identifiers until either a comma, signifying a new set of parameters with a different type will be declared, or a closing paren is found. After either has been found, we need to retroactively assign the final identifier, presumably the type, to the other identifiers.

Each parameter is then inserted into the function’s scope. While the function has a type it does not have a value. That will be taken care of when the function is called.

Unary Expressions

A unary expression is pretty quick and dirty. We take the operator, which we know to be a negation sign, and the value to be negated and wrap it up into a neat little package.

Variable Expressions

Parsing a var expression is actually a bit tricky. That’s because some of the elements are optional and some depend on what elements we've received.

If the token is an IDENT we parse an identifier. Easy. However, if the token is an LPAREN then we have an expression but a var expression may only take an AssignExpr as it’s first element. So, we forcibly parse the expression and if another type of expression has been used an error is generated.

If no value was parsed via an assignment then we must find an identifier with a type name. The type is optional if there is an assignment expression because the type can be inferred.

Last, we expect to find a closing paren.

When we insert the identifier into the current scope, we need to make sure it hasn't already been declared and generate an error if it has.

Expressions or Expression Lists?

This little method is really just a utility function. It’s pretty self-explanatory.

The reason I separated it out is to make it clear that we can have either an expression or a list. I found it helpful.

Done

And that’s about it!

Now, on to assembly! Wait...what?

Compiler 2 Part 7: AST

The scanner changes were pretty simple. The AST changes aren’t all that momentous either, per se; rather, it's more a matter of volume.

The additions in the language specification state that we need to create objects for: function calls, function declarations, identifiers and variable declarations. What might not be clear are that we also need objects to handle: assignment, if expressions, expression lists and scoping.

Assignment

If you recall from the first series, I used a nested object Expression in BinaryExpr. I explained that it would be of more use later.

It now gets used rather prolifically throughout the new objects and AssignExpr is no exception.

We track the position of the equals sign and the variable to which we’re assigning a value to. The last field contains the sub-tree of the value we’re assigning to the variable.

The value can be anything with a side effect. Function declarations (do not confuse with function CALLS) are an exception to this rule and can’t be assigned to a variable.

Function Calls

Calling a function is fairly simple. There’s an identifier which signifies the name of the function being called and a list of arguments for the function. That about sums it up!

Function Declarations

There are quite a few fields in DeclExpr. We need to keep track of the position of the ‘decl’ keyword. Then there’s the function’s ‘Name’ and it’s return type. The parameters are a list of variables and their corresponding types. The ‘Body’ of the function is an expression of some kind.

Finally, there’s a field to hold the Scope of the function. If you recall, each function has it’s own scope and this is where it’s stored!

List of Expressions

It’s just a list of expressions. Nothing to see here, move along please.

Identifiers

The identifier can be many things. It may be a type name, like int. It may be a variable name or a function name too.

It is also associated with an Object. The object is stored in the active scope. The object holds the current value and type of a variable or function. When an identifier is something like a type name, then Object is nil.

More details on the Object shortly.

Conditionals

Like the others, we first record where we found the ‘if’ keyword.

The Cond field holds an expression which evaluates to zero, for false, or any other number for true. Ideally, I would prefer the expression always evaluate to a boolean value but since we don’t have a boolean type, an integer will have to do!

The if expression is typed because it's functional.

The Then and Else clauses can by any kind of expression at this point. The type of, or returned by, the expression is not evaluated at this point. This will be verified further down the line when code generation is being handled.

There’s a Scope field for if expressions because they have scope, too.

Objects

The object consists of a Name, to which it is associated, and it’s position. We also want to know what kind of object it is. In this version of Calc it can only be either a variable or function declaration.

We also have a field used to track a variable’s offset when compiling but this will be addressed in a later post.

The Type of an object is important but may not be known during parsing. If the type is going to be inferred, then the type will initially be nil.

The Value is an expression representing the actual value of the variable. It could be anything, including nil.

Package

A package consists of a package level scope and a list of File objects.

Scope

The scope object points to a parent scope, or nil, and contains a table of identifier names mapped to an Object.

Unary Expression

Should be self explanatory.

Variables

We keep track of the position of the ‘var’ keyword. We keep track of the identifier used for the name and an Object representing the variable to save a call to Lookup for it later.

More Scope

Four functions have been introduced to work with scoping but only three are worthy of note. NewScope, creates a new scope. Insert, inserts a new object into the scope and returns either nil or the previous object assigned to the same value. Lookup returns nil or the object associated with ident.

Walk and Print

Walk was adjusted to deal with the new types.

Print is in sorry shape and probably should be removed. It could have been improved to display an AST in it’s entirety. I didn't care to update it for sake of time.

Compiler 2 Part 6: Scanner

Much like tokens, the scanner hasn't changed much but mainly gained some new functionality. This should be a short but sweet post.

Scan

To scan for an identifier, we detect if the current character in the scanner is a letter of some kind. This is per our specification for an identifier. If a letter was found, we scan for an identifier of some kind and return the result.

A small change to the next section allows us to scan two characters at a time for our comparison operators. Consider assignment verses equality. One operator has a single equals sign and the other a double equals sign. After storing the current character in a temporary variable, the scanner is advanced again so we can look ahead by one character.

Once we find a valid token and determine that it might be one of two different values, we call selectToken to determine which token we want. Since the scanner has already advanced to the next character, we test to see if it matches a second character. If it matches, we return the first token and advance the scanner again. Otherwise, we return the second token.

Next

The next function had a bug in Calc 1. A newline was never recorded as a result of the bug so the Position of a character was never properly reported. Since most of the source code passed to the Calc 1 scanner was always on a single line the bug wasn’t caught until after the compiler was released.

The bug has since been fixed and back-ported to Calc 1.

Identifiers

Like scanNumber, scanIdentifier continues to advance the scanner until the end of an identifier is found. As long as the first character of an identifier is a letter, the remaining characters can be a digit or a number.

The next part of the code is a little quirky. It is there to protect against the end of a file in the middle of an identifier, which is obviously an error. It also is needed when an identifier is alone on a line because it is the return value for a function.

Last, it makes a call to token.Lookup. This code, if you recall, determines whether the identifier is actually a keyword or just an identifier. That’s why we had to change the default return value of Lookup to the IDENT token, rather than ILLEGAL.

Summary

Again, not a lot to do here. There’s nothing particularly amazing in the additions.

On to parsing and the abstract syntax tree! This is where the major changes appear!

Compiler 2 Part 5: Tokens

Finally! We get to look at some code!

In the token package, I had to add a plethora of new operators, some keywords and a few other tokens.

New Tokens

The IDENT token will be used for any type of identifier, be it a variable name or a type name.

The COMMA token is a special case which only sees use in function parameters in Calc 2. When multi-value assignment and multi-variable declarations come in to play it will see more use.

The DECL, IF and VAR tokens are representative of the three keywords by the same names.

The balance of the new tokens are all new operators. ASSIGN for variable assignment, AND and OR for the corresponding logical operators and the other six are for comparisons.

The IsKeyword function was added to complement the other boolean testing functions.

Last, and perhaps most importantly, Lookup had a seemingly minor change with further reaching consequences. It now returns an IDENT token rather than ILLEGAL when looking up a string. This is useful in the scanner when determining whether an identifier is really an identifier or if it is actually a keyword.

Errors

Errors were moved from the scanner to the token package.

It felt like a better fit, here, considering tokens are used throughout the entire system whereas the scanner is only used by the parser. It now eliminates the need for an additional, essentially unnecessary, import.

The Add function was changed to make it easier to write error messages.

There are various other refinements to the error handling that I encourage you to look at but I go into here.

Files

The complete Calc source of the file is no longer stored in the File structure. It doesn't need to be there since it’s main facility is to help with error reporting throughout the package. All the data it needs is already there and the source wasn't ever used for anything but the file size.

The length of the source code now tracked by the size field.

The base field is now supplied as a parameter in NewFile. This is because the base value of the file may no longer be one when multiple files are involved.

FileSets

A file set holds the collective file information for a package. A new file set has a base of one for the same reason a file had a base of one in the previous series.

When the Add method is called, a new file is added to the set and the base is increased by the size of the source code added.

The Position of a token is now determined by cycling through the files in a file set. If the position (of type Pos) is within the base and the base + size of the file then we know the position is in that file. We then call Position method on the file to get the Position information from it for use in error reporting.

NoPos

Every variable has a type. When inferring a type of a variable via assignment, there is no actual type keyword. So, a new ast.Ident is created with the type’s name and given a position of NoPos. Using the term NoPos is more indicative of it’s use than illegalPos used in Calc 1 so the variable was renamed.

Summary

That concludes the changes to the token package. Not much work needed to be done here and I think the changes are pretty straight forward.

Adding new tokens or keywords is incredibly simple. Some of the infrastructure to support things like multiple source files is a bit more difficult but not too bad.

Lets move on to the scanner.

Compiler 2 Part 4: Language Design - Variables

Table of Contents

1. Introduction to Apprentice Compiler Design
2. Language Specification
3. Infrastructure
4. Language Design Decisions
5. Tokens
6. Scanner
7. AST
8. Parser
9. Assembly
10. C Runtime
11. Using the C Runtime (Assembly Part 2)
12. Compiler, Code Generation
13. Front End

Previously, I discussed the new language features and corresponding infrastructure that will be needed to implement Calc 2. Now I’d like to discuss language design a bit more, focusing on variable declarations.

In the first series of articles I discussed some of the thought that goes into language design. In this second series, we’re going to talk a bit more about that.

Variables

At first glance, variables are easy. A word or letter equals another value. No problem!

Not so fast!

First, you might decide what the declaration is even going to look like so we can fit it into our grammar rules.

Before anything can be finalized, we need to start asking ourselves a bunch of questions. Here’s a small sample:

• How is assignment going to look? 
• How will variable types be declared, if at all? 
• What is a valid variable name? 
• How will I determine the value of a variable? 
• Should I have pointers? 
• What happens when I take the address of a variable and assign it to itself, creating a circular reference? 
• What happens when I try to access a variable that hasn’t been declared? 
• How should I handle variable shadowing? 
• Strong or weak typing? 
• Dynamic or static typing?

That’s only a quick few off the top of my head. The questions feel endless sometimes but you need to keep asking them!

I realize you might not know what questions to ask. I also understand you might not know what type systems there are, what variable shadowing is and how addressing works. I can’t possibly teach you everything there is to know in a blog series but I’ll do my best to get you on the right track.

I leave it as an exercise for you to do a search for any of these terms or concepts you don’t understand. It’s a deep, deep rabbit hole so be prepared!

So lets address the majority of these questions as they pertain to Calc 2.

Variable Names

Most languages restrict what kind of characters can be used for a variable name. Usually, the first character must be a letter so that the scanner doesn’t have to make a decision on whether a sequence of characters is an identifier, number or something else. The rest of the characters should be letters or numbers and probably not any symbols outside of an underscore.

It begs the question, “Why?”

Consider a number versus an identifier. Is 0xFF a number or an identifier? We know, by looking at it, it’s most likely to be intended to be an hexadecimal representation of a number but how does our scanner figure that out? How does it know 0xFF is a number but OxFF isn't?

Since a number can contain letters and identifiers can contain numbers it stands to reason that we need SOME way to differential between the two. The typical answer is to specify that a sequence of numbers and letters that start with a letter is an identifier and a similar sequence starting with a number may be a number representation of some kind.

Why no symbols? Well, let’s take a look at another example: a+b. Are we adding two variables, “a” and “b”, or is it an identifier “a+b”? As people, we can usually use context to discover the meaning of the expression but it’s much harder for a compiler. Not only that, finding the correct context might be very time consuming, even for a human.

We might, for example, think that if neither a nor b were declared as variables then it must be an identifier. Can we safely assume that or is it reasonable to believe the programmer made a mistake and meant to declare each variable but forgot to?

Since including symbols in an identifier name is outweighed by the complexity of parsing the result, it’s simpler to not include them.

Strong, Static Typing

Before talking about a variable declaration we need to take a quick detour into type systems.

If you don’t know much, or anything, about them then I encourage you to do some research. It may not be perfect but Wikipedia is a good start. You can find place to start here.

In Calc's case, I chose strong, static typing. Once a variable is a certain type then it is that type forever. If “a” is a string then it can only ever be assigned strings. It can’t be redeclared either within the same scope.

Static typing means that every variable must have it’s type set when it is declared. This can be done either through an explicit type name or through inference.

A type is said to be inferred when the type is taken from an assigned value and not via an explicit type name.

Variable Declaration

Should the type name come before or after the variable name? In C, the type comes before. In Go, it comes after. Why does it matter? Well, lets consider parsing the two following sets of code:

(int a)
(a int)

When it comes to parsing, neither really has a distinct advantage though I’d give a slight edge to option one for clarify of intent.

Let look at another set of examples. this time with the keyword ‘var’:

(var int a)
(var a int)

In this form, I actually like option two better because it looks nicer. Yes, that matters.

Look at the first option. After the var keyword the int looks out of place. Is it a keyword or a variable? Parsing-wise, it doesn't matter but this time it matters to the people who have to read it: us. To me, at least, option two is clearer. Declare a variable ‘a’ and make it of type ‘int’.

Assignment

In C based languages assignment looks like this: identifier = value. This seems sensible enough but there are other options, too:

(= a 5)
(set a 5)

As far as parsing goes, both are identical. The equal sign has the advantage of adding another operator and not introducing any new keywords. Unfortunately, it also might create ambiguity with equality, a common issue in many languages. Set does make our intentions more clear but at the cost of another keyword to parse.

Quite frankly, the cost is minimal but it’s not unreasonable to want to keep either the symbols in your language or the keywords to an absolute minimum. Languages like Scheme and Go do a good job. On the other end of the spectrum is C++, which has gotten out of hand.

I found this thread amusing. 357 keywords? That’s a level of insanity I’d never care to know.

Declaration with Assignment

It just keeps getting worse, doesn't it? First, assume that the language uses the var keyword to declare a variable and the equals sign for assignment. Here are a few different forms it could take:

(= (var a int) 5)
(var a int 5)
(var a 5) - using type inference
(var a 5 int)
(var a int = 5)
(var (= a 5))

I'm sure you could come up with more choices. So, which is the best?

That’s a tough question to answer. In my case, I decided to go with the last option and that has to do with declaring multiple variables and doing multiple assignment. Keep reading for an explanation.

Multi-Assignment

Calc 2 isn't going to have multi-assignment but it’s something to think about and you might want to add it to your own language. How might that look in Calc?

(=  a b, 1 2)
(= (a b) (1 2))
(= ( a 1) (b 2))

Just by looking at this you can see the added complexity. All three options are quite hideous and certainly gives me pause about how to add it properly.

You need to think about how a feature like this is going to fit with the rest of the language. Go’s handling of multiple variables fits like a glove in most cases. Swapping two variables is as easy as:

a, b = b, a

Looks, and feels, good. Consequently, multi-assignment from a function is equally as elegant:

a, b, c = returnsThreeResults()

How good is that? Damn fine. You can also chose to disregard certain variables from function calls with a simple underscore.

It’s clear that the Go developers thought carefully about how handle multiple assignment properly and I think they did a darned good job.

Looking to Go, I decided to use something similar.

(= a b, 1 2); assign1 to a, 2 to b
(= a b, b a); swap the values of a and b

So, when declaring multiple variables, or declaring with assignment:

(var a b int)
(var (= a b, 1 2))
(var (= a b, (returnTwoValues)))

Pointers

Calc 2 isn't going to have pointers but there’s a good chance that future versions will. I think I would make an effort to hide much of the complexity of pointers away from the user but they have their uses.

Pointers and dynamic memory allocation go hand in hand even though they’re mutually exclusive. Pointers can add a lot of complexity and the garbage collector that future versions of Calc are going to use will need to deal with that complexity.

You need to keep this in mind.

Look no further than C to see how bad pointer abuse can become. In Go, the developers decided that pointers were useful enough to include in the language but took efforts to prevent abuse. Case in point, Go doesn't have pointer arithmetic nor does Go allow casting of pointers to incompatible pointer types.

Undeclared Variables

Scoping and the symbol table allow us to detect when a variable is undeclared. Undeclared variables will result in an error in Calc 2.

You’re free to handle this however you want too. Perhaps you would prefer to create a new variable each time an undeclared variable is discovered. Bare in mind, however, that this means that if a programmer makes a typo a new variable will be created instead of warning them through a helpful error that the variable doesn't exist.

Something to think about.

Resolution

I hope I’ve demonstrated how something seemingly simple quickly becomes complex. These choices have far reaching consequences. We have to introduce new operators and keywords. We have to introduce new complexity for both ourselves and our users.

This was a fairly long post and I only covered something as simple as variable declarations!

Later on we’ll have to think about some special cases. For example, if a declaration is a valid expression then should it be allowed in variable assignment? Can you do something like (= a (var b int))? If not, how do we stop that?

I want to impress upon you the weight you bare. Seemingly simple decisions, like using LISP-like expressions, have huge impact on later decisions. Can I, for example, relegate these expressions to mathematical expressions only and use a C-like syntax for the rest of the language? Do I have to conform to encapsulating everything in parentheses?

The questions, and doubts, never end! I’ll just let you mull that over for a bit.

* Update - Fixed some typos *

Compiler 2 Part 3: Language Infrastructure

Previously, I talked about the new language features to be implemented in Calc 2. Now, I’d like to talk about some of the thought process behind these features and the new infrastructure that will be needed to implement them.

Functions

Procedures introduce some fun new concepts.

Scope is a word we use to talk about visibility of symbols. A symbol may represent a function or variable. Scoping determines when a variable is unique to a function or whether it can be accessed lexically.

Lexical scoping is a term used to describe a scoping method where variables are accessible within child scopes. Most languages I've used have lexical scoping. It means that when a variable has been declared in a function, it is accessible anywhere within that function, including nested functions or if statements.

As the parser reads from top to bottom, it will place any function declarations within the top-most scope, usually called the global scope. When a function is called, the global scope can be checked to see if a corresponding symbol exists and then the function can be accessed.

Of course, then there will need to be an entry point. In most compiled languages, this is called the main function or object.

Variables and Assignment

Most everything needed for variable assignment will be handled by scoping, too.

A variable, in many languages, is merely a symbol which represents a value in memory. It has a type, a name and a value. When assigning a value to a variable we need to ensure their types match and that it is mutable.

Mutable, from the word mutate, is the ability to change. By contrast, an immutable object is one that cannot change.

To assign a value to a variable we search for it in the current scope. If there is a parent scope, we move up a level and search for it there, recursively repeating the process until there are either no more scopes to search or we find the correct symbol.

Looping

Recursion is fun. For most of us, our first experience with looping comes from the venerable ‘for’ and ‘while’ statements. Calc will eventually have such constructs but in Calc 2 all we have is recursion.

In the most simple terms, a recursive function is one which calls itself.

Branching

The if statement is your typical, basic branching mechanism. A branch is like a fork in the road. Depending on a specific criteria, you chose to go down either one path or the other and they are mutually exclusive.

A branch has it’s own scope. You may declare a variable inside an if statement and it will be unique to that branch and will not be accessible outside of the branch. It uses normal scoping rules.

Types

Even though Calc 2 will still consist of a single type, the infamous integer, I will be introducing static typing and type-checking.

Static typing is a type system where a type is either explicitly or implicitly set when a variable is declared at compile time. What does this mean?

It means that the type of a variable is determined before a program is ever run and can be checked for type-correctness (types match or are compatible) when the program is compiled.

By contrast, a dynamic type system checks the type of a variable at runtime (while the program is running).

As previously stated, Calc 2 still only has one type. The basic “int” type is 32 bits. It is also signed, meaning that one bit is reserved to determine whether the number is positive or negative. Be aware of these limitations if you try to calculate a number that is too large to be held in this data type.

Negative Numbers

From a human standpoint a negative number is pretty easy. It’s a dash before a number.

That’s the key. It’s dash before a number. The number itself is not negative. It’s a positive number with a dash prepended to it.

The scanner is only aware that a number is a series of uninterrupted digits; so, lexically, a negative number is a bit tougher. The dash is scanned first as a separate lexical element from the number. The parser receives both of them separately.

Enter what we call a unary expression. This type of expression has only a single operand. This is in contrast to a binary expression, which has two operands. During parsing we’ll need to remember that the dash may indicate subtraction or negation.

Multiple Source Files

Multiple sources bundled up into a single object brings some unique difficulties but is, overall, simpler than one might think.

The only real obstacle to overcome is resolving symbols which exist in other files. A function may be called that exists somewhere else or not at all. Naming collisions could also happen.

Next Up…

Language design decisions!