[Swift-devel] on the semantics of 'array closing'

[Ian Foster]

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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/swift-devel/attachments/20070616/6e2b5eff/attachment.html>