Generators, References & Linked Data Structures

A generator creates a new name (storage cell):

33.1 LOC and HEAP generators

A generator creates a new name (storage cell):

LOC INT — a local cell on the stack, deallocated when the enclosing range is left.

HEAP INT — a cell on the garbage-collected heap, alive as long as it is reachable.

REF INT a = LOC INT := 1;      # same as INT a := 1 #
REF INT b = HEAP INT := 2;     # lives beyond the current block #
INT c := 3;                    # declarations default to LOC #
HEAP INT d := 4;               # a heap variable declared with the short form #

33.2 Scope rules

A reference must not be stored somewhere that outlives what it refers to:

Use HEAP for anything that must outlive its block. a68g checks scopes and reports violations.

REF INT global := NIL;
BEGIN
   INT local := 5;
   global := local          # SCOPE VIOLATION: local dies at END #
END;

33.3 A linked-list stack

HEAP NODE := (v, top) creates a heap node, initializes it with a structure display, and yields its reference.

top is a variable of mode REF REF NODE; REF NODE (top) dereferences once to get the node reference.

Pitfall: writing top IS NIL would compare the *variable* top itself (a REF REF NODE) with NIL — always false. Cast first: REF NODE (top) IS NIL.

stop is a standard label that ends the program.

BEGIN
   MODE NODE = STRUCT (INT value, REF NODE next);
   REF NODE top := NIL;

   PROC push = (INT v) VOID: top := HEAP NODE := (v, top);
   PROC is empty = BOOL: REF NODE (top) IS NIL;
   PROC pop = INT:
      IF is empty THEN print(("stack underflow", newline)); stop
      ELSE INT v = value OF top; top := next OF top; v
      FI;

   FOR i TO 5 DO push(i * i) OD;
   WHILE NOT is empty DO print((whole(pop, 0), " ")) OD;
   print(newline)
END

33.4 Traversing a list

REF NODE p := top;
WHILE REF NODE (p) ISNT NIL DO
   print(value OF p);
   p := next OF p
OD

33.5 Binary search tree

left OF t has mode REF REF TREE (a reference to the field), so insert can update the field in place — no special "pointer to pointer" syntax needed.

BEGIN
   MODE TREE = STRUCT (INT key, REF TREE left, right);

   PROC insert = (REF REF TREE t, INT k) VOID:
      IF REF TREE (t) IS NIL THEN t := HEAP TREE := (k, NIL, NIL)
      ELIF k < key OF t THEN insert(left OF t, k)
      ELSE insert(right OF t, k)
      FI;

   PROC inorder = (REF TREE t) VOID:
      IF t ISNT NIL THEN
         inorder(left OF t);
         print((whole(key OF t, 0), " "));
         inorder(right OF t)
      FI;

   PROC contains = (REF TREE t, INT k) BOOL:
      IF t IS NIL THEN FALSE
      ELIF k = key OF t THEN TRUE
      ELIF k < key OF t THEN contains(left OF t, k)
      ELSE contains(right OF t, k)
      FI;

   REF TREE root := NIL;
   []INT keys = (50, 30, 70, 20, 40, 60, 80, 35);
   FOR i FROM LWB keys TO UPB keys DO insert(root, keys[i]) OD;
   inorder(root); print(newline);
   print(("contains 60: ", contains(root, 60), newline));
   print(("contains 65: ", contains(root, 65), newline))
END

33.6 Garbage collection

a68g's heap is garbage collected: unreachable HEAP objects are reclaimed automatically. Heap size can be set on the command line (see a68g --help). ALGOL 68 was one of the first widely specified languages to *require* a garbage-collected heap.