Introducing Dawn (Part 1)

By Scott J Maddox.

First published 2021-04-08.

Allow me to introduce you to Dawn, a work-in-progress programming language. I am designing Dawn to be a practical, general-purpose programming language that combines the factorability of Forth, the purity and expressiveness of Haskell, and the performance and control of C, with safety and correctness guarantees beyond those provided by Rust. Now, if you’re at all familiar with these languages, then just from reading that sentence you might have an inkling that I’m either a crackpot or painfully naive. If you did, then I applaud your skepticism. Nonetheless, I believe I have glimpsed a path to this seemingly impossible confluence of properties, and in this series of blog posts I hope to share at least a part of that vision with you.

In order to properly motivate the choices made in Dawn, we’ll talk about each of these four languages, how they achieve these remarkable properties, and how we can leverage their strengths and temper their weaknesses, starting with Forth.

Forth is a remarkably small and simple programming language in which functions are defined as a sequence of operations on a stack. In Forth, function parameters are not given names. Instead, parameters are implicitly passed via the stack. This results in highly factorable and refactorable code, since functions can be trivially split and recombined along any syntactic boundary. According to Chuck Moore, Forth’s original designer, this factorability is the defining characteristic of Forth:

Forth is highly factored code. I don’t know anything else to say, except that Forth is definitions. If you have a lot of small definitions, you are writing Forth. In order to write a lot of small definitions, you have to have a stack.

Another, more general, way to describe such a programming language is to say it is concatenative. Concatenative programming languages are closely related to combinatory logic, which is further closely related to the APL family of programming languages. The common thread among all of these is the concept of “point-free” or “tacit” programming, in which functions are defined entirely as the composition of other functions.

Unfortunately, this style of programming has historically come with a few disadvantages. First, the strict ordering of values on the Forth stack necessitates some minimum amount of stack shuffling, which can be tedious and error prone and obscure the meaning of programs. Second (and related), as anyone who has tried to understand someone else’s Forth or APL code can attest, the lack of parameter and value names can lead to what is often called “write-only code”—that is, code that is prohibitively difficult to read and understand. Finally, concatenative and tacit programming languages have historically, almost universally, been weakly or dynamically typed, which, in some respects, limits their refactorability when compared to strong statically typed languages.

Most of these advantages and disadvantages are well described by Jon Purdy in his 2012 blog post titled “Why Concatenative Programming Matters”, which I highly recommend stopping to read right now, before you continue reading below. In the section titled “The Dark Side”, Jon gives an example of translating the following function, given in traditional mathematical notation,

f(x, y, z) = y² + x² − |y|

into an equivalent function in concatenative notation:

f => drop dup dup × swap abs rot3 dup × swap − +

For anyone familiar with traditional mathematical notation, the meaning of the first definition will immediately be quite clear. In contrast, even to someone extremely familiar with the meaning of each of the terms in the concatenative definition, the overall meaning of the definition is obscured by the presence of various stack shuffling terms, namely drop, dup, swap, and rot3. The situation is significantly improved by refactoring the concatenative notation to use a newly defined square function and the higher-order functions bi and dip:

square => dup ×
f => drop [square] [abs] bi − [square] dip +

But, the underlying meaning is still not as immediately clear as it is for the traditional mathematical notation.

Upon recognizing this distinct and persistent disadvantage to concatenative notation, many concatenative programming language designers, such as Slava Pestov, the designer of Factor, and Jon Purdy, the designer of Kitten, decided to include an escape hatch—a way to bind values to local named variables. Unfortunately, this breaks one of the primary advantages of concatenative notation: that functions can be trivially split and recombined at any syntactic boundary—i.e. their factorability.

In Dawn, I have taken a novel approach that retains factorability. Rather than avoiding stack shuffling by assigning values to local named variables, a Dawn programmer may make use of an arbitrary number of arbitrarily named stacks. In Dawn, the function f(x, y, z) = y² + x² − |y| might be defined like this:

{fn square => clone mul}
{fn f => {spread $x $y $z} {$z drop}
    {$y clone square pop} {$x square pop} add {$y abs pop} sub
}

Let’s break this down.

First, the definition of square is quite straightforward. It clones the value on the top of the current stack and then multiplies the top two values, leaving their product on top of the current stack. This is the same as the definition square => dup ×, given above, just with clone instead of dup and mul instead of ×.

Next, the definition of f is composed of the following 7 sub-expressions:

1. {spread $x $y $z} is syntactic sugar¹ that takes the top 3 values from the current stack (the stack from which f was called) and spreads them to the stacks $x, $y, and $z, respectively, with the top-most (right-most) value going to $z.
2. {$z drop} drops the value from the top of the $z stack. That value is then permanently gone. (It’s passed on! It is no more! It has ceased to be!)
3. {$y clone square pop} clones the value at the top of the $y stack, squares it, and then pops the square off the $y stack onto the current stack.
4. {$x square pop} squares the value at the top of the $x stack and then pops the square off of the $x stack onto the current stack.
5. add takes the top two values from the current stack, adds them together, and leaves the sum on top of the current stack.
6. {$y abs pop} takes the remaining value from the top of the $y stack, takes the absolute value of it, and then pops the absolute value off the $y stack onto the current stack.
7. sub takes the top two values from the current stack, subtracts the right-most from the left-most, and leaves the difference on top of the current stack.

While this Dawn translation is certainly more verbose than the traditional mathematical notation, I hope you can see (now that I have explained what each term means) that it is a fairly direct syntactic translation, and that the overall meaning is nearly as clear as it is for the traditional mathematical notation. The additional verbosity in the Dawn translation is due, in large part, to all functions in Dawn being linear, in the sense of linear logic—that is, every value is used exactly once. In order to simulate using a value less than or more than once, the combinators drop and clone must be used, which increases verbosity. However, as we’ll see later, when we talk about Haskell, C, and Rust, the inherent linearity of concatenative notation is another major motivation for making Dawn a concatenative programming language—the price paid in increased verbosity in this example is more than made up for by the dividends of performance, control and reduced verbosity in other examples.

Furthermore, though it may not be immediately obvious, this function definition can be trivially split and recombined at any valid syntactic boundary. To be clear, it would not be valid to start with {$y clone square pop} {$x square pop} and extract square pop} {$x square into a helper function. It is not valid to split nested curly brace pairs. However, you could easily refactor {$y clone square pop} {$x square pop} into {$y clone} {$y square} $y-> {$x square} $x-> (where $y-> and $x-> are syntactic sugar for {$y pop} and {$x pop}), and then it would be perfectly valid to extract {$y square} $y-> {$x square} into a helper function.

In Dawn, there are no local variables to hoist out or rename—there are only functions that operate on named stacks. Conceptually, these named stacks can be considered to be different parts of one big multi-stack. In Forth, functions are defined as a sequence of operations on a stack… except for the functions with side effects, such as setting a global variable or performing input or output. In Dawn, every function is defined as a sequence of operations on a multi-stack. There are no exceptions.

In the next post, we will talk about Haskell and see how it’s possible for there to be no exceptions to this rule—that is, how Dawn, like Haskell, is a purely functional language, and why you should care. We’ll also see how we can further enhance the refactorability of Dawn beyond that of (the vast majority of) existing concatenative programming languages through strong, static, inferred types. And finally, we’ll begin to see why the inherent linearity of concatenative notation is well worth the cost of occasionally increased verbosity.

Discuss this post on Hacker News or Lobsters.