Tengo: Inside a script language for Go

Why I wrote it

I started Tengo between jobs. It felt like my last real chance to take on a system that complex. Making my own programming language was a milestone I wanted in my life, and I felt I had to tackle it before I got too old.

This was 2018, so no AI was around to help. Every bug in the first version is mine.

The name comes from Tengo, a character in Murakami's 1Q84.

12,121 lines before anyone saw it

I worked on Tengo for a few weeks before I pushed anything. The first commit, on January 9, 2019, was 12,121 lines of Go in 143 files. Of those, 4,707 lines were tests.

It already had the whole pipeline: a scanner, a parser, a compiler, a VM and the object model. It also had a REPL and cmd/bench, a tool that timed fib(35) in Tengo and in native Go.

Four days later, the first README already had a table of fib(35) times, with Tengo beside Go, Lua, go-lua, GopherLua, Python, otto and Anko.

Here is the program the README still opens with. It prints 6, then 123, because + on a string turns the int on its right into text.

/* The Tengo Language */
fmt := import("fmt")

each := func(seq, fn) {
    for x in seq { fn(x) }
}

sum := func(init, seq) {
    each(seq, func(x) { init += x })
    return init
}

fmt.println(sum(0, [1, 2, 3]))   // "6"
fmt.println(sum("", [1, 2, 3]))  // "123"

The syntax is close to Go's, but the types are dynamic and functions are values. I wrote 145 of the first 155 commits. Seven years on, the repository has 3.8k stars, 38 contributors and 356 commits on master.

Following fib through the pipeline

Every script takes the same path. The scanner turns text into tokens, the parser builds a tree, the compiler emits bytecode, and the VM runs it. All four are plain Go, with no dependencies outside the standard library.

This is the function I'll follow, the fib from Tengo's own benchmarks:

fib := func(x) {
	if x == 0 {
		return 0
	} else if x == 1 {
		return 1
	}
	return fib(x-1) + fib(x-2)
}
out := fib(20)

The scanner is based on Go's, and it keeps Go's semicolon rule. A newline after an identifier, a literal, return or a closing bracket becomes a semicolon. That is why Tengo, like Go, needs none at line ends.

The parser is recursive descent, with one method per construct and Go's five levels of operator precedence. It keeps one error per line, and it stops after ten.

Reading the bytecode

The compiler walks the tree once. Each function becomes a flat byte slice: a one-byte opcode, then up to two big-endian operands. Every number, string and char literal, and every function body, goes into one shared constants pool.

I wrote a short program that compiles fib and prints it with Tengo's own FormatInstructions. Here is the output, with pointer addresses trimmed:

$ go run ./dump
--- main
0000 CONST   3
0003 SETG    0
0006 GETG    0
0009 CONST   4
0012 CALL    1     0
0015 SETG    1
0018 SUSPEND
--- constants
[  0] 0 (Int|…)
[  1] 1 (Int|…)
[  2] 2 (Int|…)
[  3] (Compiled Function|…)
     0000 GETL    0
     0002 CONST   0
     0005 EQL
     0006 JMPF    16
     0011 CONST   0
     0014 RET     1
     0016 GETL    0
     0018 CONST   1
     0021 EQL
     0022 JMPF    32
     0027 CONST   1
     0030 RET     1
     0032 GETG    0
     0035 GETL    0
     0037 CONST   1
     0040 BINARYOP 12
     0042 CALL    1     0
     0045 GETG    0
     0048 GETL    0
     0050 CONST   2
     0053 BINARYOP 12
     0055 CALL    1     0
     0058 BINARYOP 11
     0060 RET     1
[  4] 20 (Int|…)

The main script is seven instructions. It stores the function in global 0, calls it with 20, and stores the result in global 1. SUSPEND ends the main script and hands control back to Go.

Inside fib, read from the top. GETL 0 pushes x, CONST 0 pushes 0, and EQL compares them. If they differ, JMPF 16 jumps past the return to offset 16.

On the last line, fib reaches itself with GETG 0, not through a closure, because it's a global. GETL 0, CONST 1 and BINARYOP 12 compute x-1, and CALL 1 0 calls with one argument. After both calls, BINARYOP 11 adds the results.

Most operators share that one opcode. BINARYOP carries the operator as a token, 11 for + and 12 for -, and the VM passes it to the left operand's BinaryOp method.

That design came from earncef, a contributor, in March 2019. Before it, each operator had its own opcode and its own case in the VM. Today the instruction set has 42 opcodes.

The constants pool has five entries, though the body uses 0 twice and 1 three times. After compiling, RemoveDuplicates merges equal constants across the program, so eight went in and five came out.

Inside VM.run

The VM is one method, VM.run in vm.go. It is a for loop around a switch on the current opcode, with one case per opcode:

func (v *VM) run() {
	for atomic.LoadInt64(&v.aborting) == 0 {
		v.ip++

		switch v.curInsts[v.ip] {
		case parser.OpConstant:
			v.ip += 2
			cidx := int(v.curInsts[v.ip]) | int(v.curInsts[v.ip-1])<<8

			if v.stackFull() {
				return
			}
			v.stack[v.sp] = v.constants[cidx]
			v.sp++

Each case decodes its own operands and works on the stack directly. Calls push frames onto a fixed array of 1,024, and every frame shares one stack of 2,048 slots.

With no other dispatch layer, a profile has one place to look. In BenchmarkFib, 76% of CPU samples land in run itself.

The first VM was less direct. Its cases called push and pop helpers. On January 14, 2019, I replaced those calls with inline stack writes in every case. On the box I used for this post, that commit alone cut fib(35) from 3.65 s to 3.00 s.

The for condition also lets a host stop a script. Before every instruction, it loads a flag that Abort sets. RunContext calls Abort when its context is done, so a deadline can stop a script mid-loop.

The flag was a plain bool in the first commit. On January 20, 2019, I added context support. The same day, I made the flag an atomic int64 to fix a data race.

In my test, a for {} loop with a 50 ms timeout returned context deadline exceeded after 50 ms. The check sits between instructions, so a slow Go function that a script calls still runs to its end.

Tail calls in the first week

Two days after the first commit, I added tail calls. Two days after that, I fixed a bug in them. The first README's table had a column for them: fibt(35), the tail-recursive version of fib.

The check only fires when the callee is the function already running and the next opcode returns. Then the call reuses the current frame:

// test if it's tail-call
if callee == v.curFrame.fn { // recursion
	nextOp := v.curInsts[v.ip+1]
	if nextOp == parser.OpReturn ||
		(nextOp == parser.OpPop &&
			parser.OpReturn == v.curInsts[v.ip+2]) {
		for p := 0; p < numArgs; p++ {
			v.stack[v.curFrame.basePointer+p] =
				v.stack[v.sp-numArgs+p]
		}
		v.sp -= numArgs + 1
		v.ip = -1 // reset IP to beginning of the frame
		continue
	}
}

It copies the arguments over the frame's first slots and sets ip to -1, so the loop restarts the function. The check compares function pointers, so only direct self-recursion qualifies. Two functions that call each other still use a frame per call.

To see the difference, I ran both kinds of recursion deep. A tail-recursive g(n - 1, acc + 1) ran 1,000,000 calls deep. return 1 + f(n - 1) failed at 682 calls with stack overflow, because each of its frames holds three of the 2,048 stack slots.

Closures and scopes

Tengo closures capture variables by reference, as Go's do. The compiler resolves every name to a global, a local, a builtin or a free variable. A local from an enclosing function becomes free, and the closure reaches it through a pointer. Take a counter:

=== closure
counter := func() {
	n := 0
	return func(d) {
		n += d
		return n
	}
}
c := counter()
out := c(2)
…
[  1] (Compiled Function|…)
     0000 GETF    0
     0002 GETL    0
     0004 BINARYOP 11
     0006 SETF    0
     0008 GETF    0
     0010 RET     1
[  2] (Compiled Function|…)
     0000 CONST   0
     0003 DEFL    0
     0005 GETLP   0
     0007 CLOSURE 1     1
     0011 RET     1

counter keeps n in local slot 0. GETLP 0 wraps that slot in an ObjectPtr and pushes the pointer. CLOSURE 1 1 builds the inner function from constant 1, with that pointer as its one free variable. Inside, n += d reads and writes through it with GETF 0 and SETF 0.

A local function that calls itself is the hard case. It captures its own slot before the slot holds anything. A long comment in compiler.go describes the fix: define the slot as NULL, build the closure, then store it with SETL.

=== localrec
f := func() {
	g := func(x) { return x == 0 ? 0 : g(x - 1) }
	return g(3)
}
…
[  4] (Compiled Function|…)
     0000 NULL
     0001 DEFL    0
     0003 GETLP   0
     0005 CLOSURE 2     1
     0009 SETL    0
…

SETL 0 writes through the pointer that GETLP left in slot 0. The closure holds that same pointer, so g finds itself.

Scopes needed fixes for years. I fixed a closure scope bug in February 2019, a block scope bug in March 2019, and two symbol-resolution bugs in September 2020.

An optimizer that only deletes

The compiler has one optimization pass, which I added in March 2019. After a RET, it deletes code that no jump can reach. Then it rewrites the jump targets and the source map to match.

In fib, the compiler emits a JMP after return 0 to skip the rest of the if chain. Nothing reaches it, so the pass drops it, and the body shrinks from 67 bytes to 62.

The pass folds no constants. a := 1 + 2 compiles to two loads and a BINARYOP, and the VM adds 1 and 2 on every run:

0000 CONST   0
0003 CONST   1
0006 BINARYOP 11
0008 SETG    0
0011 SUSPEND

Every deletion shifts the offsets after it, so every jump target and source position has to move too. The pass needed four fixes: in March 2019, twice in May 2020, and in June 2022.

Nothing by default

Modules arrived in the second week. On January 18, 2019, I added an os module and an exec module, for files, processes and environment variables.

For the next six weeks, every script could import them by default. On March 4, 2019, earncef decoupled the standard library from the compiler and VM. Since then, a script gets no modules until its host adds them.

That default is most of what the README means by "securely embeddable". import("os") fails to compile with module 'os' not found. None of the 32 builtin functions reads, writes or prints, and file imports stay off until the host turns them on.

The same month brought two more controls. SetMaxAllocs caps the instructions that can create an object, so a runaway script fails with object allocation limit exceeded. Compiled.Clone copies a compiled script, so a host can run it again without compiling it again. A host that uses both looks like this:

package main

import (
	"context"
	"fmt"
	"time"

	"github.com/d5/tengo/v2"
	"github.com/d5/tengo/v2/stdlib"
)

func main() {
	s := tengo.NewScript([]byte(`
text := import("text")
out := text.to_upper(name) + "!"
`))
	_ = s.Add("name", "tengo")
	s.SetImports(stdlib.GetModuleMap("text")) // text only: no os, no fmt
	s.SetMaxAllocs(10000)                      // fail the run past 10,000 objects

	compiled, err := s.Compile()
	if err != nil {
		panic(err)
	}

	ctx, cancel := context.WithTimeout(context.Background(), 100*time.Millisecond)
	defer cancel()

	c := compiled.Clone() // a fresh copy for this run
	if err := c.RunContext(ctx); err != nil {
		panic(err)
	}
	fmt.Println(c.Get("out")) // TENGO!
}

It prints TENGO!. The script can uppercase text, but it can't open a file, start a process or print.

Seven years of fib(35)

To see where the speed came from, I built 20 versions of Tengo, from the first commit to master, and timed fib(35) on each.

Every build ran the same script through its own cmd/bench, on one arm64 EC2 box with Go 1.27.3. Each number is the VM's time, the median of three runs.

Every build I timed

Date	Commit	Change	fib(35)
2019-01-09	2c3282d	initial commit	3.87 s
2019-01-11	b2a2934	tail call optimization	3.77 s
2019-01-13	ca128af	reduce number of memory allocation in object binary operators	3.71 s
2019-01-13	de70f7c	trying to optimize VM by cutting some repeated codes	3.65 s
2019-01-14	32df286	remove unnecessary function calls in VM	3.00 s
2019-01-20	336fbc3	some performance optimization in VM	2.90 s
2019-01-30	v1.0.0	Merge pull request #62 from d5/v1prep	2.91 s
2019-02-28	v1.10.0	SetBuiltinFunctions and SetBuiltinModules (#120)	2.83 s
2019-03-13	1921d90	fix scipt.Variable.Value() bug (#139)	2.83 s
2019-03-14	5d8457a	Removed double indirection for massive performance gains (#140)	2.26 s
2019-03-14	17329aa	update benchmark result with v1.15.0 (#141)	2.25 s
2019-03-16	052ae59	Refactored duplicate REPL code (#145)	2.25 s
2019-03-18	61890b1	module refactor (#148)	2.47 s
2019-03-20	7095b56	add ModuleMap.Remove() (#155)	2.46 s
2019-03-22	09f3d52	Opbinaryop and other minor optimizations (#157)	2.33 s
2019-03-24	b9c1c92	Compiler optimization first iteration (#165)	2.35 s
2019-04-26	v1.24.0	add variadic function parameters (#189)	2.32 s
2019-12-20	v2.0.0	fix go.sum (#238)	2.46 s
2022-06-10	v2.11.0	fix deadcode optimization (#378)	2.48 s
2026-11-01	bba82fa	test: add unit tests for untested code across the module (#512)	2.49 s

Most of the gain came in the first ten weeks. fib(35) took 3.87 s at the first commit and 2.26 s on March 14, 2019, 42% less time.

The two biggest steps both removed indirection. Inlining the stack pushes and pops on January 14 saved 18%. On March 14, earncef made the VM's stack hold interface values directly, not pointers to them. That removed a pointer hop on every read and write, and it took fib(35) from 2.83 s to 2.26 s, another 20%.

My module refactor four days later gave some of it back. It made fib(35) 9.5% slower, from 2.25 s to 2.47 s. earncef's BINARYOP change won back 5% on March 22.

Every version I timed after that stayed between 2.3 and 2.5 s, through v2.0.0 in December 2019 and master today. On master, fib(35) takes 36% less time than at the first commit.

Native Go runs the same fib(35) in 34.5 ms in that benchmark, about 72 times faster. In the README's table, Tengo's 2,315 ms compares with 4,028 ms for go-lua and 5,194 ms for goja.

The rest of the profile explains the gap. After the 76% in run, 13% of samples are in Int.BinaryOp. Every integer result is a new heap object, so arithmetic also pays the allocator.

One early trick still helps. Since January 13, 2019, Int.BinaryOp returns its receiver when the result equals it, so x + 0 allocates nothing. Even so, a 100,000-pass loop in bench_test.go makes 299,997 allocations, close to three per pass.

What I learned

Because cmd/bench shipped in the first commit, I could time all 20 versions in this post with the same tool.

The two biggest gains removed a function call and a pointer hop, and no later version I timed moved fib(35) as far. So I'd cut indirection before trying anything clever.

I'd make the safe choice the default from the start. A script with no modules can compute, but it can't touch files, processes or stdout, and the host opts in one module at a time.

Contributors found what I missed. earncef made three of the changes in this post: BINARYOP, the stack's type and the safe default.

More writing

• Zebra Code: One thread, one session

The code is at github.com/d5/tengo. Using Tengo, or have a question about it? Email me.

Written by Daniel Kang, who started Tengo in December 2018.