[Fwd: Re: CTM book (p. 262)]
Boriss Mejias
boris.mejias at uclouvain.be
Thu Mar 1 15:50:21 CET 2007
-------- Original Message --------
Subject: Re: CTM book (p. 262)
Date: Thu, 1 Mar 2007 05:55:09 -0600
From: Craig Ugoretz <craigugoretz at gmail.com>
To: Boriss Mejias <boris.mejias at uclouvain.be>
Hello,
I just wanted to post that I think I understand the problem now,
after all the help people have given me. Additionally, I did a "reply
to all" in gmail, so I want to test that the email got through to
everyone (not just Boriss). In essance, the case statement pattern
matches a stream, which is a list with a dataflow variable as the last
element on its tail. To satisfy the case statement in addition to the
Xr (the dataflow variable), the front element of the stream, in this
case the X, may be bound to an unbound variable. In abstact machine
terms, a variable identifier refers to a store variable that is not
bound to a value. I think confirmation of the last sentence is crucial,
and I apologize if I have belabored seemingly easy points to understand
in regard to this problem (and I thank Boriss again for helping me out
repeatedly).
Thanks so much,
Craig
On 2/28/07, *Boriss Mejias* <boris.mejias at uclouvain.be
<mailto:boris.mejias at uclouvain.be>> wrote:
Craig Ugoretz wrote:
> Hello,
>
> To understand the problem better, I reduced it to a minimal
> implementation. In the minimal implementation, the consumer only
> requests one item of data and displays it. Here it is:
>
>
> declare
> proc {Test1 Xs Flag}
> if Flag == true then X|Xr=Xs in {Browse X} {Test1 Xr false} else
> {Browse "Done!"} end
> end
>
> proc {Test2 Xs}
> case Xs of X|Xr then X=66 end
> end
>
> local Xs in
> thread {Test1 Xs true} end
> thread {Test2 Xs} end
> end
>
> For some reason (probably because there is less code to look at), I
> understand better what is going on, namely the rubberbanding
between the
> X and Xr between Test1 (consumer) and Test2 (producer), with Xr
being
> unbound until all the data is requested. This is per the definition
> given in the CTM book. I am a little foggy yet why this works,
I hope that after the other replies I sent you, you'll be able to
answer
this question now. The key is to understand when and why the threads
suspend, and how you can wake them up. Data-flow synchronization is not
that complicated and when you get use to it, it will look more natural
than using locks and semaphores and monitors, etc.
> but I
> suppose I could go down the abstract machine level and a take a
look at
> what is happening. Is there an abstact machine simulator for
Mozart/Oz,
> or would I need to do this manually?
it is possible that there is one already implemented with the debugger,
but I'm not sure. Ask in the users list.
cheers
Boriss
>
>
Thanks,
> Craig
>
>
> On 2/27/07, *Craig Ugoretz* < craigugoretz at gmail.com
<mailto:craigugoretz at gmail.com>
> <mailto: craigugoretz at gmail.com <mailto:craigugoretz at gmail.com>>>
wrote:
>
> Hello,
>
> To try the illustrate the binding graphically (as
opposed to a
> textual descirption):
>
> Xs <------
> / \ |
> / \ |
> V V |
> X Xr -----
>
> Another fact that I noticed: Xs is the output variable for the
> procedure (I was thinking in terms of a function). Therefore,
> through pattern matching, X and Xr become parts of the output
> variable. But, in the recursive call to DSum, the output
variable
> Xs becomes an input variable bound to Xr? Here is where I
really
> get confused...
>
>
> Craig
>
> On 2/27/07, *Craig Ugoretz* < craigugoretz at gmail.com
<mailto:craigugoretz at gmail.com>
> <mailto:craigugoretz at gmail.com
<mailto:craigugoretz at gmail.com>>> wrote:
>
> Hello,
>
> I think that I am really confusing myself with this
> problem, possibly because I have been going through the
CTM book
> too quickly without practicing enough. I can about
imagine that
> my problem with this problem, so to speak, is not with the
> thread concepts, but the concept of binding a variable in
> general (although I recognize the rubber banding taking
place -
> looked at the abstract machine example on p.242).
>
> Trying to step through the code:
>
> (1) Enter DGenerate procedure.
> (2) Block on Xs in case statement
> (3) Enter DSum function
> (4) Pattern match X|Xr on unbound variable Xs
> (5) Recursively call DSum
> (6) Xr gets bound to Xs in (5), X is still unbound (so in
other
> words, part of Xs (the Xr) gets matched to itself).
> (7) The partial value referenced by Xs in DGenerate is
> considered a binding, so the case statement proceeds.
> (8) X gets bound to N
> (9) Now, the recursive call to DSum in DSum can finish
because X
> is now bound to a value.
> (10) DSum keeps pulling values from DGenerate to a limit is
> reached. DSum sums the values.
>
> So, after all that analysis, perhaps the key elements that I
> have been missing are (6) and (7), which would refer to
earlier
> chapter material?
>
> Additionally, I may possibly be posing a lot of questions
like
> this as I move forward through the concurrency portion
of the
> text. If my questions take up too much "bandwidth" in
the this
> user's group, please let me know...
>
>
> Sincerely,
>
> Craig
>
> On 2/26/07, *Craig Ugoretz* < craigugoretz at gmail.com
<mailto:craigugoretz at gmail.com>
> <mailto:craigugoretz at gmail.com
<mailto:craigugoretz at gmail.com>>> wrote:
>
> Hi Boriss,
>
> Thank you (and others) for your great advice
regarding
> this problem. As a matter of clarification, you
write that
> X|Xr = Xs introduces variables X and Xr as local
variables.
> I was not aware of this feature of the language. So in
> other words, pattern matching, even it is not in a case
> statement, introduces local variables? A very
interesting
> point for someone new to the language to know. I am
trying
> to go through the CTM book as well as the CS2104 course
> material and there is a lot of information to digest,
> needless to say.
>
> Then, how does the function call {DSum Xr A+X
Limit-1}
> cause Xr to bound, unless Xr is considered bound
because it
> was part of the dataflow variable Xs? Alternatively, it
> seems like when A is returned by the else clause in
DSum, Xr
> becomes bound somehow - then X needs to be bound,
somehow Xs
> becomes unblocked in DGenerate, allowing X to be set
to N?
> I am sure you addressed these issues in the earlier
> responses, but I am still trying to understand - and it
> looks like I am still missing a few steps.
>
>
> Sincerely,
>
> Craig
>
> On 2/26/07, *Boriss Mejias* <
boris.mejias at uclouvain.be <mailto:boris.mejias at uclouvain.be>
> <mailto:boris.mejias at uclouvain.be
<mailto:boris.mejias at uclouvain.be>>> wrote:
>
> Hi Craig,
>
> The idea is that the procedure DGenerate suspends
in the
> case statement:
> case Xs of ... end
> because Xs is not bound yet.
>
> Then, in the other thread, when you do
> X|Xr = Xs
> you unify Xs with two new variables X|Xr using
the list
> pattern. Since X
> and Xr are not bound yet, the procedure will suspend
> with the operation A+X.
>
> After the unification of Xs, case statement of the
> DGenerate procedure
> can carry on the pattern matching, and bind X to N,
> allowing DSum to
> continue with the operation A+X.
>
> Note that the code
>
> if Limit>0 then
> X|Xr = Xs
> in
> ...
> end
>
> is equivalent to
>
> if Limit > 0 then
> X Xr
> in
> Xs=X|Xr %% or X|Xr=Xs where all three
variables are
> unbound
> ...
> end
>
> cheers
> Boriss
>
> Craig Ugoretz wrote:
> > Hello,
> >
> > The following code is from the CTM book, Ch. 4 on
> declarative
> > concurrency, p.262:
> >
> > declare
> > proc {DGenerate N Xs}
> > case Xs of X|Xr then
> > X=N
> > {DGenerate N+1 Xr}
> > end
> > end
> >
> > fun {DSum ?Xs A Limit}
> > if Limit>0 then
> > X|Xr=Xs
> > in
> > {DSum Xr A+X Limit-1}
> > else A end
> > end
> >
> > local Xs S in
> > thread {DGenerate 0 Xs} end
> > thread S={DSum Xs 0 4} end
> > end
> >
> > The generator only supplies values to the sum
function
> when it needs
> > them. Notice that the two are in different
threads
> and appear to share
> > a dataflow variable Xs. I have been trying to
> understand this code, and
> > I do not understand, after running the code
in the
> debugger, how the
> > system knows that Xs is a list variable. This is
> considering that Xs is
> > never initialized to a value initially. I am
sure
> that I am thinking in
> > sequential, not concurrent terms. The line that
> especially troubles me
> > is X|Xr = Xs in the sum function, with the X
and the
> Xr on the left.
> > Can anyone tell me how the dataflow variables
work
> such that the
> > generator and the summer work together?
> >
> >
> > Thanks,
> >
> >
> Craig
> >
> >
> >
>
------------------------------------------------------------------------
> >
> >
>
_________________________________________________________________________________
> > mozart-users mailing
> list
> mozart-users at mozart-oz.org
<mailto:mozart-users at mozart-oz.org>
> <mailto: mozart-users at mozart-oz.org
<mailto:mozart-users at mozart-oz.org>>
> >
http://www.mozart-oz.org/mailman/listinfo/mozart-users
<http://www.mozart-oz.org/mailman/listinfo/mozart-users>
>
<http://www.mozart-oz.org/mailman/listinfo/mozart-users
<http://www.mozart-oz.org/mailman/listinfo/mozart-users>>
>
>
>
>
>
More information about the mozart-users
mailing list