The care and feeding of cyclic data structures

I’ve finally managed to find some time to do a little bit more work on Arcueid, and now I’m engaged in a major code reorganisation and simplification that should make things a bit cleaner, and I have a bit of a better idea for how to fix some of the most serious problems in the 0.0.x series of the interpreter: perhaps we’ll have a 0.1.0 series soon. More on that anon.

Anyhow, what this post is really about is something that has been bothering me about the current Arc interpreter for a long time. It is very easy to crash the interpreter by simply doing the following:

arc> (= x '(1 2))
arc> (scdr x x)

This sends arc3 and every version of Anarki I have tried into an infinite loop. Seems like it shouldn’t be too hard to fix, and in the experimental branch of Arcueid I have made attempts to deal with cyclic structures like that one somehow by using a hash table that keeps track of what goes where. The pretty printer algorithm I’m testing for the new version now displays something a bit more reasonable:

arc> (= x '(1 2))
arc> (scdr x x)
(1 . (...))

There are other possibilities on what to display that may be a bit more sophisticated, but I don’t think that they’re all that useful for now. For example, the above structure could be displayed as:

arc> (= x '(1 2))
arc> (scdr x x)
#0=(1 . #0#)

as some Scheme interpreters do. Maybe we’ll eventually do something similar.

It is essentially impossible to use cyclic structures in meaningful ways within Arc at the moment thanks to some rather naïve algorithms even for some fairly simple functions like for ‘iso’. The new version I have in the works does essentially a depth-first search whenever traversing a data structure that might be cyclic, by using a hash table to keep track of what has already been visited.

~ by stormwyrm on 2013-02-21.

One Response to “The care and feeding of cyclic data structures”

  1. Nice! I commented on this at

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: