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.