Strange Looping in St. Louis

I spent the last three days in St. Louis at the Strange Loop conference and the associated Emerging Languages Camp:

    http://thestrangeloop.com/

It was truly a great conference.  The two keynotes were exceptional.  Michael Stonebraker (of Ingres and Postgres fame) spoke about his new extraordinarily fast in-memory database VoltDB.  Jeff Hawkins (of Palm and "On Intelligence" fame) spoke about his theory of how the neocortex works, with special emphasis on Sparse Distributed Representations. He also talked about how his new company Numenta had figured out how to embody some of these theories in a program called Grok, which is actually useful for real-world problems such as predicting energy usage of a building twenty-four hours in advance, to allow for advance purchase of electricity at the best rates.

But it wasn't just the keynotes.  There was a wonderful grab-bag of talks on all sorts of subjects, from retargeting the Scala compiler to generate LLVM assembly language (rather than Java), to how Grand Central Dispatch works in iOS and Mac OS X, to ruminations on P vs. NP.  The crowd was heavily tilted toward functional programming, but there were still enough others around to keep things interesting.  And the forces for static typing vs. those for dynamic typing seem to have been closely matched in strength, so Scala and JavaScript were both very hot topics. 

I had presented on ParaSail at the prior Emerging Languages Camp, and that seemed to disqualify me from presenting again this year.  But I did lead a (very small) unsession on the use of region-based storage management for parallel programming.  One benefit was it forced me to coalesce ideas on why region-based storage management is an excellent alternative to a global garbage-collected heap in a highly parallel environment.  Slides from this unsession are available at:

   http://bit.ly/QB2o9G

All in all, these past three days were a great mind-expanding experience.  I encourage anyone who has the time, to make an effort to attend Strange Loop next year; I presume it will be at about the same time of year in St. Louis again.

Work stealing and mostly lock-free access

ParaSail uses work stealing to schedule the picothreads that make up a ParaSail program.  With work stealing, there are a relatively small number of heavy-weight worker processes, roughly one per physical core/processor, each serving their own queue of picothreads (in a LIFO manner), and periodically stealing a picothread from some other worker process (using FIFO, so as to pick up a picothread that has been languishing on the other worker's queue).  See the following blog entry for more discussion of work stealing:

http://parasail-programming-language.blogspot.com/2010/11/virtual-machine-for-parasail-with.html

What this means is that a worker's queue is referenced mostly by only one process, namely the owner of the queue.

A similar situation arises in the region-based storage management used in ParaSail.  A region is created when a new scope is entered, and most of the allocation and deallocation within a region is done by the worker that created the scope.  But due to work stealing, some other worker might be executing a picothread that is expanding or shrinking an object associated with the region, so some synchronization is necessary in this case.

So what sort of synchronization should be used for these situations where most of the access to a resource arises from an owning worker process, but some of the access arises from other non-owning workers?  We could use a traditional lock-based mutex all of the time, but this slows down the common case where all the access comes from the owner.  We could use a general N-way lock-free synchronization, but this generally requires some kind of atomic compare-and-swap and involves busy waiting.  Atomic compare-and-swap is not always available in a portable fashion at the high-level language level, and busy waiting presumes that there are never more worker processes than there are available physical processors/cores, so the current holder of the lock-free resource is actually making progress while other workers are busy-waiting.

So for ParaSail we are adopting a middle ground between fully lock-based synchronization and N-way lock-free synchronization, which recognizes the asymmetric nature of the problem, namely that one process, the owner, will be performing most of the references.  With the adopted solution, we only need atomic load and store, rather than atomic compare-and-swap, and there is never any busy waiting, so we can run on top of, for example, a time-slicing operating system, where some worker processes might be preempted.

So what is the adopted solution?  For a given resource, we have two flags which are atomic variables, one mutex, and a queue, named as follows:

• Owner-wants-resource flag
• Nonowner-wants-resource flag
• Resource mutex
• Nonowner-waiting queue

When the owner wants to use the resource:

• Owner sets the owner-wants-resource flag atomically;
• It then checks the nonowner-wants-resource flag:

•  If nonowner-wants-resource flag is set:
• Owner calls the mutex lock operation;
• Owner manipulates the resource;
• Owner clears the owner-wants-resource flag;
• <<Check_Queue>> Owner then checks the nonowner-waiting queue:
• If the queue is empty, it clears the nonowner-wants-resource flag;
• If the queue is not empty, it wakes up one of the waiting nonowners;

• Owner calls the mutex unlock operation (note that this might be combined with the above waking up of one of the nonowners -- e.g. using a lock handoff).

•  If nonowner-wants-resource flag is not set:
• Owner manipulates the resource;
• Owner clears the owner-wants-resource flag.
• Owner rechecks the nonowner-wants-resource flag:
• If nonowner-wants-resource flag is now set:
• Owner calls the mutex lock operation;
• Owner does the <<Check_Queue>> operation (see above);
• Owner calls the mutex unlock operation (note that this might be combined with the waking up of one of the nonowners by Check_Queue -- e.g. using a lock handoff).

When a nonowner wants to use the resource:

• Nonowner calls the mutex lock operation;
• Nonowner sets the nonowner-wants-resource flag atomically;
• Nonowner checks the owner-wants-resource flag;
• While owner-wants-resource flag is set:
• Nonowner adds itself to the nonowner-waiting queue;
• When woken up, reacquire the lock (or get lock automatically via a handoff from the process that woke us up);

• Nonowner manipulates the resource;
• Nonowner does the <<Check_Queue>> operation (see above);
• Nonowner calls the mutex unlock operation (note that this might be combined with the waking up of another nonowner by Check_Queue -- e.g. using a lock handoff).

How do we know this approach is safe?  We need to prove that the resource is never manipulated simultaneously by the owner and a nonowner.  This can only happen if the owner decides to not use the mutex, since otherwise the manipulation happens under protection of the mutex lock.  We know that the owner sets the owner-wants-resource flag before checking the nonowner-wants-resource flag, and similarly a nonowner sets the nonowner-wants-resource flag before checking the owner-wants-resource flag.  Therefore, if the owner decides to bypass the mutex, while a nonowner is going after the resource simultaneously, the nonowner must not yet have checked the owner-wants-resource flag (think about it!). If later the nonowner does reach the check on the owner-wants-resource before the owner is done, it will put itself onto a queue rather than immediately manipulating the resource.

How do we know this approach does not leave a nonowner waiting on the queue forever?  We know the owner rechecks the nonowner-wants-resource flag after clearing the owner-wants-resource flag, so the owner will never miss the possibility that a nonowner queued itself while the owner was manipulating the resource.

So what does this approach accomplish?  We see that the owner only uses a lock-based mutex when it bumps into a nonowner that is simultaneously manipulating the resource.  On the other hand, a nonowner always uses a lock-based mutex, and in addition it uses a queue if it happens to bump into the owner simultaneously manipulating the resource.  As mentioned above, this approach also avoids the need for atomic compare-and-swap, as well as avoiding the need for busy waiting.

ParaSail standard library prefix?

Due to popular demand, we are going to try to solidify and extend the ParaSail standard library.  One practical question is the naming convention for the ParaSail standard library.  C++ uses "std::" as the namespace for the standard library.  Java uses "java." or "javax." or "com.sun." or "com.oracle.".  C# (and .NET in general) uses "System." as the prefix.  Ada uses "Ada." (as well as "System." and "Interfaces.").

So here are some possibilities for ParaSail:

• Standard::
• System::
• ParaSail::
• PS::
• PSL::
• ??

I think I am currently favoring "System::" because ParaSail has those two upper case letters which would be a bit of a pain, and the others don't seem to capture the idea as well.  Note that we will probably arrange things so that you rarely need to write the "System::" prefix, but if there is ambiguity, then it would be necessary.

Comments?

Rev 3.4 alpha 0.5 release of ParaSail now supports lambda expressions, etc.

We just released a new version (3.4 alpha 0.5) of the ParaSail compiler and virtual machine, available at the same URL as before:

    http://bit.ly/Mx9DRb

This new release includes support for declaring and passing operations as parameters of other operations.  The actual operation passed can be a nested operation, an operation of a module, or a lambda expression.  (Passing operations as parameters in module instantiations is not yet supported.)

Additional updates in this release:

1. optional outputs of an operation are now default initialized to the null value;
2. nested operations can now correctly make up-level references to variables of enclosing operations;
3. the Univ_String module now includes operations To_Vector and From_Vector for converting a Univ_String to/from a Vector of Univ_Characters; this is useful because Univ_String values are immutable;
4. the ZString module includes corresponding operations To_ZVector and From_ZVector for converting to/from a ZVector of Univ_Characters.

Here is an example of declaring an operation as a parameter of another operation, and passing a lambda expression as the actual parameter in a call:

interface Mapper<Element_Type is Assignable<>> is
    func Apply
      (func Op(Input : Element_Type) -> Element_Type;
       Vec : Vector<Element_Type>) 
      -> Vector<Element_Type>;
      // Apply "Op" to each element of vector and return the result
end interface Mapper;

class Mapper is
  exports
    func Apply
      (func Op(Input : Element_Type) -> Element_Type;
       Vec : Vector<Element_Type>) 
      -> Vector<Element_Type> is
      // Apply "Op" to each element of vector and return the result
       return [for I in 1..Length(Vec) => Op(Vec[I])];
    end func Apply;
end class Mapper;

. . .

type Univ_Int_Mapper is Mapper<Univ_Integer>;

const Squares : Vector<Univ_Integer> := [for I in 1..100 => I ** 2];
const Triple_Squares : Vector<Univ_Integer> := 
    Univ_Int_Mapper::Apply
       (lambda (X : Univ_Integer) -> Univ_Integer is (X * 3), Squares);
           // Triple each element of Squares

Allowing indenting to be significant a la Python?

We are toying with the idea of having a "mode" in the ParaSail compiler in which indenting is significant, as in Python.  This would allow the programmer to omit the "end XYZ" part of a construct, provided that they start the next statement at the appropriate level of indentation.  This would also allow the programmer to omit the ";" terminator of a statement or declaration so long as continuation lines are indented and new statements/declarations are not indented relative to the prior statement/declaration.

Because we would like to support both styles, we are considering having the "indentation is significant" flag be a function of the filename extension on the file.  If the filename ends ".psi" or ".psl" then indentation is not significant, and ";" and "end XYZ" are needed as usual.  If the filename ends ".psn" (for ParaSail, iNdented), then indentation is significant, and ";" and "end XYZ" are optional provided appropriate indenting is performed.

This is just an experiment so far, but any comments would be appreciated.  This is almost certainly well into the religious zone of language design, so an extra effort toward courtesy in any comments would be very much appreciated...

Example of doubly linked list in ParaSail

A question was posted asking how you would create in a pointer-free language like ParaSail a doubly-linked list, with constant time addition on either end of the list, and constant time removal anywhere within the list.  One straightforward way to do this is to use a Vector to store the nodes, and then use indices into the vector to create the doubly linked list. Below is such an implementation.

---

// Illustration of a doubly-linked list implemented in ParaSail

// Copyright (C) 2012, AdaCore, New York, NY
// To be used only for Personal, Academic, or Evaluation Purposes;
// Not for Commercial Production Use.
// Report errors at http://groups.google.com/group/parasail-programming-language

// There are two modules here, plus two test programs.
// The first module, Doubly_Linked_Index, provides a doubly-linked
// list of indices, the indices being usable with another vector
// where the actual data can be stored.

// The second module, Doubly_Linked_List, uses the Doubly_Linked_Index
// to provide the "Elem_Id" type, which is used to identify nodes in the
// linked list.  It also has a formal type "Element_Type" which is the
// type of the actual data to be stored in the linked list.

interface Doubly_Linked_Index<Max_Len : Univ_Integer := 100_000> is
  // Doubly-linked list acting as index into a separate vector of data
    type Elem_Id is new Integer<1..Max_Len>;
    op "[]"() -> Doubly_Linked_Index;
      // Create an empty linked list

    func Append(var DLI : Doubly_Linked_Index) -> Elem_Id;
      // Add a new node onto end of linked list

    func Prepend(var DLI : Doubly_Linked_Index) -> Elem_Id;
      // Add a new node at beginning of linked list

    func Insert_Before(var DLI : Doubly_Linked_Index; Elem_Id) 
      -> optional Elem_Id;
      // Insert new node before given element Id

    func Insert_After(var DLI : Doubly_Linked_Index; Elem_Id) 
      -> optional Elem_Id;
      // Insert new node after given element Id

    func Remove(var DLI : Doubly_Linked_Index; Elem_Id);
      // Remove specified element from linked list (if present)

    op "in"(Elem_Id; DLI : Doubly_Linked_Index) -> Boolean;
      // Return True if given element is in linked list

    func Remove_First(var DLI : Doubly_Linked_Index) -> optional Elem_Id;
      // Remove first element from linked list

    func Remove_Last(var DLI : Doubly_Linked_Index) -> optional Elem_Id;
      // Remove last element from linked list

    func Remove_Any(var DLI : Doubly_Linked_Index) -> optional Elem_Id;
      // Remove arbitrary element from linked list

    func Count(DLI : Doubly_Linked_Index) -> Univ_Integer;
      // Return count of elements in linked list

    func Max_Id_In_Use(DLI : Doubly_Linked_Index) -> optional Elem_Id;
      // Return max Elem_Id in use
end interface Doubly_Linked_Index;


interface Doubly_Linked_List
  <Element_Type is Assignable<>;
   Max_Len : Univ_Integer := 100_000> is

  // Doubly-linked list 

    type DLI is new Doubly_Linked_Index<Max_Len>;

    type Elem_Id is DLI::Elem_Id;

    op "[]"() -> Doubly_Linked_List;
      // Create an empty linked list

    func Append(var DLL : Doubly_Linked_List; Elem : Element_Type) -> Elem_Id;
      // Add a new element onto end of linked list

    func Prepend(var DLL : Doubly_Linked_List; Elem : Element_Type) -> Elem_Id;
      // Add a new element at beginning of linked list

    func Insert_Before
      (var DLL : Doubly_Linked_List; Elem : Element_Type; Elem_Id) 
      -> optional Elem_Id;
      // Insert new element before given element Id

    func Insert_After
      (var DLL : Doubly_Linked_List; Elem : Element_Type; Elem_Id) 
      -> optional Elem_Id;
      // Insert new element after given element Id

    func Remove(var DLL : Doubly_Linked_List; Elem_Id);
      // Remove specified element from linked list (if present)

    op "in"(Elem_Id; DLL : Doubly_Linked_List) -> Boolean;
      // Return True if given element is in linked list

    func Remove_First(var DLL : Doubly_Linked_List) -> optional Element_Type;
      // Remove first element from linked list

    func Remove_Last(var DLL : Doubly_Linked_List) -> optional Element_Type;
      // Remove last element from linked list

    func Remove_Any(var DLL : Doubly_Linked_List) -> optional Element_Type;
      // Remove arbitrary element from linked list

    func Count(DLL : Doubly_Linked_List) -> Univ_Integer;
      // Return count of elements in linked list

    func Max_Id_In_Use(DLL : Doubly_Linked_List) -> optional Elem_Id;
      // Return max Elem_Id in use

    op "indexing"(ref DLL : Doubly_Linked_List; Elem_Id) 
      -> ref optional Element_Type;
      // Return a reference to specified element

end interface Doubly_Linked_List;


// Here are the implementations of the above two modules

class Doubly_Linked_Index is
    interface Node<> is
        // Each node on list has next and prev Id
        var Next : Elem_Id;
        var Prev : Elem_Id;
    end interface Node;

    var Links : ZVector<Node>;  // zero-th element is header

    var First_Free : Elem_Id;
    var Num_Free : Univ_Integer;

    func Add_Node(var DLI : Doubly_Linked_Index; Next, Prev : Elem_Id) 
      -> New_Id : Elem_Id is
      // Add a node with given Next/Prev fields to Links vector
        var New_Node for DLI := Node::(Next => Next, Prev => Prev);

        if DLI.First_Free != 0 then
            // Reuse a free node`
            New_Id := DLI.First_Free;
            DLI.First_Free := DLI.Links[New_Id].Next;
            DLI.Num_Free -= 1;

            DLI.Links[New_Id] <== New_Node;
        else
            // Add a new node at end of Links vector
            New_Id := Length(DLI.Links);
            DLI.Links <|= New_Node;
        end if;

        DLI.Links[Prev].Next := New_Id;
        DLI.Links[Next].Prev := New_Id;
        return New_Id;
    end func Add_Node;

    // {Num_Free < Length(Links); First_Free in 0..<Length(Links)}
    // {(for all N of Links => N.Next in 0..<Length(Links) and then
                            // N.Prev in 0..<Length(Links)}
  exports
    op "[]"() -> Doubly_Linked_Index is
        return (Links => [(Next => 0, Prev => 0)],
                First_Free => 0, Num_Free => 0);
    end op "[]";

    func Append(var DLI : Doubly_Linked_Index) -> New_Id : Elem_Id is
      // Add a new node onto end of linked list
        return Add_Node(DLI,
          Next => 0, Prev => DLI.Links[0].Prev);
    end func Append;
            
    func Prepend(var DLI : Doubly_Linked_Index) -> Elem_Id is
      // Add a new node at beginning of linked list
        return Add_Node(DLI,
          Next => DLI.Links[0].Next, Prev => 0);
    end func Prepend;

    func Insert_Before(var DLI : Doubly_Linked_Index; Follower : Elem_Id) 
      -> New_Id : optional Elem_Id is
      // Insert new node before given element Id
        if Follower in DLI then
            return Add_Node(DLI,
              Next => Follower, Prev => DLI.Links[Follower].Prev);
        else
           // Follower not in linked list
           return null;
        end if;
    end func Insert_Before;

    func Insert_After(var DLI : Doubly_Linked_Index; Elem_Id) 
        -> optional Elem_Id is
        // Insert new node after given element Id
        if Elem_Id in DLI then
            return Add_Node(DLI,
              Next => DLI.Links[Elem_Id].Next, Prev => Elem_Id);
        else
            // Elem_Id not in linked list
            return null;
        end if;
    end func Insert_After;

    op "in"(Elem_Id; DLI : Doubly_Linked_Index) -> Boolean is
      // Return #true if given element is in linked list
      // NOTE: All elements on free list have Prev pointing to themselves
        return Elem_Id in 1..<Length(DLI.Links) and then
          DLI.Links[Elem_Id].Prev != Elem_Id;
    end op "in";

    func Remove(var DLI : Doubly_Linked_Index; Elem_Id) is
      // Remove specified element from linked list (if present)
        if Elem_Id in DLI then
            // Not on the free list, so OK to remove
            ref Elem => DLI.Links[Elem_Id];
            DLI.Links[Elem.Prev].Next := Elem.Next;
            DLI.Links[Elem.Next].Prev := Elem.Prev;

            // Mark as being on the free list
            Elem.Prev := Elem_Id;

            // Add to the free list
            Elem.Next := DLI.First_Free;
            DLI.First_Free := Elem_Id;
            DLI.Num_Free += 1;
        end if;
    end func Remove;

    func Remove_First(var DLI : Doubly_Linked_Index) -> optional Elem_Id is
      // Remove first element from linked list
        const First := DLI.Links[0].Next;

        if First == 0 then
            // List is empty
            return null;
        else
            Remove(DLI, First);
            return First;
        end if;
    end func Remove_First;

    func Remove_Last(var DLI : Doubly_Linked_Index) -> optional Elem_Id is
      // Remove last element from linked list
        const Last := DLI.Links[0].Prev;

        if Last == 0 then
            // List is empty
            return null;
        else
            Remove(DLI, Last);
            return Last;
        end if;
    end func Remove_Last;

    func Remove_Any(var DLI : Doubly_Linked_Index) -> optional Elem_Id is
      // Remove arbitrary element from linked list
        if Count(DLI) mod 2 == 0 then
            // Remove First if Count is odd, Remove Last if Count is even
            return Remove_Last(DLI);
        else
            return Remove_First(DLI);
        end if;
    end func Remove_Any;

    func Count(DLI : Doubly_Linked_Index) -> Univ_Integer is
      // Return count of elements in linked list
        return Length(DLI.Links) - DLI.Num_Free - 1;
    end func Count;

    func Max_Id_In_Use(DLI : Doubly_Linked_Index) -> optional Elem_Id is
      // Return max Elem_Id in use
        return Length(DLI.Links) - 1;
    end func Max_Id_In_Use;

end class Doubly_Linked_Index;


class Doubly_Linked_List is
    var Index : DLI;
    var Data : ZVector<optional Element_Type>;
        // zeroth element is used to represent a missing element
  exports
    op "[]"() -> Doubly_Linked_List is
      // Create an empty linked list
        return (Index => [], Data => [null]);
    end op "[]";

    func Append(var DLL : Doubly_Linked_List; Elem : Element_Type) 
      -> Result : Elem_Id is
      // Add a new element onto end of linked list
        Result := Append(DLL.Index);
        DLL.Data[Result] := Elem;
    end func Append;

    func Prepend(var DLL : Doubly_Linked_List; Elem : Element_Type) 
      -> Result : Elem_Id is
      // Add a new element at beginning of linked list
        Result := Prepend(DLL.Index);
        DLL.Data[Result] := Elem;
    end func Prepend;

    func Insert_Before
      (var DLL : Doubly_Linked_List; Elem : Element_Type; Elem_Id) 
      -> Result : optional Elem_Id is
      // Insert new element before given element Id
        Result := Insert_Before(DLL.Index, Elem_Id);
        if Result not null then
            DLL.Data[Result] := Elem;
        end if;
    end func Insert_Before;

    func Insert_After
      (var DLL : Doubly_Linked_List; Elem : Element_Type; Elem_Id) 
      -> Result : optional Elem_Id is
      // Insert new element after given element Id
        Result := Insert_After(DLL.Index, Elem_Id);
        if Result not null then
            DLL.Data[Result] := Elem;
        end if;
    end func Insert_After;

    func Remove(var DLL : Doubly_Linked_List; Elem_Id) is
      // Remove specified element from linked list (if present)
        Remove(DLL.Index, Elem_Id);
    end func Remove;

    op "in"(Elem_Id; DLL : Doubly_Linked_List) -> Boolean is
      // Return True if given element is in linked list
        return Elem_Id in DLL.Index;
    end op "in";

    func Remove_First(var DLL : Doubly_Linked_List) 
      -> Result : optional Element_Type is
      // Remove first element from linked list
        const Id := Remove_First(DLL.Index);
        if Id not null then
            // Remove element from Data vector
            Result <== DLL.Data[Id];
        else
            // List is empty
            Result := null;
        end if;
    end func Remove_First;

    func Remove_Last(var DLL : Doubly_Linked_List) 
      -> Result : optional Element_Type is
      // Remove last element from linked list
        const Id := Remove_Last(DLL.Index);
        if Id not null then
            // Remove element from Data vector
            Result <== DLL.Data[Id];
        else
            // List is empty
            Result := null;
        end if;
    end func Remove_Last;

    func Remove_Any(var DLL : Doubly_Linked_List) 
      -> Result : optional Element_Type is
      // Remove arbitrary element from linked list
        const Id := Remove_Any(DLL.Index);
        if Id not null then
            // Remove element from Data vector
            Result <== DLL.Data[Id];
        else
            // List is empty
            Result := null;
        end if;
    end func Remove_Any;

    func Count(DLL : Doubly_Linked_List) -> Univ_Integer is
      // Return count of elements in linked list
        return Count(DLL.Index);
    end func Count;

    func Max_Id_In_Use(DLL : Doubly_Linked_List) -> optional Elem_Id is
      // Return max Elem_Id in use
        return Max_Id_In_Use(DLL.Index);
    end func Max_Id_In_Use;

    op "indexing"(ref DLL : Doubly_Linked_List; Elem_Id) 
      -> ref optional Element_Type is
      // Return a reference to specified element
        if Elem_Id in DLL.Index and then
          Elem_Id in 1..<Length(DLL.Data) then
            return DLL.Data[Elem_Id];
        else
            // return reference to null value stored in zeroth element
            return DLL.Data[0];
        end if;
    end op "indexing";

end class Doubly_Linked_List;


// Two test programs, one for the Doubly_Linked_Index module
// and one for the Doubly_Linked_List module.

func Test_DLI() is
    var DLI : Doubly_Linked_Index := [];

    Println("Append three times");
    const Id1 := Append(DLI);
    const Id2 := Append(DLI);
    const Id3 := Append(DLI);

    for Id in DLI forward loop
        Println("Found Elem_Id = " | Id);
    end loop;

    Println("Prepend twice");
    const Id4 := Prepend(DLI);
    const Id5 := Prepend(DLI);

    Println("Count = " | Count(DLI));

    for Id in DLI forward loop
        Println("Found Elem_Id = " | Id);
    end loop;

    Println("Insert before original second append");
    const Id6 := Insert_Before(DLI, Id2);

    Println("Count = " | Count(DLI));

    for Id in DLI forward loop
        Println("Found Elem_Id = " | Id);
    end loop;

    Println("Remove " | Id1 | " and " | Id4);

    Remove(DLI, Id1);
    Remove(DLI, Id4);

    Println("Count = " | Count(DLI));

    for Id in DLI forward loop
        Println("Found Elem_Id = " | Id);
    end loop;

    Println("Reverse loop");

    for Id in DLI reverse loop
        Println("Found Elem_Id = " | Id);
    end loop;

    Println("Append one and prepend two");

    const Id7 := Append(DLI);
    const Id8 := Prepend(DLI);
    const Id9 := Prepend(DLI);

    Println("Count = " | Count(DLI));

    for Id in DLI forward loop
        Println("Found Elem_Id = " | Id);
    end loop;

    Println("Reverse loop");

    for Id in DLI reverse loop
        Println("Found Elem_Id = " | Id);
    end loop;

    Println("Unordered loop");
    for Id in DLI loop
        Println("Found Elem_Id = " | Id);
    end loop;

end func Test_DLI;


func Test_DLL() is
    var DLL : Doubly_Linked_List<Univ_Enumeration> := [];

    Println("Append three times");
    const Id1 := Append(DLL, #one);
    const Id2 := Append(DLL, #two);
    const Id3 := Append(DLL, #three);

    Println("Count = " | Count(DLL));

    Println("Item 2 = " | DLL[Id2]);
    Println("Item 3 = " | DLL[Id3]);

    var I := 0;
    for Elem in DLL forward loop
        Println("Found Elem = " | Elem);
        I += 1;
        if I > 5 then
            exit loop;
        end if;
    end loop;

    Println("Prepend twice");
    const Id4 := Prepend(DLL, #four);
    const Id5 := Prepend(DLL, #five);

    Println("Count = " | Count(DLL));

    for Elem in DLL forward loop
        Println("Found Elem = " | Elem);
    end loop;

    Println("Insert before original second append");
    const Id6 := Insert_Before(DLL, #six, Id2);

    Println("Count = " | Count(DLL));

    for Elem in DLL forward loop
        Println("Found Elem = " | Elem);
    end loop;

    Println("Remove " | Id1 | " and " | Id4);

    Remove(DLL, Id1);
    Remove(DLL, Id4);

    Println("Count = " | Count(DLL));

    for Elem in DLL forward loop
        Println("Found Elem = " | Elem);
    end loop;

    Println("Reverse loop");

    for Elem in DLL reverse loop
        Println("Found Elem = " | Elem);
    end loop;

    Println("Append one and prepend two");

    const Id7 := Append(DLL, #seven);
    const Id8 := Prepend(DLL, #eight);
    const Id9 := Prepend(DLL, #nine);

    Println("Count = " | Count(DLL));

    for Elem in DLL forward loop
        Println("Found Elem = " | Elem);
    end loop;

    Println("Reverse loop");

    for Elem in DLL reverse loop
        Println("Found Elem = " | Elem);
    end loop;

    Println("Unordered loop");
    for Elem in DLL loop
        Println("Found Elem = " | Elem);
    end loop;

end func Test_DLL;

Rev 3.2 of alpha release 0.5 now available

We just released a new version of the ParaSail compiler and virtual machine. This includes one major new feature (using polymorphic types as actual parameters), and a number of smaller features:

1) Support instantiating a module with a polymorphic actual type, such as:

   var VP : Vector<Expr+>;

This allows the construction of heterogeneous containers.

2) Improve detection of inappropriate calls on abstract operations. Detect when interface of operation uses polymorphic type for a parameter, while implementation uses non-polymorphic type, or vice-versa.

3) Support "continue" statement with named or multiple values, such as:

   continue loop with X => X.Left;
  and
   continue loop with (I => I+1, J => J-1);"

4) Support defining an operation with a single expression, as in:

   func Square(X : Integer) -> Integer is (X**2);

5) Support case expressions, such as:

   (case C of [#red] => X; [#green] => Y; [#blue] => Z)

---------

Version 3.2 is available at the same URL as version 3.1:

   http://bit.ly/Mx9DRb