In this post we are going to see how to generate bytecode for our language. So far we have seen how to build a language to express what we want, how to validate that language, and how to build an editor for that language, but yet we cannot actually run the code. Time to fix that. By compiling for the JVM, our code will be able to run on all sorts of platforms. That sounds pretty great to me!

Series on Building Your Own Language

Previous posts:

1. Building a lexer
2. Building a parser
3. Creating an editor with syntax highlighting
4. Build an editor with autocompletion
5. Mapping the parse tree to the abstract syntax tree
6. Model to model transformations
7. Validation

Code is available on GitHub under the tag 08_bytecode.

Adding a Print Statement

Before jumping into the bytecode generation let’s just add a print statement to our language. It is fairly easy: we just need to change a few lines in the lexer and parser definitions and we are good to go.

// Changes to lexer
PRINT              : 'print';

// Changes to parser
statement : varDeclaration # varDeclarationStatement
          | assignment     # assignmentStatement
          | print          # printStatement ;

print : PRINT LPAREN expression RPAREN ;

The General Structure of Our Compiler

Let’s start from the entry point for our compiler. We will either take the code from the standard input or from a file (to be specified as the first parameter). Once we get the code, we try to build an AST and check for lexical and syntactical errors. If there are none we validate the AST and check for semantic errors. If still we have no errors we go on with the bytecode generation.

fun main(args: Array<String>) {
    val code : InputStream? = when (args.size) {
        0 -> System.`in`
        1 -> FileInputStream(File(args[0]))
        else -> {
            System.err.println("Pass 0 arguments or 1")
            System.exit(1)
            null
        }
    }
    val parsingResult = SandyParserFacade.parse(code!!)
    if (!parsingResult.isCorrect()) {
        println("ERRORS:")
        parsingResult.errors.forEach { println(" * L${it.position.line}: ${it.message}") }
        return
    }
    val root = parsingResult.root!!
    println(root)
    val errors = root.validate()
    if (errors.isNotEmpty()) {
        println("ERRORS:")
        errors.forEach { println(" * L${it.position.line}: ${it.message}") }
        return
    }
    val bytes = JvmCompiler().compile(root, "MyClass")
    val fos = FileOutputStream("MyClass.class")
    fos.write(bytes)
    fos.close()
}

Note that in this example we are always producing a class file named MyClass. Probably later we would like to find a way to specify a name for the class file, but for now this is good enough.

Using ASM to Generate Bytecode

Now, let’s dive into the funny part. The compile method of JvmCompiler is where we produce the bytes that later we will save into a class file. How do we produce those bytes? With some help from ASM, which is a library to produce Bytecode. Now, we could generate the bytes array ourselves, but the point is that it would involve some boring tasks like generating the classpool structures. ASM does that for us. We still need to have some understanding of how the JVM is structured but we can survive without being experts on the nitty-gritty details.

class JvmCompiler {

    fun compile(root: SandyFile, name: String) : ByteArray {
        // this is how we tell ASM that we want to start writing a new class. We ask it to calculate some values for us
        val cw = ClassWriter(ClassWriter.COMPUTE_FRAMES or ClassWriter.COMPUTE_MAXS)
        // here we specify that the class is in the format introduced with Java 8 (so it would require a JRE >= 8 to run)
        // we also specify the name of the class, the fact it extends Object and it implements no interfaces
        cw.visit(V1_8, ACC_PUBLIC, name, null, "java/lang/Object", null)
        // our class will have just one method: the main method. We have to specify its signature
        // this string just says that it takes an array of Strings and return nothing (void)
        val mainMethodWriter = cw.visitMethod(ACC_PUBLIC or ACC_STATIC, "main", "([Ljava/lang/String;)V", null, null)
        mainMethodWriter.visitCode()
        // labels are used by ASM to mark points in the code
        val methodStart = Label()
        val methodEnd = Label()
        // with this call we indicate to what point in the method the label methodStart corresponds
        mainMethodWriter.visitLabel(methodStart)

        // Variable declarations:
        // we find all variable declarations in our code and we assign to them an index value
        // our vars map will tell us which variable name corresponds to which index
        var nextVarIndex = 0
        val vars = HashMap<String, Var>()
        root.specificProcess(VarDeclaration::class.java) {
            val index = nextVarIndex++
            vars[it.varName] = Var(it.type(vars), index)
            mainMethodWriter.visitLocalVariable(it.varName, it.type(vars).jvmDescription, null, methodStart, methodEnd, index)
        }

        // time to generate bytecode for all the statements
        root.statements.forEach { s ->
            when (s) {
                is VarDeclaration -> {
                    // we calculate the type of the variable (more details later)
                    val type = vars[s.varName]!!.type
                    // the JVM is a stack based machine: it operated with values we have put on the stack
                    // so as first thing when we meet a variable declaration we put its value on the stack
                    s.value.pushAs(mainMethodWriter, vars, type)
                    // now, depending on the type of the variable we use different operations to store the value
                    // we put on the stack into the variable. Note that we refer to the variable using its index, not its name
                    when (type) {
                        IntType -> mainMethodWriter.visitVarInsn(ISTORE, vars[s.varName]!!.index)
                        DecimalType -> mainMethodWriter.visitVarInsn(DSTORE, vars[s.varName]!!.index)
                        else -> throw UnsupportedOperationException(type.javaClass.canonicalName)
                    }
                }
                is Print -> {
                    // this means that we access the field "out" of "java.lang.System" which is of type "java.io.PrintStream"
                    mainMethodWriter.visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;")
                    // we push the value we want to print on the stack
                    s.value.push(mainMethodWriter, vars)
                    // we call the method println of System.out to print the value. It will take its parameter from the stack
                    // note that we have to tell the JVM which variant of println to call. To do that we describe the signature of the method,
                    // depending on the type of the value we want to print. If we want to print an int we will produce the signature "(I)V",
                    // we will produce "(D)V" for a double
                    mainMethodWriter.visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println", "(${s.value.type(vars).jvmDescription})V", false)
                }
                is Assignment -> {
                    val type = vars[s.varName]!!.type
                    // This code is the same we have seen for variable declarations
                    s.value.pushAs(mainMethodWriter, vars, type)
                    when (type) {
                        IntType -> mainMethodWriter.visitVarInsn(ISTORE, vars[s.varName]!!.index)
                        DecimalType -> mainMethodWriter.visitVarInsn(DSTORE, vars[s.varName]!!.index)
                        else -> throw UnsupportedOperationException(type.javaClass.canonicalName)
                    }
                }
                else -> throw UnsupportedOperationException(s.javaClass.canonicalName)
            }
        }

        // We just says that here is the end of the method
        mainMethodWriter.visitLabel(methodEnd)
        // And we had the return instruction
        mainMethodWriter.visitInsn(RETURN)
        mainMethodWriter.visitEnd()
        mainMethodWriter.visitMaxs(-1, -1)
        cw.visitEnd()
        return cw.toByteArray()
    }

}

About Types

We have seen that our code uses types. This is needed because depending on the type we need to use different instructions. For example, to put a value in an integer variable we use ISTORE, while to put a value in a double variable we use DSTORE. When we call System.out.println on an integer we need to specify the signature (I)V, while when we call it to print a double we specify (D)V.

To be able to do so we need to know the type of each expression. In our super simple language we use just int and double for now. In a real language we may want to use more types, but this will be enough to show you the principles.

interface SandyType {
    // given a type we want to get the corresponding string used in the JVM
    // for example: int -> I, double -> D, Object -> Ljava/lang/Object; String -> [Ljava.lang.String;
    val jvmDescription: String
}

object IntType : SandyType {
    override val jvmDescription: String
        get() = "I"
}

object DecimalType : SandyType {
    override val jvmDescription: String
        get() = "D"
}

fun Expression.type(vars: Map<String, Var>) : SandyType {
    return when (this) {
        // an int literal has type int. Easy :)
        is IntLit -> IntType
        is DecLit -> DecimalType
        // the result of a binary expression depends on the type of the operands
        is BinaryExpression -> {
            val leftType = left.type(vars)
            val rightType = right.type(vars)
            if (leftType != IntType && leftType != DecimalType) {
                throw UnsupportedOperationException()
            }
            if (rightType != IntType && rightType != DecimalType) {
                throw UnsupportedOperationException()
            }
            // an operation on two integers produces integers
            if (leftType == IntType && rightType == IntType) {
                return IntType
            // if at least a double is involved the result is a double
            } else {
                return DecimalType
            }
        }
        // when we refer to a variable the type is the type of the variable
        is VarReference -> vars[this.varName]!!.type
        // when we cast to a value, the resulting value is that type :)
        is TypeConversion -> this.targetType.toSandyType()
        else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
    }
}

Expressions

As we have seen, the JVM is a stack-based machine. So every time we want to use a value we push it on the stack and then do some operations. Let’s see how we can push values into the stack

// Convert, if needed
fun Expression.pushAs(methodWriter: MethodVisitor, vars: Map<String, Var>, desiredType: SandyType) {
    push(methodWriter, vars)
    val myType = type(vars)
    if (myType != desiredType) {
        if (myType == IntType && desiredType == DecimalType) {
            methodWriter.visitInsn(I2D)
        } else if (myType == DecimalType && desiredType == IntType) {
            methodWriter.visitInsn(D2I)
        } else {
            throw UnsupportedOperationException("Conversion from $myType to $desiredType")
        }
    }
}

fun Expression.push(methodWriter: MethodVisitor, vars: Map<String, Var>) {
    when (this) {
        // We have specific operations to push integers and double values
        is IntLit -> methodWriter.visitLdcInsn(Integer.parseInt(this.value))
        is DecLit -> methodWriter.visitLdcInsn(java.lang.Double.parseDouble(this.value))
        // to push a sum we first push the two operands and then invoke an operation which
        // depend on the type of the operands (do we sum integers or doubles?)
        is SumExpression -> {
            left.pushAs(methodWriter, vars, this.type(vars))
            right.pushAs(methodWriter, vars, this.type(vars))
            when (this.type(vars)) {
                IntType -> methodWriter.visitInsn(IADD)
                DecimalType -> methodWriter.visitInsn(DADD)
                else -> throw UnsupportedOperationException("Summing ${this.type(vars)}")
            }
        }
        is SubtractionExpression -> {
            left.pushAs(methodWriter, vars, this.type(vars))
            right.pushAs(methodWriter, vars, this.type(vars))
            when (this.type(vars)) {
                IntType -> methodWriter.visitInsn(ISUB)
                DecimalType -> methodWriter.visitInsn(DSUB)
                else -> throw UnsupportedOperationException("Summing ${this.type(vars)}")
            }
        }
        is DivisionExpression -> {
            left.pushAs(methodWriter, vars, this.type(vars))
            right.pushAs(methodWriter, vars, this.type(vars))
            when (this.type(vars)) {
                IntType -> methodWriter.visitInsn(IDIV)
                DecimalType -> methodWriter.visitInsn(DDIV)
                else -> throw UnsupportedOperationException("Summing ${this.type(vars)}")
            }
        }
        is MultiplicationExpression -> {
            left.pushAs(methodWriter, vars, this.type(vars))
            right.pushAs(methodWriter, vars, this.type(vars))
            when (this.type(vars)) {
                IntType -> methodWriter.visitInsn(IMUL)
                DecimalType -> methodWriter.visitInsn(DMUL)
                else -> throw UnsupportedOperationException("Summing ${this.type(vars)}")
            }
        }
        // to push a variable we just load the value from the symbol table
        is VarReference -> {
            val type = vars[this.varName]!!.type
            when (type) {
                IntType -> methodWriter.visitVarInsn(ILOAD, vars[this.varName]!!.index)
                DecimalType -> methodWriter.visitVarInsn(DLOAD, vars[this.varName]!!.index)
                else -> throw UnsupportedOperationException(type.javaClass.canonicalName)
            }
        }
        // the pushAs operation take care of conversions, as needed
        is TypeConversion -> {
            this.value.pushAs(methodWriter, vars, this.targetType.toSandyType())
        }
        else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
    }
}

Gradle

We can also create a Gradle task to compile source files

task compileSandyFile(type:JavaExec) {
    main = "me.tomassetti.sandy.compiling.JvmKt"
    args = "$sourceFile"
    classpath = sourceSets.main.runtimeClasspath
}

Conclusions

We did not go into any detail and we sort of rush through the code. My goal here is just to give you an overview of the general strategy to use to generate bytecode. Of course if you want to build a serious language you will need to do some studying and understand the internals of the JVM, there is no escape from that. I just hope that this brief introduction was enough to show you that this is not as scary or complicated as most people think.