All You Need are Coroutines and Pattern Matching


Abstract

The average programmer just wants to write code [citation needed]. Language designers, on the other hand, want to write code, that is, programming languages. Ever since the first lisp interpreter sputtered through it's first s-exp, there's been a quest to build a 'perfect' programming language. However, except for those in the Sect of the Golden Hammer, many people consider language design to be an 'open' field, at least in the sense that it's always possible to build a better language - because no matter how hard you try, there is no language that won't make you clarify your ideas.

In this work we present a language that can be bootstrapped from coroutines and mono-variadic lambdas, with types defined by structure rather than by name. Additionally, we show how a simple safe-yet-rich macro system can be built to leverage code clarity and convenience.

What is a Coroutine?

Some of you might already be familiar with coroutines. In essence, a coroutine is a function call executed in a separate light-weight self-contained process that can pass data back-and-forth with the process that called it.

I'd like to say more, but all y'all are smart, and I'm sure you've heard of them before - Think Python's generators or Lua's coroutines.

Pattern Matching

Pattern Matching is matching a data-structure against a pattern to extract specific data. Most of the time, a pattern can be thought of as a mirror version of the data-structure it's extracting the data from. For example, the pattern:

(x, (a, b))

would successfully match against the data-structure:

(1, (2, 3))

and produce the bindings:

x = 1
a = 2
b = 3

Additionally, patterns can have guards which check specific conditions. Guards should be read as 'where' in most cases, for example, the pattern:

x | x > 0

Will match any value x where x is greater than 0. If a match fails, either due to poorly structured data, or a failed guard check, an error will be returned.

A few More Things

Pattern matching is useless unless the data extracted can be used. A lambda, matches a pattern and maps the bindings to resulting code (an expression), which is run in a new coroutine. A lambda is defined as follows:

<pattern> -> <expression>

and are called by:

<lambda> <expression>

Each lambda takes only one argument, and can yield or return at most one item. Luckily, through the use of algebraic datatypes (tuples, etc.) and pattern matching, this is not much of a problem.

By default, lambdas are anonymous. To attach a name to a value (as lambdas are values), assignment is used. Assignment is similar to a lambda expression, in the sense that it matches a pattern and binds variables. however rather then executing the code in a new coroutine, the bound values become available in the current scope. Here's what an assignment looks like:

<pattern> = <expression>

For example, binding decrement to a lambda:

decrement = x -> x - 1

And calling it on 13:

decrement 13

Would give us 12. If a lambda needs to evaluate some list of operations in sequence, a block is used. A block is a list of expressions contained between curly braces separated by commas or newlines. A block may also contain a return statement, which halts the current coroutine and immediately returns a value. Otherwise, the value of the last expression evaluated is returned.

For example:

linear = (m, x, b) -> {
    proportional = m * x
    return proportional + b
    -- alternatively emit `return`
    -- as this is the last statement in the block
}

Conditionals

An if-statement is a feature common in many languages, though our language doesn't even have those (yet). To get started with some conditional logic, we'll start off with a simplified version of an if-statement. If an condition is truthy, we evaluate some other expression, otherwise, we do nothing. Our if statement will be used as follows.

if true {
    1 + 1
}

In this case, the answer would be 2. We're going to implement if first as a lambda, and then as a macro. There is some syntactic sugar at play in the above example, which will become clear shortly. Anyway, the lambda version of if will take a tuple of two arguments:

We'll call the unsugared lambda definition of if 'iffer'.

iffer (true, () -> {1 + 1})

is the same as the above if, sans syntax.

Before we write the definition of iffer, we need to establish a few things about how coroutines work in this language.

First off, yield. The yield function, when called inside a coroutine, suspends the coroutine and then returns some value. When the coroutine is called with some more values, the yield function evaluates to those values, and is no longer suspended. For example, consider:

foo = () -> {
    print "Start"
    x = yield "Yielding"
    print x
    print "End"
}

x = foo ()
-- prints "Start"
print (x "Resume")
-- prints "Resume"
-- prints "End"
-- prints "Yielding"

The reason yielding is printed last is because yield "Yielding" sets the value of the call (x "Resume") to "Yielding", which is only printed after the coroutine finishes.

The second key thing is try. try will evaluate a new coroutine. However, if it fails, instead of propagating the error up the call stack, try will return the error as a value. If the coroutine succeeds, the value will be returned as normal. with this in mind, here is a naive implementation of iffer:

iffer = (condition, then) -> {
    do_or_fail = c | c is not false -> then ()
    try (do_or_fail condition)
    return ()
}

Here's the break-down. As mentioned before, iffer is a function that takes two arguments. do_or_fail will only execute then if c is not false, because trying to evaluate do_or_fail where c is false will throw an error, which is caught by try. Finally, we return an empty tuple because I don't want to return the value of try.

Great! Now that we have the definition for iffer, let's write the macro if. if transforms an if expression into an iffer function call:

if = cond do ~> iffer (cond, () -> do)

Macros are made using a squiggly-arrow, ~>. The arguments aren't a pattern, they actually follow a small expressive templating language which we'll delve into deeper later. Anyway, the only thing we really do in this macro is hide the fact that the body after the if is actually a null-ary function.

For now, let's see this if in action:

coroutines = "cool"

if (coroutines == "cool") {
    print "Heck yeah!"
}

Obviously, "Heck yeah!" would be printed in this case.

Loops and Generators


Building a Match Statement

In many languages, such thing as a match statement exists. This statement matches a value against a variety of patterns, and returns the value fo the first one it matches.

This might look something like:

match x {
    true  -> 1
    false -> 0
}

We're going to implement match first as a function, and then as a macro. the function will take a tuple of two arguments:

So, the above will be written as:

matcher (x, [true -> 1, false -> 0])

We're using the name matcher for this function to avoid confusion with the match macro we'll implement later on. Here's how we might start a naive definition for matcher:

matcher = (value, mappings) -> {
    for value in mappings {
        result = try (mappings value)
        if result is not Error {
            return result
        }
    }
    error "Nothing was matched!"
}

Continue?

An adventure awaits...

Keep exploring!

If it's been a long day, there's nothing wrong with giving up and going home.

Note

I'm usually pretty permissive with what I create. However, my writing is my writing and my opinions are my own. Although this website's source code is released under the MIT License, all published content is © Isaac Clayton.