F# Computation Expressions expressed as higher-order macros

[LPeter1997]

In a recent discussion F# Computation Expressions came up as a possible similar feature or inspiration for the language. While the feature is powerful, it does not feel like a too coherent one in itself. I think I've found a way to bring in CEs in with not only existing (right now meaning planned) features, but also making them more powerful in the process. Since CEs are kind of a niche feature, I'll try to give an overview of them before anything else. Note that I'm not an F# programmer, so I might make mistakes, I just want the general idea to go through.

What are F# Computation Expressions?

Computation Expressions is a feature that allows modeling various abstractions that span through multiple expressions/statements and changes aspects of certain language elements. According to the official documentation, it can model:

• Non-deterministic computations
• Asynchronous computations
• Effectful computations
• Generative computations

An example asynchronous computation in F#:

let fetchAndDownload url =
    async {
        let! data = downloadData url
        let processedData = processData data
        return processedData
    }

An example sequence:

let squares =
    seq {
        for i in 1..10 do
            yield i * i
    }

They boil down to the exact same feature, with the general syntax:

builder { block }

What happens in the background?

There is really no magic here. All that happens is that some language elements (like let!, return and yield) are transformed into a call to the builder object (in our previous 2 examples this would be async or seq), essentially letting us intercept them. For example the sequence example turns into something like:

let squares = {
    seq.For(1..10, (fun i -> {
        seq.Yield(i * i)
    }))
}

That's all there is to it. The computation expressions just take some of your statements/expressions, and turn them into something else, usually a call to the builder object. The complete list of what turns into what can be found in this section of the docs. For completeness's sake here, are a few examples (assuming our builder is called builder here):

• let a in cexpr -> let a in { cexpr }
• let! a = value in cexpr -> builder.Bind(value, (fun a -> { cexpr }))
• yield expr -> builder.Yield(expr)
• return expr -> builder.Return(expr)

What is this really?

CEs are nothing, but a somewhat limited tool for Aspect Oriented Programming. The feature itself jumps on certain syntax, transforms it slightly to be an interception call to a custom listener object (called a builder here). To make most common operations/structures nicer to write, some extra keywords are introduced (let and let! are different, return, return!, ...), but they just relate to a different syntactical transformation, resulting in a different method call on the builder.

Since this is purely a syntactical feature - there are no semantic rules involved -, we could try turning to an existing feature that happens to work with syntax: macros.

Declarative macros in a bit more depth

I've touched on declarative macros in #16, but now I'd like to illustrate how it could lead us to free Computation Expressions. For this I'll initially use Rust macros, but then will have to use pseudo-notation.

Step 1: Identifying structures

Our first step is to create a macro that can identify what kind of syntactic structure we encountered. This is essentially the mechanism that decides what the found structure needs to be transformed into. Writing a macro that can match all the different control-flow structures is a bit hard with declarative Rust macros because of limitations, so we will only differentiate let-bindings and expressions for now, anything else will be ignored. The macro will insert a print statement before the matched structure, but will not modify the original source in any other way:

macro_rules! identify_structure {
    // A simple let-recognizer
    (let $p:pat = $value:expr) => {
        println!("let binding with name '{}'", stringify!($p));
        let $p = $value;
    };

    // Any expression
    ($e:expr) => {
        // To keep this a balid expression, we use the fact that blocks are completely valid expressions in Rust
        {
            println!("expression '{}'", stringify!($e));
            $e
        }
    };

    // Anything else is just kept as is
    ($i:item) => {
        $i
    };
}

Note: Rust let bindings are a bit more complex than this, but our goal is not to implement a standard compliant Rust grammar recognizer. The macro system sadly doesn't expose enough tools to let us what we want to do.

Now if we try out this code:

fn main() {
    identify_structure!(let foo = 123);
    identify_structure!(if 2 > 1 { println!("2 > 1"); });
    identify_structure!(fn bar() {});
    bar();
}

This will print:

let binding with name 'foo'
expression 'if 2 > 1 { println!("2 > 1"); }'
2 > 1

You might rightfully say that this is not entirely correct, as the right side of a let binding - here it happens to be 123 - is also an expression, why did it not get logged? We can solve this by recursing with the function! Showing the modified let-handling:

    (let $p:pat = $value:expr) => {
        println!("let binding with name '{}'", stringify!($p));
        let $p = identify_structure!($value);
    };

Now the previous program prints:

let binding with name 'foo'
expression '123'
expression 'if 2 > 1 { println!("2 > 1"); }'
2 > 1

This almost solves all our needs. Sadly Rust doesn't give us tools to recurse arbitrarily in a syntax tree in declarative macros, it only allows recognizing a few syntax fragments. This will be the reason we'll have to diverge from declarative Rust macros a bit. I will not write procedural macros, as those are really verbose.

Step 2: Applying a macro to multiple parameters

Applying another macro for multiple arguments is also fairly easy in Rust. For example, we can create an apply! macro that simply applies the macro received as the first parameter to the rest of the parameters. Example:

macro_rules! forall {
    // Match a macro name, a semicolon separator and then an arbitrary amount of statements
    ($mac:ident; $( $s:stmt );*) => {
        // Unpack all matched statements...
        $(
            // Apply the macro
            $mac!($s);
        )*
    };
}

We can combine this with a simple log! macro to log all statements:

macro_rules! log {
    ($s:stmt) => {
        println!("{}", stringify!($s));
        $s;
    };
}

fn main() {
    forall!{
        log;
        let foo = 123;
        if 2 > 1 { println!("2 > 1"); }
    };
}

Output:

let foo = 123;
if 2 > 1 { println!("2 > 1"); }
2 > 1

Step 3: Recursion!

The only thing missing really is the recursion in apply!, to visit each child. This is sadly not doable in Rust declarative macros. To illustrate, it could be something like:

macro_rules! forall {
    // Match a macro name, a semicolon separator and then an arbitrary amount of nodes
    ($mac:ident; $( $n:node );*) => {
        // Unpack all matched nodes...
        $(
            // Apply the macro
            $mac!($n);
            // Recursion for each child, very much pseudocode
            forall!($mac; children!($n));
        )*
    };
}

If this worked, Rust could implement CEs right now!

Proposed feature

I hope it became pretty clear that even Rust declarative macros are almost there to give us a POC mechanism suitable for CEs. I propose that we work on our macro system to make defining CEs completely possible to implement to their full potential. This would mean that CEs wouldn't just be in the language, but could be slightly more powerful - because it would allow syntactic observations - and be a library feature, not a language feature! In my opinion this would be:

• Pretty awesome
• A great indicator that our metaprogramming capabilities are pretty good

Some pseudo-code how we could define our CE macro in a library:

// Recursively transforms the AST using a transformer macro
macro transform(node: AstNode, transformer: macro(AstNode)): AstNode
{
    let transformed = transformer(node);
    return transformed.WithChildren(transformed.Children.Select(c => transform(c, transformer)));
}

// Let's say the user wants to log each let binding, they'd do something like
// Yes, we are essentially writing a higher-order macro and pass in a lambda-macro parameter!
macro logged(node: AstNode) = transform(node, macro(n: AstNode) = match
{
    // Make let statement logged by sequencing a call to print and the let itself
    LetStatement l => new SequenceStatement(
        new CallStatement(/* TODO: Call */),
        l
    ),
    // Don't care
    _ => node,
});

Then we can use logged! like so:

fn main() {
    logged!{
        let a = 3;
        foo();
        let b = 4;
        bar();
    }
}

And the output would be something like:

Assigned 3 to 'a'
Assigned 4 to 'b'

Note: You might have noticed, that my proposed solution falls into an infinite recursive transformation as the LetStatement node will be nested infinitely. This can be solved by making the transformer macro a bit smarter, but I think it still demonstrates the point.

Pretty keywords

There might be a fear that the pretty keywords would be lost (like await, yield, ...) if we decide to roll with this solution. Since many features could be implemented using CEs, there would be no reason for them to be part of the syntax.

We could use the fact that semantic syntax highlighting is a thing! The CE macros simply append metadata that would tell the highlighter to highlight certain keywords in the given block. This has the advantage that only the usable extra keywords will get highlighted, unlike in F#, where all keywords are always highlighted, even if the given CE doesn't allow them.