5 ms·
One day a student came to Moon and said: “I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons.” Mo
by hprotagonist 10y ago
One day a student came to Moon and said: “I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons.”
Moon patiently told the student the following story:
“One day a student came to Moon and said: ‘I understand how to make a better garbage collector...
- hawkice 10y agoIf something is purely functional and doesn't have any fixed point loopholes or other nonsense, you can know that there is no program with circular pointers.
- sp332 10y agoYou also know that your program is not Turing-complete.
- hawkice 10y agoHad a complicated discussion here, but it's ridiculous, because: Church-Turing thesis says lambda calculus is turing complete and it is purely functional with no pointers at all.
- sp332 10y agoBut it does have fixpoints... right? You need recursion somehow.
- hawkice 10y agoYou don't need the type of fixed points that cause the issues with circular pointers. Recursion can be done with (appropriately for HN) the Y combinator. The kind of tricks I'm talking about rely on laziness and are pretty complicated. See: http://stackoverflow.com/questions/37366222/why-is-this-version-of-fix-more-efficient-in-haskell http://stackoverflow.com/questions/37366222/why-is-this-vers...
- catnaroek 10y agoIn Standard ML, all recursive value definitions must have function literals as their right-hand sides. Thus, at runtime, recursion is guaranteed to go through functions (which normally aren't allocated in the heap) and/or mutable data structures (which can be handled in a special way by the garbage collector). Immutable data structures are generally guaranteed to be cycle-free. That being said, reference counting is a really bad fit for functional languages for several other reasons.
- cronjobber 10y agoMake that a functional programming language without mutually recursive first class local functions. (In the case of Lisp/Scheme, no labels or letrec)
- tachyonbeam 10y agoI don't think that's true. I think you could design a purely functional language where everything is immutable, but something contains a circular loop by definition. You could just declare that l is the list of integers going from 0 to 5 and then back to 0 ad infinitum. IMO, circular references can exist without mutation, if the language specifies that something is circular/recursive at the moment it's created. Defining a circular linked list in a declarative way rather than in terms of the instructions that build the linked list. The list is created all at once. It comes into existence with a cycle into it.
- junke 10y agoLike, say, Prolog? A = [a | A] Prolog implementations provide destructive operations and mutation, but here above this is done with unification only. Arguably, you could say that unification performs mutation (but only once).
- spyrosg 10y agoBetter than that, you can "mutate" if you're not invalidating information about the variable. Oz (not incidentally, developed by Prolog people) lets you add constraints to a variable as long as they don't contradict the previous ones. Binding to a specific value is just a very strong constraint. Re-binding to the same value is okay. This is less strict than pure functional programming, but still feels declarative and makes concurrent programming easy: no piece of code that looked previously at your variable will have its assumptions about it broken.
- kazinator 10y agoArguably we could argue that everything flips 1's to 0's and back under the hood, though. Instantiation of a new lexical environment with fresh bindings mutates something in the machine.
- amelius 10y agoHow would you implement recursion then?
- foldr 10y agoxs = 1:xs Lazy evaluation makes it possible to construct circular data structures without mutation.
- kbp 10y agoOr in Lisp one could write #1=(1 . #1#), eg: CL-USER> (subseq '#1=(1 2 3 . #1#) 0 10) (1 2 3 1 2 3 1 2 3 1)
- foldr 10y agoAh that's interesting. I was going to say that in principle a strict language could have a special syntax for defining circular data structures, but I didn't know about that particular corner of CL.