Designing Our DSL

I love programming languages, so designing a domain-specific language (DSL) to describe our image manipulation pipelines seemed obvious. Before beginning with implementation, we have to figure out what our DSL and its type system will be.

Syntax and Semantics

An important step of implementing a programming language is parsing, which takes a string and converts into an abstract representation of the program called an abstract syntax tree (AST). There’s a lot of interesting things that can be done with parsing, but we want to keep things simple, so we’ll be making a Lisp dialect.

While many languages copy the syntax of C, Lisp dialects look very different. Everything is an expression, so we might write if-then-else as (ite x y z), where if x is true, then it evaluates to y, otherwise it evaluates to z.

For each technique we implement, we’ll add a corresponding primitive to our DSL. For example, uniform white noise might just take an integer seed: (uniform 1234).

Let’s consider what kind of values we might be dealing with, to get an idea of what our type system will have to handle.

What we’ll see

Primitive values

We’ll need common primitive values, like integers, floating-point numbers and booleans.

Images

Images are our main focus, so we want to be especially precise with them.

Formats

First, images could be grayscale, RGB, HSL, etc. We will treat each format as a distinct type and use explicit casts to convert between them. We might add a tool that automatically inserts casts into the program to resolve typechecking errors, but we will leave that for later.

Sizes

Next, some techniques, such as Perlin noise are defined as functions that can be sampled at any coordinates. They effectively represent infinite textures, allowing for operations that depend on neighbors, without having to specify special behavior for handling boundaries.

There might also be techniques that depend on textures having a equal width and height.

Therefore, we’ll want our image type to be parameterized over its dimensions, allowing integers as well as infinity.

Non-2D signals

Procedural noise algorithms can be many dimensions and we might want to support this. For example 4D noise can be used to generate tileable 2D noise.

Similar to images, these can also be infinite or finite, so we’d want dimensions as well.

Therefore, we will have support signals of multiple dimensions, each tagged with a finite size or infinity, where it can contain a vector with the appropriate channels.

Future possibilities

In the future, we might want coordinates, first-class functions, or other types of arguments. We’ll leave figuring those out for later.

Type System

We’ll allow types Int, Float, Bool, Signal[...], and <FORMAT>[...], where Signal takes in a list of dimension sizes (inf or a value of type Int) and <FORMAT> is RGB or HSL. (We’ll add more formats later.)

While we won’t currently allow first-class functions, our primitives will have function types. We will type them, as if they could be curried, in case we decide to add it later. Note that we’ll allow output types to depend on arguments and argument types.

To make this clearer, consider an upscale operator. It could be of type (mult: int) -> signal[n_1, n_2, ..., n_m] -> signal[mult * n_1, mult * n_2, ..., mult * n_m]. Here, mult is the first argument, yet appears in the return type.

A program in our DSL will be a single expression and will not allow one to define functions. This should simplify typechecking, since all values will be constants or the result of an operator applied to constants. We might revisit this and formalize the type system depending on how complex things get.

Summary

We outlined the design of a Domain-Specific Language (DSL) tailored for image processing and procedural noise generation. We will be making a Lisp dialect to simplify the syntax. For the type system, we’ll support signals with parameterized dimensions and channels, where RGB images are 2D signals with 3 channels. We’ll also allow output type’s arguments to depend on input arguments and their type parameters.