Tessera, part 1.

I’ve been working on a domain specific language called “Tessera” for defining tilings of the plane and rendering them to SVG. It is particularly suited for tilings with a recursive structure, typically aperiodic tilings. For example, this image of the Penrose rhombuses

was generated from this tessera script, and the image of Robert Amman’s A5 tiling in the header of this post was generated from this tessera script.

Tessera is a pure functional language implemented in C++17, source code here. I’m using Boost Spirit X3 to implement the parser, Eigen for matrices, Boost Multiprecision for greater than double precision floating point numbers, and my own “graph_ptr” class for garbage collecting smart pointers. These graph_ptrs are somewhat similar to Herb Sutter’s deferred_ptr, which I tried at first but found to perform too inefficiently for my use case. My implementation of Tessera parses source code into an expression tree and then compiles the expression tree into commands for a stack machine representation that actually executes the script.

Tessera is a Turing complete language and the scope of the project is big enough that I can’t easily document the whole thing in a single blog post. I plan on doing more posts like these, one focusing on advanced features of the language and perhaps one focusing on the language’s implementation. However, to get a feel for the language consider the following script which generates a “Sierpinki Carpet”.

let square = { regular_polygon(4) } with {
    north, west, south, east is this.edges;
    color is "purple";
};

let sierpinski_carpet = func( n ) {
    lay 
       s as N, s as NE, s as E, s as SE, s as S, s as SW, s as W, s as NW 
    such_that 
       N.east <-> NE.west,
       NE.south <-> E.north,
       E.south <-> SE.north,
       SE.west <-> S.east,
       S.west <-> SW.east,
       SW.north <-> W.south,
       W.north <-> NW.south 
    with {
       north, west, south, east on [N.north, W.west, S.south, E.east];
    }
} where {
    let s = if (n == 1) square else sierpinski_carpet(n-1);
};

tableau( num ) {
    lay sierpinski_carpet( num )
}
  1. We define square to be a square shaped tile with its edges named after the cardinal directions as in (1) below. This is done by wrapping the output of the canned regular_polygon() function in a “with expression”. Using with we can add fields to an existing object (well, to a clone, as this is a pure functional language — objects are immutable). In this case we add a color and we add names for the four edges.
  2. We define a recursive function sierpinski_carpet.
    1. The meat of the work is done in a lay expression. Intuitively lay expressions model laying patches of adjacent tiles.
      1. We specify eight arguments to lay. Each argument is whatever object s is. Again these will be clones of s, as objects are immutable.
      2. We provide aliases for the eight arguments that can be used to refer to them within the lay expression.
      3. In the such_that clause of the expression we use the aliases to specify edge-to-edge matchings that define a square ring as in (2)
      4. In the with clause we specify the names of fields that will be part of the public interface of the patch that the lay expression evaluates to. We can specify the new fields in terms of the aliases of the arguments as they are still in scope. We let “east” refer to the east side of the east square in the patch, etc., as in (3)
    2. In the where clause of a function, which is evaluated before the function body, we can define local variables that will be in scope during the evaluation of the body. In this case we define an object s that is either a square tile to terminate the recursion or the result of evaluating a recursive call to sierpinski_carpet.
  3. In the tableau block we call sierpinski_carpet on a numeric argument that can be provided when the tessera script is executed. tableau is like the main function of a C program, the entry point of the program.

Calling sierpinski_carpet on 4 yields

Leave A Comment

Your email address will not be published. Required fields are marked *