Saturday, July 23, 2011

Another slight shift in syntax

As we use ParaSail more, we are making some additional small changes in syntax.  The first one has to do with allowing a component to be declared as a reference to another object.  The ability to return a short-lived object reference is important for user-defined indexing.  We also imagine that certain data structures will want to incorporate references as components.  Such data structures will not allow assignment, but nevertheless they can be useful for iterating over some other data structure.    For example, one might have a complex tree structure, and then an iterator over the structure which contains a reference to the current item in the tree, and references to the enclosing nodes in the tree, so that given the iterator one can generate a reference to the next element of the tree (presuming some ordering such as depth-first left-to-right).

Currently, object references are recognized by using "=>" rather than ":=" for defining their initial value.  However, that is somewhat subtle, and for a component, the initial value can't be specified when the component is declared.  Having already used the term "ref" for parameters that act as references, we have chosen to change the syntax for other objects that are references by explicitly using the term "ref" for them as well.  For example:
    ref X => M[I];
    ref const R => T.Right;
    ref var L => T.Left; 

A "ref" by itself means that the reference is a read-write reference only if the object to which it refers is a variable.  Explicitly using "ref const" makes the reference read-only even if the object to which it refers is a variable.  Explicitly using "ref var" makes the reference read-write, and requires the object to which it refers to be a variable.  So the first example above creates a reference to the Ith element of M, providing read-write access only if M is a variable, the second creates a read-only reference to the Right component of T, and the third creates a read-write reference to the Left component of T, and requires that T itself is a variable.

Having adopted the use of "ref", we can now leave off the "=> obj" part and simply specify a type, and in that way declare a component which will be a reference. Here is an example of an iterator that walks over a tree structure. It uses a "ref" component to point to a particular node in the tree:
    class Tree_Iterator is
        ref Current_Node : Tree_Node;
        var Enclosing_Node : optional Tree_Iterator;
        var Which_Child : Child_Index; 
        func First_Item(ref Root : Tree_Node) -> Tree_Iterator is
            // Return leftmost child of Root to start the iteration
            return Leftmost_Child
              ((Current_Node => Root, Enclosing_Node => null, Which_Child => 0));
        end func First_Item;

        func Leftmost_Child(It : Tree_Iterator) -> Tree_Iterator is
             // Return iterator designating leftmost child
             if Num_Children(It.Current_Node) == 0 then
                 // We are at the leftmost child already
                 return It;
                 // Recurse down the left side
                   (Current_Node => It.Current_Node[1],
                    Enclosing_Node => It,
                    Which_Child => 1);
             end if;
        end func Leftmost_Child;

        func Next_Item(It : Tree_Iterator) -> optional Tree_Iterator is
            // Advance iterator to next item in left-to-right depth-first walk
            if It.Enclosing_Node is null then 
                // All done
                return null;
            elsif It.Which_Child < Num_Children(It.Enclosing_Node.Current_Node) then
                // Return next child of same enclosing node
                return Leftmost_Child
                  ((Current_Node => It.Enclosing_Node[It.Which_Child + 1],
                    Enclosing_Node => It.Enclosing_Node,
                    Which_Child => It.Which_Child + 1));
                // Recurse to go to next sibling of enclosing node
                return Next_Item(It.Enclosing_Node);
            end if;
        end func Next_Item;
    end class Tree_Iterator; 

This Tree_Iterator has a component that is a reference to a node in a tree, an optional Tree_Iterator for the enclosing node in the tree, and an indication of which child the current node is of the enclosing node.

By specifying simply "ref" rather than "ref var" or "ref const" for the Current_Node reference, we are saying that it is a reference to a variable when the enclosing Tree_Iterator object is a variable.

Any type that has a (constructor) function in its interface that takes a "ref" input and produces a new object of the type as an output is presumed to be burying the "ref" somewhere in the object. (Of course the compiler can just "look" in the class and see this, but a client of the module wants to know strictly from looking at the interface.) If the objects of a type incorporate a reference within them, then objects of that type do not permit assignment, since references in ParaSail are always required to be short-lived. The result of such a constructor function therefore can only be used to initialize a new object, be passed as a parameter, or be used to define the next value for a loop variable. The result of such a function cannot be assigned as the new value for an existing object.

Now that we are using "ref" explicitly for objects and components, it makes the syntax used for parameters, where "ref" comes after the parameter name and the ":", seem inconsistent. Hence we are changing the syntax for parameters to more closely match that of objects and components:
    operation_input ::= 
       id ':' type [ := default ]
     | 'var' id ':' type
     | 'ref' [ 'var' | 'const' ] id ':' type
     | 'global' [ 'var' ] id ':' type
     | [ 'locked' | 'queued' ] [ 'var' ] id ':' type 

   operation_output ::=
       [ id ':' ] type
     | 'ref' [ 'var' | 'const' ] [ id ':' ] type

For example:
    func Append(var L : List; E : Element);
    op "indexing"(ref V : Vector; I : Index) -> ref Element;
    func Get_Next(queued var Q : Queue) -> Element;
We will be posting a new draft of the ParaSail reference manual reflecting these changes shortly to the ParaSail google group:

1 comment:

  1. We have changed the approach a bit for handling objects with internal "ref" components. We now call such objects "ref" objects, and require that they be identified as "ref"s themselves. So in the above example, in most places that Tree_Iterator appears, it will be identified as a "ref" object. For example:

    func First_Item(ref Root : Tree_Node)
    -> ref Tree_Iterator is ...


    func Next_Item(ref It : Tree_Iterator)
    -> ref optional Tree_Iterator is ...

    This will serve to emphasize that a Tree_Iterator is fundamentally a reference to something else. It also makes it clearer that when you pass a Tree_Iterator as a "var" parameter, you are generally not updating the Tree_Iterator itself, but rather what it refers to.

    For a more complete example, see the use of Slice in the Parallel Quicksort example posted at: