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.

Graalpy

A couple of years ago I wrote about my fascination with GraalVM and the Truffle Interpreters framework, but somehow I got the impression that the different truffle implementations (for Ruby, for Python...) would end up mainly as an amazing intellectual achievement but with litte real use save for a few Java applications wanting to get some scripting power or to have access to python AI-science libraries. I think was pretty wrong. I've recently looked into the truffle python implementation, graalpy, and the project is really alive and well (same as truffle ruby). Graalpy provides a python3.10 implementation that you can use as a replacement of the standard CPython implementation as long as it's only using the standard library modules or external modules written in pure python. If your application uses external extension modules, you'll have to look into the compability table.

They claim that graalpy can run certain applications up to 3 or 4 times faster than CPython, which is amazing. I'm not going to enter into that discussion, I just want to review how graalpy works.

So graalpy is a python interpreter built with the truffle framework. That means that (as you can read in my aforementioned post) indeed it's not just an interpreter, but an interpreter (written in Java) and a high performance JIT (the graalVM compiler). When graalpy executes a python souce file it compiles (as CPython does) that file to a .pyc file, containing python bytecodes. Then the graal interpreter creates an AST for those python bytecodes and interprets them. Overtime, we have the especialization/partial evaluation of the interpreter code (Java bytecodes) that interprets that AST, that is sent to the Graal Compiler to generate high performance native code. Then you go through all the crazy optimizations and deoptimizations that the ultra-smart people that build these amazing JIT's have developed. Et voilá, you have a high performance interpreter!

That's more or less what I had managed to understand 2 years ago, but graalpy comes with an extra, it makes good use of the Native Image technology. First, we have to bear in mind that the Graal JIT compiler, that is written in Java, can be compiled to native code. From here

There are two operating modes of the Graal compiler when used as the HotSpot JIT compiler: as pre-compiled machine code (“libgraal”), or as dynamically executed Java bytecode (“jargraal”).

libgraal: the Graal compiler is compiled ahead-of-time into a native shared library. In this operating mode, the shared library is loaded by the HotSpot VM. The compiler uses memory separate from the HotSpot heap. It runs fast from the start since it does not need to warm up. This is the default and recommended mode of operation.

jargraal: the Graal compiler goes through the same warm-up phase that the rest of the Java application does. That is, it is first interpreted before its hot methods are compiled. This mode is selected with the -XX:-UseJVMCINativeLibrary command line option.

That's pretty interesting. As we know the Graal compiler can be used not just as a JIT compiler, but also as an AOT compiler, and it's written in Java. For using it as JIT in your JVM process you'll import it as a library, either as native library (.so, .dll...) or as a Java jar. For importing it as a native library you'll have to previously compile it AOT. If used as Java jar, it will be first interpreted and then (for its hot methods) JIT compiled by the other JIT compiler, the less optimized C1. From here:

The primary benefit of libgraal is that compilations are fast from the start. This is because the compiler is running compiled from the get-go, by-passing the HotSpot interpreter altogether. Furthermore, it’s compiled by itself. By contrast, jargraal is compiled by C1. The result is that the compiled code of the compiler is more optimized with libgraal than with jargraal.

When you download graalpy (a .tar.gz that you just uncompress and that's all, no installation process as such) you can choose between a native version and a "normal" java version. The native version does not only mean using the native libgraal that I've previously mentioned, but that the java code for the truffle interpreter (and all the java standard libraries it depends on) has been compiled to native code. From here:

You can download GraalPy as a standalone distribution for Oracle GraalVM or GraalVM Community Edition. There are two standalone types to choose from:

Native Standalone: This contains a Native Image compiled launcher
JVM Standalone: This contains Python in the JVM configuration

If you want to use graalpy as a drop-in replacement for cpython to see if you get better performance, you want the Native Standalone version, as explained in this interesting quick reference:

The native runtime is most compatible with CPython. It runs as an ahead-of-time compiled Python launcher, which starts up faster and uses less memory.

The JVM runtime can interoperate with Java and other GraalVM languages can be added to it. You can identify it by the -jvm suffix in its name.

After installing (just unzipping the tar.gz) that "Native Standalone" version on Ubuntu, you mainly have the launcher app (graalpy), a folder with the python3.10 python modules, and a massive 350 MBs libpythonvm.so shared library, that I guesss contains the SubstrateVM and the result of compiling to native code the Java code of the Truffle interpreter and of all the Java Standard library packages used by the interpreter.

And now comes the big question. If Truffle power comes from optimizing with the Graal JIT the Java bytecodes of especialized parts of the interpreter, and now we are using a version where that interpreter has already been AOT compiled to Native code... does this make any sense? Well, others have gone through the same doubts, and there's a very interesting explanation in stackoverflow.

- Question
My understanding is that AOT compilation with native-image will result in methods compiled to native code that are run in the special-purpose SubstrateVM. Also, that the Truffle framework relies on dynamically gathered profiling information to determine which trees of nodes to partially evaluate. And that PE works by taking the JVM bytecode of the nodes in question and analyzing it with the help of the Graal JIT compiler. And here's where I'm confused. If we pass a Truffle interpreter through native-image, the code for each node's methods will be native code. How can PE proceed, then? In fact, is Graal even available in SubstrateVM?

- Answer
Besides the native code of the interpreter, Substrate VM also stores in the image a representation of the interpreter (a group of methods that conform the interpreter) for partial evaluation. The format of this representation is not JVM bytecodes, but the graphs already parsed into Graal IR form. PE runs on these graphs producing even smaller, optimized graphs which are then fed to the Graal compiler, so yes SVM ships the Graal compiler as well in the native image. Why the Graal graphs and not the bytecodes? Bytecodes were used in the past, but storing the graphs directly saves the (bytecodes to Graal IR) parsing step.

As I've said, that answer is really, really interesting. I thought that the Substrate VM used in Native Image applications provided little more than memory management (the JVM memory model) and Garbage Collection, but at least in this case it also includes the Graal Compiler. Additionally you can invoke the Graal Compiler (through the JVM Compiler Interface - JVMCI) passing over not just Java bytecodes, but directly Graal IR graphs.

Out of excitement I was thinking that graalpy would also bring an end to that huge CPython problem, the GIL (Global Interpreter Lock). Unfortunately that's not the case so far. Some of the graalpy guys have taken part in the discussions about the diffeent approaches to removing the GIL from CPython, and have explained that so far they also use a GIL, mainly to avoid problems with C-Extensions. It's quite a pity, seen that in the ruby world, while the current main ruby interpreter YARV (sort of the equivalent to CPython) built in C also has a GIL, Truffle Ruby has got rid of it.

On several occasions while checking some "academic" stuff about Truffle interpreters (not just graalpy) I've seen some references to PyPy (a python implementation using a JIT), comparing its Tracing JIT approach to the Partial Evaluation approach taken by Truffle. It seems now that the guys from graalpy and PyPy are working together on HPy a better API for C-extensions for python.

Python Lambdas to the Limit

The limited support for lambdas in python (the body of a lambda must be a single expression) is something that felt really painful to me when I went back into python programming last year. Overtime I've realised that this is not so horrible, as this limitation forces you to use a local function (that if) declared with a meaningful name, that can make your code more clear than using a relativelly long lambda declared in place. Anyway, I continue to find this limitation annoying, as in many cases I would prefer to use a lambda than a local function

It's important to make clear that the lambda limitation is not about having just a single line. You can have a lambda with multiple lines, as long as those lines make up an expression. What you can not have in a lambda is statements (not even one).

Related to this, I've recently come across a trick that allows us to overcome this limitation in many use cases. We can declare the body of our lambda as a sequence or a list with expressions as items. That sequence/list is an expression with nested expressions (its items). I mean, this is perfectly valid:

f1 = lambda x: (
    print(f"{x} received"),
    x+2
)

OK, that's good, but a normal use case involves assigning values to variables in the lambda and doing something with those variables. Assigning a value to a variable is a statement... well, not necessarily, as in python we have Assignment Expressions (aka walrus operator)! Add to the mix Conditional Expressions (aka ternary operator), and we are pretty well covered. We can write things like this:

fn = lambda x, y: (
    print("started"),
    x := x.upper(),
    y := y.upper(),
    print(f"result: {x} - {y}")
)

fn("aaa", "bbb")
#started
#result: AAA - BBB

Notice that the lambda returns the expression that makes up its body, so in these cases it's returning the sequence (with the different evaluated expressions), e.g. (None, 'AAA', 'BBB', None). That's fine in cases like the above where we are not interested in the return, but in the common case where the lambda is intended to "calculate" something and return it (that would be the last expression in the sequence), we'll have to invoke the lambda and access to its last item, I mean: my_fn("a", "b")[-1] which reads a bit strange. To avoid this, we can write a factory function (I'll call it "multi" for "multi-lambda") that wraps the lambda in a function that takes care of invoking it and returning the last value. I mean:

def multi(fn: Callable) -> Callable:
    return lambda *args: fn(*args)[-1]
    

That we can use in a rather complete example like this:

cities = ["Paris", "Xixon"]

cities2 = map(multi(lambda x: (
    print(f"formatting: {x}"),
    y := x.upper() if x.startswith("P") else x.lower(),
    f"||{x}-{y}||"
)), cities)

print(list(cities2))

#formatting: Paris
#formatting: Xixon
#['||Paris-PARIS||', '||Xixon-xixon||']

  

I would have not thought we could write code like this in python!

I can't close this post without mentioning coconut python, a functional superset of python that among many other cool features comes with (multi) statement lambdas.

JavaScript LazyProperty and Lookup

In my previous post I talked about lazy/cached properties in Python. We can use similar techniques in JavaScript, as explained here and here. The second post leverages decorators, available only in (very) recent versions.

I have nothing to add to those articles, and this post is indeed about the basis: properties lookup and getters-setters. While in python we call attributes to the fields in one object, in JavaScript we call them properties. Each property has a Property Descriptor object associated to it, that defines the behaviour of the property. We have 2 types of descriptors (which means that we have 2 types of properties), data descriptors (that correspond with a normal data field in other languages) and accessor descriptors (that correspond with getters/setters in other languages).

I have not found any complete reference about property look-up in JavaScript, so what I'll write below is based on experience and some recent tests. Notice that accessor descriptors in JavaScript correspond to Python descriptors, but as we saw last week Python differentiates between Data and Non-Data Descriptors (depending on the combination of __get__, __set__, __delete__ that they feature).

When looking up a property in an object JavaScript will check first in that object, and if not there it'll check in its prototype chain. When getting the property there's no extra logic. However, when setting it, it's a bit more complex.
- If the property exists in the object, it's used/updated.
- If the property does not exist in the object:
--- if it exists in the prototype chain:
------ if what it finds in the prototype chain is an accessor it'll use that accessor. This means that if the accessor has a set(), it'll use that setter, but if it has no set() it'll do nothing.
------ If the property exists in the prototype chain as a data property, it'll set it in the object, not in the prototype.
--- if it does not exist in the prototype chain it'll set it in the instance

Let's see some code:

class Book {
    constructor(name) {
        this.name = name;
    }

    get isbn() {
        console.log("isbn property getter");
        return `${this.name}-ISBN`;
    }
}

So my Book class has an isbn getter property (it's defined in the class, so it's in Book.prototype, reachable from a Book instance through the prototype chain), that automatically "calculates" the isbn, but let's say that for a specific instace I want to set a particular value. This will do nothing:

// this line has no effect, no crash, but it will set nothing
// as the getter only was defined in the class, not in the instance, trying to set the value in the instance does nothing
console.log("- try to set it to aaaa")
b1.isbn = "aaaa";
console.log(b1.isbn);
// Atomka-ISBN

I have to define a property in the instance (I'll just use a data property) using Object.defineProperty

// I have to do it like this:
console.log("- define isbn property in the instance and set to 'aaaa'")
Object.defineProperty(b1, "isbn", {
    value: "aaaa",
    writable: true,
    enumerable: true,
    configurable: true,
  });
console.log(b1.isbn);
//aaaaa

Now that the property exists in the instance, trying to set it again will work fine, as it will just use the data property in the instance, and not the accessor property in the prototype chain:

//now that it's been set in the instance I can update it
console.log("- update it to 'bbbb'")
b1.isbn = "bbbb"
console.log(b1.isbn);

An now an example of how getting a data property from an object will search it in the prototype chain if it's not directly in the object, but setting it will set it in the object.

Book.prototype.canBeRead = true
let b1 = new Book("Atomka");

console.log(`b1 can be read: ${b1.canBeRead}`); //it gets it from the prototype chain
// true

b1.canBeRead = false;
console.log(`b1 can be read: ${b1.canBeRead}`); //but it sets it in the instance
// false

b2 = new Book("Ange Rouge")
console.log(`b2 can be read: ${b2.canBeRead}`); //it remains as true in the prototype chain
// true

Additionally, notice that the delete operator only works in direct properties (own properties) of an object, it does not go through the prototype chain at all.