Temple of Odin: Template Language Breakdown

Temple of Odin is a template language interpreter I've been working on. As of writing, it's at least good enough to be used on the website you're reading this on. I wanted to give an overview of how it works and what makes it special.

Introduction

Temple of Odin is a template markup language. This means its sole purpose is to seed data into a text template. Below is an example of ToO's (Temple of Odin's) syntax.

Tomorrow I would like to wake up at @($.hour):00am

The seed data (identified by the dollar sign) has some kind of hour field, probably an integer. The interpreter finds this field and inserts the value into the template. Doing the same thing with a standard C format string might look like this.

printf("Tomorrow I would like to wake up at %d:00am", hour);

The difference is that ToO can put logic into the template itself. If we wanted, we could change the template to convert from a 24-hour internal representation to be displayed as a 12-hour clock.

Tomorrow I would like to wake up at @($.hour > 12 ? $.hour - 12 : $.hour):00@($.hour > 12 ? "pm" : "am")

hour	output
7	Tomorrow I would like to wake up at 7:00am
14	Tomorrow I would like to wake up at 2:00pm
21	Tomorrow I would like to wake up at 9:00pm

The ternary expressions return values that get formatted into the text. ToO also has if-statements and for-loops.

Watch me count to ten! @for i in 1..=10 {@(i)@if i < 10 {,} }done

I decided to only allow range-based loops so there's no possibility of an infinite loop. I can't think of any situations where an unbounded loop in a template would be useful anyways. With the loop variable i, we can also see that ToO is capable of storing state within a scope. It's pretty easy to assign a variable as well.

@(x := 0)
@(y := 0)
@(w := $.w)
@if true {
	@(x = w)
	@(y := w)
}
@(x), @(y)

There are the same scope rules as Odin. y gets shadowed inside the if-statement, but that wouldn't be allowed in the outer scope. At the end, x is equal to w and y is still 0.

This article is not meant to be full documentation of ToO; in fact, I wouldn't recommend other people use it yet. The library is at the stage of development where I'm testing it in the real world (this website) before adding polish. Once it has my full confidence, the docs will be in the Git repo.

First Implentation

I'm going into more technical detail now. I'm assuming you already have some knowledge of interpreters and ASTs (abstract syntax trees).

Sergei Kharni's article, Optimising interpreters: fusion was what spurred me on to this project. The article introduced me to the concept of supernodes, a way to optimize tree walk interpreters by combining node evaluations that often happen together. This process can even be automated through heuristics on code.

A good example would be adding a constant number to a variable: x + 5. A standard AST might represent this with 3 nodes that need evaluation: the top-level node for with an add operation, and its two child nodes. If we notice that constants get added to variables a lot, we could reduce the number of nodes that get evaluated by making a specialized supernode that simply holds a number to be added to another node's result.

I was trying out Go templates at the time. They are convenient and simple, but I had some frustrations. Setting up custom callbacks is required for a lot of basic functionality, such as math operations. I also found that the error reporting left a lot to be desired. Making a mistake could mean part of my template not rendering without any details of what I did wrong.

With that in mind, and because it sounded fun, I decided to roll my own template language using this fancy technique. I started by doing exactly what I'd done for previous interpreters. I defined a new type for all the different node possibilities, then I hooked them into a tree using pointers. I wrote a function called evaluate_node that recursively solved each node.

Node :: struct {
	variant: union {
		^Source_Node,
		^Access_Node,
		^Implicit_Selector_Node,
		^If_Node,
		^For_Loop_Node,
		^Operation_Node,
		^Unary_Node,
	},
	next:   ^Node,
}

Source_Node :: struct {
	using node: Node,
	str:        string,
}

Access_Node :: struct {
	using node: Node,
	name:       string,
	from:       ^Access_Node,
}

If_Node :: struct {
	using node: Node,
	condition:  ^Node,
	if_true:    ^Node,
	else_if:    ^Node,
}

For_Loop_Node :: struct {
	using node: Node,
	variables:  [2]strings,
	iterator:   ^Node,
	block:      ^Node,
}

Operation_Node :: struct {
	using node: Node,
	lhs:        ^Node,
	rhs:        ^Node,
	op:         Token_Kind,
}

Unary_Node :: struct {
	using node: Node,
	rhs:        ^Node,
	op:         Token_Kind,
}

evaluate_node :: proc(n: ^Node) -> Value {
	switch nvar in n.variant {
		...
	}
}

The output is just a concatenation of every top-level node's result. The next variable in the nodes makes a linked list of subtrees. Each one gets evaluated in order and writes to the output stream.

Hello, please call me @(nickname)!

Source_Node{str = "Hello please call me "} -> Access_Node{name = "nickname"} -> Source_Node{str = "!"}

The problem with all these types is that every one requires more code to handle it in the evaluation function. On top of that, the whole point of this supernode concept was that I would create more node types to merge the functionality of existing nodes. The code got more bloated with every type, and I was getting annoyed. It wasn't clear how this could go on while keeping complexity reasonable.

Present Implementation

As I was struggling with how I would deal with the growing complexity, I was very fortunate to be reading Ryan Fleury's user interface articles. His insights on code complexity were exactly what I needed to hear. This passage from The Widget Is A Lie hit me hard, "Attaching a too high-level or top-down name to nothing more than a useful data-organization mechanism—like 'widget'—can often lead us astray. And, indeed, using the 'widget' label did lead me astray for years."

That was exactly what I'd done. I saw a for-loop, and I created a struct called For_Loop_Node with fields for the declaration, iterator, etc. I didn't think seriously about what the for-loop needed to do until after I created that struct. It turns out that basing my interpreter's structure off the way the language looks in a text file is a bad idea.

"Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won't usually need your flowchart; it'll be obvious." I used to think that quote by Fred Brooks meant good types made the right algorithm obvious. Now I'm convinced of the opposite. Types are revealing when they are a reflection of your algorithms, not some arbitrary mental model.

I needed to find a better way to represent my instructions. The main codebase was too big for fast iteration, so I made prototypes to find what worked. It didn't take long for a much more elegant solution to emerge.

AST_Node :: struct {
	flags:   bit_set[AST_Node_Flag],
	value:   Value,
	op:      Token_Kind,
	noderef: int,
}

AST_Node_Flag :: enum {
	Insert_Guard_RHS,
	Load,
	Push_RHS,
	Push_Value,
	Value_Is_LHS,
	LHS,
	Peek_LHS,
	LHS2,
	RHS,
	Peek_RHS,
	Swap_Sides,
	Enter_Scope,
	Leave_Scope,
	Flip,
	Jump,
	Jump_If_False_Or_Error,
	Write_Out,
	Consume_Guard_RHS,
}

I didn't intend to bring my instructions closer to a bytecode, but that's just what ended up happening.

flags defines flag bits that turn on/off behaviors of the node
value is a general-purpose value to be pushed to the stack or used in an operation
op is a token kind that defines specific operator actions. (add, subtract, assign)
noderef is a reference to another node for doing jumps

Aside from doing jumps, a stack removes the need for nodes to reference each other directly. For many other languages it can be important to control what sub-trees do and don't get called. For example: func1() && func2() This expression calls func1 first, but if func1 returns false, it won't call func2. This makes a difference if func2 has any side effects. In ToO however, side effects are not possible on an expression level, so we can evaluate both func1 and func2 before knowing about the boolean && operation.

You may have noticed flags such as RHS, LHS, and Push_RHS. The stack is actually double-sided. The right-hand side (RHS) and left-hand side (LHS) refer to the beginning and end of the stack respectively. In a statement like x, y := 1, 2, the interpreter can push the names x and y to the left, then 1 and 2 to the right. Now assignment operations can pop from both sides to create the variables.

The best part is how many possibilities are now open to combine nodes. An operator node could store a constant in its value field and use it directly instead of popping from the stack. The Flip flag toggles the last boolean on the stack, so the ! unary operator doesn't need to add any new nodes. All of this can be from trivial additions to the evaluation function.

Benchmarks

Let's see how ToO holds up (in speed) against some other template languages. I chose Go templates, Shopify Liquid, and not anything like mustache, because they have control flow. I understand that the benchmarks are not perfect. I don't have any experience with Ruby, which Shopify Liquid is implemented in. The code for these tests are published here. Please send me feedback if you find any issues with my methodology.

System76 Lemeur Pro running Pop!_OS 22.04
11th Gen Intel i5-1135G7 @ 2.40GHz x 8
16 GiB of RAM
	Temple of Odin	Go Templates	Liquid
Large Text	31.194µs	88.74µs	167.207µs
Large Text (Pre-Compiled)	25.674µs	59.621µs	110.504µs
Factorials	142.88µs	210.573µs	1.405957ms
Factorials (Pre-Compiled)	138.726µs	173.264µs	1.308769ms

Lenovo Thinkpad T430 running Windows 10 Pro
3rd Gen Intel i7-3632QM @ 2.20GHz x 4
16 GiB of RAM
	Temple of Odin	Go Templates	Liquid
Large Text	86.103µs	236.192µs	740.4µs
Large Text (Pre-Compiled)	71.066µs	204.151µs	530.43µs
Factorials	195.197µs	502.911µs	3.06ms
Factorials (Pre-Compiled)	192.94µs	472.606µs	2.75ms

Doing a speed comparison with Ruby code is a little unfair. I will say Liquid is still the most capable in terms of features right now (I'm assuming from their docs because I've never used it seriously). I'm more disappointed that Go templates didn't hold up better. Sure, Go has some GC overhead and stuff, but I figured its more minimal syntax and feature set would give it an edge.

Other Details

The Two Tokenizers

The language passes in and out of two states. What I call Source and Statement. Take a look at this template:

1 + 1 = @(1 + 1)

We see two ones, a plus sign, and an equal sign. However, before the @ sign, the first '1 + 1 =' is just being interpreted as a string. The @ sign then tells the parser to enter a statement. The other tokenizer now recognizes the ones as number tokens, the plus sign as its own token, ignores the whitespace.

Why do we even need a tokenizer for plain text? Because you can use backslash escape sequences to skip whitespace and insert special characters.

Type System

Normally I would use a simple type system for an interpreted language, but Temple of Odin is meant to interop with Odin types, so it inherits Odin's strict and detailed type system. That being said, a lot of type checking still needs to happen during execution. ToO has no way to know if some expressions are valid until the template is supplied with a seed value.

I am @($.year_born - $.current_year) years old.	 I sure hope year_born and current_year are the same numeric type!

I employ some tricks to make sure I don't have too much repeated code for all the different types. For example, all integers are 64 bit and unsigned under the hood. That is until they need to multiply or divide where being signed actually matters. For integers under 64 bits, there's some additional logic that makes them overflow when going above their bounds.