The Voodoo Programming Language

Robbert Haarman

2012-01-14

Introduction

Voodoo is a programming language designed to be a thin abstraction layer over CPUs' native instruction sets and operating systems' calling conventions. Operations provided by Voodoo closely correspond to those of common CPU instruction sets, allowing programs to be expressed with a minimum of overhead. At the same time, Voodoo is not tied to a specific instruction set, and support for new CPUs and operating systems can easily be added.

Rationale

When implementing programming languages, one of the hurdles to overcome is code generation. Ultimately, the program must be translated from the source language into machine code for the machine that the program is to run on. Generally, the code to be generated differs from machine architecture to machine architecture and from operating system to operating system. Implementing efficient code generators for all combinations of hardware and operating system requires a lot of work and expertise.

To reduce the effort required for code generation, many programming language implementations compile to higher level languages, instead of to machine code. An existing implementation of the higher level language can then be used to execute the program. Unfortunately, many higher level languages provide models of computation that may hinder efficient implementation of the source language. Also, implementations of higher level languages are not always easy to port to new platforms.

Voodoo aims to reduce the effort required to generate reasonably efficient code for multiple target platforms. It provides low-level operations similar to those found in many CPU instruction sets, allowing for efficiency close to machine code. At the same time, it supports a variety of instruction sets and operating systems, and support for new combinations can easily be added. Using Voodoo, compiler writers can get reasonable efficiency on a variety of target platforms at the cost of writing a single code generator.

Language Overview

A Voodoo program consists of data, function definitions, and code. All of these are introduced by magic words such as function, call, and string. Any part of the program may be preceded by a label, and labels can be referred to from the code.

Hello World in Voodoo

To quickly get a feeling for a programming language, it is often instructive to look at a simple yet complete program. The following is an implementation of the traditional Hello World program in Voodoo:


#### Hello world in Voodoo

section data
greeting:
string "Hello, world!\x00"

section functions
import puts
export main

main:
function argc argv
    call puts greeting
    return 0
end function

When compiled and linked with a library that provides an appropriate implementation of the puts function, this program will print Hello, world!.

What follows is a more formal description of the Voodoo programming language.

Tokens

Comments

Comments start with a hash mark (#) and run until the end of the line. The following is an example comment:


# This is an example comment

Integers

Integers consist of an optional plus or minus sign, followed by one or more digits. Examples of valid integers:


0
+12
-1

Strings

Strings consist of zero or more characters enclosed in double quotes. Examples of valid strings:


""
"Hello, world!"

Symbols

Symbols consist of letters, digits, underscores, and hyphens, although only a letter or an underscore is allowed as the first character of a symbol. Examples of valid symbols:


foo
some-symbol

Escape Sequences

To facilitate entering special characters and to inhibit the special meaning certain characters normally have, an escape mechanism is provided. Escape sequences start with a backslash, and have the following meanings:

`\\`	An actual backslash character
`\"`	A double quote character
`\n`	A newline
`\r`	A carriage return character
`\t`	A tab character
`\xXX`	The character with hexadecimal value `XX`
`\<space>`	A space character
`\<newline>`	Line continuation character. The newline and any leading whitespace on the next line is ignored.

Examples of the usage of the escape characters:

`"Hello world\n"`	A string with a newline in it
`"\\\""`	A string consisting of a backslash followed by a double quote
`call foo \ bar`	Same as: `call foo bar`

Labels

Places in a program can be marked with labels, so that the place can be referred to from the code by mentioning the label. A label consists of a symbol followed by a colon. When referring to a label, only the symbol is used, without the colon.

For example:


foo:
word 12

declares a word with the value 12, and a label 'foo' that refers to the place where this value is stored. For example, if the value happens to be loaded at the address 71234, writing 'foo' in the program will have the same effect as writing 71234 in the same place.

Values

Values are the smallest unit of data in a Voodoo program. Examples of values are:

`12`	The integer 12
`x`	The value of x (may be a label or a local variable)

At-Expressions

The character @ can be used to denote the value at some address. An address prefixed with @ denotes the word stored at that address, rather than the address itself. The address may be an integer, a local variable, or a label. For example:

`@12`	The word stored at address 12
`@x`	The word stored at address x

Syntactically, at-expressions are values. Therefore, in any place where a value can be used, an at-expression can also be used.

Data Definitions

Data can be inserted into a Voodoo program by means of the magic words byte, word, and string, followed by the value of the byte, word, or string to be inserted. For example:


# A byte with value 42
byte 42

# A word with value -1
word -1

# The string "hello"
string "hello"

Actions

Voodoo code consists of actions. Actions consist of a magic word, usually followed by a number of values. This section lists all actions supported by Voodoo. In the list below, '<x>', '<y>', and '<z>' denote values, '<symbol>' denotes a symbol, and '<expr>' denotes an expression. (expressions are discussed further on). Ellipsis (…) is used to denote that more items may follow, and square brackets ([ and ]) are used to denote that an item is optional.

call <x> <y> <z> …

Calls the function <x> with the arguments <y> <z> …. There may be zero or more arguments.

goto <x>

Continues the program at location <x>, rather than at the next action after the goto.

Any value can be used as the location to go to. However, the consequences of using goto to cross function or block boundaries (e.g. performing a goto to a label inside a different function) are undefined.

let <symbol> <expr>

Introduces a local variable <symbol>, and initializes it to the result of evaluating <expr>.

This action is only allowed inside functions or blocks, that is, between function and the corresponding end function, or between block and the corresponding end block.

The scope of a variable introduced by let includes every statement after the let action and before the end function or end block that ends the function or block in which the variable is introduced.

return [<expr>]

Returns from the current function. If <expr> is specified, it is evaluated and the function returns the result of the evaluation. Otherwise, the return value is unspecified.

set <symbol> <expr>

Evaluates <expr> and assigns the result to <symbol>. <symbol> may not be a label, because labels cannot be assigned to.

set-byte <base> <offset> <x>

Sets the byte at <base> + <offset> to <x>. <offset> is given as a number of bytes.

set-word <base> <offset> <x>

Sets the word at <base> + WORDSIZE * <offset> to <x>.

The address computed by <base> + WORDSIZE * <offset> is expected to be a multiple of the word size. The behavior of set-word is undefined if this condition is not satisfied.

tail-call <x> <y> <z> ...

Performs a tail call to the function <x> with arguments <y> <z> …. This has an effect similar to 'return call <x> <y> <z> ...', but re-uses the call frame of the current function. This means that if <x> takes fewer or at most as many arguments as the current function, the tail call requires no extra space.

Expressions

Certain actions have the ability to evaluate expressions. Expressions can be simple values, but expressions can also perform computations on values. The following are valid expressions:

add <x> <y>

The result of adding <y> to <x>.

If the result of the addition cannot be represented in a single word, the result of add is undefined.

and <x> <y>

The bitwise and of <x> and <y>.

asr <x> <y>

Performs an arithmetic right shift. The bits in <x> are shifted <y> positions to the right. The sign of <x> is preserved, so that the result has the same sign as <x>. The result is undefined if <y> is negative.

bsr <x> <y>

Performs a bitwise right shift. The bits in <x> are shifted <y> positions to the right. <y> zero-valued bits are shifted in from the left. The result does not necessarily have the same sign as <x>. The result is undefined if <y> is negative.

call <x> <y> <z> ...

Similar to the action call, this calls the function <x> with the arguments <y> <z> ... (there may be zero or more arguments). The result of this expression is the value returned from the function.

div <x> <y>

The (integer) result of dividing <x> by <y>.

If <x> ≥ 0 and <y> > 0, the result is the largest integer equal to or less than the algebraic quotient of <x> and <y>.

If either <x> or <y> is negative, the result is implementation-defined.

If <y> is zero, or if the quotient cannot be represented in a single machine word, the result is undefined.

get-byte <base> <offset>

The value of the byte at address <base> + <offset>.

get-word <base> <offset>

The value of the word at address <base> + (WORDSIZE * <offset>).

The address computed as <base> + (WORDSIZE * <offset>) is expected to be a multiple of the word size. If this condition is not met, the behavior of get-word is undefined.

mod <x> <y>

For <x> ≥ 0 and <y> > 0, returns <x> modulo <y>.

If either <x> or <y> is negative, the result is implementation-defined.

If <y> is zero, the result is undefined.

mul <x> <y>

The result of multiplying <x> by <y>.

If the algebraic result of <x> * <y> cannot be represented in a single word, the result of mul <x> <y> contains only the low-order bits of the full result.

not <x>

The ones' complement of <x>; i.e. all the bits in <x> inverted.

or <x> <y>

The bitwise or of <x> and <y>.

rol <x> <y>

Rotates the bits in <x> to the left by <y> positions. Bits that are rotated off the left are inserted on the right. The result is undefined if <y> is negative.

ror <x> <y>

Rotates the bits in <x> to the right by <y> positions. Bits that are rotated off the right are inserted on the left. The result is undefined if <y> is negative.

shl <x> <y>

Performs a left shift. The bits in <x> are shifted <y> positions to the left. The result is undefined if <y> is negative.

shr <x> <y>

Performs a right shift. The bits in <x> are shifted <y> positions to the right. It is implementation-defined whether this operation preserves the sign of <x> (for operations with specific sign-preservation properties, use asr or bsr). The result is undefined if <y> is negative.

sub <x> <y>

The result of subtracting <y> from <x>.

If the result of the subtraction cannot be represented in a single word, the result of sub is undefined.

xor <x> <y>

The bitwise exclusive or of <x> and <y>.

Conditionals

Conditionals in Voodoo take the following form:

if<test>
    ... some code here ...
else if<test>
    ... other code here ...
... more "else if" parts ...
else
    ... some code ...
end if

There can be any number of else if parts, and the final else clause is optional. The tests that are provided are the following:

ifeq <x> <y>: Tests if <x> is equal to <y>.
ifge <x> <y>: Tests if <x> is greater than or equal to <y>.
ifgt <x> <y>: Tests if <x> is strictly greater than <y>.
ifle <x> <y>: Tests if <x> is less than or equal to <y>.
iflt <x> <y>: Tests if <x> is strictly less than <y>.
ifne <x> <y>: Tests if <x> is different from <y>.

Function Definitions

A function definition looks like:


function x y z
    <code>
end function

Here, the function being defined takes 3 arguments, which can be referred to as x, y, and z from the code inside the function body. A function may have zero or more arguments and is practically always preceded by a label, so that the function can be referenced from code.

A function should only be entered using call or tail-call, and should only be left through a return action. Furthermore, a function should always be called with the same number of arguments it was defined with. Failing to meet any of these requirements results in undefined behavior.

Blocks

Blocks can be used to define a scope in which local variables (introduced with let) can be referred to. A block looks like:


block
    <code>
end block

Inside a block, variables may be introduced using let. Such a variable is in scope (can be referred to) from the first statement after the let until the end block that terminates the block.

Blocks can be placed anywhere an action can be placed: at top-level, inside functions, inside blocks, and inside conditionals.

Sections

A Voodoo program is divided in a number of sections. In source code, these are introduced by a directive of the form section <identifier>, where <identifier> is an identifier for the section.

The following section identifiers are valid:

Identifier	Meaning
`code`	This section contains executable code
`data`	This section contains data
`functions`	This section contains function definitions

Example usage of the section directive:


section data
# define data here ...

section functions
# define functions here ...

Import and Export

To allow Voodoo programs to refer to definitions in other files, and to allow other files to refer to definitions in Voodoo programs, the magic words import and export are used.

Using import, definitions from elsewhere are made available to a Voodoo program:


section data
import stderr

section functions
import fputs

# We can now refer to stderr and fputs

Data and functions defined in a Voodoo program can be made available to other programs using export:


section data
export answer

answer:
word 42

section functions
export foo

foo:
function
  # some code here
end function

Alignment

Many architectures require that data and/or code obey certain alignment restrictions. For example, an architecture may require that a word of data be at an address that is a multiple of the word size. Voodoo provides the align directive, which specifies the alignment for the next program element.

Without any arguments, align inserts filler bytes into the current section, so that the next element added to the section will respect the default alignment for the section. The default alignment for each section is implementation-dependent, but must ensure that the alignment restrictions of the target platform are obeyed.

When written as align <n>, where <n> is an integer, the directive will insert filler bytes as necessary to align the next element to be added to the section on a multiple of <n> bytes.

The filler bytes inserted by align are unspecified. In particular, they are not guaranteed to be valid code.

Example uses of the align directive:


section data

x:
byte 1

# Ensure that y is aligned according to
# the target platform's alignment restrictions
align
y:
word 42



section functions

# Ensure that foo is aligned according to
# the target platform's alignment restrictions
align
foo:
function n
    # some code here
end function

Features

To aid authors and programs in generating code that is compatible with a particular Voodoo implementation, implementations are encouraged to provide means to query their features. This document specifies a number of features as key-value pairs, where the key is the feature name, and the value is a string that provides additional information about the feature (as described in the specification of the feature).

Implementations may also advertise features not specified in this document. To prevent conflicts with future versions of Voodoo, these features should have names starting in x-. Implementations are encouraged to use this mechanism to advertise support for extensions to the language specified by this document.

Name	Description
bits-per-word	The value indicates the number of bits per word for the given implementation. E.g. 32.
byte-order	Order of bytes in a word. The following values are defined: big-endian Bytes are ordered from most significant to least significant little-endian Bytes are ordered from least significant to most significant
bytes-per-word	The number of bytes required to store a word. E.g. 4
voodoo	Version of the Voodoo language supported by the implementation. The version described in this document is 1.0.

Implementation

The Voodoo programming language is implemented by the Voodoo compiler. This implementation compiles Voodoo code to assembly code or object files for x86, AMD64, ARM, or MIPS. The implementation is written in Ruby. It is available under the terms of the LGPLv2 license and can be downloaded from the Voodoo compiler page.

Related Work

This section provides links to some projects that are related to the Voodoo programming language.

C--

C-- is a language with very similar aims to Voodoo's. Like Voodoo, C-- aims to be a target language for programming language implementations, providing a thin abstraction layer over the target platform without getting in the way of efficient implementation of high level constructs. Compared to Voodoo, C-- seems more complete. However, development on C-- implementations seems to have stagnated.

LLVM

LLVM, the Low-Level Virtual Machine, provides a compiler framework that has similar aims to Voodoo. Compared to Voodoo, LLVM provides many more features. This comes at the cost of more complexity and a much heavier implementation.

The Common Language Infrastructure

The Common Language Infrastructure (CLI), designed by Microsoft and published as ECMA-335, is a specification that allows programs written in a variety of high-level languages to compile to a common byte code format and share data and code with one another. Compared to Voodoo, it is much more extensive, including such things as a type system and garbage collection. Where Voodoo is lightweight and aims to be language-agnostic, the CLI is heavier and more geared towards statically typed languages with class-instance object systems.

TurboVM

TurboVM is a virtual machine that exposes a RISC instruction set, designed to be simple and efficient to generate, parse, and execute. Like Voodoo, TurboVM is intended as back end for programming implementations. Also like Voodoo, it aims to be simple and lightweight. Voodoo could be compiled to TurboVM byte code, and, conversely, TurboVM byte code could be compiled to Voodoo, either as a possible intermediate step to native code generation.

Alchemist

The Alchemist code generation library is a library that can be used to generate machine code. A possible future direction for Voodoo implementations is to use Alchemist to generate (and possibly execute) machine code on the fly.