Some additional examples of ParaSail

Here is a grab-bag of ParaSail examples, with interspersed musings embedded in the comments.  These are acceptable to the ayacc/aflex-based parser posted earlier.

import XXYZ;  // TBD: Does this precede the interface?
              //      Any notion of "use" or "using"
interface Hello_World <Standard_IO<>> is
    procedure Main(IO : ref Standard_IO);
end interface Hello_World;

// TBD: What do enumeration type declarations look like?
//      The first parameter is an id-list type.  The other
//      parameters might be something relating to first/last,
//      'image, etc.

// TBD: What is the comment syntax?  "//" or "--"?  
//      Modula and ML use "(* *)" but ML folks are suggesting
//      the use of "# " as the start of a comment that goes to the EOL.
//      For some reason I find "#" pretty ugly, especially in the
//      middle of a line.
//      C#, C++, and Java all support "//", as well as the
//      partial line '/* ... */'.  That seems error-prone,
//      so sticking with "//" by itself seems simplest.
//      Also "--" means decrement to half the world.

// Syntax:  module::module, type::operation, type::nested_entity,
//          object.component, object.operation [equiv to type::operation(object, ...)]

// TBD: When a non-abstract interface has no module parameters, does that mean
//      the module name can be used directly as a type name?  Or are the "<>"
//      mandatory?  Can we say "interface Univ_Enumeration<> is ..."

// TBD: Should we make aggregates usable when outside the associated class?
//      What about "extension" aggregates?  Operator "aggregate"?

// TBD: Get rid of "subtype" and just use "type Blah is ..." or "type Blah is new ..."
//      "subtype" is a relationship, not a kind of entity.

interface Std <> is

    abstract interface Any<> is
        operator "end" (Obj : ref var Any);
    end interface Any;
    
    abstract interface Assignable<> extends Any is
        operator "copy" Assignable -> Assignable;
    end interface Assignable;

    -- type Univ_Enumeration is ...; // type with all enumerals
    
    type Boolean is Enum <[#false, #true]>; // True or False
    type Ordering is Enum <[#less, #equal, #greater, #unordered]>;

    -- type Univ_Integer is ...; // infinite precision integers with +/- inf
    -- type Univ_Real is ...;    // infinite precision rational numbers 
         // with +/- zero and inf
    -- type Univ_Character is ...;  // ISO 10646, 31-bit character
    -- type Univ_String is ...;  // UTF-32
    
    
end interface Std;

interface Std::Integer<First, Last : Univ_Integer> is
    operator "from_univ"(Univ : Univ_Integer {Univ in First .. Last}) 
      -> Integer;
    operator "to_univ"(Int : Integer) 
      -> Result: Univ_Integer {Result in First .. Last};

    operator "+"(Left, Right : Integer {[[Left]] + [[Right]] in First .. Last}) 
      -> Result : Integer {[[Result]] == [[Left]] + [[Right]]};
end interface Std::Integer;

// [[x]] means "to_univ"(X), as a nod to the double bracket notation used in
// denotational semantics to define the meaning of an expression in a program.


abstract interface Std::Ref<Target_Type is Any<>> 
is
   function Is_Writable(R : Ref) -> Boolean;
   function Exists(R : Ref) -> Boolean;
   function Fetch(R : Ref {Exists(R)}) -> Target_Type;
   procedure Store(R : Ref {Is_Writable(R)}; 
     New_Contents : Target_Type) {Exists(R)};
   procedure Delete(R : Ref {Is_Writable(R)}) {not Exists(R)};
end interface Std::Ref;

class Hello_World <Context<>; Standard_IO<>> is
  exports
    procedure Main(IO : ref Standard_IO) is
       Put_Line(IO.Output, "Hello World");
    end procedure Main;
end class Hello_World;

interface String<Character<>; Index is Integer<>> is
    operator "in"(Lit : Univ_String) -> Boolean;
    operator "from_univ"(Lit : Univ_String {Lit in String}) 
      -> String;
    operator "to_univ"(Str : String) -> Result : Univ_String
      {Result in String};
    operator "~"(Left, Right : String) -> Result : String
      {Length(Result) == Length(Left) + Length(Right)};
end interface String;
      
interface Standard_IO<Context<>; Input_Stream<>; Output_Stream<>> is
    function Output(Context) -> Output_Stream;
    function Input(Context) -> Input_Stream;
end interface Standard_IO;

interface Output_Stream<String<>> is
    procedure Put(Output : ref Output_Stream; Char : String::Character);
    procedure Put(Output : ref Output_Stream; Message : String);
    procedure Put_Line(Output : ref Output_Stream; Message : String);
end interface Output_Stream;

interface Input_Stream<String<>> is
    function Get(Input : ref Input_Stream) -> String::Character;
    function Get_Line(Output : ref Input_Stream) -> String;
end interface Input_Stream;

interface Integer<First, Last : Univ_Integer> is
    operator "in"(Lit : Univ_Integer) -> Result : Boolean 
      {Result == Lit in First .. Last};
    operator "from_univ"(Univ_Integer {Univ_Integer in First .. Last}) 
      -> Integer;
    operator "to_univ"(Integer) -> Result : Univ_Integer 
      {Result in First .. Last};
    operator "+"(Left, Right : Integer 
      {[[Left]] + [[Right]] in First .. Last}) 
      -> Result : Integer
        {[[Result]] == [[Left]] + [[Right]]};
    operator "-"(Left, Right : Integer
      {[[Left]] - [[Right]] in First .. Last}) 
        -> Integer;
    operator "*"(Left, Right : Integer
      {[[Left]] * [[Right]] in First .. Last}) 
        -> Integer;
    operator "/"(Left, Right : Integer
      {[[Left]] / [[Right]] in First .. Last}) 
        -> Integer;
    operator "=?"(Left, Right : Integer) -> Ordering;
end interface Integer;

interface Character<> is
    operator "in"(Lit : Univ_Character) -> Boolean;
    operator "from_univ"(Lit : Univ_Character {Lit in Character}) 
      -> Character;
    operator "to_univ"(Char : Character) 
      -> Result : Univ_Character 
      {Result in Character};
end interface Character;

interface Vector<Component is Assignable<>; 
   First : Univ_Integer := 1;
   Max_Length : Univ_Integer := +inf> is
    function Length(Vec : ref const Vector) -> Univ_Integer 
      {Length in 0..Max_Length};
    function Last(Vec : ref const Vector) -> Univ_Integer 
      {Last == Length(Vec) + First - 1};
    operator "[]"(Vec : ref Vector; Index : Univ_Integer 
      {Index in First..Last(Vec)}) 
      -> ref Component_Type;
    operator "~"(Left, Right : Vector) -> Result : Vector 
      {Length(Left) + Length(Right) == Length(Result)}; 
        // "~" is pronounced "concatenate"
        // or "connect" or "tied to"
        // or "chained to" or "linked to" or ...?
    operator "~"(Left : Vector; Right : Component) -> Result : Vector
      {Length(Left) + 1 == Length(Result)};
    operator "~"(Left : Component; Right : Vector) -> Result : Vector
      {Length(Right) + 1 == Length(Result)};
    operator "~"(Left, Right : Component) -> Result : Vector
      {Length(Result) == 2}; // Do we really need this one?  
                             // Is equivalent to "[Left, Right]"
    operator "null"() -> Result : Vector {Length(Result) == 0};
    procedure Append(Vec : ref mutable Vector; Value : Component)
      {Length(Vec') == Length(Vec) + 1};
    procedure Append(Vec : ref mutable Vector; Other_Vec : Vector)
      {Length(Vec') == Length(Vec) + Length(Other_Vec)}; 
                                        // Vec' means new value
                                        // do we prefer "old(...)"?
                                        // How about post(...) and pre(...)?
                                        // or "new(...)" and "old(...)"?
                                        // Since these are appearing in
                                        // a postcondition, it seems
                                        // redundant to say "post" or "new".
                                        // In any case "new" reads better than post.

    operator ":="(Left : ref var Vector; Right : Vector)
      {Length(Left) == Length(Right)};
      
    operator ":=:"(Left, Right : ref var Vector)
      {Length(Left') == Length(Right) and 
       Length(Right') == Length(Left)};
    operator "+"(Left, Right : Vector {Length(Left) == Length(Right)}) 
      -> Result : Vector
      {Length(Result) == Length(Left)};  // component-wise addition
    
end interface Vector;

interface Stack<Component is Assignable<>; 
  Size_Type is Integer<>> is
    
    function Max_Stack_Size(S : Stack) -> Size_Type 
      {Max_Stack_Size > 0};
    
    function Count(S : Stack) -> Size_Type 
      {Count <= Max_Stack_Size(S)};
    
    function Init(Max : Size_Type {Max > 0}) -> Stack 
      {Max_Stack_Size(Init) == Max and Count(Init) == 0};
    
    function Is_Empty(S : Stack) -> Boolean
      {Is_Empty == (Count(S) == 0)};
    
    function Is_Full(S : Stack) -> Boolean
      {Is_Full == (Count(S) == Mas_Stack_Size(S))};
      
    function Top(S : Stack {not Is_Empty(S)}) -> Component;
    
    procedure Pop(S : ref var Stack {not Is_Empty(S)}) 
      {Count(S') == Count(S) - 1};
      
    procedure Push(S : ref var Stack {not Is_Full(S)}; 
      X : Component) {Count(S') == Count(S) + 1};
      
end interface Stack;

Flex-based lexical scanner for ParaSail

In this entry and the next are Flex and Yacc grammars for the current definition for ParaSail.  They are actually grammars designed for aflex and ayacc, Ada equivalents of flex and yacc produced many years ago by the Arcadia project, so the commenting conventions and the code are for Ada rather than some other language.  But hopefully you can make the transformation fairly easily to your language of choice.

This entry contains the "aflex"-compatible grammar; the next will contain the "ayacc"-compatible grammar.

-- Flex-compatible grammar for ParaSail
%START IDENT Z

STRING_LITERAL  (\"([^\"]|[\\][.])*\")

CHAR_LITERAL    (\'([^\']|[\\][.])\')

IDENTIFIER        [a-zA-Z]([_]?[a-zA-Z0-9])*

  -- The following are used to match all numeric literals.
  -- Note that double underscores are rejected.
DIGIT_SEQUENCE    [0-9]([_]?[0-9])*
HEX_SEQUENCE      [0-9a-fA-F]([_]?[0-9a-fA-F])*
EXPONENT          [Ee][-+]?{DIGIT_SEQUENCE}

%%

  -- ParaSail reserved words
"abs"        {ECHO_L; ENTER(Z); return (ABS_kw);}
"abstract"    {ECHO_L; ENTER(Z); return (ABSTRACT_kw);}
"all"        {ECHO_L; ENTER(Z); return (ALL_kw);}
"and"        {ECHO_L; ENTER(Z); return (AND_kw);}
"block"        {ECHO_L; ENTER(Z); return (BLOCK_kw);}
"case"        {ECHO_L; ENTER(Z); return (CASE_kw);}
"class"        {ECHO_L; ENTER(Z); return (CLASS_kw);}
"concurrent"    {ECHO_L; ENTER(Z); return (CONCURRENT_kw);}
"const"        {ECHO_L; ENTER(Z); return (CONST_kw);}
"continue"    {ECHO_L; ENTER(Z); return (CONTINUE_kw);}
"each"        {ECHO_L; ENTER(Z); return (EACH_kw);}
"else"        {ECHO_L; ENTER(Z); return (ELSE_kw);}
"elsif"        {ECHO_L; ENTER(Z); return (ELSIF_kw);}
"end"        {ECHO_L; ENTER(Z); return (END_kw);}
"exit"        {ECHO_L; ENTER(Z); return (EXIT_kw);}
"exports"    {ECHO_L; ENTER(Z); return (EXPORTS_kw);}
"extends"    {ECHO_L; ENTER(Z); return (EXTENDS_kw);}
"for"        {ECHO_L; ENTER(Z); return (FOR_kw);}
"forward"    {ECHO_L; ENTER(Z); return (FORWARD_kw);}
"function"    {ECHO_L; ENTER(Z); return (FUNCTION_kw);}
"if"        {ECHO_L; ENTER(Z); return (IF_kw);}
"import"    {ECHO_L; ENTER(Z); return (IMPORT_kw);}
"in"        {ECHO_L; ENTER(Z); return (IN_kw);}
"interface"    {ECHO_L; ENTER(Z); return (INTERFACE_kw);}
"is"        {ECHO_L; ENTER(Z); return (IS_kw);}
"locked"    {ECHO_L; ENTER(Z); return (LOCKED_kw);}
"loop"        {ECHO_L; ENTER(Z); return (LOOP_kw);}
"mod"        {ECHO_L; ENTER(Z); return (MOD_kw);}
"mutable"    {ECHO_L; ENTER(Z); return (MUTABLE_kw);}
"new"        {ECHO_L; ENTER(Z); return (NEW_kw);}
"not"        {ECHO_L; ENTER(Z); return (NOT_kw);}
"null"        {ECHO_L; ENTER(Z); return (NULL_kw);}
"of"        {ECHO_L; ENTER(Z); return (OF_kw);}
"operator"    {ECHO_L; ENTER(Z); return (OPERATOR_kw);}
"optional"    {ECHO_L; ENTER(Z); return (OPTIONAL_kw);}
"or"        {ECHO_L; ENTER(Z); return (OR_kw);}
"procedure"    {ECHO_L; ENTER(Z); return (PROCEDURE_kw);}
"queued"    {ECHO_L; ENTER(Z); return (QUEUED_kw);}
"ref"        {ECHO_L; ENTER(Z); return (REF_kw);}
"rem"        {ECHO_L; ENTER(Z); return (REM_kw);}
"return"    {ECHO_L; ENTER(Z); return (RETURN_kw);}
"reverse"    {ECHO_L; ENTER(Z); return (REVERSE_kw);}
"select"    {ECHO_L; ENTER(Z); return (SELECT_kw);}
"some"        {ECHO_L; ENTER(Z); return (SOME_kw);}
"then"        {ECHO_L; ENTER(Z); return (THEN_kw);}
"type"        {ECHO_L; ENTER(Z); return (TYPE_kw);}
"var"        {ECHO_L; ENTER(Z); return (VAR_kw);}
"while"        {ECHO_L; ENTER(Z); return (WHILE_kw);}
"with"        {ECHO_L; ENTER(Z); return (WITH_kw);}
"xor"        {ECHO_L; ENTER(Z); return (XOR_kw);}

  -- Match all the compound ParaSail delimiters. 
"=?"        {ECHO_L; ENTER(Z); return(COMPARE);}
"=="        {ECHO_L; ENTER(Z); return(EQ);}
"!="        {ECHO_L; ENTER(Z); return(NEQ);}
">="        {ECHO_L; ENTER(Z); return(GEQ);}
"<="        {ECHO_L; ENTER(Z); return(LEQ);}
"**"        {ECHO_L; ENTER(Z); return(POWER);}
":="        {ECHO_L; ENTER(Z); return(ASSIGN);}
":=:"        {ECHO_L; ENTER(Z); return(SWAP);}
".."        {ECHO_L; ENTER(Z); return(DOT_DOT);}
"::"        {ECHO_L; ENTER(Z); return(DOUBLE_COLON);}
"[["        {ECHO_L; ENTER(Z); return(DOUBLE_LEFT_BRACKET);}
"]]"        {ECHO_L; ENTER(Z); return(DOUBLE_RIGHT_BRACKET);}
"=>"        {ECHO_L; ENTER(Z); return(REFERS_TO);}
"->"        {ECHO_L; ENTER(Z); return(GIVES);}
"==>"        {ECHO_L; ENTER(Z); return(IMPLIES);}
";;"        {ECHO_L; ENTER(Z); return(SEQUENCE);}
"||"        {ECHO_L; ENTER(Z); return(PARALLEL);}

  -- Match all the ParaSail single-character delimiters.
<IDENT>\'  {ECHO_L; ENTER(Z);     return(PRIME);}
"("        {ECHO_L; ENTER(Z);     return('(');}
")"        {ECHO_L; ENTER(IDENT); return(')');}
"["        {ECHO_L; ENTER(Z);     return('[');}
"]"        {ECHO_L; ENTER(IDENT); return(']');}
"<"        {ECHO_L; ENTER(Z);     return('<');}
">"        {ECHO_L; ENTER(Z);     return('>');}
"{"       {ECHO_L; ENTER(Z);      return('{');}
"}"       {ECHO_L; ENTER(Z);      return('}');}
"*"        {ECHO_L; ENTER(Z);     return('*');}
"+"        {ECHO_L; ENTER(Z);     return('+');}
","        {ECHO_L; ENTER(Z);     return(',');}
"-"        {ECHO_L; ENTER(Z);     return('-');}
"."        {ECHO_L; ENTER(Z);     return('.');}
"/"        {ECHO_L; ENTER(Z);     return('/');}
":"        {ECHO_L; ENTER(Z);     return(':');}
";"        {ECHO_L; ENTER(Z);     return(';');}
"|"        {ECHO_L; ENTER(Z);     return('|');}
"?"        {ECHO_L; ENTER(Z);     return('?');}
"~"        {ECHO_L; ENTER(Z);     return('~');}

  -- The following is used to match all valid ParaSail identifiers
  -- except reserved words. Note that leading digits and underscores
  -- are not allowed and that double underscores are not allowed.

{IDENTIFIER}       {ECHO_L; ENTER(IDENT);return(Identifier);}

  -- Enumeration literals
[#]{IDENTIFIER}    {ECHO_L; ENTER(IDENT);return(Enum_Literal);}

  -- Decimal numeric literals
{DIGIT_SEQUENCE}{EXPONENT}?  {
                  ECHO_L; ENTER(Z);
                  return(Integer_Literal);}

{DIGIT_SEQUENCE}[.]{DIGIT_SEQUENCE}{EXPONENT}?  {
                  ECHO_L; ENTER(Z);
                  return(Real_Literal);}

  -- Based numeric literals.

{DIGIT_SEQUENCE}[#]{HEX_SEQUENCE}[#]{EXPONENT}? {
                  ECHO_L; ENTER(Z);
                  return(Integer_Literal);}

{DIGIT_SEQUENCE}[#]{HEX_SEQUENCE}[.]{HEX_SEQUENCE}[#]{EXPONENT}? {
                  ECHO_L; ENTER(Z);
                  return(Real_Literal);}

"0"[xX]{HEX_SEQUENCE}        {ECHO_L; ENTER(Z); return(Integer_Literal);}
"0"[bB]{DIGIT_SEQUENCE}        {ECHO_L; ENTER(Z); return(Integer_Literal);}

  -- Match all valid character literals.
<Z>{CHAR_LITERAL}            {ECHO_L; ENTER(Z); return(Char_Literal);}

  -- Match all valid string literals.
{STRING_LITERAL}                {ECHO_L; ENTER(Z); return(String_Literal);}

"//".*    {ECHO_L;}           -- ignore comments to end-of-line

"--".*    {ECHO_L;}           -- ignore comments to end-of-line

  -- The following matches all whitespace.  Except for vertical tabs.  AFLEX,
  -- ALEX and LEX do not support vertical tabs.
[ \r\t\f]+ {ECHO_L;}        -- ignore spaces,Carriage returns,tabs,form feeds

  -- The following matches all new lines.

[\n]       {ECHO_L; linenum;}

  -- The following matches everything else and prints an error message
  -- indicating that something unexpected was found.

.          {ECHO_L; 
            text_io.put_line("?? lexical error '" & 
          parasail_lex_dfa.yytext & "' ??");
        num_errors := num_errors + 1;}

%%
with parasail_tokens; 
use  parasail_tokens;
use text_io;

package parasail_lex is
  
  lines      : positive := 1;
  num_errors     : natural := 0;
  Trace          : Boolean := False;

  procedure ECHO_L; --local version_of define_string.
  procedure linenum; 

  function yylex return token;

end parasail_lex;

package body parasail_lex is

  procedure ECHO_L is
  --
  -- Local version of the  define string.
  -- 
  begin
     text_io.put(yytext);
  end ECHO_L;


  procedure linenum is
    line_number_string : constant string :=
          integer'image ( lines );
  begin
    lines := lines + 1;
    put(line_number_string);
    for i in 1 .. 5 - integer ( line_number_string'length ) loop
      text_io.put(" ");
    end loop;

  end linenum;

##

end parasail_lex;

(A)Yacc-based parser for ParaSail

Here is the ayacc-compatible grammar for ParaSail and a simple driver program adapted from an old Ada parser.  Again the commenting conventions and the code are in Ada, but it should be straightforward to transform it into some other language.

--------------------------------------
-- Tentative YACC Grammar for ParaSail
--------------------------------------

-- Single-character delimiters --
%token ',' ';' ':' '.'
%token '+' '-' '*' '/' 
%token '~' '?'
%token '(' ')' '[' ']' '<' '>' '{' '}'
%token '|' 
%token PRIME -- '''

-- Compound delimiters --
%token COMPARE -- "=?"
%token EQ   -- "=="
%token NEQ  -- "!="
%token GEQ  -- ">="
%token LEQ  -- "<="
%token POWER  -- "**"
%token ASSIGN -- ":="
%token SWAP   -- ":=:"
%token DOT_DOT -- ".."
%token DOUBLE_COLON  -- "::"
%token DOUBLE_LEFT_BRACKET  -- "[["
%token DOUBLE_RIGHT_BRACKET -- "]]"
%token REFERS_TO  -- "=>"
%token GIVES    -- "->"
%token IMPLIES    -- "==>"
%token SEQUENCE   -- ";;"
%token PARALLEL   -- "||"

-- Literals --
%token Char_Literal
%token Enum_Literal
%token Integer_Literal 
%token Real_Literal
%token String_Literal

-- Identifier --
%token Identifier 

-- Reserved words --
%token ABS_kw
%token ABSTRACT_kw
%token ALL_kw
%token AND_kw
%token BLOCK_kw
%token CASE_kw
%token CLASS_kw
%token CONCURRENT_kw
%token CONST_kw
%token CONTINUE_kw
%token EACH_kw
%token ELSE_kw
%token ELSIF_kw
%token END_kw
%token EXIT_kw
%token EXPORTS_kw
%token EXTENDS_kw
%token FOR_kw
%token FORWARD_kw
%token FUNCTION_kw
%token IF_kw
%token IMPORT_kw
%token IN_kw
%token INTERFACE_kw
%token IS_kw
%token LOCKED_kw
%token LOOP_kw
%token MOD_kw
%token MUTABLE_kw
%token NEW_kw
%token NOT_kw
%token NULL_kw
%token OF_kw
%token OPERATOR_kw
%token OPTIONAL_kw
%token OR_kw
%token PROCEDURE_kw
%token QUEUED_kw
%token REF_kw
%token REM_kw
%token RETURN_kw
%token REVERSE_kw
%token SELECT_kw
%token SOME_kw
%token THEN_kw
%token TYPE_kw
%token VAR_kw
%token WHILE_kw
%token WITH_kw
%token XOR_kw

%start module_list

{ 
   subtype yystype is integer;
}


%%

module_list : 
    module
  | module_list module
  ;

module : 
    import_clauses interface_declaration ';' 
  | import_clauses class_definition ';' 
  ;

import_clauses : 
  | import_clauses IMPORT_kw qualified_name_list ';'
  ;

qualified_name_list : 
    qualified_name
  | qualified_name_list ',' qualified_name
  ;

interface_declaration : 
   opt_ABSTRACT_kw opt_CONCURRENT_kw INTERFACE_kw module_defining_name 
     formals_and_implemented_interfaces
     IS_kw
      interface_element_list
   END_kw INTERFACE_kw module_defining_name ;
   
opt_ABSTRACT_kw :  ABSTRACT_kw | ;

opt_CONCURRENT_kw : CONCURRENT_kw | ;

formals : '<' opt_module_formal_list '>' ;

formals_and_implemented_interfaces :
    formals
  | opt_formals EXTENDS_kw interface_name_list
  ; 

opt_formals : formals | ;

interface_name_list :
    interface_name
  | interface_name_list ',' interface_name
  ;

interface_name : module_name | module_instantiation ;
   
module_defining_name : qualified_name ;

opt_module_formal_list : module_formal_list | ;

module_formal_list : 
    annotated_module_formal 
  | module_formal_list ';' annotated_module_formal 
  ;

annotated_module_formal : opt_annotation module_formal opt_annotation ;

opt_annotation : annotation | ;

module_formal : type_formal | value_formal ;

type_formal : 
    Identifier IS_kw module_instantiation 
  | module_instantiation 
  ;

value_formal : 
    id_list ':' type_name 
  | id_list ':' type_name ASSIGN simple_expression  -- to avoid use of '>'
  ;

id_list : 
    Identifier
  | id_list ',' Identifier
  ;

type_name : qualified_name ;

qualified_name : 
    Identifier 
  | qualified_name DOUBLE_COLON Identifier ;


module_instantiation : 
  module_name '<' opt_module_actual_list '>' ;


module_name : qualified_name ;

opt_module_actual_list : module_actual_list | ;

module_actual_list :
    module_actual 
  | module_actual_list ',' module_actual 
  ;

module_actual : 
    type_specifier_or_expression
  | Identifier REFERS_TO type_specifier_or_expression
  ;

-- simple_expression subsumes type_name in this rule
type_specifier_or_expression : 
    type_name annotation
  | simple_expression              -- to avoid problems with '>'
  | module_instantiation
  ;
  
type_specifier : 
    type_name annotation 
  | type_name 
  | module_instantiation 
  ;

interface_element_list : 
  | interface_element_list interface_element ';'
  ;

interface_element : 
    operation_declaration 
  | object_declaration 
  | interface_declaration 
  | type_declaration 
  ;


class_definition :
   opt_CONCURRENT_kw CLASS_kw module_defining_name 
      formals_and_extended_interface 
   IS_kw
      class_element_list
   END_kw CLASS_kw module_defining_name ;

formals_and_extended_interface :
    formals
  | opt_formals EXTENDS_kw interface_name
  | opt_formals EXTENDS_kw Identifier ':' interface_name
  ; 


class_element_list : 
    local_class_element_list
  EXPORTS_kw 
    exported_class_element_list ;

local_class_element_list :
  | local_class_element_list local_class_element ';'
  ;

local_class_element : interface_element | exported_class_element ;
  
exported_class_element_list :
  | exported_class_element_list exported_class_element ';'
  ;

exported_class_element : 
    operation_definition 
  | object_definition 
  | class_definition 
  ;
  
   
annotation : '{' annotation_element_list '}' ;

annotation_element_list : 
    annotation_element
  | annotation_element_list ';' annotation_element
  ;

annotation_element : interface_element | condition ;

condition : expression ;


operation_declaration : 
    function_declaration 
  | procedure_declaration 
  | operator_declaration 
  ;

function_declaration :
  FUNCTION_kw Identifier operation_inputs GIVES operation_outputs ;

procedure_declaration :
  PROCEDURE_kw Identifier operation_inputs ;
  
operator_declaration :
  OPERATOR_kw operator_designator operation_inputs opt_gives_operation_outputs ;

opt_gives_operation_outputs : GIVES operation_outputs | ;
  
operator_designator : String_Literal ;
  
operation_inputs :
    annotated_operation_input
  | '(' opt_annotated_operation_input_list ')' opt_annotation 
  ;

opt_annotated_operation_input_list : annotated_operation_input_list | ;

annotated_operation_input_list : 
    annotated_operation_input
  | annotated_operation_input_list ';' annotated_operation_input
  ;

annotated_operation_input : opt_annotation operation_input opt_annotation ;

operation_input : 
    id_list ':' opt_input_modifier operand_type_specifier 
  | input_modifier operand_type_specifier 
  | operand_type_specifier 
  ;

opt_input_modifier : input_modifier | ;
  
operand_type_specifier : type_name | type_formal ;

input_modifier : 
    output_modifier 
  | QUEUED_kw opt_output_modifier
  | LOCKED_kw opt_output_modifier
  ;


operation_outputs : 
    annotated_operation_output
  | '(' annotated_operation_output_list ')' opt_annotation 
  ;

annotated_operation_output_list :
    annotated_operation_output
  | annotated_operation_output_list ';' annotated_operation_output
  ;

annotated_operation_output : opt_annotation operation_output opt_annotation ;

operation_output : 
    id_list ':' opt_output_modifier operand_type_specifier
  | output_modifier operand_type_specifier 
  | operand_type_specifier 
  ;

opt_output_modifier : output_modifier | ;

output_modifier :  
    REF_opt_optional_mutable 
  | REF_opt_optional_mutable VAR_kw 
  | REF_opt_optional_mutable CONST_kw 
  ;

REF_opt_optional_mutable :
    REF_kw
  | REF_kw OPTIONAL_kw
  | REF_kw MUTABLE_kw
  | REF_kw OPTIONAL_kw MUTABLE_kw
  ;

object_declaration : 
   var_or_const Identifier ':' type_specifier opt_ASSIGN_expression ;

opt_ASSIGN_expression : ASSIGN expression | ;
   
var_or_const : VAR_kw | CONST_kw ;

object_definition :
    CONST_kw Identifier opt_colon_type_specifier ASSIGN expression
  | VAR_kw Identifier ':' opt_OPTIONAL_kw opt_MUTABLE_kw type_specifier 
      opt_ASSIGN_expression
  | VAR_kw Identifier ASSIGN expression 
  ;

opt_colon_type_specifier : ':' type_specifier | ;

opt_OPTIONAL_kw : OPTIONAL_kw | ;
opt_MUTABLE_kw : MUTABLE_kw | ;

type_declaration : TYPE_kw Identifier IS_kw opt_NEW_kw type_specifier ;

opt_NEW_kw : NEW_kw | ;

operation_definition : 
    function_definition 
  | procedure_definition 
  | operator_definition 
  ;

function_definition : 
  function_declaration IS_kw statement_list ';' END_kw FUNCTION_kw Identifier ;

procedure_definition : 
  procedure_declaration IS_kw statement_list ';' END_kw PROCEDURE_kw Identifier ;

operator_definition : 
  operator_declaration IS_kw statement_list ';' END_kw OPERATOR_kw Identifier  ;


statement_list : 
    annotated_statement
  | statement_list SEQUENCE statement_list
  | statement_list ';' statement_list
  | statement_list PARALLEL statement_list
  | statement_list ';' PARALLEL statement_list
  ;
  
opt_semi : ';' | ;

annotated_statement : opt_annotation statement opt_annotation ;

statement : 
    local_declaration 
  | local_definition 
  | simple_statement 
  | label compound_statement
  | compound_statement
  | '(' statement_list opt_semi ')' 
  ;

opt_label : label | ;

simple_statement :
    name ASSIGN expression
  | name SWAP name
  | name '(' opt_operation_actual_list ')'
  | RETURN_kw opt_WITH_values 
  | CONTINUE_kw LOOP_kw opt_id opt_WITH_values 
  | EXIT_kw compound_statement_kind opt_id opt_WITH_values
  ;

opt_operation_actual_list : operation_actual_list | ;

opt_WITH_values : WITH_values | ;

WITH_values : WITH_kw '(' operation_actual_list ')' ;

opt_id : Identifier | ;

compound_statement_kind : LOOP_kw | IF_kw | CASE_kw | SELECT_kw | BLOCK_kw ;

local_declaration : operation_declaration | type_declaration ;

local_definition :
    object_definition 
  | operation_definition 
  ;

label : '*' Identifier '*' ;

compound_statement :
    if_statement
  | case_statement
  | while_loop_statement
  | for_loop_statement
  | block_statement 
  | select_statement
  ;

if_statement : 
  IF_kw condition THEN_kw 
     statement_list ';'
  elsif_list
  opt_else
  END_kw IF_kw opt_id opt_WITH_values ;

elsif_list : 
    elsif_clause
  | elsif_list elsif_clause
  ;

elsif_clause :
  ELSIF_kw condition THEN_kw
     statement_list ';' ;

opt_else : ELSE_kw statement_list ';' | ;

case_statement : 
  CASE_kw expression OF_kw
    case_alt_list
    opt_default_alt
  END_kw CASE_kw opt_id opt_WITH_values ;

case_alt_list : 
    case_alt
  | case_alt_list case_alt
  ;

case_alt :
    '[' choice_list ']' REFERS_TO statement_list ';' ;

choice_list : 
    choice  
  | choice_list '|' choice 
  ;

choice : expression_or_range ;

opt_default_alt : '[' DOT_DOT ']' REFERS_TO statement_list ';' | ;

while_loop_statement :
  WHILE_kw condition LOOP_kw
    statement_list ';'
  END_kw LOOP_kw opt_id opt_WITH_values ;

for_loop_statement :
  FOR_kw iterator_list opt_direction LOOP_kw
    statement_list ';'
  END_kw LOOP_kw opt_id opt_WITH_values ;

iterator_list : 
    iterator 
  | iterator_list ',' iterator
  ;

iterator :
    Identifier IN_kw choice_list
  | EACH_kw Identifier OF_kw expression
  | Identifier ASSIGN expression THEN_kw next_value_list WHILE_kw condition
  | Identifier REFERS_TO name THEN_kw next_name_list WHILE_kw condition
  ;

next_value_list : 
    expression 
  | next_value_list PARALLEL expression 
  ;

next_name_list : 
    name 
  | next_name_list PARALLEL name 
  ;

opt_direction : direction | ;

direction : CONCURRENT_kw | FORWARD_kw | REVERSE_kw ;

select_statement :
  SELECT_kw 
     select_alt_list
  END_kw SELECT_kw opt_id opt_WITH_values ;

select_alt_list : 
    select_alt
  | select_alt_list PARALLEL select_alt
  ;

select_alt : '[' statement_list opt_semi ']' REFERS_TO statement_list opt_semi ;

block_statement :
  BLOCK_kw
    statement_list ';'
  END_kw BLOCK_kw opt_id opt_WITH_values ;
 
expression : 
    simple_expression
  | expression binary_operator expression
  | expression IN_kw expression_or_range
  | expression NOT_kw IN_kw expression_or_range
  | expression '?' expression ':' expression 
  ;

simple_expression :  -- used to avoid use of '>' in module instantiation
    primary
  | unary_operator simple_expression  -- makes unary ops higher precedence
  ;

expression_or_range : 
    expression
  | expression DOT_DOT expression ;
  
primary :
    name
  | Integer_Literal
  | Real_Literal
  | Char_Literal
  | String_Literal
  | Enum_Literal
  | NULL_kw
  | '(' expression ')'
  | '(' conditional_expression ')'
  | '(' quantified_expression ')'
  | aggregate
  | DOUBLE_LEFT_BRACKET expression DOUBLE_RIGHT_BRACKET 
  ;
  
name :
    qualified_name attribute_list opt_PRIME
  | qualified_name PRIME
  | qualified_name 
  | name '(' opt_operation_actual_list ')'
  | name '[' opt_operation_actual_list ']'
  | name '.' selector
  ;

attribute_list :
    Enum_Literal
  | attribute_list Enum_Literal 
  ;

opt_PRIME : PRIME | ;

operation_actual_list : 
    operation_actual 
  | operation_actual_list ',' operation_actual 
  ;

operation_actual : 
    expression
  | Identifier REFERS_TO expression 
  ;

selector : Identifier ;

unary_operator : '+' | '-' | ABS_kw | NOT_kw ;

binary_operator :
    '+'  | '-' | '*'  | '/' | POWER | '~' 
  | COMPARE | EQ | NEQ | '<' | LEQ | '>' | GEQ
  | AND_kw | OR_kw | XOR_kw  
  | AND_kw THEN_kw | OR_kw ELSE_kw | IMPLIES
  ;


aggregate : class_aggregate | container_aggregate ;

class_aggregate : '(' opt_operation_actual_list ')' ;

container_aggregate : '[' container_element_list ']' ;
  
container_element_list : 
    container_element 
  | container_element_list ',' container_element 
  ;

container_element : 
    expression
  | choice_list REFERS_TO filtered_expression_stream ;

container_key : expression ;

filtered_expression_stream : 
    expression_stream
  | expression_stream ':' condition
  ;

expression_stream : 
    expression 
  | expression_stream '~' expression
  ;

conditional_expression :
    if_expression
  | case_expression
  ;

if_expression : 
  IF_kw condition THEN_kw 
     expression
  elsif_expr_list
  opt_else_expr ;

elsif_expr_list : 
    elsif_expr_clause
  | elsif_expr_list elsif_expr_clause
  ;

elsif_expr_clause :
  ELSIF_kw condition THEN_kw expression ;

opt_else_expr : ELSE_kw expression | ;

case_expression : 
  CASE_kw expression OF_kw
    case_expr_alt_list
    opt_default_expr_alt ;

case_expr_alt_list : 
    case_expr_alt
  | case_expr_alt_list case_expr_alt
  ;

case_expr_alt : '[' choice_list ']' REFERS_TO expression ;

opt_default_expr_alt : '[' DOT_DOT ']' REFERS_TO expression | ;

quantified_expression :
    FOR_kw ALL_or_SOME_kw iterator ':' condition ;

ALL_or_SOME_kw : ALL_kw | SOME_kw ;

%%


package parasail_parser is

    procedure yyparse;

    echo : boolean := false;
    number_of_errors : natural := 0;


end parasail_parser;

with parasail_tokens, parasail_lex_io, parasail_goto, parasail_shift_reduce;
with parasail_lex, text_io;

use  parasail_tokens, parasail_lex_io, parasail_goto, parasail_shift_reduce;
use  parasail_lex, text_io;
package body parasail_parser is

    procedure yyerror(s: in string := "syntax error") is
    begin
       number_of_errors := number_of_errors + 1;
       put("<<< *** ");
       put_line(s);
    end yyerror;


##%procedure_parse

end parasail_parser;

------------------

And here is the driver program, also written in Ada:

with parasail_parser, parasail_lex_io, parasail_lex, text_io;
use  parasail_parser, text_io;

with parasail_lex_dfa;
procedure parasail_main is
  in_file_name: string(1..80);
  last        : natural;
begin
    text_io.put("Enter input file: ");
    text_io.get_line(in_file_name, last);
    parasail_lex_io.open_input(in_file_name(1..last));
    parasail_lex_io.create_output;

    put_line("---- Starting parse ----");

    -- parasail_lex_dfa.aflex_debug := True;

    parasail_lex.linenum;
    yyparse;


    parasail_lex_io.close_input;
    parasail_lex_io.close_output;

    put_line("---- Finished parse ----");
    new_line;
    put(integer'image(number_of_errors));
    put_line(" errors found");


end parasail_main;

An intentional race condition in a ParaSail concurrent loop

An intriguing question, given the presence of the concurrent loop construct in ParaSail, is what would happen if there were a loop exit or a return statement in the body of a concurrent loop.  Earlier we have said that only forward and reverse loops would allow an exit statement.  But perhaps we should allow an exit or a return from within a concurrent loop as a way of terminating a concurrent computation, aborting all threads besides the one exiting or returning.  This would essentially be an intentional race condition, where the first thread to exit or return wins the race.  This would seem to be a relatively common paradigm when doing a parallel search, where you want to stop as soon as the item of interest is found in the data structure being walked, for example, and there is no need for the other threads to continue working.

In some sense, a return statement in a concurrent loop is easier to understand, if we presume we are in a function searching (in parallel) for some item in a data structure, and we want to return the item as soon as any thread finds it.  An exit statement in a concurrent loop is a bit harder to understand, since we would need a way to record the result of the winning thread somehow.  Perhaps we would want to allow some code associated with the exit statement that occurs after all of the other threads have been aborted.  Perhaps "exit loop then record winner;" might be a syntax indicating that the record winner code is to be executed after the loop has effectively been stopped, but still in the context of the winning thread, with visibility on the local variables of the loop body containing the exit loop then ... construct.

For example, using the generalized for loop from the previous posting:

    var Winner : Node := null;
    for T := Root then T.Left || T.Right 
      while T != null concurrent loop
        if T.Key == Desired_Key then
            exit loop then Winner := T;
        end if;
    end loop;

At this point Winner is either still null if no node in the tree has the Desired_Key, or is equal to some node whose Key equals the Desired_Key. If there is more than one such node, it would be non-deterministic which such node Winner designates. 

Clearly this kind of brute force search of the tree would not be needed if the tree were organized based on Key values.  This example presumes the Key is not controlling the structure of the tree.  Also note that if this were a function whose whole purpose was to find the node of interest, the exit loop then ... statement could presumably be replaced by simply return T and we wouldn't need the local variable Winner at all.

Generalized For loops in ParaSail

As we start to dive into the lower-level control structures for ParaSail, one clearly very important structure is the for loop.  We have already suggested the basic structure:

    for I in 1..10 [forward | reverse | concurrent] loop

However, it would be nice if the for loop could also be used for more general looping structures. A number of languages have adopted a for loop where there is an initialization, a "next step", and a termination/continuation condition.  The best known is probably that of C, inherited by C++ and Java:

    for (init; test; next)...

The init and next parts are arbitrary statements (to be more precise, expressions evaluated for their side-effects), while test is treated as a condition whose truth determines whether iteration continues.

A number of LISP variants, and languages based to some degree on LISP such as Dylan, also have a similar generalized looping capability:
Scheme:

    (do ((I initial next) (J initial next) ... )
      (test) 
        loop body
    )

Dylan:

    for (I = initial then next while: test)
        loop body
    end for

In the case of the C for loop, next is an arbitrary statement, whereas for the LISP-based languages, next is the next value for the associated loop variable. This is perhaps related to the fact that in C there is special syntax for incrementing and decrementing a variable, meaning that a statement that increments the loop variable (e.g. I++) can be as concise as simply specifying the next value (e.g. I+1) in languages without this special syntax.

The LISP-based languages generally define these sorts of for/do loops in terms of tail recursion, where the next value is what would be passed as the parameter in the tail-recursive call.  It is interesting to consider whether more general kinds of recursive algorithms could be mapped to an iterative control structure.  For example, could a recursive walk of a binary tree be represented as some kind of for loop?  This is particularly interesting for a language with implicit parallelism, where it might be desirable to have multiple threads involved in walking the various branches of the tree.

The above considerations lead us to the following possible approach to a generalized for loop in ParaSail (borrowing heavily from the Dylan syntax):

    for T := Root then T.Left || T.Right 
      while T != null loop
        loop body
    end loop

This would represent a "loop" which on each iteration splits into two threads, one processing T.Left and the other T.Right. The iteration stops when all of the threads have hit a test for T != null which returns false.  The general syntax would be:

    for var := initial then next {|| next} 
      [while | until] test [concurrent] loop
        loop body
    end loop

If we were to specify concurrent loop then it would presumably imply that the daughter threads are to be created immediately once the test was found to be true, not waiting for the loop body of the parent thread to finish. This would effectively create a thread for every node in the tree, with the loop body executing concurrently for each node.