I have been looking at certain languages which support concurrency E and Multilisp and I was wondering if anyone has knowledge of the promises/futures mechanism where you basically block until some value is "lazily" evaluated for asynchronous calls. I am curious as to what the benefits of this approach are and what particular problems it solves. The wiki makes mention of pipelining for asynchronous calls to systems with high latency but are there others?

It's a convenient way to keep a handle to a value lying around until you actually use it.

bla = connection.read() // doesn't actually read, but starts the (async) read
// do some fun stuff
print(bla) // *now* it blocks if the data isn't available

A contrived example, but hopefully you can see how this generalizes to carrying around a bunch of handles that can be processed in the background while you keep on going with your program's logic.

Thanks for the reply. I am still a bit confused by this notion. What theoretical advantages does it have over normal asynchronous setups (not knowing much about them)?

Well, for one, you don't have to sit there managing the async calls; you don't have to register the call explicitly nor pay attention to when it's completed. The call gets launched implicitly, and the language handles blocking for you when you need its result.

Thanks David. I think I might have to dig a bit into some of the theoretical papers on the topic also to see what they have to say.

I think you might have better luck looking at practical examples of lazily evaluated chunks (some languages call them "thunks") – the theoretical papers might not provide the kind of enlightenment you're looking for. :wink:

That might be true. I actually am somewhat familiar with the notion of lazy evaluation and "thunks". Unfortunately after discovering the wiki page on this it gives references but alot of them I simply do not have access to. I think only 1 piece (1977) might be available with my acm subscription :(.

I would still suggest that you look at use in real languages solving real problems as your answers are likely to be more immediate. Googling for 'scala lazy evaluation' gave me this first result for example which goes into some brief usage examples – and there are plenty others.

The usefulness seems pretty apparent to me straight off the bat, is there something in particular about it you'd like clarified?

Well I was wondering if there were any theoretical nuances to it that I might have missed. I am also curious (since I am working on language implementation) how this particular feature is implemented. I assume that a request for the data needed for the promise is fired off immediately i.e. when you you specify some expression thunk it will send out requests for the information. Perhaps my understanding of concurrency is just too newbie but if you "pipeline" requests for values what are the expectations in terms of timing? i.e. since it's a stateful environment and depending on when the request arrives the value may or may not be the same wouldnt this pose issues for predicting what you get out of a promise? (I hope that isnt too stupid of a question).

What kind of thing are you including in the category of "theoretical nuances"? Can you give an example of some language feature somewhere that has "theoretical nuances"?

As for concurrency, well, it's handled implicitly by the semantics of the construct. You can think of a promise as a semaphore such that any consumer will always block until the producer, err, produces – and that only happens once. And from then on, the semaphore may be consumed as many times as you like. But you don't have timing issues because you can't consume it until it's ready, and typically you can't change it after you've made it available.

Under the hood, this can be implemented in any number of ways, but using a few primitive synchronization tools (even simple mutexes) it's pretty easy to achieve.

You could implement it fairly straightforwardly in other languages with the right synchronization tools, if you cared to do so.

Hmm. I guess I am not sure what I am looking for exactly. Something which has theoretical nuances though I am sure I know less that a fifth of whats out there is something like recursion and it's links to things in both lambda calculus and combinatory logic. I thought the y-combinator was pretty interesting the first time I encountered it and with continuations and such it's quite an interesting notion. The problem I guess is until I read up more about concurrency/distributed systems I may not get a particularly full picture here. As for the issue concerning pipelining-

http://en.wikipedia.org/wiki/Futures_and...

has a section on pipelining requests in future/promise expressions. My question goes towards how well the programmer can predict the behavior of something like this. It would seem to me from a cursory read that packeting everything as a single request to a remote machine might not yield the same result as doing so for "multiple requests" and if some expression in general sends messages to n machines how can the programmer determine to what extent what the result from the computation should be.

If your question is how does something fit in to the greater picture of all things computation and the meaning of life and the universe and Mathematics (with a capital M), and so forth – I don't really mean that facetiously – I can't really help you there and I suspect that most academic papers also focus on much more specific aspects.

As for predicting the behavior, the semantics are pretty clear: if you use some value that is not ready yet, you will block until it is ready. If that value in turn depends on another value that might or might not be ready, you'll have to wait on that too. Because of how programming works, you don't have simultaneous interdependency of values.

Another way you might be asking the question is how to predict in general what happens when you send requests to black boxes; that's not really specific to futures/promises/etc. but rather just programming in general (how one knows what to expect out of some process).

You may be right. I suspect most CS papers tend to be quite specific in the topics they address. However I guess I am trying to contextualize this information in terms of computational models revolving around concurrency. Perhaps unlike notions like STM which has both constructs and more underlying theoretical aspects maybe from your description the idea of promise/futures are somewhat simpler.

The question is not quite as general as that i.e. obviously in a lot of cases what happens in a program might be difficult to predict. The question goes more towards the idea of pipelining. I.e. a simple implementation which blocks until values are ready (thanks from the description!) seems relatively easy to visualize and implement. The problem I was wrestling with was how this notion is handled when systems attempt to pipeline requests. I.e. how would the programmer know what the expected behavior should be (and how this might be implemented). Lets say I have a futures expression of some shape x which dispatches futures to say for the moment 1 machine and I wish to minimize the wait time the pipelining idea from the wiki seems to suggest that the request "can be" passed in one bundle and perhaps returned in the same manner.

The problem in my mind is what if you have extremely complex futures expressions and hope to process these in a lazy manner. This is problematic in non-distributed imperative environment (because functions are potentially stateful and do not depend solely on their inputs). Perhaps there may not be a simple answer to this and maybe different implementations elect to do different things(I really dont know).

Anyhow thanks for the help.

The implementation-specific questions you're discussing – how the programmer might give various hints to the language scheduler to prioritize or bundle requests – can probably only be addressed in the context of a specific language. Most languages I know of that implement futures/etc. don't give you this kind of control. As with many high-level languages, you're supposed to assume/hope that the implementation will do something reasonable most of the time.

You can think of lazy evaluation like so: think of the lazy value as a function handle that is passed around. That function's body can be evaluated at most one time, and when the body is evaluated, it is replaced with the result of the evaluation. When it is evaluated, you still have the handle, but it is no longer to a function per se but rather to the resulting value. If you never use the lazy value, you will never call the function. So in many ways, a lazily evaluated value is really not so different from a memoized function call. (Some languages implement lazy evaluation exactly as I said, actually: a function body which is replaced with the result of evaluation.)

Futures are kind of like kicking off a thread in the background and later having the calling 'join' the future's thread (which means to block until that thread finishes). It's not a new concept at all, it's just that languages are embedding the concept into their semantics with specific syntax.
Promises are similar except that they're not necessarily kicked off by the thread that will consume the value.

Extremely complex lazy evaluation is exactly the same as normal lazy evaluation. As long as you don't have interdependence of values, it's just following a chain of evaluations. You can think of it as cooperative multithreading if that makes things easier. Or think of it as memoization.

The key is that you don't consume something until it is ready to be consumed – standard semaphore semantics with the exception that once there's a production on the semaphore, the number of consumptions is unlimited.

Thanks David. I am just curious if any languages do implement this pipeline technique the wiki mentions and how they go about bundling requests in this manner. It seems at a cursory glance to be not so easy to figure out in a complex expression how the bundling may or may not work. It may be that this pipelining behavior is mere extrapolation on the wiki's authors part. I really dont know(it seems to me in a concurrent situation to be quite troublesome).

The problem with lazy evaluation I think is with complex expressions is that depending on when the expression is actually evaluated the result may be different (if you are calling functions which are influenced by side effects) and difficult to predict. I know many pure functional languages do use tricks like memozation or term graph rewriting to get this effect- being pure I guess this is potentially alot easier.

EDIT: I guess perhaps the assumption is that when an asynch future/promise situation occurs that the function invoked remotedly are such that they will not change state multiple times between when the future expression is send as a request and the expression is evaluated. I.e. that the complex lazy version and the simple lazy version would yield the same result (or perhaps the requesting system doesnt care).

I don't know any off the top of my head, but that's not really saying much. I think it's fairly safe to say that there aren't mainstream languages that implement this kind of functionality. Keep in mind that the gap between what has been discussed in research or academic papers and what has been implemented into real, practical languages (as opposed to proofs of concept) is sometimes kind of large. Languages tend to lag research by quite a bit, after all.

You could well be right that somebody imagined the possibility of bundling things or whatever and said oh, this sounds cool, I'll put it up as an application of these techniques. Maybe somebody did more research into it and even worked out some examples and proofs of concepts. But I wouldn't read too much into this.


Straight lazy evaluation is actually "extremely easy" to predict: it behaves in exactly the same way as a function call. The function returns whatever it does at the point in time where you call it; the lazily evaluated value will give you whatever value it has at the first time that you read it. Of course, this is "easy" only in the sense that the semantics are extremely clear; as with any kind of function that gives you different values for the same input, it's not always obvious why it's doing that. Nonetheless, the semantics themselves (and usually the underlying implementation) are still quite straightforward.

Having pure functional languages obviates almost all of these problems because there aren't side effects to worry about.

Thanks David. I think we basically agree on that one. Though I think that having a situation where the call x() yields something which is from a preceding state in the system but not the current state to be problematic semantically. Sure you can say that we define this as returning whatever when the function is first invoked but I suspect this could in certain situations create a sense of state multiplicity and since who calls what when in a execution makes the output for the program difficult to predict (especially if it's modified and some person issues call x() at another point in the program). So to me it seems like a poor choice of semantics i.e. defining something like that in imperative languages which effectively makes things rather fragile (and difficult to predict).

That problem exists with any form of caching. It's true in general that you don't want to cache something if its value will meaningfully change during some period, if you don't update that cache appropriately. I.e., this is not a problem unique to futures etc. but to any kind of programming.

It's not just that we define away the problem when we see it; it's that the semantics are defined such that you get the value you got when you first invoked it, just like memoization. It's not really a "dirty trick"; it's the definition of the semantics.

You keep talking about difficulty of prediction. What's the implication there? Are you trying to write a program that guesses at the output of a program? Presumably not as that is a formally unsolvable problem. If you're saying it requires smarts on the part of the programmer to realize what's going on, well, that may be true, but it's also true of lots of other things. So I'm not sure what you're driving at.

I'm not sure why you think it's fragile; it's actually quite simple and in many ways rather elegant. I also disagree that its behavior is that hard to predict. Presumably, you would not lazily evaluate something whose value strongly depended on context unless there was a particularly good reason to do so. Either way, you would presumably document surprising behavior, or it would not be a function that had problems in that regard.

That's a good point actually. I suspect that much like any other situation selective use of lazy evaluation maybe be ok if the subset of functions you are calling are "pure". I think I mentioned this in my edit. I was more concerned about it in a general context. Perhaps it maybe possible to infer functions which have potential side effects and just toss out warnings on the use of memoization in situations like that. I guess perhaps somewhat dislike the notion that some function x at t = m when called at some point y the first time will hold the value which may not be what is expected at some subsequent call point z (assuming that the thing changes) and if say someone changes the code so that function x is called at t = n < m it might break the code. As you indicated though perhaps documentation can cope with this problem.

I wasnt in this case talking about futures tho. I suspect to deal with latency issues it could be quite useful. Though perhaps the system should make a conservative type check to see if the function in question depends on values other than it's arguments (and some relatively stable state).

You must dislike an awful lot of things about programming then. :tongue:
Seriously though, you seem to be objecting to potential misuses of the feature rather than its semantics. There are lots of things that can be misused, especially when you throw concurrency into the mix. All kinds of crazy things can happen.

You can probably infer, to some extent, which functions might have side effects, yes, and print warnings about them.

But remember that like anything else, you can have a tool and use it correctly or use it incorrectly. The compiler can't really detect all possible misuses of something. Concurrency is a great place to find all kinds of ways to really shoot yourself in the foot.