4 ms·

In Haskell, data are immutable and yet cyclic structures are possible. allOnes = 1 : allOnes

openasocket 10y ago
This is possible in Haskell because it allows for lazy evaluation. In a strict language, immutability means you can't form cycles.
- pklausler 10y ago
  While non-strict evaluation helps with forming cyclic structures in general, in this specific example it is not required. You just need a language that allows names to appear in their bindings, such as in C: struct node { int x; struct node *next; } allOnesList = { 1, &allOnesList }, *allOnes = &allOnesList;
  - openasocket 10y ago
    Haha, I hadn't thought of that! That ability to create self-referential data is the main factor. That isn't really possible in lisp without some sort of letrec function, which this lisp shouldn't support. You would also have to watch out for recursive function definitions. Usually, the function body will just contain the symbol that refers to the function, which conceptually is similar to a straight pointer to the function, and someone might try to optimize it that way. In fact, with more thought, I realized the lazy evaluation is actually orthogonal to forming cyclic data. The "allOnes = 1 : allOnes" line doesn't necessarily form a cycle (depending on the interpreter/compiler, I imagine ghc and any other sensible implementation will form a cycle). Naively, this will just create a thunk which will get repeatedly evaluated, generating a long list of ones. EDIT: Nevermind, you're right.
    - pklausler 10y ago
      Thunks don't get repeatedly evaluated, sorry. Just once at most.
  - dfox 10y ago
    For normal lisp implementations, allowing names to appear in their own definitions requires lexical environment frame to be mutable, which breaks the assumption that all notionally on-heap objects are immutable. This observation is somewhat relevant to the weird semantics of "lexical" scoping in Python, because the obvious semantics would cause cycle between frame object and function defined in it's scope.

This is possible in Haskell because it allows for lazy evaluation. In a strict language, immutability means you can't form cycles.

pklausler 10y ago
While non-strict evaluation helps with forming cyclic structures in general, in this specific example it is not required. You just need a language that allows names to appear in their bindings, such as in C: struct node { int x; struct node *next; } allOnesList = { 1, &allOnesList }, *allOnes = &allOnesList;
- openasocket 10y ago
  Haha, I hadn't thought of that! That ability to create self-referential data is the main factor. That isn't really possible in lisp without some sort of letrec function, which this lisp shouldn't support. You would also have to watch out for recursive function definitions. Usually, the function body will just contain the symbol that refers to the function, which conceptually is similar to a straight pointer to the function, and someone might try to optimize it that way. In fact, with more thought, I realized the lazy evaluation is actually orthogonal to forming cyclic data. The "allOnes = 1 : allOnes" line doesn't necessarily form a cycle (depending on the interpreter/compiler, I imagine ghc and any other sensible implementation will form a cycle). Naively, this will just create a thunk which will get repeatedly evaluated, generating a long list of ones. EDIT: Nevermind, you're right.
  - pklausler 10y ago
    Thunks don't get repeatedly evaluated, sorry. Just once at most.
- dfox 10y ago
  For normal lisp implementations, allowing names to appear in their own definitions requires lexical environment frame to be mutable, which breaks the assumption that all notionally on-heap objects are immutable. This observation is somewhat relevant to the weird semantics of "lexical" scoping in Python, because the obvious semantics would cause cycle between frame object and function defined in it's scope.