Hacker News Reader

Comment by junke | Hacker News Reader

Is there an explanation of the memory allocation used? There seem to be a GC (https://github.com/eriksvedang/Carp/blob/master/src/gc.c), maybe used in the compiler only, coupled with lifetime analysis (https://github.com/eriksvedang/Carp/blob/8665a7f9a19d9347cc0...), which as far as I know is used once (https://github.com/eriksvedang/Carp/blob/6107e619d4f632acace...) in the compiler. This analysis seems tied to the manual "reset!" special form which apparently frees any existing data bound to a symbol. So, what happens when lifetime analysis cannot determine lifetime? what about stack-allocation? What should I worry about when programming in Carp w.r.t. memory?

View on HN

As far as I understand from listening to Erik talk about Carp, there is an interactive interpreter which does use GC. In contrast, the compiler generates GC-free code.

Thanks. Is this talk online? I can't find it.

Sorry, it was not recorded.

> In contrast, the compiler generates GC-free code.

Yes, but the question was how it does that. Does it reject code where it cannot reliably detect lifetimes? Or does it generate code that just does not deallocate (i.e., that leaks) objects whose lifetime the compiler can't determine? Both of these are "GC-free"...

Very simple. The compiler, written in lisp (with a GC) just generates C code, which is compiled and executed. Without any GC, it tracks the vars.

No, not simple. Analyzing an arbitrary lisp program to determine the lifetimes of all allocated structures reduces to the halting problem, so it's undecidable. You must either restrict the input program or tolerate some leaks.

>arbitrary lisp program

Well, Carp is a dialect of Lisp so it's free to impose whatever semantics it wants. It's not a dynamically-typed language (where it would indeed be impossible to statically manage memory).

Yes, only the statically compiled code is GC free.

Very simple. Each C allocated structure is allocated at the end of its C scope, and free'd at each end. Since the compiler knows the scope of each variable it's trivial.

Harder is of course the ffi, which doesn't generally know if the extern call allocated something. This is undecidable for the compiler and he has to trust the user/program. Other lisps have an attribute for those externally malloc'd args.

No, really no. First of all the values of the variables can escape their scope, e.g. when used as a return value. Secondly, some child scopes outlive their parents, e.g. closures. As the parent comment correctly points out you'd literally need to solve the halting problem to infer all the lifetimes for arbitrary code.

tracking the scope of vars is a simple compiler job (yes, also across functions, when used as byval or byref args or return values) and not a uncomputable problem. please stop spreading fud.

you only need a GC to recycle cyclic data structures, with links back to previous nodes. since Carp does not create such data structures in the generated C code the reclamation scheme can be kept simple.

heap vars to be kept global (such as closed-over upvals you are complaining about to be leaking) are kept global and released at the end. every dynamic language does keep it functions and closed over values global.

however, lexical closures are released at the end of scope, and remaining tracked heap vars are copied.

> heap vars to be kept global (such as closed-over upvals you are complaining about to be leaking) are kept global and released at the end.

In other words, they leak if the program no longer references them.

> every dynamic language does keep it functions and closed over values global.

Yes, but most of them collect closed-over values when they are no longer used. Using a garbage collector. To avoid memory leaks.

Oh my, have you ever implemented a dynamic language?

Tracked global vars are of course free'd at the end of the program. There's no leak.

2nd closed-over values inside global closures can only be freed at end. A common problem in non-GC'd languages, which can only be fixed by adding a GC. Yes. The goal here is to avoid a GC. So don't reference big memory inside closures (as upval or return val, local is OK), or undef them explicitly, as in every dynamic language.

Using local closures would fix that, but Carp has no syntax for that I think. It would need an assignment from lambdas. Most langs prefer a simple global deffun variant instead. Lua got that right. That's why lua is the preferred game VM. But being able to use the easier and more simple lisp syntax should be preferred.

> problem [...] which can only be fixed by adding a GC

Cool, we're agreed then.

The compiler does lifetime analysis, and there is a "reference borrowing" concept like in Rust.

So it rejects code for which it can't prove lifetimes. Why not just say so? There's an uncomfortable degree of beating around the bush in this thread.

Curious if semantics of this subdomain of "allowed/legal" programs will be easy to understand, or will it be "try and see on case-by-case basis if your code compiles". Still, this way or the other, probably user will have to gradually learn and build intuition, as with learning any other aspect of any programming language.

Also: will be/is the lifetime-checking done in the same way in the interpreter, even though it uses GC? Otherwise, those are in effect two, I think significantly different dialects of the language.

It will require roughly the same amount of practice as when learning Rust, so a pretty significant learning effort I'm afraid.

I'll try to do as much checking as possible in the interpreter so that the transition from interpreted to compiled code is smooth. Right now there is none though.

That's not quite how I'd put it. The documentation is pretty scarce, but if it's anything like Rust, you have to be explicit about ownership and somewhat explicit about lifetimes.

That is, it's not just "rewrite your program until the prover succeeds".

Reply on news.ycombinator.com