Hacker News Reader

Comment by MaxBarraclough | Hacker News Reader

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?)

View on HN

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

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?

Ah yes I missed that that when posting my earlier comment.

As for your example, it uses exponential memory because your example produces exponential data. The only thing I'd need to show is that SectorLISP's ABC garbage collector doesn't grow at a large rate as the input size increases. According to the simulator's "heap" statistic, your example needs 449 doublewords of memory to compute a data structure that's 266 double words in size. That seems linear, but it's not, because if you add a few A's then the gap narrows.

The cool thing about your example is that even though it's generating exponential data, that data structure doesn't require an exponential amount of memory to be stored internally. Currently the SectorLISP simulator only does things like de-duplication for DEFINEs which the simulator reports as "code" size in doublewords. However that's a friendly branch feature and the rest of the time SectorLISP just does plain "what you see is what you get" evaluation. I'm sure much more advanced techniques have been discovered since McCarthy wrote his original paper.

To be clear, my understanding of the GC is that what I wrote would use a linear amount of storage before the gc and potentially an exponential amount after. But maybe the gc runs in more places than I’d realised and so it never gets to only be linear.

I've recorded a screencast of your algorithm running in Blinkenlights. That might help intuitively explain what the ABC Garbage Collector is doing: https://justine.lol/sectorlisp2/binarytree2.mp4

> I think the parent was talking about a let rec construction for data

You know more Haskell than I do ;-)

What I had in mind were recursive and mutually recursive functions, defined with letrec, as examples of reference-cycles in functional programming.

> a let rec construction for data

Is there actually any Lisp dialect where letrec works for data? I'm not aware of such, at least where it comes to major ones (CL and common implementations of Scheme).

It would need a lazy data constructor and the lisp ones are (usually) strict. If you make cons et al lazy then letrec on data works as it does in other languages. Alternatively, make letrec wrap the values in thunks. The resulting cyclic structures are then moderately annoying to work with.

Oh, I forgot lazy Lisps. But those would probably not be considered "major".

> Alternatively, make letrec wrap the values in thunks.

Aaaand of course I forgot that as well. My bad. So basically full lexical scoping and the presence of lambda should be enough to create cyclic structures, even in the absence of mutability.

Common Lisp let’s you write e.g.

  (list-length '#1=(1 2 3 4 . #1#))

But I think that isn’t what you mean.

I don’t understand how to construct cyclic references using only letrec. Do you have a concrete example?

LETREC requires mutability in the presence of lexical scope. Otherwise it works fine in the way you describe it. Using lexical scope, IS-ODD and IS-EVEN would be bound in parallel and (LAMBDA (X) (NOT (IS-ODD X))) would close over IS-ODD before it is bound, so it would be undefined when applied inside of the outer LAMBDA.

Of course dynamic scoping will bite you earlier or later because of the upward and downward FUNARG problems. See my book (http://t3x.org/lfn/) for lots of entertaining details.

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/

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.

> I'm not aware of non-academic general purpose languages that actually fall in this category.

Erlang?

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.

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.

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.

When you say log n slowdown, what is n here? The length of the program? Or something completely different?

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’.

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)".)

Right, and updates are also O(32 log32(n)) rather than O(2log2(n)), rather than O(1) for arrays. It’s a bit more complicated when you think about cache lines being updated but mutable arrays massively win on cache

Why do you have a constant before the log term? Isn’t that completely meaningless?

It is meaningless mathematically. It’s as meaningless as the parent talking about log32(n) because of course log32(n) = log n / log 32, so there is just a constant of 1 / log 32 being put at the front.

I think the subtext is really a statement about constant factors. The parent is saying “if trees are wide then lookups are cheap” and I am saying “if trees are wide then updates may be expensive” (to update an immutable binary tree of size n, you must allocate log2(n) nodes of size (say) 3. To update a 32-ary tree you need log2(n) / log2(32) = log2(n) / 5 nodes of size 33 so, as 33/5 = 6.6 > 3, the wider tree requires more allocation for updates.)

malloc isn't typically O(n) though, so I don't think that's reasonable math?

If you are talking about Pippenger-Fischer theorem, then that's about Turing machines, not machines with RAM. Or is there another theorem I don't know about?

It's a separate theorem. I'm not quite sure where I've seen it before, but https://www.cs.princeton.edu/courses/archive/fall03/cs528/ha... seems to the right thing. Generally I've also heard it mentioned in the context of Okasaki's book about purely functional data structures.

Elm is also strict and purely functional.

elm does not have its own runtime so this discussion doesn’t really apply.

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).

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

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!)

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. 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.

Potentially cyclic values are statically known

But yes, GCs have evolved in the past decade, so these things are subject to change

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

Sure, but presumably they can't be expressed in SectorLISP.

Reply on news.ycombinator.com