Pointer-free primitives for ParaSail

Having pretty much settled on eliminating explicit pointers from ParaSail (largely to simplify compile-time alias analysis and race-condition elimination), the question is: what sorts of primitive data structures are needed in ParaSail to allow the user to construct essentially arbitrary abstractions on top of the primitives without using explicit pointers? The ParaSail interface/class module already provides a basic kind of basic record or struct capability.  As mentioned in an earlier posting, we have also suggested the use of the keyword optional to signify that an object might or might not have a value of its specified type, with its default being a null value.  Internally this could be implemented either with an extra bit to signify null-ness, or with an implicit level of indirection with a null pointer used to indicate null-ness (some indirection is clearly necessary for a recursive data structure). 

By using the optional keyword and the basic record capability provided by a class, the user can quite easily construct structures such as linked lists and binary trees.  However, more complex structures will have to end up falling back on a generalized notion of container with pointers replaced by the use of generalized indexing.  For example, a directed graph structure can be represented by a vector of nodes with the edges between the nodes being represented by indices into the vector.  To some extent this is going back to a Fortran array-oriented view of the world.  However, with the arrays being extensible, and the elements of the arrays being arbitrarily complex objects, which themselves are potentially optional and extensible, there is significantly more flexibility available to the programmer than what the original Fortran arrays provided.

As a first stab at what primitive container types are needed, it would seem that a basic array type, indexed by integers, and extensible only by whole-array assignment with a longer or shorter array, might be adequate.  The elements of the array would be of an arbitrary type, including user-defined types.  The whole-array assignment would deal with whatever storage management is necessary to reuse or reclaim the prior value of the object being assigned.  The compiler would attempt to arrange to have the new value be created in the storage region associated with the object to which it will be assigned, so as to avoid having to physically move the new value into that storage region as part of the assignment (see earlier post on region-based storage management).  For example, given:

    var X : Basic_Array<...> := Build_Array(Length => 10);
    ...
    X := Extend_Array(X, New_Length => 20);

the compiler would arrange for the calls on Build_Array and Extend_Array to create their resulting array in a storage region appropriate for X, so that the assignment need not move the created array into that region.  Essentially, as part of being called, a function would receive information about the region in which its result(s) should be allocated.  This information would be propagated as necessary to try to minimize the unnecessary movement of data between storage regions as part of an assignment operation.

It would seem that with this combination of the record-like capability provided by classes, the notion of optional, and something like this Basic_Array type extensible only by whole-array assignment, we have all of the building blocks needed to create arbitrary data structures in ParaSail without the use of pointers.

Updated (A)Yacc grammar for ParaSail

Here is an update to the ParaSail (A)Yacc grammar posted a few weeks ago.   This one has no shift/reduce or reduce/reduce conflicts.   The "N Queens" example is accepted by this grammar.  Below the grammar is the slightly updated (A)Flex lexer:

--------------------------------------
-- 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   -- "||"
%token PLUS_ASSIGN -- "+="
%token MINUS_ASSIGN -- "-="
%token TIMES_ASSIGN -- "*="
%token DIVIDE_ASSIGN -- "/="
%token POWER_ASSIGN -- "**="
%token CONCAT_ASSIGN -- "|="
%token AND_ASSIGN -- "and="
%token OR_ASSIGN -- "or="
%token XOR_ASSIGN -- "xor="

-- 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 IMPLEMENTS_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 standalone_operation_definition ';'
  ;

import_clauses : 
  | import_clauses IMPORT_kw qualified_name_list ';'
  ;

qualified_name_list : 
    qualified_name
  | qualified_name_list ',' qualified_name
  ;

interface_declaration : 
   opt_interface_qualifier INTERFACE_kw module_defining_name 
     formals_and_implemented_interfaces
     IS_kw
      interface_element_list
   END_kw INTERFACE_kw module_defining_name ;
   
opt_interface_qualifier : interface_qualifier | ;

interface_qualifier : 
    class_qualifier
  | ABSTRACT_kw opt_class_qualifier
  ;

opt_class_qualifier : class_qualifier | ;

class_qualifier : CONCURRENT_kw ;

standalone_operation_definition : 
    function_definition
  | procedure_definition
  ;

formals : '<' opt_module_formal_list '>' ;

formals_and_implemented_interfaces :
    formals
  | formals implements_list
  | opt_formals EXTENDS_kw interface_name opt_implements_list
  ; 

opt_formals : formals | ;

opt_implements_list : implements_list | ;

implements_list : IMPLEMENTS_kw interface_name_list ;

interface_name_list :
    interface_name
  | interface_name_list ',' interface_name
  ;

interface_name : module_name | module_instantiation ;
   
module_name : qualified_name ;

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 type_formal opt_annotation
  | opt_annotation operation_formal
  | opt_annotation value_formal opt_annotation
  ;

opt_annotation : annotation | ;

type_formal : 
    Identifier IS_kw module_instantiation 
  | module_instantiation 
  ;

operation_formal : operation_declaration ;

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

id_list : 
    Identifier
  | id_list ',' Identifier
  ;

type_name : 
    qualified_name 
  | polymorphic_type_name
  ;

polymorphic_type_name : qualified_name '+' ;

qualified_name : 
    Identifier 
  | qualified_name DOUBLE_COLON Identifier ;


module_instantiation : 
  module_name '<' opt_module_actual_list '>' ;

opt_module_actual_list : module_actual_list | ;

module_actual_list :
    module_actual 
  | module_actual_list ',' module_actual 
  ;

module_actual : 
    simple_type_specifier_or_expression
  | Identifier REFERS_TO simple_type_specifier_or_expression
  ;

-- simple_expression subsumes simple type_name in this rule
simple_type_specifier_or_expression : 
    qualified_name annotation      -- polymorphic type name not allowed here
  | simple_expression              -- simple_expr to avoid problems with '>'
  | module_instantiation
  ;
  
annotated_type_specifier : 
    type_specifier
  | type_specifier annotation
  ;

type_specifier : 
    opt_CONCURRENT_kw type_name 
  | opt_CONCURRENT_kw module_instantiation 
  ;

opt_CONCURRENT_kw : CONCURRENT_kw | ;

interface_element_list : 
  | interface_element_list interface_element ';'
  ;

interface_element : 
    operation_declaration 
  | object_declaration 
  | interface_declaration 
  | type_declaration 
  ;


class_definition :
   opt_class_qualifier CLASS_kw module_defining_name 
      class_formals_and_implemented_interfaces
   IS_kw
      class_element_list
   END_kw CLASS_kw module_defining_name ;

class_formals_and_implemented_interfaces :
    formals_and_implemented_interfaces
  | opt_formals EXTENDS_kw Identifier ':' interface_name opt_implements_list
  ; 


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 | quantified_expression ;

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 :
    simple_operation_input opt_annotation
  | annotation simple_operation_input opt_annotation
  | '(' opt_annotated_operation_input_list ')' opt_annotation
  ;

simple_operation_input :   -- avoids trailing use of "IS"
    id_list ':' opt_input_modifier simple_operand_type_specifier 
  | input_modifier simple_operand_type_specifier 
  | simple_operand_type_specifier 
  ;

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 : 
    operation_input opt_annotation
  | annotation operation_input opt_annotation 
  | opt_annotation function_declaration
  | opt_annotation procedure_declaration
  ;

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

opt_input_modifier : input_modifier | ;
  
simple_operand_type_specifier :
    type_name
  | module_instantiation
  ;

operand_type_specifier : 
    simple_operand_type_specifier
  | Identifier IS_kw module_instantiation 
         -- NOTE: Operation can have "type" parameters 
         -- such as "Left_Type is Integer<>"
  ;

input_modifier : 
    output_modifier 
  | QUEUED_kw opt_output_modifier
  | LOCKED_kw opt_output_modifier
  ;


operation_outputs : 
    simple_operation_output opt_annotation
  | annotation simple_operation_output opt_annotation
  | '(' annotated_operation_output_list ')' opt_annotation
  ;

simple_operation_output :   -- avoids trailing use of "IS"
    id_list ':' opt_output_modifier simple_operand_type_specifier
  | output_modifier simple_operand_type_specifier
  | simple_operand_type_specifier
  ;

annotated_operation_output_list :
    annotated_operation_output
  | annotated_operation_output_list ';' annotated_operation_output
  ;

annotated_operation_output : 
    operation_output opt_annotation
  | 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 :  
    OPTIONAL_kw
  | 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_kw Identifier ':' 
      opt_OPTIONAL_kw opt_MUTABLE_kw annotated_type_specifier 
      opt_ASSIGN_expression
  | CONST_kw Identifier ':' opt_OPTIONAL_kw annotated_type_specifier 
      opt_ASSIGN_expression
  ;

opt_ASSIGN_expression : ASSIGN expression | ;
   
object_definition :
    CONST_kw Identifier ASSIGN expression
  | VAR_kw Identifier ASSIGN expression
  | CONST_kw Identifier REFERS_TO name
  | VAR_kw Identifier REFERS_TO name
  ;

opt_OPTIONAL_kw : OPTIONAL_kw | ;
opt_MUTABLE_kw : MUTABLE_kw | ;

type_declaration : 
    TYPE_kw Identifier IS_kw opt_NEW_kw annotated_type_specifier ;

opt_NEW_kw : NEW_kw | ;

operation_definition : 
    function_definition 
  | procedure_definition 
  | operator_definition 
  ;

function_definition : 
  function_declaration IS_kw 
     statement_list_with_semi 
  END_kw FUNCTION_kw Identifier ;

procedure_definition : 
  procedure_declaration IS_kw 
     statement_list_with_semi 
  END_kw PROCEDURE_kw Identifier ;

operator_definition : 
  operator_declaration IS_kw 
     statement_list_with_semi 
  END_kw OPERATOR_kw Identifier  ;

statement_list_opt_semi :
    statement_sequence
  | statement_list_with_semi
  ;

statement_list_with_semi : 
    statement_sequence_with_semi
  | statement_list_opt_semi PARALLEL statement_sequence_with_semi
  ;

statement_list :                -- "||" is lower precedence than ";" and ";;"
    statement_sequence
  | statement_list_opt_semi PARALLEL statement_sequence
  ;

statement_sequence_with_semi : statement_sequence ';' ;

statement_sequence :
    annotated_statement
  | statement_sequence SEQUENCE annotated_statement
  | statement_sequence_with_semi SEQUENCE annotated_statement
  | statement_sequence_with_semi annotated_statement
  ;
  
annotated_statement : 
    opt_annotation local_declaration  
            -- NOTE: these already allow trailing annotations
  | opt_annotation statement opt_annotation
  ;

statement : 
    local_definition 
  | simple_statement 
  | label compound_statement
  | compound_statement
  -- NOTE: now will use BLOCK instead of: '(' statement_list_opt_semi ')' 
  ;

opt_label : label | ;

simple_statement :
    name assign_operator expression
  | name SWAP name
  | name '(' opt_operation_actual_list ')'
  | '(' operation_actual_list ')' ASSIGN expression  -- multiple assignment
  | RETURN_kw expression
  | 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 
  | object_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_with_semi
  elsif_list
  opt_else
  END_kw IF_kw opt_id opt_WITH_values ;

elsif_list : 
  | elsif_list elsif_clause
  ;

elsif_clause :
  ELSIF_kw condition THEN_kw
     statement_list_with_semi ;

opt_else : ELSE_kw statement_list_with_semi | ;

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_with_semi ;

choice_list : 
    choice  
  | choice_list '|' choice 
  ;

choice : term_or_range ;

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

while_loop_statement :
  WHILE_kw condition LOOP_kw
    statement_list_with_semi
  END_kw LOOP_kw opt_id opt_WITH_values ;

for_loop_statement :
  FOR_kw iterator_spec opt_direction LOOP_kw
    statement_list_with_semi
  END_kw LOOP_kw opt_id opt_WITH_values ;

iterator_spec : 
    iterator 
  | '(' iterator_list ')'
  ;

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
  | Identifier ':' type_specifier ASSIGN expression 
  ;

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_sequence_with_semi ;

block_statement :
  BLOCK_kw
    statement_list_with_semi
  END_kw BLOCK_kw opt_id opt_WITH_values ;
 
expression :  
    expression_component
  | expression '|' expression_component
  ;

expression_component : -- logical operators are non-associative
    comparison_expression
  | comparison_expression logical_operator comparison_expression
  | comparison_expression '?' expression_component ':' expression_component
  ;

comparison_expression :  -- comparisons are non associative
    simple_expression
  | simple_expression comparison_operator simple_expression
  | simple_expression IN_kw type_or_term_or_range
  | simple_expression NOT_kw IN_kw type_or_term_or_range
  | simple_expression IS_kw NULL_kw
  | simple_expression NOT_kw NULL_kw
  ;

simple_expression : -- used to avoid use of '>' in module instantiation
    term
  | simple_expression adding_operator term
  ;

type_or_term_or_range :
    polymorphic_type_name
  | term_or_range       -- includes simple type name
  ;

term_or_range : 
    term
  | term DOT_DOT term  -- avoid ambiguity on use of '+'
  ;
  
term : 
    factor
  | term multiplying_operator factor
  ;

factor : 
    primary
  | primary power_operator factor  -- right associative
  | unary_operator factor  -- makes unary ops higher precedence 
  ;

primary :
    name
  | Integer_Literal
  | Real_Literal
  | Char_Literal
  | String_Literal
  | Enum_Literal
  | NULL_kw
  | '(' 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 ;

adding_operator : '+' | '-' ;

multiplying_operator : '*' | '/' ;

power_operator : POWER ;

assign_operator : 
    ASSIGN | PLUS_ASSIGN | MINUS_ASSIGN | TIMES_ASSIGN | DIVIDE_ASSIGN 
  | CONCAT_ASSIGN | AND_ASSIGN | OR_ASSIGN | XOR_ASSIGN
  ;

comparison_operator : COMPARE | EQ | NEQ | '<' | LEQ | '>' | GEQ ;

logical_operator :
    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 : '[' opt_container_element_list ']' ;
  
opt_container_element_list : container_element_list | ;

container_element_list : 
    container_element 
  | container_element_list ',' container_element 
  ;

container_element : 
    expression_component
  | choice_list REFERS_TO filtered_expression_stream 
  | DOT_DOT REFERS_TO filtered_expression_stream 
  ;

container_key : expression ;

filtered_expression_stream : 
    expression
  | expression ':' condition
  ;

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 ;

case_expr_alt_list : 
    case_expr_alt
  | case_expr_alt_list ';' case_expr_alt
  ;

case_expr_alt : 
    '[' choice_list ']' REFERS_TO expression 
  | '[' DOT_DOT ']' REFERS_TO expression   -- NOTE: must come last
  ;

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 (A)Flex lexer:
---------------------------------------------------

%START IDENT Z


GRAPHIC_CHAR  [ !"#$%&'()*+,-./0-9:;<=>?@A-Z\[\\\]^_`a-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);}
"implements" {ECHO_L; ENTER(Z); return (IMPLEMENTS_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);}
"+="  {ECHO_L; ENTER(Z); return(PLUS_ASSIGN);}
"-="  {ECHO_L; ENTER(Z); return(MINUS_ASSIGN);}
"*="  {ECHO_L; ENTER(Z); return(TIMES_ASSIGN);}
"/="  {ECHO_L; ENTER(Z); return(DIVIDE_ASSIGN);}
"**="  {ECHO_L; ENTER(Z); return(POWER_ASSIGN);}
"|="  {ECHO_L; ENTER(Z); return(CONCAT_ASSIGN);}
"and="  {ECHO_L; ENTER(Z); return(AND_ASSIGN);}
"or="  {ECHO_L; ENTER(Z); return(OR_ASSIGN);}
"xor="  {ECHO_L; ENTER(Z); return(XOR_ASSIGN);}

  -- 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('?');}

  -- 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.  See Ada LRM 2.6.

<Z>{CHAR_LITERAL}      {ECHO_L; ENTER(Z); return(Char_Literal);}

  -- Match all valid string literals.  See Ada LRM 2.6.

{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 does not support vertical tabs.  This causes use to fail
  -- when parsing some of the ACVC Btests.

[ \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
-----    if Trace then
-----      TEXT_IO.PUT_Line("Token :" & YYTEXT & ":");
-----    end if;
 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;

N Queens Problem in ParaSail

Here is a (parallel) solution to the "N Queens" problem in ParaSail, where we try to place N queens on an NxN chess board such that none of them can take each other. This takes the idea of using the "continue" statement as a kind of implicit recursion to its natural conclusion.  This presumes you can turn a "normal" data structure like Vector<> into a concurrent data structure by using the keyword "concurrent," which presumably means that locking is used on all operations to support concurrency.  It is debatable whether this use of a "continue" statement to effectively start the next iteration of a loop almost like a recursive call is easier or harder to understand than true recursion. 

interface N_Queens <N : Univ_Integer := 8> is
    // Place N queens on a checkerboard so that none of them can
    // "take" each other.
    type Row is new Integer<1, N>;
     
    function Place_Queens() -> Vector<Vector<Row>> 
      {for all I in Place_Queens#range : Length(Place_Queens[I]) == N};
end interface N_Queens;

class N_Queens <N : Univ_Integer := 8> is
    type Column is new Integer<1, N>;
    type Sum is Vector<Boolean, Index => Integer<2, 2*N>>;
    type Diff is Vector<Boolean, Index => Integer<1-N, N-1>>;
    
exports
    
    function Place_Queens() -> Vector<Vector<Row>> 
      {for all I in Place_Queens#range : Length(Place_Queens[I]) == N} is
      // Place N queens on checkerboard so that none of them can "take" each other
      var Solutions : concurrent Vector<Vector<Row>> := [];
      
      *Outer_Loop*
      for (C : Column := 1; Trial : Vector<Row> := [];
        Diag1 : SSum := [.. => #false]; Diag2 : Diff := [.. => #false]) loop
          // Iterate over the columns
        
          for R in Row concurrent loop
              // Iterate over the rows
              if not Diag1[R + C] and then not Diag2[R - C] then
                  // Found a Row/Column combination that is not on any diagonal
                  // already occupied.
                  if C < N then
                      // Keep going since haven't reached Nth column.
                      continue loop Outer_Loop with (C => C+1, Trial => Trial | R,
                        Diag1 => Diag1 | [(R+C) => #true],
                        Diag2 => Diag2 | [(R-C) => #true]);
                  else
                      // All done, remember trial result.
                      Solutions |= Trial;
                  end if;
              end if;
          end loop;
          
          
      end loop Outer_Loop;
      return Solutions;
      
    end function Place_Queens;
end class N_Queens;