Method References

I've been recently reading about method references in Java, particularly interested in whether invokedynamic is also used with them (as it happens with lambdas). The answer is yes and as you can read in that document the main difference is that for lambdas the Java compiler needs to "desugar" the lambda into a private method, which is obviously unnecessary for method references.

When the compiler encounters a lambda expression, it first lowers (desugars) the lambda body into a method whose argument list and return type match that of the lambda expression, possibly with some additional arguments (for values captured from the lexical scope, if any.) At the point at which the lambda expression would be captured, it generates an invokedynamic call site, which, when invoked, returns an instance of the functional interface to which the lambda is being converted. This call site is called the lambda factory for a given lambda. The dynamic arguments to the lambda factory are the values captured from the lexical scope. The bootstrap method of the lambda factory is a standardized method in the Java language runtime library, called the lambda metafactory. The static bootstrap arguments capture information known about the lambda at compile time (the functional interface to which it will be converted, a method handle for the desugared lambda body, information about whether the SAM type is serializable, etc.)

Method references are treated the same way as lambda expressions, except that most method references do not need to be desugared into a new method; we can simply load a constant method handle for the referenced method and pass that to the metafactory.

This other article gives a deeply interesting explanation of how lambdas and invokedynamic works.

Regarding method references (do not confuse them with the related, low level Method Handles), this article explains them pretty well. As I expected you can get a method reference to an instance method that gets its "this" value ("receiver object" in the article) bound to that instance, and you can get method references to static methods. The not so obvious thing is that you can get references to instance methods that are not bound to a "this" value ("References to unbound non-static methods" in the article). They'll use as "this/receiver object" the first parameter received when being invoked. That's pretty nice, as you can reuse the same method reference object with different receivers.

This has made me think about how delegates work in .Net, I could remember that we have something very similar, about which I wrote in one of my first posts. We call that Open Instance Delegates, but their creation is rather less friendly than in Java, so they remain as a not particularly well known feature. As a reminder:

MethodInfo mInf = typeof(Person).GetMethod("DoSomethingInstance");
  Func openDelegate = (Func)(Delegate.CreateDelegate(typeof(Func), mInf));
  //now let's call our Open Delegate with different instances of Person
  Console.WriteLine(openDelegate(p1,"formatting: ", 3));
  Console.WriteLine(openDelegate(new Person(){Name = "Xurde"},"formatting: ", 4));
  Console.WriteLine(openDelegate(new Person(){Name = "Nel"},"formatting: ", 2));

Another nice feature of Java Method references is that we can have references to constructors, using this syntax: ClassName::new. This is not possible in C#, I think because the CLR does not allow binding delegates to ConstructorInfo objects, only to MethodInfo objects. This is not a big deal, because we can just create a lambda that invokes the constructor: () => MyConstructor(), but anyway, it's nice that Java allows to directly reference the constructor.

In my old post I've seen that C# delegates provide also Close Static Delegates, that is a delegate pointing to a static method and where the delegate Target ("this") is bound to a value that will be passed as the first parameter to the static method. I still can not see much use for this, but well, just another feature.

Coroutine Sample

From time to time some Computer Science concept comes to my mind and keeps me busy reflecting about it. Recently I disserted about Promises vs Futures, now I've been thinking about what a coroutine really is. In principle for me a coroutine was a function that could return multiple times, getting suspended on each return and continuing from that point in the next invocation. You get this construct in languges like C#, JavaScript and Python when using await or yield.

Well, we can say that I was on the right track, but that the thing is a bit more complex. Reading here and there, with A Curious Course on Coroutines and Concurrency being a real eye opener, I find that there's a difference between generators and coroutines. Generators are functions that contain yield statements and use them to produce (generate) a sequence of results rather than a single result, to create iterables/iterators. A coroutine also contains yield statements, but uses them not (or not only) for producing values, but to consume values. C# lacks this feature, but in Python and JavaScript we can send values to a generator function (that becomes a coroutine then) by means of .send(value) or .next(value).

Long time ago I posted about how this could be used to simulate the async/await magic, but other than that (or the complex collaborative multitasking cases, using trampolines and so on), it's not easy for me to think of particularly interesting use cases for "simple" coroutines. The grep example in the above mentioned pdf could be rewritten with just a closure for example. Well, in the end I have come up with what I think is a good use case.

I'm going to invoke from "A" a method in ObjectB multiple times, passing different values, but these values that we have in "A" should be "enriched-updated" before sending, and this update follows a sequencial logic. I can put that logic in a coroutine, that I place between A and ObjectB. In my Example ObjectB is a User with a method haveMeal. "A" is the "feeding" logic that prepares the meals, but rather than sending them directly to ObjectB.haveMeal, it will send them to a coroutine that adds medication (morning, lunch or dinner ones) to that meal, and will then send that "enriched meal" to ObjectB.

The coroutine looks like this

import { User } from "./User.js";
import { Meal } from "./Meal.js";

let user = new User("Francoise");

//coroutine that consumes meals, adds medicines to them and sends them to a user
function* medicinesAdderFn(user){
    while (true){
        let medsGroups = [["morning pill"], ["afternoon pill"], ["dinner pill"]];
        for (let meds of medsGroups){
            let meal = yield null;
            meal.addMedicines(meds);
            user.haveMeal(meal);         
        }

        // let meal = yield null;
        // meal.addMedicines(["morning pill"])
        // user.haveMeal(meal);

        // meal = yield null;
        // meal.addMedicines(["afternoon pill"]);
        // user.haveMeal(meal);

        // meal = yield null;
        // meal.addMedicines(["dinner pill"])
        // user.haveMeal(meal);

    }
}

let meals = [
    new Meal("breakfast", ["croissant", "compota"], null, ["coffee", "water"]),
    new Meal("lunch", ["soup", "beans"], ["flan"], ["water"]),
    new Meal("dinner", ["pure", "cookies"], null, ["ekko", "water"]),
    new Meal("breakfast", ["pain au chocolat", "compota"], null, ["coffee", "water"]),
    new Meal("lunch", ["soup", "pasta"], ["riz au lait"], ["water"]),
    new Meal("dinner", ["omelet", "magdalenes"], null, ["ekko", "water"])
];

let medicinesAdder = medicinesAdderFn(user);


//initial call to "prime" the generator (runs the generator until executing the first yield)
medicinesAdder.next();
//normal calls to the generator providing values
for (let meal of meals){
    medicinesAdder.next(meal);    
}

And you can see the full sample here

Use await to avoid Stack Overflows

In my last post I mentioned that I should revisit my posts [1] and [2] about avoiding stack overflows. Well' I've done so and I've realised that while the technique that I describe there (using a timeout to exit the current call and then enter the next "recursion") makes sense in a pre-async/await world, but we can use a much more simple approach based on async-await. This technique that I'm going to show now is valid both for tail and not tail recursions

First let's see the code. I can transform these recursive functions (that in node, that lacks of Tail Call Optimizations, would crash when used with a large number

function factorial(n) {
	//return (n !== 0) ? n * factorial(n - 1) : 1;
	if(n === 0 || n === 1){
		return 1;
	}
	else{
		return n * factorial(n-1);
	}
}

function tailFactorial(n, total = 1) {
	if (n === 0) {
		return total;
	}    
	else{
		// proper tail call
		return tailFactorial(n - 1, n * total);
	}
}

Into these, that will not overflow the stack, cause basically we are no longer recursivelly stacking new frames in the stack, the await keyword is sort of avoiding the recursion

async function factorialWithAwait(n) {
	if(n === 0 || n === 1){
		return 1;
	}
	else{
		await "nothing";
		return (n * await factorialWithAwait(n-1));
	}
}


async function tailFactorialWithAwait(n, total = 1, resFn){
	if (n === 0){
		return total;
	}
	else{
		//this await prevents the stack overflow as we are exiting the function before the recursive call!
		await "nothing";
		//if we comment the await above, we'll get the stack overflows, cause this await here is AFTER the recursive call, so we continue to stack them up!
		return await tailFactorialWithAwait(n-1, n * total);
	}
}

This works thanks to how the eventloop and the microtask queue work in JavaScript.

To put it more simply, when a promise is ready, its .then/catch/finally handlers are put into the queue; they are not executed yet. When the JavaScript engine becomes free from the current code, it takes a task from the queue and executes it.

That means that adding an "await 'nothing'" in our code will cause that when JavaScript comes across this await for an already resolved value, it will add the ".then part" (that is what comes after the await) to the microtask queue, and will exit the current function (so releasing the current stack frame). Then it will take the task from the microtask queue and execute it.

As usual I've uploaded the code to a gist

From Recursion to Trampolines

I've recently come across one more piece of Groovy beauty. Closures (the objects used to represent a block of code), have multiple methods, the "usual suspects" (like memoize, curry...) and also so cool stuff like trampoline.

Trampolines are a technique used to adapt a tail recursive function into an iterative one, just by turning the recursive call into a function (usually called thunk) that is returned and will be used in a loop. Well, this article in JavaScript explains it pretty good.

All the articles I've seen use trampolines for Tail recursion (this is necessary as most languages do not implement Tail Call Optimizations), but what if we have a recursive function that peforms additional actions (post actions) after the recursive call? Last year I wrote 2 posts ([1] and [2]) about preventing stack overflows in recursive functions, both for tail and non tail recursion. The technique that I use there (and that probably I'll revisit in short) had nothing to do with trampolines, but the way I saved "post actions" for executing them after the recursive calls, helped me find a technique for using trampolines with not Tail recursion

In each call to the "recursive function adapted for trampoline iteration", apart from returning a function with the next "pseudo recursive call" I return a function with the post action, that I stack up and will execute after the recursion. Well, I better copy here the code:

let st = "helloworld";

//normal recursive (non tail recursion) function
function recursiveTransformString (source){
    if (source.length === 0)
        return "";
    if (source.length === 1)
        return source.toUpperCase() + source;

    
    let curItem = source[0];
    let transformed = recursiveTransformString(source.substring(1));
    return curItem.toUpperCase() + transformed + curItem;
}

console.log(recursiveTransformString(st));
//HELLOWORLDdlrowolleh

//the above function adapted to be used in a trampoline
function transformStringAdaptedForTrampoline (source){
    if (source.length === 0)
        return [""];
    if (source.length === 1)
        return [source.toUpperCase() + source];
    
    let curItem = source[0];
    let nextRecursion = () => transformStringAdaptedForTrampoline(source.substring(1));
    let postAction = (result) => curItem.toUpperCase() + result + curItem;
    return [undefined, nextRecursion, postAction];
}

//trampoline factory
function createTrampolineWithPostAction(fn){
    return (...args) => {
        let postActions = [];
        let [result, nextRecursion, postAction] = fn(...args);
        while (result === undefined){
            postActions.push(postAction);
            [result, nextRecursion, postAction] = nextRecursion();
        }

        while(postActions.length){
            result = postActions.pop()(result);
        }
        return result;
    }
}

let trampolined = createTrampolineWithPostAction(transformStringAdaptedForTrampoline);

console.log(trampolined(st));
//HELLOWORLDdlrowolleh

As usual I've uploaded the code to a gist

For further reading, this article is another good read about trampolines.

Linux Process Memory Consumption

Properly understanding the memory consumption of a process is quite an endeavor. For Windows I've given up. Over the years I've gone through different articles and discussions about the WorkingSet, Private Bytes and so on... and I've not managed to get a full understanding. In Linux things seem to make quite more sense.

I have several recent posts that could join this current one in a sort of "Understanding Memory series". This one about the whole Memory consumption in your system, this about the available physical memory, and this one where among other things I talk about the Virtual Address Space.

I'm going to talk now about the physical memory consumed by a specific process and about "shared things". With the top command we see 3 memory values: VIRT, RES and SHR. VIRT is the virtual address space, so as I explained in previous articles it has nothing to do with physical memory and normally it's not something we should care about. RES is the important one, it's the physical memory used by the process, and it's the same value that we see with the ps v pid command under the RSS column.

Well, things are not so simple. Processes share resources among them. I can think of 2 main ones: SO's (shared objects/shared libraries, that is, Linux equivalent to dll's) and the code segment between different instances of the same process. From what I can read here and here, the memory taken by a SO will be included in the RSS value of each process using that library (though it's taking, at least for most part of the SO, physical memory only once). The same goes for the code segment space, for each instance of the same process the RSS value will include the code segment space, though it's loaded only once in physical memory. This means that if you add up the RSS value of all the processes in your system it will give you a far bigger value than the real physical memory consumption that is provided by free -m.

RSS is the Resident Set Size and is used to show how much memory is allocated to that process and is in RAM. It does not include memory that is swapped out. It does include memory from shared libraries as long as the pages from those libraries are actually in memory. It does include all stack and heap memory.

Remember that code segment pages are shared among all of the currently running instances of the program. If 26 ksh processes are running, only one copy of any given page of the ksh executable program would be in memory, but the ps command would report that code segment size as part of the RSS of each instance of the ksh program.

When a process forks, both the parent and the child will show with the same RSS. However linux employs copy-on-write so that both processes are really using the same memory. Only when one of the processes modifies the memory will it actually be duplicated. This will cause the free number to be smaller than the top RSS sum.

There's an additional point to take into account, Shared Memory. Contrary to what you could think, when talking about "Shared Memory" in linux systems we are not talking about shared libraries, but about a different concept, memory reserved by shmget or mmap. Honestly I know almost nothing about it, I'm just telling what I've read here and here

"shared libraries" != "shared memory". shared memory is stuff like shmget or mmap. The wording around memory stuff is very tricky. Using the wrong word in the wrong place can totally screw up the meaning of a sentence

This Shared Memory is the SHR value on top's output. All processes sharing a block of shared memory will have it counted under their SHR value (but not under RSS).

The RSS value doesn't include shared memory. Because shared memory isn't owned by any one process, top doesn't include it in RSS.

Truffle Interpreters

In my previos post about Graal VM I mentioned that maybe I would write an additional post about Truffle. This is how I summarized in that post what Truffle is supposed to be:

The Truffle Language Implementation Framework. It allows "easily" writing programming languages implementations as interpreters (written in Java) for self-modifying Abstract Syntax Trees (what?!). It has allowed the creation of very efficient Ruby, Python and JavaScript implementations to run in the GraalVM. As these implementations are written in Java you can run them on a standard JVM, but they'll be slow, as it's the GraalVM JIT compiler who allows these implementations to run efficiently, so that's why Truffle is so linked to GraalVM. This is a really good (and thick) read.

This idea of writing high performance interpreters seems odd to me. I know very little about compilers, interpreters and VM's, but it seems to go against the last decades of common Computer Science knowledge. 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! Indeed, Oracle has discontinued Nashorn (that was developed along with the invokedynamic-Da Vinci thing and that compiled JavaScript to Java bytecodes containing invokedynamic), and replaced it with Graal.js, that is based on Truffle.

Truffle is intended to run with the GraalVM Compiler, so OK, as this is an optimized JIT, your interpreter, written in Java and compiled to bytecodes, will end up compiled into a very optimized machine code thanks to all the optimizations that this cool JIT will do overtime, but anyway, we are optimizing an interpreter... and there can not be such a difference between the GraalVM Compiler and the Hotspot JIT to allow for this big change that Truffle seems to mean.

Well, I think I've finally understood what's the magic with Truffle. This article has been quite esential (and this other one has also helped). First we have that the AST that gets constructed for the program that you are interpreting will evolve (based on runtime profiling) from dynamically typed nodes into statically typed nodes. And then comes the real magic, the Partial Evaluation technique. Your interpreter code (the java bytecodes, not the code being interpreted) that was written to work with any types, will be especialized to work with the types being used in these executions. This is the Futamura projections, your interpreter gets specialized to run a specific source code!

So in the end your interpreter will ask Graal to compile to native code especialized versions of the different classes that make up the interpreter. From one of the articles:

Partial evaluation is a very interesting topic in theoretical computer science – see the Wikipedia article on Futamura projections for some pretty mind-bending ideas. But for our case, it means compiling specific instances of a class, as opposed to the entire class, with aggressive optimizations, mainly inlining, constant folding and dead code elimination.

All the above seems terribly complex (and magic) to me, and at some point I still wonder if I'm really understanding it correctly. The Truffle-Ruby documentation here has a couple of paragraphs that seem to confirm that my understanding is correct.

The Truffle framework gets the bytecode representation of all of the AST interpreter methods involved in running your Ruby method, combines them into something like a single Java method, optimizes them together, and emits a single machine code function.

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.

Same as Ruby has now 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) and the new Truffle interpreter, it would be interesting to see if other languages plan a similar move. For the moment Groovy has no plans for that. After the performance improvements they reached when moving from callsite caching to indy (invokedynamic), they don't seem to see any reason to create a Groovy Truffle interpreter. Bear in mind also that as with all Java code, they are getting additional performance improvements "for free", just by running with the GraalVM JIT rather than the C2 Hotspot JIT.

Groovy Types, AsType

It was such a long time ago that I expressed my profound admiration for Groovy. At that time I was impressed by its metaprogramming capabilites, recently I've been delighted by what a beautiful platform for DSL's it provides (Jenkins pipelines...), and lately it's its approach to Types that has caught my attention.

The dynamic vs static typing, and strong vs weak vs duck typing debate can be a bit confusing. I talked about it long in the past. Groovy's approach to type checking is pretty interesting, and this article is an excellent reference. In the last years it has gained support for static type checking (checks done at compile time) by means of the @TypeChecked and @CompileStatic annotation, but I'm not much interested on it. What's really appealing to me is that when working in the "dynamic mindset", its Optional typing approach allows us to move between dynamic typing and duck typing. When you declare types for variables or method/function parameters, Groovy will do that type check a runtime, but if you don't declare the type, it will be declared as Object, but no type checks will be applied, and the Groovy invokation magic (callsite caching in the past, invokedynamic in modern versions) will give you a duck typing behaviour. It will try to find a method with the given name, will try to invoke it, and if it works, it works :-)

All this thinking about type systems reminded me of my discovery of structural typing via TypeScrit time ago, and made me wonder if when using type declarations Groovy would support structural typing at runtime (I mean, rather than checking if an object has an specific type, checking if the "shapes" match, that is, the expected type and the real type has the same methods). The answer is No, (but a bit).

In other words, Groovy does not define structural typing. It is however possible to make an instance of an object implement an interface at runtime, using the as coercion operator.

You can see that there are two distinct objects: one is the source object, a DefaultGreeter instance, which does not implement the interface. The other is an instance of Greeter that delegates to the coerced object.

This thing of the "as operator" (AsType method) and the creation of a new object that delegates calls to the original object... sounds like a Proxy, n'est ce pas? So I've been investigating a bit more, and yes, Groovy dynamically creates a proxy class for you (and an instance of that proxy). Thanks to the proxy you'll go through the runtime type checks, and then it will try to invoke the requested method in the original object, and if it can not find it you'll get a runtime error.

import java.lang.reflect.*;

interface Formatter{
    String applySimpleFormat(String txt);
    String applyDoubleFormat(String txt);
}

class SimpleFormatter implements Formatter {
    private String wrap1;
    private String wrap2;
    
    SimpleFormatter(String w1, String w2){
        this.wrap1 = w1;
        this.wrap2 = w2;
    }

    String applySimpleFormat(String txt){
        return wrap1 + txt + wrap1;
    }

    String applyDoubleFormat(String txt){
        return wrap2 + wrap1 + txt + wrap1 + wrap2;
    }
}

class TextModifier{
    String applySimpleFormat(String txt){
        return "---" + txt + "---";
    }
}

def void formatAndPrint(String txt, Formatter formatter){
    System.out.println(formatter.applySimpleFormat(txt));
}

def formatter1 = new SimpleFormatter("+", "*");
formatAndPrint("bonjour", formatter1);

def modifier = new TextModifier();
try{
    formatAndPrint("bonjour", modifier); //exception
}
catch (ex){
    //runtime exception, when invoking the function it checks if modifier is an instance of Formatter
     println("- Exception 1: " + ex.getMessage());
}    

Formatter formatter2;
try{
    formatter2 = modifier;
}
catch (ex){
    //runtime exception, it tries to do a cast
// Cannot cast object 'TextModifier@1fdf1c5' with class 'TextModifier' to class 'Formatter'
    println("- Exception 2: " + ex.getMessage());
}   


formatter2 = modifier.asType(Formatter); //same as: modifier as Formatter;

//this works fine thanks to the Proxy created by asType
formatAndPrint("bonjour", formatter2); 

println "formatter2.class: " + formatter2.getClass().name;
//TextModifier1_groovyProxy

//but it is not a java.lang.reflect.Proxy
println ("isProxyClass: " + Proxy.isProxyClass(formatter2.class));

As you can see in the code above, Groovy creates a "TextModifier1_groovyProxy" class, but it does so through a mechanism other than java.lang.reflect.Proxy, as the Proxy.isProxyClass check returns false.

I'll leverage this post to mention another interesting, recent feature regarding types in a dynamic language. Python type hints and mypy. You can add type declarations to your python code (type hints), but they have no effect at runtime, nothing is checked by the interpreter, your code remains as dynamic and duck typed as always, the type hints work just as a sort of documentation. However, you can run a static type checker like mypy on your source code to simulate compile time static typing. This is in a sense similar to what you do with TypeScript, only that you are not transpiling from one language (TypeScript) to another (javascript), you are only doing the type checking part.