JavaScript async generators oddity

Recently I've found a stackoverflow discussion where a weird feature of JavaScript async generators is mentioned. If the async generator yields a Promise, the generator itself (well, the next() method in the corresponding generator object) will wait for the resolution of the Promise, returning its value.

I mean, this sentence for example:
yield Promise.resolve("AAA");
is replaced by this one:
yield await Promise.resolve("AAA");

This means that in this code below, the try-catch inside the generator will catch the exception:

function asleep(timeout) {
    return new Promise(res => setTimeout(res, timeout));
}

async function* asyncCities(){
    await asleep(1000);
    try {
        yield Promise.reject("rejected City");
    }
    catch (ex) {
        console.log(`Exception: ${ex} caught in the async generator`)
        yield "fixed";
    }
}

async function main() {
    let citiesGenerator = asyncCities();
    try {
        let city = await citiesGenerator.next();
        console.log(`city: ${city.value}`);
    }
    catch (ex){
        console.log(`Exception: ${ex} caught in the main function`)
    }
    //Exception: rejected City caught in the async generator
    //city: fixed
}

main();

This is slightly different from returns in asynchronous functions, where (as we saw in my previous post) if we return a Promise, the wrapping Promise will resolve to the resolution of that inner Promise, but all this is managed by the caller, not by an "invisible await" inside the async function. This means that in the below code the exception will be caught in the main function:

async function getCapital() {
    await asleep(1000);
    // this try-catch here is useless, returning a rejected promise is fine, it's outside when they wayt for it that they will get an exception and will have to handle it
    try {
        return Promise.reject("rejected City");
    }
    catch (ex) {
        console.log(`Exception: ${ex} caught in the async function`)
        return "fixed";
    }    
}

async function main() {
    // an exception happens here, as obviosuly in an async function the "return Promise" was not replaced by a "return await Promise" as it happens with the async generator
    // so the internal try-catch was useless
    try {
        let capital = await getCapital();
        console.log(`capital: ${capital}`);

    }
    catch (ex) {
        console.log(`Exception: ${ex} caught in main function`)
    }
    //Exception: rejected City caught in main function

}

I hardly can think of any situation where this behaviour will cause any gotcha, but it seemed interesting to me to mention it here.

Promise.race and Access to the Resolved Promise

With the JavaScript Promise.race method we obtain the result/exception of the first resolved/rejected Promise. Normally that's all we need, but in some cases we would like to know the Promise itself that caused that resolution or rejection (notice that in Python asyncio.wait we obtain the Futures, not its values/exceptions), so what could we do? The solution for me is creating a "wrapper" Promise that resolves/rejects when the original Promise resolves/rejects. This wrapper Promise will resolve to the original Promise (not to its result). Initially I was thinking of resolving to a tuple with the result and the original Promise, but that's not necessary, as we can get the result by awaiting again the already resolved original Promise.

What we have to bear in mind is that a Promise A does not resolve to another Promise B, it will wait for that Promise B to be resolved to a "normal value", and then Promise A will resolve to that "normal value". I mean:

    let result = await Promise.resolve(Promise.resolve("AA"));
    console.log(result);
	//AA

    async function getMsg() {
        return Promise.resolve("AA");
    }
    result = await getMsg();
    console.log(result);
	//AA

    result = await Promise.resolve("").then(result => Promise.resolve("AA"));
    console.log(result);
	//AA
    
	result = await new Promise(resFn => resFn(Promise.resolve("AA")));
    console.log(result);
	//AA

Because of that, we will resolve the wrapper Promise to an array containing the original Promise, rather than directly to the original Promise. Else, when awaiting for the wrapper Promise we would end up getting the result of the original Promise, rather than the resolved original Promise.
So let's say we have this async getPost function.

async function asleep(timeout) {
    return new Promise(res => setTimeout(res, timeout));
}

const delays = {
    "A1": 1000,
    "B1": 2000,
    "C1": 50,
}

async function getPost(id) {
    console.log(`getting post: ${id}`)
    if (delays[id] === undefined) {
        await asleep(500);
        throw new Error(`Missing post: ${id}`);
    }

    await asleep(delays[id]);
    return `POST: [[${id}]]`;
}

We will launch a bunch of getPost actions, and we want to perform an action each time one of the posts is retrieved. We'll use Promise.race() for that, but we need to know the Promise that got resolved, so that then we can filter it out and invoke Promise.race again with the remaining ones (it's what we typically do in Python with asyncio.wait).

async function runPromises1(postPromises) {
    while (postPromises.length) {
        // Notice how we wrap the Promise in an array. That way we have a Promise that resolves to an Array of a Promise
        // if we had a Promise p1 resolving to a Promise p2, then we would have the thing that p1 would not really resolve until p2 resolves, resolving to its result
        
        // this simple syntax works fine:
        let [pr] = await Promise.race(postPromises.map(p => p.then(result => [p]).catch(ex => [p])));
        try {
			// the "internal" pr Promise is already resolved/rejected at this point
            let result = await pr;
            console.log(`resolved index: ${pr._index}, result: ${result}`);
        }
        catch (ex) {
            console.log(`Error: resolved index: ${pr._index}, exception: ${ex}`);
        }        
        postPromises = postPromises.filter(p => p !== pr);
    }
}

async function main() {
    let postPromises = ["A1", "B1", "C1", "D1"].map(getPost); // (id => getPost(id));
    postPromises.forEach((pr, index) => pr._index = index);
    await runPromises1(postPromises);
}

main();

As you can see, the important thing is this line:
await Promise.race(postPromises.map(p => p.then(result => [p]).catch(ex => [p])))
where the .then and .catch create the new Promise that will resolve/reject to an array containing the original Promise.

Rather than using then-catch we could write the above leveraging async, using an Immediately Invoked Async Arrow Function. An async function returns a new Promise that gets resolved/rejected when the function completes. As in the previous case we have to use the trick of returning the original Promise wrapped in an Array.

async function runPromises2(postPromises) {
    while (postPromises.length) {
        // Notice how we wrap the Promise in an array. That way we have a Promise that resolves to an Array of a Promise
        // if we had a Promise p1 resolving to a Promise p2, then we would have the thing that p1 would not really resolve until p2 resolves 
        
        // this more complex syntax also works fine, it's the same idea as the above
        // we have an Immediatelly Invoked Async Function Expression, it creates a Promise that resolves when the internal promise is resolved, returnig the promise itself (wrapped in an array)
        let [pr] = await Promise.race(postPromises.map(p => (async () => {
            try {
                await p;
            }
            catch {}
            return [p];
        })()));
        try {
            let result = await pr;
            console.log(`resolved index: ${pr._index}, result: ${result}`);
        }
        catch (ex) {
            console.log(`Error: resolved index: ${pr._index}, exception: ${ex}`);
        }        
        postPromises = postPromises.filter(p => p !== pr);
    }
}

This is one of those few cases where using .then().catch() looks cleaner than using async-await. Also, this need of knowing the Promise that has been resolved rather than just its value is not particularly realistic. In most cases we would just need to pass to .race/.wait... not just the getPost Promise, but a Promise for a function that both invokes getPromise and then performs the ensuing "print" action.

Asyncio as_completed

When looking into one colleague's code recently I realised that I was missing the right/simple way to deal with one common asyncio situation. So I have a list of Awaitables (Futures/Tasks) and I want to run some code as soon as any of them completes, and continue to do so until all of them have completed. Given an async function like this that I will be callintg in paralell:

delays = {
    "A1": 2,
    "B1": 1,
    "C1": 0.1,
}

async def get_post(id: str) -> str:
    print(f"getting post: {id}")
    if not id in delays:
        await asyncio.sleep(0.5)
        raise Exception(f"Missing post: {id}")   
     
    await asyncio.sleep(delays[id])
    return f"POST: [[{id}]]"

I was using asyncio.wait in a loop, like this:

async def retrieve_posts():
    post_ids = ["A1", "B1", "C1", "D1"]
    pending_tasks = [asyncio.create_task(get_post(id)) for id in post_ids]
    while len(pending_tasks):
        done_tasks, pending_tasks = await asyncio.wait(pending_tasks, return_when=asyncio.FIRST_COMPLETED)
        for done_task in done_tasks:
            try:
                # at this point, where the done_block is a resolved Future, these 2 sentences are equivalent:
                #block_result = done_task.result()
                post = await done_task
                print(f"post obtained: {post}")
            except Exception as ex:
                print(f"Error retrieving post: {ex}")
                continue

asyncio.run(retrieve_posts())

That works, but my colleage was using a more elegant approach, asyncio.as_completed. as_completed returns an iterator that in each iteration returns a Future (a new one, not one of those that you've passed over to it). That new Future resolves as soon as one of the provided Futures returns. This means that you can rewrite the above like this:

async def retrieve_posts():
    post_ids = ["A1", "B1", "C1", "D1"]
    tasks = [asyncio.create_task(get_post(id)) for id in post_ids]
    for task in asyncio.as_completed(tasks):
        try:
            post = await task
            print(f"post obtained: {post}")
        except BaseException as ex:
            print("Exception getting post: {ex}")
            

asyncio.run(retrieve_posts())	

So asyncio.wait is a better fit when you have some awaitables and as they resolve you'll be launching additional async tasks. asyncio.as_completed should be used when you have beforehand all the awaitables that you're going to run.

Looping over awaitables brings to my mind that python feature, the async for construct (equivalent to JavaScript for-await). I wonder why as_complete returns an iterable-iterator rather than an asynchronous iterable-iterator, but well, we can easily leverage as_completed to create an asynchronous generator, like this:

    async def as_completed_generator(awaitables: list[Awaitable]):
        for aw in asyncio.as_completed(awaitables):
            try:
                res = await aw
                yield res
            except BaseException as ex:
                yield ex

    async def retrieve_posts():
        post_ids = ["A1", "B1", "C1", "D1"]
        tasks = [asyncio.create_task(get_post(id)) for id in post_ids]
        async for post in as_completed_generator(tasks):
            if not isinstance(post, Exception):
                print(f"post retrieved: {post}")
            else:
                print(f"Exception: {post}")	
				

Notice how in order to allow us manage rejected awaitables our async generator yields either values or exceptions.

I'll leverage this post about asyncio to mention something that I did not include in this previous post about Futures vs Futures. The result() method in concurent.futures.Future is a blocking method, that blocks the current thread until a result is available, while the result() method in asyncio.Future is not. It will immediatelly return a value/throw and exception if the Future has been resolved/rejected, or throw an exception (InvalidStateException) if it's still suspended.

Tail Call Optimization

Some days ago one colleage told me that his main complain about Python was the lack of Tail Call Optimization. Indeed Guido was very clear about that, in order to avoid messing the stack traces there will never be (well, don't know if now that he's no longer the BDFL maybe that could change) TCO in Python (in the cPython runtime I guess). Though over the time I have written several posts about how to adapt your code to prevent stack overflows (by using async-await in JavaScript and Python, or by using trampolines), I'd never paid much attention to this Tail Call Optimization thing, so I suddenly got intrigued.

First, I immediatelly associate Tail Call Optimization to Tail Recursive code, but this is not necessarilly so. A Tail Call happens when the last instruction in a function is a call to another function. Callbacks and Continuations come easily to mind. Normally Callbacks and Continuations are not used massively, so optimizing them won't be particularly important, neither in performance terms (improved memory locality) nor in terms of risking a stack overflow, save for functional style programming fully adhering to the CPS (Continuation Passing Style) style. That's why Tail Call Optimization is mainly important for recursive code (though it can be applied to any general Tail Call).

Another important point is distinguishing between direct recursion and mutual or indirect recursion. In direct recursion a function calls itself, in mutual/indirect recursion f1 calls f2 that calls f1 again. Indirect recursion and not recursive tail calls are more complex to optimize than direct recursive tail calls. From the wikipedia article:

The special case of tail-recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. When the language semantics do not explicitly support general tail calls, a compiler can often still optimize sibling calls, or tail calls to functions which take and return the same types as the caller.

However, for language implementations which store function arguments and local variables on a call stack (which is the default implementation for many languages, at least on systems with a hardware stack, such as the x86), implementing generalized tail-call optimization (including mutual tail recursion) presents an issue: if the size of the callee's activation record is different from that of the caller, then additional cleanup or resizing of the stack frame may be required. For these cases, optimizing tail recursion remains trivial, but general tail-call optimization may be harder to implement efficiently.

For example, in the Java virtual machine (JVM), tail-recursive calls can be eliminated (as this reuses the existing call stack), but general tail calls cannot be (as this changes the call stack).[13][14] As a result, functional languages such as Scala that target the JVM can efficiently implement direct tail recursion, but not mutual tail recursion.

Curious about the last statement, I've found this that explains it pretty well.

Have you noticed that the method address starts with 0? That all methods offsets start with 0? JVM doesn't allow one to jump outside a method.

As I've aforementioned, Python does not provide any sort of TCO. We can modify a bit our code writing trampolines ourselves, that will work fine with tail and not tail recursion, direct and mutual recursion. We could also use the async/await trick, but I assume it'll be pretty awful in performance terms. And then, we have several smart people that have come up with some general solutions. There is this decorator that throws (an catches) an exception every 2 recursive calls, so the stack never grows (but I guess it'll hit performance pretty hard). Then this module that seems more ellaborate, and then this one that modifies one function bytecode to use trampolines.

Kotlin has the tailrec modifier that you can use in a function definition and will only work for direct tail recursion. In this article you can see how the Java bytecodes generated by the Kotlin compiler for a tailrec function implement the tail recursion by updating values in the current stack frame and performing a jump to the start of the function (so transforming the recursion into a loop), rather than doing a call.

I've learned from this article that .Net comes with support for tail calls at the bytecode level by means of the tail. instruction. I guess at the CLR bytecode level you are not allowed to write a jump to outside of the current function (same as in the JVM), so this tail function instructs the JIT compiler to compile the ensuing call bytecode into a native jump instruction, rather than creating a new stack frame and doing a native call. . It seems the F# compiler uses that instruction for non recursive tail calls, while transforming recursion into loops for recursive tail calls. The C# compiler does none of them.

The above brings up 2 general points to reflect about for me.
First, when providing Tail Call Optimizations in a VM environment, should the "high level language" to bytecodes compiler perform the optimization, or should that be delegated to the bytecodes to Native code JIT compiler. Well, for VM's on which we use an interpreter and 1 or n JIT's for "hot code" it's clear that that should be done by the "language to bytecodes" compiler. If there's no interpreter involved, just JIT, I'm not sure which one of the two compilers should perfomr optimization.
Second point, should we instruct the compiler about performing the optimization (as we do in Kotlin with tailrec) or should the compiler decide on its own and perform the optimization when he can and sees fit (as the F# compiler seems to do)? I would say I prefer the former approach.

There's this interesting discussion about the above topics appliced to C# and .Net.

Kotlin and "Generators"

In my previos post I mentioned how Kotlin suspendable functions are the basis for asynchronous programming and also for generators-like functionality. In JavaScript, Python and C# we have different constructs-keywords for these 2 things, async-await on one side and yield on the other, so it's interesting to see how Kotlin manages both things through the same suspend construct/keyword.

The equivalent to a JavaScript or Python generator function (a funtion that produces elements as we iterate it) is created in Kotlin by means of the sequence() and yield() functions, like this:

val cities = sequence {
        yield("Paris")
        yield("Lyon")
        yield("Bordeaux")
    }
    
    for (city: String in cities) {
        println(city)
    }

sequence is a function (a Sequence Builder) that receives a "suspendable block" that has as receiver the abstract SequenceScope class, and yield() is a suspendable function of the SequenceScope class. Let me show their signatures:

fun  sequence(
    block: suspend SequenceScope.() -> Unit
): Sequence

abstract suspend fun yield(value: T)

The usage of suspendable functions for providing generators-like functionality seemed surprising to me. The "external interface" of a suspendable function is that you have a function that you invoke once, will get suspended 1 to n times in its suspension points, and finally will return one result to you. With generators what we have is a function that gets involved n times, producing one value each time. So, how can a suspendable function work for this second case? Well, as I explained in my previous post the internal details of a suspendable function is that the function is transformed by the compiler into a state machine, with each suspension point corresponding to one of those states. When the function invokes another suspendable function (suspension point) it returns to the caller a COROUTINE_SUSPENDED value, so that the caller knows that it has been suspended. When the async operation we're waiting is completed the coroutine will resume the suspend function (by invoking its corresponding Continuation). When the suspendable function reaches its end it will return its result, rather than a COROUTINE_SUSPENDED. For our generator like functionality we'll be calling an iterator.next() method. If this iterator invokes the suspendable function and the suspendable function (that in this case does not need of any asynchronous call to produce each of its iteration values) stores the value produced for this iteration "shomewhere" and returns COROUTINE_SUSPENDED, then the iterator can retrieve that value. Then the next call to iterator.next() will resume the suspendable function so that it produces the next value, and so on. So this should work!

I've been digging into Kotlin's source code (SequenceBuilder.kt) to verify that the strategy that I've just described is indeed what Kotlin is doing. The key element is the SequenceBuilderIterator class, that is no more than a SequenceScope, an Iterator and a Continuation. I'll just copy below its definition and main method signatures:

private class SequenceBuilderIterator : SequenceScope(), Iterator, Continuation {
    private var state = State_NotReady
    private var nextValue: T? = null
    private var nextIterator: Iterator? = null
    var nextStep: Continuation? = null

    override fun hasNext(): Boolean {
        ...
    }

    override fun next(): T {
        ...
    }

 
    override suspend fun yield(value: T) {
        ...
    }

    override suspend fun yieldAll(iterator: Iterator) {
        ...
    }

    // Completion continuation implementation
    override fun resumeWith(result: Result) {
       ...
    }

    override val context: CoroutineContext
        get() = EmptyCoroutineContext
}

So when we invoke the sequence() function passing to it a suspendable function/block that uses as receiver a SequenceScope:
- This sequence() creates a SequenceBuilderIterator that stores in its nextStep property a Continuation object for that suspend function (block), that in turn will store a SequenceScope (indeed that SequenceBuilderIterator instance) object in its state.
- It wraps the SequenceBuilderIterator in a Sequence object (which iterator() method will just return that SequenceBuilderIterator)

Then when we want to iterate that Sequence we invoke its iterator() method to obtain the SequenceBuilderIterator instance. Invoking .next() on this iterator will invoke the Continuation for the suspend function/block (referenced from the nextStep property. From this suspending function/block we invoke yield(), that is another suspend function that receives the SequenceScope (our almighty SequenceBuilderIterator) as receiver and that will set in that SequenceBuilderIterator the value to return (in the nextValue property). So the so versatile SequenceBuilderIterator object is what joins everything. It has a next() method for the iteration, that returns the value set in the nextValue property by its yield method, and has another property (nextStep) pointing to the continuation (that wraps the main suspend function).

Notice that the CoroutineContext associated to a SequenceBuilderIterator is an EmptyCorotuineContext. We saw in my previous posts that Continuations have a CoroutineContext that holds a Job and a Dispatcher, but for the Continuation for our "generator-like" functionality, that Job and Dispatcher are not needed at all.

Kotlin Asynchronous Programming

One of the first things I looked into when I started to fiddle with Kotlin was if it had the async-await "magic keywords" and it took me a while to understand that the approach to asynchrous programming in Kotlin is rather different from the strategies followed in JavaScript, Python or C#.

Asynchronous programming in JavaScript revolves around Promises, both if you use the async-await magic or if you go more old-school and explicitely chain Promises. A function marked as async in JavaScript implicitly returns a Promise, and when you await on that Promise the compiler "breaks" the function transforming it into a state-machine so that when that promise is resolved the function is invoked again in the point after the await (the corresponding state in the state-machine). Asynchrony in C# revolves around Tasks, and methods marked as async return a Task. In Python asynchronous programming revolves around awaitables (Tasks, Futures and Coroutine objects) and when a function marked as async (a coroutine function returning a coroutine object) performs a real asynchrouns operation (it gets "suspended"), it will yield a Future to the event loop (the python approach is more confusing to me, but I managed to more or less explain it last year)

In Kotlin the key element in asynchronous programming are suspendable functions (marked with the suspend keyword) and the Continuation Passing Style (CSP) that comes with them. Indeed suspendable functions are a broader concept, as they are also used for the equivalent to generators in JavaScript and Python. As you can guess from its name a suspendable function can be suspended at different points, suspension points, points from where the function is calling other suspendable functions. Once the function invoked from the suspension point completes the caller/calling function will be resumed from that suspension point. Each suspend function is indeed a state machine. Well, this feels like async functions in other languages, but the internals are a bit different. Suspendable functions do not return Promises/Futures... but receive something that at first (wrong) sight seemed like callbacks to me, Continuations. A Continuation contains the function to be invoked, its state (the values of its variables) and the point where the function has to be resumed (state machine), so it's more complex than a simple callback. From this excellent article:

Each suspendable lambda is compiled to a continuation class, with fields representing its local variables, and an integer field for current state in the state machine. Suspension point is where such lambda can suspend: either a suspending function call or suspendCoroutineUninterceptedOrReturn intrinsic call.

So for each suspendable function we have a Continuation class that contains the code of the function, its variables and the point where it has been suspended (the function is made up of a switch-case state machine, so that point is a label for that switch). When a suspendable function f1 invokes another suspendable function f2 it passes over to it its own continuation object. f2 will set in its own continuation a reference to the f1's continuation. This way, once the invoked suspend function f2 completes the continuation for the caller function f1 will be invoked. If in turn f2 invokes another suspendable function f3, this will be added to the chain of continuations: f3 -> f2 -> f1. You can read about this for example here or here

Notice that the way this chain of Continuations is created is like the opposite of what we do in JavaScript (or C#, or Python) when creating a chain of Promises, where when an async function returns a Promise the caller function attaches to the Promise the next function to execute (via .then()

Apart from suspend functions and continuations the other key aspect of asynchrony in Kotlin are coroutines. A chain of suspend function calls runs in a coroutine. A suspend function can only be invoked from another suspend function or from a Coroutine. From here.

A coroutine is an instance of a suspendable computation. It is conceptually similar to a thread, in the sense that it takes a block of code to run that works concurrently with the rest of the code. However, a coroutine is not bound to any particular thread. It may suspend its execution in one thread and resume in another one.

So a coroutine is a "suspendable execution flow", similar to threads or processes, but we don't create coroutines (instances of classes inheriting from the AbstractCoroutine class) directly, we create them through a CoroutineBuilder function. CoroutineBuilders like launch or runBlocking are extension methods of the CoroutineScope interface. The source code for coroutine builders is for sure pretty interesting. We can see there that a coroutine builder creates a CoroutineContext that passes over to the Coroutine constructor and then the builder invokes Coroutine.start().

CoroutineScopes and CoroutineContexts are the other essential pieces of Kotlin asynchrony. They are well explained here, where we can learn that a CoroutineScope holds a CorotuineContext, and that the CoroutineContext is a set of various elements. The main elements are the Job of the coroutine and its Dispatcher. The Dispatcher determines what thread/s will be used for executing the different suspend functions of the coroutine. A Continuation has a reference to its Context. From another article I noted down this: "When resuming, continuations don't invoke their functions directly, but they ask the dispatcher to do it. The Dispatcher is referenced from a CoroutineContext, that is referenced from the Continuation."

Another good article about coroutines is this one

There's an important usage difference that comes from the differences between Promises/Tasks/Futures... and Continuations. In JavaScript when you invoke an async function you have to explicitly state (by means of the await keyword) that you are "suspending" at that point until the Promise is resolved. In Kotlin there's no option to indicate if you want to suspend or not, any invocation to a suspend function means that the caller function will get suspended (if the called one really does something asynchronous). I guess the explanation for this is because you can only pass your continuation to the suspend function at the point of invokation, while with promises you can decide to await for the result just as you obtain the Promise, or await for it later (doing something else in between). The problem with this is that when your suspend function invokes several functions (some "normal" funtions, some suspend functions), you don't know at first sight if it's suspending at those invokations points or not, you have to check if the invoked function is a "normal" or suspend one. In one hand forcing you to use a sort of "await" keyword when invoking a suspend function would be redundant, but on the other hand would make code more clear to me.

What can be a bit confusing is that while Kotlin does not need async-await keywords for writing asynchronous code, it does indeed provide an async() function and an await() function, that you can need in certain cases. async() is a coroutine builder, that contrary to other builders like launch(), returns a Deferred (a sort of Promise/Future) that completes when the corresponding coroutine finishes. In turn, Deferred has an await suspendable method. We can see an example combining both functions here. Related to the previous paragraph, if you want to invoke a suspend function, but not get your current function suspended (as when in JavaScript we invoke an async function but do not await for it at that point) you can wrap the call to the suspend function in a block and pass it to async().

Reading a bit about asynchrony in Raku (that pretty interesting descendent of the honorable Perl language) I've seen that they have Promises also, but they keep() or break() rather than resolve() or reject(). It seemed odd at first sight, but indeed that's what we use in natural language, keeping or breaking promises, not resolving or rejecting.

Truffle vs Invokedynamic

Reading (and writing) about Truffle and graalpy lately has had me thinking (again) about languages and interpreters. When I first heard about Truffle I wrote in the corresponding post:

Indeed, the Java guys spent much time and efforts to adapt the JVM, by means of the Da Vinci project and the new invokedynamic bytecode instruction, to strongly increase its performance with dynamic languages. After doing that, all of a sudden comes Truffle and you can write interpreters for languages that you compile to "self-modifying AST's" (not to Java bytecodes), and those implementations of JavaScript, Ruby... seem to be faster that the implementations that compiled those languages to Java bytecodes and that leveraged that recent and magical invokedynamic instruction!

After that initial astonishement I managed to more or less understand how Truffle, Partial Evaluation and so on work and make code fly. It seems like the future of dynamic languages in the JVM will be based on Truffle rather than invokedynamic. Oracle discontinued Nashorn (Javascript engine based on invokedynamic) while promoting its Truffle equivalent. For Python on the JVM, given that Jython remains stuck in Python 2.7, it's clear that graalpy has no other contender. However, for Ruby we have alive and well both a "traditional" version, JRuby that years ago was updated to leverage invokedynamic, and a Truffle version, TruffleRuby.

In case you wonder if TruffleRuby could be making some use of invokedynamic (in the code of the interpreter methods for the different AST nodes... the answer is NO

- How is this related to invokedynamic?
TruffleRuby doesn't use invokedynamic, as it doesn't emit bytecode. However it does have an optimizing method dispatch mechanism that achieves a similar result.

Already in my post from 2021 I had written something that I had forgotten and that pretty much surprised me at that time:

the "classic" JRuby (that continues to use as far as I know a strange mix of a Ruby interpreter written in Java and a runtime compiler to java bytecodes, that then will be either interpreted or JIT compiled by the JVM)

I tend to forget that interpreters do not need a bytecode stage, they can parse the source into an AST and directly interpret that AST, and indeed this used to be the common behaviour of first interpreters. The CPython interpreter compiles the python sources to bytecodes for a stack based VM (and saves them to a .pyc file) and then interprets those bytecodes (as we saw in my last post graalpy also uses those pyc bytecode files as an intermediate step for building its ASTs. The modern ruby C runtime YARV (that includes both an interpreter and a JIT) also compiles ruby source code to bytecodes for a stack based VM, but the old C runtime, MRI, was just building an AST from the ruby source and direclty interpreting that complex AST (I think this is what is called a pure AST-walking interpreter)

JRuby is a complex beast that is well explained here. It does not use the "YARV ruby bytecode format" or a specific one, it creates an AST from the ruby source and starts to interpret it (AST-walking interpreter). When a method becomes "hot" it will JIT compile it to Java bytecodes that will be run by the Java interpreter, that in turn can decide that this method has become "hot" and compile it to native code (and reoptimize via PGO and so on...).

JRuby’s JIT compiler is similar in nature, the primary difference being the source and destination formats. In Java the source format is Java bytecode, and the destination format is native machine instructions. Conversely, in JRuby, the source format is the JRuby AST, and the destination format is Java bytecode. Perhaps the most fascinating aspect of the JRuby JIT compiler is that it benefits from both the initial compilation into Java bytecode, and then later, when Java may attempt to translate the JRuby-generated bytecode into native machine instructions. So effectively, it is possible to get a double-JIT on your executing code.

That's amazing, you end up with 2 interpreters (for the AST built from the ruby source and for the Java bytecodes) and 2 JITs (for turning the ruby AST into Java bytecodes and for turning those bytecodes into native code, which indeed goese throught the 2 Java JITs: C1 and C2 or C1 and GraalCompiler). Regardless of how cool that looks, it makes pretty good sense to me that RubyTruffle performs better with its more straightforward approach, interpreting the AST, especializing/Partial Evaluation, and JIT compilation to Native code.

What is not clear to me is whether TruffleRuby creates its AST directly from ruby source code or whether it has an intermediate step and leverages YARV bytecodes (or another bytecode format).

As a final note, it's interesting to note that as explained here, Jython goes a different route from JRuby, it does not have an interpreter phase, it directly compiles to Java bytecodes and feeds them to the JVM. This is the same behaviour of IronPython on .Net.

Jython uses an ANTLRv3 generated parser to generate an AST that conforms to the spec for the one you can get from Pythons built in compile function (if you ask for AST Jython will just return after this stage). This is then fed through a custom compiler that uses the ASM Java bytecode generation library to generate Java bytecode that is then loaded and executed. Jython does not (in contrast to JRuby) have an initial interpreted stage, but compiles directly to Java bytecode and lets the JVM handle it from there. Because of this I've never liked it when people describe Jython as a Python interpreter written in Java, I'd much rather call it a Python implementation for Java.

By the way, while reading different sources about all this stuff, I've found a couple of references to a free ebook about interpreters programming. that looks pretty interesting.