Promises/Futures with callbacks

[Stuart Sierra]

I've been working on this off and on for a while. It feels like it's needed.

Design page: http://dev.clojure.org/display/design/Promises

My implementation: https://github.com/stuartsierra/cljque/blob/promises/src/cljque/promises.clj

I haven't figured out all the details, but I wanted to get the discussion started. What other capabilities would be needed at the core?

-S

[Timothy Baldridge]

This interface looks a lot like the one used for add-watch. Could we possibly use it instead?

Timothy

-S

--
You received this message because you are subscribed to the Google Groups "Clojure Dev" group.
To view this discussion on the web visit https://groups.google.com/d/msg/clojure-dev/-/XD1hnBvjNt8J.
To post to this group, send email to cloju...@googlegroups.com.
To unsubscribe from this group, send email to clojure-dev...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/clojure-dev?hl=en.

--
“One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.”
(Robert Firth)

[Ivan Kozik]

On Sun, Nov 25, 2012 at 2:06 AM, Stuart Sierra
<the.stua...@gmail.com> wrote:
> Design page: http://dev.clojure.org/display/design/Promises

"The callback is responsible for calling deref on the promise." is
very clever approach and I think I'll like it a lot.

> I haven't figured out all the details, but I wanted to get the discussion
> started. What other capabilities would be needed at the core?

In Twisted, Deferreds acquired[1] a notion of cancellation after many
years without .cancel(), and it has since been found quite useful. I
use .cancel() in both my Twisted code and client-side
goog.async.Deferred-using code.

Cancellation allows the user of a promise-returning function to say
"actually, I don't need the result any more, stop doing work if you
can" (call the canceller function if the promise has one). The
canceller function can do things like abort an in-progress HTTP
request.

Ivan

[1] https://twistedmatrix.com/trac/ticket/990

[Sean Corfield]

I assume 'follow' should be 'attend' (and 'retry-operation' should be 'do-operation') in the code example?

Being able to call a function when a future completes looks very useful. I like it.

Does 'attend' return a new object that wraps the original promise/future or does it modify the underlying object? If the latter, what happens if it is called multiple times? If the former, what happens if you deliver the original promise... and then call deliver on the wrapped object?

[Brandon Bloom]

> What other capabilities would be needed at the core?

Have you thought much about cancelation?

Although a bit complex, the .NET Parallel Extensions have a pretty complete cancellation story:

http://msdn.microsoft.com/en-us/library/dd997364.aspx

The interesting bit is that you should be able to cancel a process tree via a top-level promise. However, .NET's model is co-operative; subprocesses can choose to be non-cancelable, unlike a unix process. Just like push-sequences are like inside-out pull-sequences, cancellation is a bit like outside-in exceptions.

[Brandon Bloom]

> "The callback is responsible for calling deref on the promise."

I agree that this is a decent approach. Referring back to the design page, this is choice #3. Here are the three possibilities again:

1. Provide separate callback attachment points for success and failure
2. Pass the exception to the callback as a normal value
3. Wrap the value or exception in a union type

I agree that 1 is ugly to compose and 2 is makes differentiating failure impossible.

It makes me wish there was a magic #4 choice: Force a function to immediately receive an exception upon invocation.

Right now, this is invalid Clojure:

(defn f [x] (catch Exception e))

(you need a try form)

In Ruby, there is an implicit block around the method of each body.

def f(x)

rescue Exception => e

end

(Ruby uses begin/rescue/ensure instead of try/catch/finally. There is also "else" for when no exception occurs.)

Right now, IFn provides one method: invoke. It would be interesting if it also provided a raise(Excepetion) method.

I'm on-and-off-again working on a CPS transform for the CLJS analyzer. I planned to reify Continuations as a protocol with two methods: 'return and 'raise. This is the same as option #1 above. The reason I don't care about composition ugliness is because it's mostly generated by the AST transform. Additionally, there is some performance gains to be had by avoiding extra try/catch blocks in JavaScript and by reusing one of the two callbacks when creating a new continuation for a later function call. I expected to define Tasks (promises with a callback) in terms of continuations using #3 and then to define Clojure's current promises as (defn promise [] (task deref))

[tomoj]

So in cljs, promises will implement IDeref by throwing an exception when unrealized?

[Stuart Sierra]

Timothy Baldridge wrote:
> This interface looks a lot like the one used for
> add-watch. Could we possibly use it instead?

I thought about this when I was working on it. It's true
that `attend` is similar in spirit to `add-watch`, but the
semantics of the callback function are quite different.

The signature of the `add-watch` callback function is

    [key reference old-value new-value]

The old-value has no meaning for promise/future, and
supplying the new-value doesn't force the caller to
dereference the promise to throw exceptions.

Secondly, `add-watch` assumes a the callback can be called
more than once, which is not the case with promise/future.
`remove-watch` would have no real meaning, except in the
case of cancellation, which I will answer separately.

-S

[Stuart Sierra]

Sean Corfield wrote:
> I assume 'follow' should be 'attend' (and
> 'retry-operation' should be 'do-operation') in the code
> example?

`follow` was a variant of `attend` in my implementation.
I'll fix the example.

> Does 'attend' return a new object that wraps the original
> promise/future or does it modify the underlying object? If
> the latter, what happens if it is called multiple times?
> If the former, what happens if you deliver the original
> promise... and then call deliver on the wrapped object?

`attend` modifies the promise. The promise stores a
collection of callback functions to be executed when it is
delivered.

-S

[Stuart Sierra]

Brandon Bloom wrote:
> Have you thought much about cancelation?

I have thought about it a little. In my current
implementation, you cannot directly cancel a callback
created with `attend`, which is a low-level operation.

Instead, the `on` macro returns another promise which is the
result of the callback function. If you `deliver` to that
returned promise before the original promise is delivered,
the callback function is never run. This effectively allows
you to cancel the callback.

-S

[Stuart Sierra]

tomoj wrote:
> So in cljs, promises will implement IDeref by throwing an
> exception when unrealized?

That's a good question. I want this feature to be available
in ClojureScript, but I haven't yet considered all the
implications for the API.

The ClojureScript API for promises would have to be slightly
different because the host environment is single-threaded.
Since it is impossible to block a thread in JavaScript, I
think that `deref` on a promise that has no value would have
to throw an exception.

JavaScript has no concept of executors, so callback
functions would be invoked synchronously or with
setTimeout(f, 0).

-S

[Stuart Sierra]

Brandon Bloom wrote:
> It makes me wish there was a magic #4 choice: Force a
> function to immediately receive an exception upon
> invocation.

I was wishing for that too, but I don't think it's possible
without fundamentally altering Clojure's function invocation
semantics. That is a larger change than I am willing to
tackle for this project.

-S

[Sean Corfield]

On Sun, Nov 25, 2012 at 7:03 AM, Stuart Sierra <the.stua...@gmail.com> wrote:

`follow` was a variant of `attend` in my implementation.

I'll fix the example.

'kthx.

`attend` modifies the promise. The promise stores a

collection of callback functions to be executed when it is
delivered.

Is this collection ordered or unordered? Can the same callback be 'attended' multiple times?

-- 

Sean A Corfield -- (904) 302-SEAN
An Architect's View -- http://corfield.org/
World Singles, LLC. -- http://worldsingles.com/

"Perfection is the enemy of the good."
-- Gustave Flaubert, French realist novelist (1821-1880)

[Stuart Sierra]

I wrote:
> `attend` modifies the promise. The promise stores a
> collection of callback functions to be executed when it is
> delivered.

Sean Corfield wrote:
> Is this collection ordered or unordered? Can the same
> callback be 'attended' multiple times?

In my implementation it's a vector, so calling `attend`
multiple times just adds on to end of the vector. Calling
`attend` twice with the same function creates two separate
callbacks. Again, `attend` is a low-level primitive. User
code will normally call a macro like `on` or `then`.

I don't want to make any guarantees about the order in which
callbacks will be *executed*, because they may be running
simultaneously on different threads.

-S

[Sean Corfield]

On Sun, Nov 25, 2012 at 7:42 AM, Stuart Sierra <the.stua...@gmail.com> wrote:

In my implementation it's a vector, so calling `attend`

multiple times just adds on to end of the vector. Calling
`attend` twice with the same function creates two separate
callbacks. Again, `attend` is a low-level primitive. User
code will normally call a macro like `on` or `then`.

OK.

 

I don't want to make any guarantees about the order in which
callbacks will be *executed*, because they may be running
simultaneously on different threads.

Got it. That answers all of my questions so far. Thanx!

-- 

[Brandon Bloom]

Instead, the `on` macro returns another promise which is the
result of the callback function. If you `deliver` to that
returned promise before the original promise is delivered,
the callback function is never run. This effectively allows
you to cancel the callback.

Does that propagate the cancelation in anyway? If you have a multi-step asynchronous operation, you need a way to cancel the whole operation during an intermediate step.

[Brandon Bloom]

What about dynamic bindings? Should the 'on, 'then, and other macros use 'bound-fn ?

[Stuart Sierra]

I wrote:
> If you `deliver` to that returned promise before the
> original promise is delivered, the callback function is
> never run. This effectively allows you to cancel the
> callback.

Brandon Bloom wrote:
> Does that propagate the cancelation in any way? If you

> have a multi-step asynchronous operation, you need a way
> to cancel the whole operation during an intermediate step.

As I've conceived it, promises are containers for values,
not processes. I think managing processes is a separate
concern which is outside the scope of what I am proposing.
But I don't think that anything here would prevent you from
implementing a cancellation policy.

If you `deliver` a value to a promise, any "downstream"
promises dependent on it will be executed. If you `fail` the
promise with an exception, those downstream promises will
also fail. So in that sense, if you choose a special value
or exception to indicate cancellation, then that
cancellation will be propagated.

What promises cannot do is propagate values or exceptions
"upstream" to promises from which they were derived. For
that, you would need a separate mechanism to communicate the
cancellation request. You could use an atom for this, or
even a another promise!

Futures can still be cancelled with future-cancel; this
proposal does not change that.

-S

[Stuart Sierra]

Brandon Bloom wrote:
> What about dynamic bindings? Should the 'on, 'then, and
> other macros use 'bound-fn ?

Ideally, the behavior of dynamic bindings in promise
callbacks would be consistent with other Clojure forms that
start asynchronous operations.

If this proposal for promises were added to clojure.core, it
could use the private function `binding-conveyer-fn`.

If promises are provided as a standalone library, they can
use `bound-fn`, but I would be tempted to leave that up to
users. It's more efficient not to wrap every callback in
`bound-fn`, and you can still call it explicitly when you
need to.

-S

[Tom Jack]

> (let [p (promise)] @(future (on [v p] v)))
#<Promise@6d165270: :pending>

Is this intended, or a bug? Like with `on`, I expected to be able to
return a promise and have it auto-trampolined. But I can imagine that
futures were supposed to be this way, and that one should do `@(future
@(on [v p] v)))` instead?

[Stuart Sierra]

I think it's a bug. I've fixed it in my latest commit:
https://github.com/stuartsierra/cljque/commit/e32353924e4e7ed800df2b201c824e53a16972e9

My intent with this project is to unify Promises and Futures
under the same API. But you could also argue that Futures
are different so they should not have the same
"auto-trampoline" behavior.

-S

[tomoj]

I noticed "there is no notion of executors" and "Callbacks execute either synchronously or asynchronously (e.g., with setTimeout)" in the ClojureScript section of your wiki page. I'm curious what this might look like, and whether this has any implications for cljque on the JVM.

If you squint, the executor parameter in cljque looks like Rx's IScheduler. In Rx this is an important spot for parametrization — e.g. the choice of whether to run callbacks synchronously or asynchronously via setTimeout (or process.nextTick, or requestAnimationFrame, or MessageChannel...) could be a choice of which IScheduler implementation to use. IScheduler also includes analogues to ScheduledExecutorService methods, a state parameter that isn't relevant to us, and cooperation with IDisposable for cancelling a scheduled action (and its 'children').

One way to do some of this kind of parametrization in cljque (assuming you don't want to implement ExecutorService) is to set *callback-executor* to nil, and just apply transformation functions to callbacks. You could do this in a ClojureScript port of cljque, assuming callbacks are always called synchronously (as if *callback-executor* were always nil). E.g.: (fn next-tick [f] (fn [p] (.nextTick js/process #(f p)))), then (attend promise (next-tick f)). In my promise library, I make *callback-executor* such a transformation function ("callback middleware"?), and allow passing an override middleware rather than an executor: (attend promise f next-tick).

I wonder, though, whether it may make sense to implement a protocol (or two?) analogous to IScheduler, allowing (on the JVM) both ExecutorServices and bits of Clojure(Script) to participate. I have sometimes called it "IInvoker".


Is there any particular reason you chose to put the "auto-trampoline" ("auto-join" is probably a better term) on the deliver side? In my promise library, I put this on the attend side, which makes it implementable (and removable and customizable) via callback middleware. I'm not sure why you'd want to be able to turn this off or hook into it. I've struggled for a while with the question of whether to allow turning this behavior off (or whether to have this behavior at all!) in a promise library. It makes promises violate the monad laws, but I haven't been able to think of any cases where it seems to cause real trouble. I do have a use case where I want callback middleware to see every intermediate promise, which in cljque would require using a custom deliver which just calls -deliver (and custom then/recover), but this use case doesn't make much sense for cljque's promises. I could imagine doing something somewhat similar with custom INotify implementations, but I suspect this use case is irrelevant for cljque. I wonder if there really are no relevant use cases?


A couple minor notes:

1) I think v/q/e need to be :volatile-mutable? I had what seemed like a concurrency bug which was fixed by making this change, but I didn't save the code. The problem I imagine is that, despite the locking in Promise, without volatile, threads may see old values for v/q/e, dropping callbacks, calling callbacks more than once, or returning nil on deref. I'm not sure about this.

2) For me, the type inferred for .submit in future-call was Runnable instead of Callable, so futures always deref'd to nil. Typehints fixed it. I'm guessing this problem only affects some Clojure versions (or some JVMs?!)

[tomoj]

Glad to see future seqs coming back. I've been thinking about their relation to IReduce (CollReduce) for a while. My conclusion so far is that future seqs, if they implement IReduce at all, must do so with synchronous semantics like other IReduces. That is, they must return whatever the reducef returns, and the reducef must never be called after reduce returns. Of course this means they would only implement IReduce on the JVM (like Seqable).

A separate protocol (which I name "IReact") analogous to IReduce can be introduced for async semantics. react returns a promise of the reduced (reacted?) value, and makes no guarantees about when the reactf will be called (alternatively, you might guarantee that the reactf will _only_ be called after react returns).

A few examples of where the conflation might cause trouble:

1) into — if 'to' is an IEditableCollection, into will call persistent! on the return value of reduce, causing an error if it's a promise.
2) r/mapcat — seems broken. I expected it to do temporal interleaving, and almost got that working (modulo inconsistency wrt time): https://www.refheap.com/paste/d9d3461738ad9a8aa23a853e5 . But this code looks wonky, and should r/mapcat do temporal interleaving on future seqs, anyway? I'd expect concatenation, with a separate operator for temporal interleaving (..or no such operator at all, given that it will not be a pure function on future seqs?).
3) r/partition-by (proposed new operator: http://dev.clojure.org/jira/browse/CLJ-991) — this will break with async-IReduce, since promises aren't PartitionBuffers (similar to the problem with into).
4) r/reductions (drafted new operator: https://gist.github.com/543a721f0f44cf48459d) — maybe there is a way to write this which avoids the problem, but as I wrote it, this will break if reducef is called after reduce returns.
5) r/take and r/drop have concurrency bugs for async-IReduce since they swap an atom and then deref it. This seems like just a bug in r/take and r/drop to me, but it doesn't matter for sync-IReduce since there will only be the one reducing thread calling the reducef.

With separation between react and reduce, you can also make react notice when the reactf returns a promise, attending on it and passing its value to the next reaction (or failing the returned promise on an error).

Unfortunately, splitting out IReact seems to require duplicating the relevant parts of clojure.core.reducers. But that sort of seems right to me — reaction is not (quite) reduction. And I don't see another viable option yet. Hopefully I'm missing something.

[Alex Miller]

Just FYI, I would love to have a talk proposal in this area for Clojure/West in Portland Mar 18-20th. 

http://clojurewest.org/call-for-presentations/

--
You received this message because you are subscribed to the Google Groups "Clojure Dev" group.

To view this discussion on the web visit https://groups.google.com/d/msg/clojure-dev/-/QTElbwzVgv8J.

[Stuart Sierra]

On Thursday, December 6, 2012 2:20:40 PM UTC-5, tomoj wrote:

I noticed "there is no notion of executors" and "Callbacks execute either synchronously or asynchronously (e.g., with setTimeout)" in the ClojureScript section of your wiki page. I'm curious what this might look like, and whether this has any implications for cljque on the JVM.

Hi tomoj,

These are all interesting questions. I'll need some more time to think about them.

-S

[Stuart Sierra]

On Thursday, December 6, 2012 5:15:22 PM UTC-5, tomoj wrote:

Glad to see future seqs coming back.

Just to be clear: Future Seqs are an idea that I've been toying with. I'm happy to discuss them with anyone who's interested.

Future Seqs are *not* part of my proposed plan for promises/futures in Clojure. I just happened to put my experimental implementations in the same GitHub repo.

-S

[Brandon Bloom]

What promises cannot do is propagate values or exceptions
"upstream" to promises from which they were derived. For
that, you would need a separate mechanism to communicate the
cancellation request. You could use an atom for this, or
even a another promise!

As excited as I am for listenable futures, I can't help but feel like we're missing an opportunity to focus on a more fundamental abstraction.

In Rich's recent Clojure eXchange talk, he mentioned Erlang and Armstrong's 2003 thesis. It had been a while since I read it, so went back and took another look. There's a lot of parallels between Erlang, Unix, .Net Parallel Extensions, etc when it comes to process model. I think, beyond simply cancelation, there is a need for process tree and supervisor abstractions. Futures, whether listenable or not, inherently imply a fork in execution code path. The notion of a hierarchy of linked processes seems to be a fundamental property of communicating sequential processes.

I realize that this may be outside the scope of your project, but I'd like the community as a large to be thinking about these things...

[Tom Jack]

Putting the auto-join on the attend side seems to make it difficult to
implement IDeref and IPending. If the join were implemented by an
executor-like, you could opt out on attend by passing nil for the
executor. But there is no way to opt out for deref or realized?, other
than binding some dynamic variable.

I still can't think of any use cases for hooking into the join for
cljque's Promise. If someone needs to do something different, they
should probably implement a new promise type, instead of trying to
shove it inside some Executor notion. I wonder, then, if the join
should be done inside Promise's -deliver, rather than in the deliver
helper, so that other promise types can customize their join if
necessary.

It could be nice if then and recover returned a promise of the same
type as the source. Otherwise we wind up with Promise everywhere and
it becomes harder to work with certain custom promise types. A
protocol similar to IEmptyableCollection might allow creating an
unrealized promise of the same type as another promise, say
(defprotocol IEmptyablePromise (empty-promise [this])). It could work
to assume that the return value is both INotify and IDeliver.
Personally I tend to prefer to separate the IDeliver and INotify
implementations (though "we're all consenting adults" is almost
convincing to me). If IDeliver had an extra function, say (notifier
[this]), which returned an INotify (and was the identity on Promise),
then empty-promise could just return an IDeliver. then-call could then
look like: https://www.refheap.com/paste/43f1c7f13480a4f025bda6dd7 .