← Back to context

Comment by creata

1 day ago

One solution is to forbid recursive data types - e.g., require every struct type to only reference types that have already been defined. I can't think of any languages that do this.

Another solution is to make things immutable (like Erlang), or "as-if" immutable (like Koka), which guarantees that data can only point to things that have already been defined, preventing cycles.* Erlang uses this to simplify generational collection - because old data can't point to young data, it doesn't need a card table or anything like that.

I think it's perfectly possible to have a general purpose language without cycles: you can just use integer indices into an array instead of pointers if you want cyclic data structures. This is common in Rust, when people want to avoid the overhead of reference counting, but don't want to use unsafe code.

* A hidden assumption here is that the language is eagerly evaluated. There are languages like Haskell that have immutability and cyclic data structures.

5 comments

creata

Reply
asplake  1 day ago

Even with cyclic relationships between types, immutability makes cycles within instances difficult (without laziness anyway). A syntax tree would be a good example.

  • xscott  1 day ago

    Yes, and the nice thing about doing it with immutability is you can still have recursive types to build linked lists, trees, and/or dags. From there you can build hash-array-mapped-tries, finger-trees, and so on, giving you friendly dict/list or JSON style data structures.

  • creata  1 day ago

    Yes, either is sufficient, I think.

    Edit: I think the common idea with both solutions is that our objects have some weak order (the order in which their types were defined, and the time at which the object was created, respectively), and objects are only allowed to point to objects strictly less than them in this order.

daxfohl  18 hours ago

Couldn't you make lazily evaluated code in erlang too, even if it's not lazy by default like Haskell? You'd just need function pointers, right? Or is that not enough?

  • creata  17 hours ago

    Haskell can have circular references because its laziness is implemented with thunks, which have a mutable cell in which to store the computed value so that terms don't get evaluated more than once. Here's a Haskell function that makes a circular linked list:

        -- circular linked list with one item
    repeat x = let xs = x:xs in xs

    Here's a rough equivalent in JavaScript that doesn't use thunks, just functions:

        function repeat(x) {
        function xs() {
            return [x, xs]; // [first, rest]
        }
        return xs;
    }

    The Haskell version has a cycle because, after evaluation, `repeat x` will be a circular linked list, but all the "lists" we create in the JavaScript code above are just the closure `xs`.

    For completeness, here's a JavaScript version that uses thunks:

        class Thunk {
        constructor(f) { this.f = f; }
        get() { if (this.f) { this.v = (this.f)(); delete this.f; } return this.v; }
    }

    function repeat(x) {
        let xs = new Thunk(() => {
            return [x, xs]; // [first, rest]
        });
        return xs;
    }

    If you try calling `x = repeat(1); x.get()`, you can see that we get a circular list.