🚀 go-pugleaf

In article <1992Nov13.130852.22775@jyu.fi>, sakkinen@jyu.fi (Markku Sakkinen) writes:
> >> But set types have always been sadly crippled in
> >> Wirth's languages:  Pascal implementers are not required to support
> >> even the the full CHAR type as the base type for SET OF CHAR,
> >> not to speak of true SET OF INTEGER.  Fully-fledged set types could often
> >> be useful abstractions in programming.
> >
> >Wirth's aim was always to avoid putting algorithms into the language
> >which could be expressed by the language itself. Having a basic set type,
> >you are able to build up arbitrary set types which work efficiently.
> 
> These extremely restricted set types could well be replaced by
> PACKED ARRAY [ ... ] OF BOOLEAN.  It's the set types with large
> base types that are difficult and tedious for programmers to write
> themselves.  Imagine that arrays were restricted to base types
> of cardinality no greater than 128, and you would have to build up
> larger arrays yourself.

To prove the easiness of large set types in Oberon I've attached my
Sets module which accepts arbitrary ARRAY OF SETs.

> >> I have read somewhere that the parameter modes were variable vs. constant
> >> in an early version of Pascal.  That would have been much better
> >> than the current by-value vs. by-reference distinction (which should be left
> >> as an implementation issue)!
> >
> >The choice between by-value and by-reference as an implementation issue? 
> >Sounds not reasonable -- probably I've missed your point.
> 
> Let me elaborate.  The important conceptual dichotomy in parameters
> is whether the called procedure can modify the actual parameter
> (in the caller's context) or not.  In the former case (variable)
> it is necessary to pass a reference to the actual parameter,
> or do copy in - copy out.  In the latter case (constant), the parameter
> can be passed either by reference or by value,
> without any difference in the semantics.
> 
> Value parameters as in Algol 60, Pascal, Modula-2, etc. bundle
> the choices by not allowing constant parameters to be passed
> by reference.  The gain from this approach is that the programmer
> automatically gets a copy that can be modified without affecting
> the actual parameter.  It was probably quite nice in the Algol 60 days,
> when variables were mostly single integers or reals (and the other
> alternative was the formidable call-by-name).
> 
> The loss is that the copy is done even when
> it is not needed, and with large parameter objects it's a big loss
> (imagine recursive calls with a 1000 x 1000 array parameter).
> It seems to be common practice that programmers declare very
> large parameters as VAR even in cases where they should absolutely
> not be modified -- only to avoid the performance penalty.

Agreed, programmers shouldn't be enforced to use VAR-parameters
for reasons of efficiency only. But, even with the semantics of
Oberon or Modula-2, it's not to difficult for the compiler to
detect that your 1000 x 1000 array isn't modified and, thus,
doesn't need to be copied.

Usually, the calling procedure passes a reference to the array onto
the stack in both cases and the called procedure then makes a copy
of the array if you have call-by-value and your array parameter
is subject to changes.

Your point (hopefully I understand now your point :-) is that this
decision can be eased for the compiler by replacing call-by-value by
passing of readonly parameters. While this is not really necessary
to achieve the efficiency goal, I believe it's a worthy feature because
it would help to make the code more readable.

And now the promised attachment. It's still in early Oberon style,
i.e. separated DEFINITION and MODULE.

#!/bin/sh
# This is a shell archive (produced by shar 3.49)
# To extract the files from this archive, save it to a file, remove
# everything above the "!/bin/sh" line above, and type "sh file_name".
#
# made 11/16/1992 07:42 UTC by borchert@mathematik.uni-ulm.de
# Source directory /export/home/borchert/tmp/48
#
# existing files will NOT be overwritten unless -c is specified
#
# This shar contains:
# length  mode       name
# ------ ---------- ------------------------------------------
#   3205 -r--r--r-- Sets.3
#   1337 -rw-rw-r-- Sets.od
#   4661 -rw-rw-r-- Sets.om
#
# ============= Sets.3 ==============
if test -f 'Sets.3' -a X"$1" != X"-c"; then
	echo 'x - skipping Sets.3 (File already exists)'
else
echo 'x - extracting Sets.3 (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'Sets.3' &&
.\" --------------------------------------
.\" Oberon System Documentation   AFB 8/90
.\" (c) University of Ulm, SAI, D-7900 Ulm
.\" --------------------------------------
.de Pg
.nf
.ie t \{\
.	sp 0.3v
.	ps 9
.	ft CW
.\}
.el .sp 1v
..
.de Pe
.ie t \{\
.	ps
.	ft P
.	sp 0.3v
.\}
.el .sp 1v
.fi
..
.TH Sets 3 "Oberon System"
.SH NAME
Sets \- operations for sets of arbitrary length
.SH SYNOPSIS
.Pg
CONST setsize = MAX(SET) + 1;
.sp 0.7
TYPE CharSet = ARRAY ORD(MAX(CHAR)) DIV setsize OF SET;
.sp 0.7
VAR lengthError: Events.EventType;
.sp 0.7
PROCEDURE InitSet(VAR set: ARRAY OF SET);
.sp 0.3
PROCEDURE Complement(VAR set: ARRAY OF SET);
.sp 0.3
PROCEDURE Union(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
PROCEDURE Difference(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
PROCEDURE Intersection(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
PROCEDURE SymDifference(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
.sp 0.3
PROCEDURE In(VAR set: ARRAY OF SET; i: LONGINT) : BOOLEAN;
PROCEDURE CharIn(VAR charset: CharSet; ch: CHAR) : BOOLEAN;
PROCEDURE Equal(set1, set2: ARRAY OF SET) : BOOLEAN;
.sp 0.3
PROCEDURE Incl(VAR set: ARRAY OF SET; i: LONGINT);
PROCEDURE Excl(VAR set: ARRAY OF SET; i: LONGINT);
PROCEDURE InclChar(VAR charset: CharSet; ch: CHAR);
PROCEDURE ExclChar(VAR charset: CharSet; ch: CHAR);
.sp 0.3
PROCEDURE Subset(set1, set2: ARRAY OF SET) : BOOLEAN;
PROCEDURE Card(set: ARRAY OF SET) : INTEGER;
.Pe
.SH DESCRIPTION
.I Sets
implements set operations for character sets and
sets of arbitrary length.
.I setsize
defines the number of bits per
.B SET
type.
.I CharSet
is an array of
.B SET
sufficient for characters.
.I InitSet
initializes
.I set
to the empty set.
.PP
Following set operators are implemented:
.sp
.TS
l l.
set operator	set operation
_
unary \fB-\fP	\fIComplement\fP
\fB+\fP	\fIUnion\fP
\fB-\fP	\fIDifference\fP
\fB*\fP	\fIIntersection\fP
\fB/\fP	\fISymDifference\fP
\fBIN\fP	\fIIn\fP and \fICharIn\fP
\fB=\fP	\fIEqual\fP
\fBINCL\fP	\fIIncl\fP and \fIInclChar\fP
\fBEXCL\fP	\fIExcl\fP and \fIExclChar\fP
.TE
.PP
\fISubset\fP returns \fBTRUE\fP iff
\fIset1\fP is contained in \fIset2\fP.
\fICard\fP returns the cardinality
(number of elements) of \fIset\fP.
.SH DIAGNOSTICS
\fISets\fP
raises \fIlengthError\fP with priority \fIPriorities.assertions\fP
if the length of \fIresult\fP is less than
the length of \fIset1\fP or \fIset2\fP.
.SH "SEE ALSO"
.TS
lfI l.
Assertions(3)	error handling for length errors
.TE
.\" ---------------------------------------------------------------------------
.\" $Id: Sets.3,v 1.5 91/11/25 09:15:53 borchert Exp $
.\" ---------------------------------------------------------------------------
.\" $Log:	Sets.3,v $
.\" Revision 1.5  91/11/25  09:15:53  borchert
.\" lengthError is now handled by Assertions
.\" 
.\" Revision 1.4  1991/11/12  08:43:40  borchert
.\" Events.EventNumber replaced by Events.EventType
.\"
.\" Revision 1.3  1991/06/21  15:32:34  borchert
.\" minor fix
.\"
.\" Revision 1.2  91/06/18  13:57:08  borchert
.\" new operators added
.\" 
.\" Revision 1.1  90/08/31  17:02:19  borchert
.\" Initial revision
.\" 
.\" ---------------------------------------------------------------------------
SHAR_EOF
chmod 0444 Sets.3 ||
echo 'restore of Sets.3 failed'
Wc_c="`wc -c < 'Sets.3'`"
test 3205 -eq "$Wc_c" ||
	echo 'Sets.3: original size 3205, current size' "$Wc_c"
fi
# ============= Sets.od ==============
if test -f 'Sets.od' -a X"$1" != X"-c"; then
	echo 'x - skipping Sets.od (File already exists)'
else
echo 'x - extracting Sets.od (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'Sets.od' &&
(* Oberon Library      -  UNIX System V  -      AFB 9/89 *)
(* (c) University of Ulm, Sektion Informatik, D-7900 Ulm *)
X
DEFINITION Sets;
X
X   IMPORT Events;
X
X   CONST
X      setsize = MAX(SET) + 1;
X
X   TYPE
X      CharSet = ARRAY ORD(MAX(CHAR)) DIV setsize OF SET;
X
X   VAR
X      lengthError: Events.EventType;
X	 (* raised with Priorites.assertions if the length of
X	    the result is less than its parameters
X	 *)
X
X   PROCEDURE InitSet(VAR set: ARRAY OF SET);
X
X   PROCEDURE Complement(VAR set: ARRAY OF SET);
X
X   PROCEDURE In(VAR set: ARRAY OF SET; i: LONGINT) : BOOLEAN;
X
X   PROCEDURE Incl(VAR set: ARRAY OF SET; i: LONGINT);
X   PROCEDURE Excl(VAR set: ARRAY OF SET; i: LONGINT);
X
X   PROCEDURE CharIn(VAR charset: CharSet; ch: CHAR) : BOOLEAN;
X
X   PROCEDURE InclChar(VAR charset: CharSet; ch: CHAR);
X   PROCEDURE ExclChar(VAR charset: CharSet; ch: CHAR);
X
X   PROCEDURE Intersection(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
X   PROCEDURE SymDifference(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
X   PROCEDURE Union(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
X   PROCEDURE Difference(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
X
X   PROCEDURE Equal(set1, set2: ARRAY OF SET) : BOOLEAN;
X   PROCEDURE Subset(set1, set2: ARRAY OF SET) : BOOLEAN;
X
X   PROCEDURE Card(set: ARRAY OF SET) : INTEGER;
X
END Sets.
SHAR_EOF
chmod 0664 Sets.od ||
echo 'restore of Sets.od failed'
Wc_c="`wc -c < 'Sets.od'`"
test 1337 -eq "$Wc_c" ||
	echo 'Sets.od: original size 1337, current size' "$Wc_c"
fi
# ============= Sets.om ==============
if test -f 'Sets.om' -a X"$1" != X"-c"; then
	echo 'x - skipping Sets.om (File already exists)'
else
echo 'x - extracting Sets.om (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'Sets.om' &&
(* Oberon Library      -  UNIX System V  -      AFB 9/89 *)
(* (c) University of Ulm, Sektion Informatik, D-7900 Ulm *)
X
MODULE Sets;
X
X   IMPORT Assertions, Events, Priorities;
X
X   CONST
X      setsize = MAX(SET) + 1;
X
X   TYPE
X      CharSet = ARRAY ORD(MAX(CHAR)) DIV setsize OF SET;
X
X   VAR
X      lengthError: Events.EventType;
X	 (* raised with Priorites.assertions if the length of
X	    the result is less than its parameters
X	 *)
X
X   PROCEDURE LengthError(procname: ARRAY OF CHAR);
X   BEGIN
X      Assertions.Raise(NIL, lengthError, procname, "set lengths are different");
X   END LengthError;
X
X   PROCEDURE InitSet(VAR set: ARRAY OF SET);
X      VAR i: LONGINT;
X   BEGIN
X      i := 0;
X      WHILE i < LEN(set) DO
X	 set[i] := {}; INC(i);
X      END;
X   END InitSet;
X
X   PROCEDURE Complement(VAR set: ARRAY OF SET);
X      VAR i: LONGINT;
X   BEGIN
X      i := 0;
X      WHILE i < LEN(set) DO
X	 set[i] := - set[i]; INC(i);
X      END;
X   END Complement;
X
X   PROCEDURE In(VAR set: ARRAY OF SET; i: LONGINT) : BOOLEAN;
X   BEGIN
X      RETURN (i MOD setsize) IN set[i DIV setsize]
X   END In;
X
X   PROCEDURE Incl(VAR set: ARRAY OF SET; i: LONGINT);
X   BEGIN
X      INCL(set[i DIV setsize], i MOD setsize);
X   END Incl;
X
X   PROCEDURE Excl(VAR set: ARRAY OF SET; i: LONGINT);
X   BEGIN
X      EXCL(set[i DIV setsize], i MOD setsize);
X   END Excl;
X
X   PROCEDURE CharIn(VAR charset: CharSet; ch: CHAR) : BOOLEAN;
X   BEGIN
X      RETURN (ORD(ch) MOD setsize) IN charset[ORD(ch) DIV setsize]
X   END CharIn;
X
X   PROCEDURE InclChar(VAR charset: CharSet; ch: CHAR);
X   BEGIN
X      INCL(charset[ORD(ch) DIV setsize], ORD(ch) MOD setsize);
X   END InclChar;
X
X   PROCEDURE ExclChar(VAR charset: CharSet; ch: CHAR);
X   BEGIN
X      EXCL(charset[ORD(ch) DIV setsize], ORD(ch) MOD setsize);
X   END ExclChar;
X
X   PROCEDURE Intersection(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
X      VAR
X	 index: INTEGER;
X   BEGIN
X      IF (LEN(result) # LEN(set1)) OR (LEN(result) # LEN(set2)) THEN
X	 LengthError("Intersection"); InitSet(result); RETURN
X      END;
X      index := 0;
X      WHILE index < LEN(result) DO
X	 result[index] := set1[index] * set2[index];
X	 INC(index);
X      END;
X   END Intersection;
X
X   PROCEDURE SymDifference(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
X      VAR
X	 index: INTEGER;
X   BEGIN
X      IF (LEN(result) # LEN(set1)) OR (LEN(result) # LEN(set2)) THEN
X	 LengthError("SymDifference"); InitSet(result); RETURN
X      END;
X      index := 0;
X      WHILE index < LEN(result) DO
X	 result[index] := set1[index] / set2[index];
X	 INC(index);
X      END;
X   END SymDifference;
X
X   PROCEDURE Union(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
X      VAR
X	 index: INTEGER;
X   BEGIN
X      IF (LEN(result) # LEN(set1)) OR (LEN(result) # LEN(set2)) THEN
X	 LengthError("Union"); InitSet(result); RETURN
X      END;
X      index := 0;
X      WHILE index < LEN(result) DO
X	 result[index] := set1[index] + set2[index];
X	 INC(index);
X      END;
X   END Union;
X
X   PROCEDURE Difference(set1, set2: ARRAY OF SET; VAR result: ARRAY OF SET);
X      VAR
X	 index: INTEGER;
X   BEGIN
X      IF (LEN(result) # LEN(set1)) OR (LEN(result) # LEN(set2)) THEN
X	 LengthError("Difference"); InitSet(result); RETURN
X      END;
X      index := 0;
X      WHILE index < LEN(result) DO
X	 result[index] := set1[index] - set2[index];
X	 INC(index);
X      END;
X   END Difference;
X
X   PROCEDURE Equal(set1, set2: ARRAY OF SET) : BOOLEAN;
X      VAR
X	 index: INTEGER;
X   BEGIN
X      index := 0;
X      WHILE (index < LEN(set1)) & (index < LEN(set2)) DO
X	 IF set1[index] # set2[index] THEN
X	    RETURN FALSE
X	 END;
X	 INC(index);
X      END;
X      WHILE index < LEN(set1) DO
X	 IF set1[index] # {} THEN
X	    RETURN FALSE
X	 END;
X	 INC(index);
X      END;
X      WHILE index < LEN(set2) DO
X	 IF set2[index] # {} THEN
X	    RETURN FALSE
X	 END;
X	 INC(index);
X      END;
X      RETURN TRUE
X   END Equal;
X
X   PROCEDURE Subset(set1, set2: ARRAY OF SET) : BOOLEAN;
X      VAR
X	 index: INTEGER;
X   BEGIN
X      index := 0;
X      WHILE (index < LEN(set1)) & (index < LEN(set2)) DO
X	 IF set1[index] - set2[index] # {} THEN
X	    RETURN FALSE
X	 END;
X	 INC(index);
X      END;
X      WHILE index < LEN(set1) DO
X	 IF set1[index] # {} THEN
X	    RETURN FALSE
X	 END;
X	 INC(index);
X      END;
X      RETURN TRUE
X   END Subset;
X
X   PROCEDURE Card(set: ARRAY OF SET) : INTEGER;
X      VAR
X	 index: INTEGER;
X	 i: INTEGER;
X	 card: INTEGER;
X   BEGIN
X      card := 0;
X      index := 0;
X      WHILE index < LEN(set) DO
X	 i := 0;
X	 WHILE i <= MAX(SET) DO
X	    IF i IN set[index] THEN
X	       INC(card);
X	    END;
X	    INC(i);
X	 END;
X	 INC(index);
X      END;
X      RETURN card
X   END Card;
X
BEGIN
X   Assertions.Define(lengthError, "Sets");
END Sets.
SHAR_EOF
chmod 0664 Sets.om ||
echo 'restore of Sets.om failed'
Wc_c="`wc -c < 'Sets.om'`"
test 4661 -eq "$Wc_c" ||
	echo 'Sets.om: original size 4661, current size' "$Wc_c"
fi
exit 0
-- 
_______________________________________________________________________________

Andreas Borchert, University of Ulm, SAI, D-W-7900 Ulm, Germany
Internet: borchert@mathematik.uni-ulm.de