Algol68 and GC

[Bakul Shah]

Another question for Algol68 experts in this group:
A long time ago[1] in this newsgroup Piet Von Oostrum said this:
One example: dynamic arrays are easy: Algol 60 had it, see also
the discussion on alloca in this newsgroup. Unions are easy: C
has them. The combination of dynamic arrays and union however
forces you to use the heap, and hence garbage collection.

Not sure I quite understand this. Wouldn't unions or sum types
by themselves require GC?

Second, would any restriction have helped avoid GC? For instance,
what if the mode of a union variable can not be changed once
assigned a particular type value?

[1] https://groups.google.com/g/comp.lang.misc/c/qkmB_3zuC7Y/m/erN_TfDF38IJ

[Charles Lindsey]

I think this raises the same issues as the modals thread.
However, C++ has exactly this same problem, but I don't know how it handles it.

But if your union contains no dynamic arrays, it is easily implemented as an
object whose size is the size of the largest object in the union.

--
Charles H. Lindsey ---------At my New Home, still doing my own thing------
Tel: +44 161 488 1845 Web: https://www.clerew.man.ac.uk
Email: c...@clerew.man.ac.uk Snail-mail: Apt 40, SK8 5BF, U.K.
PGP: 2C15F1A9 Fingerprint: 73 6D C2 51 93 A0 01 E7 65 E8 64 7E 14 A4 AB A5

[Andy Walker]

On 21/12/2021 23:08, Bakul Shah wrote:

> Another question for Algol68 experts in this group:
> A long time ago[1] in this newsgroup

Wow! A thread from more than a third of a century ago that
we both contributed to!

> Piet Von Oostrum said this:
>   One example: dynamic arrays are easy: Algol 60 had it, see also
>   the discussion on alloca in this newsgroup. Unions are easy: C
>   has them. The combination of dynamic arrays and union however
>   forces you to use the heap, and hence garbage collection.

I note Charles's reply, but I don't think it's directly to
do with /dynamic/ arrays, assuming that by that you mean arrays
whose size is not known at compile time. "Simply" allocating space
for the largest possible member of the union is not quite so simple,
in general, ISTM. Consider, eg:

[65536] REAL a; # 2^16, so "only" something like 256K bytes #
[65536] UNION (INT, [] REAL) b;

Now we don't know what size of array will be assigned to any one of
the elements of "b", but it could be "a", so if we allocate the amount
of storage that /could/ be used by any element of "b", then we have to
allow space for 2^16 reals for each, or space for 2^32 reals in total.
That will certainly overflow in a 32-bit computer, even if in reality
only tiny arrays are used in "b". So the choice for the compiler is
to put artificial constraints on the sizes of "a" and "b", or else to
arrange to allocate only the space that is actually used. But that
is not known at compile time, even if, as above, we know the sizes of
all the arrays that occur. So, as a matter of practicality, we have
to use the heap so that elements of "b" can be re-sized as needed.
Or, of course, we could change the union to include a "REF [] INT".

Note that in the comparable case with "STRUCT" types, the
type includes the bounds [eg "MODE STRUCT S = (REAL a, [10] INT b);"]
so the actual sizes are known when objects are declared.

IOW, whereas in C a union is an overlaid structure, in A68
it is simply a name for a collection of types. There are no actual
objects whose type is "UNION ...".

Meanwhile, I note that in your reply to Charles, you say
that you "never had a chance to use A68". Well, now you do! A68G
is freely available, and works "everywhere". As Bart is fond of
pointing out, it's not the fastest kid on the block; but it's
absurdly fast compared with the mainframes of the '70s, so it's
plenty fast enough for everything I need to do.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Nevin

[Bakul Shah]

On 12/22/21 12:16 PM, Andy Walker wrote:
> On 21/12/2021 23:08, Bakul Shah wrote:
>> Another question for Algol68 experts in this group:
>> A long time ago[1] in this newsgroup
>
>     Wow!  A thread from more than a third of a century ago that
> we both contributed to!

Some people never grow up :-)

BTW, I have to thank you & D.F.Brailsford for your introductory
book that opened my eyes about Algol68 in the late '70s! Later
I bought a copy back I still refer to now and then.

>>                        Piet Von Oostrum said this:
>>    One example: dynamic arrays are easy: Algol 60 had it, see also
>>    the discussion on alloca in this newsgroup. Unions are easy: C
>>    has them. The combination of dynamic arrays and union however
>>    forces you to use the heap, and hence garbage collection.
>
>     I note Charles's reply, but I don't think it's directly to
> do with /dynamic/ arrays, assuming that by that you mean arrays
> whose size is not known at compile time.  "Simply" allocating space
> for the largest possible member of the union is not quite so simple,
> in general, ISTM.  Consider, eg:
>
>   [65536] REAL a;  # 2^16, so "only" something like 256K bytes #
>   [65536] UNION (INT, [] REAL) b;
>
> Now we don't know what size of array will be assigned to any one of
> the elements of "b", but it could be "a", so if we allocate the amount
> of storage that /could/ be used by any element of "b", then we have to
> allow space for 2^16 reals for each, or space for 2^32 reals in total.
> That will certainly overflow in a 32-bit computer, even if in reality
> only tiny arrays are used in "b".  So the choice for the compiler is
> to put artificial constraints on the sizes of "a" and "b", or else to
> arrange to allocate only the space that is actually used.  But that
> is not known at compile time, even if, as above, we know the sizes of
> all the arrays that occur.  So, as a matter of practicality, we have
> to use the heap so that elements of "b" can be re-sized as needed.
> Or, of course, we could change the union to include a "REF [] INT".

Thanks! This helps quite a bit!

Actually I don't see how the compiler can do anything but
pretend this is "[65536] UNION (INT, REF [] REAL) b;" as
even at *runtime* it can't know how large any individual
UNION element may be.

>
>     Note that in the comparable case with "STRUCT" types, the
> type includes the bounds [eg "MODE STRUCT S = (REAL a, [10] INT b);"]
> so the actual sizes are known when objects are declared.
>
>     IOW, whereas in C a union is an overlaid structure, in A68
> it is simply a name for a collection of types.  There are no actual
> objects whose type is "UNION ...".
>
>     Meanwhile, I note that in your reply to Charles, you say
> that you "never had a chance to use A68".  Well, now you do!  A68G
> is freely available, and works "everywhere".  As Bart is fond of
> pointing out, it's not the fastest kid on the block;  but it's
> absurdly fast compared with the mainframes of the '70s, so it's
> plenty fast enough for everything I need to do.

I have had it for a while! In fact I tried this just now:

[10] UNION(INT, []REAL) b;

b[1] := 12;
b[2] := []REAL(1.1, 2.2, 3.3);

print((b[1],b[2],newline));
b[2] := 1;
print((b[1],b[2],newline))

Doing such a thing in C++ would cause a memory leak as the
user is entirely responsible for memory management. Still,
I can't help wondering if the compiler can just do malloc/free
behind the scenes rather than a proper GC.

At the moment I don't feel motivated enough to write more than
toy programs in A68. I look at it mainly for inspiration.

[Bart]

This stuff is routine in any dynamic language, where everything is a
union. This is mine in action:

b := new(list, 5)

b[1] := 12
b[2] := (1.1, 2.2, 3.3)
println b

b[2] := 1
println b

Output is this:

(12, (1.100000, 2.200000, 3.300000), <Void>, <Void>, <Void>)
(12, 1, <Void>, <Void>, <Void>)

Here it uses reference counting; the memory used by b[2] is recovered
when something else is assigned to it.

It's harder in a static language, even though all types are known which
is supposed to make things easier. The problem is that here:

b[2] := 1

it doesn't know /at compile time/ what is currently stored in b[2].
(Obviously these simple examples can be be analysed; in general it is
not known.)

[Bakul Shah]

On 12/22/21 2:14 PM, Bart wrote:
> This stuff is routine in any dynamic language, where everything is a
> union. This is mine in action:

My question was really only about Algol68.

[Bart]

That told me ...

[Andy Walker]

On 22/12/2021 21:31, Bakul Shah wrote:

> BTW, I have to thank you & D.F.Brailsford for your introductory
> book that opened my eyes about Algol68 in the late '70s! Later
> I bought a copy back I still refer to now and then.

That's very kind, but sadly it was published at the wrong
time; we wrote it several years before publication, intending it
as a course text for the A68R we were then teaching [and for which
Woodward and Bond was not ideal]. It should have been first to
market, and have made us wealthy beyond the dreams of avarice. Or
something. But the representatives of [well-known major publisher]
went rogue on us, messed us around for over a year, and were caught
at it by W-KMP, who promptly dropped the project. By the time we
were rescued by Ellis Horwood, it was too late. There were already
several texts on the market, the RR had come out, A68R was being
replaced by A68RS, and the following year my department switched
to Pascal [grr!] and then to Basic [grr, tho' better for teaching
than Pascal]. We did our best, but the whole book is a bit of a
compromise, and we couldn't even sell it to our own students.

I can't honestly recommend it, except as nostalgia. But
I quite like the style ...! The amusing thing, to DFB and me, is
the number of people who know us both and say "Oh, I know which
chapters you wrote", and get it entirely wrong. FTAOD, the good
jokes are all mine, the rubbish ones Dave's.

[Charles Lindsey]

On 22/12/2021 21:31, Bakul Shah wrote:

> [10] UNION(INT, []REAL) b;
>
> b[1] := 12;
> b[2] := []REAL(1.1, 2.2, 3.3);
>
> print((b[1],b[2],newline));
> b[2] := 1;
> print((b[1],b[2],newline)

changing that first [10] to [max int} results in:

a68g: exiting: source/genie.c: 5898: object of invalid size