Compilation and the future of sUTL

Part of the sUTL history essay, with current release notes distinguishing shipped behavior from future ideas.

This essay records the history and design direction of sUTL. Since the original reconstruction, sUTL 1.0 and JavaScript, Python and Go packages have been released. Implementation releases from 1.1.0 support step/depth limits and cancellation. Compiler and native-code-generation ideas below remain proposals. See the current reference and sUTL in Everything.

The performance problem

Historical sUTL could become slow when transforms became complicated.

Looking at the old implementations now, this is not mysterious.

They are fundamentally tree-walking interpreters.

During execution they repeatedly inspect the shape of transforms, parse compact path strings, construct small maps for builtin calls, copy scopes, resolve libraries by name, create intermediate arrays and recursively invoke the general evaluator.

A reduce over many items can repeatedly rebuild scope and re-enter the interpreter for the callback transform.

Nested library transforms multiply that cost.

The language itself is not inherently condemned to that performance profile.

A modern implementation should compile.

Compile the program, not the syntax every time

The compiler would lower a transform into an intermediate representation or bytecode, so paths, builtins and library references are resolved once rather than rediscovered on every evaluation.

The source representation should remain MLSNBN.

But execution could look like:

MLSNBN sUTL
    ↓
validate
    ↓
compile
    ↓
internal IR / bytecode
    ↓
execute many times

A transform such as:

{
  "name": "^$.person.name",
  "score": ["&+", "^$.a", "^$.b"]
}

might compile conceptually into:

MAKE_MAP 2
  KEY "name"
    PATH_HEAD SOURCE ["person", "name"]
  KEY "score"
    ADD
      PATH_HEAD SOURCE ["a"]
      PATH_HEAD SOURCE ["b"]

The compiler resolves once what the old interpreter rediscovers on every evaluation.

Paths should be compiled once rather than repeatedly split and interpreted.

A head path such as ^$.person.address.street should walk directly to the first result rather than constructing intermediate lists and taking element zero afterwards.

Wildcard paths can use iterators rather than materializing a new array at every step.

Scope can be represented by cheap frames or slots rather than copied maps.

Library references can be resolved during compilation.

Constant expressions can be folded.

Pure repeated subexpressions can potentially be memoized.

Core library transforms can themselves compile to the same IR, and selected stable operations could eventually be intrinsified where doing so preserves exact semantics.

For static transforms applied to many records, compilation changes the economics dramatically:

receive transform once
        ↓
validate + compile + cache
        ↓
execute against 500,000 records

The cost of understanding the program is paid once.

Native code generation is also plausible

An even more aggressive tier could emit JavaScript and let a modern JIT optimize the result.

A simple compiled sUTL transform might ultimately become code not far from:

function transform(src) {
    return {
        name: src.person?.name ?? null,
        total: src.a + src.b
    };
}

The language's metaprogramming means not every transform can always be statically reduced that far. A program may construct a new transform dynamically and evaluate it.

But even that can be handled with compile-and-cache:

constructed transform
      ↓
canonical hash
      ↓
already compiled?
    ↙       ↘
  yes       no → compile
    ↓
 execute

A sensible implementation could therefore have several tiers:

MLSNBN sUTL
    ↓
compiled IR / bytecode
    ↓
optional generated host code

The important optimization is architectural, not merely rewriting the old interpreter in a faster systems language.

Historical sUTL and a future sUTL

I would keep two projects conceptually separate.

The first is recovered sUTL0.

Its purpose is archaeological: preserve the site, examples, implementations and actual deployed semantics; document disagreements honestly; and make the historical language executable again.

That work should remain conservative.

The second could eventually be a new language version or implementation project whose premise is:

Programs remain MLSNBN.
Evaluation remains pure and deterministic.
The language remains capable of expressing real computation.
Implementations are designed around compilation, metering, validation and generated programs.

It could keep the aspects of sUTL that now seem strongest:

programs, inputs and results share the MLSNBN value model;
ordinary maps and lists retain natural structural meaning;
simple transforms still resemble the result they produce;
transforms are portable values rather than source-code strings;
programs can construct and evaluate programs;
there are no ambient side effects;
external effects are described as values and performed only by a harness.

The implementation could then modernize aggressively underneath those semantics.

A language for moving computation through data systems

When sUTL was first built, "a transformation language for JSON-like data" was a reasonable description.

I now think that description misses the most interesting property.

The world has standardized heavily around MLSNBN-shaped data. HTTP APIs, document databases, message queues, event systems, configuration files and agent tool protocols continually move these structures around.

At the same time, there is increasing value in safely moving small pieces of computation closer to the places where data lives.

Usually those two worlds are separated.

Data is portable and safe but passive.

Programs are expressive but require special transport, execution environments and security boundaries.

sUTL sits in an unusual place between them.

A transform is an ordinary structured value.

It can pass through an API that only knows how to carry data.

It can sit in a database record.

It can be emitted by an agent.

It can be inspected before execution.

It can be hashed, cached and versioned.

Yet when handed to an evaluator it is a real program.

That was already implicit in the original design.

The modern opportunity is to take that property seriously.

Perhaps the best description of the idea is no longer "JSON transformation language" at all.

It is:

sUTL is a pure programming language native to MLSNBN: a way to make structured data computational without turning it into arbitrary host-language code.

That is what bOTL was slowly reaching toward.

It is what Lisp made imaginable.

It is what Python and JavaScript made portable.

And, with agents now routinely generating structured calls and programs being pushed ever closer to data, it may be a more useful idea today than it was in 2015.

Read the essay

From bOTL to sUTL · Portable computation and active data · Compilation and the future of sUTL

Source

Adapted from the sUTL source material.

Back to sUTL · Software & Agents · All topics

View page as JSON