Futures
Kelly Murray
will exist in the future. (I don't know if
futures trading on the stock market is related, but it may be..)
The key to a future is that it may be manipulated as if it
where the actual value in the future. Thus, it can be passed
as arguments to functions, stored in data structures, etc.
Only when the exact value is needed does the computation
to which the value refers need produce the value.
This is called "implicit synchronization",
and is well suited to a functional programming style
such as lisp.
This feat is /relatively/ easy to accomplish in Lisp because
it uses run-time typing, and therefore you can pass around
objects of unknown type within the system. It is only when
the type of an object is verified or used in a "strict" operation
that a specific
value for an object must exist, which is called "forcing" the
value. However, it requires low-level changes to type-checking
in the implementation, and can't really be done "on top"
of an existing Lisp.
This concept is generally considered lazy evaluation, and
is useful for non-parallel computation, and is often associated
with streams that represent perhaps infinite values which
only get computed as they are needed.
Scheme has a similiar concept called "promises", which omit
the key element of implicit synchronization.
In its place, the programmer is required to explicitly
synchronizing the promises by forcing their values
passing the promise to the function FORCE, which returns
the actual value. This can be done very easily "on top of"
an existing Lisp because it requires little or no changes
in the low-level code generated by the compiler and at runtime.
Franz's AllegroCLIP supported "promises", and not "futures".
To evaluate two arguments in parallel using futures,
you'd do something like:
(foobar (future (zip 1)) (future (zap 2)))
which would call FOOBAR with two future objects representing
the values of calling ZIP and ZAP.
The calls to ZIP and ZAP would execute in parallel
to each other and along with FOOBAR.
Using a promise instead of a future, the call to FOOBAR could
not be made until the values of ZIP and ZAP returned, because
one must FORCE the values before calling FOOBAR.
[unless FOOBAR itself was recoded to call FORCE.]
(foobar (force (promise (zip 1))) (force (promise (zap 2))))
The astute reader will notice this code in fact will not
execute in parallel at all, because the call to FORCE will
immediately wait for the computation to finish, and thus
the ZIP call must complete before the ZAP call is invoked
as a promise, which also is immediately waited for.
The "fix" is to use a let to get the two processing running
before forcing them:
(let ((zip-1 (promise (zip 1)))
(zap-2 (promise (zap 2))))
(foobar (force zip-1) (force zap-2)))
But unfortunately, this results in only TWO parallel operations,
because the force call on zip-1 causes the current process to
immediately wait for zip-1 to complete.
Using real future objects this problem is completely eliminated
because FOOBAR can be called immediately while both zip-1 and zap-2
are being computed, resulting in THREE computations occuring in
parallel.
Depending on the algorithm, the difference can be dramatic,
because the third process is now free to create MORE
parallel computation while the first two processes are executing.
-Kelly Murray k...@niclos.com
Howard R. Stearns
seen (though, personally, I try not to look for such things).
What's your point, question, suggestion...?
Rob Warnock
+---------------
| Scheme has a similiar concept called "promises"...
| ...one must FORCE the values before calling FOOBAR.
| [unless FOOBAR itself was recoded to call FORCE.]
|
| (foobar (force (promise (zip 1))) (force (promise (zap 2))))
|
| The astute reader will notice this code in fact will not
| execute in parallel at all, because the call to FORCE will
| immediately wait for the computation to finish, and thus
| the ZIP call must complete before the ZAP call is invoked
| as a promise, which also is immediately waited for.
|
| The "fix" is to use a let to get the two processing running
| before forcing them:
|
| (let ((zip-1 (promise (zip 1)))
| (zap-2 (promise (zap 2))))
| (foobar (force zip-1) (force zap-2)))
|
| But unfortunately, this results in only TWO parallel operations,
| because the force call on zip-1 causes the current process to
| immediately wait for zip-1 to complete.
But this is not how promises are intended to be used in Scheme.
Instead, it is expected that you *will* "recode FOOBAR" to pass
the promises down un-forced:
(foobar (promise (zip 1)) (promise (zap 2)))
and that only where the value of an argument is actually needed would
the "force" eventually be done (if ever).
The downside (from a "futures" or "lazy-eval" sperspective) is that
everyone from "foobar" all the way down has to understand that any
given value might be a promise, and force it when necessary. Though
[as the standard explicitly permits] partial relief from this odium
can be gotten from:
- Implementations which allow "force" to be the identity operator
when applied to non-promises;
- Implementations which implement "implied forcing" in primitives;
- Or simply use (define (force-if-needed x) (if (promise? x) (force x) x)).
Yes, it's "uglier" than futures, but not as disfunctional as you claim.
-Rob
-----
Rob Warnock, 8L-855 rp...@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
2011 N. Shoreline Blvd. FAX: 650-964-0811
Mountain View, CA 94043 PP-ASEL-IA
Tim Bradshaw
> That may have been the clearest explanation of promises and futures I've
> seen (though, personally, I try not to look for such things).
>
> What's your point, question, suggestion...?
>
I think he was following up to the discussion a while back on multiprocessor
support in CL, where Duane Rettig said that the system Franz did used futures.
And to give my article some point, futures is what I *don't* want in
a multiprocessing Lisp. I just want separate threads to be able to use
separate CPUs, and be able to get at the heap at once, and I'm willing
to deal with locking in almost all cases myself, and take the consequences
(core dumps!) if I foul up.
--tim