The BONES Manual

This is BONES, a compiler for R5RS Scheme that generates x86_64 assembly code. BONES is designed to be simple and easy to understand, both to reduce the effort to learn and extend the system and to keep the complexity of the compiler at a minimum.

BONES is a batch-compiler, it takes a Scheme source file and produces an assembler file to be subsequently translated into object code. It is also a whole-program compiler, which means it does not support separate compilation of multiple modules. The runtime system is by default added to your program before it is compiled, so there are no external libraries, with the exception of a few bits from the C library ("libc") (this is optional).

BONES is mostly R5RS-compliant, but intentionally cuts some corners to reduce code-size, increase performance and simplify the compiler and runtime system. Type-checks are generally omitted, for example. Very little error checking is done and arithmetic overflow of small integers ("fixnums") is not detected. Some R7RS procedures are available in addition to the primitives required for R5RS.

Since BONES produces assembly-code, build-times are quite short. The produced code is CPU- and OS-specific and currently supports x86_64 on Linux, *BSD, Mac or Windows. Porting the system to other architectures and operating systems should be (relatively) straightforward, as the platform-specific parts of the compiler are small and the runtime-system is just a single file of about two thousand lines of assembly code.

The compiler is self-compiling and uses just a few functions from the C-library. Alternatively, programs can be compiled on Linux without using a C library, by just invoking raw system calls, but support for this is currently incomplete (mostly related to number<->string conversion). Code compiled with BONES can be easily embedded into programs written in other languages as long as they allow calling C functions.

There are very little debugging facilities. The compiler expects correct code and no attempt is made to provide more than the most basic error messages. It is recommended to develop and test code first in an interactive Scheme implementation and use BONES only for generating executables when the code can be assumed to work.

The development files for BONES are hosted at bitbucket.org, where you will find example code (mostly tests). The compiler itself is developed with a currently unreleased Scheme system, but as BONES compiles itself, no additional implementation is needed to make changes and extend the system.

To run programs compiled with BONES (and to run the compiler itself), an x86_64 system is required, with support for SSE2 and SSE3 instructions. Currently the compiler runs under the Linux, *BSD, Mac OS X and Windows operating systems.

BONES has been successfully tested on the following systems:

The NASM assembler is required on all supported platforms. To link the assembled code you will typically need a C development environment.

On Linux GCC is the recommended compiler, but you will only need it for linking, and for providing the basic C runtime code (CRT). A subset of the functionality provided by this system can be compiled to native code that does not need C runtime support - in this case all you need is ld, the GNU linker.

On Windows, Microsoft Visual C and MINGW are supported.

On Mac OS, Xcode should be installed, with gcc or clang binaries in the PATH, or another C compiler that is able to link macho64 binaries.

BONES is written in Scheme and translates Scheme to x86_64 assembler for the syntax accepted by NASM, which will have to be installed on your system. To link the assembled code you will need a linker and C runtime support files, including the C library, so a C compiler should be installed as well.

To build the system, you need the pre-compiled assembly code for the bones executable, which you can obtain by downloading a distribution tarball at this location:

http://www.call-with-current-continuation.org/bones/bones.tar.gz

or

http://www.call-with-current-continuation.org/bones/bones.zip

After downloading, unpack the file using the tar(1) command and assemble and link the appropriate assembler file for the compiler:

• For Linux:

  tar xfz bones.tar.gz
  cd bones-<date>
  nasm -f elf64 bones-x86_64-linux.s -o bones.o
  gcc bones.o -o bones -lrt
  

• For Free/Net/OpenBSD:

  tar xfz bones.tar.gz
  cd bones-<date>
  nasm -f elf64 bones-x86_64-bsd.s -o bones.o
  gcc bones.o -o bones
  

  At least on OpenBSD, you may need to invoke gcc with the -static and -nopie options to generate a working executable. Alternatively pass -feature pic to bones when compiling the Scheme code.

• For Windows:

  Unzip the archive and enter the following commands in a command shell window that has access to the command-line MSVC development tools:

  cd bones-<date>
  nasm -f win64 bones-x86_64-windows.s -o bones.obj
  link bones.obj libcmt.lib /out:bones.exe
  

  If you are using MINGW, linking is done with the following command:

  gcc bones.obj -o bones.exe
  

• For Mac OS:

  tar xfz bones.tar.gz
  cd bones-<date>
  nasm -f macho64 bones-x86_64-mac.s -o bones.o
  gcc bones.o -o bones
  

  You may get a linker warning complaining that the object file produced by NASM does not have "PIE" enabled. I'm not completely sure why this happens and how this warning can be prevented. The linked executables run fine as far as I can tell (it may be caused by a bug in NASM or the Apple linker, but I'm not sure about it.) You can disable this warning by adding the option -Wl,-no_pie when linking an executable.

Now you have a compiler, which you can test by entering

./bones

which should give you some usage information.

The bones executable can be moved anywhere you desire, but assumes that some supporting files are in the directory where it is invoked. You can use the -L command-line option (described below) to set the directory where the supporting files are located. The default search path contains the following directories:

• The current directory (".")
• The value of BONES_LIBRARY_PATH, if set. Multiple directories can be given, when separated by ";" (semicolon) on Windows or ":" (colon) on other systems.
• "/usr/share/bones"
• "/usr/local/share/bones"

Additionally, when assembling generated code produced by BONES, you will have to pass -I<INSTALLDIR>/ to the NASM invocation, as the code contains %include directives that refer to the assembler-parts of the runtime system. Note that trailing slash - this is required for NASM.

If you find any bugs in BONES (you probably will), please send them to the author (see below under "Contact") so that the bug can be fixed in future releases. You should also first check the git(1) development repository at http://bitbucket.org/bunny351/bones/ - perhaps the bug has already been fixed. The master branch should always be in a usable state, just clone the repository and use the contained sources to build a new bones:

git clone https://bitbucket.org/bunny351/bones.git
cd bones
bones bones.scm -o mynewbones.s

Consult the NEWS file for obtaining information about the latest changes.

Values used in the system are of two kinds: 64-bit immediate exact numbers (fixnums) and 64-bit pointers to data. A fixnum is marked by having the lowest bit set to 1. Pointers are always aligned on an 8-byte boundary and so automatically have their lowest 3 bits set to 0. This allows to distinguish between immediate and non-immediate data by just testing the lowest bit. This is necessary to implement type-predicates and to allow the garbage collector (described below) to handle them specifically.

Fixnums represent an integer value shifted one bit to the left, with the lowest bit set.

Non-immediate data (blocks) are preceded by a 64-bit header, containing the size and the type of the block, in addition to one bit used for house-keeping during garbage collections. The size is encoded in the lowest 56 bits, the type in the upper 7 bits.

Non-immediate data is again classified into normal blocks, containing other values (fixnums or pointers to blocks) and byteblocks, where the actual data-area after the header contains raw bytes. Currently this are strings and floating-point numbers.

The last class of blocks are special blocks, which are like normal blocks, but with the first slot holding a native pointer value. This is used for procedures - the pointer in that case points to the actual machine code of the procedure (and is not traced during GC). The remaining slots hold free variables, in case the procedure is a closure, i.e. needs to retain references to variables defined in a scope lexically outside of the procedure.

BONES uses IEEE-754 floating-point numbers on all supported platforms.

Here is a rough overview of the different objects used in the system:

#t, #f and the undefined (void) value are unique and never allocated.

Strings use a single-byte encoding, Unicode is not supported. Characters-codes are not limited to 8-bit, though, but when assigned or extracted to/from strings, only the least significant 8 bits are used.

For information about the use of the slots in port and record objects, you should study the source code, in particular r5rs.scm.

Records are vector-like blocks where the two first slots contain a record tag (symbol) and a fixnum id, designating the exact type of the record. Id 1 is used for error-objects.

As argument types are not checked, primitives are only sensitive to the underlying representation, not the actual type. This can be used for interesting effects, for example:

(string->copy <FLOAT>)  ==>  <a string containing the raw bytes of the IEEE double>

(vector->list '(1 . 2)) ==>  (1 2)

(define-values (make pred? data) (make-disjoint-type 'foo))
(vector-copy (make 99))    ==>  #(foo 2 99)

Operations that expect a normal block will have an undefined effect when invoked on objects that are byte-blocks and vice versa. Usually the program will crash.

BONES uses a Cheney-style copying garbage collector. This sacrifices one half of the available heap space to gain faster allocation and collection and to make the time needed to collect garbage independent on the amount of available memory. Fixnums are ignored during GC, blocks are traversed in breadth-first manner to copy all live data in every collection into the second half of the heap-space. Once all live data has been copied, the halves of the heap-space are flipped and program execution continues. The time needed for a GC depends on the amount of live data. The fewer data is allocated, the lower is the impact of the GC on the total run-time of a program.

Pointers that do not point into the garbage collected heap are ignored by GC, so it is allowed to store pointers to user-allocated blocks (in fact to any kind of data) into Scheme data-structures.

Note that storing pointers to heap-allocated data in non-heap data is disallowed and optionally checked at runtime. Otherwise the garbage collector will not be able to detect that the stored value is still live, if no other pointer to that object exists. Since the GC moves data in the heap on every collection (because it is copied from the old heap-space to the new one), the old pointer will be invalid after the collection finishes. A check for this can be enabled by passing -DENABLE_WRITE_BARRIER to NASM, which may slightly decrease runtime performance.

The heap can not be resized dynamically and has a fixed size. Use the TOTAL_HEAP_SIZE macro to specify a heap-size different from the default size. 1% of the heap is used as a reserve zone - once the allocation-pointer enters this zone, a garbage collection will be triggered. This allows to defer the limit-check when small blocks of data are allocated.

There are basically four ways to invoke non-Scheme code from compiled programs:

1. Use system to run shell commands. This is the easiest and most portable method, unless you need to have access the BONES runtime- system or want to modify or inspect Scheme data.
2. Embed a compiled program inside other code that can interface to C. For more information on this see below. This is also quite straightforward and very flexible, without the need to use assembly code.
3. Use the $inline special form to mix assembly code instructions directly with Scheme code, where $inline is defined as

   ($inline STRING ARGUMENT ...)

   Executes the assembler instructions in STRING, given the results of evaluating the arguments in ARGUMENTS, specifically in the rax, r11 and r15 registers. At most three arguments may be passed. Multiple instructions inside STRING can be given, when separated by ; (semicolon). Note that changing other registers than the ones used for passing arguments may change local variables and thus should be avoided, unless you really know what you are doing. STRING is not evaluated.

4. Use the $primitive special form to refer to a primitive procedure written in assembly code:

   ($primitive STRING)

   Returns a procedure refering to the primitive procedure named by the label STRING. STRING is not evaluated.

   The procedure must be written in assembly code and takes its arguments in the argument registers described in the chapter describing the register usage. rbx holds the current procedure, rcx the current continuation (a procedure block), and rdx to r12 contain the first seven arguments passed to the current procedure. Additional arguments are passed in a static array and are not accessible from separately compiled code, so your primitive may not accept more than seven arguments.

   To return, invoke the continuation procedure with a single result in rcx, like this (NASM syntax, assuming the result is in rax):

   mov rbx, rcx            ; make continuation the current procedure
   mov rcx, rax            ; put result into the correct register
   mov rax, [rbx + 8]      ; get code-pointer to continuation
   jmp rax                 ; and jump to it
   

   During execution of your primitive you are free to modify all registers as you please, with the exception of rbp, r13 and r14, as long as you follow the steps given to invoke the continuation. rsp may be modified, but must be restored when the primitive returns.

   No implicit argument-count checks are done. Returning multiple values from user-defined primitives is not supported. The stack is not used for procedure call arguments or return-addresses.

Compiled programs can be linked to code written in other languages, provided they are able to interface to C. Normally an object file compiled with BONES exports the entry-point main (or _start when the C-libray is disabled). By compiling the Scheme program with the option -feature embedded, the entry-point is renamed to bones, having this signature:

BONES_X scheme(BONES_X argument);

where BONES_X is a generic type designating a Scheme value.

The function is not reentrant, and so can not be used by multiple threads, because it refers to static data buffers and variables. It is possible to combine multiple programs by using the -DPREFIX=<prefix> option when assembling each compiled program. In this case the entry-point will be named <prefix>_scheme. Every entry-point refers to a self-contained Scheme environment and thus can be run in a separate thread, if desired.

The file bones.h contains a number of macros and type-definitions (including the BONES_X type) that provides some basic operations to extract types and values from Scheme data objects. Refer to this file for more information.

On the first invocation of the entry-point, the argument is ignored. Once the Scheme procedure return-to-host is invoked, the entry-point function returns the argument given to that primitive. This value will be located in the Scheme heap (unless it is a fixnum) and should not be retained across later invocations of the entry-point, because subsequent garbage collections will move the object and thus invalidate the retained pointer.

The argument can be a fixnum, or a pointer to Scheme-data allocated in non-heap memory. In that case it will be ignored by the garbage collector, but may not be modified to hold pointer to heap-data (this will be detected and result in an error-message and termination of the process, when the program was assembled with the -DENABLE_WRITE_BARRIER argument.

If you want to copy the argument given to the entry-point into the Scheme heap, take a look at the file copy.scm in the BONES distribution. This file provides a procedure to create a heap-copy of an arbitrary complex Scheme object.

Note that return-to-host suspends the executing Scheme code and returns the argument given to the following invocation of the entry-point.

When embedding code in a shared library on Linux or *BSD, you should compile your Scheme code with the -feature pic option to make sure the generated code is position independent. On Windows and Mac, pic is enabled by default.

As already mentioned, there are practically no debugging facilities. It is possible to enable some checks for lowlevel data access and for exceeding argument-counts and -limits. To do so, use the -feature check option (or use provide for enabling this in your program specifications).

Currently, the check feature enables the following:

• Out-of-bounds slot-access of vector-like objects.
• Out-of-bounds access of byte-vectors objects.
• Checking whether a non-procedure was called.
• Checking the correct number of arguments in a procedure call.
• Checking the maximum number of arguments in apply.
• Checking attempts to modify immutable data (literals).

Failed checks invoke the exception handler, and thus can be caught. In certain fatal situations, for example, when the heap is full or corrupted, the error-processing machinery may not be able to exit with a meaningful message.

Access to undefined ("unbound") variables will produce linker errors, where the variable name will be mangled, by prefixing it with "___" (three underscores) and replacing non-alphanumeric characters with "_XX". "XX" in this case is the hexadecimal code of the character.

The heap has a fixed size and does not resize dynamically. You can change the default size of the heap setting the TOTAL_HEAP_SIZE configuration macro when assembling a compiled program.

inexact->exact uses the FISTTP instruction, so a CPU with SSE3 support is required.

Complex numbers and other numeric types with the exception of small integers and floating-point numbers are not supported.

string->number does not detect overflow when converting integers and returns -1 if the result does not fit into a fixnum.

Library support for on Linux for "nolibc" mode is incomplete:

• number->string and string->number do not support inexact numbers.

The maximum number of arguments that can be passed to a procedure is currently 1024 + 9. You can change this by giving a different value for the NUMBER_OF_NON_REGISTER_ARGUMENTS in the boneslib.s file.

Building shared libraries ("bundles") from code compiled with BONES does currently not work on Mac OS X.

The system should be relatively easy to port. The only target-specific code is contained in the x86_64.scm backend, in the runtime library in <ARCH>/boneslib.s and in the files defining intrinsics and system-calls. The compiler makes very little assumptions about the used assembler-syntax and should be suitable for most assemblers, unless you want to generate code for a very unusual target.

The code-generation scheme assumes that a certain number of registers is available, and the more registers are available for arguments and local variables, the better. In fact, this is the reason why BONES has not been ported to i386: the number of available registers is too low. On modern architectures this is not much of an issue anymore, though.

The default configuration file base.scm selects the appropriate files to be included for defining intrinsics and system-specific code, so extending this will be required. If no target feature is given on the command-line (currently linux, bsd, mac or windows), then a default-target is selected, which is the target, the compiler is currently running on, or more specifically: the target for which the currently executing compiler was configured. This feature will be named default-linux, default-bsd, default-mac or default-windows, depending on the OS. Don't forget to add a case for the default-configuration variable in cmplr.scm.

If you intend to provide a nolibc mode, that is, a compilation mode that generates code for use without the C library, then this should also be reflected in base.scm.

The code currently makes no assumptions about endianness.

On 32-bit systems, care must be taken with alignment of floating-point numbers: the actual float value must be located on an 8-byte boundary, as most architectures require this, and even if not, aligned memory-accesses are likely to be more efficient. Allocation of floating-point numbers and the code in the garbage collector copying data from one heap-space to the other need to take this into account.

On x86_64 systems, the FPU provides machine-instructions for many transcendental functions. Other architectures will probably not have support for these, so the associated intrinsic operations in <ARCH>/intrinsics.scm need to be adapted to call C library functions.

The actual implementation of library- and system-calls are located in <ARCH>/<OS>/syscalls.scm and <ARCH>/<OS>/syscalls-nolibc.scm, respectively, depending on the compilation mode. The operations here use OS-dependent constants, defined in <ARCH>/<OS>/constants.scm, which needs to be generated and added manually. To generate this file, compile and run the C program constants.c, which produces the file when executed.

All compile-time features, defined using the -feature option or the provide program-specification clause are also defined in compiled programs in the form of assembler macros (or symbols), prefixed with FEATURE_, converted to uppercase and with - (hyphen) replaced by _ (underscore) characters. The generated code should also perform an include of the <ARCH>/boneslib.s file appropriate for the target platform.

To reduce code size in statically linked executables it may be worthwhile to use a replacement for the standard C library. glibc is relatively large and complex and there exist alternatives in the form of MUSL or dietlibc, which are much smaller, simpler and more than sufficient in most cases. By linking these statically, the program is self-contained and has fast startup times. Using MUSL, for example is straightforward: instead of linking with gcc, use musl-gcc, like this:

bones myprogram.scm -o myprogram.s
nasm -f elf64 myprogram.s -o myprogram.o
musl-gcc myprogram.o -o myprogram

If you are interested in extending the compiler or runtime system, or if you'd like to experiment, here are a few suggestions:

• Generating machine code and creating elf64/win64 object files directly. This would remove the need for an assembler and speed up the compilation process.
• Compiling into memory directly, for later execution. This is complicated by the fact that memory-pages need to be made executable, but still be reclaimable by the garbage collector.
• Extending the language, for example by adding support for R7RS. Implementing the R7RS module system will be quite a challenge, though, as the syntax-expander used ("alexpander") does not support this in the moment.
• Porting the system to other architectures and operating systems.
• Generate code suitable for the GNU assembler (as). Since the GNU binutils are needed anyway on Linux, and because as is quite fast, this would remove the need for NASM. On the other hand, NASM is more featureful and supports a nicer and more consistent assembler syntax.
• Other backends, say, asm.js or LLVM. This is a challenge as well, as these languages do not support jumps to arbitrary locations.
• With a little work code compiled with BONES should be able to run without any library at all ("bare metal"), which would make it possible to write, say, an OS Kernel in Scheme.

Some parts of BONES are not by the author, but have been taken from other sources:

The pretty-printer (pp.scm) is

Copyright (c) 1991, Marc Feeley, Author: Marc Feeley, Distribution restrictions: none

The pattern-matching package was written by Alex Shinn and is in the public domain.

The syntax-expander (alexpand.scm) is

Copyright 2002-2004 Al Petrofsky

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of the author nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

The topological sorting routine in tsort.scm was written by Moritz Heidkamp and is in the public domain.

Everything else was written by Felix Winkelmann and is put into the public domain.

Cheney's Algorithm describes the garbage collection method used in BONES.

Compiling with Continuations by Andrew Appel covers CPS-based compilation of high-level languages in great detail.

Essentials of Programming Languages describes the CPS-conversion algorithm used in BONES and contains a lot of interesting information about implementing interpreters.

Agner Fog's website contains a wealth of information about x86 CPUs and optimization tips.

A list of of Linux/x86_64 system calls can be found here.

Simply FPU contains a lot of information on the x86 FPU.

Check out schemers.org for basic information about Scheme and the different standards.

The Intel manuals exhaustively describe the x86 architecture.

Also check out the Linux ABI for x86_64 architectures.

If you have questions, bug-reports or suggestions for improvements, please contact me at felix <at> call-with-current-continuation <dot> org.