7 ms·

Can somebody please explain or give me some links how FP is supposed to work without a GC? For example Rust has different types of function pointers (Fn, FnMut,

Can somebody please explain or give me some links how FP is supposed to work without a GC? For example Rust has different types of function pointers (Fn, FnMut, FnOnce), to guarantee the possibility of lifetime analysis (so it is arguable to consider it a functional programming language). On the other hand the most common FP languages (OCaml, Haskell) all come with a GC. Or am I wrong in assuming this is a functional language?

astrange 5y ago
As long as you forbid or mark cycles (…or ignore the problem) lifetime analysis can be done statically. Which is better anyway. Automatic memory management doesn't need a GC.
- silon42 5y ago
  It's really surprising that it's rare in functional languages. Immutability seems like it should guarantee no cycles (?), so reference counting could be used.
  - jbjohns 5y ago
    Why would immutability guarantee no cycles? Here is a line of valid haskell: star e = let (sp, a) = (Split a e, atom sp) in sp EDIT: I guess I should probably explain it: star is a function that takes an expression "e" and returns the value "sp" which is "Split a e" where "a" is the results of calling the "atom" function on "sp". This is creating a representation of a regex star operator. Note that the tuple defined in the let definition is only to define a name for the two values of the tuple so that they can refer to each other.
    - JoelMcCracken 5y ago
      I mean generally tying the knot is a useful technique, but I think these scenarios all require/exploit non-strict, which is in itself not really immutable in the sense most people use it. But yes, such code is often useful so that e.g. a parent xml node can refer to its childen nodes while also children nodes can refer to their parents. Anyway, I'm not sure about this, but I think you can't have circular data structures in the context of strict evaluation (or can you? maybe by defering execution via anonymous functions? I wonder....)
      - jbjohns 5y ago
        I'm fairly certain I've done similar things in Ocaml (in fact, I think it's where I learned this technique).
  - wyager 5y ago
    There are two ways to get cycles in Haskell. One is through “tying the knot”. E.g. to create an infinite list of 1,1,1,1,1,… ones = 1 : ones This will actually be compiled to a list cell with a pointer back to itself. You can construct more complicated self-referential data structures thanks to laziness. The other way you could get a cycle is that it actually does have mutable data structures, although their use is restricted so they can’t have any observable mutable effect in pure code. But you have e.g. IORef which is basically a mutable pointer. If you wanted no cycles you would need to eliminate some subset of laziness, knot-tying transformations, recursion, and any support for mutable data structures. But yes, I think it could be done.
  - kragen 5y ago
    Reference counting is usually very expensive, because even reading a variable updates the reference count, and ending a scope involves testing the reference count of every variable defined inside the scope and conditionally deallocating the referent. Without reference counting, here's the end of a hairy function scope that deallocates 15 local variables and restores two callee-saved registers: 11a6: 48 83 c4 78 add $0x78,%rsp 11aa: 5b pop %rbx 11ab: 41 5e pop %r14 11ad: c3 retq Now imagine looping over 15 local variables to decrement each reference count, test it, and do a conditional jump based on the result; if that's open-coded, your epilogue is humongous, and if it's in a reference-count-decrementing subroutine, it's going to have mispredicted branches all over the place, costing you maybe 15 cycles each, a total of about 100 cycles for this function. We're talking about adding an order of magnitude of cost to subroutine call, or more. (I think this function doesn't really need 15 local variables; that's the compiler's fault.) This gets worse with multithreading, because writing to the same reference count on different cores would even in the best case require one core stealing the cache line from another in order to modify it, which may stall the core; but often even an atomic reference count increment is more expensive even than that because it involves a memory barrier. Reference counting can become reasonably cheap if it's done at large granularity (filesystem files or COM objects, not conses); if you can elide almost all of the reference-count updates, as in Rust; or if your language runtime is just so dog-slow at everything that the extra cost of reference counting isn't that important, like CPython. 30 years ago or more, before generational GC had gone mainstream, reference counting was a more reasonable choice, because GC was going to be very slow in any case, and ref counting at least used less memory—especially important on machines without cache or virtual memory. (Purely immutable (applicative) languages like Haskell and Miranda are usually lazy, since that's the payoff for completely abjuring side effects. But lazy evaluation is implemented at the machine level by mutation.)
    - naasking 5y ago
      > Reference counting is usually very expensive, because even reading a variable updates the reference count There are many papers out there on how to elide most ref count operations on locals, and runtimes that use ref counting for automatic memory management typically defer ref count updates in various clever ways (like Nim IIRC). You give up some latency for significant throughput gains.
  - dwohnitmok 5y ago
    The big thorn is closures, which show up all over the place in FP. You either need to limit closures vs ordinary functions (as e.g. Rust does), have manual memory annotations (such as e.g. what Swift does) or you basically need a GC. The former two choices are annoying if you really take advantage of functions as first-class citizens.
    - silon42 5y ago
      Yes, I thought that might be a problem... I guess Rust is the choice for me.
pharmakom 5y ago
use value semantics for everything is one way
vnorilo 5y ago
Lisp is not necessarily functional. There's a lot of mutation in Common Lisp even if the community favors a functional style. I think the question is: how does Lisp function without garbage collecting cons cells? For one, I'm not sure they even rely on cons cells like "real" Lisp. Clojure doesn't either. They cite ML as inspiration. Carp language guide states object lifetimes are statically inferred [1] which my guess is they allocate on stack (or malloc/free by scope) and detect use-after-free at compile time. Another, more theoretical approach is using linear types which require all values to be "consumed" [2] 1: https://github.com/carp-lang/Carp/blob/master/docs/LanguageGuide.md https://github.com/carp-lang/Carp/blob/master/docs/LanguageG... 2: https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash-cons-papers/BakerLinearLisp.pdf https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash...
- protomikron 5y ago
  Thanks for the links. There's also this Reddit discussion [0] from 2 years ago (it mentions Carp btw.) and an explanation about how Carp manages memory [1]. [0] https://www.reddit.com/r/haskell/comments/d5d13i/is_it_possible_to_design_a_functional_language/ https://www.reddit.com/r/haskell/comments/d5d13i/is_it_possi... [1] https://github.com/carp-lang/Carp/blob/master/docs/Memory.md https://github.com/carp-lang/Carp/blob/master/docs/Memory.md
  - alexisread 5y ago
    In particular, the reddit discussion mentions ASAP, which is a set of static analysis algorithms that can work with mutability, generics (polymorphism) and linear types. http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-908.pdf http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-908.pdf As far as I'm aware, this really only applies to single threaded systems. However, if you implement threadsafe modules and keep the shared stuff internal (use the ASAP algos here), you can fit the majority of use-cases including hard-realtime constraints. Composita is the module system I'm referring to. http://www.composita.net/Composita.html http://www.composita.net/Composita.html It allows concurrency with managed memory and no GC, through static analysis of the module (component) interface queues.
- 5y ago
timonoko 5y ago
Me knows: "TN-tools in Nokia were automatically compiled into C-code to be run in VAX-computers. Compiled C-code did not have garbage collector, there was separate reclaim-command for discarding used data. If you managed to run your program without ever hearing the BEEP caused by garbage collector, your program was ready for VAXing." https://timonoko.github.io/Nokolisp.htm https://timonoko.github.io/Nokolisp.htm
mlang23 5y ago
Lisp is definitely not as functional as for instance Haskell is. Side-effect-freeness was never really a topic for Lispers.
- medo-bear 5y ago
  You are right, Lisp is far more versatile. There is even a statically-typed language Coalton [1] embedded into Lisp. [1] https://coalton-lang.github.io/20211010-introducing-coalton/ https://coalton-lang.github.io/20211010-introducing-coalton/
cmrdporcupine 5y ago
From the Carp docs: Memory management is handled by static analysis, a value is owned by the function where it was created. When a value is returned or passed to another function the initial function will give up ownership of it and any subsequent use will lead to a compiler error. To temporarily lend a value to another function (for example to print it) a reference must be created, using the ref special form (or the & reader macro). and achieved through a linear type system where memory is owned by the function or let-scope that allocated it. When the scope is exited the memory is deleted, unless it was returned to its outer scope or handed off to another function (passed as an argument).
- andi999 5y ago
  So how is memory fragmentation avoided?
  - pjc50 5y ago
    That's a question for the underlying allocator, surely? (Quite often the answer is "it isn't")
    - andi999 5y ago
      Not just for the allocator. I always thought a main point of a garbage collector was heap compactification (shuffling things around so there is more space), but maybe I am wrong.
      - xxs 5y ago
        Not every GC has compaction phase though, but generational ones do by design.
      - cmrdporcupine 5y ago
        Nah, only copying / generational collectors do heap compactification. A simple Mark&Sweep collector doesn't, for example. Nor does reference counting. Both of which are used by many Lisp or Lisp-like languages. Nothing can substitute for a really good allocator.
mumblemumble 5y ago
In general, most lisps are imperative, or support multiple paradigms including imperative. First-class functions are a necessary feature of FP, but the mere presence of the feature does not make a language functional. Some counterexamples include Fortran and Smalltalk. It's an easy misconception because most the well-known newer entries to the lisp family - Scheme, Racket, and Clojure - are all mostly functional, and because most of the major non-functional dialects of lisp died out 30 or 40 years ago.
RobertKerans 5y ago
& Rust is surely a highly imperative language that has absorbed functional idioms (where appropriate), rather than something that falls under the banner of "functional language"?
- amelius 5y ago
  There's a reason why functional languages all use a GC. And that reason makes Rust not such a good language for functional idioms unless you stay within very strict lines.

astrange 5y ago

As long as you forbid or mark cycles (…or ignore the problem) lifetime analysis can be done statically. Which is better anyway. Automatic memory management doesn't need a GC.

silon42 5y ago
It's really surprising that it's rare in functional languages. Immutability seems like it should guarantee no cycles (?), so reference counting could be used.
- jbjohns 5y ago
  Why would immutability guarantee no cycles? Here is a line of valid haskell: star e = let (sp, a) = (Split a e, atom sp) in sp EDIT: I guess I should probably explain it: star is a function that takes an expression "e" and returns the value "sp" which is "Split a e" where "a" is the results of calling the "atom" function on "sp". This is creating a representation of a regex star operator. Note that the tuple defined in the let definition is only to define a name for the two values of the tuple so that they can refer to each other.
  - JoelMcCracken 5y ago
    I mean generally tying the knot is a useful technique, but I think these scenarios all require/exploit non-strict, which is in itself not really immutable in the sense most people use it. But yes, such code is often useful so that e.g. a parent xml node can refer to its childen nodes while also children nodes can refer to their parents. Anyway, I'm not sure about this, but I think you can't have circular data structures in the context of strict evaluation (or can you? maybe by defering execution via anonymous functions? I wonder....)
    - jbjohns 5y ago
      I'm fairly certain I've done similar things in Ocaml (in fact, I think it's where I learned this technique).
- wyager 5y ago
  There are two ways to get cycles in Haskell. One is through “tying the knot”. E.g. to create an infinite list of 1,1,1,1,1,… ones = 1 : ones This will actually be compiled to a list cell with a pointer back to itself. You can construct more complicated self-referential data structures thanks to laziness. The other way you could get a cycle is that it actually does have mutable data structures, although their use is restricted so they can’t have any observable mutable effect in pure code. But you have e.g. IORef which is basically a mutable pointer. If you wanted no cycles you would need to eliminate some subset of laziness, knot-tying transformations, recursion, and any support for mutable data structures. But yes, I think it could be done.
- kragen 5y ago
  Reference counting is usually very expensive, because even reading a variable updates the reference count, and ending a scope involves testing the reference count of every variable defined inside the scope and conditionally deallocating the referent. Without reference counting, here's the end of a hairy function scope that deallocates 15 local variables and restores two callee-saved registers: 11a6: 48 83 c4 78 add $0x78,%rsp 11aa: 5b pop %rbx 11ab: 41 5e pop %r14 11ad: c3 retq Now imagine looping over 15 local variables to decrement each reference count, test it, and do a conditional jump based on the result; if that's open-coded, your epilogue is humongous, and if it's in a reference-count-decrementing subroutine, it's going to have mispredicted branches all over the place, costing you maybe 15 cycles each, a total of about 100 cycles for this function. We're talking about adding an order of magnitude of cost to subroutine call, or more. (I think this function doesn't really need 15 local variables; that's the compiler's fault.) This gets worse with multithreading, because writing to the same reference count on different cores would even in the best case require one core stealing the cache line from another in order to modify it, which may stall the core; but often even an atomic reference count increment is more expensive even than that because it involves a memory barrier. Reference counting can become reasonably cheap if it's done at large granularity (filesystem files or COM objects, not conses); if you can elide almost all of the reference-count updates, as in Rust; or if your language runtime is just so dog-slow at everything that the extra cost of reference counting isn't that important, like CPython. 30 years ago or more, before generational GC had gone mainstream, reference counting was a more reasonable choice, because GC was going to be very slow in any case, and ref counting at least used less memory—especially important on machines without cache or virtual memory. (Purely immutable (applicative) languages like Haskell and Miranda are usually lazy, since that's the payoff for completely abjuring side effects. But lazy evaluation is implemented at the machine level by mutation.)
  - naasking 5y ago
    > Reference counting is usually very expensive, because even reading a variable updates the reference count There are many papers out there on how to elide most ref count operations on locals, and runtimes that use ref counting for automatic memory management typically defer ref count updates in various clever ways (like Nim IIRC). You give up some latency for significant throughput gains.
- dwohnitmok 5y ago
  The big thorn is closures, which show up all over the place in FP. You either need to limit closures vs ordinary functions (as e.g. Rust does), have manual memory annotations (such as e.g. what Swift does) or you basically need a GC. The former two choices are annoying if you really take advantage of functions as first-class citizens.
  - silon42 5y ago
    Yes, I thought that might be a problem... I guess Rust is the choice for me.

pharmakom 5y ago

use value semantics for everything is one way

vnorilo 5y ago

Lisp is not necessarily functional. There's a lot of mutation in Common Lisp even if the community favors a functional style. I think the question is: how does Lisp function without garbage collecting cons cells? For one, I'm not sure they even rely on cons cells like "real" Lisp. Clojure doesn't either. They cite ML as inspiration. Carp language guide states object lifetimes are statically inferred [1] which my guess is they allocate on stack (or malloc/free by scope) and detect use-after-free at compile time. Another, more theoretical approach is using linear types which require all values to be "consumed" [2] 1: https://github.com/carp-lang/Carp/blob/master/docs/LanguageGuide.md https://github.com/carp-lang/Carp/blob/master/docs/LanguageG... 2: https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash-cons-papers/BakerLinearLisp.pdf https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash...

protomikron 5y ago
Thanks for the links. There's also this Reddit discussion [0] from 2 years ago (it mentions Carp btw.) and an explanation about how Carp manages memory [1]. [0] https://www.reddit.com/r/haskell/comments/d5d13i/is_it_possible_to_design_a_functional_language/ https://www.reddit.com/r/haskell/comments/d5d13i/is_it_possi... [1] https://github.com/carp-lang/Carp/blob/master/docs/Memory.md https://github.com/carp-lang/Carp/blob/master/docs/Memory.md
- alexisread 5y ago
  In particular, the reddit discussion mentions ASAP, which is a set of static analysis algorithms that can work with mutability, generics (polymorphism) and linear types. http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-908.pdf http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-908.pdf As far as I'm aware, this really only applies to single threaded systems. However, if you implement threadsafe modules and keep the shared stuff internal (use the ASAP algos here), you can fit the majority of use-cases including hard-realtime constraints. Composita is the module system I'm referring to. http://www.composita.net/Composita.html http://www.composita.net/Composita.html It allows concurrency with managed memory and no GC, through static analysis of the module (component) interface queues.
5y ago

timonoko 5y ago

Me knows: "TN-tools in Nokia were automatically compiled into C-code to be run in VAX-computers. Compiled C-code did not have garbage collector, there was separate reclaim-command for discarding used data. If you managed to run your program without ever hearing the BEEP caused by garbage collector, your program was ready for VAXing." https://timonoko.github.io/Nokolisp.htm https://timonoko.github.io/Nokolisp.htm

mlang23 5y ago

Lisp is definitely not as functional as for instance Haskell is. Side-effect-freeness was never really a topic for Lispers.

medo-bear 5y ago
You are right, Lisp is far more versatile. There is even a statically-typed language Coalton [1] embedded into Lisp. [1] https://coalton-lang.github.io/20211010-introducing-coalton/ https://coalton-lang.github.io/20211010-introducing-coalton/

cmrdporcupine 5y ago

From the Carp docs: Memory management is handled by static analysis, a value is owned by the function where it was created. When a value is returned or passed to another function the initial function will give up ownership of it and any subsequent use will lead to a compiler error. To temporarily lend a value to another function (for example to print it) a reference must be created, using the ref special form (or the & reader macro). and achieved through a linear type system where memory is owned by the function or let-scope that allocated it. When the scope is exited the memory is deleted, unless it was returned to its outer scope or handed off to another function (passed as an argument).

andi999 5y ago
So how is memory fragmentation avoided?
- pjc50 5y ago
  That's a question for the underlying allocator, surely? (Quite often the answer is "it isn't")
  - andi999 5y ago
    Not just for the allocator. I always thought a main point of a garbage collector was heap compactification (shuffling things around so there is more space), but maybe I am wrong.
    - xxs 5y ago
      Not every GC has compaction phase though, but generational ones do by design.
    - cmrdporcupine 5y ago
      Nah, only copying / generational collectors do heap compactification. A simple Mark&Sweep collector doesn't, for example. Nor does reference counting. Both of which are used by many Lisp or Lisp-like languages. Nothing can substitute for a really good allocator.

mumblemumble 5y ago

In general, most lisps are imperative, or support multiple paradigms including imperative. First-class functions are a necessary feature of FP, but the mere presence of the feature does not make a language functional. Some counterexamples include Fortran and Smalltalk. It's an easy misconception because most the well-known newer entries to the lisp family - Scheme, Racket, and Clojure - are all mostly functional, and because most of the major non-functional dialects of lisp died out 30 or 40 years ago.

RobertKerans 5y ago

& Rust is surely a highly imperative language that has absorbed functional idioms (where appropriate), rather than something that falls under the banner of "functional language"?

amelius 5y ago
There's a reason why functional languages all use a GC. And that reason makes Rust not such a good language for functional idioms unless you stay within very strict lines.