🚀 go-pugleaf

Recently, I decided to write a longish Oberon program, and a problem
about the sematics of the type guard mechanism occured to me. Would
anybody care to comment? The problem is explained in the following
program code:

MODULE Test;

TYPE
  PList=POINTER TO List;
  PXList=POINTER TO XList;
  List=RECORD next:PList
  END;
  XList=RECORD(List) key:INTEGER
  END;

(*  We need the

        PROCEDURE find(p:PXList;x:INTEGER):PXList;

    with value equal to the  pointer to first list element
    whose key is greater or equal to x if such an element
    exists, and NIL otherwise *)

(*  Version 1

    This version does not work because the component
    q.next cannot be assigned to q without a typeguard
    (q.next is considered to be of type PList)

  PROCEDURE find(p:PXList;x:INTEGER):PXList;
   VAR q:PXList; 
   BEGIN
     q:=p;
     WHILE (q # NIL) & (q.key < x) DO
       q:=q.next
     END;
     RETURN q
   END find;
*)

(*  Version 2

    This version stops with a run-time error if and when q.next
    becomes equal to NIL. Essentially, the type guard q.next(PXList)
    requires that q.next be nonNIL

  PROCEDURE find(p:PXList;x:INTEGER):PXList;
   VAR q:PXList; 
   BEGIN
     q:=p;
     WHILE (q # NIL) & (q.key < x) DO
       q:=q.next(PXList)
     END;
     RETURN q
   END find;
*)

(*  Version 3

    This version version fails for the same reason as the
    previous one: q cannot be NIL if a typeguard is used

  PROCEDURE find(p:PXList;x:INTEGER):PXList;
   VAR q:PList; 
   BEGIN
     q:=p;
     WHILE (q # NIL) & (q(PXList).key < x) DO
       q:=q.next
     END;
     RETURN q(PXList)
   END find;
*)

(*  Version 4

    Finally, this works, but is inelegant due to the redundant
    NIL check on function return

  PROCEDURE find(p:PXList;x:INTEGER):PXList;
   VAR q:PList; 
   BEGIN
     q:=p;
     WHILE (q # NIL) & (q(PXList).key < x) DO
       q:=q.next
     END;
     IF q=NIL THEN RETURN NIL
     ELSE RETURN q(PXList)
     END
   END find;
*)

(*  Version 5

    Of course, this also works; but I find it contradicting
    the spirit of strong typing. The procedure find is intended
    to be used only with parameters of type PXList, and this 
    should be evident from the type of the argument. In a sense,
    the parameter type should be the "greatest common denominator"
    of the admissible types. 

  PROCEDURE find(p:PList;x:INTEGER):PList;
   VAR q:PList; 
   BEGIN
     q:=p;
     WHILE (q # NIL) & (q(PXList).key < x) DO
       q:=q.next
     END;
     RETURN q
   END find;
*)
(*
  For me the right solution to the above problem would be to
  specify that the type guard p(PXList) may be used whenever
  one knows that p is of type PXList OR p is equal to NIL.
  In that case Version 2 would work (as well as Version 3).
  The objection that p(PXList) guarantees the existence
  of p(PXList).key, and therefore p should not be equal to NIL
  when a typeguard is used is countered by remarking that the
  actual existence of the component p(PXList).key may be
  ascertained by a separate NIL check. That should not be too
  onerous as NIL checking is an integral part of any pointer 
  processing algorithm
*)

VAR
   p,q,r:PXList;

BEGIN
  NEW(p);NEW(q);
  p.next:=q;p.key:=1;
  q.next:=NIL;p.key:=2;
  q:=find(p,2);
  r:=find(p,10)
END Test.

Sincerely,

Bostjan Vilfan
***********************************************************************
Bostjan Vilfan                  Voice  : +386-61-176-8391
University of Ljubljana, FER    Fax    : +386-61-126-4630
Trzaska 25                      E-mail : bostjan.vilfan@fer.uni-lj.si
61000 Ljubljana, Slovenia
***********************************************************************