7 ms·

Very impressive. > SectorLISP uses what we call an ABC garbage collector and it took only 40 bytes of assembly. > [...] > Fast immediate garbage collection w

Very impressive. > SectorLISP uses what we call an ABC garbage collector and it took only 40 bytes of assembly. > [...] > Fast immediate garbage collection with zero memory overhead and perfect heap defragmentation is as easy as ABC when your language guarantees data structures are acyclic. Neat, but my understanding was that even pure functional languages can't generally make this guarantee, because things like letrec complicate matters. If SectorLISP can take this approach, why doesn't Haskell? (Or does it?)

aidenn0 5y ago
I mean even a doubly-linked list is a cyclic data structure...
- MaxBarraclough 5y ago
  Sure, but presumably they can't be expressed in SectorLISP.
__s 5y ago
Haskell does, https://wiki.haskell.org/GHC/Memory_Management https://wiki.haskell.org/GHC/Memory_Management
- WJW 5y ago
  I'm pretty sure that Haskell supports cyclic data structures and that GHC garbage collection is more complicated than that. See for example the presentation by Ben Gamari over here: https://www.youtube.com/watch?v=EQqBpVRA3wU https://www.youtube.com/watch?v=EQqBpVRA3wU. Haskell GC is a generational copying design. Optionally you can enable the low-latency GC in newer runtimes, which is still generational and copying for the youngest generation but uses a parallel mark-and-sweep algorithm for the later generations.
  - __s 5y ago
    Potentially cyclic values are statically known But yes, GCs have evolved in the past decade, so these things are subject to change
- kmill 5y ago
  That page is incorrect about GHC's memory management -- I verified this with a question to haskell-cafe around 2014, and I guess no one got around to updating it. The linked paper at the bottom of the article explains how things work and have worked for a long time now. The source of cyclic references, and even references from old to new generations, comes from "thunks" (unevaluated lazy computations). Haskell guarantees that a thunk only ever gets evaluated once, and the way this is implemented is that the thunk is mutated with a pointer to the evaluation result. So the garbage collector needs to deal with mutations, cyclic references, and references from old to new generations. (All that in a language with supposedly immutable data!)
ridiculous_fish 5y ago
I believe Erlang makes this guarantee and exploits it in the GC: ...the terms are immutable and thus there can be no pointers modified on the old heap to point to the young heap so old objects cannot refer to young objects. This means it doesn't have to deal with write barriers, etc.
supergarfield 5y ago
Letrec requires either laziness (which implies some sort of internal mutability, as thunks get replaced by values at some point), or "internal" mutability that may not be visible to the programmer (like in OCaml, where in a `let rec` some variables will initially be null pointers, and get updated once other definitions have run). In languages with no mutability at all (not even internal mutability like with these two features), you can't create cycles and refcounting becomes possible, but I'm not aware of non-academic general purpose languages that actually fall in this category. Esoteric functional languages like Unlambda do make that guarantee, and implementations can use a ref counter as their GC. I've written more about this here: https://terbium.io/2019/09/cyclic-immutable/ https://terbium.io/2019/09/cyclic-immutable/
- macintux 5y ago
  > I'm not aware of non-academic general purpose languages that actually fall in this category. Erlang?
  - masklinn 5y ago
    Erlang does have some mutability (the process dictionary, and the mailbox), but the fact that the language is largely immutable is leveraged by the GC: if I remember correctly the private heap GC is a generational semi-space copying GC, but because the language is immutable it doesn’t need to have write barriers, to perform a minor collection only a scan of the stack（and process dict) is necessary to know the valid roots of the young heap.
- isaacimagine 5y ago
  If data is immutable and you tie the lifetime of data to a single stack frame, you only need a single bit for reference counting: whether the current frame owns the reference. Calling a function just requires setting this to bit low (some asterisks here), and all objects tied to a given frame can be collected when the frame returns.
IsTom 5y ago
Strict purely functional languages will sometimes provably introduce log n slowdown that can't be amortized away. This is certainly a trade-off. This doesn't happen when you've got mutation or laziness. One language that I'm aware which makes this tradeoff is Erlang.
- foldr 5y ago
  Elm is also strict and purely functional.
  - masklinn 5y ago
    elm does not have its own runtime so this discussion doesn’t really apply.
    - foldr 5y ago
      Ah, I wasn't referring to the point about garbage collection further up the thread. I was just noting that Elm is another example of a strict purely functional language (and so another example of a language that gets purity in exchange for losing access to certain O(n) algorithms).
- mixedmath 5y ago
  When you say log n slowdown, what is n here? The length of the program? Or something completely different?
  - dan-robertson 5y ago
    I think the theme is ‘you can’t do arrays; the best approximation is made of trees, hence log n in the size of the array vs 1’.
    - remexre 5y ago
      Though I think Clojure has a linear datastructure that's O(log32(n)) for all the common ops. (This is the one with all the memeing because someone called it "practically O(1)".)
jart 5y ago
Author here. Why would it? Let's have a look at Scheme letrec (or let* in Emacs Lisp) translated to pseudo-SectorLISP: (LETREC ((IS-ODD? (QUOTE (LAMBDA (X) (CAR X)))) (IS-EVEN? (QUOTE (LAMBDA (X) (NOT (IS-ODD X)))))) (IS-EVEN? (QUOTE (NIL T NIL T)))) The oldskool LISP way of writing that is: ((LAMBDA (IS-ODD? IS-EVEN?) (IS-EVEN? (QUOTE (NIL T NIL T)))) (QUOTE (LAMBDA (X) (CAR X))) (QUOTE (LAMBDA (X) (NOT (IS-ODD X))))) As far as I can tell, letrec is just a nicer syntax for the same thing. So I don't know why it should require any mutability. It works probably because LISP is dynamically scoped. Most languages and modern LISP implementations prefer different scoping models to make the Assoc() equation faster. However that comes at a cost, since it can turn the difficulty of LISP up to 11. Next thing you know, you're discovering things like the Y combinator. So I have major respect for what languages like Haskell and Scheme are doing, because it's incredibly difficult. One of the reasons why I created SectorLISP is because I wanted to have a fun bastion of simplicity when I don't need the more mature tools. SectorLISP doesn't have any kind of internal mutability last time I checked. But I have experimented with it. For example, the Peel() optimization described in the blog post is how we solve the "make Assoc() faster problem". As it's written in the blog post, it's 100% pure. But if you introduce a tiny bit of mutability, it can go even faster on benchmarks even though it doesn't change the complexity class. See https://justine.lol/sectorlisp2/fast.js https://justine.lol/sectorlisp2/fast.js
- dan-robertson 5y ago
  I think you’ve a trivial error in your function definitions but I don’t think it’s relevant. I think you’re right about avoiding cycles. I think the parent was talking about a let rec construction for data, e.g. in Haskell: let funky_list = 1:2:3:4:funky_list (Note that : is the cons operator). If this is allowed then you may have issues. I think the problem is perhaps that the GC won’t work if you have pointers in the opposite of the normal direction. The fix though is relatively simple: add forwarding pointers (somehow), then after copying from the ‘B’ region to the ‘C’ region you leave behind a forwarding pointer and, if you see it again in your copying, you don’t make a duplicate copy of the data. Then I think you can proceed as before. But representing forwarding pointers efficiently is hard, I suspect. Actually I think I don’t understand the GC sufficiently. Do you end up with a lot of memory usage after this or a little? ((LAMBDA (D Z) (D Z)) (QUOTE (LAMBDA (X) (COND (X ((LAMBDA (Y) (CONS Y Y)) (D (CDR X)))) ((QUOTE T) (QUOTE T))))) (QUOTE (A A A A A A A A))) This should get you a binary tree about 8 levels deep with T on every leaf, and I think it should use linear memory (in the depth of the tree) but I don’t understand how the GC avoids ending up with an exponential amount of memory being used?

aidenn0 5y ago

I mean even a doubly-linked list is a cyclic data structure...

MaxBarraclough 5y ago
Sure, but presumably they can't be expressed in SectorLISP.

__s 5y ago

Haskell does, https://wiki.haskell.org/GHC/Memory_Management https://wiki.haskell.org/GHC/Memory_Management

WJW 5y ago
I'm pretty sure that Haskell supports cyclic data structures and that GHC garbage collection is more complicated than that. See for example the presentation by Ben Gamari over here: https://www.youtube.com/watch?v=EQqBpVRA3wU https://www.youtube.com/watch?v=EQqBpVRA3wU. Haskell GC is a generational copying design. Optionally you can enable the low-latency GC in newer runtimes, which is still generational and copying for the youngest generation but uses a parallel mark-and-sweep algorithm for the later generations.
- __s 5y ago
  Potentially cyclic values are statically known But yes, GCs have evolved in the past decade, so these things are subject to change
kmill 5y ago
That page is incorrect about GHC's memory management -- I verified this with a question to haskell-cafe around 2014, and I guess no one got around to updating it. The linked paper at the bottom of the article explains how things work and have worked for a long time now. The source of cyclic references, and even references from old to new generations, comes from "thunks" (unevaluated lazy computations). Haskell guarantees that a thunk only ever gets evaluated once, and the way this is implemented is that the thunk is mutated with a pointer to the evaluation result. So the garbage collector needs to deal with mutations, cyclic references, and references from old to new generations. (All that in a language with supposedly immutable data!)

ridiculous_fish 5y ago

I believe Erlang makes this guarantee and exploits it in the GC: ...the terms are immutable and thus there can be no pointers modified on the old heap to point to the young heap so old objects cannot refer to young objects. This means it doesn't have to deal with write barriers, etc.

supergarfield 5y ago

Letrec requires either laziness (which implies some sort of internal mutability, as thunks get replaced by values at some point), or "internal" mutability that may not be visible to the programmer (like in OCaml, where in a `let rec` some variables will initially be null pointers, and get updated once other definitions have run). In languages with no mutability at all (not even internal mutability like with these two features), you can't create cycles and refcounting becomes possible, but I'm not aware of non-academic general purpose languages that actually fall in this category. Esoteric functional languages like Unlambda do make that guarantee, and implementations can use a ref counter as their GC. I've written more about this here: https://terbium.io/2019/09/cyclic-immutable/ https://terbium.io/2019/09/cyclic-immutable/

macintux 5y ago
> I'm not aware of non-academic general purpose languages that actually fall in this category. Erlang?
- masklinn 5y ago
  Erlang does have some mutability (the process dictionary, and the mailbox), but the fact that the language is largely immutable is leveraged by the GC: if I remember correctly the private heap GC is a generational semi-space copying GC, but because the language is immutable it doesn’t need to have write barriers, to perform a minor collection only a scan of the stack（and process dict) is necessary to know the valid roots of the young heap.
isaacimagine 5y ago
If data is immutable and you tie the lifetime of data to a single stack frame, you only need a single bit for reference counting: whether the current frame owns the reference. Calling a function just requires setting this to bit low (some asterisks here), and all objects tied to a given frame can be collected when the frame returns.

IsTom 5y ago

Strict purely functional languages will sometimes provably introduce log n slowdown that can't be amortized away. This is certainly a trade-off. This doesn't happen when you've got mutation or laziness. One language that I'm aware which makes this tradeoff is Erlang.

foldr 5y ago
Elm is also strict and purely functional.
- masklinn 5y ago
  elm does not have its own runtime so this discussion doesn’t really apply.
  - foldr 5y ago
    Ah, I wasn't referring to the point about garbage collection further up the thread. I was just noting that Elm is another example of a strict purely functional language (and so another example of a language that gets purity in exchange for losing access to certain O(n) algorithms).
mixedmath 5y ago
When you say log n slowdown, what is n here? The length of the program? Or something completely different?
- dan-robertson 5y ago
  I think the theme is ‘you can’t do arrays; the best approximation is made of trees, hence log n in the size of the array vs 1’.
  - remexre 5y ago
    Though I think Clojure has a linear datastructure that's O(log32(n)) for all the common ops. (This is the one with all the memeing because someone called it "practically O(1)".)

jart 5y ago

Author here. Why would it? Let's have a look at Scheme letrec (or let* in Emacs Lisp) translated to pseudo-SectorLISP: (LETREC ((IS-ODD? (QUOTE (LAMBDA (X) (CAR X)))) (IS-EVEN? (QUOTE (LAMBDA (X) (NOT (IS-ODD X)))))) (IS-EVEN? (QUOTE (NIL T NIL T)))) The oldskool LISP way of writing that is: ((LAMBDA (IS-ODD? IS-EVEN?) (IS-EVEN? (QUOTE (NIL T NIL T)))) (QUOTE (LAMBDA (X) (CAR X))) (QUOTE (LAMBDA (X) (NOT (IS-ODD X))))) As far as I can tell, letrec is just a nicer syntax for the same thing. So I don't know why it should require any mutability. It works probably because LISP is dynamically scoped. Most languages and modern LISP implementations prefer different scoping models to make the Assoc() equation faster. However that comes at a cost, since it can turn the difficulty of LISP up to 11. Next thing you know, you're discovering things like the Y combinator. So I have major respect for what languages like Haskell and Scheme are doing, because it's incredibly difficult. One of the reasons why I created SectorLISP is because I wanted to have a fun bastion of simplicity when I don't need the more mature tools. SectorLISP doesn't have any kind of internal mutability last time I checked. But I have experimented with it. For example, the Peel() optimization described in the blog post is how we solve the "make Assoc() faster problem". As it's written in the blog post, it's 100% pure. But if you introduce a tiny bit of mutability, it can go even faster on benchmarks even though it doesn't change the complexity class. See https://justine.lol/sectorlisp2/fast.js https://justine.lol/sectorlisp2/fast.js

dan-robertson 5y ago
I think you’ve a trivial error in your function definitions but I don’t think it’s relevant. I think you’re right about avoiding cycles. I think the parent was talking about a let rec construction for data, e.g. in Haskell: let funky_list = 1:2:3:4:funky_list (Note that : is the cons operator). If this is allowed then you may have issues. I think the problem is perhaps that the GC won’t work if you have pointers in the opposite of the normal direction. The fix though is relatively simple: add forwarding pointers (somehow), then after copying from the ‘B’ region to the ‘C’ region you leave behind a forwarding pointer and, if you see it again in your copying, you don’t make a duplicate copy of the data. Then I think you can proceed as before. But representing forwarding pointers efficiently is hard, I suspect. Actually I think I don’t understand the GC sufficiently. Do you end up with a lot of memory usage after this or a little? ((LAMBDA (D Z) (D Z)) (QUOTE (LAMBDA (X) (COND (X ((LAMBDA (Y) (CONS Y Y)) (D (CDR X)))) ((QUOTE T) (QUOTE T))))) (QUOTE (A A A A A A A A))) This should get you a binary tree about 8 levels deep with T on every leaf, and I think it should use linear memory (in the depth of the tree) but I don’t understand how the GC avoids ending up with an exponential amount of memory being used?