Lively Linear Lisp – 'Look Ma, No Garbage!' (1992) [pdf] | Hacker News Reader

Lively Linear Lisp – 'Look Ma, No Garbage!' (1992) [pdf]

dl.acm.org

83 pointsTomte24 comments

Lively Linear Lisp – 'Look Ma, No Garbage' (1992) - https://news.ycombinator.com/item?id=20369522 - July 2019 (39 comments)

Lively Linear Lisp – 'Look Ma, No Garbage' (1991) - https://news.ycombinator.com/item?id=14248419 - May 2017 (18 comments)

I must be missing something because I don't see how this is an advance over anything. You have a FREE function, so use-after-free at runtime is still possible. Why not just have malloc and free together then, and program in C but without any lexical scoping so that "Look ma no garbage"?

[edit]

I see why C without scoping would still produce garbage:

  int* foo =  malloc(sizeof(int));
  foo = null;

Linear Lisp forces you to clean up memory. It doesn't allow complex data structures to be assigned to variables without moving the existing contents of those variables elsewhere where they can be disposed of later.

I don't know about Linear Lisp, but if you do linear types as in Wadler's "Linear Types Can Change the World"[0] then the absence of the call to free would be a compilation error.

[0] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31...

Why not inserting a call to free automatically instead of forcing you to do it manually?

Isn't that exactly why Rust needs lifetime annotation and Drop trait implementations? How could you achieve the same result without that, or without a garbage collector alternatively?

You'd use automatic reference counting, as Swift and Nim do.

Good point! I had previously assumed this was considered a form of "garbage collector" although not tracing.

Well, sort of - it adds overhead, though in the form of an extra byte/object and an extra CPU cycle when objects are allocated/deallocated to check/update the reference counts, rather than the lag spikes tracing GCs are known for.

1. When you call free matters - it does something after all!

2. You can build abstractions that call free for you. The common withX callback-style function can be better typed with linear types and call free for you, for instance.

2 would be a kind of explicit destructors/drop ?

Something like this fictional language,

    with-some-resource { res ->
         // use res as you like
    }

The with-some-resource function takes care of the resource management, while the type system takes care res doesn't escape the lambda.

What if you want to move the ownership of the resource and let the new owner eventually to dispose it?

Then withX isn't the right abstraction.

The original situation (malloc gives you a linear variable) handles what you want. A function that takes the variable but does not return it effectively "takes ownership of it" and the type system will force a free.

There's a "Linear Constraints" paper draft out there that emulates ownership and borrowing with linear types, and uses the titular new language feature to greatly improve ergonomics.

Because it is based on linear types, not affine types.

With affine types, like Rust, you can use a type zero or one times, with linear types you must use it exactly once.

So not calling free() as per all possible dataflow analysis, would be a compilation error.

By the way, this is the approach adopted by Haskell with Linear Haskell extensions.

What's the difference between PUSH and CONS?

Also, what does the free-list register do?

For the former, "push x list" is to "cons x list" as "var += 7" is to "var + 7". It's just syntactic sugar to modify a variable.

PUSH is just an alias for CONS, useful for emphasising that you're working with a stack.

The free list holds all the cons cells not in use. Note that in this machine, there is no way to create or destroy cons cells - that's the whole point! Rather, when you need to cons some values, you pull a cell off the free list and populate it (see the implementation of CONS), and when you want to throw a cons cell away, you put it back on the free list (see the implementations of POP and FREE).

The main difference, in Common Lisp at least, is that push modifies the list to add the new cell. Cons returns a new list with the cell added so the old list remains untouched.

  CL-USER> (let ((list (list 1 2 3 4)))
             (cons 5 list)
             list)
  (1 2 3 4)

  CL-USER> (let ((list (list 1 2 3 4)))
             (push 5 list )
             list)
  (5 1 2 3 4)

Careful - push is a macro which modifies the value bound to "list", but doesn't modify any of the cons cells in that list.

So no rplaca/d, just cons and setf?

Right.

Is it possible to simulate a Turing machine in Linear Lisp without using exponential memory?

Can't you represent the tape as a pair of lists of symbols? Why would that go exponential?

I agree, that should work. Thanks.

Reply on news.ycombinator.com