The Voodoo Programming Language

Introduction

Voodoo is a programming language designed to be a thin abstraction layer over CPUs' native instruction sets and operating systems' calling conventions. It provides functionality to read and write memory, perform arithmetic, define and call functions, and not much more. In particular, Voodoo has no concept of types, let alone type safety. Voodoo is as dangerous as it is powerful.

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.

Voodoo aims to provide a level of abstraction high enough to reduce the effort of generating code for numerous target platforms, while allowing any construct to be expressed efficiently.

Language Overview

A Voodoo program consists of a 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. Finally, a program is divided into a data section and a code section.

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:

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.

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:

In the rest of this document, '<x>', '<y>' and '<z>' will be used to indicate arbitrary values.

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).

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.

let <symbol> <expr>

Introduces a local variable <symbol>, and initializes it to the result of evaluating <expr>. This action is only allowed on function level; that is, between function and the corresponding end function, and not inside an if… end if block. The scope of a variable introduced by let includes every statement after the let action and before the end function that ends the function in which the variable is introduced.

return <expr>

Evaluates <expr> and returns the result from the current function.

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>.

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 the exact result of <x>/<y> is not an integer, the result is converted to an integer in an implementation-defined way. If <y> = 0 or if the result cannot be represented in a single word, the behavior of div 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>

Returns the integer n such that n = <x> - (<y> * z), where z is the result of div <x> <y>. The behavior of mod <x> <y> is undefined when the behavior of div <x> <y> 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>.

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.

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:

Example usage of the section directive:

section data
# define data here ...

section functions
# define functions here ...

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

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, 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.