12
$\begingroup$

I have recently been making my own programming language and I am finding most concepts easy to understand, however I'm not sure how to implement async/await in my language.

ATM, I'm using C# to create this language and I have no idea how to go about implementing such features.

The language is an interpreted one.

I'm able to implement a JS-like Promise system, but this doesn't help with running asynchronous C# functions, for example sending a HTTP request.

What I have working with such "promise-like" system is this:

var any f = Future.create(|resolve, reject| => resolve(2));
f.then(val => Console.writeLine(val));

It works perfectly within the language, however trying to run async C# functions whilst the entire interpreter does not use async at all I have no idea how to do.

The only options I can think of is

  1. Make every C# function async (like the parser, interpreter, etc.) by default, but I'm not sure if this would help
  2. Use the .GetAwaitor().GetResult() but apparently this shouldn't really be used

I've tried searching and looking everywhere on Google for ways to implement this but I could never find any, so any resources for this topic would be appreciated.

$\endgroup$
2
  • $\begingroup$ I take it you're writing an interpreter? It would help to make this explicit. By the way, welcome to the site! $\endgroup$
    – kaya3
    Commented Dec 21, 2023 at 22:49
  • $\begingroup$ @kaya3 thanks, I've edited my question $\endgroup$ Commented Dec 21, 2023 at 22:51

1 Answer 1

13
$\begingroup$

I'm able to implement a JS-like Promise system, but this doesn't help with running asynchronous C# functions, for example sending a HTTP request.

Async/await is syntax sugar for promises.

You'll need to familiarize yourself with Continuation Passing Style (CPS). Basically, CPS is a way to write regular, sequential ("procedural") code as a chain of callbacks. Ex:

function() {
    let x = foo("a", "b")
    let y = bar("c", "d")
    let z = baz(1, 2, x)
    return y + z
}

converted into CPS is

function(k) {
    foo("a", "b", function(x) {
        bar("c", "d", function(y) {
           baz(1, 2, x, function(z) k(y + z))
        })
    })
}

This is roughly what your interpreter needs to do with async functions before you interpret them. Convert:

async function() {
    let x = await foo("a", "b");
    let y = await bar("c", "d");
    let z = await baz(1, 2, x);
    return y + z;
}

into

function() { return new Promise(resolve => 
    foo("a", "b").then(function(x) {
        bar("c", "d").then(function(y) {
           baz(1, 2, x).then(function(z) resolve(y + z))
        })
    })
}

Specifically:

  • After parsing an async function or other kind of aysnc block, desugar it into a regular function which returns a promise, where all the awaits are replaced with .then and .catch callbacks.
  • If your language supports top-level async, you can parse and desugar the entire source to get one big promise which you then execute. Alternatively, to avoid parsing the entire file at once, you can parse and desugar each individual statement into a promise, waiting to parse the next statement until the promise resolves. Basically, write an async function evalRemaining(int pos), which lexes/parses and desugars the first statement into a promise, then adds a .then callback to that promise which recursively calls evalRemaining with the position right after that statement's end.
  • If your language supports top-level async in a REPL you handle it similarly: read/lex/parse/desugar the current line into a promise, then wait until that promise resolves before asking the user for the next line, by putting the code to do so in the promise callback.

Now, your goal is to desugar a statement or expression with awaits, into a promise expression where the awaits are replaced with .then and .catch callbacks, and the promise resolves into the expression result. This is essentially the same as converting a block of procedural code into a function written in CPS.


There's a lot of existing literature on continuation passing style. You mentioned having trouble finding resources to implement async/await, but if you can rephrase your queries about implementing async/await into implementing CPS conversion, I guarantee you'll find online guides and other resources.

Rule-based async/await (CPS-style) conversion via preorder traversal

Like type-checking, computing the derivative in calculus, and other algorithms, one way to do async/await conversion is to create a fixed set of rules which handle general cases and compose into whatever code you may encounter. Specifically, create a rule for every kind of statement which desugars in a special way, and then to desugar an arbitrary statement, run a preorder traversal, processing each sub-statement or expression with the applicable rule.

Here are some of these rules. If your language has unique semantics, you may need to come up with other rules or modify these rules on your own. There are also be optimized rules for more specific cases which will generate faster / smaller code. Lastly, I didn't check these rules, so there may be bugs:

Async function/block

async function f(...) -> T {
    ...
    <... throw x; ...>
    <... return y; ...>
}

converts into

function f(...) -> Promise<T> {
    return new Promise((resolve, reject) => {
        ...
        <... resolve(x); ...>
        <... reject(y); ...>
        // In case the function doesn't return anything,
        // add this to the end of the Promise or it'll never resolve
        resolve()
    });
}

(e.g. return foo gets converted into resolve(foo), throw bar gets converted into reject(bar), otherwise code is desugared with the following rules and placed into the promise closure).

Async blocks, if your language supports them (like Rust), are similar:

async {
    ...
    result
}

converts into

Promise::new(|resolve| {
    ...
    resolve(result)
})

Desugar from inside out (preorder traversal)

If a statement contains a nested await but it's in an async function or block, desugar the inner async function/block before desugaring the outer one. This also applies to async expressions and other rules.

Statements or expressions without await

A sequence of statements without an await is unchanged.

async function() {
    a;
    while (b) { c; d; }
    try { e; } catch { f; } finally { g; }
}

converts into

function() -> Promise<()> {
    return new Promise(resolve => {
        a;
        while (b) { c; d; }
        try { e; } catch { f; } finally { g; }
        resolve();
    });
}

Expression or expression statement

before;
context <... await expr ...> context;
after;

becomes

before;
expr.then(e => {
    context <... e ...> context;
    after
});

e.g.

let a = foo();
let b = bar(await baz()) * 2;
let c = a + b;

becomes

let a = foo();
baz().then(e => {
   let b = e * 2;
   let c = a + b;
});

If statement

if (cond) {
    then;
} else {
    else;
}
rest;

If either then or else contain an await, the entire if must be converted into a new promise

new Promise(resolveTheIf => {
    if (cond) {
        then.then(resolveTheIf);
    } else {
        else.then(resolveTheIf);
    }
}).then(() => {
    rest;
})

(of course, make sure resolveTheIf doesn't shadow the outer resolve in case then or else contains a return statement).

If cond contains an await, you can convert into the equivalent:

let c = cond;
if (c) {
    then...
} else {
    else...
}
rest...

and then convert from there.

If either then or else does not contain an await, replace then.then(resolveTheIf) or else.then(resolveTheIf) with then; resolveTheIf() or else; resolveTheIf() (respectively).

If your if/else returns an expression like Rust, convert the zero argument call/closure into a one-argument one. Ex:

let foo = if (cond) {
    await then()
} else {
    else()
}
...

converts into

Promise::new(|resolveTheIf| {
    if (cond) {
        then.then(resolveTheIf);
    } else {
        resolveTheIf(else)
    }
}).then(|foo| {
    ...
})

While statement

Similar to the above

while (cond) {
    body;
}
rest;

if body contains an `await, this converts into

const recurse = resolveTheWhile => {
    if (cond) {
        body.then(() => recurse(resolveTheWhile));
    } else {
        resolveTheWhile();
    }
};
new Promise(recurse)

If cond contains an await, you can resolve it before the while block.

Like return and throw when desugaring an async function, break desugars into resolveTheWhile(). If you have nested whiles and allow labeling them, so that users can call break outer from within the inner loop to break the outer one, you have to call resolveTheWhile of outer to break the outer loop.

Switch and for statements

These can be deduced from the if and while statements. I'll show an example of a complicated for statement.

for (let i = await init(); await cond(i); await update(i)) {
    await body;
}
rest;

converts into

init().then(i => {
    const recurse = resolveTheFor => {
        cond(i).then(c => {
            if (c) {
                body.then(() => update(i).then(() => recurse(resolveTheFor)));
            } else {
                resolveTheFor();
            }
        })
    };
}

Try/catch/finally statement

This is similar to the if statement, except that the catch block corresponds to a .catch promise callback.

try {
    tryCode;
} catch (e) {
    catchCode;
} finally {
    finallyCode;
}
...

If either tryCode, catchCode, or finallyCode contain an await, you need to convert the entire statement into a promise.

If tryCode, catchCode, and finallyCode all contain awaits, the entire statement converts into:

new Promise((resolveTheTry, rejectTheTry) => {
    // In general, you should be careful duplicating code when desugaring
    // because it can lead to exponential blowup (imagine what happens if you
    // put finallyCode in the desugared output twice, and then the user writes
    // 32 nested try/finally statements. Language users write that kind of 
    // garbage, then if you're not careful, your interpreter will desugar it
    // into billions or more syntax nodes.
    const finally = (rethrown, e) => {
        finallyCode;
        if (!rethrown) {
            resolveTheTry();
        } else {
            rejectTryTry(e);
        }
    };
    tryCode.then(() => finally(false)).catch(e => {
        catchCode.then(() => finally(false)).catch(e2 => finally(true, e2))
    })
}

If any of tryCode, catchCode, or finallyCode don't contain an await, you can those into new Promise(resolve => { code; resolve() }). There may be optimized variants, but since there are 6 others, I'm not going to compute them all.

A block without a catch case

try {
    tryCode;
} finally {
    finallyCode;
}

converts into

new Promise((resolveTheTry, rejectTheTry) => {
    const finally = (rethrown, e) => {
        finallyCode;
        if (!rethrown) {
            resolveTheTry();
        } else {
            rejectTheTry(e);
        }
    };
    tryCode.then(() => finally(false)).catch(e => finally(true, e))
});

Convert a statement or expression without await into one with await

If necessary, you can convert an expression which doesn't contain await

expr

into one that does

await new Promise(resolve => resolve(expr))

Or a statement

stmt;

into

await new Promise(resolve => { stmt; resolve() });

Out of the above rules, this is only necessary in the try/catch/finally one.

$\endgroup$
6
  • $\begingroup$ Thanks for your reply, I am able to get the promise structure to work (resolve reject, then, catch) etc, but I'm not sure how this would work on the C# backend, as the entire interpreter doesn't use await at all, but if I wanted to run a function such as a http get request, I'm not sure how I'd make this work with the native functions. $\endgroup$ Commented Dec 22, 2023 at 1:46
  • $\begingroup$ I edited my question to show what I have working. $\endgroup$ Commented Dec 22, 2023 at 1:53
  • $\begingroup$ Does the native http request function take a callback or return a promise? If it does, your request wrapper should return a promise object which gets resolved within the callback. If the native function blocks, a non-ideal solution is just to spawn a separate thread or use a thread pool, call the native function, and then call back into the main thread and resolve the promise there. $\endgroup$
    – tarzh
    Commented Dec 22, 2023 at 2:08
  • $\begingroup$ I also don't know how you've implemented promises, and whether you have your own async runner or you are using C#'s. If you made your own async runner (you implemented promises without using C#'s async), then you need to integrate it some way with C#'s async runner to call its async functions, and I'm not quite sure how to do that. $\endgroup$
    – tarzh
    Commented Dec 22, 2023 at 2:19
  • 2
    $\begingroup$ Since you're using C# async native functions, the wrappers to those native functions like http request will be async or return a C# promise (Task). Your inner interpreter needs to be async, but you can wrap it in a function which just calls it and then ContinueAndWait() (since your interpreter is the only promise running, and it contains all the promises generated by your code, you can block on it). Then the parser and REPL don't need to be async, even if you're interpreting code as you parse. $\endgroup$
    – tarzh
    Commented Dec 22, 2023 at 2:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .