Wednesday, June 21, 2006

The prophecy was unclear

My explanation of prophecies wasn't very clear. Ezra Cooper asked in the comments:
You say that the subexprs of the prophecy form are evaluated in a separate thread; is each one evaluated in its own separate thread? Or is one background thread generated for that whole prophecy? What happens after yielding--it queues up a value for other threads, but what does the present thread do?
The idea is that a prophecy form spawns one single background thread, which immediately goes to work evaluating the prophecy's subexpressions sequentially. Within that thread, each call to yield queues up its value and the thread immediately continues evaluating (this is in contrast to generators, which cause a transfer of control upon a yield).

When any other thread requests a value from the prophecy, it either dequeues the first yielded value, blocks if no values have yet been queued, or raises a stop-iteration exception if the prophecy is complete (i.e., the prophecy background thread has terminated and all yielded values have been dequeue).

But in my servlet example, each page in the servlet only wants to read one single yielded value, so there's no need to block the page from loading until all the values have been yielded. That's why the prophecy->stream library function provides a lazy stream view of the prophecy which the servlet can use to pull items off the queue by need. That is:
(define (view stream)
(if (null? (force stream))
;; produce a web page signalling that we're done
'(html (body "DONE"))
;; produce a web page displaying the first item in the stream
(send/suspend/dispatch
(lambda (proc->url)
`(html
(body
(p ,(render-item (car (force stream))))
;; a link to view the next item in the stream
(p ,(a ([href ,(proc->url
(lambda (request)
(view (cdr (force stream)))))])
"Next"))))))))
This procedure generates a web page that shows a view over the first item in the stream, with a link to display the next. When the user goes back to the previous page and reclicks the link, the servlet simply reloads this same stream (which was the cdr of the previous page's stream). In other words, we've effectively masked out any mutation. The streams provide a lazy view of an immutable sequence of values, but which are produced "eagerly" in a background thread by the prophecy.

3 comments:

Ezra Cooper said...

OK, I think I understand this now.

It sounds like the functionality you're getting is quite similar to the idea of UNIX pipes--in particular, the idea of forking off a background process and reading from its standard out.

Is the "yield" operation essential? How would it be different if you forked a thread that would yield a stream? Rather than sequentially executing yield statements, you'd be constructing a stream in a pure-functional way. This would give you independence of evaluation order, at least.

Just curious about the design space.

Dave Herman said...

I think I like that even better. Skip the silly imperative stuff and drop the relationship with generators.

At least for my purposes, you're right that yield isn't essential. I suppose at this point the main difference between what I wanted and what PLT Scheme's pipes provide me is the ability to communicate something other than characters between threads.

So I believe what I want is "value pipes", where one thread is eagerly creating a stream of values, and another thread is lazily consuming it.

When I get a chance I'll implement a library for this.

Dave Herman said...

Except.. how does the "eager" thread signal to the system that "I have some data available, but not all"? Other than imperatively, that is? In other words, if the eager stream simply produces a list, then it won't be available until the whole list is available.

I'm not an expert on laziness, but it seems to be an asymmetric thing: it's driven entirely by observation, not computation.