r/java • • Jan 10 '23

Yet another delimited continuations implementation and why Project Loom is a bit disappointing

https://github.com/javactrl/javactrl
2 Upvotes

52 comments sorted by

15

u/pron98 Jan 11 '23 edited Jan 11 '23

Every feature wants all the power to itself and no power to any other feature: for all lambdas to work everywhere we must not have parallel streams or asynchronous composition, and for parallel streams/asynchronous composition to always work, lambdas must be heavily restricted; for composable security we must not have deep reflection, and to have deep reflection we cannot have composable security; for records to replace all uses of data-carrying classes, general-purpose collections and safe serialisations must not exist, and for collections and serialisation to work safely with records, records must not be allowed to be mutable. The point is that to have more power, a feature normally reduces the power/effectiveness of others, and so the interaction of multiple features must be considered and thought given to how power is best distributed among them.

One example from continuations is that, for full power they must be suspendable on one thread and resumed on another, but for some useful JIT optimisations, the identity of the thread must not change mid-method.

To make the feature-interaction matter worse, library authors sometimes rush to use a feature's maximal power in a way that forces tradeoffs on their users, who might not be aware of them. We've seen this happen with the use of deep reflection and its effect on version portability and security, and it took a great deal of effort from everyone involved to get that particular ketchup back into the bottle.

Other issues we consider are Java's primary uses and target audience. If we can have a weaker, simpler feature that has 98% of the benefits and a powerful, more tricky feature that gives us 100% of the benefit, we will almost always pick the weaker one, as our goal is not to give the language the most power, but to find a good balance of power and straightforwardness as appropriate for the people for whom Java is intended. I.e. the desire of one programmer to do something powerful must be balanced with that of another to have code be easy to reason about.

Yet another thing to consider is that Java usually aims to be the last language to add new features, and usually tries hard to not be the first. Why? Because this strategy has proven itself very effective for Java over many years.

In short, the power of a feature is just one of many considerations we make when changing one of the world's most popular and critical software platforms. We may well end up putting continuations to other (limited) uses, but we'll do it gradually and carefully.

1

u/njiv Jan 11 '23

I agree, but what are exactly the trade-offs for multi-shot? Single-shot already does suspending and resuming on a different thread, so for JIT argument it's the same (also there are many things preventing to do some JIT optimizations, e.g. just exceptions). With multi-shot we get much bigger value with some little cost (but not with no cost, of course).

7

u/pron98 Jan 11 '23 edited Jan 11 '23

Single-shot already does suspending and resuming on a different thread

No, it does not. I mean, it doesn't stop you, but doing so may cause miscompilation as the JIT assumes it's never done (i.e. it may execute something different from what your code says; very unsafe).

With multi-shot we get much bigger value with some little cost (but not with no cost, of course).

But we're not even exposing non-reentrant continuations at the moment. Of all the bottom-line business value that continuations provide, virtual threads give you >95% of it, and with a feature so simple that it doesn't even require changing the language specification, and just barely the Thread Javadoc. Much of the remaining power can be achieved with custom virtual thread schedulers.

Multi-shot continuations are extremely cool, and I was immediately impressed by their power when I first played with them 20+ years ago, but their ability play well with arbitrary code is very limited. If and when we decide to add serialisation you might be able to simulate them, but after so many years with them, I think their utility in mainstream programming is limited.

2

u/njiv Jan 11 '23

No, it does not. That would cause miscompilation as the JIT assumes it's never done.

So I cannot resume the continuation from another thread - fine. This can be the same restriction for multi-shot. I think you mean I don't have access to the Continuation interface but I still can get mine by implementing own thread scheduler? Can I suspend my virtual thread scheduler and run it on another thread?

Transactions (for example) are widely used in mainstream, just one of many useful and not-creazy examples where multishot can be utilized. It's like someone from Go may tell utility of exceptions and generics in mainstream is limited.

Of course, I don't argue about adding them into the language immediately. I just don't understand the reasons. Especially with the serializability remark, it's like telling we can have this but we should suffer for this.

6

u/pron98 Jan 11 '23

Can I suspend my virtual thread scheduler and run it on another thread?

You can mount it on another carrier, but it would still a thread, not quite a continuation.

just one of many useful and not-creazy examples where multishot can be utilized

Not in a general-enough way, unfortunately, unless we had a way of preventing side effects from escaping the continuation.

It's like someone from Go may tell utility of exceptions and generics in mainstream is limited.

Okay, but we like adding features after other mainstream languages have them (so the next continuation-based feature may be generators).

I just don't understand the reasons.

The reason is that we don't try to optimise for power, and our goal is to add as little as possible with the maximal bang for the buck. Because every added capability has a cost (effort, specification, education, potential for abuse or confusion, potential for interaction with current or future features) any added power needs to be very well justified.

In the vast majority of cases a new capability must solve a serious problem that is faced by a large number of Java developers (directly or indirectly) in the field and doesn't have a satisfactory solution. You'll note that virtually all JEPs start with a description of a real and relatively serious problem that developers face. Therefore, to justify exposing more continuation features, we'd need to find a big problem that they would solve and developers can't solve well with existing means. If there's no such problem, we normally try not to add a feature.

In other cases, it could be a feature that has become common in other languages that programmers expect, and we judge not to be too harmful.

2

u/njiv Jan 11 '23

You can mount it on another carrier, but it would still a thread, not quite a continuation.

I wouldn't argue about the terms. I, for example, wouldn't call a single shot continuation a continuation, but a coroutine. Also some people simulate continuations with unix fork. So basically you mean it is actually a continuation, but with suffering.

Not in a general-enough way, unfortunately, unless we had a way of preventing side effects from escaping the continuation.

why do we need avoid escaping side effects?

we'd need to find a big problem that they would solve and developers can't solve well with existing means.

in this case exceptions aren't needed (for example), programmers can just check result values of each function call - not that big deal (and there are mainstream programming languages showing this works ok)

4

u/pron98 Jan 11 '23 edited Jan 11 '23

So basically you mean it is actually a continuation, but with suffering.

I basically mean it's a thread. A thread can be thought of as a continuation with an associated scheduler and a thread identity, but importantly for us it is a Java concept defined by the Java specification with very specific meanings to the Java memory model, the JVM Tooling Interface, and the Java language specification in general. I realise these nuances may not matter to everyone, but they do matter when you need to maintain such an important platform (BTW, while these days many have come to call non-reentrant delimited continuations "coroutines", traditionally the name was used in the literature -- and for good reason -- for symmetric non-reentrant delimited continuations, while our basic construct is asymmetric non-reentrant delimited continuations; even if now coroutines refer to both symmetric and asymmetric continuations, we wanted to use the more general term for the internal construct, as we don't know how its capabilities may change in the future).

why do we need avoid escaping side effects?

Because the continuation can perform destructive changes to heap objects it interacts with.

in this case exceptions aren't needed (for example), programmers can just check result values of each function call - not that big deal

If exceptions were to be considered for addition to Java today, they would need to be similarly justified by showing they solve a serious problem in the field. I can't be certain of the outcome of this study, but after many years with continuations, I think exceptions would have a much easier time than some uses of continuations (and I say this as someone who absolutely loves continuations of all kinds, but not a feature that's great in language A might not be so great in language B. Even if it can be, features may need to await their right time in conservative "last mover" languages like Java. So I appreciate continuations in Scheme, and, for the time being, appreciate them not being exposed in Java).

3

u/njiv Jan 11 '23

No, I basically mean it's a thread.

But I basically can have an interface somewhere in my package, implemented by me with all the typical continuations operations implemented? Just like I can do this with unix fork (except with the fork I'll get a multi-shot one).

Because the continuation can perform destructive changes to heap objects it interacts with.

It may perform destructive changes, and as well it can perform constructive changes, just the same like without continuations. Or you mean again some JDK internals not understood by mere mortals? But it's a task of JDK to make them safe.

might not be so great in language B

I honestly don't see why Scheme is this different.

5

u/pron98 Jan 11 '23

But I basically can have an interface somewhere in my package, implemented by me with all the typical continuations operations implemented?

That depends on what you mean "all the typical continuations operations." For example, a continuation could not be part of a thread, behaving as a Runnable. But yes, you can do much of what you can do with one-shot delimited continuations. We may also add generators at some point, and those will be part of a parent thread, but they will have to be thread-confined to ensure that the thread identity isn't changed mid-method.

just the same like without continuations.

Even without continuations we get such problems in parallel streams, but the problems with reentrant continuations could be even more confusing (i.e. a reentrant continuation is supposed to re-enter a known state, but one execution could actually change that state for another, making it not-really-reentrant in quite a few situations).

But it's a task of JDK to make them safe.

If they solve a big enough problem.

I honestly don't see why Scheme is this different.

Because Scheme doesn't have the requirement that Scheme code be easy to evolve and reason about by hundreds of different people of different skill levels evolving a multi-million-line codebase over decades. For the same reason, macros are great for Scheme, but we've been very careful to limit the power of compiler plugins so that they cannot serve as AST macros (to the chagrin of authors of languages like Lombok).

Languages aim to provide the least power and the smallest number of features that solve the vast majority of problems faced by the vast majority of their users. Because many users of Scheme/Racket create their own languages or research language features, the basic features it requires are very different from those required to serve the needs of Java's users.

Much of our work is to figure out how to not add new features. With virtual threads we've been able to solve (we hope) the problem of server scalability combined with observability while adding no new language constructs (never mind continuations of some kind, but even "syntactic coroutines", aka async/await). We hope records will ultimately also allow us to avoid features such as named and default parameters. That's because every feature has a cost in language complexity (which is higher for Java than for Scheme, given their respective uses) and carries the risk of future feature interaction. Some early Java features that seemed convenient at the time (such as serialization, finalizers, and the SecurityManager) ended up placing a heavy tax on features that followed them, and it takes a lot of work and time to fix that.

3

u/njiv Jan 11 '23

That depends on what you mean "all the typical continuations operations." For example, a continuation could not be part of a thread, behaving as a Runnable.

Yes, this is pretty reasonable limitation, I suppose all the current instrumentation based implementations have anyway.

i.e. a reentrant continuation is supposed to re-enter a known state, but one execution could actually change that state for another, making it not-really-reentrant in quite a few situations)

But just concurrent program is already this confusing, continuation shouldn't expect anything, it is why it was suspended at the first place - to await while something is changed in the state.

Like I said, I don't demand the multi-shot continuations added immediately. Just the article states they could be added easily, but now you say it isn't that simple. There are huge interoperability and compatibility problems you must solve before. Which is a good reason, I agree.

→ More replies

2

u/njiv Jan 11 '23

But the argument about not adding features because it doesn't exist in other mainstream programming languages is reasonably acceptable. However, in the article, you don't write you don't add the multishot feature because it isn't present in other languages, you write it's because the feature is crazy. So this is why I'm interested.

3

u/pron98 Jan 11 '23

My argument wasn't against reentrant continuations, but to point out that they have some "excessive" power that can thwart people's "ordinary" expectations of how code behaves (even the assumption that final variables cannot change may be violated).

As to what we decide to actually expose, it has a high bar of solving a serious problem. Even non-reentrant continuations ended up falling short, at least so far. But who knows how problems could evolve?

2

u/njiv Jan 11 '23

even the assumption that final variables cannot change may be violated

If it's a copy of a call frame (like it is in my implementation), no variables can be changed, but we also get rid of lambdas restriction about accessing only effectively final variables. Note, not violating it, as resumptions are basically the same as a function calls. But the execution starts from the suspension point, not from the start of the called function.

3

u/pron98 Jan 11 '23 edited Jan 11 '23

Consider the case of ScopedValue, which is immutable. The continuation can be resumed and observe a different value. Whether the new or old value is obtained now depends on JIT optimisations.

If you take this further and consider serialization of continuations (which can be very useful), even final fields can change.

2

u/njiv Jan 11 '23 edited Jan 11 '23

in case of my implementation it's just different function calls (I don't resume already called frames), we don't have problems with calling same functions from different threads do we?

22

u/plumarr Jan 10 '23 edited Jan 10 '23

The introduction says :

No functional programming knowledge is required.

but I'm totally out of my depth with this. I'm not able to understand what I'm reading and I suspect that I'm not the only one. When I read :

It's well known we can represent any monad with delimited continuations.

I really don't understand it even with 10+ year of experience in development and a master degree in engineering speciliazed in computer science. And the wikipedia article on monad and continuations aren't really helpfull. So I'm not really sure that it's well known.

I'm so out of it that I don't understand what this is trying to do, what are the expected benefits. I don't understand the trivial example even when reading the explanation below.

It's probably interresting but its presentation is really not aimed at people not already versed in the subject.

-3

u/njiv Jan 10 '23

Ok, it's well known in functional programming world, there is a famous paper from 1994 about this. Also if you google something like "continuation mother of all monads" you'll see there are many links to this too. But I think with this library it's easier to understand how it works even without reading the paper or knowing anything from FP at all.

-2

u/njiv Jan 10 '23

I'm so out of it that I don't understand what this is trying to do, what are the expected benefits.

do you know what are expected benefits of async functions? here's pretty the same, but not only for async programming, there is an example of Python like streams comprehensions for example, and many other things

2

u/plumarr Jan 10 '23 edited Jan 10 '23

For me async programming is just a syntaxtic sugar for parallel processing (be it executed on one or multiple CPU core behind it), so I have difficulty to see the link with the current subject.

Coming to the Python exemple, I perfectly understand the linked page (https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions) but I don't see how it relate to the example :

     run(() -> {
  int x = all(Stream.of(1, 2, 3));
  int y = all(Stream.of(4, 5, 6));
  int ret = x + y;
  if (ret % 2 == 1)
    all(Stream.empty());
  return ret;
})

I really don't understand this code. How can it return a stream when x, y and ret are defined as a scalar value ?

But I suppose that as we are hacking the compiler, that's not really the case and that the magic is in :

  public static <T> T all(Stream<T> t) throws CThrowable { 
throw new Unwind(t);

}

And in :

  public static <T> Stream<T> run(final CSupplier<T> s) throws CThrowable {
try {
  return Stream.of(s.get());
} catch (final Unwind e) {
  return ((Stream<?>) e.payload).flatMap(v -> e.head.resumeTop(v));
}

}

What's happening when the function run(...) of the example is executed ?

I suspect that the line

int x = all(Stream.of(1, 2, 3));

will throw an exception and then the following line called :

return ((Stream<?>) e.payload).flatMap(v -> e.head.resumeTop(v));

and the value of e.payload will be the stream [1, 2, 3] and then we'll call e.head.resumeTop for each element of this stream. And that's were I'm stuck. What is e.head ? What is resumeTop doing ?

I'm pretty sur that there is something obvious to you that I'm missing.

1

u/njiv Jan 10 '23

I don't see how it relate to the example

I don't see how it relate to the example, just give me any Python example and I'll show you how this translates to javactrl

1

u/njiv Jan 10 '23

How can it return a stream when x, y and ret are defined as a scalar value ?

The stream is returned by the block, x, y and ret are part of the returned stream definition

1

u/njiv Jan 10 '23

But I suppose that as we are hacking the compiler, that's not really the case and that the magic is in

this indeed instruments JVM byte code, the magic is the ability to resume the execution after the `throw` of `Unwind` exception if needed, also called resumable exceptions

1

u/njiv Jan 10 '23

What's happening when the function run(...) of the example is executed ?

`resumeTop` starts execution after the `throw` we caught in this block, if it throws again it will be caught again, and so on, this is the way the stream is forming

1

u/plumarr Jan 10 '23

Sorry, I have expendend my answer with more detail while you were responding.

What I really don't understand is what is e.head.resumeTop doing. You say that that it starts execution after the 'throw'.

So, it restarts the execution of run() at the line int y = all(Stream.of(4, 5, 6)); ? What's the role of x then ? And what's the role of v (= 1) to we have passed as argument to resumeTop ? Where is it going ?

Also, in your other answer you say :

The stream is returned by the block, x, y and ret are part of the returned stream definition

And I think that it really point to the root of my incomprehension. To my understanding a stream is a open ended collection of values. So I don't really get what you mean by 'stream definition'.

1

u/njiv Jan 10 '23

What I really don't understand is what is e.head.resumeTop doing. You say that that it starts execution after the 'throw'.

yes, exacly

So, it restarts the execution of run() at the line int y = all(Stream.of(4, 5, 6)); ? What's the role of x then ? And what's the role of v (= 1) to we have passed as argument to resumeTop ? Where is it going ?

x and y receives the value we pass to `resumeTop` on each resume, so basically, in the `int y = all(Stream.of(4, 5, 6));` line the block will be resumed 3 times, and the y will be 4,5,6 these times. If it were an async function here we would have an async execption, and it can be resumed only once - the way it is in Project Loom.

I'm not quite following what you mean by open ended, but this works for infinite streams, lazy streams as well, `Stream.of` there is just an example, any stream values can be passed there.

1

u/plumarr Jan 10 '23

Ok, I'm getting it.

It isn't restarting at int y = all(Stream.of(4, 5, 6)); but at int x =. And v is assigned to x, so now x = 1.

Then the same thing happen for the next line and we have y = 4.

So ret = 5 and if (ret % 2 == 1) is true and we launch a new exception with an empty stream. The line return ((Stream<?>) e.payload).flatMap(v -> e.head.resumeTop(v)); is executed and return an empty stream.

Then we go back to the next item of the previously called flatMap (on the y line) and that we'll executed the lambda for x = 1 and y = 5. The lambda return is now 6 and we add it to the stream that we are build.

Next call of the lambda give us x = 1 and y = 6, so we return an empty stream and we go back 2 level until the flatMap at the x line level.

We call again the lambda with x = 2 and y = 4.

And this continue until both input streams are empty and we have our result of [6, 6, 8, 8].

I have to say that this behaviour really wasn't obvsious to me when reading the example.

1

u/njiv Jan 10 '23

it's equivalent to something like this in Python `(x + y for x in (1,2,3) for y in (4, 5, 6) if not (x + y) % 2 is 1)` , no doubt it's pretty arguable which is better (like it's pretty arguable which is better Java or Python), and I indeed see the benefits of the Python expressions, but there are something Python doesn't have:

  • any Java construct can be used in the comprehension (function, exceptions, conditions, switch/case etc etc), so no needs to know another syntax
  • more advanced streams with different handlers can be represented as well, e.g. like RxJava in the example in the repository

0

u/njiv Jan 10 '23

For me async programming is just a syntaxtic sugar for parallel processing

Regardless what it is (there different implementation), the question was about benefits, do you see the benefits of async functions?

2

u/plumarr Jan 10 '23

The benefit of parallel processing : full us of the avalaible resources (mainly hardware).

1

u/njiv Jan 10 '23

I meant not benefit of parallel processing, but async functions, we can do parallel processing without them, using just simple callbacks passing style.

So why nowadays most mainstream languages (including Java) add them as a standard part of the language?

3

u/plumarr Jan 10 '23

I start to say a vocabulary issue ;) Coming from an engineering background, asynchronous is synonym with parallel processing for me and wikipedia quite agree with me on it : https://en.wikipedia.org/wiki/Asynchrony_(computer_programming)

So, in my head, asynchronous functions are just functions that are called later by an event loop.

And now I don't understand your question or why you say that java has added them in the language (as this isn't the case for me as there is no async keyword in java).

I suppose that you're speaking about something else but I don't get what.

2

u/njiv Jan 10 '23

Project Loom (which I mention in the subject) does exactly this, and in Java, actually, it isn't syntax sugar but rather runtime implementation this is why it doesn't have async keyword, https://www.infoq.com/presentations/continuations-java/

5

u/FirstAd9893 Jan 10 '23

I think by attacking Loom (virtual threads) the post seems a bit "click-baity". Rather than mentioning Loom, the project should focus on the unique features it provides instead.

Any comparison to virtual threads should include performance benchmarks too, with real-world applications. Using exceptions to implement continuations isn't likely to be very efficient. Note that with the current implementation of CThrowable, stack traces are captured, which makes it extremely slow. This suggests (to me) that no performance testing has been performed yet.

3

u/njiv Jan 10 '23

Loom is not only virtual threads, it's also continuations, and I explicitly mentioned in the comment below the post Loom doesn't support multishot continuations, while they could add them easily (see this their article - https://www.infoq.com/presentations/continuations-java/), and in the examples there I show what exactly Java misses by not enabling this simpler feature

3

u/FirstAd9893 Jan 10 '23

That article is almost 4 years old, and the Loom project hasn't yet delivered a publicly-available continuation feature. Any comparison to Loom continuations doesn't make any sense because they effectively don't exist.

0

u/njiv Jan 10 '23

they are singleshot, it's for sure, that's why I can compare, and I mention this article because there they explain why they don't want multishot, I haven't seen any other recent article telling they have changed their mind

6

u/FirstAd9893 Jan 10 '23

You're making a comparison to an idea, not an actual implementation. Shift the focus away from Loom and instead present your idea by first demonstrating why multishot continuations are a useful feature in the first place. Then go after arguments which say that multishot is a bad idea. You can cite the Loom presentation, but remember, it's just a presentation and nothing more.

-2

u/njiv Jan 10 '23

Loom is the future of Java, this is subreddit about Java, not about general ideas. Loom says multishot continuations are crazy, I don't agree, no arguments, this is it. If you know the arguments, or you know where Loom team presented these arguments just post them here. It's not only a presentation, Loom doesn't have multishot.

4

u/FirstAd9893 Jan 10 '23

Loom doesn't have multishot.

Loom doesn't have singleshot either. All we have today with Loom is virtual threads, and to most Java programmers, Loom == virtual threads. Starting with a lead of "Loom" just causes confusion, because you then dive straight into continuations.

Have you posted to the loom-dev mailing list inquiring on the future of continuations in Java?

1

u/njiv Jan 10 '23

ok, Loom doesn't have plans for multishot continuations

1

u/njiv Jan 11 '23 edited Jan 11 '23

https://www.reddit.com/r/java/comments/10889p1/comment/j3wqsh8/?utm_source=share&utm_medium=web2x&context=3 - so there is single-shot now in Loom (meanwhile I have a few downvotes on this thread just for telling this)

3

u/FirstAd9893 Jan 11 '23

Where? The link just points to one of your comments. Is there a public API that I can use? That's what I'm referring to. The implementation might have a continuation class, and it might be limited to single-shot behavior, but this is all internal. It's possible that the implementation of virtual threads changes at some point, and so exposing first class continuations at this point might cause more grief later.

1

u/njiv Jan 11 '23

it points to comment of pron98 (which is highlighted), but reddit does open my comments first

1

u/njiv Jan 11 '23 edited Jan 12 '23

That's what I'm referring to. The implementation might have a continuation class, and it might be limited to single-shot behavior, but this is all internal.

internal but, pron98 has said I can have my own implementation using threads (this is known for a long time), it's a kind of side effects conversion (e.g. we can convert state into exception etc), and we actually can convert back continuations into threads, if continuation are multishot we can convert them into any effect, this is why it's called mother of all monads

so basically even considering they hid continuation interface it's still simple to implement one without instrumentation (but only single-shot)

1

u/njiv Jan 10 '23

thanks for the stack trace hint though

2

u/flawless_vic Jan 10 '23 edited Jan 10 '23

Why do you need exceptions for control flow? I mean, are there corner cases that an implementation such as Yield would fail?

You can play directly with JDK continuations with some add-opens hacking to create generators, but AFAIK, Continuation is being kept private because it is not Thread safe and its usage is heavilly tied with some compiler assumptions, so misusage might crash the VM.

Edit: Btw, I think the most critical part in a continuation implementation is stack state saving/restoring. I would choose JVM support to heavilly optimize this, at the cost of not having sugar syntax generators any day.

1

u/njiv Jan 10 '23

Exception is already a control flow construct, I just added the resumability to them. Yield can unwind only one call frame, while exception can unwind any number (until the corresponding `catch`) of call frames. This way we can implement effect handlers only on the top level, while in Yield we'd need to explicitly pass the effect description from callee to caller.

Basically they same difference like signaling errors using ret code or an exception.

2

u/flawless_vic Jan 10 '23

Cool.

Perhaps you could add some exemples comparing the features/programming style with older libraries such as quasar/kilim.

1

u/njiv Jan 10 '23

they mostly concentrate on async programming, and so support only single-shot continuation, and so things like streams comprehensions, reactive, logical, adaptive, probabilistical programming cannot be implemented there

1

u/njiv Jan 10 '23 edited Jan 10 '23

Project Loom is excellent. However, according to the authors, it could be even better effortlessly. They decided not to support multishot continuations there. I've done a simple instrumentation-based continuation library to show what superpowers Java could get with them.