recshow(): show() for self-referential and DAG-structured objects

92 views
Skip to first unread message

Toivo Henningsson

unread,
Aug 6, 2012, 8:44:35 AM8/6/12
to juli...@googlegroups.com
I've implemented a prototype show() function recshow() that handles self-referential objects.

Examples:

    require("recshow.jl")
    type T; x; y; end
    type Unshowable; end
    show(io::IO, x::Unshowable) = error("Tried to show Unshowable()")

    println("Simple and tree structured objects: just as show")
    recshow(1.55);   println()
    recshow(155);    println()
    recshow("abc");  println()
    recshow(T(1,2)); println()

    println("\nSelf-referential object:")
    s = T(1,1); s.y = s
    recshow(s); println()

    println("DAG structured object:")
    t = T(1,1)
    recshow(T(t,t)); println()

    println("Exception during show recording ==> partial printout:")
    recshow(T(s, Unshowable()))

produces

    Simple and tree structured objects: just as show
    1.55
    155
    "abc"
    T(1, 2)

    Self-referential object:
    <obj>    = T(1, <obj>)

    DAG structured object:
    <obj>    = T(<x1>, <x1>)
    <x1>     = T(1, 1)

    Exception during show recording ==> partial printout:
    <obj>    = T(<x1>, #encountered exception!
    <x1>     = T(1, <x1>)
    Exception in recshow:
    Tried to print Unshowable()
     in recshow at recshow.jl:158
     in recshow at recshow.jl:163
     in load at util.jl:230
     in load at util.jl:242
    at test.jl:28
     in load at util.jl:253

I think it would be nice to eventually replace the use of show() in the REPL by this kind of functionality.
It should be helpful in working with any kind of data structure that is not a tree;
e g in my own DAG coding I've been swamped by repeat printouts.

To create a place to detect cycles and repeats, I've had to split the use of show() into two parts:
  • When creating a new type, implement a show() method to show it
  • When showing an object, use rshow()
To make the cycle detection work with a given type, calls to show inside of show itself must be replaced by rshow. (better name, anyone?)
This is where I need help, and feedback!
Do people think this is a good way to go about it?

 / Toivo


ps.
I've attached my current recshow.jl, which should hopefully reproduce the examples above.
The tricks to capture strings going to the IO seem to be a bit different between the julia versions,
so please let me know if it fails.

The code captures the entire output of show into a graph structure, manipulates it a bit, and then prints it.
It also contains a default show implementation for composite types written in julia, that uses rshow on the field's values.

I made recshow() inline short printouts of repeated objects, but only if they are immutable.
This should prevent losing info about object identity in the printout.

 / Toivo

recshow.jl

Toivo Henningsson

unread,
Aug 7, 2012, 3:48:05 AM8/7/12
to juli...@googlegroups.com

Ok, to be more blunt.
How would you guys feel if I were to submit a pull request to replace

    print(io::IO, x) = show(io, x)

in string.jl:3 with

    print(io::IO, x) = rshow(io, x)
    rshow(io::IO, x) = show(io, x)

and to replace in base/ all recursive calls to show within show with calls to rshow instead?
The intent is that rshow may be overloaded on the io argument, while show is overloaded on the x argument.

I know that this is controversial, since it alters the design of how to call/implement show.
But I see no other way to let the plethora of show implementations work for showing self-referential data.
This is why I would like to initiate a discussion. Any thoughts welcome!

 / Toivo

Btw, here is a gist with the (slightly updated) code: https://gist.github.com/3282772

Jeffrey Sarnoff

unread,
Aug 8, 2012, 9:24:20 AM8/8/12
to juli...@googlegroups.com
In your test.jl code,
type T
x
y
end
s = T(1,1); s.y = s

show(s) displays "T(1,T(1,T(1 ... stack overflow" and recshow(s) displays "<obj>    = T(1, <obj>)".
I agree that show(s) should show self-referential objects gracefully and clearly, which recshow(s) does.
 
My only suggestions are
(1) the resolution should work for other's tailored show(), print() routines made for their self-referential types without attention to the detail you see.  
(2) the resolution should incur no special constructions with users writing show(), print() routines for other things.

tor

unread,
Aug 8, 2012, 1:52:35 PM8/8/12
to juli...@googlegroups.com

Looks useful. I don't understand why this should be controversial. A standard way of showing self referenial objects seems like an obvious idea. Rshow has my vote.

One thing though, both show and rshow are very slow.

here I build an AVL tree with 300 nodes:

julia> tic(); t = build([1:300], [1:300]); toc();
elapsed time: 0.0008909702301025391 seconds

then I show it:

tic(); recshow(t); toc()
Node([Node([Node([Node([  ...  ],19,19,37,0), Node([  ...  ],57,57,37,0)],38,38,75,0)  ...  ],76,76,150,0)  ...  ], 151, 151, 300, 0)
elapsed time: 7.463517904281616 seconds

It appears to run in exponential time of the number of tree nodes. Plain old show is exactly the same.

Tim Holy

unread,
Aug 8, 2012, 2:26:16 PM8/8/12
to juli...@googlegroups.com
On Tuesday, August 07, 2012 12:48:05 AM Toivo Henningsson wrote:
> Ok, to be more blunt.
> How would you guys feel if I were to submit a pull request
> [snip]
> I know that this is controversial, since it alters the design of how to
> call/implement show.
> But I see no other way to let the plethora of show implementations work for
> showing self-referential data.
> This is why I would like to initiate a discussion.

You may get the most discussion from core developers if you simply go ahead
and submit that pull request. Then people can open a branch, test it out, use
GitHub to make comments on individual lines, etc. Much of the communication
among core developers seems to happen on GitHub. Now that I've been using it a
while, I see why.

--Tim

Stefan Karpinski

unread,
Aug 8, 2012, 2:29:37 PM8/8/12
to juli...@googlegroups.com
Part of the reason is that having a pull request of some functionality makes it pretty easy to try something out. With text pasted into an email, there's a lot of messing around required to even try something out. I suspect that we want to take some of this functionality and just bake it into the default show, which really ought to handle printing recursive data structures but doesn't because we just haven't gotten around to it.


--Tim

--




Toivo Henningsson

unread,
Aug 8, 2012, 4:17:59 PM8/8/12
to juli...@googlegroups.com


On Wednesday, August 8, 2012 8:29:37 PM UTC+2, Stefan Karpinski wrote:
Part of the reason is that having a pull request of some functionality makes it pretty easy to try something out. With text pasted into an email, there's a lot of messing around required to even try something out. I suspect that we want to take some of this functionality and just bake it into the default show, which really ought to handle printing recursive data structures but doesn't because we just haven't gotten around to it.

Ok, great! I'll see if I can get that pull request in order.

I just wanted to know if I was going in the right direction, or if anyone has any strong opinions about this, since it's a pretty big break with the current functionality in a few ways:
  • recshow has to consume the entire output before it can present anything to the user,
    or it might miss to name a result that is reused.
  • show must to be split into two functions:
    one user-facing (currently rshow),
    one to implement for new types (currently show)

Stefan Karpinski

unread,
Aug 8, 2012, 4:26:11 PM8/8/12
to juli...@googlegroups.com
On Wed, Aug 8, 2012 at 4:17 PM, Toivo Henningsson <toiv...@gmail.com> wrote:

Ok, great! I'll see if I can get that pull request in order.

Yes, please!
 
I just wanted to know if I was going in the right direction, or if anyone has any strong opinions about this, since it's a pretty big break with the current functionality in a few ways:
  • recshow has to consume the entire output before it can present anything to the user,
    or it might miss to name a result that is reused.
  • show must to be split into two functions:
    one user-facing (currently rshow),
    one to implement for new types (currently show)

Splitting into two functions is ok, but the consuming an entire object bit is problematic. I'm not keen on the <obj> = {<obj>} output style. Maybe we can come up with something that allows incremental printing and is more in line with existing syntax.

Toivo Henningsson

unread,
Aug 9, 2012, 7:31:58 AM8/9/12
to juli...@googlegroups.com


On Wednesday, August 8, 2012 10:26:11 PM UTC+2, Stefan Karpinski wrote:
On Wed, Aug 8, 2012 at 4:17 PM, Toivo Henningsson <toiv...@gmail.com> wrote:

Ok, great! I'll see if I can get that pull request in order.

Yes, please!

Ok, it's in. So now I guess we can take the issues from there...

Splitting into two functions is ok, but the consuming an entire object bit is problematic. I'm not keen on the <obj> = {<obj>} output style. Maybe we can come up with something that allows incremental printing and is more in line with existing syntax

I agree. I'm interested in if anyone comes up with a better way.
The presentation can definitely be improved (but I'm not sure how :)

Reply all
Reply to author
Forward
0 new messages