Algol 68 references and the heap

last modified November 13, 2026

A reference is a value that designates storage of some mode. The storage may be a variable declared in a clause or a cell obtained from the heap, and a program reaches it by dereferencing the reference. This article describes the generators that create storage away from the current clause, the difference between a name and a reference variable, the value NIL, and the structures that link one cell to another.

Allocating on the heap

HEAP followed by a mode is a generator: it allocates one cell of that mode and yields a reference to it. NEW does the same in this implementation. The cell has no name of its own, so a program keeps the reference in a variable and dereferences it by writing the variable's name.

BEGIN
  REF INT p = HEAP INT;
  p := 42;
  print((whole(p, 0), newline));
  REF REAL q = NEW REAL := 1.5;
  q := q * 2;
  print((fixed(q, 0, 2), newline))
END

The declaration of p gives a name to the new cell, and the assignment stores 42 in it. The second declaration combines the allocation with an initial value. In both cases the reference is used like the variable it designates: whole(p, 0) reads the integer and q := q * 2 stores a new real into the same cell.

$ a68g heap.a68
42
3.00

Reference variables and retargeting

A reference variable is declared with := and holds a reference that may be replaced by another one. Assigning a new generator to it points the variable at different storage, which is called retargeting.

BEGIN
  REF INT p := HEAP INT := 3;
  print((whole(p, 0), newline));
  p := HEAP INT := 8;
  print((whole(p, 0), newline))
END

The first assignment gives p a cell holding 3, and the second gives it a fresh cell holding 8. The first cell is no longer reachable and is reclaimed by the garbage collector. The mode of p is REF INT, so p := 7 is rejected: the right side would have to be a reference, not an integer.

$ a68g retarget.a68
3
8

Local storage and dangling references

LOC allocates a cell in the current clause instead of the heap. The cell disappears when the clause ends, so a reference to it must not leave the clause; a program that returns one gets a runtime error rather than a reference to reused storage.

PROC make = REF INT: HEAP INT := 7;

BEGIN
  REF INT p = make;
  print((whole(p, 0), newline));
  p := 9;
  print((whole(p, 0), newline))
END

The procedure allocates on the heap, so the cell outlives the call and the caller may read and change it. Replacing HEAP with LOC in the same procedure makes the program fail at run time with REF INT value is exported out of its scope, which is the check for a dangling reference.

$ a68g heapmake.a68
7
9

The value NIL

NIL is the reference that designates nothing. It is useful as the end of a chain of nodes, and a reference that may be NIL is tested with IS NIL or ISNT NIL before it is dereferenced.

MODE NODE = STRUCT(INT value, REF NODE next);
MODE LIST = REF NODE;

BEGIN
  LIST empty = NIL;
  LIST one = HEAP NODE := (1, NIL);
  print((empty IS NIL, " ", one IS NIL, newline))
END

MODE LIST = REF NODE abbreviates the reference mode, which makes the declarations read as list values. The empty list is the nil reference and the one-element list is a node whose next field is also NIL. The two tests print true and false. Dereferencing NIL is a runtime error, so the test has to come first.

$ a68g nil.a68
T F

Nodes that point to nodes

A structure may contain a field of a reference mode, and a node that refers to a node of its own mode builds a list. A procedure that allocates one node and links it to an existing chain is the usual constructor.

MODE NODE = STRUCT(INT value, REF NODE next);
MODE LIST = REF NODE;

PROC cons = (INT value, LIST rest) LIST: HEAP NODE := (value, rest);

BEGIN
  LIST l := cons(1, cons(2, NIL));
  l := cons(0, l);
  print((whole(value OF l, 0), " ", whole(value OF next OF l, 0), newline))
END

cons allocates a node from a value and the rest of the list, and returns the reference to it. The nested calls build the chain 1, 2, and the third call puts a 0 in front of it. l is a reference variable, so the assignment changes which node the name refers to without touching the nodes themselves.

$ a68g prepend.a68
0 1

Traversing a list

A list is read by following the next fields until the chain reaches NIL. Because each node points to a smaller list, the traversal is naturally recursive, and a procedure of mode LIST accepts both a node and NIL.

MODE NODE = STRUCT(INT value, REF NODE next);
MODE LIST = REF NODE;

PROC cons = (INT value, LIST rest) LIST: HEAP NODE := (value, rest);

PROC show = (LIST l) VOID:
  ( l ISNT NIL | print((whole(value OF l, 0), " ")); show(next OF l) );

PROC total = (LIST l) INT:
  IF l IS NIL THEN 0 ELSE value OF l + total(next OF l) FI;

BEGIN
  LIST l = cons(1, cons(2, cons(3, NIL)));
  show(l);
  print((newline));
  print((whole(total(l), 0), newline))
END

show prints the value of a node and calls itself on the rest, using a conditional clause written with a bar instead of IF. It stops when the reference is NIL, because the condition is then false and no branch runs. total adds the values in the same way and returns 0 for the empty list, so the three nodes sum to 6.

$ a68g list.a68
1 2 3
6

Rows on the heap

The generator works for any mode, including a row mode. The reference then designates the whole row, and the elements are reached through the reference.

BEGIN
  REF []INT row = HEAP [1:3] INT;
  FOR i TO 3 DO row[i] := i * i OD;
  FOR i TO 3 DO print((whole(row[i], 0), " ")) OD;
  print((newline))
END

The bounds are part of the generator, so the row is created with three elements and the loops use them directly. A reference to a row is useful when the row has to be returned from a procedure or shared between clauses, since a row value is copied on assignment.

$ a68g heaprow.a68
1 4 9

Reclaiming storage

Algol 68 Genie reclaims heap cells that can no longer be reached, so a program does not free them itself and a reference that is dropped simply becomes garbage. The initial heap size is chosen by the implementation and may be changed with the --heap option, as in a68g --heap=16M program.a68, or with the pragmat PR heap=16M PR at the start of the program.

Next steps

The variables and references article introduces REF, aliases, and the generators, and the structures article explains the field selection used by the nodes above. The unions article shows a node that holds one of several modes, while rows describes the row modes that may also live on the heap.

Source

Revised Report on the Algorithmic Language Algol 68

The Algol 68 Genie project

In this article we have allocated cells with HEAP and NEW, written through a reference, retargeted a reference variable, seen the runtime check for a dangling local reference, used NIL as the end of a chain, built and traversed a linked list with a reference field, allocated a row on the heap, and changed the heap size. The bits article continues with the bit patterns that a program manipulates directly.

Author

My name is Jan Bodnar, and I am a passionate programmer with extensive programming experience. I have been writing programming articles since 2007. To date, I have authored over 1,400 articles and 8 e-books. I possess more than ten years of experience in teaching programming.

List all Algol 68 tutorials.