5 ms·
If 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.
by hawkice 10y ago
If 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.