The Voodoo Programming Language
2010-04-14
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:
"Hello world\n" |
A string with a newline in it |
"\\\"" |
A string consisting of a backslash followed by a double quote |
call foo \ |
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.
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) |
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
functionand the correspondingend function, and not inside anif… end ifblock. The scope of a variable introduced byletincludes every statement after theletaction and before theend functionthat 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-wordis 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
addis 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
divis 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-wordis 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 ofmod <x> <y>is undefined when the behavior ofdiv <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
subis 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:
| 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 ...
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.