Lazy evaluation is one way programming languages achieve infinitely self-contained immutable lists.

One way of thinking about lazy evaluation is that expressions are put in stasis until they absolutely need to be evaluated. The expression can be referred to as if it were fully evaluated, but in reality evaluation is deferred. This is in contrast to eager evaluation where the entire expression is fully evaluated when it is encountered.

Many languages, especially those focused on functional programming, contain lazy evaluation. Languages with lazy evaluation include Haskell, OCaml, and Scala.

Take for example Scala:

lazy val x: LazyList[Any] = x #:: LazyList.empty

(Note that in Scala, the LazyList class is immutable)

This creates a lazily evaluated LazyList which has itself as the head of the List, which of course is the entire list. Basically, it's saying "the LazyList is a list of itself, which is a list of itself, which is a list of itself, which is...".

The lazy before the val ensures that the evaluation of the list is deferred until later. Printing the list, depending on implementation, should print something akin to:

LazyList(<not computed>)

(Try it online at scastie)

Notably, the type annotation LazyList[Any] is required in this case. As the list is recursive, inference of the type of the list's contents isn't possible - the type can't be easily calculated automatically. This isn't always a necessity though...the compiler will tell you if it can't figure things out.

In summary, lazy evaluation is a common way of achieving the kind of self recursive list you desire while maintaining immutability. It is far from the only use case of lazy evaluation, but it gets the job done by allowing safe compile time self-referential expressions.

Many languages support referring to identifiers before they are fully defined.

Example in C++:

struct recursive_type {
    recursive_type *x;
    int y;
    recursive_type(recursive_type *_x, int _y) : x(_x), y(_y) {}
} a(&a, 1);

// Or mutual recursive references:
extern recursive_type b;
recursive_type c(&b, 2), b(&c, 3);

PHP:

<?php
$a = [ &$a, 1 ];

$b = [ &$c, 2 ];
$c = [ &$b, 3 ];

var_dump result (for some reasons it has one extra level displayed on tio):

array(2) {
  [0]=>
  *RECURSION*
  [1]=>
  int(1)
}
array(2) {
  [0]=>
  &array(2) {
    [0]=>
    *RECURSION*
    [1]=>
    int(3)
  }
  [1]=>
  int(2)
}
array(2) {
  [0]=>
  &array(2) {
    [0]=>
    *RECURSION*
    [1]=>
    int(2)
  }
  [1]=>
  int(3)
}

Combinatorial Game Suite is an interesting example, that it is not referring to variables, but internal markers on the definition of games, a kind of mathematical object that this language is mostly concerned about.

It has the keyword pass to refer to the innermost level of the game surrounding the keyword, But you could also label it explicitly:

a{a|}               // equivalent to {pass|} = on
a{{a|}|}            // simplifies to {pass|} = on
a{0|{0|{{a|*}|*}}}  // a game that doesn't simplify, from the example in the
                    // help file, but rewritten to make its structure clearer

It works even if a was previously defined, and it would not use the previously defined value. (But note that v, vv, vvv, etc, are not valid variable or label names in CGSuite.)

Let's consider a realistic example: how could you implement a binary tree where nodes have properties left, right and parent in an immutable data structure?

One solution is to actually implement an immutable directed graph with labeled edges. An immutable directed graph with labeled edges could be implemented as an immutable map where keys are nodes and values are immutable maps from string to maybe-node.

If we want to build the binary tree

              X1
             /  \
           X2    X3

We first create objects X1, X2, X3, then create the immutable map:

b = {
  X1 -> {"parent"->null, "left"->X2, "right"->X3},
  X2 -> {"parent"->X1, "left"->null, "right"->null},
  X3 -> {"parent"->X1, "left"->null, "right"->null}
}

Plainly that immutable map can be built up from smaller immutable maps. (And one of those maps we can reuse, and gain some advantages of a persistent data structure.)

And now b[X2]["parent"] is X1. The downside here is that to say the moral equivalent of X1.left.parent we need to say b[b[X1]["left"]]["parent"] which is rather gross. One mitigation for that is to take a cue from languages such as JavaScript or Python and make .s a sugar for ["s"]. That reduces the expression to b[b[X1].left].parent. There are other sugars you might create to make that a little easier on the eyes.

I see two basic ways here

Allow (immutable) initialization of objects independent on order of definition

If one wants data structures with references or cycles one simply could spell out the cycles/references explicitly and assign the intermediate objects a name. This is the way all programmers are used to. The ordinary inline expression syntax only allows for tree-like data structures. I would not change that.

In go-like syntax this could look like (this is just a syntax example)

type A struct {
    Bref *B
}

type B struct {
    Aref *A
}

const Aobj = A{Bref: &Bobj}
const Bobj = B{Aref: &Aobj}

Note: There is no fundamental reason why the above could not work. Currently in go this fails, because go allows arbitrary code expressions in initialization and tries to figure out the initialization order. However for the plain system-defined constructor A{...} or B{...} the order of initialization does not matter and it would, in this special case, be ok to accept this program as legal go.

But you were only asking for the syntax how this could look like. And this is one example.

Also one could envision to define local constants this way, too. Key is to give up the ordering of the definitions.

Two stage initialization/construction

This is not directly related on how to literally specify cyclic data structures, but I think it is important nontheless and completemts the other above.

Clearly, one can construct non-tree datastructures with deeply immutable types when one allows the objects to be mutable in the construction phase.

Or in other words have a two stage construction.

First create the object with all fields initialized with default values and then secondly fill in the correct values (perhaps this is even user-code).

Just after these two phases the object would become immutable. Of course this has the complication that the constructor code has to take care that dependent objects may be not fully constructed yet.

In C++ it is already almost like this. Upon entry of the constructor the 'this' pointer points to an allocated object. In the body of the constructor some recursive algorithm could run, which then uses the 'this' pointer to create cyclic references even though the object is not fully constructed yet.

Key enabler here would be to allow the constructor (and only the constructor) to modify the fields even for immutable types.

Similar thing exists in Python with frozen dataclasses. Since frozen dataclasses are not really a first-class immutable type and just emulate immutability one can in the constructor indeed set the fields. But that just highlights the general problem on how to extend or subclass immutable types.

Remark

BTW your question is missing an important detail. You do not specify what kind of "immutability" you refer to.

Is it "shallow immutability" or "deep immutability" [1]?

Python: tuple itself can contain mutable objects and these objects can be mutated -- they just cannot be replaced in the tuple.

The shallow immutability already solves the covariance / contravariance problems of container types. But the deep immutability is needed for the thread safety. This needs to be taken into account in your design.

In OCaml, bindings shadow each other by default, but an initializer has access to the previous declarations with the same name:

let a = 40
let a = a + 2             (* a = 42 *)

However, you can use the rec keyword to allow a binding's initializer to refer to the binding's name itself.

let a = 40                (* This declaration is basically useless *)
let rec a = 1 :: 2 :: a   (* Here, "a" refers to its own declaration *)

The following code effectively defines a single binding "a" that contains a cyclic list. Note that OCaml is not lazily evaluated. This cyclic initialization is possible because most values in OCaml — including (linked) list nodes — are boxed (heap-allocated), so it's possible for the runtime to know the address of a value before it's actually initialized. The language specifically prohibits using a let rec declaration if the right-hand-side expression could potentially try to read the binding before the value is fully constructed.

Instead of focusing on the syntax of literal expressions for cyclic object graphs (and possibly restricting the facility only for this case), consider a more general approach.

You are already considering having most types with mutable and immutable versions, with different underlying memory layouts. Probably there will be some form of automatic conversion between these types. This alone allows for first constructing the mutable version, and "freezing" the object, say assigning a mut var into a non mut var.

This is nice and suffice for small objects, and overlaps with the case of literal expressions, that tends to be on the small size. But this fails for constructing big objects, objects with very complicated building processes (an async step, for example), and also annoys the programmer with the notion of building "many" dynamic objects only to throw them away after using them for constructing the immutable image.

Keyword here, "constructing". The modern notion of a constructor includes the "all or nothing" effect. Or the object is fully functional after the construction ends, with all the static invariants validated, or the object never comes to be. No intermediary state is visible.

But inside the constructor the object is allowed to be in a invalid state. Say, property a is assigned first, while construction of object for property b is not even started, and can still fail.

Enriching your language with an tmpmut version of immutable types, that have the same nominal fields but have all invariant restrictions lifted, allows for accumulating state for a immutable object, in immutable memory layout, that latter gets "converted" and validated into the typed immutable version.

Use example:

def foo( List mut ) { ... }
def bar( list imm ) { ... }
def fillwith( List tmpmut , source ) { ... }

var li mut = new List( string );   # This is mutable list
foo( l1 );                         # Mutate away

# We want to build a custom immutable list,
# but a partially constructed immutable object cannot
# be accepted where a proper immutable object is expected.

var l2 tmpmut = new List( 10 );  # Note the `tmpmut`
foo( l2 );                       # Fails

fillwith( l2 , source );  # Ok
var l3 List imm = l2;     # Calls tmpmut -> imm operation
bar( l3 );                # Ok

Definitions example:

# Dynamic lists are heap allocated reference objects,
# so its hashcode does not depend on contents.

def List type mut

    var HashCode u32;

    def constructor()
        this.HashCode = System.HashCode.GetOne();

# Immutable lists have a different memory layout,
# and obviously different methods. Immutable lists
# has an automatically generated hashcode that depends
# on lists contents *after* it is completed.

def List type imm

    var ... ;
    var HashCode u32 = lang.auto.HashCode32;

# Temporary immutable Lists have the same memory
# memory layout of immutable counterpart, and a
# different set of methods of mutable and immutable
# versions. In particular, the conversion operation
# from `tmpmut` into `imm`.

def List type tmpmut 

    def _ explicit ( source List tmpmut ) List imm
    {
        # Running dynamic checks

        if source.X then ...

        # Return an `tmpmut` where an `imm` is specified.
        # Here the compiler checks the static invariants of
        # `imm` type, before returning.

        return source;
    }