[Swift-devel] on the semantics of 'array closing'
Mihael Hategan
hategan at mcs.anl.gov
Tue Jun 19 09:48:31 CDT 2007
On Tue, 2007-06-19 at 08:41 -0500, Mike Wilde wrote:
> Mihael Hategan wrote, On 6/19/2007 7:55 AM:
> > On Tue, 2007-06-19 at 07:40 -0500, Mike Wilde wrote:
> >> This is a good breakdown, but I dont yet see how to distinguish
> >> between the two situations you lay out here, Mihael.
> >
> > The distinction is made by thinking about local vs. grid execution. If
> > something cannot occur during local execution but can occur during grid
> > execution, we probably want to hide that from the user as much as
> > possible. Programming against randomly unreliable systems is hard. We,
> > as long time Grid users and developers, have the unique position of
> > identifying such problems and dealing with them as we can.
> >
> >> I think we need to turn these cases into slightly more detailed
> >> examples and then consider how we want the system to respond and
> >> what the user would need to do in each case to recover/continue.
> >
> > I thought we've done this before, to a sizable extent, both on the
> > mailing lists, and face-to-face.
>
> You are probably right, with respect to the exeception handling
> disussion. We need to move such discussions into proposed language
> spec doc changes so that we can turn them into decisions and
> campaigns to implement them.
>
> The mailing list is the right place to discuss, but then we need to
> summarize that discussion into a consensus.
>
> Also, I think there's two new aspects proposed here - of a foreach()
> or map() reaching a threshold of "enough results" that it can be
> called done,
With sparse arrays, it would be sufficient to not have the results from
the iterations that fail. If we had try/catch constructs, that would
simply translate into:
foreach k,v in V {
try {
results[k] = process(V[k]);
}
catch (*) {}
}
thus alleviating the need for a complex foreach construct.
> and of a streaming model of computation where a DAG
> acts like a pipeline even though it was specified as a set of
> function applications.
I'm not really sure what that refers to.
>
> Are you and Ben at a point where you could gather these issues
> (map(), error handling, thresholds and streaming) and turn them into
> proposed language improvements?
We would need to chat some, and, of course, have the necessary time.
Mihael
>
> If so, you should, and if not, we should decide if we need more
> discussion on the list.
>
> Its likely that an attempt to do such a language update right now
> would lead directly to more discussion, as writing language spec
> tends to expose more unresolved issues.
>
> - Mike
>
> >
> >> Your cases separate out logical errors (1) from physical ones (2)
> >> which is I agree a useful distinction.
> >>
> >> But I wonder in case 2, when you have a program thats been
> >> productively proceeding, and then encounters a physical error, in
> >> some cases the program will have processed a give function "long
> >> enough" to end that function call and proceed ("correctly") with the
> >> data it has, while in other cases, the program can not proceed until
> >> it has generated every single member that a foreach or map function
> >> was to iterate over.
> >
> > Right. The former is the m out of n pattern with timeouts. While very
> > rarely occurring in nature, we may eventually want to support such a
> > thing. Also, given that reliable performance measurements are hard to
> > get in a massively multi-user heterogeneous environment, we would need
> > to find specific ways to express time.
> >
> > Mihael
> >
> >> In the latter branch of this case, we'd want to be able to restart
> >> the program, while in the former branch, we'd want to be able to
> >> ignore certain errors and continue.
> >>
> >> - Mike
> >>
> >>
> >> Mihael Hategan wrote, On 6/19/2007 3:55 AM:
> >>> On Mon, 2007-06-18 at 21:54 -0500, Ian Foster wrote:
> >>>> Interesting issue, as raised by Mike: it seems that we want to define
> >>>> a "map" function that can specify various "conditions" on the map,
> >>>> e.g., the length of time to wait for results, what to do if not all
> >>>> results are returned, etc. I wonder if others have done that before?
> >>> There are two types of errors and time-outs:
> >>> 1. The ones that occur as part of the workflow:
> >>> - Computations on some data does not return the expected files
> >>> - The user wants to run multiple algorithms on some data and only
> >>> select the fastest one or the ones that run in a specific time.
> >>> - etc.
> >>> 2. The ones that occur because of exceptional conditions in the system:
> >>> - A badly configured site fails to run things
> >>> - A job sits for a long time in a queue
> >>>
> >>> I think the first class can be handled in the language, but the second
> >>> should not.
> >>>
> >>> Occam seems to support such things, by composing various keywords (e.g.
> >>> PAR ... FOR and then timeouts or error handling). I personally favor
> >>> composition of smaller dedicated functions/keywords to big, do-it-all
> >>> functions.
> >>>
> >>> Mihael
> >>>
> >>>> Ian Foster wrote:
> >>>>> I like the notion of having a "map" function. If that could entirely
> >>>>> replace the current element assignments, that would be a wonderful
> >>>>> simplification, it seems to me.
> >>>>>
> >>>>> Ian.
> >>>>>
> >>>>> Ben Clifford wrote:
> >>>>>> There's a different approach, which is to asay that 'a' is a variable and
> >>>>>> can be assigned to once. Thus assignemnt syntax like a[0]=something
> >>>>>> becomes illegal and we need more functional language constructs. So
> >>>>>> instead of writing:
> >>>>>>
> >>>>>> for e,i in input_array {
> >>>>>> output_array[i] = p(e);
> >>>>>> }
> >>>>>>
> >>>>>> we would write:
> >>>>>>
> >>>>>> output_array = foreach i in input_array {
> >>>>>> return p(i);
> >>>>>> }
> >>>>>>
> >>>>>> (its a haskell map in different syntax!)
> >>>>>>
> >>>>>> That means that, at the language level, output_array is now properly
> >>>>>> single assignment.
> >>>>>>
> >>>>>>
> >>>>>> On Fri, 15 Jun 2007, Ian Foster wrote:
> >>>>>>
> >>>>>>
> >>>>>>> Hi,
> >>>>>>>
> >>>>>>> For:
> >>>>>>>
> >>>>>>> a[0] = p()
> >>>>>>> a[1] = q()
> >>>>>>> b = s(a)
> >>>>>>>
> >>>>>>> I think there are two distinct issues.
> >>>>>>>
> >>>>>>> a) Determining the size of the array. This could presumably be done by
> >>>>>>> declaring it, e.g.:
> >>>>>>>
> >>>>>>> a[2] or some similar notion
> >>>>>>> a[0] = p()
> >>>>>>> a[1] = q()
> >>>>>>> b = s(a)
> >>>>>>>
> >>>>>>> or by some "closing" concept.
> >>>>>>>
> >>>>>>> b) Whether or not each element of an array is a separate single-assignment
> >>>>>>> variable. If they are, then the code above should work just fine. If they are
> >>>>>>> not, then we have a couple of behaviors we could define. One would be that
> >>>>>>> b=s(a) blocks until all elements in "a" are defined. The other is that we have
> >>>>>>> a way of "closing" (once again). In that case, we have to define what happens
> >>>>>>> if b=s(a) accesses an element that is not defined.
> >>>>>>>
> >>>>>>> Ian.
> >>>>>>>
> >>>>>>> Ben Clifford wrote:
> >>>>>>>
> >>>>>>>> There is a problem that has been called the 'array closing problem'.
> >>>>>>>>
> >>>>>>>> It manifests itself in the tutorial in that certain bits of code that
> >>>>>>>> intuitively can either in a procedure or in the top level can, in practice,
> >>>>>>>> only go in to a procedure.
> >>>>>>>>
> >>>>>>>> In that context, I tried to think about better ways to explain/document the
> >>>>>>>> behaviour than "mumble mumble move that code into a procedure".
> >>>>>>>>
> >>>>>>>> In Swift we claim to have 'single assignment variables'.
> >>>>>>>>
> >>>>>>>> >From single assignment variables we get our grid job ordering:
> >>>>>>>>
> >>>>>>>> a = p()
> >>>>>>>> b = s(a)
> >>>>>>>>
> >>>>>>>> causes first grid job p to run, and when that has completed, then grid job s
> >>>>>>>> will run.
> >>>>>>>>
> >>>>>>>> This is the same as if we had written:
> >>>>>>>>
> >>>>>>>> b = s(a)
> >>>>>>>> a = p()
> >>>>>>>>
> >>>>>>>> The ordering comes from the use of a as an 'output' for p and an 'input' for
> >>>>>>>> s, not from source text ordering.
> >>>>>>>>
> >>>>>>>> In that model, its meaningless to assign two different things ta a, like
> >>>>>>>> this:
> >>>>>>>>
> >>>>>>>> a = p()
> >>>>>>>> b = s(a)
> >>>>>>>> a = t()
> >>>>>>>>
> >>>>>>>>
> >>>>>>>> Note that I've omitted the data types from the above. This works in the
> >>>>>>>> implementation for simple types such as a datafile marker type.
> >>>>>>>>
> >>>>>>>> What is important is that each variable is either unassigned or has its
> >>>>>>>> single value - whenever we refer to that variable, we can either use the
> >>>>>>>> value it has, or defer evaluation of that expression until the variable has
> >>>>>>>> its value.
> >>>>>>>>
> >>>>>>>> Now consider arrays. In the present syntax, arrays can be passed as single
> >>>>>>>> (complex) values to/from procedures, like before:
> >>>>>>>>
> >>>>>>>> a = p()
> >>>>>>>> b = s(a)
> >>>>>>>>
> >>>>>>>> Here a and b are array types.
> >>>>>>>>
> >>>>>>>> That's fine. a is assigned to by the first statement, and b is assigned to
> >>>>>>>> by the second statement.
> >>>>>>>>
> >>>>>>>> But we also support a different assignment syntax for arrays, that looks
> >>>>>>>> like this:
> >>>>>>>>
> >>>>>>>> a[0] = p()
> >>>>>>>> a[1] = q()
> >>>>>>>> b = s(a)
> >>>>>>>>
> >>>>>>>> This fails at the moment (specifically, I think the execution engine will
> >>>>>>>> hang).
> >>>>>>>>
> >>>>>>>> Why? Because the is no one point at which we assign a value to 'a' - the
> >>>>>>>> assignment is split over multiple statements, which can be in various places
> >>>>>>>> (and inside loops etc).
> >>>>>>>>
> >>>>>>>> There is nothing in the implementation that detects that a has been assigned
> >>>>>>>> its value.
> >>>>>>>>
> >>>>>>>> So there is this notion in the karajan intermediate code of 'closing an
> >>>>>>>> array'. This is an assertion made in the object code that all assignments
> >>>>>>>> to pieces of an array have been made - that, in affect, the array has its
> >>>>>>>> value.
> >>>>>>>>
> >>>>>>>> The suggested hack/workaround for this is to move the array element
> >>>>>>>> assignments into a procedure:
> >>>>>>>>
> >>>>>>>> (file f[]) z() {
> >>>>>>>> f[0] = p();
> >>>>>>>> f[1] - q();
> >>>>>>>> }
> >>>>>>>>
> >>>>>>>> a = z()
> >>>>>>>> b = s(a)
> >>>>>>>>
> >>>>>>>> This works. (which is sort-of a violation of referential transparency)
> >>>>>>>>
> >>>>>>>> It works because Swift implicitly marks arrays returned from compound
> >>>>>>>> procedures as closed (which may or may not be correct).
> >>>>>>>>
> >>>>>>>> So in most variable scopes, arrays behave like single-assignment variables,
> >>>>>>>> but each array can have one specific scope in which members can be assigned
> >>>>>>>> to. In that scope, the array cannot be treated as a whole variable.
> >>>>>>>>
> >>>>>>>> In the z() example above, that special scope is the body of z(). In the
> >>>>>>>> previous example, that scope is the global scope, and the program is invalid
> >>>>>>>> by the rule above that the array cannot be referred to as a whole in the
> >>>>>>>> same place that its members are individually assigned to.
> >>>>>>>>
> >>>>>>>> That's my explanation of what's going on now. I think it matches reality. I
> >>>>>>>> don't like that this is reality, but it is what we have.
> >>>>>>>>
> >>>>>>>> Comments appreciated.
> >>>>>>>>
> >>>>>>>>
> >>>>>>>>
> >>>>>>
> >>>>> --
> >>>>>
> >>>>> Ian Foster, Director, Computation Institute
> >>>>> Argonne National Laboratory & University of Chicago
> >>>>> Argonne: MCS/221, 9700 S. Cass Ave, Argonne, IL 60439
> >>>>> Chicago: Rm 405, 5640 S. Ellis Ave, Chicago, IL 60637
> >>>>> Tel: +1 630 252 4619. Web: www.ci.uchicago.edu.
> >>>>> Globus Alliance: www.globus.org.
> >>>>>
> >>>>>
> >>>>> ____________________________________________________________________
> >>>>>
> >>>>> _______________________________________________
> >>>>> Swift-devel mailing list
> >>>>> Swift-devel at ci.uchicago.edu
> >>>>> http://mail.ci.uchicago.edu/mailman/listinfo/swift-devel
> >>>>>
> >>>> --
> >>>>
> >>>> Ian Foster, Director, Computation Institute
> >>>> Argonne National Laboratory & University of Chicago
> >>>> Argonne: MCS/221, 9700 S. Cass Ave, Argonne, IL 60439
> >>>> Chicago: Rm 405, 5640 S. Ellis Ave, Chicago, IL 60637
> >>>> Tel: +1 630 252 4619. Web: www.ci.uchicago.edu.
> >>>> Globus Alliance: www.globus.org.
> >>>> _______________________________________________
> >>>> Swift-devel mailing list
> >>>> Swift-devel at ci.uchicago.edu
> >>>> http://mail.ci.uchicago.edu/mailman/listinfo/swift-devel
> >>> _______________________________________________
> >>> Swift-devel mailing list
> >>> Swift-devel at ci.uchicago.edu
> >>> http://mail.ci.uchicago.edu/mailman/listinfo/swift-devel
> >>>
> >>>
> >
> >
>
More information about the Swift-devel
mailing list