_    __    ___  
   / \  / /_  ( _ ) 
  / _ \| '_ \ / _ \           Algol 68: identity relations and nil
 / ___ \ (_) | (_) |
/_/   \_\___/ \___/ 
                    



                                                     Jose E. Marchesi
                                                      January 1, 2026


Identity relations are fun when mixed with nil!

Names and references

In Algol 68 references are  not explicitly dereferenced, like in other
languages.   Instead, dereferencing  always happens  automatically, as
required, depending on the syntactic context where the name appears.

Identity relations

An identity relation:

A :=: B


compares two names.  Both  'a' and 'b' are supposed to  be of the same
mode, which has to be a name, i.e. a reference to something.

This is an error:

int i = 10, j = 20;

i :=: j


Because 'i' and 'j' are integral values, not names. 

This works:

int i, j;

i :=: j


But the identity relation always yields 'false'.  Both 'i' and 'j' are
of mode ref int, and the values  ascribed to them (not the values they
refer to) are names generated by the implicit sample generators in the
variable declaration.  The names generated  by a generator will always
be disjoint,  like in most if  not all languages variables  are occupy
disjoint storage,  so the identity  relation will always  yield false.
In the same scenario, 'i :=: i' would always yield 'true'.

Now consider:

int i;
ref int j := i;

i :=: j


In that identity relation we have a ref int at the lhs ('i') and a ref
ref int at the rhs ('j').  Since an identity relation expects names of
the same  mode in both  sides, if it  is to be  valid then one  of the
sides should be suitable to be coerced  to the mode in the other side.
To  determine  what side  gets  coerced,  and how,  balancing  occurs.
Basically, one  of the sides  is chosen to be  in a soft  context, the
other in a  strong context. Then the tertiary at  the strong side gets
coerced to the mode of the tertiary at the soft side

In the example above, it is clear  that 'j', which is of mode 'ref ref
int',  can be  coerced  to 'ref  int',  which  is the  mode  of i,  by
dereferencing, so the lhs is chosen to be the soft context and the rhs
is chosen  to be  the strong context.   Therefore, in  this particular
example, the identity relation yields  the answer to: is 'j' referring
to 'i'?

Note   how   in   Algol   68  there   is   no   explicit   indirecting
operator/construct,  so one  has  to  rely on  coercions  in order  to
dereference.

nil

Now, nil is a name that can refer to values of any mode.  This doesn't
mean nil has  a special mode like 'ref anything'.   What this means is
that particular instances of nil in the program have particular modes,
depending on the  context where they appear.  For example  the mode of
the nils in:

ref int foo = nil;
int bar := nil;


is 'ref int'.  But the mode of the nils in:

ref ref int baz = nil;
ref int quux := nil;


is 'ref  ref int'.  In  other words, nil can  only appear in  a strong
context,  which  are  syntactic  contexts  where  it  is  possible  to
determine the expected mode statically.

This  means that  whenever nil  appears  in an  identity relation,  it
always occupies the  strong position.  Therefore it is  the other side
that determines  the mode, no coercions  are ever done... and  here is
where problems usually start.

Consider the typical list traversing code:

ref Node node := head;

while node :/=: nil
do process_node (node);
   ptr := next of node
od


The mode  of node is  'ref ref Node'.   Since nil always  occupies the
strong position,  we are comparing  a 'ref ref  Node' with a  'ref ref
Node' nil... which always yields  false, because the identity relation
above answers the question: is node itself nil?  It will never be nil,
the identity  relation will always  yield true, our program  is wrong,
and will  result in  a run-time  error or a  segmentation fault  if we
compile without -fcheck=nil.

What we want to  know is whether the value referred  by 'node' is nil.
We can use a cast:

while ref Node (node) :/=: nil
do process_node (node);
   ptr := next of node
od


The cast puts node in a strong  context with goal mode 'ref Node', and
that results in dereferencing it once.   The resulting value is a name
of mode ref Node, which is  used in the identity relation and compared
to a 'ref  Node' nil.  Now this  does answer the question  we want: is
the value referred by 'node' nil?  The code is correct.

So  as it  happens, when  nil  is involved  in practice  it is  always
necessary to  use casts in  identity relations  in order to  "fix" the
mode on the soft side and  determine how much dereferencing happens on
the strong side.

This can be annoying and error prone, and it was early recognized that
the  apparently  symmetric  identity   relation  is  really  not  that
symmetric  as its  syntax suggests.   In  fact, in  an ALGOL  bulletin
(AB40.4.3 R. Haentjens, Proposal for a  Simple Syntax for the ALGOL 68
unit) an alternative  syntax was proposed for  identity relations, due
to this reason.

Fortunately there is  a clever trick, used by  McGettrick, Lindsey and
others, that  makes this problem  go away  and in fact  makes programs
more readable: for every mode you define, define also a "nihil" for it
if you are going to operate with  references to it. Then use the nihil
in identity relations and neve use nil directly.

For example:

mode Node = struct (int payload; ref Node next);
ref Node no_node = nil;

while node :/=: no_node
do process_node (node);
   ptr := next of node
od


The nil stored in  no_node has mode 'ref Node', so  when it appears in
the identity declaration it becomes the soft side and makes 'node' (in
the strong side) to be coerced to 'ref Node'.  In this case, node gets
dereferenced once, which is what we want.

Hope this helps.