• Algol68 and GC

    From Bakul Shah@21:1/5 to All on Tue Dec 21 15:08:40 2021
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Charles Lindsey@21:1/5 to Bakul Shah on Wed Dec 22 15:25:14 2021
    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 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

    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: chl@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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Andy Walker@21:1/5 to Bakul Shah on Wed Dec 22 20:16:19 2021
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bakul Shah@21:1/5 to Andy Walker on Wed Dec 22 13:31:52 2021
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bart@21:1/5 to Bakul Shah on Wed Dec 22 22:14:49 2021
    On 22/12/2021 21:31, Bakul Shah wrote:
    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.

    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.)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bakul Shah@21:1/5 to Bart on Wed Dec 22 14:32:07 2021
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Andy Walker@21:1/5 to Bakul Shah on Wed Dec 22 23:49:57 2021
    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.

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bart@21:1/5 to Bakul Shah on Wed Dec 22 23:38:24 2021
    On 22/12/2021 22:32, Bakul Shah wrote:
    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.

    That told me ...

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Charles Lindsey@21:1/5 to Bakul Shah on Thu Dec 23 12:24:23 2021
    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

    --
    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: chl@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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)