How to print recursive values in Scala?

I have experience implementing the circle notation, but in C.

Firstly, there is more than one approach.

You have to step back and consider: are objects always going to be printed to text using toString? That is to say, are you not planning to have I/O streams, and a way to print objects to a stream rather than converting them to a string?

If you plan to have I/O streams, then you can make them generic enough that a string output stream implementation is possible, and that can be the basis for converting an object to a string.

In implementing the circle notation, it's possible to do things in various ways. The key problem is that you don't want to put a numeric label on everything, whether it is needed or not, because that will look ugly. For instance:

#1=(#2=(a b) #3=(c d) e) ;; no circularity or substructure sharing!

But at the point where your printer finds it most convenient to start emitting an object, it has to know: emit a label, or not?

Another point to consider is that that circle notation is expensive. That's why ANSI Lisp specifies the *print-circle* special variable for enabling it, which is off by default. It's probably a good idea to implement such a switch.

A major complication in circular notation is that if your Lisp dialect has an object system whereby the programmer can create new class types that have custom printing methods, the circle notation has to work even when these custom printing methods are traversed. That's important because in the absence of custom methods, your printer can easily pass an arbitrary context object to itself as it recurses. The object can indicate that circle notation is on (no need to keep checking the dynamic variable, and it can hold a hash table for the labels and whatnot). If the printer calls out to a custom print method, which can call back into the printer, that nice internal context cannot be passed: it's not part of the API.

Anyway, a simple algorithm which works is to first walk the object to be printed and build a hash table of all of its constituent objects that are "circle eligible". For instance, fixnum integers or interned symbols are not; don't add them to the hash. In the hash (which I'm assuming here is a Lisp style hash), you can associate nil with the object when it is first introduced. If a duplicate of the object is seen, the nil flips to t. Of course, any time you find the visited object is already in the hash, you don't recurse on it. That would defeat the whole exercise. Once the hash is built, you refer to it while printing. When about to print a "circle eligible" object, you first look it up in the hash. If the hash has a t, then you replace that t with the value of the label counter, emit the text #<counter>= where <counter> is the label counter value, and then print the object. The counter is incremented. If the hash associates the object with an integer, then it means you have previously printed the #<counter>= notation already for that object. This is just a reference to that object: so just print #<that integer># to represent that object, and you're done.

That's the basic idea. If you ever decide implement a flat list notation with the consing dot, you will need the following logic. For instance, consider the circular list #1=(a b c . #1#). If the printer is oblivious to circularity, it just prints (a b c a b c a b c ... forever, or until hitting a configured list length limit. It's just looping until the cdr iterator hits an atom. In circle mode, the printer, while rendering a flat list, has to watch whether the cdr iterator has a hit in the circular hash. If so, it then has to print the consing dot and the notation, close the paren and terminate the loop. The #= case can occur in this position: (a b c . #1=(d e . #1#)). A positive hash hit is essentially treated as if it were a terminating atom.

Firstly, this is a binary tree not a list, since both parameters to Cons can be Cons:

new Cons(new Cons(Atom("a"), Null), new Cons(Atom("b"),Null))

You can handle self-referential objects using a test:

final class Cons(a: Val, d: => Val) extends Val {
 override def toString =
    if (d == this) {
      "Cons(" + a.toString + ", self)"
    } else {
      "Cons(" + a.toString + "," + d.toString + ")"
    }
}

But mutually-referential objects are still a problem:

lazy val lst1:Val = new Cons(Atom("a"), lst2)
lazy val lst2 = new Cons(Atom("a"), new Cons(Atom("b"), lst1))

For a tree the only sensible way to do this is to mark nodes as you parse them and check that you don't re-visit a node. For a true list you can use the double-pointer technique to detect loops.