Long rant on Erlang-style Actors: Lost Dimension

This post is follow up to my previous post about programming languages. If we apply the conceptual framework that was discussed in the post we will see that modern event-driven programs designed in OO paradigm (but not necessary in OO-language) has the following dimensions of analysis and discourse.

  1. Steps (statements)
  2. Work/evaluation (blocks/composite/statements/functions/procedures)
  3. Processes (objects, methods, events)

IMHO component-based programming adds additional dimension: intentional/technical. But since this dimension is much more subtle and not universally accepted, I leave it out of this discussion.

Every piece of the code in modern OO-applications could be reasoned in the terms of these dimensions. It could be noted, that these dimensions of discourse are not independent. Each new dimension differentiate and integrates the previous one. And we could see dimensions were developed sequentially in mainstream languages:

  1. Steps: FORTRAN, BASIC (line-based)
  2. Steps+Work: Pascal, Algol, C
  3. Steps+Work+Processes: C++, Java, ...

And modern mainstream OO-languages like Java even enforce this classification making every procedure or function belonging to some object or class. This raises some objections from functional programmers, but these objections are objected by OO programmers, that feel more comfortable when no code is left unclassified from point of view of these three dimensions.

The transitions between level 1 and level 1*2 was well documented in the essay “Go to considered harmful”. I would suggest to refresh line of reasoning used in that essay, since I would use the same line of reasoning later. I do not know the essay with similar clarity that discusses transition between 1*2 and 1*2*3.

The classical functional languages are much more tricky thing to classify. Firstly they try to suppress the first level Steps calling them non-pure, and then they introduce the first class functions, that clearly add to the process dimension of the program. So the primary focus of functional languages is level 2 with suppressed but leaking level 1 and half done level 3. The functional programming does add new “effects” dimension of discourse, but this dimension is somewhat underdeveloped, since some points on it are considered “better” then other. It is possible to write event-driven process-based programs in functional languages, it just less obvious since there less of language support.

Note that all of the above is directly describing the synchronous case. When things got to asynchronous case, the same dimensions can be applied. And here we will the same problems.

The step in the synchronous case was, modifying or reading program state, and going to the next statement to execute (either textually next, or jump). Work and processes based this step notions. Lets now consider how these dimensions map on asynchronous case:

  1. Step: In asynchronous case the step is receiving event, modifying state, and sending events.
  2. Work: The work dimension would be notion of block that has single point of entry (by events) and has a single exit (producing event). Then asynchronous blocks could be parametrised as asynchronous procedures and composed using asynchronous operators.
  3. Process: The process based decomposition is quite obvious, it is a component that has state and receives and sends events.

Note that the classical actor model provides only two of these dimensions: 1*3. There is notion of step and there is notion process (actor). And there every event is processed in the single step.

Erlang truthfully implement this model. And it also assumes single step event processing. There is also no work-based decomposition. The work dimension is lost from Erlang. It is also lost from all Erlang-style implementation of actor model.

The proof is quite simple. It is not possible to esaly apply functional composition operators to Erlang actors. And it is possible to specify which events actor receives, but it is hard to specify specify which are directly or indirectly produced by the actor. So it is asynchronous version of “go to” mess of synchronous code.

Note that there is the language that support all three dimensions. It is E programming language. This is possibly the first language that allows for structured asynchronous programming. The primary enabler for such programming is “when” operator that takes operation that returns promise as parameter and returns promise as result. This allows composing asynchronous processes. However the set of asynchronous operators in E is not complete. I have also created AsyncScala library in the same paradigm, that has a richer set of asynchronous operators. There is also AsyncGroovy library in the source repository, but it somewhat dated (it could be revived, if someone wishes to take over it).

The key differences of E-style 1*2*3 actors in contrast with with classical 1*3 actors are the following:

  1. There is a notion of asynchronous expression and asynchronous operation, and code reflects structure of assumed asynchronous operations. Usually there is a Promise object that represents outcome of composite asynchronous operation.
  2. Actors are separate from event queue. Single event queue could support many actors.
  3. Actors are lightweight.
  4. The framework is responsible to delivering events to the specific objects that represent actors. The normal asynchronous code does not have operations that explicitly retrieve operations from event queue.

Since a collection of E-style actors in one vat logically represent single Erlang-style actor, then I would like to name this model sub-actor model, in order to distinguish it from classical actor model, but possibly there is a better name for them.

Thus I claim that E-style actors are more powerful then Erlang-style because they provide explicit support for additional dimension of analysis and discourse about asynchronous program: work-based decomposition of the program. Erlang-style actors do not provide explicit support for this dimension, and this causes much of the pain related to asynchronous programming in Erlang.

And if you are designing a new programming language or a library that supports asynchronous programming, please consider adding a explicit notion of compose-able asynchronous operations to it. A good smoke test for notion of asynchonous operation would be applicability of functional composition operations to asynchronous operations. It really is not that difficult, just try not to leave out the key features mentioned above. You could use E or AsyncScala as a sample.

Update 1 (2012-02-20): fixed some typos

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Naming the model

I would like to name this model sub-actor model

Hi Constantine,

My first reaction to this name is that I don't like it. The phrase that I've been using is

"Communicating Event Loops with non-blocking promises"

However, I agree that phrase is too long. But first, is the concept you're trying to name the same as the one named by the above phrase? A subset? A superset?

I guess that we stress

I guess that we stress different aspects of the model.

Communicating Event Loops is a common point. Non-blocking promises is a kind of implied property. A promise is a component that lives inside such event loop, and it must be non-blocking because many other components also live inside event loop.

But your phrase misses the point about model, that I consider as the key point. The event handling is not done by one big event handler as in the traditional actor model, but this responsibility is distributted among many smaller components that share the same event loop. These components are actor-like, but more dynamic and fine-grained and collectively form one big actor. So I have named them sub-actors. Other possible names are fine-grained actors, or non-monolithic actors.

Note that there are almost complete implementations of sub-actor model that do not offer explicit support for structured event-driven programming with promises: GUI event loop. GUI event loops of the applications are also communicating event loops. It also offer dynamic and modular event handling (each control handles own events, and controls dynamically come and go).

Excellent point

Yes, Tom Van Cutsem (of AmbientTalk and JavaScript proxies) has stressed this aspect as well. However, I do not think of the objects within a vat as actor-like. I consider the vat to be actor-like, in fact identical to an actor but for this multi-faceted nature, and the objects within the vat to simply be objects.

Perhaps this issue should be the defining characteristic that distinguishes "vat"s from other forms of communicating event loops? AFAIK, only systems that are E-like in this sense have used the term "vat".

Common constraints

The actor model enforces some constraints and through this provide some safety benefites in concurrency aspect, and these benefits are similar in both models. If we look from pseudo-social point of view, the difference here is in Erlang-style single entity exclusively uses these benefits, but in E-style these benefits are shared between many entities that live in the vat, and new benefits are created as result (like safe shared memory interactions, lesser resource consumption, garbage collections), and some freedom of exclusive use is lost (for example, out-of-order receiving of events).

And If we have a vat with single object that has only ownway methods, we will have actor. So classical actors are kind of subset of E objects with vat if we look. In AsyncScala, I have even implented a vat that lives inside Scala actor.

Composite Actor Model?

I'm still thinking about the name. What about name Composite Actor Model (vs. Monolythical Actor Model)?

Seems related

I haven't quite absorbed the meaning of your three dimensions. But they at least remind me of a point I've been making lately that seems closely related:

In a system with a blocking receive such as Erlang, to reason about the consistency of distributed state, one must reason about both heap state and suspended stack state within each process. In a non-blocking system such as the E-like systems, because each turn executes to completion, the consistency of distributed states depends only on inter-turn heap states. A stack is just a vat's way of getting from one consistent heap state to another.

In operational semantics, there is small step semantics and big step semantics. For a conventional sequential imperative language, I think of a big step semantics as being like a classic mutually recursive eval/apply evaluator (but written in a purely functional language) -- it describes everything that happens from a top level call to the corresponding top level return. I think of a small step semantics as being like a classic explicit control evaluator (but again written in a purely functional language) -- it describes the transition caused by the smallest explanatory units of computation, where the transition effects both stack and heap. In an E-like system, big steps are the turns and small steps are the computational steps within a turn.

For a classic actors language, the small steps are the atomic actor events. An actor event is everything that happens within an actor directly in response to receiving one message:

  • creating actors, endowed with accessible actors
  • sending accessible actors as messages to other accessible actors
  • constructing the actor's successor state from accessible actors

where the accessible actors are

  • the actor's instance variable (acquaintances)
  • the incoming message's payload
  • actors newly created within this event

All this applies with equal force to a vat, where the actor event corresponds to everything that happens within a turn and the actor state corresponds to the vat's inter-turn heap state.

In other words, in an E-like system but not in an Erlang-like system

One small step for an actor is one big step for objects

As it happens, we recently

As it happens, we recently finished a first draft of an operational semantics for AmbientTalk which, like E, is based on communicating event loops with non-blocking promises. The formal semantics is based on that of Coboxes, which uses a similar model.

If I understand your terminology well, our semantics would qualify as a small-step semantics.

Your notion of "one small step for an actor is one big step for objects" can be readily seen in the semantics: each actor (vat) will fully reduce (evaluate) its active expression to a value before it can further reduce the next message in its message queue.

Inconsistency Robustness in Actor Systems

The Actor Model is very abstract and unfortunately often misunderstood.

It is important to understand the difference between non-imperative contexts where futures can be implicitly introduced and imperative contexts where they must be introduced explicitly.

In any case, "event loop" is confusing terminology because there can be "holes in the cheese." [Hewitt and Atkinson 1979, ActorScript], which means code is just nested expressions (i.e. no loop).

These days, an important use of Actor systems is the implementation of Inconsistency Robustness.

* Carl Hewitt and Russ Atkinson. "Specification and Proof Techniques for Serializers" IEEE Journal on Software Engineering. January 1979.

Are serializers just a pattern of promises?

It is important to understand the difference between non-imperative contexts where futures can be implicitly introduced and imperative contexts where they must be introduced explicitly.

Hi Carl, I agree completely. In E-like systems, all asynchrony including promises/futures must be introduced explicitly. In classic actors systems (including E's predecessor Joule), asynchrony is pervasive and implicit and sequence is only a pattern -- as your early actors work so elegantly pointed out.

In any case, "event loop" is confusing terminology because there can be "holes in the cheese." [Hewitt and Atkinson 1979, ActorScript].

I hadn't seen "Swiss Cheeze" before. Perhaps you added it to that paper since I last looked? I was having trouble puzzling it out until I saw the footnote (vi) that explained that they are a new name for actors "serializers". If I just think about the old serializers, am I missing anything important?

When doing classic fine-grained actors in Joule, we did find we needed something like the serializers that you and Gul Agha have explored. When used pervasively, we found it re-introduced lost progress hazards analogous to conventional deadly embrace.

In E-like systems, we find that virtually all of our need for serializers can just be handled by simple patterns of promises. (I think all the points I am about to make apply to your futures as well, which I leave for you to judge.) To delay access to a resource by some until it is released by others, have the first group send their messages into an unresolved promise. Messages to an unresolved promise just queue up in the promise. To release, resolve that promise to the resource.

We find that the most common form of this in practice is monotonic -- once released it stays released -- allowing us to resolve the promise directly to the resource. Of course, sometimes we need to dynamically re-acquire and release such locks, in which case promises need to be used as classic serializers and we must beware of classic lost progress hazards such as deadly embrace. The pleasant surprise is how rarely that latter dangerous case is needed in E-like systems.

In support of this claim, there are now several deployments of E-like systems in enough practical use to provoke an accumulation of the reusable promise pattern abstractions that people find they need. Many of these (including the ones Constantine links to above) do some form of monotonic delay and release. None of these that I am aware of have introduced something like classic serializers. This may of course simply be because we never realized how much they would have helped us, so we left them out from ignorance. I don't think so, but these are live projects and communities (especially Kris Kowal's Q library and Q-Continuum group), so one can try and find out.

In any case, however that question resolves, I don't understand how the need for serializers makes the term "event loop" confusing. Can you explain?

I'm maybe too pragmatic, but

I'm maybe too pragmatic, but I'm interested in the actors in imperative context. For non-imperative contexts I might wish to improve some "imperative" property of the program (like decreasing wall-clock time, by increasing CPU time due to actor's overhead), and I want to do it by carefully selecting boundaries in such calculations. Modern CPU do not support pervasive actors well, so I would not like to use them for converting integer to string, the assumption about cost of message send is simply not true now.

Are "holes in the cheese" coroutines, or I miss something?

I have looked though your recent articles, and they still do not explicitly the discuss work dimension. This dimension is emergent in code samples in the articles, but it is not yet explicit. Even when discussing ActorScript, this dimension is not discussed.

In the intoruduction of the article "Actor Model of Computation: Scalable Robust Information Systems", you discuss process dimension in the form of actors. And you discuss step dimension in the form of events. The work based dimension is not explicitly acknoledged.

When we consider the part of the program from work based dimension, we logically decompose the entire work to be done into smaller units of work, and define conditions when these units work to be executed. The language that supports work-based decomposition makes such work definition explicit from source code. For sequential code such transition was done with introduction of structured programming. This article is possible the best discussion of the issue. Just read this article with assumption that direct oneway event sending is a goto version of asychronous programming.

You could possibly notice that at some point of time, texbooks stopped to use step-based decomposition in pseudo-code, and started to use work-based decomposition using indentation and nested blocks.

Note that there is not the only dimension of discourse. And we could reason about acutal steps that program does (changing memory, IO, etc). We could also reason about the program, as about processes that exchange messages, and are affected by them. And the primary difficulty of learning OOP is learing this new dimension of discourse about the program.

These three dimensions are orthogonal. We could reason about the program as about the processes, and as about work to be done, and as specific steps to be done.

One of the first things for explicitly supporting asynchronous work-based decomposition is to allow naming asynchrnous units of work and to define operators that work over units of work (for example like PAR/SEQ (including loop forms) from Occam). In ActorScript, units of work are not even explicitly named on the interface, the name of asynchronous operation is implicitly defined by event it processes. This kind of like gosub in line-based BASIC, that took line number instead of name of procedure.

There is a notion of the future, but I have not found a discussion of what it represents (outcome of unit of work). And using of futures looks somewhat out-of-place here, as I undestand actor does not interacts with future using oneway messages as required by actor model, but by using blocking calls. In E and AsyncScala, the promise is more or less normal component that built upon oneway message sending. This is possible because E and AsyncScala asynchronous components could share the concurency context. And as I understand, in ActorScript each asynchronous component has own concurrency context. So ActorScript is kind of less flexible than E in this regard.

BTW serializers are quite easy to implement and use with promises. I have reinvented them in AsyncScala as RequestQueue, and they are used extensively in the code.

Discourse dimensions

Just to clarify what discourse dimensions are using project plan as analogy:

When we analyzing program from Steps dimensions, we are looking for answer to the question: What is done? So we are seeking specific effects on external world. In project plan it would total list of the leaf tasks.

When we analyzing program from Work dimensions, we are looking for answer to the question: How is it done? So we are decomposing all work that should be done by the program into smaller and smaller units. When we add this dimension into the project plan, we get hierarchical tree of tasks with dependencies.

When we analyzing program from Process dimensions, we are looking for answer to the question: Who does? So we are decomposing all work that should be done by the program into different points of responsibility. When we add this dimension into the project plan, we get tasks assigned to organizational units and people thus designated areas of responsibility.

The core actor model focuses on the questions "What is done?" and "Who does it?" and provide clear support for reasoning along these questions. But there is a weak support for discourse along the dimension "How it is done?" in Erlang and similar actor languages (as it brilliantly demonstrated in above-mentioned presentation). And we could start here by explicitly defining asynchronous operation as a set of events contributing to the common purpose. I have tried to define these concepts in the context of AsyncScala project, but possibly more generic definition could be created.

No rollback and retry mechanism built into Actor Model

There is no rollback and retry mechanism built into the Actor Model.

I don't really recognize the

I don't really recognize the description of Erlang in the topic post:

And there every even[t] is processed in the single step. Erlang truthfully implement[s] this model. And it also assumes single step even[t] processing. There is also no work-based decomposition.

The proof is quite simple. It is not possible to [easily] apply functional composition operators to Erlang actors. And it is possible to specify which events actor receives, but is not hard to [] specify ...

Is this an unintended negative?

... which are directly or indirectly produced by the actor. So it is asynchronous version of “go to” mess of synchronous code.

Note that there is the language that support all three dimensions. It is E programming language.

Although I generally prefer E's concurrency model, I think the criticism of Erlang's model on the basis given here is not adequately justified.

Erlang is a stratified language in which the sequential sublanguage is functional. The sublanguage supports functional composition and decomposition as well as any other dynamically typed functional language, AFAICS. Also, it supports composition of processes, because all you really need for that is that process ids are first-class.

You're using the word "actor" to refer to a process in Erlang and to an object in E. This complicates the comparison because an Erlang process is something like an E vat and something like an E object; the concepts in the two languages don't map one-to-one (and programming styles differ in a way that takes this into account, e.g. something that might be implemented as an object-based abstraction in E would either be implemented as a process or as a functional value-based abstraction in Erlang). Also, neither Erlang nor E are pure actor languages, so using pure-actor-language terminology (when these
languages already have their own terminology that does not conflict) is confusing IMHO.

I take the point that E supports first-class references to objects within foreign vats, whereas Erlang does not support first-class references to values within foreign processes. That's one of the reasons I prefer E's model. You can simulate that in Erlang to some
extent, though.

I don't see how the criticism of Erlang on the basis that it can be difficult to tell what messages are produced (if that's what you intended to say) wouldn't also apply to E. Selectors or types of sent messages are not explicitly declared in either language. In order to tell what messages can be sent by a piece of code, you have to search that code for message sends with the selector you're interested in or with a dynamic selector.

Possible vs. Supported

Erlang sequential language does supports functional composition. But I'm talking about functional composition of asynchronuos operation. If we consider asynchronous operation as a set of events with some outcome, then it could be seen, that there is direct support for events, but no support for operations. Looking at sequetial code we could see work-based decomposition in the source, but looking at event handling code we could see work-based decomposition. Just by looking to the text of the program we could not even guess about received event whether it indicates finish of some logical asynchronous operation that we have initiated or starts new operation that this process should implement. In E such distinction is clear. The sturcture of the E program reflects logical structure of the asynchronous operation. The structure of Erlang pogram does not. This was almost exactly the point Edsger W. Dijkstra made about gotos in sequential programming.

It is hard to compose asynchronous operations in Erlang, because there is no explicit notion of asynchronous operation in the language. On other hand, in E composition is easy. One asynchronous operation could simply call other asynchrounous operation just by using method call, and there is when operator that allows establishing quite complex relationships.

Your point about referencing values is related to this discussion. But it is about process-based composition (the dimension 3 in the post), rather than work-based compostion (the dimiensio 2 in the post,: asynchronous operations). There is a difference on this dimention as well, as you correctly noted. BTW what is referenced is not the value inside the vat. It is a facet of event loop, that will dispatch events to the value. So Erlang process is single facetted by default, and E vat is multi-facetted.

I do not consider the possibility of emulation as an acceptable argument here, since we can emulate everying, provided that the language is turing complete. To emulate E-like multi-faceted actor behavior it is required to globally enforce coding convensions, and go through the pain of manually dispatching events to logical subprocesses inside single Erlang process. This is what I call unsupported, since the structure of the program does not reflect logically assumed structure.

Combining reactions

Combining your two main points about what's new here, how about

"vats with promise combinators"

?

I have just noticed, that

I have just noticed, that both names describe means rather then purpose. And objects are missed. Maybe it would worth trying to figure out the name from purpose?

Promise combinators and vats allow us structured asynchronous programs. Promise cobinators structure the program along work dimension, and vats help to structure along process dimension. So if the classical actor programming is OOAP (object-oriented asynchronous programming), if we reintroduce structured programming we will get OOSAP (object-oriented structured asynchronous programming).

Note that it also puts dimentions in order:

  1. Steps - asynchrnonous
  2. Work - structured
  3. Process - object-oriented

I will think a bit more on it.

I also think of E vats as

I also think of E vats as the actors, and of E objects as just plain objects. That's why in AmbientTalk we used the term "actor" instead of "vat". AFAICT, the term vat is indeed unique to E.

The multi-faceted nature of vats is lacking good terminology and illustrative examples. What we need is a small example that demonstrates the benefits of this multi-faceting well, sort of like the way Paul Graham's accumulator example illustrates the expressive power of closure.

I do fully agree with Constantine about the compositional virtues of promises. I've been meaning to write up an article that draws the parallel between monads and promises, but perhaps the analogy is already more well-known than I thought, as I stumbled upon this blog post.

Shouldn't be too surprising,

Shouldn't be too surprising, esp. considering similar things done in the same spirit with backtracking, continuations, and data flow. (Another reason monads aren't that meaningful as a specific abstraction?)

This is well known, for

This is well known, for example F#'s asynchronous workflows and C#'s async/await (although I'm not sure whether the C# designers realize that async/await is notation for monads since the implementation is rather ugly and limited to "one shot" monads that only call the continuation once -- though perhaps that's for performance reasons).

Not ugly using promises and generators

async/await [...] the implementation is rather ugly

The implementation in JavaScript-with-Q-and-generators is Q.async

limited to "one shot" monads that only call the continuation once -- though perhaps that's for performance reasons

I don't know their actual reasons, but performance aside, I'd make the same choice since multiple use continuations are a horror. In an imperative context, no one writes there call/return code to be robust against a caller "returning" multiple times. And no one who read call/return code can be vigilant enough to always ask "but what if the return path from this call is taken multiple times".

In private conversation with Jonathan Rees many years ago, he agreed that it was a security mistake for W7 (his thesis on an ocap Scheme) to have preserved indefinite extent continuations, for this reason.

Granted, with shallow async functions/generators, the hazard is much narrower -- from the await/yield out to the return from the async function. And it is already the path that you have to learn to worry about more that the normal return path, because it may be postponed till after other interleavings occur or may not happen at all. But still, these are both much easier to learn to reason about than the possibility that the post await/yield path is taken multiple times.

Why mulit-shot returns are needed at all?

I agree that mult-shot returns are extremely hard to reason about. Some of quite nasty bugs I caught during development of framework were related to multi-shot calls of resolvers (continuations) in control constructs.

If multiple of values should be returned, there is a much more understandable variant using streams (like Rx framework in .NET), which even more usable with promises.

I have yet too see where actual muti-shot call/cc for the same continuation are generally nessesary or even useful, especially for stateful computations, where it is extremly easy to break some assumptions of the code.

That's a good reason, but

That's a good reason, but there are counterarguments. First, async calls use a different syntax in C# (namely `await expr`) so it would be syntactically clear where multiple returns could occur. Second, this would be significantly more elegant and would allow you to reuse existing libraries since it could be unified with LINQ.

That said I agree that the common imperative programming style where you use local state doesn't mix well with this, since through multiple returns state that appears syntactically to be local can suddenly become global. A solution for this is to implement all statefulness with state monads: that would create different copies of the local state for each branch of a multiple return instead of sharing them.

F# assumptions

The interesting thing about F# (and likely C#) is that asynchronous support was desgined with assumption that the code is mostly synchronous, with some asynchronous islands in it. At least this is what I understood from private email exchange with Tomas Petricek.

But E and AsyncScala were designed with assumption that code is mostly asynchronous, but there are some synchronous islands of legacy or purely functional code in it.

So some their design decisions make sense from this perspespective, but this also why I do not particularly like F# implementation.

That's just a matter of the

That's just a matter of the standard library, e.g. whether reading a file is asynchronous. The .NET world is moving toward that with Windows 8 where all possibly expensive operations are asynchronous.

Futures are simpler than promises

Futures are significantly simpler than promises. Is it possible to prove that using futures is necessarily less efficient than using promises? On the other hand, is it possible to prove that using futures can always be as efficient as using promises?

Counter-example

Why do you think that this is so?

Possibly your reason for this statement is that futures simplify work-based decomposition of the program comparing with naive non-blocking promises.

I find futures more difficult to use than promises. If we add listener to futures, they are not that more useful than promises. But they have undefined concurrency context associated with the listeners. In contrast to them, E-style promises have well defined concurrency context for the listeners.

If we use blocking with futures, this could lead to deadlocks, getting us to the square one of the concurrency hell. So no usability gain is here as well.

On other hand, with the right set of asynchronous operators, promises do allow to write well structured program, with clear asynchronous operations boundaries. For example, here is a simple well-structured echo server written using promises in the Scala. It is not much different from C echo server written using synchronous API. But is even-based, uses non-blocking sockets, and live in the single thread. You could try to do the simialr feat using actors and futures. At least for the similar readability.

I guess the problem is the right set of operators. And I think that AsyncScala provides quite a complete set. E does not yet provide comarable set of basic operators.

So E-style promises is the best of two worlds: no concurrency hell and the clear work-based decomposition of the program.

I understand that learning a programming language and the new library possibly is too much for the sake of the discussion, but please try to look at the samples at guide. They use quite plain Scala code without Scala advanced type system features. I think that my library is counter-example to you claim about similicity of the futures relatively to promises. And the E programming language is counter-example as well, albeit it is a bit weaker conter-example right now since it offers less asynchronous operators out of the box.

Futures are *very* simple

Futures are very simple and don't need "listners".

Let's talk about imperative

Let's talk about imperative context. Do you mean blocking futures or what?

If you mean blocking futures, than the are difficult because of several issues.

When actor is blocking on the future, it is not able to handle other requests. Including the possible callbacks that needed by the operation that have created the future. So we need a global knowledge about the program to understand if our program can deadlock or not. This is exactly a multi-threading hell. Calling the hell easy is a bit cheeky. Like with any hell, it is easy to get to this hell, but not to live in it.

Blocking on the future, consume resources. It cosume thread with its stack and it consumes any resources that were allocated and references on the lower frames of the stack. While we are waiting for future, these resources stay allocated. And since it is quite easy to deadlock, these resources might stay alloacted forever.

If you mean behind-scene registering listers, so the futures looks like a normal synchronous code, but work like even-driven code. Then promises can do it too as E and AsyncScala demostrate. But E and AsyncScala provide additional guarantees about execution context and they provide clear turn boundaries, so the developer see points where it should restore invariants about objects. Transparent futures abstract it out, and it could lead to unexpected failures. So it is not easy either.

Easy of writing the code is not equal to easiness of living with the code. And I much more concerned about the second. And considering that later is much longer, the pain of the second should reduced as much as possible, even at expense of the first.

So please be more elaborate about your thesis. Examples would also help.

Futures vs. Promises

Could you clarify what you mean by the terms `future` and `promise`? What distinction are you making?

I thought one has a blocking

I thought one has a blocking force and the other doesn't (you provide a callback that receives the val). It's been awhile..

... and, for the record, the

... and, for the record, the distinction can often mean the difference between direct style and manual CPSing (a global transformation).

We hit this, for example, when building a membrane library for secure object sharing across frames/tabs/windows in a browser (see our WWW 2010 paper). The issue was forced because the communication channel primitive between agents is asynchronous. All JavaScript mashup writers have to deal with this; the issue is very real :)

I actually found both approaches awkward. Callbacks invert your control flow, leading to spaghetti (manual one-shot CPSing pattern). Adding implicit blocking (call/cc) makes it too hard to predict library code which may now block on some other webpage (see an earlier LtU discussion about systems programming with continuation support).

For the scenarios we examined, I suspect FRP would have been a nicer fit than futures or promises. There are no blocking forces, and instead of crazy callback spaghetti nonsense, you have structured primitives for asynchrony. The underlying primitives may be asynchronous callbacks, but that's the wrong abstraction for programming.

Reactive vs. Futures

I think reactive programming beats futures/promises in most cases. The scenarios you examined were the rule, not the exception.

If we have reactive, then we can provide a value that indicates we're waiting on another value. Or we can use `improving` values, to monitor an incremental computation. The system has much greater visibility. The asynchronous structure will also be more obvious in the semantics.

Inversion of the control is a solved problem

This was the exactly the innovation of E, which I have continued with AsyncScala (while borrowing ideas from Occam as well). E discovery was that it is possible to write well strucutred event-driven programs without inversion of the control. If you are too busy to look at the AsyncScala library or to E programming language, you could look at the language neutral description of ideas(the description is still JVM oriented, but please get to the asynchronous operators part).

In E and AsycnScala the style is still direct, and there is explicit CPSing using promises. Even more, there are explicit boundaries where context switch could happen, so it is possible to restore invariants.

Your description of the problems with non-blocking is description of the symptoms of the main problem in the pre-E approaches to working with Promises. The dimension of work-based decomposition of the program was lost from source code. It was in the head of the programmer, but it was not apparent from source code. The E-style of event-driven programming make this dimension apparent again in the source code. And this usuability jump is quite similar to the jump what happened with introducing of the structured programming to sequential programming.

As for FPR, you might be interested to look to this thread in the previous post. My thesis is that FPR is the incomplete model for event-driven program. BTW there is an example in the framework that demonstrates structured handling of GUI event streams (the entire program lives in AWT even loop except for the timer thread).

My thesis is that FPR is the

My thesis is that FPR is the incomplete model for event-driven program.

I'd wager that FRP is strictly more general than future/promise programming. A reactive value is essentially:

type Reactive 'a = Future 'a * Reactive 'a

That is, it's a list of futures, whose continuation is automatically propagated to the next future in the list once the current future resolves. You'd have to write a lot of glue on futures to achieve the same result, but Reactive 'a can quite trivially reproduce the behaviour of futures and promises.

You are taking quite a risky

You are taking quite a risky wager considering that your "more general than future/promise" approach uses futures to define the basic type. Could you define your type without using futures?

Another thing to note is that your type you are proposing is able to handle homogenous event streams unless I'm missing something. The event streams for real applications are heterogenous. You could possibly could work around it by using some type like "any" or even by using the string to encode all data. Considering that IO is event driven activity, try to write a simple program using FRP that opens file and copies data from that file to another files with opening files and IO to be consdered events.

The next thing to note is CS known some extra data structures beyond lists. Trees and other cyclic and acyclic graphs are possible examples. I understand that this was a long tradition since LISP to try using lists for everythig, but I have thought, that in statically typed languages this tradition was given up. By using list, you limit the model to sequential processing of events. I see no provisions for handling parallel and correlating event streams.

On other hand, with promises it is easy to work with both heterogeneous and homogenous event streams. e promise itself is one time event channel. I even implemented homogenous event streams in AsyncScala. And they are quite easy to work with.

So I do not see how FRP is more general that futures/promises. Also your claim about a lot of glue code will have a more weight, if you would provide a sample. So far I have seen only samples that are quite trivially implemented using promises (with E-style promises).

You are taking quite a risky

You are taking quite a risky wager considering that your "more general than future/promise" approach uses futures to define the basic type. Could you define your type without using futures?

I can equally define futures in terms of reactive values. I'm just defining the type in a way you would be familiar with.

Another thing to note is that your type you are proposing is able to handle homogenous event streams unless I'm missing something. The event streams for real applications are heterogenous.

Part of our disconnect is that you're working from a dynamically typed context, and I work in statically typed contexts. What we consider "homogenous" and "heterogenous" is different. Where you see Foo and Bar as different types, I might just see a sum:

type FooBar = Foo | Bar
(* reactive values are of type "Reactive FooBar" *)
So I do not see how FRP is more general that futures/promises. Also your claim about a lot of glue code will have a more weight, if you would provide a sample.

Here's a sample from a declarative UI library in C#, where Property<T> is a reactive value the UI framework automatically manages for me:

UI Foo(Property<int> current)
{
    return new Flow
    {
        Title = current.Select(x => "Current counter=" + x),
        Alignment = current.Select(x => x < 1 ? Align.Center : Align.Left),
        Margin = new Box { All = 1.EM(), Right = Measure.Auto, Left = Measure.Auto },
    };
}

How would you represent the stream of values for a mutable UI interface using promises, except by using a stream of promises, and writing a bunch of glue code to thread the state through? That essentially reproduces reactive programming, acknowledging that promises alone were insufficient to begin with (Greenspunning reactive programming).

I cannot understand your

I cannot understand your argument. To me you are saying that something like that plus is less generic than sine, because it is requite a lot glue code to implement sine with plus. For me it is obviously reverse. The plus is obviously more generic, because it is possible to implement sine and a lot of other functions with it.

As for GUI example, could you please provide more complete sample and documentation. I do not known details of new syntax of c-sharp. In the provided fragments there is some contradictions from point of view of 1.1, like returning a new instance of Flow object from void method. Also please describe in plain english what the complete example does, if it is not described in the documentation.

But using promises and promise-based streams is quite easy to implement the similar reactive samples. For example, I have a sample in the library that is based on this demo of RX framework. It listens for events on the control until the value "STOP" is entered. And it also trottles values, displays only changed ones, and in parallel updates current time. Also you see from the example, that the amount of the code is quite resonable.

The plus is obviously more

The plus is obviously more generic, because it is possible to implement sine and a lot of other functions with it.

Invalid analogy. Reactive values are to promises/futures, as integers are to natural numbers. You can use both to implement the same algorithms, but if you use naturals where you want to work with negative numbers, you have to do all sorts of remapping to "represent" negative numbers. It's literally unnatural, pardon the pun.

like returning a new instance of Flow object from void method. Also please describe in plain english what the complete example does, if it is not described in the documentation.

Fixed the return type. This code fragment is a declarative specification of UI dataflow. The idea is that changes to Property<T> automatically flow to all values derived from it, ie. the Title and Alignment properties via Select. Since you mention the Rx framework, Property<T> implements IObservable<T>.

We don't have to recreate the whole graph, or even a subgraph when a value changes. Just the Property cells update automatically, like spreadsheet cells. The code needed to achieve this in C# is something like 500 lines.

You can achieve something similar using promises, but you would require more infrastructure, hence vats, runners and the syntactic extensions aSeq, aSend, etc. This infrastructure that is basically just replicating the semantics of reactive values, a semantics implemented in C# with no need for syntactic extensions to make it readable.

Asynchronous computations for N values subsumes asynchronous computations for 1 value.

Promises vs. Reactive values

I will look more into the sample. I will possibly create comparable sample in the next few days to simplify comparison.

You can achieve something similar using promises.

My point is that I could achieve it very easily and naturally with promises.

but you would require more infrastructure, hence vats, runners and the syntactic extensions aSeq, aSend, etc.

Note that aSeq and aSend are just library functions that take closures as argument that is imported from the AsyncControl object. It is part of the internal DSL, and it even does not need CPS rewrite from Scala. So your argument about syntax extensions is invalid.

C# has quite a rich infrastructure for their asynchronous library, including not well defined creation of execution contexts. It is not called vats, but you cannot leave out creation of execution context anyway. In your case, the standard library does it for you.

Invalid analogy. Reactive values are to promises/futures, as integers are to natural numbers.

I would say that the promises to reactive values are what integer is to array of integers.

Asynchronous computations for N values subsumes asynchronous computations for 1 value.

Please clarify what do you mean here. So far it looks like saying that array of ints is more generic that single int, so let's use arrays everywhere because they more generic. Promises allows both N values and a single where needed, and it is possible to have promises for N values as well.

Note that the advantage of the promise is that it allows to think about program in the term of the work-based program decomposition. The sinking in the terms of the streams is somewhat more unnatural, since streams do not represent a unit of asynchronous work since they do not have a natural outcome semantics, after one value is received other could be expected until stream is closed.

Also, from what I have seen in that old presentation, RX streams have push semantics, and it makes more difficult to use. Promise based streams allows poll semantics. So for consumers of the streams inversion of the control is required. This is particularly strange since it was Microsoft who understood that push API causes great problems for parsing XML and offered poll XML parser in standard library, that offer much greater usability since they did not require inversion of the control. Just consider case of IO (particularly the case of recursive parsing) that is very natural for promises and which is less natural for reactive values that assume that handling happens in the single place.

C# has quite a rich

C# has quite a rich infrastructure for their asynchronous library, including not well defined creation of execution contexts. It is not called vats, but you cannot leave out creation of execution context anyway. In your case, the standard library does it for you.

I'm actually not utilizing much of MS's standard library. The fundamental LINQ operators I depend on are actually in the 500 line file I linked to. The Property type can naturally integrate with Microsoft's reactive operators, but it doesn't need to.

Please clarify what do you mean here.

I mean exactly that you can trivially create a reactive stream of values, where the stream produces only 1 value, and that's a future. If you start with futures, it's not so simple to reproduce the semantics of reactive values.

Re: aSeq and aSend, I will have to review your interface again, but making the closures explicit reduces the readability.

Also, from what I have seen in that old presentation, RX streams have push semantics, and it makes more difficult to use.

The push semantics is the whole point of reactive values! As lmeyerov mentioned earlier, reifying the push semantics in direct-style code is the benefit of FRP, so you don't have to reason about control inversion.

This is particularly strange since it was Microsoft who understood that push API causes great problems for parsing XML and offered poll XML parser in standard library, that offer much greater usability since they did not require inversion of the control.

I think this progression is deceptive. XML does not have a natural push semantics like asynchronous/blocking interfaces do, it has a query/pull-based semantics. The underlying source of the XML, like a file, could have a push semantics, but that's an implementation detail hidden behind the interface. The push semantics are turned into pull semantics via a producer/consumer pattern.

Sasa library

I have started to look through your library. What you have provided by the reference looks just like API. Do you have a GUI sample code that actually demostrate usage of this API?

I do not see much differences from Streams library in the AsyncScala (it also described in the guide).

  • AStream - is an interface, and differently from RX, I do not need to invert one and I do not need to keep a separate IDisposable for unsubscription. The stream could be directly closed. Also it implements pull API, so consumers could decide rate at which events are consumed.
  • RichStream is a Scala analog is to static class with extension methods in C# that allows filtering over any stream.
  • QueueStream is almost like your Property class. It will become practically equal if "changed" extension method is applied to it and then trottle(0, timer). I could reasonalby easy create an extension method "latest" that will always return the latest value supplied.
  • And there are also trivial streams over collections.

So far I do not see how the Property is significantly better than Promise-based streams. You even have Promise-like functionality in your class (the methods Error, TryGetValue, HasValue, etc.), that is more naturally implemented using Promises concentrate value retreival functionality in one place.

You also have some nice ideas in the library like merging streams, I will possibly add them as utilities to my library as well.

I have started to look

I have started to look through your library. What you have provided by the reference looks just like API. Do you have a GUI sample code that actually demostrate usage of this API?

I'm afraid I haven't released the UI library yet, so there's no public interface for it. The closest analog is Bling. You'll see a similar interface for declarative dataflow dependencies that I'm trying to achieve. The declarative dataflow is what FRP is about, and what promises alone lack.

So far I do not see how the Property is significantly better than Promise-based streams.

I'm not saying reactive values are better than streams of promises with a proper API, I'm saying they're equivalent, and more expressive than promises alone. The API supporting the promise-stream abstraction is critical to this equivalence though. It has to be declarative in transforming one stream type into another, and combining streams, etc. You then pretty much have FRP.

A stream of promises is actually what Property<T> started as, along the lines of Conal Elliot's Reactive library. Turns out it was unnecessary, since I could just depend on Rx.NET when I needed to. Rx.NET is a good source of inspiration for this interface, since it's well documented.

To use a promise stream in a GUI setting, you then need a cursor-like abstraction, which is what Property<T> is. Updates to all cursors must also be synchronized to prevent glitches. I'm currently doing this with software transactions, but you probably depend on Vats/event loops since turns are sufficient for this. However, inter-Vat promise streams would only be eventually consistent, so you would experience glitches there.

Combining Streams

A problem with simple `streams of promises` is that there is no unique, declarative way to merge two streams of updates. FRP uses a time model primarily to place streams on the same dimension for merge.

I suppose for your approach you're just using whatever implicit order Rx.NET offers?

I suppose for your approach

I suppose for your approach you're just using whatever implicit order Rx.NET offers?

Yes. Rx.NET is just a framework for push-based computation. Ordering involves waiting or coordination, which isn't always appropriate. IObservable<T> requires clients to make no assumptions about ordering. If you want to order results, you could do something like:

property.GetEnumerator().OrderBy(x => x.Foo);

Or ensure your event source is ordered, ie. a stream of clock events and sampling at that time.

I solved update coordination by using a simple STM to ensure updates are serializable, but there are certainly other approaches. Concurrent revisions is a promising deterministic approach to concurrency I recently found.

As far as I can tell, your

As far as I can tell, your example only gives you local coordination. It assumes knowledge about about the provenance of the computation -- if property/x was achieved as a function of another stream, coordination is often with respect to such an earlier stream, and that means we assume knowledge about that stream was (explicitly) packed into property. That seems like the type of a thing a language/framework for concurrency should do for you.

Synchrony and Coordination

Good point. I'll expand on it. In such a structure as:

y = foo(x);
z = bar(x,y);

The `z` value should always use a consistent `x` and `y`, as opposed to updating twice (e.g. first for x, later for y). FRP and synchronous languages achieve this by explicitly controlling where (and whether) semantic delay is introduced.

Presumably we could perform some white-box analysis and constrain to update orderings that preserve consistency. This approach is pursued by Jonathon Edwards (coherence). But I dislike relying on such white-box analyses.

The `z` value should always

The `z` value should always use a consistent `x` and `y`, as opposed to updating twice (e.g. first for x, later for y). FRP and synchronous languages achieve this by explicitly controlling where (and whether) semantic delay is introduced.

And I do achieve consistency properties via STM:

MemoryTransaction.Run(() =>
{
  var y = foo(x);
  var z = bar(x,y);
});

There are no such guarantees with raw Rx.NET though.

This is really cool :)

This is really cool :) Whenever I thought about it, I ran into concerns with legibility of nested transactions and basic implementation issues. This was years ago, however, and it seems like the space has significantly matured..

It's actually pretty simple,

It's actually pretty simple, and I'm pretty sure it has the desired properties. Transacted<T> is an encounter-time locked transactional variable consisting of about 450 lines of heavily commented C#. Property<T> inherits from Transacted<T> and just implements the observer subscription logic (which is not itself transactional at the moment).

I'm not sure if transaction nesting will end up being making programs illegible, since I only need a few top-level transactions. Transaction syntax is pretty short though.

Can you expand on how STM

Can you expand on how STM helps? IIRC the problem is as follows.

    // x, y and z are Property's
    // the goal is to keep z.Value equal to bar(x.Value, y.Value)
    var z = new Property(); // FRP value, using the terminology of naasking's library
    x.Subscribe(xval => { z.Value = bar(xval, y.Value); })
    y.Subscribe(yval => { z.Value = bar(x.Value, yval); })

If you do this everything works out until x and y can change at the same time. For example if this happens:

    var y = x.Select(xval => foo(xval));
    var z = new Property(); // FRP value
    x.Subscribe(xval => { z.Value = bar(xval, y.Value); })
    y.Subscribe(yval => { z.Value = bar(x.Value, yval); })

If we now update x, then it's possible that first the callback that updates z will run, and only after that the callback that updates y and then z. So z will be updated twice, the first time with a wrong value.

The traditional solution is to do clever scheduling. But perhaps the same can be achieved with STM, I just don't understand how your snippet does this.

You are correct, STM doesn't

You are correct, STM doesn't help with inconsistent updates from the same updater, it addresses conflicting updates from other, concurrent updaters. It ensures that updater Y has seen a consistent set of values isolated from updater Z.

Standard FRP mechanisms for addressing glitches apply here as well. I took a slightly different approach. Property currently dispatches updates depth-first in order of subscription, always using the instantaneous value of the property, and it skips stale values caused by mutating recursive updates. This seems to handle many glitch scenarios, though I haven't convinced myself it handles them all.

So in your scenario, we have the following sequence of updates:

x.Value = _
y.Value = foo(_)
z.Value = bar(x.Value, y.Value)  (from y.Subscribe)
z.Value = bar(x.Value, y.Value)  (from x.Subscribe)

xval and yval always equal x.Value and y.Value respectively, ie. the instantaneous value, and not any cached value. The Select, SelectMany, etc. combinators all use Property.Value, and not the value provided by IObserver.OnNext.

So if you change the order

So if you change the order of the statements, it will glitch?

var z = new Property(); // FRP value
x.Subscribe(xval => { z.Value = bar(xval, y.Value); })
var y = x.Select(xval => foo(xval));
y.Subscribe(yval => { z.Value = bar(x.Value, yval); })

Though if you use the combinators you can't put the Select in the middle, so there's a possibility that it does work. I don't think it does though. Take the following scenario:

var a = ... some property ...;
var b = a.Select(f);
var c = a.Select(g);
var d = {the property that computes bar(b,c)};

Now if updating a causes an update to b first, then that will cause an update to d with the stale value of c, and vice-versa if it causes an update to c first.

Re: your first scenario, you

Re: your first scenario, you reference y before it's defined, which isn't possible in C#.

Re: second scenario, I believe that does indeed glitch within the transaction, since c is not yet updated when b notifies its subscriptions. The problem is ultimately the depth-first propagation inherent to IObservable.

However, all values are consistent on transaction commit. If glitching within a transaction is a problem, we can solve it in one of two ways:

  1. Switch to breadth-first updating.
  2. Use the MemoryTransaction.Completed event to run post-commit observations on the consistent values.

I haven't decided which way to go, although the first is obviously the easiest for end users.

Breadth first doesn't work

Breadth first doesn't work either. You need to visit the dataflow graph in topological order. This can be done by substituting a priority queue where you'd use a stack for breadth first and a queue for depth first traversal. You give each node a number saying where in the topological order it is, and you make sure that the number associated with a particular Property is higher than the properties it listens to. By inserting the properties into the priority queue with that number you make sure that you always visit all the predecessors of a property before you visit the property itself.

The problem with your current approach is not just the glitches, perhaps an even bigger problem is that it can take exponential time. For example in this scenario (the dependencies go from left to right):

a -- b -- c -- d etc.
  \/   \/   \/
  /\   /\   /\
u -- v -- w -- x etc.

Here b depends on a,u and c depends on b,v and v depends on a,u, etc. If you now update either a or u, then you'll get a cascade of exponentially many stale updates. For example for this ordering:

b = f(a,u)
v = g(a,u)
c = h(b,v)
w = i(b,v)
etc.

If we update a that will trigger an update to b first, which will trigger an update to c to d etc. When the top row is done the update from a to v will fire, which will then update c, which will update d, etc. Only after that the update to w will fire, which will again update d etc.

Top sort

This topological traversal is the only approach I've ever used (even down to numbering the nodes). Static scheduling can also work in many cases, but since it can't always work, I've avoided it. As long as the work queue stays relatively small, a priority queue is actually overkill in my experience. It's fine just to sweep a short worklist for the minimal element. Of course you have to be slightly careful not to double-schedule a node, but that's not exactly hard, you just have to remember to do it.

The problem with your

The problem with your current approach is not just the glitches, perhaps an even bigger problem is that it can take exponential time.

This is a property of IObservable itself. IEnumerable.SelectMany(IEnumerable,T0->T1->R) is the permutation of every T0 with every T1 associated with T0. IObservable being the dual of IEnumerable, we can expect the same from any straightforward implementation of that interface.

You can keep exactly the

It's not inevitable. You can keep exactly the same interface and update in linear time (e.g. with a priority queue). Plus you'd avoid glitches :)

Not without violating the

Not without violating the encapsulation of the observables in order to track the expression depth, or carrying the priority queue as some global state. And that still won't help you if you integrate with Rx.NET.

Eliminating Stale Updates

I use a very simple two-step mechanism to control against processing `stale` updates in my RDP implementation:

  1. `Touch` the observers, telling them that an update is coming soon.
  2. Propagate the updates.

The idea is that an observer with two dependencies (on a,u for example) that is touched from both will know to wait for the second update before propagating further. Additionally, intermediate` processes can touch their own observers - i.e. when `b` is touched, it would automatically touch c and w.

This doesn't eliminate all redundant computation (I might just miss combining updates for a and u, for example). But it does get close to ideal, and it's easy to implement.

(A topological sort would also work, of course, but I don't like depending on a global white-box analysis of dependencies. Makes me feel anti-modular and insecure.)

That's another way, though

That's another way, though some FRP implementations (and I believe naasking's as well) don't want to trigger updates when the value didn't change. In other words, if a property has value x, then updating it with value x shouldn't trigger updates. Although you could handle that with your scheme as well, with a little extra care (you'd still suffer the extra overhead of touching a perhaps large dataflow subgraph that did not need to be touched). Interesting approach!

No Change

Yes, it's reasonable to avoid recomputing values again when there has been no change. But the answer here is trivial: just treat `no change` as a possible update value, or a flag in the update.

For RDP, I have a way of doing this, too. ;)

Partitioned dataflow subgraphs

I keep touching within vats or partitions, so that keeps the overhead for touching subgraphs under control. Between vats I use a batch-processing mechanism. The main purpose is snapshot consistency, but the batches also implicitly group updates in a way that tends to minimize redundant computations.

Presumably, you could build some pathological behavior that crosses partitions like crazy in order to defeat both the batching and touching mechanisms and demonstrate an exponential stabilization cost. But it at least would be difficult to do by accident.

by accident?

uh, i urge you and everybody to never underestimate what a fool programmer like me can do out of cluelessness / desperation to meet a deadline.

fools and their deadlines

Bad ideas can be implemented in any language, and people insist on having them. Best I can do is make them work at the bad ideas, especially those that would step on other people's toes.

Well, there's also object capability security and type safety to box in both malign bastards and benign fools, and limit the damage they can inflict. But, in my role as a language designer, it is beyond my prerogative to prevent people from granting authority to fools. (Though... I do ensure they can revoke it.)

In any case, I simply don't classify acts of foolishness as accidental. ;)

Embracing the glitches

The `z` value should always use a consistent `x` and `y`, as opposed to updating twice (e.g. first for x, later for y). FRP and synchronous languages achieve this by explicitly controlling where (and whether) semantic delay is introduced.

Its possible to design a glitch tolerant language, you only need to have the appearance of no glitches to the user, whether your implementation prevents them from actually occurring is design choice.

Soft Armor against Glitches

For RDP, in partitioned systems, I don't guarantee glitch-freedom. For example, Alice's view of Charlie might be inconsistent with Alice's view of Bob's view of Charlie. But I do provide snapshot consistency between vats, so that each vat sees only consistent snapshots of other vats.

Snapshot consistency is easily achieved by processing updates in `batches` corresponding to monotonic instants, after ensuring consistency within the vat each instant. This use of batching has additional advantages for performance and efficiency.

Snapshot consistency is weaker than glitch-freedom, but is sufficient to resist most glitches in practice, and especially eliminates the syntactically obvious ones. That is, you'd need to have `global` knowledge that Bob depends on Charlie in order to recognize the inconsistency.

I'm hoping this use of snapshot consistency achieves an effective balance between performance, progress, and productivity.

I further expect developers to eliminate the remaining glitches by the simple mechanism of specifying appropriate `delay` for signals that cross partitions. Delay simply shifts updates and glitches into the future, where they won't harm anyone. One could still observe those future glitches with `anticipate`, but using anticipate at least makes it reasonably obvious that developers are willing to accept inconsistencies.

Too much delay costs space for buffering, whereas too little causes straggling updates and allows glitches... and also costs space to support EC and retroactive correction (since we'd need a longer history). Fortunately, appropriate space-saving delays are easily enforced in a distributed system (simply disconnect the troublemakers!).

I've spent much design effort to keep glitches out of the `normal` programming experience. This is based on my limited exposure to `eventual consistency`. Eventual consistency is like a safety net - it's nice to have below you, but you wouldn't want to traverse it.

I dislike the explicit delay

I dislike the explicit delay approach, having developers sort this out on their own is too much of a burden on them. My simple approach is to re-run everything until the system stabilizes (eventual consistency), tracing dependencies dynamically to achieve that. I haven't tried this in a distributed system context, but I would guess that it could work with a couple of extra round trips.

Burden from explicit delay

Burden from explicit delay is likely lower than you imagine. It is still easily encapsulated within relevant abstractions. Discovered resources can easily include estimated delays.

I think your proposal won't scale.

Large systems have more updates in any given period, and it takes longer to propagate those updates. They rarely stabilize. Instead of eventual consistency, you experience perpetual inconsistency.

RDP tries to be efficient about it. Rather than stabilizing on one value at a time, I stabilize on signals representing all anticipated future values, then just destabilize parts of those signals to accommodate further updates.

I'm OK with encapsulated

I'm OK with encapsulated delay. I just don't like the idea of developers having to figure out where to put their delay calls.

In my world, you can always view an inconsistent system, but you'll just get called again as the system becomes more consistent. The system needs barriers though: at some point you must decide not to process that next update right away and let the system stabilize. For UI/animation, at least, this point is easy to identify (render the current frame before rendering the next :) ).

you'll just get called again

you'll just get called again as the system becomes more consistent

At least you hope you're becoming more consistent... as opposed to less so, due to new updates.

I just don't like the idea of developers having to figure out where to put their delay calls.

Developers wear a lot of different hats. If your current hat is labeled `architect` or `framework` or `tuning` or similar, you might be messing with delays. Heterogeneous delay provides a lot of power with a relatively low complexity burden, and there are cases where developers will want access to that power.

Adding these delays just

Adding these delays just don't feel right to me, it looks to me like banging an engine with a hammer to get it to run right. I guess the main issue is: will the developer be exposed to the right amount of information to make well informed decisions about were to add delays? If they have to understand a massive global data flow graph or if they can only understand through how the system behaves during tests...I don't think it will work.

The reasoning required to

The reasoning required to choose delays in RDP is of the form "how long does this stage in the pipeline take?", without regard to global context or independent pipelines. And rough estimates work well enough.

With promises, the answer is

With promises, the answer is the stage is complete, when the appropriate promise that represents the single run of the stage is resolved.

There is no need to guess. The guesses go wrong anyway with changes in hardware and software (particularly optimizers and new version of libraries). So with each change of the system all guesses about the system timing should be re-evaluated.

So promises allows local and implementation independent reasoning about relative timings of operations. Delays require global and implementation specific knowledge.

Sometimes reasoning about timings in astronomical time are needed, but this happens mostly in the following cases:

  • Hard real-time
  • Low-level aspects of user interface
  • Simulation and games

But for other areas reasoning in the terms of astronomical time does not looks natural.

Shared State Synchronization

Promises are stateful - their state is unfulfilled, fulfilled, possibly broken. Other stateful synchronization mechanisms include semaphores, queues or channels, tuple spaces, blackboard metaphors.

One advantage of shared state synchronization mechanisms is that they decouple a client from the provider of a service in the temporal dimension. In many cases, the different services don't even need to be active at the same time.

I fully expect RDP developers would use such mechanisms for batch processing, incremental computations, queuing print jobs or songs in a playlist, and so on. Several idioms call for them.

But excessive use of shared state has disadvantages, too. It introduces complexity, potential for corruption, and a memory management burden (which can be difficult to discharge unless kept local). There can be subtle vulnerabilities to denial of service attacks.

Fortunately, I find RDP's primary approach (explicit delay, anticipation, stateless synchronization) to be quite synergistic with the use of shared state mechanisms. (Though it did take some effort to develop suitable state models.) Further, it has a purity to it that is lost once you introduce shared state - it's simply easier to reason about.

Delays require global and implementation specific knowledge.

It's easy to estimate delays conservatively, and so long as the estimates aren't egregiously wrong (i.e. multiple orders of magnitude on the conservative side) there is very little harm in doing so.

There is less tolerance for erring too low, since we can't retroactively correct certain effects (i.e. the sped arrow, the spoken word, the neglected opportunity). But if the only impact was on state, tolerance might be measured in hundreds of milliseconds.

So this isn't something that is particularly sensitive. Moderately conservative estimates are actually preferable because they prevent the `latency-creep` problem that happens as we extend a system - i.e. conservative estimates give the scheduler some extra freedom to fit in new behaviors without affecting observable latencies.

Hard real-time, Low-level aspects of user interface, Simulation and games [...] But for other areas reasoning in the terms of astronomical time does not looks natural.

My position is that all systems have a real-time aspect. Even for batch-processing, we at least want the ability to stop (pause, kill) the batch process in real-time. Usually, we'll also want to observe incremental progress in real-time.

For a local OS it might seem this is a trivial concern - just open up your task manager or `ps aux`, and kill as needed. It's the OS's job, right? But as we scale to distributed systems and open systems, secure and real-time task management in the language layer becomes very valuable.

I tend to think it's the rest of the world that is bass ackwards and awkward in this respect. They try to build real-time systems on top of batch-processing models and shared-state synchronization.

I expect that you'd quickly find use of explicit delay in terms of astronomical time quite natural in many roles, and no more difficult than deciding the size of a button for display.

Yet its not apparent enough

Yet its not apparent enough for the delays to be added in automatically by the compiler. I guess I would really need to see an example along with the reasoning that the developer has to go through to know that the delay should be added.

Compiler

No, a compiler could automatically introduce delays.

But I'm not fond of compilers automatically injecting semantic content. IMO, compilers exist for one reason only - to implement what is written efficiently and predictably. (Even optimizations must be predictable. An optimization that is unstable across apparently minor changes in code is worse than no optimization.)

So, while I could have a compiler do this, there's no way I would allow it without some explicit grant from the developers. I do have one behavior `bsynch` that informs the compiler or interpreter to inject just enough delay to equalize delay on asynchronous signals (e.g. from parallel pipelines). I've also considered use of ranged delays that let the compiler choose within a range.

OTOH, I don't mind delay encapsulated, e.g. in dependency injection or link layers, including access to foreign services and FFI. So long as the responsibility for them is well understood.

Anyhow, the answer to your question about how developers "know that the delay should be added" is that this isn't exactly arcane knowledge - delay should always be added. The goal is for the logical delay to roughly reflect physical latencies of calculation and communication. The only question is whether it be more convenient to pretend that a few local operations have zero delay (i.e. to coordinate operations as synchronous) and to make up for it before or after.

Content-addressing; Eventual consistency

Snapshot consistency is easily achieved by processing updates in `batches` corresponding to monotonic instants, after ensuring consistency within the vat each instant.

I think a good basis for this is content-addressed data, as in Git. It's a proven model for efficiently distributing changes to "human-sized" data. But I doubt you like it. ;-)

Eventual consistency is like a safety net - it's nice to have below you, but you wouldn't want to traverse it.

Yes. I find eventual consistency a horrible paradigm for end-user applications. For example, in Twitter, it's simply impossible to know whether one has seen all messages.

RE: Content Addressing

I'm having troubles seeing how content addressed data would be a good basis for snapshot consistency. I think, rather, that the converse might be true.

streams of updates

What do you mean under "unique, declarative way to merge two streams of updates"? What would you do with merged stream?

Note, that there is combined handing of the two streams in the sample: timer and text changes.

This is obviously imperative code with functional elements. But I consider the code easy to understand and modify. There is no explicit time dimension, but relationship between events is specified using promises and there is an implicit ordering due to the properties of the vat.

Data fusion is what we do

Data fusion is what we do with merged streams - calculate some information that wouldn't be possible without both data resources.

Your sample is very ad-hoc, and I would find it difficult to reason about consistency. This seems to be common to most observer-pattern code in imperative systems, which perhaps is why some intelligent people have written in favor of deprecating the observer pattern.

I do not see how they are

I do not see how they are deprecating the observer pattern. Molecules do not deprecate atoms. And they build upon observer pattern, so it serves them as a foundation. The observer patterns serves as foundation for promises as well.

They offer practically the same thing as Rx (which we have discussed earlier), but using Scala way and they seems to have priority over Rx. And offer some control-flow like constructs over the streams. The streams in AsyncScala are practically the same, but they do not need to recover from inversion of the control in domain specific way, since there are generic approach for such recovery basing on promises. AsyncScala streams do lack some of primitives that are described in the article, but I do not see major difficulties with adding them, I will possibly add them in the next version.

The thing that makes me wondering is that they describe a lot of ways to consume events from event source and combine these event streams in the new ones. But a little is said about constructing base event sources (Signal is actually intermediate between real event source like button and consumers). The same incompleteness could be encountered in FRP as well.

Also the events seems to be considered as discardable and representing state changes (so later event supersedes earlier rather than adds to it), so model does not look to be suitable for complex event processing and generic IO (and the article partially confirms that it is not suitable for CEP due to these reasons in section 7.4).

Deprecating observer pattern

Deprecating observer pattern by replacing it with a more structured and constrained variation is not so different from deprecating `goto` by replacing it with structured programming models.

Sure, something very like goto is still used `under-the-hood` in the form of jumps. And sure, something very like observer pattern is still used `under-the-hood`. None of that is relevant.

In programming, molecules do deprecate atoms. That's the nature of abstraction.

Initial event source

But a little is said about constructing base event sources (Signal is actually intermediate between real event source like button and consumers). The same incompleteness could be encountered in FRP as well.

The same incompleteness applies to procedural programming, too - we're somehow mysteriously presented with a bunch of procedures that represent access to the OS, network, and filesystem. Other than path dependence, nothing fundamentally requires such systems be procedural. Why not reactive by default?

If we had a reactive language, we would simply present the relevant event sources in a compatible reactive manner and leave the implementation details to the language runtime - perhaps extensible with plugins.

For an embedded reactive language, we simply model the `plugins` internally by writing adapter code. This is what applies here - you'd simply extend the reactive interface that seems a good-enough match to whatever service, resource, or library you're adapting.

I'm talking about somewhat

I'm talking about somewhat different thing. I'm talking about creating and destroying new event sources while handling events, while staying within single paradigm.

For example like creating pop-up dialog, responding to events within creating and destroying controls on the dialog, and then finishing dialog producing an event.

I have not seen example for FRP like it. All examples dealt with fixed configuration of event sources, and they were combining events from the these sources.

Other example that I have not seen is like the following. Let's consider we have asynchronous interface to access web. How we could implement robot scanning the pages using FRP model. The page generates a lot of IO event while it is being processed and processing the page generates new application events in form of scheduled scans of pages. Promise based API allows natural organization of such functionality, but such event handling task seems to be out of the scope for FRP, because it requires management of event sources.

IO is naturally event-driven, it is organized using blocking API just because of mainstream programming languages do support as convenient means of organizing event-driven code as for normal sequential code.

As far as I know all FRP GUI

As far as I know all FRP GUI systems that let you create widgets dynamically do so with imperative update to the GUI widget tree. So they are not pure FRP. This was discussed in a previous thread.

That said you can build every application as an event stream transformer. The input event stream represents data sent from the OS to the program and the output event stream represents data sent from the application to the OS. For example if you want to make a system call to do network IO you send this request on the output event stream. Some time later the OS will post the result on the input event stream.

What's missing from FRP is a known way to build a high level composable interface to e.g. network and GUI from this low level interface. Perhaps it's easily possible with existing FRP combinators, but I'm not aware of anybody who has shown how.

Event streams

Do you have any sample code of FRP managing UI? In samples that I have seen, the imperative GUI construction and FRP event handling are somewhat disjoint worlds. FRP code fragments looks like bubbles in the imperative code that manage UI.

There is no problem in event transformer approach. GUI applications are such event transformers. The question is how such event transformers compose. GUI approach decompose even handling into components over single event loop. Such component have different life times and are affected only by specific sub-streams in event stream. And they generate own event sub-streams (for example converting mouse events to list selection events).

The vat/promise model is a generalization of such approach, so there are multiple interacting event loops that host multiple components within single application or even application cluster. This is a total model, that supports creation of event sources, their lifetime, and handling event streams and sub-streams.

FRP model samples that I have seen worked only with parsing pre-existing event streams (from point of view of FRP code). When something should be done with UI, the code was falling back to plain imperative code (or to IO monad in haskell, which is haskell way of imperative code).

You could look at the

You could look at the Flapjax demos. You are exactly right that the problem with the pure FRP OS interface (for example the pair of event streams) is that it is unknown how to build a composable GUI toolkit on top of that. That is what I (perhaps unsuccessfully) tried to explain in the thread I linked to.

That said the imperative update can be largely hidden under the hood. What you do to achieve a dynamic GUI is to define a stream of widgets instead of a static widget. For example:

widgets = [image("carrot.jpg"), label("hello"), listbox(...)]
b = button("switch")
widgetID = b.clicks.fold(0, (id,click) => (id+1)%3))
widget = widgetID.map(id => widgets[id])
gui = stack(b,widget)

Here the functions image, label, listbox, button and stack create widgets. The button has a property `clicks` that we fold over to get a count of the number of clicks happened so far modulo 3. We then use this time varying `id` to index into the widgets array and we get a time varying widget. The last line composes the button and the time varying widget to a single GUI by stacking them vertically. The result is a gui that starts by displaying an image of a carrot and a button named "switch". When you click the button the carrot switches to a label saying "hello", and when you click it again you get a listbox. When you click it again it goes back to the carrot, etc.

To be clear, Jules is

To be clear, Jules is essentially concerned with managing unique identifiers in the FRP setting (somewhat like NeelK's work), which is a concern in any pure system (including through the use of promises). In the work I'm familiar with, such purity wasn't an actual concern (the encoding happens somewhere, and the systems were fine with the usual techniques).

The case Constantine is interested seems to relate to higher-order behavior, which is fine as demonstrated by this widget that builds an interface in responses to a webservice. The service returns a stream of arrays of links, each array is mapped into a UI, and the UIs are swapped in as they come. The UIs themselves are reactive (e.g., mouseover effects).

Handling modal UIs seems similar to my view of Jule's concerns on naming. They can be handled within the UI framework; it does not need special FRP/language support. E.g., the notion of the DOM can have a notion of a global modal dialog. I think doing this in a pure world is a little awkward -- for example, every UI can return merge operations for the modal dialog -- but it is not essential to programming with streams. (E.g., if the language does not have clean support for leaving this as an implicit parameter, just use mutation).

It's not just unique

It's not just unique identifiers. Say you have a b = button("click me") function that constructs a button. Such a button will have an event stream of clicks b.clicks. This stream of clicks will not be active until the button b is installed somewhere in the widget tree. Therefore this installation in the widget tree cannot happen functionally, not even if you have a way to generate a unique identifier for the button. Installing b in the widget tree somehow mutates it or its clicks stream. This also means that such a GUI toolkit can not be built on top of the pure FRP combinators in the setting that the interface to the OS is also pure FRP (an example of such a pure FRP interface to the OS is the stream of system calls from the program to the OS and a stream of answers from the OS to the program). This is what I mean when I say that when compositional FRP GUI toolkits (e.g. flapjax) use imperative update in an essential way. It can probably be done with arrow FRP since GUI widgets are basically arrows in the arrow FRP sense, but the resulting interface is not pretty. Especially for dynamic interfaces and stateful widgets.

This is what I mean when I

This is what I mean when I say that when compositional FRP GUI toolkits (e.g. flapjax) use imperative update in an essential way.

This is exactly why I call FRP incomplete paradigm for event-driven applications. They might be nice way to organize local event handling, but FRP is not a complete functional approach to event-driven applications as it is sometimes advertised.

It's not just unique

It's not just unique identifiers. Say you have a b = button("click me") function that constructs a button. Such a button will have an event stream of clicks b.clicks. This stream of clicks will not be active until the button b is installed somewhere in the widget tree. Therefore this installation in the widget tree cannot happen functionally, not even if you have a way to generate a unique identifier for the button.

I think it is possible, in the same way that a zipper is functional. From time step to time step, there's a different DOM zip. That means GUI programming implicitly (or, using traditional functional methods, explicitly) passes this DOM around.**

It can probably be done with arrow FRP since GUI widgets are basically arrows in the arrow FRP sense, but the resulting interface is not pretty. Especially for dynamic interfaces and stateful widgets.

We may have said the same thing, I'm not sure :) In short, it's possible, but I don't find it useful outside of ICFP/POPL papers and some crazier ideas :) It seems like an ok way to model things, but rather twisted for an end-user abstraction and actual implementation.

This is exactly why I call FRP incomplete paradigm for event-driven applications. They might be nice way to organize local event handling, but FRP is not a complete functional approach to event-driven applications as it is sometimes advertised.

I don't understand how promises get around this, unless by promises you mean using state. I'm not claiming FRP's event scheduling is a panacea -- for example, Sean and Naasking have both demonstrated useful relaxations/extensions for inconsistency tolerance and nested/partial time steps -- but I feel like this discussion has been on a shifting basis. Do you have some sort of formal property you want with a corresponding example?

** This implicit monolothic GUI passing is also one of the only ways I see how to build a modal dialog functionally, and is one reason I dislike them. Modal to the page, frameset, tab, window, ... how much state are we passing?

Promises and event streams

I don't understand how promises get around this, unless by promises you mean using state. I'm not claiming FRP's event scheduling is a panacea -- for example, Sean and Naasking have both demonstrated useful relaxations/extensions for inconsistency tolerance and nested/partial time steps -- but I feel like this discussion has been on a shifting basis. Do you have some sort of formal property you want with a corresponding example?

This is a quite deep question.

The complete event-driven application paradigm should allow organizing application as global event stream that decomposed to smaller and smaller sub-streams that dynamically come and go and layered above each other. So I seek is that creation of components that are final or intermediate event sources should be also done by events. Initiating creation of component is an event, finishing creation of it is an event, doing some operation on it and receiving reply are events too. Destruction of component is a pair of events too. So the application is a giant event stream that is logically factored into smaller and smaller sub-streams that are handled independently.

All variations of actor model (both E-style and Erlang-style) support it. E-style is a advantage over Erlang-style actors that event streams could be factored out even further using promises (I will get to it later).

All FRP samples are did imperative management of event sources. For example, I have not seen a good sample that works like the following.

  • There is a generic network interface object and service object (for example HTTP server).
  • A service object at its discretion initiates opening a stream of incoming connections on some port.
  • The network interface object binds server socket to port and return a stream of sockets.
  • The http service partially handles input connections and delegate it to event driven handlers basing on URL and headers. The handlers handle request in own way using services that http service is not aware of.
  • When someone requested stopping handling http requests, http service just closes event stream of incoming connections.

So this network application is a big event stream. And the events in this stream should be handled in some modular way.

I do not see how to implement such task naturally with FRP in modular way. Note that network interface, http server, and handler generally should not know which events they are using. The event should be private to each component.

Other important issue is that for IO applications there is always a factor of flow-control. The speed of data producers and consumers could differ greatly. So event consumer should be able to select a speed at which it receives event. And this could be easily done by putting consumer into the control, allowing it to request each event from event source separately, by providing a onetime event listener.

But straightforward event listeners case inversion of the control in the application, and application becomes the mess. Here promises come to rescue. Promises (with control flow operators that I'm advocating) put event consumer back into the control and it is now possible to implement application without inversion of the control. There is a kind of CPS rewrite happening under hood, but it is not affecting the programmer.

And promises make event exchange private. Other event consumer do not need to filter out unneeded requests. They only receive events they have explicitly asked for. And it own turn this makes event handling modular, since event handling decisions are done locally, so other components do know and should not care which kinds events are used to implement what they have requested.

There are a lot of issues

You might find it useful to pick one concrete property, reason about it semi-formally, and show why FRP cannot possibly satisfy it. I don't feel like you have in this post. Otherwise, I feel like we'll continue this gopher game where you claim something and I show how it's done.

Flapjax showed we can program that client with FRP. Nate Foster's work shows that you can build networks with FRP (and several older FRP projects did similar things, such as distributed games, as well as the whole network building block language that is essentially dataflow).

Questions of flow control seem both encodable within the system and, if really that important, doable at the language level.

I don't see why how FRP fails at the privacy question.

creating and destroying new event sources

In FRP, one typically models this with first-class event streams. E.g. listening on a socket might be described as an event stream of new event streams. An output event requesting the creation of a new dialogue (with a given name - integer, string) might later result in an input event providing a corresponding event stream (with the same name). (Most FRP models do model events in addition to signals. The only exception I'm aware of is Elerea.)

The difficulty with FRP is not modeling new event sources, but rather hooking FRP behaviors into the new external services (such as GUI or network); it's easy to end up needing end-to-end changes. I discuss the challenge when motivating reactive demand programming (RDP). In RDP, the open composition problem is easier - you simply `demand` existence of a dialogue with a given specification, and in response you get a signal or first-class behaviors for accessing user-input.

Are demands the similar to promises?

As far as I understand you are saying about the problem of creating new components that are event sources in the following paragraph.

A client application is not aware of other clients. FRP is pure, thus a stateful service shared by multiple clients will never be modeled within those clients as an FRP expression. Same holds for sensors, actuators, and foreign services. Clients and servers do not compose without escaping the FRP paradigm.

So I guess we are no the same page here, but using different words and view points to describe the same problem. That interesting thing is that you are aware of composition problem of FRP.

In RDP, the open composition problem is easier - you simply `demand` existence of a dialogue with a given specification, and in response you get a signal or first-class behaviors for accessing user-input.

Demanding dialog with the specified specification is exactly what promises are for. A promise represents an outcome of asynchronous operation. The operation is started using some method with parameters, and than it is possible to work with result after promise resolves (or event before it with promise pipelining). It would be interesting what would you end with, but on the first sight you are describing reasons why have switched from SEDA-like (AFAIR Apache MINA uses this model as well) to E-like model or working with asynchronous services. The promises were the answer to me. It is quite possible that your 'demands' end up with something very similar to promises, since you are trying to address the same evolutionary pressures and you are aware of them.

Not very

Demands are similar to messages (commands, queries) but have a more RESTful and reactive nature - like publishing and maintaining a remote value. Creating a dialog in RDP would not be a one-time message (with another message to destroy it); rather, you'd simply maintain the demand for however long you want the dialog to exist, and the demand will automatically be removed when you stop maintaining it.

Response to each demand is also RESTful and reactive. Promises are single-assignment, delayed, and stateful, whereas responses in RDP are reactive, immediate, and stateless. But, early on, a response involving shared-state communication could simply be `waiting...`, which is similar to a promise.

Developers could use explicit state to model fire-and-forget events - i.e. Alice modifies state to indicate that a dialog should be raised, and another agent owned by Bob observes this state and raises the dialog. This decoupling through state has both advantages (allowing asynchronous communication) and risks (Alice might fail to maintain the state, and there is now a GC burden that is difficult to discharge in an open distributed system). Fortunately, there are state models that help recover the desirable properties, e.g. based on synchronization of micro databases (for partitioning tolerance and resilience) and temporal data (for animation, expiration, and resource control). There are also techniques to achieve pseudo-state for stability where we don't really care about an accurate record.

Use of intermediate state would similarly be necessary to model single-assignment promises in RDP. Modeling promises with state isn't difficult, and was one of my earliest pseudocode validations of RDP. But I would discourage modeling promises. I haven't found any use cases for them. The case for single-assignment seems to be quite weak in a reactive programming model!

not naturally event-driven

The page generates a lot of IO event while it is being processed and processing the page generates new application events in form of scheduled scans of pages.

Again, you beg the question by assuming events are generated in order to prove need for events. And also you focus on the issue of purity rather than the modeling of events. (As I said earlier, most FRP models include support for events. One could even model generating and waiting on events for processing a web page, and asynchronous processing.)

Today's JavaScript-heavy web makes a rather poor target for declarative programming models. But, ignoring that, if I were to model your example eventlessly, I would extract a set of dependencies from each then demand access to each dependency in a RESTful manner. No need for events, though I could still use intermediate state for scheduling and stateful synchronization.

IO is naturally event-driven, it is organized using blocking API just because of mainstream programming languages do support as convenient means of organizing event-driven code as for normal sequential code.

IO is not naturally event-driven. It isn't naturally blocking, either. In some cases, path dependence makes events or blocking sequential API the easiest way to model IO.... but that would be a bit like calling `cars` natural because we have paved roads.

depends on meaning of the world 'event'

IO is not naturally event-driven. It isn't naturally blocking, either. In some cases, path dependence makes events or blocking sequential API the easiest way to model IO.... but that would be a bit like calling `cars` natural because we have paved roads.

We are diving further into philosophy here, and I hope would dive deep enough to discuss of what is meaning of word 'is' ;)

If we take is a generic definition of event as observable occurrence, then it becomes quote obvious that IO is event-driven (at least for me).

  • Starting writing buffer to file is an event generated by application
  • operating system observes it and puts data to memory and notifies SATA controller
  • SATA controller observes notification and data and writes sends it to HDD.
  • Internal HDD controller observes incoming data and request and does some black magic involving heads moves, magnetic fields (having own internal stream of events), and in very unlucky case possibly smoke and mirrors. HDD controller nofies SATA controller back after finishing all of this.
  • SATA controller observes it and notifies operating system.
  • Operating system observes it and notifies application.
  • And the application after receiving notification, possibly notifies someone else, for example updating progress bar or telling operating system that it wants to receive more data from a socket.

Note that is very hard to model it only in terms of state, since it is not clear when to check for the change of state. There should be some event that triggers state detection. So state model of IO would be a kind of incomplete, since it involves events anyway. Events involves both state + control flow, so they represent ordering on time dimension in addition to state.

The blocking sequential API still use pair of events. But application is just refusing to handle other possible events while waiting for reply (at least on this thread). So sequential API is a mismatch with event-driven nature of IO. It just more convenient in some situations since most of the languages do not support event-driven control flow in a natural way. E-style actor model that I'm advocating does allow such natural event handling.

However it of course depends on what meaning of word 'natural' is ;)

meaning of event

The notion of an `event` is essentially "a change in state that an observer finds interesting enough to report". Events are subjective - temporal points of interest to some agent.

A common problem is that the changes one observer finds interesting enough to report are not the same changes a downstream observer is interested in recognizing. So, downstream observers are resigned to the painful and error-prone task of reconstructing state from upstream events.

Most of this is accidental complexity, a consequence of using `events` in the data stream when (by nature) events are subjective and local to each agent.

Keyboard events

I think this is too narrow definition of the event, it does not seem to naturally include messages as a kind of events.

Observer is naturally limited by capabilities of observed. I would possily like observe HD movie on the ceiling to show HD movies, but in my room in the current configuration it is currently impossible. If observed does not report some event, the observer has to derive this event from other events. In the current application on day work, we derive events from timer and database changes for some events and JMS queue for other events. So I consider mismatch between observer and observer is a natural thing, it is not possible to create observed that by default report everything (for example, objects do not usually report if they are in memory or paged out to disk by OS, but could report changes in property).

Let's consider keyboard events. There are key press and key up events that seems to conform your definition. But there is key press event, that does not seems to conform.

After key pressed the key on the keyboard is in the same state as before pressing (some wear down has happened and some sweat is possible left on the key, but it is not what is reported). Even more, multiple key press events are generated while key is down. I do not see how you would model is as series of state changes.

On other hand, checking state could be viewed as a series of event as well, we send event "please tell you state" and receive an event "my state is X". Even human perception is very active multi-level process of exchanging messages between neurones and input signal are usually gone after they percieved (partucularly for the audio channel). Modelling speach as state changes in speaker is quite hard.

Keyboard state

there is key press event, that does not seems to conform.
After key pressed the key on the keyboard is in the same state as before pressing.

To observe a keypress requires observing a change in key state - down then up. In practice, this observation is typically made upstream of the application - i.e. an observer in the OS, possibly in the keyboard itself. But if you go far enough upstream, you'll eventually reach observation of state.

This is true no matter the event. Messages on a network are ultimately sourced from observing changes in voltage. Multi-part messages are sourced from building state for smaller ones, and eventually observing a completion state.

Key-repeat events when holding a button down (besides being a dubious feature with no intuitive relation to user input through a keyboard) are ultimately implemented in terms of observing a stateful model of time (a clock or counter) and key state.

mismatch between observer and observer is a natural thing

Similarly, epicycles are a natural consequence of assuming Earth sits still at the center of our solar system.

checking state could be viewed as a series of event as well, we send event "please tell you state" and receive an event "my state is X".

Yes, this can be done. Yet it seems like an abstraction inversion.

human perception is very active multi-level process of exchanging messages between neurones and input signal are usually gone after they percieved (particularly for the audio channel). Modelling speech as state changes in speaker is quite hard.

I'm not advocating that we model in terms of events or `changes in state`.

Modeling speech is difficult in any case. Assuming we know what to say and how to say it (the Turing Test problem), there is the challenge of synthesizing a voice. Yet, ultimately - as far as our computers are concerned - speech is a pattern of voltage states (or changes in voltage state) in a speaker (or microphone).

model with state

Note that is very hard to model it only in terms of state, since it is not clear when to check for the change of state.

You think in terms of events to check state (query events, answer events). But that isn't necessary. A stateful approach to observing state would be `continuous` in nature, just like state itself. E.g. continuously watch a given field for the duration a boolean value holds true.

Reactive programming models are suitable for expressing this. And don't assume that observable intermediate states are `missed` in all reactive models just because they are in some reactive models.

Events not essential

events seems to be considered as discardable and representing state changes (so later event supersedes earlier rather than adds to it), so model does not look to be suitable for complex event processing and generic IO

If events are sufficiently constrained in their expressiveness, the inability to readily perform `complex event processing` becomes rather moot. And there are other approaches to IO than just those you are familiar with.

It is my impression that you think events are much more essential and wonderful than they actually are. You have used the word `event` 20 times in one comment.

My own judgement has been that events and event-processing are a major source of accidental complexity and fragility and non-essential state in programming systems. It's hard to recover from a lost or disordered event (whether through network failure or programmer error). We spend much time attempting to maintain a consistent view of the world with an easily corrupted or divergent local state model.

I deprecate events in my reactive demand programming model, but I do provide adapters to model common event streams in a stateful/RESTful manner. E.g. if clients press a button on a keyboard, this might be represented as the button being down for 3 ms (or whatever I estimate from the adapter's event stream, in case of overlapping button presses in a frame), then back up.

Effectively, I model events by observing changes in state, rather than the more traditional modeling changes in state with events.

I utilize suitable declarative state models for eventless updates and control, so I could add a character to a text field upon observing the button-down. It is possible to control state with even more state, analogous to how CEP controls events with even more events.

Different kinds of events

We are talking about event-driven programs now, aren't we? There are surely programs for which events are not essential (compilers are typical example, but for incremental compilers events become more interesting, but still not essential). Coincidentally classical functional languages shine on such tasks until easy run-time extension is needed.

I have been exposed to different kinds of events: from mouse move to SWIFT messages. CEP is more related to later kind of events and it is often happens in B2B context. And in such context events are quite essential. For UI, tasks more loose practice of working with events is more acceptable, but user would not like loosing keyboard events anyway.

For different kinds of events different processing quality is required.

BTW could please provide references to other IO approaches that you have in the mind?

Interactive Programming

We're talking about real-time, interactive or reactive programs. You conflate the requirement (real-time, interaction with humans and environment) with a particular mechanism to achieve it (event-driven).

You speak of keyboard `events`, mouse move `events`, and SWIFT `messages`, but those certainly aren't the only way to represent the communications. Keyboards have state (buttons are up or down). Mouse is typically modeled as position over time. SWIFT, even if we were to keep the same ontology, could replace messaging readily enough with tuple spaces or a more stateful mechanism.

Don't assume that using state means we must lose information. A naive implementation might do so, but if states are tagged with virtual times it becomes easy to collapse just the right states (when dealing with fixpoints) while keeping all the important ones separate.

could please provide references to other IO approaches that you have in the mind?

You've been provided references, to the use of Brookian behaviors (in your earlier thread), and the use of declarative state models and my RDP. Here are a couple more: Elephant, a language based on speech acts. Dedalus and Bloom, Berkeley's work on temporal logic for cloud programming. AmbientTalk also has an approach for treating messages as stateful conversations.

Wouldn't it be easier

Wouldn't it be easier with

type Reactive 'a = Future ('a, Reactive 'a)

Global inversion convention is a tough sell

I've read Mark's thesis about twice, and several parts several times :)

This is my entire problem:

and there is explicit CPSing using promises.

One way of looking at it is that FRP lets us turn control flow into regular old value passing. Questions of how to reify and compose control flows, such as when calling into/from third-party code, are fairly elegantly avoided**. Basically, everything is asynchronous: push (react), not pull.

Futures and their variants also let us compute over asychnronous values just like regular synchronous values. However, we now have the problem of how to know if a library call may indefinitely block (force).

Promises eliminate the risk of these blocking calls by again making everything asynchronous. However, instead of the nice value-based approach of FRP and futures, 1) there are CPS-style callbacks everywhere by convention (making life tricky when they are not available) and 2) reasoning about them is an inversion of reasoning about direct program (back to direct style). I like FRP because I get direct flows, and for sequenced interactions, likewise prefer the PLT/Racket Server's use of continuations: callback pasta was the problem, not the solution.

**: except when you want to play with asynchronous compositions, such adding new primitives or, say, Kim Burchett's paper @ PEPM on optimizing away message passes (similar to deforestation)

Edit: I agree with you that FRP, especially as practiced today, is incomplete in many ways, though perhaps not in the ways you are thinking :)

Asynchronous Composition with Proimises

Your statement is true for Erlang-style actros, but it is false for E-style actors. This is exactly where division between two models is.

Have you actually looked at E samples or AsyncScala samples? The advantage of E model is that it makes the best of two worlds.

  1. CPSing explicit in the sense that the programmer know where it happens and there is no nasty surprises.
  2. CPSing implicit in the sense that the programmer do not perform global code rewrite and the code still looks like normal well-structured program. That just returns promises rather than values.

I understand, that you probably know from the experience the advantages and disadvantages of promises. But this discusssion, you cannot rely on the prior experience alone, since my point is that the experience changed with E and AsyncScala. E has greatly changed the way of working with promises. In AsyncScala, I have developed it further. The changes might look subtle, but they change they way the program is organized, because we are back to normal value passing and structured programming, but we keep advantages of the promises. This is the main point of my post. This is why I claim that E and AsyncScala approach to concurrecny is better than Erlang-style actors. For a quick start, you could look a the language-neutral description of the concepts.

You could also look at NIO-based echo server(the description in the guide). The server looks almost like normal the normal echo server written using synchronous API in C++. The difference is that the values are extracted using aWhen operator (that return promise), and loops are done aSeqLoop operator. And there is aSeq operator that orders asynchronous actions sequentially. But this is still normal value passing, and it is even possible to use mutable values from the lexical scope under right conditions.

I'll reread that stuff now,

I'll reread that stuff now, but in case you know the author: I tried to read the 'language-neutral description' several times and failed. Likewise, I've found the code examples too dependent on host language assumptions (syntax, semantics, etc.) -- I'm coming from a very different starting point than the author.

I'm the author. The

I'm the author. The AyncScala guide assumes knowledge of Scala. The wiki pages were intended as abstract and reusable quick reference part that specify what is common in three different versions of the framework (Java, Scala, Groovy), but the asynchronous operator syntax is intentionally abstract from the language, but assumes some imperative Java-like host language.

Gotcha. Even knowing what

Gotcha. Even knowing what vats and promises are, I found the description of AsyncScala's view of promises too hard to read. I think at least four important concepts are going on in this api -- sync/async, same vat / diff vat, source and sink, and arrow types. I didn't find them very clear; I'm assuming they act how E's acts.

Wrong strawman :)

I've reread the E docs, and I think I see where I was missing you:

My understanding of the promises construct, in the assembly of the web:

var carPromise = asyncGetCarFromServer("mercedes");
//...
carPromise.then( //non-blocking, just registers a listener 
  {
   succeed: function (car) { 
       var status = inspectTires(car);
       alert("Your car tires are: " + status); 
   },
   fail: function (e) { alert("fail: " + e); } 
  };
//finish event loop trip; succeed/fail may (or might not) run now

Using it in this way is wrong in practice, and what I meant in the sense of my CPSing argument. I now realize this was the wrong strawman :) I was thinking of our WWW scenario (sharing proxy objects between frames/vats) where returning a wrapped type (the promise) was not an option, and so the callback would be required to unwrap it.

The correct, canonical way is as follows:

var carPromise = asyncGetCarFromServer("mercedes");
statusPromise = carPromise.then({succeed: inspectTires});
statusPromise.then({succeed: alert}); //side effect
...

At this point, I agree with you that it is much better: we again have the explicit first-class push dataflow that I wanted :) There are differences in singly-assigned dataflow variables (e.g., Oz) and streams (FRP) -- you can do cool things with streams/cells/etc. like monitor an algorithm and make stronger statements about the value of something over time -- but they aren't related to what I was discussing.

Interestingly, for my proxy scenario, FRP and promises actually both still kind of fall down. Using either will taint whatever code uses them (consuming code will insert a force/callback and be back at square one). More particularly, given code written for the same-frame case, how do you update it to take the event stream / promise? In FRP/promises, you can't flatten out of the type ('a R -> 'a), while futures can ('a F -> a). Instead, FRP/promises advocate lifting the rest of the program, which is a tough sell :)

Better sell then Erlang-style actors

Using the abstract operators the example will looks like the following:

 seq car := {
   asyncGetCarFromServer("mercedes")) 
 } then status := {
   car.inspectTires()
 } then {
   alert("Your car tires are: " + status)
 } then {
   status
 }

Or using shortcut form:

 seq(car := asyncGetCarFromServer("mercedes")), status := car.inspectTires()) {
   alert("Your car tires are: " + status)
 } then {
   status
 }

If we assume that alert is an asynchronous operation as well that returns promise that finishes after alert is dismissed, then the entire operator will return the promise that is resolved with status after alert is dismissed. The next example demonstrate loops.

 seq worst := {
   all for i in 0..10  {
     seq(car := asyncGetCarFromServer("mercedes", i)), status := car.inspectTires()) {
       alert("Your car " + i + " tires are: " + status)
     } then {
       status
     }
   } fold(result := Status.OK, status) {
     Status.worst(result, status)
   }
 } then {
   alert("Worst car status is "+worst)
 } then {
   worst
 }

This example start body for all values 1..10 at the same time in interleaving fashion. And it returns promise that eventually resolves to the worst status available when all alerts are dismissed. Retrieving the car and examining their statuses will happen in logically parallel fashion in the same event loop, the result is folded to the worst status. Then the worst status is shown and total asynchronous operation result returns the worst status.

So trick is that all operators returns promises, and they could be easily composed. And yes, this is the lifting asynchronous parts of the programs. But I think it is better option than rewriting the program into Erlang-style actors. The big portions of the program could remain synchronous ones, but for other parts this is less painful than Erlang-style actors and less painful then using monitors.

Updated: Fixed the samples to match description and some typos

I think this is in agreement

I think this is in agreement with what I wrote, right?

The syntax is obfuscating my understanding of the value semantics for streaming however. Does "all for ... { }" return a stream (of anything), and "fold () { }" take a stream and return a promise? This is very much on the path towards the type of operator Naasking and I are advocating :)

What are the synchrony guarantees (e.g., synchrony hypothesis)? For example, if multiple promises are waiting on the same promise, and the base promise resolves, am I guaranteed that all of those promises will run before any subsequent promises?

What are the synchrony

What are the synchrony guarantees (e.g., synchrony hypothesis)? For example, if multiple promises are waiting on the same promise, and the base promise resolves, am I guaranteed that all of those promises will run before any subsequent promises?

Since Constantine is depending on Vats/event loops, only the promise streams within a vat would satisfy synchrony. Streams that cross vats would only be eventually consistent.

Also, your link is broken. Here's the fixed link.

For the same-vat case,

For the same-vat case, what's the propagation guarantee across a DAG of promises?

For the cross-vat case, what is the intuition for the proof of eventual consistency? Something like a guarantee on the order of messages sent directly from one vat to another? If that's it, I thought a programmer would still have to do more work for eventual consistency.

Nice to finally have a clear answer on these things :)

Promise and Vat guarantees

I have described some of these guarantees in the guide. They are practically the same as E.

The same chapter of the guide discusses promises. Note that the Promise is the normal component lives in the vat. From other vat it is possible to access promise only using resolver.

When request/response method is invoked, firstly a promise is created, then the message object is created that references resolver of the promise, the message is sent to the vat of target object, then created promise is returned to the invoker.

When the message is dispatched to the target vat, the method is invoked that creates promise as result. And resolver from the origianl promise is registered as listener to the new promise. After new promise is resolved, the resolver is notified in the original vat, where it notifies all listeners that were registered with that promise (and these listeners resolvers for other promises in other vats).

In early versions of the framework (Java version), it was hard to understand that actual promise objects should not be directly shared between different vats. After I have done it, the framework and its testing were greatly simplified.

I don't see how this answers

Edit: I didn't find these answers clear. Anybody who is interested should check out this paper. I don't think there are many guarantees about consistency wrt side effects, just about deadlock (livelock remains, and now we have something called 'datalock'). Properties like eventual consistency, esp. if we talk about data invariants, seem to be at a higher level.

Years ago, I was trying to figure out how to add transactions to FRP to fix many of these problems. I believe some of Jonathan Edward's work on 'coherence' can, in a weird sense, be thought of as along the same lines.

Consistency with Vats

E does offer: weak ordering guarantees for communication on far references, determinism within the vat, and simple guarantees on failures for far refs (i.e. if one message fails, all subsequent messages fail). The queuing discipline within a vat is also predictable. In practice, developers can achieve the consistency they need without too much effort. If they want want eventual consistency, they must apply some self discipline, i.e. favoring commutative, monotonic messages.

I also pursued transactions for my earlier efforts at parallel RDP (not FRP, but similar), but the vat-like approaches have proven both easier to use and to perform better.

I've found a useful technique - clocked vats, each vat allows as `drift` relative to other vats on the same clock. For example, if a vat named Wanda is at time 300, she might tell the clock to not allow anyone else to reach time 310. If combined with logical delay (do X at time T+10) this technique can shift EC back to true deterministic parallelism. The `drift` makes parallelism coarse-grained, supporting an easily tunable tradeoff between efficiency, consistency, and latency.

It turns out the implicit batching, triggered on a clock, is powerful for both efficiency and consistency: Each vat output groups of messages only at the end of each instant, and processes inputs only at the beginning of each instant. This offers snapshot consistency between vats, and hides temporary internal inconsistencies within each vat. This is a very powerful weapon against glitches.

For distributed computation, I can conveniently replace "waiting on a common clock" with "logical disruption of communication" (which is expressed via proxy behaviors). That way I'm still wait-free and deterministic up-to-disruption. The burden of recognizing and recovering from disruption is then shifted back to the developer, where my resilient RDP paradigm makes it a very easy burden.

If you're interested in highly parallel implementations of FRP, I'd strongly recommend working with vats, and clocked vats in particular.

I do not use promises for any of this. Nor do I recommend them.

Yeah, all these notions of

Yeah, all these notions of clocked vats etc. are what I'm worried about in the cross-vat scenario.

Within a vat, if a programmer mistakenly uses a side-effect in reacting to a promise being resolved, I think it's as problematic as in the current FRP scenario,

Cause and Side-effect

I understand. Side-effects from observers can lead to unpredictable causal relationships - indirectly, through references on shared state or resources.

But I think it's hyperbole to say "as problematic as".

Promises are at least single-assignment, so we can be sure that earlier observers don't change the observations - no reentrancy issues. Sure, in a poor design the resolution of a promise might be impacted by seemingly unrelated events. But we can reason about that, too, by independent mechanism - clear, causal relationships can be enforced by the object capability model.

I used clocked vats more as a substrate for my reactive model. My intent was that programmers only be exposed directly to vats for FFI/Legacy integration or creating new `primitive` behaviors. Though, I've recently started a more simplistic RDP implementation and might not expose vats to developers at all.

all for

The operator "all for" does not creates an explicit stream, it iterates collection and starts all asynchronous operations at the same time (and these operations return promises), then waits for result and fold collapses them into the single value when they become available. The intermediate results exist as a tree of unresolved promises in memory. There could be a "seq for" analog that waits for iteration to complete before starting next. It might be simpler to understand for non-loop version of "all" operator.

all {
 operation(1)
} and {
 operation(2)
}

This form will starts both asynchronous operations, and when these operations complete, resolves that operation result promise with tuple.

And "fold" is par of "all for" operator.

There is also library support for the streams in AsyncScala.

So "all" returns "Array 'a"

So "all" returns "Array 'a" rather than "Array (Promise ('a))" or "Promise (Array ('a))"? In a sense, this ordering of types is in an increasing order of flexibility :)

"all for ... fold ..."

"all for ... fold ..." is a single operator like "if ... then ... else ...". It might be possible to make it orithogonal, but from the implementation and usage experience, it caused more problems then solves. For stuations when stream of values is needed, there are usually additional ordering conditions, which are best handled by explicit stream abstraction (and these streams also have sequential and interleaving versions of the fold). The idea of the all operator is that it allows to wait for all branches that are executed in interleaving fashion. The order of completion is not important, but we need to ensure that all of the have completed.

In AsyncScala, aAllFor(collection, closure) returns a builder for the loop operator. Neither array of promises nor promise of array is a result of operator. The system of promises is created and folded on the air without storing them into itermediate structure. You could see a similar techniquie in queue sample from Q javascript library.

And there are predefined folds to lists and and unit which are used most often. AFAIR the fold to unit type was most used in practice for IO applications.

Non-loop verion of all operator returns a promise for tuple.

The Q library is nice :)

The Q library is nice :)

depends on thread efficiency

Hewitt: Futures are significantly simpler than promises.

I read this as saying "blocking is significantly simpler than non-blocking", which is true. Most of Const(antine)'s remarks match this understanding. I'm really interested in this sub-thread, so I only aim to encourage more discussion below. Note non-blocking means async, while blocking roughly means synchronous.

(I only barely follow the first post distinguishing dimensions of steps, work, and processes, and that's why I haven't said anything yet. Since I don't plan to learn about E, there's not much I can contribute when E is part of the main context. I work in distributed async C which seems insanely complex when I'm not feeling charitable in the middle of analyzing tough bugs.)

Blocking is always with respect to a scheduler. For blocking system calls, the scheduler is a system scheduler. Under native threads, blocking is with respect to a thread scheduler -- probably still an OS scheduler as just noted.

Under lightweight green threads, or any kind of single-threaded multiplexer of continuations or network finite state machines, blocking is with respect to a single-threaded user space scheduler driving the engine. And if running in a real-time process, you're not supposed to make system-blocking calls as per the last paragraph, since that would stall the entire green thread engine.

Unfortunately blocking means both things (system and user), so it would be nice to have two different words, but we don't really. Maybe folks can remember to allow both in discussion. Maybe terms system-block and green-block are helpful.

Futures that system-block are expensive, because native thread stacks are expensive in space footprint, typically at least many kilobytes in size -- even megabytes. (This is what Const was saying.) And system context switches can be expensive compared to non-blocking schemes to do fine-grained work between system context switches.

But you can also implement futures that green-block, and then they're basically just as efficient as any other user-space non-blocking mechanism, because it's just syntax or lightweight code organization on top of non-blocking user-space tools. A green thread stack can be very small, easily a thousand times smaller that native thread stacks on average. For example, at least one per network connection is a fine idea, even if you have many thousands of them.

With a non-blocking async api (of whatever flavor), you either poll or get notified. And either way you can fire callbacks or awaken blocked green threads. In this context, making a green thread runnable is just a slightly indirect way to invoke a continuation as a callback. It only adds significant latency if another wait occurs once runnable. (And this is easy to do unecessarily, by mistake, yes.)

Anyway, I'd say futures are efficient if and only if threads (or their local moral equivalent) are efficient. To address practical usage concerns, it also must be cheap to kill threads or interrupt waits based on timeouts to respond to deadlocks or other problems.

Split stacks

native thread stacks are expensive in space footprint, typically at least many kilobytes in size -- even megabytes

No longer, with split stacks. [Previously.]

discontiguous is useful

Yes, split stacks are neat: good idea to note them again. C does not require stacks be contiguous, despite pervasive convention. I did not insert parenthetical "(normally)" or "(usually)" in my comment when I said native stacks were expensive. Here brevity assumes convention.

The first two words of your comment are correct only when split stacks are a free choice -- for example, if split stacks are pervasive. So here your brevity implies falsehood. But I get your drift.

Green threads

As I understan the problem with green threads is that it is quite hard to develop own non-blocking libraries that plays by rules of the green threads. Also green threads do not specify well the possible points of interruption. So it is not clear at which points the component must maintain the invariants.

As for usuability of non-blocking API, I have provided more links at my other comment. It contains a more language neutral description of the operators. I think that with the right set asynchronus operators, usuablity of non-blocking API is greater, particularly if we consider both service provider and service consumer sides.

hard development

const: hard to develop own non-blocking libraries that plays by rules of the green threads.

Yes; it's easier if you develop both the libraries and the green threads, but still hard -- or at least really ugly which is about the same thing. I've been thinking about that. I can't tell whether I was thinking about it before this discussion and brought it to the foreground, or whether new ideas started fresh. I'll note them at end below.

Regarding points of interruption, the style of green thread I know is single-threaded and hence cooperatively scheduled, so you can pick possible points of interruption. Those points correspond to async calls in my code. (If you don't make an outbound async call, or return from one or yield, then you can't be interrupted, so critical sections are trivial to protect.) Blocking system calls are single-threaded queueing requests to a thread pool where a worker thread can block on your behalf, then notify you afterward without blocking your engine.

Design of operator suites does seem important to end users of async api. When I bounce ideas off one coworker, he says, "What we really need is a nicely defined set of async operators." His focus is high level, so high-level guarantees in operators seem appealing.

A while ago I started revving a green thread library, and I stopped because it wasn't fun. I had assumed it would be fun, but had a funny realization as I wrote about it. I write a lot of prose at work as well as a lot of code. (I write more docs than the next twenty devs who write the most, all taken together.) Crafting explanations had become work because I do it constantly. Writing rarely seems fun any more, it simply must be done.

It was thinking about split stacks that made me notice a new plan I had to write code in C that was intended as both normal synchronous code and async green thread code, depending on whether it passed through a C-to-C compiler.

This is related to a dual train of thought, intending to write both a synchronous and async version of utilities, including a Lisp interpreter with Smalltalk class extensions. A good test technique is to do things twice but differently, then compare. A sync library would make it easier to write an async library.

Then it occurred to me: the same code might do both, if I ran the sync C code through a compiler to rewrite it in async CPS style targeting the C based green threads acting as host implementaiton of everything else. That actually sounds like fun. I haven't really had any reason to write a C parser before, so that would be new. And when the only work is rewriting for consumption by a native C compiler, all the hard parts occur there. Basically, it's just refolding the stack to work with refcounted stack frames and a trampoline.

To compile the same code as both a normal C program and as parts of green threads to run inside lightweight processes, it seems necessary to put declarative annotations in C comments for the C-to-C compiler, so it knows things like which calls are async and which calls are blocking system calls that must be routed to a thread pool, etc.

(Sorry this is long. I suspected you'd find it interesting.)

A future responds to a request with a retrun or throws

A future responds to a request with a return or throws. Those sending requests can do whatever they want with the returned value or exception. In general, those sending requests don't know exactly what is going on inside parties to which they are making the requests, e.g., the parties receiving the requests might be on different computers.

Futures vs. Promises again

There are two questions here:

  1. why it is useful?
  2. Is it possible to achieve the same result with promise, while keeping advatages of promises?

The answer to the first questions is that accessing future make concurrent program more structured and this allows reasoning about the program in the terms of tree of untis of work. Since the answer to the question "how the program works?" becomes more clear from the structure of the program. But futures make the program more deadlock-prone. Promises are less liable to it.

That gets us to the second question. The E programming langauge is the demonstration of the answer yes. In E promises are only slightly more verbose than blocking futures. And this was the gratest E innovation. You could read the relatively language-neutral description of the idea here(the set of asynchronous control flow operators over is described here). You do not need to learn a new language to read these pages. Note that these are not operators over promises, they are operators about code blocks that returs promises. Note for AsyncScala I borrow ideas from both E and Occam.

E demonstrates, that promises are very natrual and usable in distributed case (even with a very limited set of operators E offers). In AsyncScala, I have not yet implemented support for distributed case, because, in real enterprise applications, I have much problems with intra-application concurrency than with distribution. And in distributed there are very tricky issues related to the evolution of the application and application protocols that make automatic support less useful then it usually claim.

So the thesis that it is not possible for promises to be useable as futures is not supported by evidence, since there are counter-examples. A bit more verbose syntax is well compensated by the greatly reduced risk of the deadlock problems.

Deadlocking issues with Futures?

What particular deadlocking issues with futures do you have in mine?

Future deadlock issues

There are two kinds of deadlock issues related to futures that I'm most worried about.

The first deadlock issue is because while waiting for the future to resolve, the actor cannot accept other messages. This causes the problem, because the actor is only authoritative source of information about its mutable state, so none could answer to requests that involve access to the actor state. This practically forbids two insteresting kinds of behavior with actors and futures: callbacks and recursion. Even more, before using the future, the global knowledge about the program is required to determine if using the future is safe. It is required to know if initiated logical asynchronous operation involves direct or indirect message sends back to initiator of asynchronous operation. So we are kinda back to the age of early FORTRAN compilers that had similar problems with recursion as well.

The second deadlock issue is because while waiting for the future actor occupies logical or real thread. This issue is implementation dependent, but there is a worrying trend in this direction. This issue is happens when limited thread pools are used, like Scala fork/join thread pool for the actors that is enabled by default. If we have 8 threads in such thread pool, and we have 8 actors blocking on the futures, no new events could be dispatched to any other actors, since there is no more threads.

And even thread pool is unlimited, starting a new thread takes time and consume resources. And global GC each few seconds is not that much differrent from deadlock.

Actors are *very* abstract

There is nothing that says that an Actor cannot process a new message while other processing is occurring in the holes in the cheese.

Efficiently implementing actors requires sophisticated engineering.

Efficiently implementing

Efficiently implementing actors requires sophisticated engineering.

So does effectively using them at non-trivial scales.

Makes me somewhat uncomfortable with the paradigm.

Many-core computing is not for the faint of heart

Exponentially increasing computation will continue for at least another decade imposing increasingly demanding engineering requirements.

Consequently, practice will necessarily become increasingly sophisticated. Of course, we need to be able explain it as simply as possible to non-practictioners.

Not Necessarily

You resign yourself too easily to a fate of growing complexity.

Even need we relinquish determinism, consistency, predictable timing at a global scale, there is little reason to roll over and abandon them locally and without a fight the way actors model does.

There are better tools than actors for controlling parallel and distributed systems. Lightweight time warp protocols. Dataflows and pipelines. Event calculus. Bloom and Dedalus. Most of them involve temporal semantics in some variation, because computing needs time.

Not Relevant

State being global is not the problem. Making state local is not the solution.

State being unpredictable is the problem. Inconsistency between observers is the problem. Maintaining determinism in presence of program modularity and composition is the problem.

To win such features in actors model requires fighting the system with serializer patterns and similar, and too easily reintroduces the problems of deadly embrace that people were aiming to avoid by selecting actors model.

Indeterminacy and inconsistency are the norm

Indeterminacy and inconsistency are the norm. Denial and attempting suppression of these norms is futile. Inconsistency Robustness is the answer.

Insisting on complete determinism and consistency is self-defeating.

Essential indeterminism and

Essential indeterminism and inconsistency is orders of magnitude less than is casually introduced by actors model. There is a difference between tolerating a mess and creating one.

To suppress accidental and unnecessary sources of inconsistency or indeterminism is not futile. Further, even for the essential sort, we can control where inconsistency is observed, where indeterminism is introduced, how they are realized and experienced.

Inconsistency robustness is not the only answer. An alternative to tolerating inconsistency is to break in a consistent way, then recover in a consistent way - e.g. resilient, crash-only software. Another alternative is to resolve apparent inconsistencies in an arbitrary but deterministic way - e.g. if simultaneously told to turn both left and right, favor left.

Actors and Actors with Futures are different

BTW do you have a mathematical definition of actor model? So far I have seen definitions only in plain English (for example in "Actor Model of Computation: Scalable Robust Information Systems"), that leaves many points unformalized and undefined.

A most interesting undefined point is whether actor could start handling the next message before completely responding to the previous message. It seems it is allowed after handler for the next message is set. But it makes reasoning about actors quite hairy, since output messages from the handling the previous message (after next handler is set) could be sent later than messages from the next next message. And it is not clear whether the handler for the next message could be set multiple times.

Also, please note that there is no futures in the core actor model as you define it in the article. There are only one-way messages. The futures might be built above one-way messages (as required by actor model), just like promises. But unless their semantics is specified, it is quite useless to discuss whether we can handle messages while waiting for them.

The resonalbe translation of a future to the actor model with one-way messages is a single assignment component (basically a Promise). That allows to set value using a one message, and to retrieve the value using sending request (which is efficiently a listener for the future, since we do not know the time when it resolves) and receiving the value some time later. But this model assumes that this future will handle incoming requests sequentially.

The actor-based language could rewrite listening for the future by splitting code into the two parts, the part before the value from the future is required, and the part after value from the future is required. And then start listening for future resolution in order to execute continuation.

If this is variant, that you have in the mind, then, yes, it could handle other messages while waiting. However, there we have here an implicit listener created by compiler, in order to translate futures that looks blocking into one-way messages.

Since we need to perform such global CPS rewrite of the program in order to support futures over actor model with one-way languages, we get a higher level model then actor model. Which properties are not generally the same as properties of the actor model.

This is just like the properties of normal parallel and sequential programming with locks and semaphores are not the same as properties of actor model despite of the fact that all such programs could be tranformed to the actors using compilers (and actually locks and semaphores are implemented on some operating systems using message sends to the kernel, such such translations are actually implemented). So you could not generally claim that all properties of the pure actor model are applicable to the extended actor model with futures. The properties should be still specified and proved. For example, actors with futures will have a different induction principle, since handing event is now multi-step process because actor state now might be different before and after the future.

And after we have performed CSP rewrite in order to support futures, we have situation that by usability is not much different from the E-style promise-based programming with event loops. The key difference point is whether continuation point is cut off implicitly or explicitly. With futures with have an implicit cut off, that saves on typing and make code more "clean". With E-style promises we have explicit cut off. It require more typing, but it clearly specifies that the rest of the code could be executed at later time something could already change at that point, so please take care. So I think that E and AsyncScala approach is better than implicit translation of futures, because it there are much less surprises for the programmer at small cost of a bit more typing.

But there is even tricky issues that are lurking when the actors with futures are translated to plain actors. We have a situation where actor is potenitally waiting for several events (resolutions of futures and normal events). It is not clear what will happen next, so the actor state should modified not just by setting next handler, but using some operations that allow making incremental updates to active handler sets and incremental updates to the state. E-style actors are designed to handle it very well, since the processing of events within vat (that corresponds to the actor) allows the modular event handling from start. For actors with futures, some compiler trickery seems to be required (by possibly using E-like approach inside).

Futures are Actors

A first approximation definition of the future construct is as follows:

“future” expression ≡ (| eval (environment) → expression.eval(environment) ?? (value → (| message → value..message |), catch exception → (| message → throw exception |) ) |)

However, there are sophisticated run-time considerations in implementing the above.

There are many ways to formalize the Actor Model including operational and denotational. See the references in Actor Model of Computation: Scalable Robust Information Systems.

Could please specify which

Could please specify which works do you have in mind on actor sematics? I'm particularly interested in ones that formalize the futures in the way you are using it. Some works that I have checked like "Foundations of Actor Semantics" do not seems to formalize futures. I'm also interested if the description of the futures in the actor model is adequqate on the wikipedia. It would be very nice if you will provide some references there, since that section of wikipedia pages is still without confirming references.

I do no see how futures are better than promises as they are implemetned in E. E also allows sending requests to not yet resolved promises. So far I do not understand why you claim that futures are simpler than promises.

What is the definition of a promise?

Given that a future has a very simple definition, is there any corresponding simple definition for a promise?

Definition of promise

Note, that you have given only partial definition of the future. The other part is defined by future-aware compiler. Which is as you have said is tricky to implement (ActorScript compiler has to be really smart to make sure that at least arithmetic is efficiently implemented since everything seems to be concurrent and futures by default).

Promises are implemented in library and compiler in E as far as I know. And they are implemented as plain library in AsyncScala. The implementation in Scala is quite simple (the essential methods are "listen" and "resolver" all other are utility methods). Making promise to behave as a proxy for the resolution is not so complex either. AsyncScala does not supports it yet, but I have previously implemented it in Java (code is heavily optimized, so it is not readable as it could be, compare it with the proxy implemented in Scala).

Note that there is additional factor that affects complexity of base components. AsyncScala offers static typing for the components, and because I do not modify compiler, so it requires to have an interface for each asynchronous component that can be used from other vats. So contract of the asynchronous component is well defined. ActorScript seems to be based on dynamic typing with respect to messages. I currently do see how the simple definition of the future actor would be possible for static type systems.

The open question how the future actually works on both implementation side and compiler side, since you have not yet provided a reference to formalization of it. I have impression that you are using futures in your definition of the future. For example, it seems that "??" operation have to resolve the future, if the left side is a future, so the value can be tested. But there is no "resolve" operation in your definition of the future. If left side could not be a future, than futures looks like not so composeable.

Complexity of promises vs. simplicity of futures

Going forward does the complexity and verbosity of promises provide any real advantage over the conceptual and expressive simplicity of futures?

Of course, run time optimizations are important. But these optimizations should only make programs run faster.

Complexity and verbosity of promises

Why do you think that promises are more verbose and complex? If you would implement futures in some host language like Scala (or Java for more difficult challenge), do you think that the futures with same semantics will be less verbose? Will such futures support type safety?

The complexity of future in your example is hidden by compiler(that has unknown to me complexity, but possibly a quite high one) and library. And you seems to be using futures to implement future (and if it so, that is not fair for comparison all). The complexity of promises could be hidden as well provided a good compiler is used.

But what is really important is usage rather than internal implementation. And even in Scala, the usage is quite simple. For example, echo server over the sockets is quite trivial. Or you could provide a example of actor-based component that uses futures, so we could compare complexity implementing the same idea with promises. So far the claim about promise complexity does not look justified to me, even if we use promises in Scala that does not have a native support for them.

For example the following is a re-implementation of one of your examples using AsyncScala.

trait Counter { // trait(interface) is mandatory because I do not make changes to Scala language, but it also useful for declaring published operations
  def go : Promise[Unit]
  def stop : Promise[Integer]
}
class CounterImpl(var counter = 0) {
  var stopped = false;
  def go = { 
    aSeqLoop { 
      // this loop runs body in different turns while result promise resolves to true, the loop returns a promise
      // the loop process is interleaved with other operations in the same vat
      // so stop message could be received between iterations.
      if(stopped) {false} else {count++;true}
    }
  }
  def stop = {
    stopped = true // go operation will stop on next turn
    counter
  }
}
def waitSampleCounter() : Promise[Unit] = {
  // creating object with asynchronous proxy, having a compliler could simplify this expression greatly
  val sampleValue = ObjectUtil.export(classOf[Counter], new CounterImpl(0))
  // observe method just adds listener to the promise
  sampleValue.go.observe(x => print("counter stopped ") }
  // the line above is not blocking, so the message is scheduled, and code proceeds to the next line
  // map returns promise that is result of map operation, 
  // in this case a promise that resolves after value was printed
  sampleValue.stop().map(x => print(x))
  // the result of the method is promise resolved on the previous line
}

I think that the sample is simpler and easier to understand for mainstream programmers, than what you provide in the article. The code is simpler and more straightforward. It even provide additional feature that your code does not seem to provide. It allows to find out when process started by go operation finished.

Note while component is using mutable state, the usage of the variables is safe if created proxy is used by clients, since components live in the vat and vat dispatches only one event at time. aSeqLoop operator produces a multiple events (an event per iteration), so it does not block receiving stop operation.

Simplicity and conciseness of futures

Below is an implementation using a future that is much more concise and conceptually simpler

Counter ≡ actor(count ↦Integer) continue ←true (|

stopcount also continue ←false,
gocontinue ?? (true → future go also countcount +1, false → void) |)

Note that above implementation is referentially transparent in that a variable does not change value within a scope. (An assigned value is visible only to the next message received.)

Possibly too small sample

Below is an implementation using a future that is much more concise and conceptually simpler

And practically the same could be written in AsyncScala:

class CounterImpl2(var count: Integer) {
  var stopped = false
  def stop = {stopped = true;count}
  def go = {if(!stopped) {count = count + 1;aLater{go}}}
}

If we drop out keywords, we receive the parctically the same complexity as in your version. And I think that dropping keywords is valid for this comparison, since AsyncScala does not modify scala compiler, and we comparing complexity of ideas rather than complexity of surface syntax or count of new lines.

This version is less efficient right now then version above in the current implementation of AsyncScala, since go builds a chain of promises to be resolved. This is planned to be optimized out later. If go is made oneway operation rather than returning void value that could be waited for, more efficient version is available:

class CounterImpl2(var count: Integer) {
  var stopped = false
  def stop = {stopped = true;count}
  def go {if(!stopped) {count = count + 1;aSend{go}}}
}

So the code does not demonstrate advantages over promises. Do you have some more extensive sample with a clear semantics to compare complexity.

Note that above implementation is referentially transparent in that a variable does not change value within a scope. (An assigned value is visible only to the next message received.)

So what? In your code change of variable looks is assignment in surface syntax, and likely you impelmented as assignment when transalted to underlying language for performance reasons. It is only referentially transparent on intermediate translation layer, and it behaves somewhat surprising to people that will come from mainstream languages like Java, the thing that looks like assignment suddently does not have effect in some situations.

It might be simpler to have a formal proofs about actors using it. But does it makes informal reasoning easier? If we have stateful actors which mutable state is protected by framework, while not model state explicitly using variables and stateful objects? This would be more modular than forcing update update of variables at the end of the work on the message. Referentially transparency looks like a trade off to me. It makes some things easier and some things more complex. It should be carefully considered in each context.

Simplicity of futures

What are the formal definitions of aLater and aSend? Also, how many more of such language constructs are required?

aLater and aSend

Strictly speacking they are not true primitives. The primitive operation is only one enqueing an action to the vat. The operations aSend and aLater are layered above it, and it is described in this section of the guide. This is like loop forms and goto, asynchronous control flow operators are built upon one way message sends.

aSend {block} enqueues action with the current vat and is basically is

  Vat.current.enqueue {() => block}

aLater {block} is a bit more tricky since it uses promises. The operation creates proimse immediately and than sends message to the current vat that initiave asynchronous operation that returns promise as well, then registers resolver from original promise as listener to new promise. If block thown exception, then original resolver is smashed with exception as well.

  def aLater[T](vat: vats.Vat)(f: => Promise[T]): Promise[T] = {
    val rc =  new Promise[T]
    val resolver = rc.resolver()
    vat.enqueue {()=>
      try {
        block().listen(resolver)
      } catch {
        ex => resolver.apply(Failure(ex))
      }
    }
    rc
  }
  def aLater[T](f: => Promise[T]): Promise[T] = {
    aLater(Vat.current)(f)
  }

The abstract set of control flow operators is described here. In AsyncScala all of them (except for loop forms of any) are implemented as library.