<p>Suppose a language has a rust-style trait system but is garbage collected and most types are reference types by default.</p>
<p>I could create a trait like this:</p>
<pre class="lang-rs prettyprint-override"><code>trait ToString {
    fn to_string(self) -&gt; String;
}
</code></pre>
<p>Typical implementation would be something like:</p>
<pre class="lang-rs prettyprint-override"><code>impl ToString for List&lt;T: ToString&gt; {
    fn to_string(self) -&gt; String { &quot;[&quot; + self.map(|i: T|i.to_string()).join(',') + &quot;]&quot; }
}
</code></pre>
<p>But if I then do:</p>
<pre class="lang-rs prettyprint-override"><code>let mut a = []; // [] creates a mutable vector, there are no arrays
a.push(a); // Type of a is decided based on what is added to it
print!(a);
</code></pre>
<p>It will create an infinite loop printing the list forever.</p>
<p>In Python, if you do this you'll get:</p>
<pre class="lang-py prettyprint-override"><code>a = []
a.append(a)
print(a)
# [[...]]
</code></pre>
<p>It will detect the cycle and print <code>[...]</code> instead of the full list if the list was already in the process of being printed.</p>
<p>How can I modify my <code>ToString</code> interface to allow types to detect if they are already being printed and prevent an infinite loop for recursive data structures. Ideally it would work for arbitrary data structures and not just lists, while also keeping it ergonomic to implement the interface.</p>

<strings>
Creating an interface for stringifying objects that allows loop detection
CC BY-SA 4.0
2023-09-01T13:43:27.763Z
You might also want to check out how Racket does it with [`mpair`s](https://docs.racket-lang.org/reference/mpairs.html). It displays more info about the structure of the cycle(s). For example, if you have `(define a (mlist 1 2 3 4)) (set-mcar! (mcdr (mcdr a)) (mcdr a)) (set-mcdr! (mcdr (mcdr a)) a)` then when you print `a` you get `#0=(mcons 1 #1=(mcons 2 (mcons #1# #0#)))`
David Young
CC BY-SA 4.0
2023-09-01T19:10:38.277Z
@DavidYoung FYI, Racket adopted that from Common Lisp.
Barmar
CC BY-SA 4.0
2023-09-03T12:17:01.293Z
If your language is statically typed, how does `a.push(a)` even work? What is the inferred type?
xigoi
CC BY-SA 4.0
2023-09-03T12:39:04.607Z
A list of lists of list of lists... @xigoi
mousetail 'he-him'
CC BY-SA 4.0
2023-09-03T18:55:17.250Z
@mousetail In that case, couldn't you just detect at compile time that the type is self-referential and use a stringifying function that doesn't descend?
xigoi
CC BY-SA 4.0
2023-09-03T20:39:58.273Z
Yes, but the trick is making that work for arbitrary, user-defined types @xigoi
mousetail 'he-him'
<p>I don't think this requires changing your <code>ToString</code> interface itself, rather you can change the protocol by which the language invokes the <code>to_string</code> method. That is, don't just unconditionally call <code>.to_string()</code> when a string conversion is needed.</p>
<p>Here's a simple solution which could work either for a single-threaded language, or for a language like Java which allows synchronising (i.e. <a href="https://en.wikipedia.org/wiki/Reentrant_mutex" rel="nofollow noreferrer">reentrant locking</a>) on an object. Since your language is garbage-collected, you already have overhead memory per object, so add one extra bit to this overhead for an &quot;is being stringified&quot; flag. The protocol is then: when an implicit string conversion should take place,</p>
<ul>
<li>If the flag is already set on this object, then return <code>'...'</code>.</li>
<li>Otherwise, set the flag, invoke <code>to_string()</code>, unset the flag, and then use the result.</li>
</ul>
<p>In code, the implementation would look like this (where <code>str</code> is the function called either explicitly or implicitly when a string conversion is needed):</p>
<pre class="lang-python prettyprint-override"><code>def str(obj):
    if obj.is_stringifying:
        return '...'
    else:
        obj.is_stringifying = True
        try:
            return obj.to_string()
        finally:
            obj.is_stringifying = False
</code></pre>
<p>In case it's not clear, the <code>.is_stringifying</code> flag is internal to the language, it is not a &quot;real&quot; attribute and user code isn't supposed to see it. It's part of the object header.</p>
<p>The <code>'...'</code> string could be made an overrideable property on the interface, or a separate method, if you want to give users more control over the string representation of recursive objects. But in this case, there should be a default implementation for the vast majority of cases where this either doesn't matter or can't happen anyway.</p>
<p>Note that this can still suffer from infinite recursion if someone ever invokes <code>.to_string()</code> directly in their own implementation of <code>.to_string()</code>; users instead must call the <code>str</code> function for explicit conversions, or rely on implicit conversions (e.g. when the object is concatenated with a string, or included in a string template). Python deals with this by naming the method <code>__str__</code>, using the convention that methods beginning with two underscores are part of a language protocol and shouldn't be called directly from user code.</p>
<hr />
<p>That said, the above does exhibit some weird behaviour in edge cases. If a user puts some other code inside <code>to_string</code> which calls out of the &quot;stringifying&quot; code into the rest of the application, then that code in the application will not observe the correct stringifying behaviour for all objects.</p>
<p>This isn't necessarily a design problem, since it only happens if the <code>ToString</code> implementation is incorrect; you can also get incorrect behaviour from e.g. the standard library's <code>sort()</code> function if you provide an incorrect comparator implementation. But it is a limitation, and using the object header also means <code>to_string()</code> has to be a synchronised method if the program is multi-threaded, which isn't great.</p>
<p>If you want to address this, here's an alternative approach which does change the <code>ToString</code> interface: the idea is that instead of returning a string, you <em>write</em> the object's string representation to a &quot;writer&quot; object. Then the writer object itself can hold the state of which objects are currently being stringified. (The writer can't safely be passed between threads, but concurrent string conversions in different threads would each have their own writer.)</p>
<p>Here we assume that the <code>ToString</code> interface's <code>to_string</code> method accepts a <code>writer</code> object. Then the protocol for string conversion is that a writer is created, the object's <code>to_string</code> method is invoked passing that writer object, and then the writer's result is used.</p>
<pre class="lang-python prettyprint-override"><code>class Stringifier:
    def __init__(self):
        self._stringifying = set()
        self.out = ''
    
    def write_str(self, s):
        self.out += s
    
    def write_obj(self, obj):
        # a stable, unique id per object
        # could be its address as an integer, if the GC won't move it
        obj_id = id(obj)
        if obj_id in self._stringifying:
            self.write_str('...')
        else:
            self._stringifying.add(obj_id)
            try:
                obj.to_string(self)
            finally:
                self._stringifying.remove(obj_id)

def str(obj):
    writer = Stringifier()
    writer.write_obj(obj)
    return writer.out
</code></pre>
<p>This somewhat resembles how Rust's <a href="https://doc.rust-lang.org/std/fmt/trait.Display.html" rel="nofollow noreferrer"><code>Display</code></a> trait works, except with the added check to avoid self-recursion. But from the user's side, the implementation for a user-defined type looks the same as for implementing <code>Display</code>.</p>
<p>This kind of interface (where you pass a writer around) can also be more efficient than recursive string concatenation, since it doesn't have to build a lot of temporary string objects in the process. Additionally, if the string is meant to be written to e.g. console output or a file, then an appropriate writer object can be provided such that the object's string representation never has to exist in memory all at once.</p>

CC BY-SA 4.0
2023-09-01T13:51:51.747Z
2023-09-01T17:11:23.660Z
2023-09-01T17:11:23.660Z
kaya3
CC BY-SA 4.0
2023-09-01T15:23:07.010Z
The question asks for a suitable interface, i.e. a type or protocol, but what probably is needed is what you provide: an implementation that detects recursion because it is a runtime property and unlikely to be expressed in a type.
Christian Lindig
CC BY-SA 4.0
2023-09-01T15:34:46.280Z
I think this may work not very well in multithreaded programs…
user3840170
CC BY-SA 4.0
2023-09-01T15:55:30.683Z
@user3840170 Good point, if the language has threads then a simple flag in the object header would require synchronising on the object when you stringify it. I've edited to mention this.
kaya3
CC BY-SA 4.0
2023-09-02T03:39:36.793Z
The stringifier is reminiscent of Swift's [`TextOutputStream`](https://developer.apple.com/documentation/swift/textoutputstream)/[`TextOutputStreamable`](https://developer.apple.com/documentation/swift/textoutputstreamable), though by the nature of those protocols they can't detect recursion -- they only have an equivalent to `write_str`, not `write_obj`.
Bbrk24
CC BY-SA 4.0
2023-09-02T05:24:49.703Z
Instead of a flag on the object header, which allows only one such method and requires messing with the internal object representation, you could just use a global `(Weak)Set` that is filled with the objects being stringified. By emptying it only after the initial `to_string` call, you could not just implement loop detection but also avoid printing the same object multiple times.
Bergi
CC BY-SA 4.0
2023-09-02T11:59:24.450Z
@Bergi That's also an option, sure. No need for it to be a weakset, since it only holds references for as long as they're also held by a local variable in an active stack frame ─ that is, unless you plan to leave them in the set until the original `to_string` call, which I don't think is a good idea, because then you can't tell whether `[a, b, ...]` should be `[a, b, a]` or `[a, b, b]` or `[a, b, [...]]`, and converting objects to strings is mainly used for debugging.
kaya3
# Creating an interface for stringifying objects that allows loop detection
Posted by: username_0 on 2023-09-01
Suppose a language has a rust-style trait system but is garbage collected and most types are reference types by default.
I could create a trait like this:
trait ToString {
    fn to_string(self) -> String;
}

Typical implementation would be something like:
impl ToString for List {
    fn to_string(self) -> String { "[" + self.map(|i: T|i.to_string()).join(',') + "]" }
}

But if I then do:
let mut a = []; // [] creates a mutable vector, there are no arrays
a.push(a); // Type of a is decided based on what is added to it
print!(a);

It will create an infinite loop printing the list forever.
In Python, if you do this you'll get:
a = []
a.append(a)
print(a)
# [[...]]

It will detect the cycle and print [...] instead of the full list if the list was already in the process of being printed.
How can I modify my ToString interface to allow types to detect if they are already being printed and prevent an infinite loop for recursive data structures. Ideally it would work for arbitrary data structures and not just lists, while also keeping it ergonomic to implement the interface.
**Tags:** strings
> **Comments:**
> **username_1**: You might also want to check out how Racket does it with [`mpair`s](https://docs.racket-lang.org/reference/mpairs.html). It displays more info about the structure of the cycle(s). For example, if you have `(define a (mlist 1 2 3 4)) (set-mcar! (mcdr (mcdr a)) (mcdr a)) (set-mcdr! (mcdr (mcdr a)) a)` then when you print `a` you get `#0=(mcons 1 #1=(mcons 2 (mcons #1# #0#)))`  
> **username_2**: @DavidYoung FYI, Racket adopted that from Common Lisp.  
> **username_3**: If your language is statically typed, how does `a.push(a)` even work? What is the inferred type?  
> **username_0**: A list of lists of list of lists... @xigoi  
> **username_3**: @mousetail In that case, couldn't you just detect at compile time that the type is self-referential and use a stringifying function that doesn't descend?  
> **username_0**: Yes, but the trick is making that work for arbitrary, user-defined types @xigoi  
---
## 1 answers
### Answer by username_4 on 2023-09-01. Score: 8
I don't think this requires changing your ToString interface itself, rather you can change the protocol by which the language invokes the to_string method. That is, don't just unconditionally call .to_string() when a string conversion is needed.
Here's a simple solution which could work either for a single-threaded language, or for a language like Java which allows synchronising (i.e. reentrant locking) on an object. Since your language is garbage-collected, you already have overhead memory per object, so add one extra bit to this overhead for an "is being stringified" flag. The protocol is then: when an implicit string conversion should take place,

If the flag is already set on this object, then return '...'.
Otherwise, set the flag, invoke to_string(), unset the flag, and then use the result.

In code, the implementation would look like this (where str is the function called either explicitly or implicitly when a string conversion is needed):
def str(obj):
    if obj.is_stringifying:
        return '...'
    else:
        obj.is_stringifying = True
        try:
            return obj.to_string()
        finally:
            obj.is_stringifying = False

In case it's not clear, the .is_stringifying flag is internal to the language, it is not a "real" attribute and user code isn't supposed to see it. It's part of the object header.
The '...' string could be made an overrideable property on the interface, or a separate method, if you want to give users more control over the string representation of recursive objects. But in this case, there should be a default implementation for the vast majority of cases where this either doesn't matter or can't happen anyway.
Note that this can still suffer from infinite recursion if someone ever invokes .to_string() directly in their own implementation of .to_string(); users instead must call the str function for explicit conversions, or rely on implicit conversions (e.g. when the object is concatenated with a string, or included in a string template). Python deals with this by naming the method __str__, using the convention that methods beginning with two underscores are part of a language protocol and shouldn't be called directly from user code.

That said, the above does exhibit some weird behaviour in edge cases. If a user puts some other code inside to_string which calls out of the "stringifying" code into the rest of the application, then that code in the application will not observe the correct stringifying behaviour for all objects.
This isn't necessarily a design problem, since it only happens if the ToString implementation is incorrect; you can also get incorrect behaviour from e.g. the standard library's sort() function if you provide an incorrect comparator implementation. But it is a limitation, and using the object header also means to_string() has to be a synchronised method if the program is multi-threaded, which isn't great.
If you want to address this, here's an alternative approach which does change the ToString interface: the idea is that instead of returning a string, you write the object's string representation to a "writer" object. Then the writer object itself can hold the state of which objects are currently being stringified. (The writer can't safely be passed between threads, but concurrent string conversions in different threads would each have their own writer.)
Here we assume that the ToString interface's to_string method accepts a writer object. Then the protocol for string conversion is that a writer is created, the object's to_string method is invoked passing that writer object, and then the writer's result is used.
class Stringifier:
    def __init__(self):
        self._stringifying = set()
        self.out = ''
    
    def write_str(self, s):
        self.out += s
    
    def write_obj(self, obj):
        # a stable, unique id per object
        # could be its address as an integer, if the GC won't move it
        obj_id = id(obj)
        if obj_id in self._stringifying:
            self.write_str('...')
        else:
            self._stringifying.add(obj_id)
            try:
                obj.to_string(self)
            finally:
                self._stringifying.remove(obj_id)

def str(obj):
    writer = Stringifier()
    writer.write_obj(obj)
    return writer.out

This somewhat resembles how Rust's Display trait works, except with the added check to avoid self-recursion. But from the user's side, the implementation for a user-defined type looks the same as for implementing Display.
This kind of interface (where you pass a writer around) can also be more efficient than recursive string concatenation, since it doesn't have to build a lot of temporary string objects in the process. Additionally, if the string is meant to be written to e.g. console output or a file, then an appropriate writer object can be provided such that the object's string representation never has to exist in memory all at once.
> **Comments:**
> **username_5** (2023-09-01): The question asks for a suitable interface, i.e. a type or protocol, but what probably is needed is what you provide: an implementation that detects recursion because it is a runtime property and unlikely to be expressed in a type.  
> **username_6** (2023-09-01): I think this may work not very well in multithreaded programs…  
> **username_4** (2023-09-01): @user3840170 Good point, if the language has threads then a simple flag in the object header would require synchronising on the object when you stringify it. I've edited to mention this.  
> **username_7** (2023-09-02): The stringifier is reminiscent of Swift's [`TextOutputStream`](https://developer.apple.com/documentation/swift/textoutputstream)/[`TextOutputStreamable`](https://developer.apple.com/documentation/swift/textoutputstreamable), though by the nature of those protocols they can't detect recursion -- they only have an equivalent to `write_str`, not `write_obj`.  
> **username_8** (2023-09-02): Instead of a flag on the object header, which allows only one such method and requires messing with the internal object representation, you could just use a global `(Weak)Set` that is filled with the objects being stringified. By emptying it only after the initial `to_string` call, you could not just implement loop detection but also avoid printing the same object multiple times.  
> **username_4** (2023-09-02): @Bergi That's also an option, sure. No need for it to be a weakset, since it only holds references for as long as they're also held by a local variable in an active stack frame ─ that is, unless you plan to leave them in the set until the original `to_string` call, which I don't think is a good idea, because then you can't tell whether `[a, b, ...]` should be `[a, b, a]` or `[a, b, b]` or `[a, b, [...]]`, and converting objects to strings is mainly used for debugging.  
---
