Strange, strange loops!

I’ve just finsihed reading Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter.
The works of Gödel, Church, Turing, Cantor and others are presented in this beautiful book, which is extraordinarily witty and amusing with its dialogues in the style of Lewis Caroll’s What the Tortoise Said to Achilles and Escher paintings for illustrations.
This book is focused on self-reference and the emergence of self-awareness in complex systems. Self-references often have interesting implications, be it Gödel’s theorem or Turing’s proof that no program can solve the Halting Problem.

This article shows some examples of self-reference, using the LISP and Haskell programming languages.

In LISP languages, the cons cell is an essential data structure, composed of two parts. It is created with the CONS function, which takes two arguments. To create a list, one merely links cons cells together by having a pointer to data in the first part of a cell (the CAR), and a pointer to the next cons cell in the second part (the CDR).

Let’s create a cons cell, its first part pointing to a number and the second part set to NIL. We’ll call it “self”:

[1]> (setf self (cons 1 NIL))
(1)
[2]> (car self)
1
[3]> (cdr self)
NIL

We can now make (CDR self) point to… self:

[4]> (car (setf (cdr self) self))
1
[5]> (car (cdr (cdr (cdr (cdr (cdr self))))))
1

Line [4] reads as: point the second part of self to self, and return the first part of this whole construction.
Line [5] is: give me “the first part of the (second part of * 5) self”.
Self is the list made of the number “1”, followed by itself! Obviously, we can’t print it anymore:

[6]> self
(1 1 1 1 1 1 1 1..... (endless list)

This recursive construction is a problem in the construction of simple reference-counting garbage collectors:

One day a student came to Moon and said: “I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons.” Moon patiently told the student the following story: “One day a student came to Moon and said: ‘I understand how to make a better garbage collector… #

Which came first: the chicken, or the egg?
This profound philosophical question can be approached with laziness and self-reference: The chicken came from an egg, which could come from the same chicken.

In Haskell:

module GEB where

data Chicken = Chicken 	{ comingFrom :: Egg}	deriving Show
data Egg = Egg 		{ laidBy :: Chicken}	deriving Show

myChicken = Chicken myEgg
myEgg = Egg myChicken

This code creates two types, Chicken and Egg. To create a Chicken instance, one has to call “Chicken” with an Egg as the parameter. To create an Egg instance, one has to call “Egg” and give as a parameter a Chicken object, which will be the parent.

Two variables are then declared:

• the Chicken “myChicken”, with comingFrom = myEgg
• the Egg “myEgg”, where laidBy = myChicken

This code compiles and runs fine:

*GEB> :type myChicken 
myChicken :: Chicken
*GEB> :type myEgg 
myEgg :: Egg

Try doing that with C++ references!
With Haskell’s lazy evaluation, the variables won’t actually be computed until there is an explicit need to use their value. Sadly, it means that printing these objects creates an endless loop of self-creation:

*GEB> myChicken 
Chicken {comingFrom = Egg {laidBy = Chicken {
    comingFrom = Egg {laidBy = Chicken {
    comingFrom = ... this goes on and on forever.

Well, things often break. In human languages, this leads to paradoxes such as “this sentence is false”, in Mathematics to Gödel’s incompleteness theorems, in programming languages to infinite loops or memory leaks…

But most often self-reference and infinite loops are a source of wonder and beauty! They are at the center of the extraordinary paintings of M.C. Escher and René Magritte, at the core of computation in lambda calculus with Y = λf·(λx·f (x x)) (λx·f (x x)), and even in quantum mechanics where they bring fascinating infinities.

And in our human brains… at the root of consciousness?