Creating an RPG backend - a scheme tutorial

About this tutorial

My road to Scheme started in 2013. It took me many years to understand how to use Scheme well. I want to help you to get there faster. Also I’ll describe my mistakes, so you can learn from them without repeating them.

I will do it in the way which works best for me: By building a roleplaying system backend.

The goal

We will build a library and commandline tool to decide the results of interaction in roleplaying systems: Skill tests, challenges person against person, single battle actions and resolving a battle in one roll.

The commandline tool will also provide minimal description of the battle actions, as flavor for a game, and the library will provide information needed to give feedback to the player.

We’ll implement the 1d6 rules, because they are free licensed — and because I created them. That’s not a good reason to choose a ruleset in general, but it is a way for me to fill two needs with one deed, because I also need a clean implementations of those rules for dryads wake, a game I started a while back.

As syntax I’ll use wisp, also known as srfi-119, because it looks easier for non-lispers — and to fill two needs with one deed again.

The data

The first step is to build the data structures. They also describe the outcome of the functions we create.

When I started with Scheme, I used primitive data structures for most things: mainly singly linked lists and hash maps. This is the approach I knew from Python. But in Scheme, the cleanest way to structure data is to use records, standardized across implementations in srfi-9. They are equivalent to named tuples in Python. In Java you’d call them data classes.

Let’s start. The minimal data class we need is the result of a roll.

import : srfi srfi-9
define-record-type <roll-result>
  roll-result face value
  . roll-result?
  face roll-face
  value roll-value

Note: Creating a record type has low overhead, but it is not completely free (though it could be made to be free by keeping more info outside the record). See the appendix Cost of records in memory and time for empiric results. Here we just need to know that the overhead is less than factor 4, which we’ll ignore.

Defining a record type creates functions for the record which you can then use to create instances of such records. This is about the same as for named tuples in Python, just with more convenience.

So we have the first data structure: a roll-result which has a face (the face of the die which faced up) and a value (what the face means). Also there’s an accessor function to test whether something is a roll-result (roll-result?).

Note the angle-brackets (<>) around the first element — the name. These are required.

The second element in a record definition is the constructor. It receives values.

The third element is a predicate — the name of a function which can test whether something is of this type.

The rest of the arguments are the constructor-arguments with accessor functions. We can access the face as roll-face x (note that I dropped the result-suffix for brevity) and the value as roll-value x, with x as a roll-result object.


Cost of records in memory and time

In the tutorial we used records to keep data. The simplest one was the roll-result:

import : srfi srfi-9
define-record-type <roll-result>
  roll-result face value
  . roll-result?
  face roll-face
  value roll-value

Instead of the records, we could also use a cons-pair or a list.

define as-record : roll-result 4 4
define as-pair : cons 4 4
define as-list : list 4 4

As the most compact alternative, we could create two vectors, one for each element.

To see the effect, let’s create ten million records, and then ten million cons pairs and lists, and two vectors with the data. Then we’ll check the cost.

define roll-results : map (λ (x) (roll-result x x)) : iota : * 10 : expt 2 20
define roll-results : map (λ (x) (cons x x)) : iota : * 10 : expt 2 20
define roll-results : map (λ (x) (list x x)) : iota : * 10 : expt 2 20
define faces : make-vector : * 10 : expt 2 20
define values : make-vector : * 10 : expt 2 20
for-each (λ (x) (vector-set! faces x x)) : iota : * 10 : expt 2 20
for-each (λ (x) (vector-set! values x x)) : iota : * 10 : expt 2 20

Memory usage

To check the memory usage, we can simply use top and pgrep:

top -n1 -p $(pgrep guile | tail -n 1) # assuming that the highest PID is the last started process

With the record types, the program consumes 972 MiB, so each record in the list takes up about 97 bytes.

With a simple cons-pair, the program consumes 610 MiB, so each pair consumes about 61 bytes.

However with a list, the same program consumes 1200 MiB, so each list element takes up around 120 bytes.

The vectors take up 535 MiB, so each pair of values requires only about 54 bytes.


Creation times also differ. To test:

echo record
time guile -c '(import (srfi srfi-9))
  (define-record-type <roll-result>
    (roll-result face value)
    (face roll-face)
    (value roll-value))
  (define roll-results (map (λ (x) (roll-result x x)) (iota (* 10 (expt 2 20)))))'
echo cons-pair
time guile -c '(define roll-results2 (map (λ (x) (cons x x)) (iota (* 10 (expt 2 20)))))'
echo list-pair
time guile -c '(define roll-results2 (map (λ (x) (list x x)) (iota (* 10 (expt 2 20)))))'
echo vectors
time guile -c '(define faces (make-vector (* 10 (expt 2 20))))
  (define values (make-vector (* 10 (expt 2 20))))
  (for-each (λ (x) (vector-set! faces x x)(vector-set! values x x)) (iota  (* 10 (expt 2 20))))'

On my system the record-creation requires about 8s to 9s, the cons-approach needs 2.5s to 3s and the list-approach needs 3s to 4s. The vectors are between cons and lists.


A record of two values requires about twice as much memory as the cheapest approach with plain cons or vectors and requires about three times as much time.

With Guise and Guile

License: cc by-sa

Author: Arne Babenhauserheide

Created: 2020-05-06 Wed 09:34

Emacs 24.5.1 (Org mode 8.2.6)